Generalization Bounds for Uniformly Stable Algorithms

Abstract

Uniform stability of a learning algorithm is a classical notion of algorithmic stability introduced to derive high-probability bounds on the generalization error (Bousquet and Elisseeff, 2002). Specifically, for a loss function with range bounded in $[0,1]$, the generalization error of a $\gamma$-uniformly stable learning algorithm on $n$ samples is known to be within $O((\gamma +1/n)\sqrt{n\log (1/\delta )})$ of the empirical error with probability at least $1-\delta$. Unfortunately, this bound does not lead to meaningful generalization bounds in many common settings where $\gamma \ge 1/\sqrt{n}$. At the same time the bound is known to be tight only when $\gamma =O(1/n)$. We substantially improve generalization bounds for uniformly stable algorithms without making any additional assumptions. First, we show that the bound in this setting is $O(\sqrt{(\gamma +1/n)\log (1/\delta )})$ with probability at least $1-\delta$. In addition, we prove a tight bound of $O({\gamma }^2+1/n)$ on the second moment of the estimation error. The best previous bound on the second moment is $O(\gamma +1/n)$. Our proofs are based on new analysis techniques and our results imply substantially stronger generalization guarantees for several well-studied algorithms.

Appeared in Neural Information Processing Systems (NeurIPS), 2018

Cited by in corpus (16)

• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• On the cross-validation bias due to unsupervised pre-processing
• Sharper bounds for uniformly stable algorithms
• Reasoning About Generalization via Conditional Mutual Information
• Toward Better Generalization Bounds with Locally Elastic Stability
• Hypothesis Set Stability and Generalization
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Global Convergence of Three-layer Neural Networks in the Mean Field Regime
• Target-Embedding Autoencoders for Supervised Representation Learning
• Improved Learning Rates for Stochastic Optimization
• An Exponential Efron-Stein Inequality for Lq Stable Learning Rules
• Explaining generalization in deep learning: progress and fundamental limits
• Algorithmic Instabilities of Accelerated Gradient Descent
• Multi-fidelity Stability for Graph Representation Learning
• A Tight Lower Bound for Uniformly Stable Algorithms
• Stability Enhanced Privacy and Applications in Private Stochastic Gradient Descent