A Proximal Stochastic Gradient Method with Progressive Variance Reduction

By Lin Xiao, Tong Zhang. 2014

777 citations recorded by the source corpus.

We consider the problem of minimizing the sum of two convex functions: one is the average of a large number of smooth component functions, and the other is a general convex function that admits a simple proximal mapping. We assume the whole objective function is strongly convex. Such problems often arise in machine learning, known as regularized empirical risk minimization. We propose and analyze a new proximal stochastic gradient method, which uses a multistage scheme to progressively reduce the variance of the stochastic gradient. While each iteration of this algorithm has similar cost as the classical stochastic gradient method (or incremental gradient method), we show that the expected objective value converges to the optimum at a geometric rate. The overall complexity of this method is much lower than both the proximal full gradient method and the standard proximal stochastic gradient method.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability, 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 Statistics and Probability

In Optimization & Training

Citations in the corpus

Reducing Noise in GAN Training with Variance Reduced Extragradient (2019, methodology): “This strategy has been first introduced for variance reduced methods by Xiao and Zhang (2014) for SVRG and has been discussed for saddle point optimization by Palaniappan and Bach (2016).”
SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives (2014, methodology): “F (x) = f(x) + h(x), where h : R → R is convex but potentially non-differentiable, and where the proximal operation of h is easy to compute — few incremental gradient methods are applicable in this setting [3][4].”
Minimizing finite sums with the stochastic average gradient (2013, methodology): “Indeed, we provide here an argument to justify a non-uniform sampling strategy based on the Lipschitz constants of the individual gradients f ′ i and we note that in subsequent works this intuition has proved correct for related algorithms [53,64].”
How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD (2018, background): “Recall the following property about gradient mapping—see for instance [32, Lemma 3.7]) The following deﬁnition and properties of Fenchel dual for convex functions is classical, and can be found for instance in the textbook [29].”
Federated Optimization: Distributed Machine Learning for On-Device Intelligence (2016, methodology): “Another algorithm from the SGD class of methods is Stochastic Variance Reduced Gradient 1 (SVRG) [43] and [47, 100, 44].”
Distributed optimization with arbitrary local solvers (2015, background): “On the other hand, Stochastic Variance Reduced Gradient (SVRG) and its variants [27, 29, 30, 42, 69] are often interpreted as ‘memory-free’ methods with variance reduction.”
Stochastic Variance Reduction for Nonconvex Optimization (2016, methodology): “Algorithm 2 attains linear convergence for strongly convex f (Johnson & Zhang, 2013); for non-strongly convex functions, rates faster than Sgd can be shown by using an indirect perturbation argument—see e.g., (Koneˇcn´y & Richt´arik, 2013; Xiao & Zhang, 2014).”
A Universal Catalyst for First-Order Optimization (2015, methodology): “More importantly, it also applies to incremental algorithms such as SA G [24], SAGA [6], Finito/MISO [7, 14], SDCA [25], and SVRG [27].”
Semi-Stochastic Gradient Descent Methods (2013, background): “A possible explanation for this can be found in an extension of SVRG to proximal setting Xiao and Zhang [22], released after the first version of this paper was put onto arXiv (i.”
Stochastic Optimization with Importance Sampling for Regularized Loss Minimization (2014, background): “Regression problems also fall into the above. k k Let w ∗ be the optimum of (1). k k We say that a solution w is ǫ P -sub-optimal if P ( w ) − P ( w ∗ ) ≤ ǫ P .”
On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants (2015, methodology): “1) While our analysis focuses on strongly convex functions, we can extend it to just smooth convex functions along the lines of [5, 28].”
Non-Uniform Stochastic Average Gradient Method for Training Conditional Random Fields (2015, background): “More recently, Xiao and Zhang [2014] show that NUS gives a dependence on ¯ L in the context of a related algorithm that uses occasional full passes through the data (which substantially simpliﬁes the analysis).”
Stochastic Variance Reduction Methods for Saddle-Point Problems (2016, background): “The difference with the convex minimization set-up of [24] is that the proof is more direct, and we get a shr inkage directly on the iterates (we have no choice for monotone operators), without the need to d o averaging of the iterates.”
Katyusha: the first direct acceleration of stochastic gradient methods (2016, methodology): “The convergence rate of SGD can be further improved with the so-called variance-reduction technique [9, 11, 17, 24, 25, 31, 32, 35, 36].”
Memory and Communication Efficient Distributed Stochastic Optimization with Minibatch Prox (2017, methodology): “Noting that φ I (i) t (z) is the sum of b components, and each component is β-smooth while the overall function f (i) k is (γ+κ)-strongly convex, the lemma follows directly from the convergence guarantee of prox-SVRG (Xiao and Zhang, 2014, Corollary 1).”
Mini-Batch Semi-Stochastic Gradient Descent in the Proximal Setting (2015, methodology): “APPENDIX A TECHNICAL RESULTS Lemma 3 (Lemma 2 in [2]).”