CLASP: Online learning algorithms for Convex Losses And Squared Penalties

Ricardo N. Ferreira, Joao Xavier, Claudia Soares
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:30861-30878, 2026.

Abstract

Addressing Constrained Online Convex Optimization (COCO), we introduce CLASP (Convex Losses And Squared Penalties), a framework that minimizes cumulative loss together with squared constraint violations. We propose two variants of CLASP, CLASP-I and CLASP-F, allowing for a joint or separate handling of the static decision set and the time-varying constraints, a decoupling flexibility that affords simpler implementations when projections onto the static decision set are easy. Our theoretical analysis departs from prior work by fully leveraging the variety of cutter operators, and contraction properties such as the strongly quasi-nonexpansiveness, a proof strategy not previously applied in this setting. For convex losses, both CLASP algorithms achieve regret $O\left(T^{\max{\beta,1-\beta}}\right)$ and cumulative squared penalty $O\left(T^{{1-\beta}}\right)$ for any $\beta \in (0,1)$. Most importantly, for strongly convex problems, we provide the first logarithmic guarantees on both regret and cumulative squared penalty: In the strongly convex case, both CLASP algorithms guarantee that the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ferreira26a, title = {{CLASP}: Online learning algorithms for Convex Losses And Squared Penalties}, author = {Ferreira, Ricardo N. and Xavier, Joao and Soares, Claudia}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {30861--30878}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ferreira26a/ferreira26a.pdf}, url = {https://proceedings.mlr.press/v306/ferreira26a.html}, abstract = {Addressing Constrained Online Convex Optimization (COCO), we introduce CLASP (Convex Losses And Squared Penalties), a framework that minimizes cumulative loss together with squared constraint violations. We propose two variants of CLASP, CLASP-I and CLASP-F, allowing for a joint or separate handling of the static decision set and the time-varying constraints, a decoupling flexibility that affords simpler implementations when projections onto the static decision set are easy. Our theoretical analysis departs from prior work by fully leveraging the variety of cutter operators, and contraction properties such as the strongly quasi-nonexpansiveness, a proof strategy not previously applied in this setting. For convex losses, both CLASP algorithms achieve regret $O\left(T^{\max{\beta,1-\beta}}\right)$ and cumulative squared penalty $O\left(T^{{1-\beta}}\right)$ for any $\beta \in (0,1)$. Most importantly, for strongly convex problems, we provide the first logarithmic guarantees on both regret and cumulative squared penalty: In the strongly convex case, both CLASP algorithms guarantee that the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.} }
Endnote
%0 Conference Paper %T CLASP: Online learning algorithms for Convex Losses And Squared Penalties %A Ricardo N. Ferreira %A Joao Xavier %A Claudia Soares %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ferreira26a %I PMLR %P 30861--30878 %U https://proceedings.mlr.press/v306/ferreira26a.html %V 306 %X Addressing Constrained Online Convex Optimization (COCO), we introduce CLASP (Convex Losses And Squared Penalties), a framework that minimizes cumulative loss together with squared constraint violations. We propose two variants of CLASP, CLASP-I and CLASP-F, allowing for a joint or separate handling of the static decision set and the time-varying constraints, a decoupling flexibility that affords simpler implementations when projections onto the static decision set are easy. Our theoretical analysis departs from prior work by fully leveraging the variety of cutter operators, and contraction properties such as the strongly quasi-nonexpansiveness, a proof strategy not previously applied in this setting. For convex losses, both CLASP algorithms achieve regret $O\left(T^{\max{\beta,1-\beta}}\right)$ and cumulative squared penalty $O\left(T^{{1-\beta}}\right)$ for any $\beta \in (0,1)$. Most importantly, for strongly convex problems, we provide the first logarithmic guarantees on both regret and cumulative squared penalty: In the strongly convex case, both CLASP algorithms guarantee that the regret is upper bounded by $O( \log T )$ and the cumulative squared penalty is also upper bounded by $O( \log T )$.
APA
Ferreira, R.N., Xavier, J. & Soares, C.. (2026). CLASP: Online learning algorithms for Convex Losses And Squared Penalties. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:30861-30878 Available from https://proceedings.mlr.press/v306/ferreira26a.html.

Related Material