PaperlayerView exact revision on arXiv

Source-linked AI summary

Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron

Sharan Vaswani, Francis Bach, Mark Schmidt

arXiv:1810.07288v3cs.LGstat.ML

TL;DR

Modern expressive models can interpolate training data, but conventional SGD uses diminishing step-sizes and has sub-linear rates. This paper exploits stochastic-gradient growth conditions to analyze constant-step-size SGD, with and without Nesterov acceleration, across convex, strongly-convex, and non-convex settings. The results include deterministic-rate guarantees and an O(1/k^2) accelerated stochastic-perceptron mistake bound under additional assumptions.

  • Problem

    Conventional SGD requires step-size decay and consequently has sub-linear convergence rates, motivating analysis of faster stochastic optimization under interpolation.

  • Method

    The paper analyzes constant-step-size SGD under strong and weak stochastic-gradient growth conditions, adding Nesterov acceleration and studying finite-sum interpolating losses.

  • Results

    The paper proves deterministic convergence rates for constant-step-size SGD, including accelerated convex and strongly-convex rates, non-convex stationarity, and an O(1/k^2) accelerated stochastic-perceptron mistake bound.

  • Takeaways & Limitations

    Under interpolation-like growth conditions, constant-step-size SGD can attain corresponding deterministic rates, including accelerated and non-convex settings.

  • Takeaways & Limitations

    The additive-error analysis introduces a noise term, and the perceptron O(1/k^2) result requires additional assumptions.

Abstract

from arXiv · show

Modern machine learning focuses on highly expressive models that are able to fit or interpolate the data completely, resulting in zero training loss. For such models, we show that the stochastic gradients of common loss functions satisfy a strong growth condition. Under this condition, we prove that constant step-size stochastic gradient descent (SGD) with Nesterov acceleration matches the convergence rate of the deterministic accelerated method for both convex and strongly-convex functions. We also show that this condition implies that SGD can find a first-order stationary point as efficiently as full gradient descent in non-convex settings. Under interpolation, we further show that all smooth loss functions with a finite-sum structure satisfy a weaker growth condition. Given this weaker condition, we prove that SGD with a constant step-size attains the deterministic convergence rate in both the strongly-convex and convex settings. Under additional assumptions, the above results enable us to prove an O(1/k^2) mistake bound for k iterations of a stochastic perceptron algorithm using the squared-hinge loss. Finally, we validate our theoretical findings with experiments on synthetic and real datasets.

1 Introduction

The paper targets slow SGD convergence by exploiting interpolation, showing that growth conditions enable constant-step-size SGD to match deterministic rates, including accelerated and non-convex settings.

  • Motivation: SGD-like methods use decaying step-sizes and therefore achieve sub-linear convergence rates.The cited introduction reports O(1/k) rates for strongly-convex and convex functions, respectively, though the passage is truncated after the first rate expression.
  • Interpolation: Interpolation makes per-example stochastic gradients converge to zero at the optimum in expressive models.The paper highlights non-parametric regression and over-parameterized deep neural networks as examples of models able to fit training data completely.
  • Strong growth condition: Under the strong growth condition, constant-step-size SGD with Nesterov momentum attains deterministic accelerated rates for strongly-convex and convex functions.This result provides theoretical support for using Nesterov acceleration with SGD.
  • Strong growth condition: Under the strong growth condition, constant-step-size SGD finds first-order stationary points as efficiently as deterministic gradient descent for non-convex objectives.The authors describe this as their first analysis of accelerated and non-convex rates under the strong growth condition.
  • Weak growth condition: The weak growth condition suffices for optimal constant-step-size SGD rates on smooth strongly-convex and convex functions.Under interpolation, the paper states that all smooth convex finite-sum loss functions satisfy this weaker condition.
  • Perceptron application: Under additional assumptions, the results yield an O(1/k^2) mistake bound for an accelerated stochastic perceptron using squared-hinge loss.The paper also evaluates its theoretical claims on synthetic and real datasets.

2 Background

The background defines SGD updates and finite-sum losses, then introduces interpolation and gradient-growth conditions used to analyze constant-step-size convergence.

  • SGD setup: SGD updates parameters using a noisy gradient and step-size: w_k+1 = w_k − η_k∇f(w_k, z_k).The gradients are assumed unbiased, so their expectation equals the full gradient.
  • Finite-sum objectives: Finite-sum objectives cover losses for models ranging from logistic regression and least squares to non-parametric regression and deep neural networks.The passage lists squared, hinge, and squared-hinge losses as common examples.
  • Finite-sum SGD: In finite-sum learning, SGD randomly selects a component loss, evaluates its gradient, and performs a descent step.Random point selection is the source of gradient noise, and unbiasedness holds automatically.
  • Convergence background: Standard SGD requires decreasing step-sizes, producing sub-linear convergence rates for convex and strongly-convex functions.The cited background specifies step-size decay at rates involving 1/√k for convex functions and 1/k for strongly-convex functions.
  • Assumptions: Some results additionally require a finite-sum structure, which the paper states explicitly when needed.
  • Interpolation: Interpolation means expressive models fit labeled training data completely, yielding zero training loss for losses lower-bounded by zero.It also implies that each per-example gradient converges to zero at the optimum.
  • Strong growth condition: The strong growth condition relates stochastic-gradient squared norms to the squared norm of the full gradient and implies interpolation.When the full gradient is zero, the condition requires every component gradient to be zero.

