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 the step-size. We propose to use line-search methods to automatically set the step-size when training models that can interpolate the data. We prove that SGD with the classic Armijo line-search attains the fast convergence rates of full-batch gradient descent in convex and strongly-convex settings. We also show that under additional assumptions, SGD with a modified line-search can attain a fast rate of convergence for non-convex functions. Furthermore, we show that a stochastic extra-gradient method with a Lipschitz line-search attains a fast convergence rate for an important class of non-convex functions and saddle-point problems satisfying interpolation. We then give heuristics to use larger step-sizes and acceleration with our line-search techniques. We compare the proposed algorithms against numerous optimization methods for standard classification tasks using both kernel methods and deep networks. The proposed methods are robust and result in competitive performance across all models and datasets. Moreover, for the deep network models, SGD with our line-search results in both faster convergence and better generalization.

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

无痛随机梯度: 插值，线性搜索和收敛速率