Semi-Stochastic Gradient Descent Methods
Jakub Konečný, Peter Richtárik · Frontiers in Applied Mathematics and Statistics · 2017
In this paper we study the problem of minimizing the average of a large number 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. For strongly convex objectives, the method converges linearly. The total work needed for the method to output an epsilon-accurate solution in expectation, measured in the number of passes over data, is proportional to the condition number of the problem and inversely proportional to the number of functions forming the average. This is achieved by running the method with number of stochastic gradient evaluations per epoch proportional to conditioning of the problem. The SVRG method of Johnson and Zhang arises as a special case. To illustrate our theoretical results, S2GD only needs the workload equivalent to about 2.1 full gradient evaluations to find a 10e-6 accurate solution for a problem with 10e9 functions and a condition number of 10e3.
Cited by 132 works. doi:10.3389/fams.2017.00009 Open-access PDF
Authors
References
- Introductory Lectures on Convex Optimization: A Basic Course
- Introductory Lectures on Convex Optimization
- Solving large scale linear prediction problems using stochastic gradient descent algorithms
- Robust Stochastic Approximation Approach to Stochastic Programming
- A dual coordinate descent method for large-scale linear SVM
- Accelerating Stochastic Gradient Descent using Predictive Variance Reduction
- Minimizing finite sums with the stochastic average gradient
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function
- A Proximal Stochastic Gradient Method with Progressive Variance Reduction
- Parallel coordinate descent methods for big data optimization