Source-linked AI summary
A Proximal Stochastic Gradient Method with Progressive Variance Reduction
Lin Xiao, Tong Zhang
TL;DR
The paper addresses efficient minimization of strongly convex composite objectives whose smooth part is a large finite average and whose other part admits a simple proximal mapping. It develops Prox-SVRG, which progressively reduces stochastic-gradient variance through a multi-stage scheme. The method achieves geometric convergence and lower overall complexity than proximal full-gradient and standard proximal stochastic-gradient methods.
Problem
The problem is to efficiently minimize a strongly convex sum of a large smooth finite average and a general convex function with a simple proximal mapping.
Method
Prox-SVRG extends SVRG variance reduction to proximal stochastic optimization using periodically computed full gradients and progressive multi-stage variance reduction.
Results
Prox-SVRG has geometric convergence in expectation and achieves the same low complexity as SDCA and SAG while applying to a more general problem class.
Takeaways & Limitations
The method offers an efficient structure-aware alternative for large-scale regularized empirical risk minimization without storing the most recent gradient for every component.
Takeaways & Limitations
The analysis assumes Lipschitz-continuous component gradients and strong convexity of the overall objective, with step size and stage length constrained by Theorem 1.
Abstract
from arXiv · showhide
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 multi-stage 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.
1 Introduction
The paper studies strongly convex objectives combining a large finite average of smooth functions with a possibly nonsmooth convex term, targeting efficient large-scale optimization. It contrasts proximal full-gradient and stochastic methods, then motivates Prox-SVRG as a structure-aware alternative.
- The regularizer may be nondifferentiable and can also encode closed convex constraints through an indicator function.
- Regularized empirical risk minimization instantiates the problem using smooth losses and convex regularizers such as Lasso, ridge, and elastic net.
- Prox-SG evaluates one component gradient per iteration, reducing per-iteration cost to 1/n of Prox-FG but suffering slower convergence from sampling variance.
- O(n(L/µ) log(1/ε)) component-gradient evaluations characterize Prox-FG, whose full-gradient iterations become expensive for large n.
- O(1/µε) component-gradient evaluations give Prox-SG a sublinear accuracy dependence, although its n-independent cost can help when n is very large and low precision is sufficient.
- Prox-SVRG extends SVRG variance reduction to the composite problem, achieving the same complexity as prior low-complexity methods and improving it with smoothness-weighted sampling.
2 The Prox-SVRG method
Prox-SVRG periodically computes a full gradient and uses corrected stochastic gradients within multi-stage proximal updates. As the reference and current iterates approach the optimum, the corrected-gradient variance decreases, enabling constant-step geometric convergence.
- SVRG correction combines a component gradient at the current iterate with a reference-point full gradient to reduce stochastic-gradient variance.
- The corrected direction remains an unbiased estimator of the full gradient at the current iterate.
- As both iterates converge to the optimum, corrected-gradient variance converges to zero, allowing a constant step size and faster convergence.
- The algorithm permits general sampling distributions, including weighted sampling based on component smoothness constants.
- Each stage uses n + 2m component-gradient evaluations, or n + m for some linear-prediction problems.
3 Convergence analysis
Under strong convexity and suitable step-size and stage-length conditions, Prox-SVRG contracts the expected objective gap geometrically. Its complexity depends on a weighted condition number and supports uniform or Lipschitz-weighted sampling.
- Theorem 1 establishes geometric convergence in expectation for Prox-SVRG under strong convexity, with η < 1/(4LQ) and sufficiently large m.The contraction factor ρ is required to be below one.
- m = O(LQ/µ) is sufficient for geometric convergence when η = θ/LQ with 0 < θ < 1/4.Here LQ/µ acts as a weighted condition number.
- θ = 0.1 and m = 100(LQ/µ) yield ρ ≈5/6.
- Each stage requires n + 2m component gradient evaluations, and setting m = Θ(LQ/µ) gives the stated overall complexity.
- For uniform sampling, LQ = maxi Li, while sampling probabilities proportional to component Lipschitz constants produce the alternative complexity bound.
4 Numerical experiments
The experiments examine Prox-SVRG on regularized logistic regression and compare it with proximal stochastic, full-gradient, accelerated, dual, and average-gradient methods. Performance depends on step size, full-gradient period, regularization, and dataset difficulty.
- Experimental setup: Prox-SVRG was evaluated on three public binary-classification datasets using effective data passes as the computational axis.The experiments used regularized logistic regression with ℓ1 and ℓ2 regularization.
- Prox-SVRG properties: η = 0.1/L gave the best Prox-SVRG behavior on rcv1 with m = 2n, while overly large or small step sizes slowed convergence.This choice matched the theoretical analysis.
- Prox-SVRG properties: For λ2 = 10−4, m = 2 slightly outperformed m = 1 overall because frequent full-gradient evaluations offset the faster per-stage convergence of m = 1.Longer periods slowed convergence through weaker variance reduction.
- Prox-SVRG properties: For λ2 = 10−5, the larger condition number required a longer period m to obtain sufficient variance reduction during each stage.The regularization setting therefore changed the preferred full-gradient period.
- Method comparisons: On rcv1, Prox-SAG, Prox-SVRG, and Prox-SDCA performed best, while Prox-SG failed to converge to the correct NNZs.RDA, Prox-SDCA, and Prox-SAG reached the correct sparsity pattern quickly, followed by Prox-SVRG and the full-gradient methods.
- Method comparisons: On covertype, full-gradient methods performed worse under smaller λ2, while on sido0 Prox-SAG performed best, followed by Prox-SVRG2 and Prox-SVRG.The sido0 dataset showed generally slower convergence.
5 Conclusions
The paper introduces Prox-SVRG for composite objectives with a smooth finite-average component and a proximable convex component. It extends SVRG variance reduction and retains low complexity while supporting broader problems without storing each component’s latest gradient.
- Contribution: Prox-SVRG extends SVRG variance reduction to proximal stochastic optimization of a smooth finite average plus a general proximable convex function.It periodically computes the full gradient to modify stochastic gradients and reduce their variance.
- Contribution: Prox-SVRG matches the low complexity of SDCA and SAG while applying to a more general problem class.The conclusion compares its complexity with these methods without asserting a formal convergence result for Prox-SAG.
- Contribution: Prox-SVRG does not require storing the most recent gradient for every component function.A weighted sampling scheme further improves complexity when component smoothness varies substantially.
A Proof of Lemma 3
The proof of Lemma 3 combines proximal optimality, strong convexity, and smoothness to control the update using the stochastic-gradient error. The result follows under a step size bounded by 1/L.
- Proximal optimality: The proximal update yields an optimality condition with a subgradient ξ ∈ ∂R(x+).Defining g = (x − x+)/η gives ξ = g − v.
- Curvature and smoothness: Strong convexity of F and R supplies the curvature bound used for arbitrary x ∈ dom(R) and y ∈ R^d.The combined objective can use curvature from either component.
- Proof combination: Smoothness of F provides a lower bound that is combined with the proximal optimality relation.The proof rewrites inner products using x − x+ = ηg and Δ = v − ∇F(x).
B Convergence analysis of the Prox-FG method
The Prox-FG convergence analysis uses a full-gradient mapping and applies Lemma 3 at the current iterate and optimum. With η = 1/L, the resulting inequality gives the stated convergence rate.
- Convergence proof: The proof defines the full-gradient mapping Gk = (xk − xk−1)/η for the Prox-FG iterates.This mapping is used to express the update in the convergence argument.
- Convergence proof: Applying Lemma 3 with y = x⋆ eliminates the stochastic-gradient error because Δ = 0.The substitution uses x = xk−1, x+ = xk, and g = Gk.
- Convergence proof: The proof rearranges the inequality and drops the nonnegative term (1 + ηµR)∥xk − x⋆∥2.This produces a simpler bound for the objective-gap analysis.
- Convergence rate: η = 1/L converts the resulting inequality into the Prox-FG convergence rate in (7).The step-size choice is made after the nonnegative term is removed.