Stochastic Nested Variance Reduction for Nonconvex Optimization

Dongruo Zhou; Pan Xu; Quanquan Gu

Source-linked AI summary

Stochastic Nested Variance Reduction for Nonconvex Optimization

Dongruo Zhou, Pan Xu, Quanquan Gu

arXiv:1806.07811v2Jun 20, 2018cs.LGmath.OCstat.ML

TL;DR

The paper addresses gradient-complexity reduction for smooth finite-sum nonconvex optimization. It introduces SNVRG, which uses K+1 nested reference points for variance reduction, and reports eO(n ∧ ε^-2 + ε^-3 ∧ n^1/2ε^-2) evaluations for an ε-approximate stationary point, with better results also for gradient-dominated functions.

Problem
Finite-sum nonconvex optimization needs efficient methods for finding ε-approximate stationary points when full-gradient methods scale poorly with n.
Method
SNVRG constructs semi-stochastic gradients with K+1 nested reference points to reduce variance across iterations.
Results
eO(n ∧ ε^-2 + ε^-3 ∧ n^1/2ε^-2) stochastic gradient evaluations achieve an ε-approximate stationary point, outperforming existing first-order algorithms.
Takeaways & Limitations
The paper partially resolves whether the n-dependence of nonconvex SVRG and SCSG can be improved, with finite-sum complexity near optimal up to logarithmic factors.
Takeaways & Limitations
The experiments illustrate SNVRG's advantage and theory rather than claiming a state-of-the-art method for training deep neural networks.

Abstract

from arXiv · show

We study finite-sum nonconvex optimization problems, where the objective function is an average of $n$ nonconvex functions. We propose a new stochastic gradient descent algorithm based on nested variance reduction. Compared with conventional stochastic variance reduced gradient (SVRG) algorithm that uses two reference points to construct a semi-stochastic gradient with diminishing variance in each iteration, our algorithm uses $K+1$ nested reference points to build a semi-stochastic gradient to further reduce its variance in each iteration. For smooth nonconvex functions, the proposed algorithm converges to an $ε$-approximate first-order stationary point (i.e., $\|\nabla F(\mathbf{x})\|_2\leq ε$) within $\tilde O(n\land ε^{-2}+ε^{-3}\land n^{1/2}ε^{-2})$ number of stochastic gradient evaluations. This improves the best known gradient complexity of SVRG $O(n+n^{2/3}ε^{-2})$ and that of SCSG $O(n\land ε^{-2}+ε^{-10/3}\land n^{2/3}ε^{-2})$. For gradient dominated functions, our algorithm also achieves better gradient complexity than the state-of-the-art algorithms. Thorough experimental results on different nonconvex optimization problems back up our theory.

1 Introduction

The paper studies smooth finite-sum nonconvex optimization and proposes nested variance reduction to reduce gradient-complexity dependence on n. SNVRG uses K+1 reference points and achieves improved complexity for stationary points and gradient-dominated objectives.

Problem: Finite-sum nonconvex optimization averages n component functions with Lipschitz continuous gradients, while targeting an ε-approximate stationary point because global minimization is generally NP-hard.The stationarity criterion is ||∇F(x)||_2 ≤ ε.
Existing methods: GD requires O(n · ε^-2) stochastic gradient evaluations, while SGD requires O(ε^-4) under bounded stochastic-gradient variance.The comparison motivates methods with better dependence on n and ε.
Method: SNVRG uses K+1 nested reference points to construct a semi-stochastic gradient whose variance decays faster than the gradients used by SVRG and SCSG.When K=1, the one-epoch procedure reduces to SVRG.
Results: SNVRG reaches an ε-approximate stationary point with eO(n ∧ ε^-2 + ε^-3 ∧ n^1/2ε^-2) stochastic gradient evaluations.The paper reports this complexity as outperforming GD, SGD, SVRG, and SCSG.
Results: A variant for τ-gradient-dominated functions finds an ε-approximate global minimizer with better gradient complexity than state-of-the-art methods.The supplied contribution passage states the outcome but does not include the full complexity expression.

