Skip to Main content Skip to Navigation
Conference papers

On the almost sure convergence of stochastic gradient descent in non-convex problems

Abstract : This paper analyzes the trajectories of stochastic gradient descent (SGD) to help understand the algorithm's convergence properties in non-convex problems. We first show that the sequence of iterates generated by SGD remains bounded and converges with probability 1 under a very broad range of step-size schedules. Subsequently, going beyond existing positive probability guarantees, we show that SGD avoids strict saddle points/manifolds with probability 1 for the entire spectrum of step-size policies considered. Finally, we prove that the algorithm's rate of convergence to Hurwicz minimizers is O(1/n p) if the method is employed with a Θ(1/n p) step-size. This provides an important guideline for tuning the algorithm's step-size as it suggests that a cool-down phase with a vanishing step-size could lead to faster convergence; we demonstrate this heuristic using ResNet architectures on CIFAR.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03043771
Contributor : Panayotis Mertikopoulos Connect in order to contact the contributor
Submitted on : Monday, December 7, 2020 - 2:19:44 PM
Last modification on : Friday, January 21, 2022 - 3:23:00 AM
Long-term archiving on: : Monday, March 8, 2021 - 7:10:07 PM

File

NonConvexSGD-NIPS.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03043771, version 1

Citation

Panayotis Mertikopoulos, Nadav Hallak, Ali Kavis, Volkan Cevher. On the almost sure convergence of stochastic gradient descent in non-convex problems. NeurIPS 2020 - 34th International Conference on Neural Information Processing Systems, Dec 2020, Vancouver, Canada. pp.1-32. ⟨hal-03043771⟩

Share

Metrics

Les métriques sont temporairement indisponibles