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.

本文提出了一种使用线性搜索技术自动设置步长的随机梯度下降算法，在数据插值设置中，使用 Armijo 线性搜索方法的 SGD 实现凸和强凸函数的确定性收敛率，同时提出了一种 Lipschitz 线性搜索策略的随机额外梯度的算法，该算法在满足嵌入条件的非凸问题和鞍点问题的情况下实现了线性收敛率，并在标准分类任务上表现出了良好的性能。