PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Variance Reduction for Nonconvex Optimization

Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabas Poczos, Alex Smola

arXiv:1603.06160v2math.OCcs.LGcs.NEstat.ML

TL;DR

The paper addresses the limited theoretical analysis of variance-reduced methods for general nonconvex finite-sum optimization. It analyzes nonconvex SVRG and its mini-batch variant, proving faster convergence than SGD and GradientDescent, linear convergence for gradient-dominated functions, and theoretical linear speedups from mini-batching. These results concern stationarity and rely on smooth finite-sum assumptions.

  • Problem

    Existing variance-reduction analyses largely assume convexity, leaving faster stochastic methods for general nonconvex finite-sum optimization insufficiently analyzed.

  • Method

    The paper analyzes SVRG for smooth nonconvex finite-sum objectives, including a gradient-dominated variant and mini-batch extensions.

  • Results

    SVRG is shown to converge faster than SGD and GradientDescent, achieve global linear convergence on gradient-dominated functions, and obtain theoretical linear mini-batch speedups.

  • Takeaways & Limitations

    Variance reduction can improve nonconvex stochastic optimization, with benefits extending to gradient-dominated objectives and parallel mini-batching.

  • Takeaways & Limitations

    The theoretical results use the stationarity gap, which does not necessarily imply an optimality gap, low training loss, or low test error.

Abstract

from arXiv · show

We study nonconvex finite-sum problems and analyze stochastic variance reduced gradient (SVRG) methods for them. SVRG and related methods have recently surged into prominence for convex optimization given their edge over stochastic gradient descent (SGD); but their theoretical analysis almost exclusively assumes convexity. In contrast, we prove non-asymptotic rates of convergence (to stationary points) of SVRG for nonconvex optimization, and show that it is provably faster than SGD and gradient descent. We also analyze a subclass of nonconvex problems on which SVRG attains linear convergence to the global optimum. We extend our analysis to mini-batch variants of SVRG, showing (theoretical) linear speedup due to mini-batching in parallel settings.

1 Introduction

The paper studies IFO-based nonconvex finite-sum optimization, where existing variance-reduction analyses largely rely on convexity. It asks whether SVRG can improve on SGD and GradientDescent, and reports affirmative theoretical results.

  • Problem setting: Nonconvex finite-sum objectives may lack convexity, while optimization is performed using an Incremental First-order Oracle.The oracle returns a component function value and gradient for a sampled index.
  • Motivation: Existing variance-reduction analyses largely do not extend to general nonconvex functions because they rely on convexity to control variance.This gap matters for stochastic optimization of deep neural networks and other large nonconvex models.
  • Research question: The central question is whether an IFO can achieve convergence rates faster than both SGD and GradientDescent for nonconvex functions in F_n.The paper also asks how the rate depends on n and the number of iterations.
  • Main contributions: Careful parameter selection in SVRG yields faster convergence than both SGD and GradientDescent.The paper reports a factor of n^1/3 improvement over GradientDescent.
  • Novelty: The work claims the first improvement in convergence rates for SGD and GradientDescent in IFO-based nonconvex optimization.It also presents the main contributions in Table 1 through IFO-complexity comparisons.
  • Main contributions: SVRG is analyzed for nonconvex optimization, with theoretical improvements over ordinary SGD and GradientDescent.The paper additionally studies gradient-dominated functions, mini-batching, and the interplay among step size, iteration complexity, and convergence.

2 Background & Problem Setup

The paper formalizes smooth finite-sum objectives and evaluates algorithms by expected stationarity. It recalls SGD’s O(1/ϵ^2) IFO complexity and establishes the assumptions and definitions used for comparison.

  • Problem setup: The objective is a finite sum f(x) = 1/n Σ_i f_i(x), with each component assumed L-smooth.Neither f nor the individual f_i need be convex, and L is independent of n.
  • Convergence criterion: An iterate is ϵ-accurate when ||∇f(x)||^2 ≤ ϵ, while stochastic algorithms are judged by the expected gradient norm at iteration t.This stationarity criterion is used because function-value and distance-to-optimum criteria are not generally suitable for nonconvex functions.
  • Oracle and SGD: The IFO model returns (f_i(x), ∇f_i(x)) for a queried component index and point.SGD uses a uniformly random component to form an unbiased gradient estimate.
  • SGD baseline: O(1/ϵ^2) IFO calls suffice for SGD to obtain an ϵ-accurate solution under the bounded-gradient assumption.The SGD theorem uses a fixed step size selected with knowledge of the total iteration count.
  • SGD baseline: SGD’s rate is limited by variance introduced by stochastic gradients, and better rates are not generally available from this baseline.The cited discussion notes this barrier even for non-strongly convex convex problems.

3 Nonconvex SVRG

