Stochastic gradient descent (SGD) holds as a classical method to build large
scale machine learning models over big data. A stochastic gradient is typically
calculated from a limited number of samples (known as mini-batch), so it
potentially incurs a high variance and causes the estimated parameters bounce
around the optimal solution. To improve the stability of stochastic gradient,
recent years have witnessed the proposal of several semi-stochastic gradient
descent algorithms, which distinguish themselves from standard SGD by
incorporating global information into gradient computation. In this paper we
contribute a novel stratified semi-stochastic gradient descent (S3GD) algorithm
to this nascent research area, accelerating the optimization of a large family
of composite convex functions. Though theoretically converging faster, prior
semi-stochastic algorithms are found to suffer from high iteration complexity,
which makes them even slower than SGD in practice on many datasets. In our
proposed S3GD, the semi-stochastic gradient is calculated based on efficient
manifold propagation, which can be numerically accomplished by sparse matrix
multiplications. This way S3GD is able to generate a highly-accurate estimate
of the exact gradient from each mini-batch with largely-reduced computational
complexity. Theoretic analysis reveals that the proposed S3GD elegantly
balances the geometric algorithmic convergence rate against the space and time
complexities during the optimization. The efficacy of S3GD is also
experimentally corroborated on several large-scale benchmark datasets.

提出一种名为分层半随机梯度下降（S3GD）的算法，此算法通过有效的流形传播计算半随机梯度，实现了对大量复合凸函数的优化，能够很好地平衡了几何算法收敛速度和时间空间复杂度。