Convergence diagnostics for stochastic gradient descent with constant step size

Abstract

Many iterative procedures in stochastic optimization exhibit a transient phase followed by a stationary phase. During the transient phase the procedure converges towards a region of interest, and during the stationary phase the procedure oscillates in that region, commonly around a single point. In this paper, we develop a statistical diagnostic test to detect such phase transition in the context of stochastic gradient descent with constant learning rate. We present theory and experiments suggesting that the region where the proposed diagnostic is activated coincides with the convergence region. For a class of loss functions, we derive a closed-form solution describing such region. Finally, we suggest an application to speed up convergence of stochastic gradient descent by halving the learning rate each time stationarity is detected. This leads to a new variant of stochastic gradient descent, which in many settings is comparable to state-of-art.

Accepted to Artificial Intelligence and Statistics, 2018

Cited by in corpus (4)

• Path integral contour deformations for observables in $SU(N)$ gauge theory
• Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chains
• HiGrad: Uncertainty Quantification for Online Learning and Stochastic Approximation
• Drill the Cork of Information Bottleneck by Inputting the Most Important Data