Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization
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
Text
Vary et al. "Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Vary et al. "Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/vary2025aistats-blackbox/)BibTeX
@inproceedings{vary2025aistats-blackbox,
title = {{Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization}},
author = {Vary, Simon and Martínez-Rubio, David and Rebeschini, Patrick},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {4942-4950},
volume = {258},
url = {https://mlanthology.org/aistats/2025/vary2025aistats-blackbox/}
}