BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access

Abstract

In adversarial Constrained Online Convex Optimization (COCO), a learner selects actions from a fixed convex set while seeking both low regret and low cumulative constraint violation (CCV) under time-varying constraints. We ask what performance is achievable when the action set is accessed through a Separation Oracle (SO), rather than an exact Projection Oracle (PO) or a Linear Optimization Oracle (LOO). We introduce $\mathtt{BAGEL}$, which combines a Lyapunov-weighted surrogate loss, blocked adaptive online gradient descent, and an infeasible-projection procedure implemented with an SO. For convex costs and any $\beta \in (0,1/2]$, $\mathtt{BAGEL}$ achieves $\mathcal{O}(T^{1-\beta })$ regret and $\mathcal{O}(T^{1-\beta }\log T)$ cumulative violation using $\tilde{\mathcal{O}}((D/r{)}^2{T}^{2\beta })$ SO calls. At $\beta =1/2$, this gives $\mathcal{O}(\sqrt{T})$ regret and $\mathcal{O}(\sqrt{T}\log T)$ violation with a near-linear number of SO calls. The result is an access oracle based guarantee, with computational relevance depends on the geometry of the action set and the cost of implementing its SO.