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

2024/12/20 by Simon Vary, Vary, Simon, David Martı́nez-Rubio +3 · 2 citations
Decision Sciences · #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2412.15956

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 ≥ 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.

Cited by

• Implicit Regularisation in Diffusion Models: An Algorithm-Dependent Generalisation Analysis
• On the necessity of adaptive regularisation:Optimal anytime online learning on \boldsymbolℓ_p-balls

Related

• Uniform Stability for First-Order Empirical Risk Minimization
• Un-regularizing: approximate proximal point and faster stochastic\n algorithms for empirical risk minimization
• Diametrical Risk Minimization: Theory and Computations
• Differentially Private Empirical Risk Minimization Revisited: Faster and More General
• Fast Rates for Empirical Risk Minimization of Strict Saddle Problems