3 SGD with Nesterov acceleration under the SGC

Under the strong growth condition, constant-step-size SGD with Nesterov acceleration achieves accelerated convergence rates for smooth strongly-convex and convex functions.

  • Algorithm: The algorithm updates three sequences, (w_k, ζ_k, v_k), using a constant SGD step-size and Nesterov acceleration parameters.The step-size is η, while α_k, β_k, and γ_k are tuned according to f's properties.
  • Proof strategy: The analysis extends Nesterov’s accelerated coordinate-descent proof to SGD under the strong growth condition.The coordinate-descent analogy uses the fact that zero optimal gradient implies zero component gradients in the finite-sum setting.
  • Strongly-convex case: Under L-smoothness and μ-strong convexity, SGC-based SGD with Nesterov acceleration satisfies the stated accelerated convergence rate.The theorem specifies parameters and establishes the rate for the strongly-convex case.
  • Convex case: Under L-smoothness and convexity, the same approach establishes the stated accelerated convergence rate for convex functions.The convex theorem likewise uses an SGC-dependent parameter choice.
  • Result: The resulting rate matches the deterministic accelerated rate up to a ρ^2 factor in both strongly-convex and convex settings.This provides a theoretical basis for using Nesterov momentum with SGD.

4 SGD for non-convex functions satisfying the SGC

For smooth non-convex objectives satisfying the strong growth condition, constant-step-size SGD reaches stationary points at the deterministic O(1/k) rate; adding PL yields linear convergence.

  • Non-convex convergence: Under the strong growth condition, constant-step-size SGD finds a first-order stationary point as efficiently as deterministic gradient descent.The result concerns smooth non-convex objectives and uses η = 1/(ρL).
  • Non-convex convergence: The method attains the optimal O(1/k) convergence rate for non-convex functions under the strong growth condition.The paper presents this as an interpolation-like non-convex result and compares it favorably with recently proposed SGD improvements.
  • Applicability: The result applies to sigmoid-activation neural networks when the strong-growth condition is satisfied.The paper connects this case to over-parameterized non-convex models such as deep neural networks.
  • PL condition: With the additional Polyak–Łojasiewicz condition, constant-step-size SGD achieves linear convergence under smoothness and SGC.The theorem uses η = 1/(ρL).
  • PL condition: The PL-based result covers optimization problems including neural networks, matrix completion, and phase retrieval when SGC also holds.The cited examples are described as satisfying PL or a related restricted strong-convexity condition.
  • Related work: Compared with related PL-based work, the paper notes that Bassily et al. use a much smaller step-size η = μ/L^2 and do not assume SGC.The paper states that its SGC result is more widely applicable than results requiring additional assumptions that imply SGC.

5 Weak growth condition

The weak growth condition (WGC) relaxes the strong growth condition and is sufficient for deterministic-rate convergence of constant-step-size SGD in smooth convex settings.

  • WGC is defined for L-smooth functions with a minimum and bounds stochastic-gradient growth relative to function suboptimality.
  • At a minimizer, WGC implies every individual gradient vanishes, thereby implying interpolation.
  • SGC implies WGC with the same constant, while WGC plus the PL inequality implies SGC with a worse constant.
  • For convex functions, SGC also implies WGC with the same constant.
  • Constant-step-size SGD under WGC attains deterministic convergence rates for smooth strongly-convex and convex functions, with iterate averaging required in the convex case.
  • The WGC-based strongly-convex result avoids the additional condition-number dependence that follows from deriving SGC through WGC and strong convexity.

6 Growth conditions in practice

Under interpolation, smooth finite-sum convex losses satisfy the WGC, while squared-hinge losses satisfy the SGC under linearly separable finite-support data.

  • Smooth finite-sum convex problems under interpolation satisfy the WGC with ρ = Lmax/L.
  • The WGC therefore covers common squared and squared-hinge losses, yielding linear convergence for strongly-convex cases when all component smoothness constants equal L.
  • Squared-hinge loss satisfies the SGC when data is linearly separable with margin τ and has finite support of cardinality c.
  • Under these assumptions, the squared-hinge SGC constant is ρ = cτ^2.
  • The squared-hinge SGC lemma is used to derive a mistake bound for the perceptron algorithm.

7 Implication for Faster Perceptron

