New algorithm balances speed and feasibility in constrained online optimization problems

A team of researchers has developed BAGEL, a new algorithmic approach to a core challenge in online learning: making decisions from a constrained set of actions while minimizing both performance loss and rule violations, all under adversarial conditions.

The Problem#

In adversarial Constrained Online Convex Optimization (COCO), a decision-maker must repeatedly select actions from a fixed convex set—say, a geometric region in high-dimensional space. The catch: the goals and constraints change over time, imposed by an adversary. The learner must achieve two objectives simultaneously: keep regret (cumulative loss relative to the best fixed action) low, and keep cumulative constraint violation (how much the rules are broken over all rounds) low.

Most prior work assumes strong access to the action set—either through exact projections onto it, or by solving linear programs over it. But these oracles can be computationally expensive for complex geometries. The question becomes: can we do better with weaker assumptions?

BAGEL's Design and Guarantees#

BAGEL combines three components: a Lyapunov-weighted surrogate loss to balance regret and constraint violation, a blocked adaptive online gradient descent strategy for stable learning, and an infeasible-projection procedure that relies only on a Separation Oracle—a tool that can check whether a point lies inside the constraint set and, if not, provide a hyperplane separating it from the interior.

For convex costs and a tunable parameter β in the range (0, 1/2], the algorithm delivers:

• $\mathcal{O}(T^{1-\beta})$ regret
• $\mathcal{O}(T^{1-\beta}\log T)$ cumulative constraint violation
• $\widetilde{\mathcal{O}}((D/r)^2T^{2\beta})$ separation oracle calls

When β is set to 1/2, BAGEL achieves $\mathcal{O}(\sqrt{T})$ regret and $\mathcal{O}(\sqrt{T}\log T)$ violation while using a near-linear number of oracle calls—a substantial improvement for problems where separation is more tractable than projection.

Why It Matters#

The result is access-oracle-based, meaning the practical value depends on two factors: the geometry of the action set (which determines the dimension D and the "radius" r) and the actual cost of implementing its separation oracle. For many real-world constraint systems, checking feasibility and finding separating hyperplanes can be orders of magnitude faster than exact projection. This opens the door to scalable online learning in high-dimensional domains with complex constraint structures.