2 Preliminaries

The paper establishes smoothness, convexity, variance, and gradient-dominance terminology, then specifies the SNVRG algorithmic framework and comparison measures.

Complexity measures: Table 1 compares algorithms by gradient complexity for stationary-point and global-minimizer objectives, plus space complexity.
Definitions: An L-smooth function has Lipschitz-continuous gradients, while strong convexity is defined separately as a curvature condition.
Definitions: Bounded stochastic-gradient variance is defined through the expected squared deviation of a randomly sampled component gradient.
Definitions: Gradient-dominated functions relate function suboptimality to gradient magnitude and need not be convex; this condition is also called the P-L condition.
Algorithmic setup: SNVRG is organized as an epoch algorithm with inputs for loop counts, step-size parameters, batch sizes, and reference-gradient updates.

3 The Proposed Algorithm

SNVRG extends SVRG with nested reference points and gradients, using them to construct updates while maintaining low storage through infrequent reference updates.

Nested variance reduction: SNVRG uses K + 1 reference points and K + 1 reference gradients, with the K = 1 case reducing to one epoch of SVRG.
Nested variance reduction: Reference points are updated at different periods, creating the nested structure across levels of the one-epoch procedure.
Nested variance reduction: The algorithm forms semi-stochastic gradients from reference points and gradients, then updates iterates using a scaled gradient step.
Reference maintenance: Reference gradients are maintained instead of recomputed at every iteration because their reference points change only after long periods.
Overall algorithm: Algorithm 2 repeatedly executes One-epoch-SNVRG and uniformly selects an output among the epoch-level iterates.
Memory complexity: SNVRG stores K reference gradients with space complexity O(Kd), and K = O(log log n) yields eO(d) space complexity.

4 Main Theory

SNVRG combines nested reference points and gradients with multi-epoch updates to improve convergence complexity for smooth nonconvex and gradient-dominated objectives.

SNVRG convergence: SNVRG uses multiple nested loops and reference gradients, with parameters selected through One-epoch-SNVRG and repeated in Algorithm 2.The convergence analysis begins by choosing the nested-loop count, step size, batch sizes, and loop lengths for one epoch.
SNVRG convergence: Theorem 4.2 establishes an expected-gradient convergence guarantee for SNVRG under averaged Lipschitz gradients and bounded stochastic-gradient variance.The theorem uses a base batch size and epoch count depending on n, ε, variance, smoothness, and initial optimality gap.
SNVRG convergence: eO(ε^-3 ∧ n^1/2ε^-2) gradient complexity improves on SCSG’s O(ε^-10/3 ∧ n^2/3ε^-2), with speedups depending on n and ε.The stated speedup is n^1/6 when n ≲ 1/ε^2 and ε^-1/3 when n ≳ 1/ε^2.
Gradient-dominated objectives: For τ-gradient-dominated functions, SNVRG-PL targets an ε-approximate global minimizer using Algorithm 2 as a component.Theorem 4.4 specifies batch size, epoch counts, and outer iterations based on τ, variance, smoothness, and the initial optimality gap.
Gradient-dominated objectives: SNVRG-PL is strictly better than nonconvex SVRG in the first complexity summand and faster by at least n^1/6 in the second.The comparison concerns the simplified gradient complexity eO(n ∧ τε^-1 + τ(n ∧ τε^-1)^1/2) versus eO(n + τn^2/3).
Gradient-dominated objectives: Under strong convexity, the method finds an ε-approximate global minimizer within a complexity matching SVRG-lep, with further acceleration matching the best-known rate.The stated baseline complexity is eO(n + n^1/2κ), and catalyst or Katyusha techniques yield eO(n + n^3/4√κ).

5 Experiments

Experiments compare SNVRG with stochastic optimization baselines on LeNet image classification across MNIST, CIFAR10, and SVHN, with learning-rate decay results reported in Figure 3.