The paper applies its growth-condition results to a squared-hinge perceptron and obtains an accelerated mistake bound under additional separability and finite-support assumptions.

  • The modified perceptron trains a binary linear classifier using squared-hinge loss and can be viewed as SGD on per-example losses.
  • For linearly separable data, the squared-hinge loss fits the training data and has zero loss at an optimum.
  • SGD with constant step-size η = 1/4 yields an expected-loss bound of E[f(wk+1)] ≤ 8/(τ^2k).
  • A lemma based on Markov’s inequality converts the training-loss bound into a mistake bound.
  • The accelerated perceptron achieves O(1/k^2) dependence while using one gradient per iteration, but requires additional assumptions and has worse margin dependence.
  • Batch accelerated gradient descent also gives a 1/k^2 mistake bound, improving on existing 1/k bounds, but is deterministic rather than stochastic.

8 Experiments

Experiments on synthetic and real classification datasets compare constant-step-size SGD with accelerated SGD, finding faster convergence for acceleration in the synthetic setting and similar performance for one real-data comparison.

  • Synthetic experiments use n = 8000 linearly separable examples in dimension d = 100 and vary the margin τ while plotting logarithmic loss against effective data passes.
  • The experiments compare constant-step-size SGD with Nesterov-accelerated SGD using margin-dependent step-size settings.
  • Acc-SGD is consistently stable and converges faster than SGD on the synthetic datasets.
  • For larger margins, the synthetic training loss reaches zero, verifying interpolation in those experiments.
  • Real-data experiments use CovType and Protein with 8000 subsampled points, radial-basis features, and squared-hinge loss.
  • On Figure 2(a), the two variants perform similarly, whereas on Figure 2(b), Acc-SGD converges considerably faster than SGD.

9 Conclusion

Under interpolation, constant-step-size SGD with or without Nesterov acceleration can match deterministic convergence rates, while experiments show faster or better empirical performance for accelerated variants in supported settings.

  • 9 Conclusion: Under interpolation, stochastic gradients of common loss functions satisfy growth conditions that support constant-step-size SGD convergence.The conclusion frames these growth conditions as the basis for the paper’s theoretical results.
  • 9 Conclusion: Constant-step-size SGD with and without Nesterov acceleration achieves convergence rates corresponding to deterministic settings.The conclusion states this for the settings covered by the paper’s interpolation-like conditions.
  • 9 Conclusion: Accelerated SGD with η = τ/L converges faster than SGD with η = 1/L on a synthetic linearly separable dataset.Figure 1 compares the methods using the dataset’s margin τ.
  • 9 Conclusion: Accelerated SGD achieves better performance than SGD with η = 1/L on CovType and Protein experiments using RBF features.Figure 2 evaluates linear classifiers on both datasets.

A Incorporating additive error for Nesterov acceleration

This appendix extends Nesterov-accelerated SGD analysis to strong growth conditions with additive error, deriving parameterized convergence results for strongly-convex and convex objectives.

  • A Incorporating additive error for Nesterov acceleration: The analysis assumes L-smoothness, convexity or strong convexity, and a strong growth condition with additive error σ.The appendix explicitly treats the more general strong-growth condition with additive error σ^2.
  • A Incorporating additive error for Nesterov acceleration: Theorem 7 gives a convergence rate for Nesterov-accelerated SGD on L-smooth, µ-strongly-convex functions under the additive-error SGC.The theorem uses a specified choice of algorithm parameters.
  • A Incorporating additive error for Nesterov acceleration: Theorem 8 gives a convergence rate for Nesterov-accelerated SGD on L-smooth convex functions under the additive-error SGC.The convex result likewise depends on a specified parameter choice.
  • A Incorporating additive error for Nesterov acceleration: The proof develops Nesterov update relations, takes expectations using unbiased stochastic gradients, and applies smoothness, convexity, or the PL inequality.The appendix derives the strongly-convex and convex cases through lemmas and parameter relations.
  • A Incorporating additive error for Nesterov acceleration: For squared-hinge loss, the strong growth constant depends on the support-size and margin assumptions, with ρ = c/τ^2 in the stated derivation.The appendix considers finite support and distributions over finitely many values when characterizing c and ρ.

C Additional experimental results

Additional experiments evaluate line-search variants of SGD and accelerated SGD on synthetic and real datasets, finding stable accelerated line-search behavior but occasional advantages for ordinary SGD line search.

  • C Additional experimental results: The experiments use line search for constant-step-size SGD and for accelerated SGD, producing SGD(LS), Acc-SGD(LS), and Acc-SGD(T) variants.The accelerated line search searches for an appropriate value of ρL.
  • C Additional experimental results: Accelerated SGD with line search is stable across datasets.This is the first observation reported from the additional experiments.
  • C Additional experimental results: Acc-SGD(LS) either matches or outperforms Acc-SGD(T).The comparison concerns accelerated SGD with and without the line-search heuristic.
  • C Additional experimental results: In some cases, SGD(LS) converges faster empirically than the accelerated variants.The authors identify this as an observed case rather than a universal outcome.
  • C Additional experimental results: Figures 3 and 4 compare SGD and accelerated-SGD variants on synthetic linearly separable data and RBF-feature CovType and Protein datasets.The captions specify the datasets and comparison targets but do not state an additional outcome.
Loading 1810.07288v3…