# BAGEL: Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization Source: [BAGEL: Projection-Free Algorithm for Adversarially Constrained Online Convex Optimization]() Collection index: [llms.txt]() Data updated: 2026-01-30T05:00:04.719Z Authors: Yiyang Lu, Mohammad Pedramfar, Vaneet Aggarwal Published: 2025-02-23T23:18:40.000Z ## Abstract Projection-based algorithms for Constrained Online Convex Optimization (COCO) achieve optimal $\\mathcal{O}(T^{1/2})$ regret guarantees but face scalability challenges due to the computational complexity of projections. To circumvent this, projection-free methods utilizing Linear Optimization Oracles (LOO) have been proposed, albeit typically achieving slower $\\mathcal{O}(T^{3/4})$ regret rates. In this work, we examine whether the $\\mathcal{O}(T^{1/2})$ rate can be recovered in the projection-free setting by strengthening the oracle assumption. We introduce BAGEL, an algorithm utilizing a Separation Oracle (SO) that achieves $\\mathcal{O}(T^{1/2})$ regret and $\\tilde{\\mathcal{O}}(T^{1/2})$ cumulative constraint violation (CCV) for convex cost functions. Our analysis shows that by leveraging an infeasible projection via SO, we can match the time-horizon dependence of projection-based methods with $\\tilde{\\mathcal{O}}(T)$ oracle calls, provided dependence on the geometry of the action set. This establishes a specific regime where projection-free methods can attain the same convergence rates as projection-based counterparts. ## Recorded benchmark results A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage. ## Original sources and implementation [Original paper]() [PDF]()