Coupling-based Convergence Diagnostic and Stepsize Scheme for Stochastic Gradient Descent
This addresses the challenge of tuning stepsizes in SGD for machine learning practitioners, offering a robust method to improve convergence efficiency, though it is incremental as it builds on existing SGD frameworks.
The paper tackles the problem of optimizing Stochastic Gradient Descent (SGD) by developing a coupling-based diagnostic to detect when iterates reach stationarity with constant stepsize, and proposes a dynamic stepsize scheme that achieves superior performance in convex and non-convex problems, as demonstrated through extensive numerical experiments.
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 initial transient phase. However, when reaching stationarity, the iterates oscillate around the optimum without making further progress. In this paper, we study the convergence diagnostics for SGD with constant stepsize, aiming to develop an effective dynamic stepsize scheme. We propose a novel coupling-based convergence diagnostic procedure, which monitors the distance of two coupled SGD iterates for stationarity detection. Our diagnostic statistic is simple and is shown to track the transition from transience stationarity theoretically. We conduct extensive numerical experiments and compare our method against various existing approaches. Our proposed coupling-based stepsize scheme is observed to achieve superior performance across a diverse set of convex and non-convex problems. Moreover, our results demonstrate the robustness of our approach to a wide range of hyperparameters.