PaperlayerView exact revision on arXiv

Source-linked AI summary

Variance Reduction for Faster Non-Convex Optimization

Zeyuan Allen-Zhu, Elad Hazan

arXiv:1603.05643v2math.OCcs.DScs.LGcs.NEstat.ML

TL;DR

The paper studies first-order optimization for non-convex machine-learning problems and applies variance reduction based on SVRG. Its method achieves a 1/ε convergence rate and is guaranteed to be at least Ω(n^1/3) faster than gradient descent, with practical cost caveats for neural-network training.

  • Problem

    Non-convex optimization arises in machine-learning applications including graphical-model inference, topic models, dictionary learning, and deep-neural-network training, motivating generic optimization methods.

  • Method

    The paper uses SVRG-based variance reduction and analyzes the variance through the squared distance between the current point and the latest snapshot.

  • Results

    The method achieves a non-trivial 1/ε convergence rate independent of σ^2 and is guaranteed to be at least Ω(n^1/3) faster than gradient descent.

  • Takeaways & Limitations

    Among first-order methods, the paper theoretically outperforms gradient descent without additional assumptions for the stated non-convex problem.

  • Takeaways & Limitations

    For large-scale neural networks, storing per-example snapshot gradients is memory-inefficient and SVRG can have a sequential per-iteration cost 11/6 greater than SGD.

Abstract

from arXiv · show

We consider the fundamental problem in non-convex optimization of efficiently reaching a stationary point. In contrast to the convex case, in the long history of this basic problem, the only known theoretical results on first-order non-convex optimization remain to be full gradient descent that converges in $O(1/\varepsilon)$ iterations for smooth objectives, and stochastic gradient descent that converges in $O(1/\varepsilon^2)$ iterations for objectives that are sum of smooth functions. We provide the first improvement in this line of research. Our result is based on the variance reduction trick recently introduced to convex optimization, as well as a brand new analysis of variance reduction that is suitable for non-convex optimization. For objectives that are sum of smooth functions, our first-order minibatch stochastic method converges with an $O(1/\varepsilon)$ rate, and is faster than full gradient descent by $Ω(n^{1/3})$. We demonstrate the effectiveness of our methods on empirical risk minimizations with non-convex loss functions and training neural nets.

1 Introduction

The paper targets generic first-order optimization for smooth non-convex objectives, where prior theory gave only GD and SGD guarantees. It introduces variance-reduced methods that improve the iteration and running-time trade-offs without additional assumptions.

  • Motivation: Non-convex optimization underlies graphical-model inference, topic models, dictionary learning, and deep neural-network training.
  • Problem setting: The paper studies finding an ε-approximate stationary point for sums of differentiable, possibly non-convex, L-smooth functions.The target satisfies ∥∇f(x)∥2 ≤ ε.
  • Our result: Variance reduction based on SVRG yields an ε-stationary point in O(1/ε) iterations and is at least Ω(n^1/3) faster than GD.The result is independent of the stochastic-gradient variance σ^2 and is the first theoretical improvement over GD for this general problem.
  • Our result: The method modifies SVRG with epochs of length proportional to n, weighted snapshot averaging, and a variance bound based on snapshot distance.The analysis bounds variance by O(∥x_k − x̃∥2).
  • Extensions: The framework extends to mini-batches and differing or upper-lower smoothness parameters, while its strongly convex extension is not faster than SVRG+Catalyst.For mini-batch size b, the speedup over GD is O((n/b)^1/3).

2 Notations and Algorithm

This section establishes notation for the simplified SVRG analysis and notes that the full proof uses a weighted snapshot choice. It also records an extension to gradient-dominated functions.

  • Problem and algorithm: The paper assumes differentiable component functions with L-Lipschitz gradients and analyzes a simplified version of its non-convex SVRG method.The high-level proof explicitly relies on simplification assumptions, while the formal convergence proof is included in the full paper.
  • Algorithmic refinement: The final proof replaces the simplified last-iterate snapshot with a weighted average of the previous epoch’s last m^2/3 iterates.The paper reports that this weighted choice also performs better empirically.
  • Extension: For gradient-dominated functions, the main theorem gives a gradient-norm guarantee in terms of the initial objective gap and the domination parameter τ.The supplied passage states the gradient-dominated condition f(x) − f(x*) ≤ τ∥∇f(x)∥2.
  • Notation: Algorithm 1 updates iterates using a fixed step length η and stochastic indices selected during each epoch.The notation distinguishes epoch and iteration indices, sampled indices, gradients, estimators, and variance.

3 Two Useful Lemmas