Experimental setup: The experiments compare SGD, SGD with momentum, ADAM, and SCSG while omitting GD and SVRG because their full-gradient calculations incur high memory cost.SCSG is a special case of SNVRG when the number of nested loops is K = 1.
Experimental setup: The study trains a standard LeNet on MNIST, CIFAR10, and SVHN image datasets.The datasets contain different image-classification tasks and training-set sizes, while LeNet uses two convolutional and three fully connected layers.
Experimental setup: Hyperparameters are tuned by grid search over batch sizes, learning rates, and batch-size ratios for the compared stochastic methods.SNVRG uses batch sizes (B, B/b, B/b^2), with B and b selected from specified grids.
Results: Figure 3 reports training loss and test top-1 error against data epochs for each dataset under learning-rate decay.Panels (a,d), (b,e), and (c,f) correspond respectively to MNIST, CIFAR10, and SVHN.
Results: With learning-rate decay, SNVRG outperforms all baseline algorithms on the reported datasets.The authors interpret this result as confirming that nested reference points and gradients can accelerate nonconvex finite-sum optimization.
Scope: The CNN experiment is intended to illustrate SNVRG’s advantage and corroborate the theory, not to claim state-of-the-art deep-neural-network training.This explicitly limits the scope of the experimental conclusion.

6 Conclusions and Future Work

The paper concludes that nested variance reduction improves finite-sum nonconvex gradient complexity while leaving optimality questions open for finite-sum and general stochastic settings.

Conclusions: The proposed stochastic nested variance-reduced method achieves substantially better gradient complexity than existing first-order algorithms for finite-sum nonconvex optimization.The conclusion frames this as partial progress on whether SVRG and SCSG dependence on n can be improved.
Future work: The finite-sum lower bound suggests the method is near optimal up to a logarithmic factor, while the general stochastic lower bound remains unknown.The authors identify deriving the general stochastic lower bound as future work.
Future work: The algorithm can be extended to nonconvex nonsmooth finite-sum optimization using proximal gradient methods.This extension is stated as a future capability rather than analyzed in the supplied conclusion passage.

A.1 Proof of Lemma 4.1

The proof of Lemma 4.1 counts reference-gradient updates and sampling costs to bound the total stochastic-gradient complexity of one SNVRG epoch.

Proof structure: The proof first establishes a supporting lemma for One-epoch-SNVRG before deriving the total gradient-computation bound.The argument then substitutes intermediate bounds into earlier inequalities.
Parameter conditions: The parameter assumptions require a step-size condition and lower bounds on the nested batch sizes.The proof uses the constant C = 100 in these assumptions.
Gradient accounting: The initial reference gradient costs B stochastic-gradient computations and is updated once at the beginning of Algorithm 1.This cost is separated from later nested reference-gradient updates.
Gradient accounting: Nested reference gradients are updated only at prescribed loop boundaries, and each sampling procedure costs 2B_l stochastic-gradient computations.The total cost T sums the initial computation and all nested updates across the loop schedules.
Complexity bound: The resulting total-gradient bound includes a logarithmic factor through the bound B + 6B log^3 B.This bound is obtained after evaluating the loop and batch parameter choices.

A.2 Proof of Theorem 4.2

The proof derives SNVRG’s gradient-complexity bound by summing per-epoch inequalities, selecting batch and epoch parameters, and accounting for stochastic-gradient work across epochs.

Theorem 4.2’s proof aggregates inequalities over S epochs to obtain the convergence bound.The derivation uses the parameter choices specified in the theorem.
Each One-epoch-SNVRG uses fewer than 7B log^3 B stochastic-gradient computations.
The total gradient complexity is obtained by multiplying the per-epoch cost by the number of epochs S.
Gradient-dominated case: Under gradient dominance, the proof applies an analogous inequality with parameters B = n ∧(4C1τσ^2/ε) and S = 1 ∨(2C1τL/B^1/2).It then uses U = log(2ΔF/ε) epochs to derive the total stochastic-gradient complexity.
Gradient-dominated case: Algorithm 3’s total cost is bounded by its U epochs, each requiring at most S · 7B log^3 B stochastic-gradient computations.

