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 $\widetilde{\mathcal{O}}((D/r)^2T^{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.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Optimization and Control (math.OC)

arXiv:2502.16744 [cs.LG]

(or arXiv:2502.16744v3 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2502.16744 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.