The paper analyzes SVRG for smooth nonconvex finite-sum functions, establishes stationary-point convergence rates, and identifies settings with global linear convergence. Its results quantify how step size, epoch length, and problem structure affect IFO complexity.

  • Nonconvex SVRG: SVRG is analyzed for nonconvex finite-sum functions whose objective and component functions are Lipschitz smooth, without requiring convexity.The analysis operates in the Incremental First-order Oracle framework.
  • Nonconvex SVRG: Theorem 2 provides a convergence-rate guarantee for nonconvex SVRG under positive parameter-dependent quantities Γ_t and γ_n.The theorem uses constant step size and variance-control parameters across inner iterations.
  • Nonconvex SVRG: Nonconvex SVRG converges to a stationary point at rate O(n2/3/T), with expected objective descent after every epoch.The epoch length and full-gradient computation determine the per-epoch IFO cost.
  • Nonconvex SVRG: O(n + n2/3/ϵ) IFO calls suffice for an ϵ-accurate stationary point with the parameter choice α = 2/3.This choice minimizes the IFO complexity among the α-dependent bounds in Corollary 2.
  • Gradient Dominated Functions: For τ-gradient dominated functions with τ > n1/3, SVRG achieves global linear convergence and requires O((n + τn2/3) log(1/ϵ)) IFO calls.The individual component functions need only satisfy smoothness in these results.
  • Gradient Dominated Functions: When f is strongly convex but its components may be nonconvex, the IFO complexity is O((n + n2/3κ) log(1/ϵ)), improving over SDCA when κ > n2/3.Here κ is the condition number L/λ.

4 Convex Case

The convex case admits direct SVRG analyses with explicit dependence on n. Choosing the step size to depend on n improves the IFO complexity relative to an n-independent step size.

  • 4 Convex Case: The convex analysis provides a direct treatment of SVRG rather than relying on strongly convex perturbations.The results are stated using the stationarity gap, with optimality-gap rates also available in the analysis.
  • 4 Convex Case: For convex component functions, Corollary 9 gives IFO complexity O(n + (√n/ϵ)) with m = n and η = 1/(8L√n).The step size diminishes with n.
  • 4 Convex Case: For convex component functions, Corollary 10 gives IFO complexity O(n/ϵ) with m = n and η = 1/(8L).This step size is independent of n.
  • 4 Convex Case: The dependence on n decreases from order n to √n through an n-dependent step size or a good initial point obtained, for example, by running O(n) SGD iterations.The latter alternative is described as a way to obtain a suitable starting point.
  • 4 Convex Case: The paper notes that modifying the algorithm can significantly improve the convex convergence rate, but theoretical gains for general nonconvex problems remain unclear.The cited modifications add a strongly convex perturbation or vary m across epochs.

5 Mini-batch Nonconvex SVRG

Mini-batch SVRG preserves the nonconvex convergence complexity while enabling theoretical linear speedup when batch gradients are computed in parallel. Its batch-size dependence is better than mini-batched SGD, although the IFO complexity itself does not improve.

  • The mini-batch method replaces individual stochastic-gradient sampling with sampling a mini-batch, reducing stochastic-gradient variance as batch size increases.
  • Mini-batch SVRG has 1/b dependence on batch size, compared with mini-batched SGD’s 1/√b dependence.
  • Mini-batch SVRG achieves IFO complexity O(n + (n2/3/ϵ)) for b < n2/3.
  • Parallel computation of b mini-batch gradients yields a theoretical linear speedup in multicore and distributed settings.
  • Mini-batching does not reduce SVRG’s IFO complexity because each batch gradient requires b IFO calls.

6 Comparison of the convergence rates

The comparison shows that SVRG improves dependence on accuracy and, in relevant settings, on n relative to SGD and gradient descent. These gains come with algorithm-specific trade-offs involving assumptions, step sizes, initialization, and mini-batching.

  • Dependence on n: SVRG’s IFO complexity depends on n2/3 for nonconvex problems and n1/2 for convex problems, versus n for gradient descent.
  • Dependence on ϵ: SGD requires O(1/ϵ2) IFO calls, whereas SVRG and gradient descent require O(1/ϵ) in convex and nonconvex settings.
  • Dependence on ϵ: For gradient-dominated functions, SVRG and gradient descent achieve global linear convergence.
  • Assumptions used in analysis: All algorithms assume Lipschitz continuous gradients; SGD additionally requires σ-bounded gradients and advance knowledge of T.
  • Step size / learning rates: SVRG and gradient descent use step sizes independent of T, but SVRG’s step sizes depend on n in the nonconvex analysis.
  • Dependence on initial point and mini-batch: SVRG is more sensitive to initialization than SGD, while mini-batches provide both parallelism and theoretical guarantees.

7 Best of two worlds

