A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets
Nicolas Le Roux Mark Schmidt Francis Bach INRIA - SIERRA Project - Team Département d’Informatique de l’École Normale Supérieure Paris, France
Abstract
We propose a new stochastic gradient method for optimizing the sum of a finite set of smooth functions, where the sum is strongly convex. While standard stochastic gradient methods converge at sublinear rates for this problem, the proposed method incorporates a memory of previous gradient values in order to achieve a linear convergence rate. In a machine learning context, numerical experiments indicate that the new algorithm can dramatically outperform standard algorithms, both in terms of optimizing the training error and reducing the test error quickly.
中文速览
随机梯度下降（SGD）在机器学习中广泛使用，但面对有限训练集上的强凸优化问题时，它的收敛速度是次线性的（O(1/k)），而全梯度法虽然收敛更快（线性收敛），每次迭代却要遍历所有样本、代价高昂。本文提出了一种叫做随机平均梯度法（Stochastic Average Gradient，SAG）的新算法：每次迭代只随机选一个样本计算新梯度，同时在内存中保存每个样本最近一次计算的梯度，用所有这些梯度的平均值来更新参数。理论分析证明，SAG在保持与SGD相同的单步计算代价的同时，实现了与全梯度法相同的线性收敛率，在训练样本数量足够大时甚至可以超越全梯度法的收敛速度。机器学习实验表明，SAG在训练误差下降速度和测试误差改善速度上都大幅优于标准SGD和全梯度法，对于只能对数据做少量遍历的场景尤其实用，填补了过去六十年中随机梯度方法在有限数据集上无法做到线性收敛的空白。
原文 arXiv:1202.6258;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1202.6258v4