Uniform Stability for First-Order Empirical Risk Minimization
This work addresses the need for stable optimization algorithms to ensure generalization in machine learning, with incremental improvements over prior open problems.
The paper tackles the problem of designing uniformly stable first-order optimization algorithms for empirical risk minimization, achieving a nearly optimal algorithm with convergence rate O~(1/T^2) and uniform stability O(T^2/n) in Euclidean geometry, and a variant with rate O~(1/T) and stability O(T/n) for more general geometries.
We consider the problem of designing uniformly stable first-order optimization algorithms for empirical risk minimization. Uniform stability is often used to obtain generalization error bounds for optimization algorithms, and we are interested in a general approach to achieve it. For Euclidean geometry, we suggest a black-box conversion which given a smooth optimization algorithm, produces a uniformly stable version of the algorithm while maintaining its convergence rate up to logarithmic factors. Using this reduction we obtain a (nearly) optimal algorithm for smooth optimization with convergence rate $\widetilde{O}(1/T^2)$ and uniform stability $O(T^2/n)$, resolving an open problem of Chen et al. (2018); Attia and Koren (2021). For more general geometries, we develop a variant of Mirror Descent for smooth optimization with convergence rate $\widetilde{O}(1/T)$ and uniform stability $O(T/n)$, leaving open the question of devising a general conversion method as in the Euclidean case.