# Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints

arXiv: https://arxiv.org/abs/2501.16919 · HTML: https://mlsanity.com/paper/2501.16919/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2025.

## Built on by (most cited first, 8 of 8)

- [BAGEL: Adversarially Constrained Online Convex Optimization under Separation Oracle Access](https://mlsanity.com/paper/2502.16744/) (2025)
- [Constrained Online Convex Optimization without Slater's Condition](https://mlsanity.com/paper/2606.31480/) (2026)
- [Optimal Anytime Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2510.22579/) (2025)
- [Theoretical Foundations of Continual Learning via Drift-Plus-Penalty](https://mlsanity.com/paper/2606.08452/) (2026)
- [Optimal Bounds for Adversarial Constrained Online Convex Optimization](https://mlsanity.com/paper/2503.13366/) (2025)
- [CLASP: An online learning algorithm for Convex Losses And Squared Penalties](https://mlsanity.com/paper/2601.16072/) (2026)
- [Federated Continual Learning as a Distributed Drift-Plus-Penalty Control Problem](https://mlsanity.com/paper/2608.21539/) (2026)
- [tildeO(√T) Regret and Polylogarithmic Constraint Violation for COCO](https://mlsanity.com/paper/2610.03983/) (2026)

## Abstract (arXiv)

We study a generalization of the Online Convex Optimization (OCO) framework with time-varying adversarial constraints. In this setting, at each round, the learner selects an action from a convex decision set X, after which both a convex cost function and a convex constraint function are revealed. The objective is to design a computationally efficient learning policy that simultaneously achieves low regret with respect to the cost functions and low cumulative constraint violation (CCV) over a horizon of length T. A major computational bottleneck in standard OCO algorithms is the projection operation onto the decision set X. However, for many structured decision sets, linear optimization can be performed efficiently. Motivated by this, we propose a projection-free online conditional gradient (OCG)-based algorithm that requires only a single call to a linear optimization oracle over X per round. Our approach improves upon the state of the art for projection-free online learning with adversarial constraints, achieving tildeO(T^frac34) bounds for both regret and CCV. Our algorithm is conceptually simple. It constructs a surrogate cost function as a nonnegative linear combination of the cost and constraint functions, and feeds these surrogate costs into a novel adaptive online conditional gradient subroutine introduced in this paper. We further extend our framework to the bandit setting, where we show that a new form of surrogate loss is necessary to properly handle bandit feedback - an issue overlooked in prior work. Finally, we develop an efficient Follow-the-Perturbed-Leader (FTPL)-based algorithm, particularly well-suited for online combinatorial optimization problems with discrete actions, which also achieves O(T^frac34) regret and CCV.