arXiv:2605.26373cs.LGmath.OC2026-05

在线学习中,非凸损失经重参数后变凸,梯度下降可实现最优后悔率。

Online Learning on Hidden-Convex Losses via Algorithmic Equivalence: Optimal Regret, Geometric Barrier, and Bandit Feedback

  • 通过更精细的算法等价分析,证明梯度下降在隐凸损失下可达到√T后悔率。
  • 首次建立海森矩阵兼容性为必要条件,扩展了可适用的重参数化类型。
  • 适用于带单点反馈的强化学习场景,带球形平滑的带宽梯度下降达T^{3/4}期望后悔率。

我们研究具有隐凸损失的对抗性在线学习,即非凸损失经非线性重参数化后变为凸。Ghai、Lu 和 Hazan(2022)在几何与光滑性假设下证明,在线梯度下降(OGD)在这些非凸损失上近似模拟在线镜像下降(OMD)于底层凸损失,使用合适正则项时可得 𝒪(T^{2/3}) 后悔率。他们未解决的关键问题是:是否能在该隐凸设置中恢复凸优化中的最优 Θ(√T) 后悔率?本文给出肯定回答。具体而言,借助更精确的离散时间算法等价论证,我们在相同假设下证明 OGD 可实现 𝒪(√T) 后悔率,与对抗凸优化的最坏情况最优率一致。同时,我们澄清了该等价关系所需的几何结构,将先前的对角雅可比充分条件替换为必要且充分的海森矩阵兼容性条件,从而扩大了允许的重参数化类。我们进一步提供紧致后悔率下界,表明海森矩阵兼容性假设是关键;当其不成立时,可构造光滑重参数化及对抗性序列,使 OGD 遭受 Ω(T) 后悔率。最后,我们将分析拓展至单点带宽反馈情形,证明带球形平滑的带宽梯度下降具有 𝒪(T^{3/4}) 期望后悔率,匹配其在凸损失下的经典速率。

原文摘要 · Abstract (English)

We study adversarial online learning with hidden-convex losses, i.e., nonconvex losses that become convex after a nonlinear reparameterization. Ghai, Lu and Hazan (2022) proved that, under geometric and smoothness assumptions, online gradient descent (OGD) on such nonconvex losses approximately simulates online mirror descent (OMD) on the underlying convex losses with a suitable regularizer, yielding $\mathcal{O}(T^{2/3})$ regret. They left open whether the optimal $Θ(\sqrt{T})$ regret from online convex optimization can be recovered in this hidden-convex setting. We answer this question affirmatively. More specifically, via a sharper discrete-time algorithmic equivalence argument, we prove that OGD achieves $\mathcal{O}(\sqrt{T})$ regret under the same assumptions, matching the optimal worst-case rate for adversarial online convex optimization. We also address another open question of Ghai, Lu and Hazan (2022) by clarifying the geometry required for this algorithmic equivalence. We replace the diagonal-Jacobian sufficient condition with a necessary-and-sufficient Hessian compatibility condition, thereby expanding the class of admissible reparameterizations. We complement our tight regret bound with a lower bound showing that the Hessian compatibility assumption is essential for OGD; when it fails, we construct a smooth reparameterization and an adversarial sequence of hidden-convex losses for which OGD suffers $Ω(T)$ regret. Finally, we extend our analysis to one-point bandit feedback and prove a $\mathcal{O}(T^{3/4})$ expected regret bound for bandit OGD with spherical smoothing, matching its classical rate on convex losses.

在线学习隐凸优化后悔率分析带宽反馈

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。