SGD Converges to Global Minimum in Deep Learning via Star-convex Path
arXiv:1901.00451
Abstract
Stochastic gradient descent (SGD) has been found to be surprisingly effective in training a variety of deep neural networks. However, there is still a lack of understanding on how and why SGD can train these complex networks towards a global minimum. In this study, we establish the convergence of SGD to a global minimum for nonconvex optimization problems that are commonly encountered in neural network training. Our argument exploits the following two important properties: 1) the training loss can achieve zero value (approximately), which has been widely observed in deep learning; 2) SGD follows a star-convex path, which is verified by various experiments in this paper. In such a context, our analysis shows that SGD, although has long been considered as a randomized algorithm, converges in an intrinsically deterministic manner to a global minimum.
arXiv commentICLR2019
References in corpus (3)
Cited by in corpus (12)
- A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
- Linear Convergence of Adaptive Stochastic Gradient Descent
- A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems
- SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolation
- Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
- Training Neural Networks for and by Interpolation
- Improved Learning Rates for Stochastic Optimization
- Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
- RNN Training along Locally Optimal Trajectories via Frank-Wolfe Algorithm
- Training Deep Neural Networks via Branch-and-Bound
- Neural Network Training Techniques Regularize Optimization Trajectory: An Empirical Study
- Adaptive versus Standard Descent Methods and Robustness Against Adversarial Examples