BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access

arXiv:2502.16744v3 Announce Type: replace 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 etain(0,1/2], mathtt{BAGEL} achieves O(T^{1-eta}) regret and O(T^{1-eta}log T) cumulative violation using widetilde{O}((D/r)^2T^{2eta}) SO calls. At eta=1/2, this gives O(sqrt{T}) regret and 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.

Related

• Improved Guarantees for Constrained Online Convex Optimization via Self-Contraction
• Polyhedral Instability Governs Regret in Online Learning
• Constrained Online Convex Optimization without Slater's Condition

Source: arXiv cs.LG | 2026-08-27