Black-Box Uniform Stability for Non-Euclidean Empirical Risk Minimization
This work addresses a theoretical challenge in machine learning for researchers, providing a solution to uniform stability in non-Euclidean settings, which is incremental as it extends prior Euclidean results.
The paper tackles the problem of achieving uniform stability for empirical risk minimization in non-Euclidean norms by proposing a black-box reduction method that converts optimization algorithms into stable learning algorithms with optimal statistical risk bounds, solving an open question from prior work.
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.