突破约束违规项下界，实现2维情形下更优的在线优化性能。
Breaking the $O(\sqrt{T})$ Cumulative Constraint Violation Barrier while Achieving $O(\sqrt{T})$ Static Regret in Constrained Online Convex Optimization
- 提出新算法，在二维空间中同时保证静态后悔项为√T，累计约束违规项降至T¹ᐟ³
- 在d=2时，累计约束违规从公认的Ω(√T)降至O(T¹ᐟ³)
- 对在线优化中权衡后悔与约束违规的理论边界有重要突破，适合研究优化算法的学者
研究受限在线凸优化问题：每轮学习者选定动作x_t ∈ X ⊂ R^d，随后揭示凸损失函数f_t和凸约束函数g_t（约束条件为g_t(x) ≤ 0）。目标是同时最小化相对于已知全部f_t、g_t的静态后悔和累计约束违规（CCV）。此前工作表明，当d≥2时，任何确保后悔为O(√T)的算法，其CCV至少为Ω(√T)，这是普遍认知。本文推翻该观点，证明在d=2时，Vaze与Sinha [2025] 的算法可同时实现后悔为O(√T)，且累计约束违规为O(T¹ᐟ³)。
原文摘要 · Abstract (English)
The problem of constrained online convex optimization is considered, where at each round, once a learner commits to an action $x_t \in \mathcal{X} \subset \mathbb{R}^d$, a convex loss function $f_t$ and a convex constraint function $g_t$ that drives the constraint $g_t(x)\le 0$ are revealed. The objective is to simultaneously minimize the static regret and cumulative constraint violation (CCV) compared to the benchmark that knows the loss functions and constraint functions $f_t$ and $g_t$ for all $t$ ahead of time, and chooses a static optimal action that is feasible with respect to all $g_t(x)\le 0$. In recent prior work Sinha and Vaze [2024], algorithms with simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ or (CCV of $O(1)$ in specific cases Vaze and Sinha [2025], e.g. when $d=1$) have been proposed. It is widely believed that CCV is $Ω(\sqrt{T})$ for all algorithms that ensure that regret is $O(\sqrt{T})$ with the worst case input for any $d\ge 2$. In this paper, we refute this and show that the algorithm of Vaze and Sinha [2025] simultaneously achieves regret of $O(\sqrt{T})$ regret and CCV of $O(T^{1/3})$ when $d=2$.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。