Msvrg selects its step size using the total iteration budget and, under σ-bounded gradients, improves convergence rates over both SGD and standard SVRG. Its nonconvex complexity is O(min{1/ϵ2, n2/3/ϵ}), but the parameter choice can be difficult in practice.

  • Msvrg uses a step size based on the total number of iterations T or the target accuracy ϵ, assuming T > n.
  • O(min{1/ϵ2, n2/3/ϵ}) is the IFO complexity of Msvrg for σ-bounded-gradient functions.
  • Convex comparison: For convex functions with σ-bounded gradients, the corresponding IFO complexity is O(min{1/ϵ2, √n/ϵ}).
  • Msvrg has faster convergence rates than both SGD and standard SVRG under additional assumptions.
  • Msvrg requires σ-bounded gradients and a step size depending on T, unlike the fixed-step-size setting emphasized for standard SVRG.

8 Experiments

The experiments evaluate nonconvex neural-network classification on CIFAR-10, MNIST, and STL-10. They compare SGD and SVRG using training loss, test error, and gradient norm against effective data passes.

  • The experiments study multiclass classification with neural networks, a typical nonconvex machine-learning problem.
  • Experimental Setup: The setup uses one fully connected hidden layer with 100 nodes, 10 softmax outputs, ℓ2 regularization, and normalized features.
  • Experimental Setup: CIFAR-10, MNIST, and STL-10 are used with predefined training and test splits.
  • SGD uses a tuned inverse-time or fixed learning-rate schedule, while SVRG uses a fixed step size selected for best training-loss performance.
  • Initialization & mini-batching: SVRG is initialized with n SGD iterations for CIFAR-10 and MNIST, and 2n iterations for STL-10, using mini-batches of size 10.
  • Results: Training loss, test error, and ∥∇f(xt)∥2 are plotted against effective data passes, counting full-gradient costs at SVRG epochs.

9 Discussion

The paper’s nonconvex SVRG analysis establishes convergence guarantees under smoothness and carefully chosen parameters, including faster rates than SGD and GradientDescent. It also identifies stationarity-based caveats and practical considerations such as initialization and mini-batching.

  • SVRG achieves faster convergence than GradientDescent by a factor of n1/3 for nonconvex finite-sum problems.
  • With fixed step size and epoch-based updates, the method obtains a descent property after every epoch, unlike ordinary SGD in general.
  • For gradient-dominated functions, a variant of SVRG achieves linear convergence to the global minimum.
  • Theoretical guarantees are stated in terms of the stationarity gap, which need not imply optimality, low training loss, or low test error.
  • The analysis uses a Lyapunov-function framework with parameters selected so that Γt remains positive and yields an iterate bound.

Proof of Theorem 3

Theorem 3 selects step size, auxiliary parameters, and epoch length as functions of n to obtain nonconvex SVRG convergence and an explicit IFO complexity bound. Subsequent results specialize these guarantees to gradient-dominated and convex settings.

  • Proof of Theorem 3: Theorem 3 sets η = µ0/(Ln^α), β = L/n^(α/2), and m = ⌊n^(3α/2)/(3µ0)⌋ for nonconvex SVRG.
  • Proof of Theorem 3: The parameter choice guarantees γn ≥ ν/(Ln^α) for a universal constant ν.
  • Proof of Theorem 3: The IFO complexity is O(n + n^α/ϵ) when α < 2/3 and O(n + n/ϵ) when α ≥ 2/3.
  • Proof of Theorem 3: The convex-case analysis recovers convergence rates for E[f(xa) − f(x∗)] from the same reasoning.

Proof of Theorem 7

The mini-batch analysis extends the nonconvex SVRG proof with batch-dependent variance bounds and parameter choices. It shows how batch size enters the convergence coefficient and supports parallel speedups within a specified range.

  • Proof of Theorem 7: Mini-batch SVRG preserves the proof structure of nonconvex SVRG while adding batch-dependent variance terms.
  • Proof of Theorem 7: The mini-batch theorem uses uniform sampling with replacement and selects epoch parameters so that the convergence coefficient γn is positive.
  • Proof of Theorem 7: For batch size b < n2/3, the parameter choice yields γn ≥ bν2/(Ln2/3).
  • Proof of Theorem 7: The analysis chooses η = µ2b/(Ln2/3), β = L/n1/3, and m = ⌊n/(3bµ2)⌋ for the mini-batch method.

H Experiments

The experiments evaluate neural-network multiclass classification on MNIST and STL-10 using objective loss, test error, and gradient norm against effective data passes. On MNIST and STL-10, SVRG and SGD show no significant difference in test error.

  • H Experiments: There is no significant difference in test error between SVRG and SGD on MNIST and STL-10.
  • H Experiments: Figure 2 reports neural-network results for MNIST and STL-10, with MNIST in the leftmost plot and STL-10 in the remaining plots.
Loading 1603.06160v2…