Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization

Simon Vary, David Martínez-Rubio, Patrick Rebeschini
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:4942-4950, 2025.

Abstract

We study first-order algorithms that are uniformly stable for empirical risk minimization (ERM) problems that are convex and smooth with respect to $p$-norms, $p \geq 1$. We propose a black-box reduction method that, by employing properties of uniformly convex regularizers, turns an optimization algorithm for H{ö}lder smooth convex losses into a uniformly stable learning algorithm with optimal statistical risk bounds on the excess risk, up to a constant factor depending on $p$. Achieving a black-box reduction for uniform stability was posed as an open question by Attia and Koren (2022), which had solved the Euclidean case $p=2$. We explore applications that leverage non-Euclidean geometry in addressing binary classification problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-vary25a, title = {Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization}, author = {Vary, Simon and Mart{\'i}nez-Rubio, David and Rebeschini, Patrick}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {4942--4950}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/vary25a/vary25a.pdf}, url = {https://proceedings.mlr.press/v258/vary25a.html}, abstract = {We study first-order algorithms that are uniformly stable for empirical risk minimization (ERM) problems that are convex and smooth with respect to $p$-norms, $p \geq 1$. We propose a black-box reduction method that, by employing properties of uniformly convex regularizers, turns an optimization algorithm for H{ö}lder smooth convex losses into a uniformly stable learning algorithm with optimal statistical risk bounds on the excess risk, up to a constant factor depending on $p$. Achieving a black-box reduction for uniform stability was posed as an open question by Attia and Koren (2022), which had solved the Euclidean case $p=2$. We explore applications that leverage non-Euclidean geometry in addressing binary classification problems.} }
Endnote
%0 Conference Paper %T Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization %A Simon Vary %A David Martínez-Rubio %A Patrick Rebeschini %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-vary25a %I PMLR %P 4942--4950 %U https://proceedings.mlr.press/v258/vary25a.html %V 258 %X We study first-order algorithms that are uniformly stable for empirical risk minimization (ERM) problems that are convex and smooth with respect to $p$-norms, $p \geq 1$. We propose a black-box reduction method that, by employing properties of uniformly convex regularizers, turns an optimization algorithm for H{ö}lder smooth convex losses into a uniformly stable learning algorithm with optimal statistical risk bounds on the excess risk, up to a constant factor depending on $p$. Achieving a black-box reduction for uniform stability was posed as an open question by Attia and Koren (2022), which had solved the Euclidean case $p=2$. We explore applications that leverage non-Euclidean geometry in addressing binary classification problems.
APA
Vary, S., Martínez-Rubio, D. & Rebeschini, P.. (2025). Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:4942-4950 Available from https://proceedings.mlr.press/v258/vary25a.html.

Related Material