Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic setting for both convex and strongly-convex functions. In the non-convex setting, this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent. Under interpolation, we also show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an O(1/k^2) mistake bound for $k$ iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.

通过研究表明，在现代机器学习中，采用具有极高表现力的模型进行训练，可以实现完全拟合或内插数据，从而得到零训练损失。我们证明，采用恒定步长随机梯度下降法（SGD）与Nesterov加速法具有相同的收敛速度，适用于凸和强凸函数。同时，我们发现，SGD可以在非凸情况下像全梯度下降法一样高效地找到一阶稳定点。最后，我们通过对合成和真实数据集的实验验证了我们的理论发现。

SGD 对超参数模型的更快收敛和快速收敛，及加速感知器