B Proof of Key Lemma A.1

Appendix B proves the key lemma through filtration-based notation, auxiliary definitions, sampling lemmas, and a final telescoping argument.

The proof introduces reference points, reference gradients, filtration, and the cumulative inner-loop length T = QK.
Definition B.1 and Lemma B.2 establish the constant-series framework used in the technical analysis.
Lemma B.3 bounds a uniform-subset sample mean for vectors whose sum is zero.
The proof of Lemma A.1 combines intermediate inequalities with Lemmas B.2 and B.3, then substitutes M = 6L.
After division by T, the resulting inequality proves Lemma A.1, with constant C = 100.

C.1 Proof of Lemma B.2

Appendix C proves Lemma B.2 by induction over nested levels, using supporting relations, conditional expectations, Young’s inequality, and telescoping across inner iterations.

The analysis defines reference-point variables, filtration, and constant series before proving relationships among nested levels.
Supporting results establish bounds such as j ·(1 + T_{s−1}) < c(s)T_s and j ·(1 + T_K) < M.
The proof uses induction from level s + 1 to level s, with index transformations connecting the corresponding inner-loop ranges.
Conditional-expectation inequalities are combined using Young’s inequality and the relationships between consecutive reference points.
Telescoping over u = 0 to T_s −1 yields the desired inequality for level s, completing the induction over all nested levels.
The supporting sample-mean result is proved by rewriting the sample mean with indicator variables and deriving the resulting bound.

D.1 Proof of Proposition C.1

Appendix D.1 proves Proposition C.1 and related supporting bounds by expanding the algorithm’s reference-gradient updates and controlling smoothness and variance terms.

Proposition C.1 follows from the definition of the reference point and the update rule in Algorithm 1.
The proof shows that reference points share initial nested components and that corresponding reference gradients remain unchanged over specified time ranges.
The relation for v(s) is derived from the definitions of v and the shared reference-gradient structure.
The constant-series inequalities are established using monotonicity, the bound (1 + 1/n)^n < 2.8, and elementary bounds on nested-loop parameters.
Lemma C.3 uses the algorithmic update, L-smoothness, Young’s inequality, and telescoping to control the objective and gradient-estimator terms.
The remaining bound decomposes an auxiliary term into J1 and J2 and applies sampling and averaged-gradient-Lipschitz arguments.

E Additional Experimental Results

Additional experiments evaluate algorithms without learning-rate decay across MNIST, CIFAR10, and SVHN, while an equivalent nested-loop SNVRG formulation specifies the algorithm’s inputs, loops, sampling, and outputs.

Additional experimental results: Experiments without learning-rate decay compare training loss and test error across MNIST, CIFAR10, and SVHN.The results are presented in Figure 4, with panels for each dataset’s training loss and test error.
Additional experimental results: The experiments use parameter settings summarized separately for MNIST, CIFAR10, and SVHN.These settings are listed in Tables 2, 3, and 4, respectively.
Equivalent nested-loop formulation: Algorithm 4 gives an equivalent nested-loop version of One-epoch-SNVRG.Its notation differs slightly from Algorithm 1 to avoid confusion and align with Figure 2.
Equivalent nested-loop formulation: The algorithm takes a function, starting point, loop parameters, step-size parameter, and batch parameters as inputs.It returns an output iterate and an endpoint iterate.
Equivalent nested-loop formulation: The nested loops repeatedly sample index sets without replacement and compute level-specific gradient quantities.Sampling and gradient updates occur across loop levels 1 through K.
Equivalent nested-loop formulation: The output iterate is selected uniformly from the generated iterates, while the endpoint is also returned.This selection occurs after the nested loops terminate.