提出强凸在线优化的高概率对数后悔界,突破了传统期望界限的局限。
Logarithmic High-Probability Regret for Online Convex Optimization with Two-Point Bandit Feedback
- 基于两点反馈设计高置信度分析,融合鞅误差与强凸性
- 实现对固定比较器的对数依赖后悔上界,维度项为线性而非平方
- 适合关注理论严谨性和鲁棒性保障的算法研究者
研究在自适应对抗环境下,基于两点反馈的强凸在线凸优化问题。针对固定比较器,提出标准两点投影梯度法在概率至少1-δ下,累计后悔上界为O(dG²/μ(log T + log(1/δ)) + dGD log(1/δ) + G log T (1 + D/r))。相比原始分析中d²量级的维度项,本方法将维度依赖降为线性。核心在于同时吸收鞅误差并保持两点法的线性维度控制。通过确定性覆盖论证,获得对最小损失的全比较器保证,维持对时间T的对数依赖,仅付出覆盖数因子代价。
原文摘要 · Abstract (English)
We study online convex optimization (OCO) with two-point bandit feedback against a non-anticipating adaptive adversary. In this setting, a learner competes with an adversarial sequence of convex losses while observing each loss only through two function evaluations. For strongly convex losses, Agarwal, Dekel, and Xiao~\citeyearpar{agarwal2010optimal} proved a comparator-wise logarithmic regret bound in expectation. Consequently, by minimizing outside the probability space, their result yields a pseudo-regret guarantee of the form $\EB A_T-\min_{x\in\mathcal K}\EB L_T(x)$, where $A_T$ is the algorithm's two-query cumulative loss and $L_T(x)$ is the comparator's cumulative loss. They asked whether a logarithmic high-probability guarantee is achievable in the same two-point strongly convex setting. Our main theorem provides the corresponding fixed-comparator high-probability statement: for any comparator $x\in\mathcal K$ fixed independently of the algorithmic random directions, the standard two-point projected gradient method guarantees, with probability at least $1-δ$, a two-query regret bound of order \[ O\left(\frac{dG^2}μ\left(\log T+\log(1/δ)\right)+dGD\log(1/δ)+G\log T\left(1+\frac{D}{r}\right)\right). \] At the comparator-wise level, our leading horizon-dependent term is linear in $d$, compared with the $d^2$-type term in the original analysis of Agarwal, Dekel, and Xiao. The key ingredient is a high-confidence analysis that simultaneously absorbs the martingale error into strong convexity and preserves the linear-in-dimension estimator control of the two-point method. A deterministic covering argument then yields a realized full-comparator guarantee against $\min_{x\in\mathcal K}L_T(x)$, preserving logarithmic dependence on $T$ at the cost of the standard covering-number factor.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。