Semi-Stochastic Gradient Descent Methods
Authors:
Open Access
- 23 May 2017
- journal article
- research article
- Published by Frontiers Media SA in Frontiers in Applied Mathematics and Statistics
- Vol. 3
Abstract
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.Keywords
All Related Versions
Funding Information
- Engineering and Physical Sciences Research Council (EP/G036136/1)
- Engineering and Physical Sciences Research Council (EP/I017127/1)
- Engineering and Physical Sciences Research Council (EP/K02325X/1)
This publication has 13 references indexed in Scilit:
- Minimizing finite sums with the stochastic average gradientMathematical Programming, 2016
- Parallel coordinate descent methods for big data optimizationMathematical Programming, 2015
- Iteration complexity of randomized block-coordinate descent methods for minimizing a composite functionMathematical Programming, 2012
- Hybrid Deterministic-Stochastic Methods for Data FittingSIAM Journal on Scientific Computing, 2012
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- A dual coordinate descent method for large-scale linear SVM2008
- Variable-Number Sample-Path OptimizationMathematical Programming, 2007
- Convergence theory for nonconvex stochastic programming with an application to mixed logitMathematical Programming, 2006
- Solving large scale linear prediction problems using stochastic gradient descent algorithms2004
- Rates of Convergence of Semi-Stochastic Approximation Procedures for Solving Stochastic Optimization ProblemsOptimization, 1986