Convergence diagnostics for stochastic gradient descent with constant step size
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.
Code (0)
등록된 구현이 없습니다.
Tasks
DiagnosticStochastic OptimizationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
The convergence behavior of Stochastic Gradient Descent (SGD) crucially depends on the stepsize configuration. When using a constant stepsize, the SGD iterates form a Markov chain, enjoying fast convergence during the in…
DiagnosticGlobal Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
Stochastic gradient descent (SGD) on a low-rank factorization is commonly employed to speed up matrix problems including matrix completion, subspace tracking, and SDP relaxation. In this paper, we exhibit a step size sch…
Matrix CompletionError Lower Bounds of Constant Step-size Stochastic Gradient Descent
Stochastic Gradient Descent (SGD) plays a central role in modern machine learning. While there is extensive work on providing error upper bound for SGD, not much is known about SGD error lower bound. In this paper, we st…
BIG-bench Machine LearningExponential Convergence of (Stochastic) Gradient Descent for Separable Logistic Regression
Gradient descent and stochastic gradient descent are central to modern machine learning, yet their behavior under large step sizes remains theoretically unclear. Recent work suggests that acceleration often arises near t…
On the influence of stochastic roundoff errors and their bias on the convergence of the gradient descent method with low-precision floating-point computation
When implementing the gradient descent method in low precision, the employment of stochastic rounding schemes helps to prevent stagnation of convergence caused by the vanishing gradient effect. Unbiased stochastic roundi…