High probability generalization bounds for uniformly stable algorithms with nearly optimal rate

Abstract

Algorithmic stability is a classical approach to understanding and analysis of the generalization error of learning algorithms. A notable weakness of most stability-based generalization bounds is that they hold only in expectation. Generalization with high probability has been established in a landmark paper of Bousquet and Elisseeff (2002) albeit at the expense of an additional $\sqrt{n}$ factor in the bound. Specifically, their bound on the estimation error of any $\gamma$-uniformly stable learning algorithm on $n$ samples and range in $[0,1]$ is $O(\gamma \sqrt{n\log (1/\delta )}+\sqrt{\log (1/\delta )/n})$ with probability $\ge 1-\delta$. The $\sqrt{n}$ overhead makes the bound vacuous in the common settings where $\gamma \ge 1/\sqrt{n}$. A stronger bound was recently proved by the authors (Feldman and Vondrak, 2018) that reduces the overhead to at most $O(n^{1/4})$. Still, both of these results give optimal generalization bounds only when $\gamma =O(1/n)$. We prove a nearly tight bound of $O(\gamma \log (n)\log (n/\delta )+\sqrt{\log (1/\delta )/n})$ on the estimation error of any $\gamma$-uniformly stable algorithm. It implies that for algorithms that are uniformly stable with $\gamma =O(1/\sqrt{n})$, estimation error is essentially the same as the sampling error. Our result leads to the first high-probability generalization bounds for multi-pass stochastic gradient descent and regularized ERM for stochastic convex problems with nearly optimal rate --- resolving open problems in prior work. Our proof technique is new and we introduce several analysis tools that might find additional applications.

this is a follow-up to and has minor text overlap with arXiv:1812.09859; v2: minor revision following acceptance for presentation at COLT 2019

References in corpus (12)

• Why Random Reshuffling Beats Stochastic Gradient Descent
• Data-Dependent Stability of Stochastic Gradient Descent
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Stability and Convergence Trade-off of Iterative Optimization Algorithms
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Generalization Bounds for Uniformly Stable Algorithms
• Tight Analyses for Non-Smooth Stochastic Gradient Descent
• Without-Replacement Sampling for Stochastic Gradient Methods: Convergence Results and Application to Distributed Optimization
• Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Back
• Privacy-preserving Prediction
• Stability revisited: new generalisation bounds for the Leave-one-Out
• Subgaussian Tail Bounds via Stability Arguments

Cited by in corpus (20)

• Private Stochastic Convex Optimization with Optimal Rates
• A Selective Overview of Deep Learning
• Recent theoretical advances in decentralized distributed convex optimization
• Sharper bounds for uniformly stable algorithms
• Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process
• Reasoning About Generalization via Conditional Mutual Information
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Generalization bounds for deep learning
• Near-Optimal Hyperfast Second-Order Method for convex optimization and its Sliding
• PAC learning with stable and private predictions
• Train simultaneously, generalize better: Stability of gradient-based minimax learners
• Robustness, Privacy, and Generalization of Adversarial Training
• Generalization bounds for learning under graph-dependence: A survey
• Stochastic Approximation versus Sample Average Approximation for population Wasserstein barycenters
• Gentle Local Robustness implies Generalization
• The Cost of a Reductions Approach to Private Fair Optimization
• Parallel and Distributed algorithms for ML problems
• Generalization Bounds for High-dimensional M-estimation under Sparsity Constraint
• A Tight Lower Bound for Uniformly Stable Algorithms
• Dimension Free Generalization Bounds for Non Linear Metric Learning