Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints

Dhruv Sarkar, Aprameyo Chakrabartty, Subhamon Supantha, Palash Dey, Abhishek Sinha
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:298-306, 2026.

Abstract

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 $\mathcal{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 $\mathcal{X}$. However, for many structured decision sets, linear optimization can be performed efficiently. Motivated by this, we propose a \emph{projection-free} online conditional gradient (OCG)-based algorithm that requires only a single call to a linear optimization oracle over $\mathcal{X}$ per round. Our approach improves upon the state of the art for projection-free online learning with adversarial constraints, achieving $\tilde{O}(T^{3/4})$ 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^{3/4})$ regret and CCV.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-sarkar26a, title = { Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints }, author = {Sarkar, Dhruv and Chakrabartty, Aprameyo and Supantha, Subhamon and Dey, Palash and Sinha, Abhishek}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {298--306}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/sarkar26a/sarkar26a.pdf}, url = {https://proceedings.mlr.press/v300/sarkar26a.html}, abstract = { 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 $\mathcal{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 $\mathcal{X}$. However, for many structured decision sets, linear optimization can be performed efficiently. Motivated by this, we propose a \emph{projection-free} online conditional gradient (OCG)-based algorithm that requires only a single call to a linear optimization oracle over $\mathcal{X}$ per round. Our approach improves upon the state of the art for projection-free online learning with adversarial constraints, achieving $\tilde{O}(T^{3/4})$ 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^{3/4})$ regret and CCV. } }
Endnote
%0 Conference Paper %T Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints %A Dhruv Sarkar %A Aprameyo Chakrabartty %A Subhamon Supantha %A Palash Dey %A Abhishek Sinha %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-sarkar26a %I PMLR %P 298--306 %U https://proceedings.mlr.press/v300/sarkar26a.html %V 300 %X 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 $\mathcal{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 $\mathcal{X}$. However, for many structured decision sets, linear optimization can be performed efficiently. Motivated by this, we propose a \emph{projection-free} online conditional gradient (OCG)-based algorithm that requires only a single call to a linear optimization oracle over $\mathcal{X}$ per round. Our approach improves upon the state of the art for projection-free online learning with adversarial constraints, achieving $\tilde{O}(T^{3/4})$ 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^{3/4})$ regret and CCV.
APA
Sarkar, D., Chakrabartty, A., Supantha, S., Dey, P. & Sinha, A.. (2026). Projection-free Algorithms for Online Convex Optimization with Adversarial Constraints . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:298-306 Available from https://proceedings.mlr.press/v300/sarkar26a.html.

Related Material