Stochastic Gradient Made Stable: A Manifold Propagation Approach for Large-Scale Optimization

By Yadong Mu, Wei Liu, Xiaobai Liu, Wei Fan. 2015

36 citations recorded by the source corpus.

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), which potentially incurs a high variance and causes the estimated parameters to 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.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Eric Learned-Miller
2. Andrew McCallum
3. Haw-Shiuan Chang
4. Hosagrahar Visvesvaraya Jagadish
5. Beng Chin Ooi
6. Zeeshan Akhtar
7. Jinyang Gao
8. Ketan Rajawat

In Computational Mechanics

1. Amrit Singh Bedi
2. Eric Learned-Miller
3. Andrew McCallum
4. Haw-Shiuan Chang
5. Hosagrahar Visvesvaraya Jagadish
6. Beng Chin Ooi
7. Zeeshan Akhtar
8. Jinyang Gao

In Computer Vision and Pattern Recognition

1. Andrew McCallum
2. Eric Learned-Miller
3. Haw-Shiuan Chang
4. Hosagrahar Visvesvaraya Jagadish
5. Beng Chin Ooi
6. Jinyang Gao
7. Xiaogang Wang
8. Xiaoou Tang

Citations in the corpus

• Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples (2017, background): “Other work proposes variants of semi-stochastic algorithms to approximate the exact gradient direction and reduce the gradient variance [47, 34].”
• Active Sampler: Light-weight Accelerator for Complex Data Analytics at Scale (2015, background): “Consequently, many SGD variants such as SAG [23], SVRG [11], S3DG [19] have been developed to reduce the variance.”
• Conservative Stochastic Optimization With Expectation Constraints (2020, background): “In most applications, such as those arising in machine learning [1], finance [2], robotics [3], signal processing [4], and communications [5], the constraint set X is easy to work with, giving rise to two classes of stochastic gradient descent (SGD) algorithms: projected SGD and Franke-Wolfe SGD.”