这篇理论论文首次给出了OGD+Projection算法在高维约束优化中违反约束的下界，搞在线凸优化的人可以看看。
本文针对约束在线凸优化(COCO)问题中的OGD+Projection算法，首次证明其累积约束违反(CCV)的下界为Ω(T^{(d-1)/(2d)})，其中d为维度。已有研究表明该算法在d=2时可达O(T^{1/3})的CCV，对任意d可达O(√T)的CCV。本文的下界结果填补了理论空白，揭示了算法在高维场景下的性能极限。该结论基于Sarkar和Sinha(2026)及Balasundaram等人(2026)的前序工作。
Lower Bound on the Cumulative Constrained Violation for the OGD+Projection algorithm for Constrained Online Convex Optimization (COCO)
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.