Semi-Stochastic Gradient Descent Methods

By Jakub Konecný, Peter Richtárik. 2013

246 citations recorded by the source corpus.

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 loss, is $O((\kappa/n)\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 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 equivalent to about 2.1 full gradient evaluations to find an $10^{-6}$-accurate solution for a problem with $n=10^9$ and $\kappa=10^3$.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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

In Computational Mechanics

In Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

Federated Optimization: Distributed Optimization Beyond the Datacenter (2015, methodology): “• The green circles (SVRGfo) give values for our proposed algorithm.”
Improved asynchronous parallel optimization analysis for stochastic incremental methods (2018, neutral): “As a result our timed experiments exhibit sub-optimal running times, e.g. compared to Konečný and Richtárik (2013).”
Variance Reduced Stochastic Gradient Descent with Neighbors (2015, background): “Recurrence of Iterates The evolution equation (2) in expectation implies the recurrence (by crucially using the unbiasedness condition Egi(w) = f ′(w)): E‖w+−w∗‖2 = ‖w − w∗‖2 − 2γ〈f ′(w), w − w∗〉+ γ2E‖gi(w)‖2 .”
AIDE: Fast and Communication Efficient Distributed Optimization (2016, methodology): “While one could use any of recent fast algorithms for finite sums [17, 4, 19, 3] with comparable results, we highlight the consequences of applying the SVRG algorithm [6, 8] as a local solver in INEXACTDANE.”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “The SVRG algorithm runs in two nested loops.”
Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods (2017, methodology): “tion to be minimized is strongly convex. To overcome this problem, a new class of so-called variance-reduced methods was developed over the last 2-5 years, including SAG [66], SDCA [68,62], SVRG/S2GD [29,32], minibatch SVRG/S2GD [31], and SAGA [12,11]. Since we assume that the linear system (2) is f”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, background): “We answer one part of this question by developing new asynchronous parallel stochastic gradient methods that provably converge at a linear rate for smooth strongly convex finite-sum problems.”
ASAGA: Asynchronous Parallel SAGA (2016, neutral): “As a result our timed experiments exhibit sub-optimal running times, e.g. compared to Konecny and Richtarik (2013).”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “Very recently, starting with the SAG [4], SDCA [5], SVRG [6] and S2GD [7] algorithms from year 2013, it has transpired that neither decreasing stepsizes nor mini-batching are necessary to resolve the non-vanishing variance issue inherent in the vanilla SGDmethods.”
Stochastic, Distributed and Federated Optimization for Machine Learning (2017, methodology): “[127] SGD O(Cgrad/ ) [196, 162] CD O(nκCpd log(1/ )) [129, 148] SDCA O((n+ κ)Cgrad log(1/ )) [163, 201, 143] SVRG/S2GD O ((nCgrad + κCgrad) log (1/ )) [80, 187, 89] S2CD O ((nCgrad + κ̂Cpd) log (1/ )) this work [84]”
Semi-stochastic coordinate descent (2014, methodology): “We conclude by combining (20), (21), (25), (26) and (28).”
Randomized Iterative Methods for Linear Systems: Momentum, Inexactness and Gossip (2019, methodology): “To overcome this problem, a new class of so-called variance-reduced methods was developed over the last 8 years, including SAG [173], SDCA [178, 166], SVRG/S2GD [89, 97], minibatch SVRG/S2GD [96], and SAGA [34, 33].”
A Simple Practical Accelerated Method for Finite Sums (2016, methodology): “FIG methods are randomized methods similar to SGD, however unlike SGD they are able to achieve linear convergence rates under Lipschitz-smooth and strong convexity conditions [Mairal, 2014, Defazio et al., 2014b, Johnson and Zhang, 2013, Konečný and Richtárik, 2013].”
Distributed Mini-Batch SDCA (2015, methodology): “Our analysis allows for flexible sampling schemes, including where data is distribute across machines, and combines a dependence on thsmoothness of the loss and/or the data spread (measured through the spectral norm).”