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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2024.

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

- [Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis](https://mlsanity.com/paper/2507.03756/) (2025)
- [On the necessity of adaptive regularisation:Optimal anytime online learning on boldsymbolℓp-balls](https://mlsanity.com/paper/2506.19752/) (2025)
- [Mirror Descent Beyond Euclidean Stability: An Exponential Separation in Initialization Sensitivity](https://mlsanity.com/paper/2606.11431/) (2026)

## Abstract (arXiv)

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 ≥ 1. We propose a black-box reduction method that, by employing properties of uniformly convex regularizers, turns an optimization algorithm for H"older 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.