PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-convex Finite-Sum Optimization Via SCSG Methods

Lihua Lei, Cheng Ju, Jianbo Chen, Michael I. Jordan

arXiv:1706.09156v4math.OCcs.CC

TL;DR

The paper addresses efficient convergence for smooth non-convex finite-sum optimization, where SGD and variance-reduction methods have different accuracy and dataset-size trade-offs. It generalizes SCSG using geometrically randomized inner loops and reports uniformly better rates than SGD, no worse performance than SVRG-type methods, and empirical gains on multi-layer neural networks.

  • Problem

    Smooth non-convex optimization requires balancing SGD's avoidance of full gradients against variance-reduction methods' improved accuracy dependence.

  • Method

    The paper generalizes SCSG to non-convex finite-sum objectives with geometrically randomized inner-loop counts.

  • Results

    SCSG achieves a uniformly better rate than SGD, is never worse than SVRG-type algorithms, and outperforms SGD empirically on multi-layer neural-network training.

  • Takeaways & Limitations

    SCSG provides a practical variance-reduction alternative that improves on SGD while retaining competitiveness with SVRG-type methods.

  • Takeaways & Limitations

    A logarithmic factor in the smooth non-convex bound is identified as an artifact of the proof and can be reduced.

Abstract

from arXiv · show

We develop a class of algorithms, as variants of the stochastically controlled stochastic gradient (SCSG) methods (Lei and Jordan, 2016), for the smooth non-convex finite-sum optimization problem. Assuming the smoothness of each component, the complexity of SCSG to reach a stationary point with $\mathbb{E} \|\nabla f(x)\|^{2}\le ε$ is $O\left (\min\{ε^{-5/3}, ε^{-1}n^{2/3}\}\right)$, which strictly outperforms the stochastic gradient descent. Moreover, SCSG is never worse than the state-of-the-art methods based on variance reduction and it significantly outperforms them when the target accuracy is low. A similar acceleration is also achieved when the functions satisfy the Polyak-Lojasiewicz condition. Empirical experiments demonstrate that SCSG outperforms stochastic gradient methods on training multi-layers neural networks in terms of both training and validation loss.

1 Introduction

The paper studies smooth non-convex finite-sum optimization, where convergence is measured by squared gradient norm rather than global function-value suboptimality. It develops SCSG to address the competing accuracy and dataset-size regimes faced by SGD and variance-reduction methods.

  • Smooth non-convex finite-sum problems include settings from generalized linear models to deep neural networks.
  • Non-convex methods generally target E∥∇f(x)∥2 because smoothness alone does not guarantee convergence to a global minimum.
  • Large datasets and moderate target accuracy can make SGD advantageous because it avoids full-gradient computation.
  • SCSG is designed to match or exceed SGD in modest-accuracy regimes and existing variance-reduction methods in high-accuracy regimes.
  • SCSG generalizes to the non-convex setting under component smoothness and is reported as faster than SGD and never worse than variance-reduction methods.
  • SCSG also shows good empirical performance for training multi-layer neural networks, using variance reduction rather than momentum or adaptive stepsizes.

2 Notation, Assumptions and Algorithm

The paper defines the notation, assumptions, computational measure, and generic mini-batch SCSG procedure. Each epoch uses sampled batches, geometrically many inner updates, and randomized output, with parameter settings analyzed for complexity.

  • Notation and assumptions: The paper measures computation through IFO cost, where sampling an index and accessing a component gradient and function value each cost one unit.
  • Notation and assumptions: An ε-accurate solution satisfies E∥∇f(x)∥2 ≤ ε, and Ccomp(ε) denotes the minimum IFO complexity for reaching it.
  • Notation and assumptions: Each component function is assumed differentiable with an L-Lipschitz gradient, while the paper additionally considers the weaker Polyak-Lojasiewicz condition.
  • SCSG method: The method outputs a random sample from the epoch iterates rather than selecting the iterate with the smallest gradient norm.
  • SCSG method: SCSG draws an epoch batch uniformly and performs mini-batch SVRG-type updates, with the inner-loop count sampled from a geometric distribution.
  • Parameter settings: The generic algorithm permits varying stepsizes and batch sizes; analyzed default settings fix the inner mini-batch size at one, although larger sizes may aid vectorization.

