Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization

Abstract

The success of deep learning has led to a rising interest in the generalization property of the stochastic gradient descent (SGD) method, and stability is one popular approach to study it. Existing works based on stability have studied nonconvex loss functions, but only considered the generalization error of the SGD in expectation. In this paper, we establish various generalization error bounds with probabilistic guarantee for the SGD. Specifically, for both general nonconvex loss functions and gradient dominant loss functions, we characterize the on-average stability of the iterates generated by SGD in terms of the on-average variance of the stochastic gradients. Such characterization leads to improved bounds for the generalization error for SGD. We then study the regularized risk minimization problem with strongly convex regularizers, and obtain improved generalization error bounds for proximal SGD. With strongly convex regularizers, we further establish the generalization error bounds for nonconvex loss functions under proximal SGD with high-probability guarantee, i.e., exponential concentration in probability.

References in corpus (12)

• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Robust Large Margin Deep Neural Networks
• Information-theoretic analysis of generalization capability of learning algorithms
• Spectrally-normalized margin bounds for neural networks
• Data-Dependent Stability of Stochastic Gradient Descent
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Optimal Rates for Multi-pass Stochastic Gradient Methods
• A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descent
• Convergence Analysis of Proximal Gradient with Momentum for Nonconvex Optimization
• Online Learning, Stability, and Stochastic Gradient Descent
• Gradient Diversity: a Key Ingredient for Scalable Distributed Learning
• Ensemble Robustness and Generalization of Stochastic Deep Learning Algorithms

Cited by in corpus (10)

• Recent advances in deep learning theory
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Stagewise Training Accelerates Convergence of Testing Error Over SGD
• Improved Learning Rates for Stochastic Optimization
• GT-STORM: Taming Sample, Communication, and Memory Complexities in Decentralized Non-Convex Learning
• Time-Delay Momentum: A Regularization Perspective on the Convergence and Generalization of Stochastic Momentum for Deep Learning
• Distributed SGD Generalizes Well Under Asynchrony
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• Why Does Multi-Epoch Training Help?
• Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors