首次证明OGD+投影算法的约束违规下界为T^{(d-1)/(2d)}
Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
- 针对约束在线凸优化问题，分析OGD+投影算法的性能极限
- 证明其累积约束违规至少为T的(d-1)/(2d)次方阶
- 适用于研究在线优化算法理论边界的研究者
研究约束在线凸优化问题，每轮学习者选定动作x_t∈X⊂R^d后，揭示凸损失函数f_t和驱动约束g_t(x)≤0的凸约束函数。目标是同时最小化与已知所有f_t、g_t的静态基准相比的静态后悔和累积约束违规（CCV）。现有最优算法OGD+Projection在d=2时达到遗憾O(√T)与CCV O(T^{1/3})，任意d时为遗憾O(√T)与CCV O(√T)。本文首次证明该算法的CCV下界为Ω(T^{(d-1)/(2d)})，这是首个此类下界结果。
原文摘要 · 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$. Currently, the best known algorithm is OGD+Projection algorithm of [Vaze and Sinha, 2025] that has simultaneous regret of $O(\sqrt{T})$ and CCV of $O(T^{1/3})$ for $d=2$ [Balasundaram et al., 2026], and simultaneous regret of $O(\sqrt{T})$ and CCV of $O(\sqrt{T})$ for any $d$ [Sarkar and Sinha, 2026]. In this paper, we show that the CCV of the OGD+Projection algorithm is $Ω(T^{\frac{d-1}{2d}})$. This is the first such lower bound result.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。