3 Convergence Analysis

The analysis derives SCSG convergence under smooth non-convex and Polyak–Lojasiewicz settings, showing that batch and mini-batch choices determine its complexity. SCSG interpolates between SGD and SVRG and can outperform both through these parameters.

  • 3.1 One-epoch analysis: SCSG’s analysis handles an extra error term absent from SVRG without assuming bounded distance to the optimum.The bounded-distance assumption is invalid for unconstrained problems, even in convex cases.
  • 3.1 One-epoch analysis: Large mini-batches increase theoretical complexity, so most subsequent analysis restricts the mini-batch size to 1.The paper notes that larger mini-batches may still help in practice through vectorization.
  • 3.2 Convergence analysis for smooth non-convex objectives: SCSG interpolates between SGD and SVRG by leveraging batch and mini-batch sizes, enabling it to outperform both methods.The paper identifies settings with excessively large batch or mini-batch sizes as suboptimal.
  • 3.2 Convergence analysis for smooth non-convex objectives: Bj ∼ j^3/2 gives the best complexity among the class of SCSG algorithms with time-varying batch sizes.The analysis considers increasing batches because large batches are wasteful when iterates are inaccurate.
  • 3.2 Convergence analysis for smooth non-convex objectives: The logarithmic factor log^5(1/ε) in the complexity bound is an artifact of the proof and can be reduced.The paper gives a reduced logarithmic form in a subsequent remark.
  • 3.3 Convergence analysis for P-L objectives: Under the Polyak–Lojasiewicz condition, SCSG can find the global minimum and is faster than SGD while never worse than SVRG.The paper reports significant acceleration over SVRG when both μ and ε are moderate.

4 Experiments

Experiments on MNIST compare SCSG variants with mini-batch SGD using data-pass and wall-clock measures. SCSG generally achieves faster loss reduction, with time-varying batch sizes performing best in the IFO comparison.

  • Experimental setup: MNIST experiments evaluate SCSG and mini-batch SGD on fully connected and convolutional neural networks.The dataset contains 50,000 training examples and 10,000 test examples.
  • Experimental setup: The comparison includes fixed-batch SGD, fixed-batch SCSG, and time-varying-batch SCSG over 20 data passes.Fixed SCSG uses b = 32, while time-varying SCSG uses Bj = ⌈j^3/2 ∧ n⌉ and bj = ⌈Bj/32⌉.
  • IFO comparison: Both SCSG versions outperform SGD on training and validation loss under the IFO comparison, especially for training loss.Time-varying SCSG is reported as the best-performing and more stable variant.
  • Batch-size effects: Variance reduction provides a larger benefit with time-varying batch sizes than with fixed batch sizes.The comparison uses SGD with the same sequence of batch sizes and best-tuned constant stepsizes.
  • Wall-clock comparison: SCSG progresses faster in both training and validation loss than SGD in wall-clock time despite slower individual updates.The wall-clock comparison uses TensorFlow on an NVIDIA GK210 GPU in an Amazon p2.xlarge node.
  • Implementation trade-offs: Larger Bj/bj generally yields better performance in the practical ratio study.The tested values of ⌈Bj/bj⌉ are 2, 5, 10, 16, and 32.

5 Discussion

The discussion presents SCSG as a smooth non-convex finite-sum method with uniformly improved theoretical positioning relative to SGD and SVRG-type methods. It also highlights empirical neural-network performance and variance reduction as its distinct acceleration mechanism.

  • 5 Discussion: SCSG is presented as uniformly better than SGD and never worse than SVRG-type algorithms.The discussion states that SCSG significantly outperforms SVRG-type algorithms when target accuracy is low.
  • 5 Discussion: SCSG empirically outperforms SGD when training multi-layer neural networks.This is reported as an empirical result rather than a theoretical guarantee.
  • 5 Discussion: SCSG extends to general stochastic optimization by sampling an epoch batch of independent data points from the objective distribution.The proof carries over after suppressing the finite-population term I(Bj < n).
  • 5 Discussion: For smooth non-convex objectives, the stochastic extension yields a bound of ˜O(ϵ^-5/3).For P-L objectives, the stated bound is ˜O(µ^-1ϵ^-1 ∧ µ^-5/3ϵ^-2/3).
  • 5 Discussion: SCSG achieves acceleration through variance reduction, unlike momentum and adaptive-stepsize methods.The paper suggests studying combinations of these techniques in deep neural-network training.

A Technical Lemmas

The appendix develops technical lemmas supporting the SCSG analysis. These cover sampling without replacement, geometric random variables, and logarithmic bounds used in later proofs.

  • Sampling lemma: The appendix begins with a lemma on the variance of a sample mean drawn without replacement.The population consists of arbitrary vectors, and the sample is a uniform subset of fixed size.
  • Sampling lemma: The sample mean is rewritten using indicator variables for membership in the random subset.This representation is used in the proof of the sampling-variance result.
  • Geometric-variable lemma: A lemma records key properties of a geometric random variable for sequences with finite expected absolute value.The condition E|D_N| < ∞ supports the stated expectation identity.
  • Auxiliary bound: A logarithmic inequality bounds gη(x) relative to z through terms involving log(1 + log α) and η log α.The bound is obtained by taking logarithms of both sides.

B One-Epoch Analysis

The one-epoch analysis establishes integrability and second-moment groundwork for the stochastic-gradient argument under the paper’s assumptions.

  • Integrability conditions: The analysis requires finite expectations for iterate differences, objective gaps, and gradient norms.These conditions are stated for the random iterates involved in the proof.
  • Second-moment bound: The proof begins by bounding the conditional second moment of the stochastic update quantity.It invokes the variance decomposition E||Z||^2 = E||Z − EZ||^2 + ||EZ||^2.
  • Second-moment bound: The stated second-moment result depends on Assumption A1.The proof explicitly uses the assumption in its final step.

Lemma B.3

The lemma derives bounds by conditioning on independent randomness, taking expectations over geometric inner-loop lengths, and applying earlier lemmas to primal and dual gaps.

  • The analysis conditions on the previous iterate and uses independence of the sampled index to apply Lemma A.1.
  • Bounds for primal and dual gaps are derived from Lemmas A.2, B.1, B.2, and B.3.
  • Expectations are taken over all randomness, including sampled indices and the geometric inner-loop length.
  • The proof completes by substituting the randomized iterate and taking expectation over past randomness.

Lemma B.6

The lemma combines inductive inequalities with geometric-loop sampling and expectation arguments to establish the stated claims, with later claims following from the first two.

  • The first two claims are proved by induction using inequalities established in the proofs of Lemmas B.4 and B.5.
  • The proof controls cross terms using 2⟨a, b⟩= ∥a∥2/c + c∥b∥2 −∥a −cb∥2/c for c > 0.
  • The step-size condition η_jL ≤ 1/4 is used when substituting one inequality into another.
  • N_j is sampled geometrically, and expectation over it is combined with Lemmas A.2 and B.1.
  • The remaining claims follow as simple consequences of the first two claims and the inequality ⟨a, b⟩≤∥a∥2/2+∥b∥2/2.

C Convergence Analysis for Smooth Objectives

The convergence analysis studies a piecewise bound W(T), proves it decreases with the iteration budget, and derives complexity bounds by separating regimes around T∗.

  • Theorem 3.2 and its corollaries analyze convergence through the function W(T).
  • W(T) is strictly decreasing on both sides of the threshold T∗ and therefore strictly decreasing overall.
  • The bound for T(ϵ) is obtained by distinguishing the cases T < T∗ and T > T∗.
  • The two regimes are represented by decreasing functions W_1(T) and W_2(T), both converging to zero as T approaches infinity.
  • The computation-complexity bound follows by relating the required iteration budget to the resulting function of T.
  • A remark states that the logarithmic factor in the bound can be reduced.

D Convergence Analysis for P-L Objectives

For Polyak–Lojasiewicz objectives, the proof applies an inequality derived from the smooth-objective analysis and iterates it across the optimization steps.

  • Theorem 3.5 begins by combining equation (22) from Theorem 3.2 with the Polyak–Lojasiewicz condition.
  • The resulting inequality is applied iteratively for j = T, T −1, . . . , 1 to prove the theorem.
  • A later reformulation uses the constant 6 in the preceding bound to obtain an alternative expression.
Loading 1706.09156v4…