The analysis combines gradient-descent and mirror-descent inequalities for unbiased gradient estimators, accounting explicitly for estimator variance. Its novelty is applying mirror-descent analysis to a smooth non-convex objective.

  • Proof interpretation: The update can be interpreted as a Euclidean mirror-descent step, enabling mirror-descent analysis in the proof.
  • Gradient descent: The gradient-descent lemma bounds expected objective decrease between consecutive iterates while accounting for gradient-estimator variance.It applies to unbiased estimators and a sufficiently small step length.
  • Mirror descent: The mirror-descent lemma is applied to a non-convex but smooth function using an unbiased gradient estimator.This is a novel use of classical mirror-descent analysis in the paper’s setting.
  • Proof interpretation: The proof uses the three-point Bregman-divergence equality and lower smoothness rather than convexity to relate gradient inner products to function differences.The resulting inequality includes a quadratic distance term involving L.
  • Proof structure: The main theorem linearly couples the gradient and mirror-descent lemmas with a variance upper-bound lemma.The variance term is incorporated through the estimator’s second-moment decomposition.

4 Upper Bounding the Variance

The paper develops a variance analysis for non-convex SVRG that bounds estimator variance using objective differences rather than distance to a global minimum. Its proof uses weighted telescoping over subepochs to handle non-convexity.

  • High-Level Ideas: Variance reduction traditionally tracks estimator variance through distance to the minimum, but that strategy fails when gradient methods need not reach a global minimum.The paper instead analyzes distances between iterates and snapshots.
  • High-Level Ideas: The proposed analysis upper-bounds variance using the objective difference between the epoch’s first and last iterates.This produces an average-variance bound proportional to f(x0) − f(xm).
  • Proof Technique: Non-convexity prevents telescoping across a full epoch, so the proof divides each epoch into O(m1/3) subepochs of O(m2/3) iterations.The step length is set to η = 1/(m2/3L), making subepoch telescoping possible.
  • Proof Technique: The analysis uses weighted sums of consecutive one-step inequalities so norm-square terms telescope within each subepoch.The weights remain within a constant factor, motivating a simplifying equal-weight assumption.
  • Variance Bound: A novel variance upper bound is derived from smoothness and vector inequalities, then combined across subepochs to obtain the epoch-level guarantee.The resulting bound controls average estimator variance by a constant times f(x0) − f(xm).

5 Final Theorem

The final theorem applies the non-convex SVRG analysis with epoch length m = n and appropriately chosen subepoch parameters. It yields a stationary point with an iteration complexity that improves on full gradient descent by Ω(n1/3), while each SVRG iteration costs at most twice an SGD iteration.

  • Proof of Theorem 5.1: The total iteration bound follows by combining the epoch-level descent guarantee with the variance upper bound and telescoping across epochs.The construction links single-epoch progress to the final stationary-point result.
  • Output Selection: Randomly selecting an epoch and inner iteration provides the output iterate used in the convergence guarantee.The paper notes that averaging iterates is common in non-convex GD and SGD but often unnecessary in practice.
  • Theorem 5.1: With m = n and η = Θ(1/(n2/3L)), Algorithm 1 produces an output x satisfying the theorem’s stated gradient-norm guarantee.These parameter choices set the subepoch scale to m0 = Θ(n2/3).
  • Running Time: Ω(n1/3) faster than full gradient descent is achieved because amortized SVRG per-iteration complexity is at most twice that of SGD.The comparison concerns solving the sum-of-smooth-functions objective in the paper’s setting.

6 Experiments

Experiments evaluate SVRG on non-convex ERM and neural-network training, comparing losses, learning rates, mini-batch sizes, and SGD baselines. SVRG performs especially well at small training errors and on more non-convex objectives, while sigmoid loss is strongest with outliers.

  • 6.1 Empirical Risk Minimization with Non-Convex Loss: SVRG uses six losses on 12 binary-classification datasets created by combining four datasets with three label-flip rates.The losses include logistic, squared, three smoothed hinge variants, and sigmoid; label flips introduce outliers.
  • 6.1 Empirical Risk Minimization with Non-Convex Loss: Sigmoid loss is strongest on datasets with many outliers, while square loss is almost always dominated for binary classification.On datasets without label flips, sigmoid is comparable to hinge or logistic loss.
  • 6.1 Empirical Risk Minimization with Non-Convex Loss: SVRG running time is quite comparable across convex and non-convex loss functions on these datasets.Testing accuracy is plotted against dataset passes, with SVRG iterations counted as 1/n pass and full-gradient computations as one pass.
  • 6.1 Empirical Risk Minimization with Non-Convex Loss: SVRG is especially fast at small training error, whereas it is not necessarily better than SGD when training error is large.The comparison fixes λ and evaluates training-objective convergence using dataset passes.
  • 6.1 Empirical Risk Minimization with Non-Convex Loss: Smaller λ makes the objective more non-convex, and SGD performs worse than SVRG in these cases.The reported objective differences depend on λ, with larger differences shown for λ = 10^-6 than for λ = 10^-3 on web.
  • 6.2 Neural Network: Neural-network experiments show a performance advantage for SVRG-based algorithms over SGD and AdaGrad; adaptive rates and smaller mini-batches further improve running time.The experiments compare SVRG variants, including adaptive learning rates and mini-batch size b = 16.

