提出新算法实现每步都满足约束且保持最优后悔值。
Constrained Online Convex Optimization with Polyak Feasibility Steps
- 用Polyak步长法在梯度下降后追加约束修正步骤
- 保证每一步行动都满足约束，且后悔值为O(√T)
- 适合对实时安全性要求高的在线优化场景
本文研究具有固定约束函数 $g : \mathbb{R}^d \rightarrow \mathbb{R}$ 的在线凸优化问题。已有工作仅能保证累计约束满足 $\sum_{t=1}^{T} g(x_t) \leq 0$ 与 $O(\sqrt{T})$ 的后悔值，且仅可访问所选动作处的约束值与次梯度 $g(x_t), \partial g(x_t)$。本文在相同信息条件下，首次实现任意时刻约束满足 $g(x_t) \leq 0 \ \forall t \in [T]$，同时保持 $O(\sqrt{T})$ 推荐值。该成果源于采用 Polyak 可行性步长：在每次在线梯度下降后，以著名的 Polyak 步长进行约束函数的次梯度下降。数值实验验证了该方法的有效性。
原文摘要 · Abstract (English)
In this work, we study online convex optimization with a fixed constraint function $g : \mathbb{R}^d \rightarrow \mathbb{R}$. Prior work on this problem has shown $O(\sqrt{T})$ regret and cumulative constraint satisfaction $\sum_{t=1}^{T} g(x_t) \leq 0$, while only accessing the constraint value and subgradient at the played actions $g(x_t), \partial g(x_t)$. Using the same constraint information, we show a stronger guarantee of anytime constraint satisfaction $g(x_t) \leq 0 \ \forall t \in [T]$, and matching $O(\sqrt{T})$ regret guarantees. These contributions are thanks to our approach of using Polyak feasibility steps to ensure constraint satisfaction, without sacrificing regret. Specifically, after each step of online gradient descent, our algorithm applies a subgradient descent step on the constraint function where the step-size is chosen according to the celebrated Polyak step-size. We further validate this approach with numerical experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。