Double Queue for Constrained Online Convex Optimization: Bridging the Best-of-Two-Worlds Constraint Violations

We study Constrained Online Convex Optimization (COCO) in the two worlds of time-varying and time-invariant constraints. Our goal is to simultaneously minimize the regret to the best fixed solution in hindsight and the hard violation prohibiting any compensated constraint violations. We name the proposed COCO algorithm Double-Q, since it leverages both an original virtual Queue to construct a surrogate loss and a surrogate virtual Queue to construct a surrogate drift-plus-penalty (SDPP). This new Double-queue design enables tighter dual violation control compared to existing single-queue approaches. By minimizing an upper bound on the SDPP at each time, Double-Q achieves ${\mathcal{O}}(\sqrt T )$ regret and ${\mathcal{O}}\left({\min \left\{ {\sqrt T \log T,{T^v}} \right\}}\right)$ hard violation without requiring Slater’s condition, where v continuously quantifies constraint variation from 0 for fixed constraints to 1 for arbitrary constraints. For the first time, this hard violation bound simultaneously guarantees the best-known ${\mathcal{O}}(\sqrt T \log T)$ violation for arbitrary constraints at worst, and recovers the best-known ${\mathcal{O}}(1)$ violation for fixed constraints at best, thus bridging the best-known constraint violations in the two COCO worlds. For strongly convex loss functions, Double-Q achieves both improved ${\mathcal{O}}(\log T)$ regret and ${\mathcal{O}}\left({\min \left\{ {\sqrt {T\log T} ,{T^v}} \right\}}\right)$ hard violation. Simulation results demonstrate that Double-Q outperforms state-of-the-art COCO algorithms across various online applications.