Stability and Convergence Trade-off of Iterative Optimization Algorithms

Abstract

The overall performance or expected excess risk of an iterative machine learning algorithm can be decomposed into training error and generalization error. While the former is controlled by its convergence analysis, the latter can be tightly handled by algorithmic stability. The machine learning community has a rich history investigating convergence and stability separately. However, the question about the trade-off between these two quantities remains open. In this paper, we show that for any iterative algorithm at any iteration, the overall performance is lower bounded by the minimax statistical error over an appropriately chosen loss function class. This implies an important trade-off between convergence and stability of the algorithm -- a faster converging algorithm has to be less stable, and vice versa. As a direct consequence of this fundamental tradeoff, new convergence lower bounds can be derived for classes of algorithms constrained with different stability bounds. In particular, when the loss function is convex (or strongly convex) and smooth, we discuss the stability upper bounds of gradient descent (GD) and stochastic gradient descent and their variants with decreasing step sizes. For Nesterov's accelerated gradient descent (NAG) and heavy ball method (HB), we provide stability upper bounds for the quadratic loss function. Applying existing stability upper bounds for the gradient methods in our trade-off framework, we obtain lower bounds matching the well-established convergence upper bounds up to constants for these algorithms and conjecture similar lower bounds for NAG and HB. Finally, we numerically demonstrate the tightness of our stability bounds in terms of exponents in the rate and also illustrate via a simulated logistic regression problem that our stability bounds reflect the generalization errors better than the simple uniform convergence bounds for GD and NAG.

arXiv comment45 pages, 7 figures

References in corpus (1)

• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints

Cited by in corpus (26)

• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Veridical Data Science
• High probability generalization bounds for uniformly stable algorithms with nearly optimal rate
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• Federated Accelerated Stochastic Gradient Descent
• Recent advances in deep learning theory
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Path Length Bounds for Gradient Descent and Flow
• An Empirical Study of Large-Batch Stochastic Gradient Descent with Structured Covariance Noise
• On the Generalization of Stochastic Gradient Descent with Momentum
• Instability, Computational Efficiency and Statistical Accuracy
• Implicit Regularization of Accelerated Methods in Hilbert Spaces
• Generalization Bounds for Stochastic Saddle Point Problems
• Learning with Gradient Descent and Weakly Convex Losses
• Improved Learning Rates for Stochastic Optimization
• Stochastic Optimization with Laggard Data Pipelines
• Stability of SGD: Tightness Analysis and Improved Bounds
• Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learning
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
• Acceleration via Fractal Learning Rate Schedules
• Understanding Deep Architectures with Reasoning Layer
• Characterization of Excess Risk for Locally Strongly Convex Population Risk
• Algorithmic Instabilities of Accelerated Gradient Descent
• Stability Enhanced Privacy and Applications in Private Stochastic Gradient Descent