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

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.