Accelerating Stochastic Gradient Descent For Least Squares Regression
Prateek Jain Microsoft Research, Bangalore, India, Sham M. Kakade University of Washington, Seattle, WA, USA, Rahul Kidambi University of Washington, Seattle, WA, USA, Praneeth Netrapalli Microsoft Research, Bangalore, India, Aaron Sidford Stanford University, Palo Alto, CA, USA,
Abstract
There is widespread sentiment that fast gradient methods (e.g. Nesterov’s acceleration, conjugate gradient, heavy ball) are not effective for stochastic optimization due to their instability and error accumulation. Numerous works have attempted to quantify these instabilities in the face of either statistical or non-statistical errors (Paige, 1971; Proakis, 1974; Polyak, 1987; Greenbaum, 1989; Devolder et al., 2014). This work considers these issues for the case of stochastic approximation for the least squares regression problem, and our main result refutes this conventional wisdom by showing that acceleration can be made robust to statistical errors. In particular, this work introduces an accelerated stochastic gradient method that provably achieves the minimax optimal statistical risk faster than stochastic gradient descent. Critical to the analysis is a sharp characterization of accelerated stochastic gradient descent as a stochastic process. We hope this characterization gives insights towards the broader question of designing simple and effective accelerated stochastic methods for general convex and non-convex optimization problems.
中文速览
长期以来，学界普遍认为动量加速方法（如Nesterov加速、共轭梯度、重球法）因误差累积和不稳定性，无法在随机优化中发挥作用。本文针对最小二乘回归的随机逼近（stochastic approximation）问题，提出了一种新的加速随机梯度下降（accelerated SGD）算法，从理论上证明了加速方法完全可以抵抗统计噪声的干扰。具体来说，该算法的偏差（bias）以$\mathcal{O}(1/\sqrt{\kappa\tilde{\kappa}})$的几何速率收缩，优于普通随机梯度下降的$\mathcal{O}(1/\kappa)$，同时方差（variance）部分仍保持极小化最大（minimax）最优的统计风险界。这一结果的关键在于引入了"统计条件数"（statistical condition number）$\tilde{\kappa}$这一新概念，以及对加速随机梯度下降迭代过程作为随机过程的精确刻画，从而打破了"随机场景下加速必然失效"的传统认知，为大规模机器学习中的快速流式优化算法设计提供了重要的理论基础。
原文 arXiv:1704.08227;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1704.08227v2