Painless Stochastic Gradient: Interpolation, Line-Search, and Convergence Rates

Abstract

Recent works have shown that stochastic gradient descent (SGD) achieves the fast convergence rates of full-batch gradient descent for over-parameterized models satisfying certain interpolation conditions. However, the step-size used in these works depends on unknown quantities and SGD's practical performance heavily relies on the choice of this step-size. We propose to use line-search techniques to automatically set the step-size when training models that can interpolate the data. In the interpolation setting, we prove that SGD with a stochastic variant of the classic Armijo line-search attains the deterministic convergence rates for both convex and strongly-convex functions. Under additional assumptions, SGD with Armijo line-search is shown to achieve fast convergence for non-convex functions. Furthermore, we show that stochastic extra-gradient with a Lipschitz line-search attains linear convergence for an important class of non-convex functions and saddle-point problems satisfying interpolation. To improve the proposed methods' practical performance, we give heuristics to use larger step-sizes and acceleration. We compare the proposed algorithms against numerous optimization methods on standard classification tasks using both kernel methods and deep networks. The proposed methods result in competitive performance across all models and datasets, while being robust to the precise choices of hyper-parameters. For multi-class classification using deep networks, SGD with Armijo line-search results in both faster convergence and better generalization.

Added a citation to the related work of Paul Tseng, and citations to methods that had previously explored line-searches for deep learning empirically

References in corpus (7)

• ADADELTA: An Adaptive Learning Rate Method
• On the Convergence of Adam and Beyond
• No More Pesky Learning Rates
• Adaptive Gradient Methods with Dynamic Bound of Learning Rate
• Reducing Noise in GAN Training with Variance Reduced Extragradient
• On exponential convergence of SGD in non-convex over-parametrized learning
• Stochastic Gradient Descent: Going As Fast As Possible But Not Faster

Cited by in corpus (12)

• Adversarial Example Games
• AdaS: Adaptive Scheduling of Stochastic Gradients
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime
• Adaptive Stochastic Optimization
• Unconstrained optimisation on Riemannian manifolds
• Explicit Regularization of Stochastic Gradient Methods through Duality
• Heuristic adaptive fast gradient method in stochastic optimization tasks
• Approximately Exact Line Search
• Stochastic Polyak Stepsize with a Moving Target
• Improved Complexities for Stochastic Conditional Gradient Methods under Interpolation-like Conditions
• A straightforward line search approach on the expected empirical loss for stochastic deep learning problems
• On Second-order Optimization Methods for Federated Learning