A Detailed Proof

The detailed proof analyzes one epoch using subepochs and a carefully chosen initialization sequence. The full non-convex algorithm instead starts each epoch from a non-uniform random iterate of the previous epoch's final subepoch.

  • Epoch setup: The proof analyzes a single epoch by setting η = 1/(m0L), choosing m0 to divide m, and dividing the epoch into d = m/m0 subepochs.The analysis also initializes preceding negative-index iterates identically for notational convenience.
  • Algorithmic modification: Algorithm 2 replaces the previous epoch's last iterate with a non-uniform random iterate from its last subepoch as the next epoch's starting vector.The passage identifies this change as crucial for the analysis without simplification assumptions.

A.1 Upper Bounding the Variance

The variance analysis bounds average within-epoch variance through distances between iterates separated by m0 steps, then combines weighted inequalities under a restriction on m0.

  • Variance-distance relation: The upper-bound lemma relates average variance within an epoch to average squared distances between vectors separated by m0 iterations.This establishes the bridge from gradient-estimator variance to iterate movement.
  • Distance decomposition: The proof relies on initializing the negative-index iterates identically and decomposing long distances into sums of m0-step distances.This decomposition is used when summing the squared-distance bounds over possible iterations.
  • Weighted summation: The proof handles negative indices and defines weighted coefficients β0, …, βm0−1 for summing the distance inequalities across the epoch.The coefficients satisfy 1 ≥ βt ≥ 1/e > 1/3.
  • Weighted summation: The analysis repeatedly relaxes and sums inequalities to obtain a weighted control of the relevant iterate-distance terms.The derivation includes telescoping, vector inequalities, and a variance bound applied to the resulting summation.
  • Parameter condition: The required parameter condition is m0 ≤ 1/(6η^2L^2d^2), which ensures the weighted bounds remain valid.The proof explicitly uses this condition when controlling the coefficient sum.

A.2 Objective Decrease using Gradient Descent

The objective-decrease analysis replaces a single whole-epoch decrease bound with a weighted sum of decreases at the epoch's final iterates, matching the variance bound.

  • Weighted objective decrease: The proof lower-bounds a weighted sum of f(x0) − f(xt) for t ∈ {m, m−1, …, m−m0+1}, rather than only f(x0) − f(xm).This choice makes the objective-decrease inequality consistent with the left side of Lemma A.5.
  • Weighted objective decrease: For each j from 1 through m0, the proof telescopes the per-iteration descent inequality and then assigns a positive weight to each resulting inequality.Summing these weighted inequalities produces the desired bound.

A.3 Final Theorem

The final theorem combines the variance and objective-decrease lemmas across epochs, selects a random stopping iterate, and chooses parameters yielding the stated stationarity complexity.

  • Epoch aggregation: The proof combines Lemmas A.5 and A.6 to obtain a single-epoch result, then telescopes that result across epochs.Epoch initialization uses the random stopping vector from the previous epoch.
  • Output selection: The output is selected uniformly at random from the epoch iterates after the analysis has established an average gradient-norm bound.The stopping-vector construction uses a weighted random choice among the last m0 iterates of an epoch.
  • Parameter choice: Choosing m = n and m0 = Θ(m2/3) = Θ(n2/3) sets the epoch length and subepoch scale used in the final parameter selection.The step length is correspondingly η = 1/(m0L).
  • Final guarantee: Theorem A.9 gives the formal statement of the non-convex guarantee for Algorithm 2 under the selected parameters.The theorem passage is followed by the corresponding output guarantee and iteration-complexity statement.
  • Final guarantee: To obtain a point satisfying ∥∇f(x)∥2 ≤ ε, the paper states the total iteration requirement for Algorithm 1 and notes a probability guarantee via Markov's inequality.The probability statement gives at least 2/3 for the same asymptotic upper bound on the deterministic gradient norm.
  • Empirical evaluation: The experiments compare SVRG across loss functions and compare SGD with SVRG on training error and neural-net test accuracy.Figure 4 varies loss functions, Figure 5 compares SGD and SVRG, and Figure 6 reports neural-net test accuracy.
Loading 1603.05643v2…