提出一种无需梯度的在线优化方法，可在非欧几何下实现高概率最优性能。
High-probability zeroth-order online convex optimisation beyond Euclidean geometry
- 基于锥测度采样构造随机梯度估计器，适配任意p/q/r范数空间。
- 在q∈[1,2]时达到理论最优率，且保证时间一致的高概率收敛。
- 适用于无梯度场景，特别适合数据驱动的实时决策系统。
研究带有ℓ_q-Lipschitz损失、ℓ_p-正则化FTRL及基于ℓ_r-球面锥测度采样的随机两点差分梯度估计器的在线凸优化问题。针对均值为凸的随机Lipschitz损失，证明了所有p,q,r∈[1,∞]下的统一高概率遗憾界。分析依赖于对偶FTRL范数中梯度估计器的全阶矩界，实现二次变差的时间一致控制。算法具备即时性与数据自适应性；在先前研究的特例中，其率恢复已知期望保证，并提升至时间一致高概率形式。结合恒定概率的下界，结果在q∈[1,2]时确立了最优性，揭示出q>2时存在的内在差距，源于估计器本身的局限。
原文摘要 · Abstract (English)
We study online convex optimisation with $\ell_q$-Lipschitz losses, $\ell_p$-regularised FTRL, and randomised two-point finite-difference gradient estimators based on cone-measure sampling from $\ell_r$-spheres. For random Lipschitz losses whose mean is convex, we prove unified high-probability regret bounds for all $p,q,r \in [1,\infty]$. The analysis is driven by all-moment bounds for the gradient estimator in the dual FTRL norm, yielding time-uniform control of the quadratic variation. The algorithm is anytime and data-driven; in the special cases previously studied, its rates recover the known in-expectation guarantees while strengthening them to time-uniform high probability. Together with constant-probability lower bounds, these results establish optimality for $q\in[1,2]$ under appropriate sampling geometry, and expose a gap for $q>2$ that appears intrinsic to the estimators themselves.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。