Semi-Stochastic Gradient Descent Methods
Jakub Konečný 111School of Mathematics, The University of Edinburgh, United Kingdom (e-mail: Peter Richtárik 222School of Mathematics, The University of Edinburgh, United Kingdom (e-mail: The work of both authors was supported by the Centre for Numerical Algorithms and Intelligent Software (funded by EPSRC grant EP/G036136/1 and the Scottish Funding Council). Both authors also thank the Simons Institute for the Theory of Computing, UC Berkeley, where this work was conceived and finalized. The work of P.R. was also supported by the EPSRC grant EP/I017127/1 (Mathematics for Vast Digital Resources) and EPSRC grant EP/K02325X/1 (Accelerated Coordinate Descent Methods for Big Data Problems). School of Mathematics University of Edinburgh United Kingdom
Abstract
In this paper we study the problem of minimizing the average of a large number ( $n$ ) of smooth convex loss functions. We propose a new method, S2GD (Semi-Stochastic Gradient Descent), which runs for one or several epochs in each of which a single full gradient and a random number of stochastic gradients is computed, following a geometric law. The total work needed for the method to output an $\varepsilon$ -accurate solution in expectation, measured in the number of passes over data, or equivalently, in units equivalent to the computation of a single gradient of the empirical loss, is $O((n/\kappa)\log(1/\varepsilon))$ , where $\kappa$ is the condition number. This is achieved by running the method for $O(\log(1/\varepsilon))$ epochs, with a single gradient evaluation and $O(\kappa)$ stochastic gradient evaluations in each. The SVRG method of Johnson and Zhang [3] arises as a special case. If our method is limited to a single epoch only, it needs to evaluate at most $O((\kappa/\varepsilon)\log(1/\varepsilon))$ stochastic gradients. In contrast, SVRG requires $O(\kappa/\varepsilon^{2})$ stochastic gradients. To illustrate our theoretical results, S2GD only needs the workload equiva
中文速览
训练机器学习模型时，当样本量 n 极大，每步都算全梯度太贵，纯随机梯度（SGD）又因方差大而收敛慢，如何两全其美是核心难题。本文提出半随机梯度下降法（S2GD，Semi-Stochastic Gradient Descent），每个训练轮次（epoch）只算一次全梯度，再按几何分布随机抽取 O(κ) 次随机梯度，通过将两者组合来压缩方差、保证线性收敛。理论分析表明，S2GD 求得 ε 精度解所需的总计算量（折算为数据遍历次数）为 O((n+κ)log(1/ε))，与当时最优方法持平，但常数更优；现有方法 SVRG 是它在参数未优化时的特例，而单轮次运行时 S2GD 所需随机梯度次数为 O((κ/ε)log(1/ε))，远优于 SVRG 的 O(κ/ε²)。这一工作为大规模经验风险最小化提供了更高效、内存友好且理论完备的优化方案，对工业级机器学习具有直接的实用价值。
原文 arXiv:1312.1666;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1312.1666v2