用预测梯度提升带宽凸优化性能,实现自适应误差控制。
Bandit Convex Optimization with Gradient Prediction Adaptivity
- 设计新型方差缩减梯度估计器,其方差由预测误差决定。
- 理论证明最优后悔界为 $O\big(\sqrt{d\,\mathbb{E}[S_T]}\big)$,与预测误差正相关。
- 适用于未知环境和非平稳场景,适合在线学习与强化学习研究者。
带宽凸优化(BCO)是一种局部反馈的在线学习框架,学习者每轮仅观测所选决策点的损失值。本文探讨在给定梯度预测 $m_t$ 时,能否通过乐观预测实现自适应的最坏情况后悔界。目标是建立依赖于累积预测误差 $S_T = \sum_{t=1}^T \|\nabla f_t(x_t) - m_t\|^2$ 的后悔界。首先证明一个负结果:在单点反馈下,即使 $S_T = o(T)$,仍存在 $Ω(\sqrt{T})$ 的不可避免后悔下界,表明梯度估计方差会掩盖准确预测的优势。为此,提出两阶段方差缩减乐观梯度下降(TP-VR-OPT),用于两点反馈设置。其核心是新的方差缩减梯度估计器,其方差随预测误差而非梯度范数增长,从而获得 $O\big(\sqrt{d\,\mathbb{E}[S_T]}\big)$ 的后悔界,其中 $d$ 为决策维度。进一步建立了信息论下界 $Ω(\sqrt{\mathbb{E}[S_T]})$,刻画了最佳可实现的预测自适应后悔界,并表明 TP-VR-OPT 在 $\sqrt{d}$ 因子内最优。还提出了无需先验知识 $\mathbb{E}[S_T]$ 或 $T$ 的自适应变体,并将框架扩展至非平稳环境,实现了同时适应预测误差与比较路径长度的动态后悔保证。
原文摘要 · Abstract (English)
Bandit convex optimization (BCO) is a fundamental online learning framework with partial feedback, where the learner observes only the loss incurred at the chosen decision point in each round. In this work, we investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner. Specifically, given gradient predictions $m_t$, we seek regret bounds that scale with the cumulative prediction error $S_T=\sum_{t=1}^T \|\nabla f_t(x_t)-m_t\|^2.$ We first establish a negative result: under the single-point feedback protocol, an unavoidable $Ω(\sqrt{T})$ regret lower bound persists even when $S_T=o(T)$, showing that the variance of gradient estimation fundamentally obscures the benefit of accurate predictions. To overcome this barrier, we propose \emph{Two-Point Variance-Reduced Optimistic Gradient Descent} (TP-VR-OPT) for the two-point feedback setting. The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm. This yields a regret bound of $O\big(\sqrt{d\,\mathbb{E}[S_T]}\big),$ where $d$ is the decision dimension. Complementing this result, we establish an information-theoretic lower bound that scales as $Ω(\sqrt{\mathbb{E}[S_T]})$, providing a fundamental characterization of the best achievable prediction-adaptive regret and showing that TP-VR-OPT is optimal up to a factor of $\sqrt d$. We further develop adaptive variants that eliminate the need for prior knowledge of $\mathbb{E}[S_T]$ or the horizon $T$, and extend our framework to non-stationary environments, establishing dynamic regret guarantees that adapt simultaneously to the cumulative prediction error and the comparator path length.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。