PaperlayerView exact revision on arXiv

Source-linked AI summary

From Averaging to Acceleration, There is Only a Step-size

Nicolas Flammarion, Francis Bach

arXiv:1504.01577v1stat.MLmath.OC

TL;DR

For non-strongly-convex quadratic problems, the paper examines how averaging, acceleration, and heavy-ball relate, including with noisy gradients. It reformulates these methods as constant-parameter second-order difference equations and analyzes their stability. The analysis links stability to O(1/n^2) convergence and motivates an algorithm combining benefits of acceleration and averaging under specified noise conditions.

  • Problem

    The paper examines how averaging, acceleration, and heavy-ball relate for non-strongly-convex quadratic problems, including when gradients are noisy.

    Source: §1 · p. 2

  • Method

    The paper reformulates averaging, acceleration, and non-strongly-convex heavy-ball as constant-parameter second-order difference equation algorithms and analyzes their stability.

    Source: §1 · p. 2

  • Results

    Stable systems converge at O(1/n^2), and the joint analysis covers averaging and acceleration for non-strongly-convex quadratic functions with noiseless and noisy gradients.

    Source: §1 · p. 2, §6 · p. 14

  • Takeaways & Limitations

    The resulting algorithm class can combine faster forgetting of initial conditions with better noise robustness when noise covariance is proportional to the Hessian.

    Source: §6 · p. 14

    The analysis of the algorithm class is limited to quadratic functions, and the result does not apply to regular stochastic gradient descent for least-squares.

    Source: §4.3 · p. 11, §6 · p. 14

Abstract

from arXiv · show

We show that accelerated gradient descent, averaged gradient descent and the heavy-ball method for non-strongly-convex problems may be reformulated as constant parameter second-order difference equation algorithms, where stability of the system is equivalent to convergence at rate O(1/n 2), where n is the number of iterations. We provide a detailed analysis of the eigenvalues of the corresponding linear dynamical system , showing various oscillatory and non-oscillatory behaviors, together with a sharp stability result with explicit constants. We also consider the situation where noisy gradients are available, where we extend our general convergence result, which suggests an alternative algorithm (i.e., with different step sizes) that exhibits the good aspects of both averaging and acceleration.

1 Introduction

The paper unifies acceleration, averaging, and non-strongly-convex heavy-ball methods for quadratic problems through a second-order difference equation. It analyzes stability and eigenvalue behavior, and extends the framework to noisy gradients to motivate an intermediate algorithm.

Background

  • Acceleration improves the convex-case function-value rate from O(1/n) to O(1/n^2), while averaging is especially advantageous with random unbiased gradients.For least-squares regression with stochastic gradients, averaging achieves O(1/n) rates even without strong convexity.Source: §1 · pp. 1–2

Section 4

  • With random zero-mean gradient noise, the joint analysis motivates an intermediate algorithm combining acceleration’s quick forgetting of initial conditions with averaging’s noise robustness.The proposed algorithm uses different step sizes.Source: §1 · p. 2

Section 2

  • Accelerated gradient descent, averaged gradient descent, and non-strongly-convex heavy-ball can be expressed as constant-parameter second-order difference algorithms, with stability equivalent to O(1/n^2) convergence.The contribution is framed for quadratic problems.Source: §1 · p. 2

Section 3

  • The paper analyzes the linear system’s eigenvalues, identifying oscillatory and non-oscillatory behaviors and giving a sharp stability result with explicit constants.Source: §1 · p. 2

2 Second-Order Iterative Algorithms for Quadratic Functions

For quadratic optimization, the section develops a constant-coefficient second-order recursion and connects its stability to convergence. It then shows how averaged gradient descent, accelerated gradient descent, and heavy-ball fit this framework through different step-size choices.

2 Second-Order Iterative Algorithms for Quadratic Functions

  • The method studies quadratic functions because computing the Hessian inverse can be too expensive when the dimension is large.Source: §2 · pp. 2–3

2.1 Second-order algorithms

  • Scaling the optimization error by n turns the convergence question into stability of a constant-term second-order system.Bounded function values in the scaled system yield O(1/n^2) convergence.Source: §2.1 · p. 3
  • The recursion can be written as a modified gradient update with two potentially different affine combinations of past iterates, a reformulation used for noisy gradients.Source: §2.1 · p. 4

2.2 Examples

  • Averaged gradient descent maps to α = 0, β = γ; accelerated gradient descent to α = γ, β = γ; and heavy-ball to α = γ, β = 0.The accelerated example uses δ_n = 1 − 2/(n+1) in this framework.Source: §2.2 · pp. 4–5

3 Convergence with Noiseless Gradients

For noiseless quadratic problems, the analysis studies a constant-coefficient second-order recurrence across Hessian eigenspaces. Its stability, eigenvalue regimes, and general bound characterize convergence and distinguish the classical methods.

3 Convergence with Noiseless Gradients

  • After rescaling the iterate error by n, the analysis reduces the quadratic problem to a constant-coefficient recurrence that decouples across Hessian eigenspaces.The eigenvalue decomposition separates the analysis into independent recursions.Source: §3 · p. 5

3.1 Characteristic polynomial and eigenvalues

  • The stable parameter region is triangular in (αh_i, βh_i), and its interior gives linear convergence; both real and complex eigenvalues occur there.The stability region is summarized in Figure 1.Source: §3.1 · p. 6, Figure 1 · p. 6
  • In stable regimes, real-root errors decay at O(1/n^2) with potentially large constants, while complex-root errors oscillate at O(1/n^2), even for arbitrarily small h_i.Strict inequalities in the lemmas give linear convergence; the real-root bound's constant can be arbitrarily large.Source: §3.1 · pp. 6–7

3.2 Classical examples

  • Averaging loses linear convergence on strongly convex problems and heavy ball is not adaptive to strong convexity, whereas acceleration is adaptive through h_i-dependent contraction.Acceleration and heavy ball have oscillatory behavior.Source: §3.2 · p. 7

3.3 General bound

  • The general deterministic bound is eigenvalue-regime-independent and yields O(1/n^2) for some starting points, with unimprovable inverse dependence on αn^2 and (α + β)n.The αn^2 term recovers the traditional second-order rate for quadratic functions and is relevant only when α > 0.Source: §3.3 · p. 8
  • The objective gap is addressed, but iterate distance may remain bounded without tending to zero; averaged gradient descent gives O(1/n) without assumptions on initialization.This O(1/n) rate follows from the bound involving (α + β)n when α = 0.Source: §3.3 · p. 8

4 Quadratic Optimization with Additive Noise

For noisy quadratic optimization, the paper casts gradient updates as a stochastic linear dynamical system and derives convergence bounds for different step-size choices. The analysis distinguishes unstructured noise from structured least-squares noise, where it yields a bias–variance trade-off but does not cover standard least-squares SGD.

4.1 Stochastic difference equation

  • The noisy recursion assumes uncorrelated, zero-mean gradient noise with bounded covariance, and the paper expresses the excess-cost analysis as an initial-condition term plus a noise-dependent term.For quadratic functions, the reduced variable follows a second-order recursion with an additive noise term.Source: §4.1 · p. 9

4.2 Convergence result

  • The analysis separates initial-condition and noise contributions to expected excess cost, then bounds convergence for quadratic functions with arbitrarily small eigenvalues and finite-covariance uncorrelated noise.The authors conjecture that the bound’s scalings with the iteration horizon are tight, while noting it is an upper bound.Source: §4.1 · p. 9, §4.2 · p. 10
  • For unstructured noise, averaged gradient descent has a bounded but non-vanishing bound, while Nesterov’s step sizes suggest possible divergence.The paper reports observing the suggested divergence in experiments.Source: §4.2 · p. 10

4.3 Structured noise and least-square regression

  • For least-squares structured noise, the framework improves on more general bounds; varying α gives an explicit bias–variance trade-off, and optimized constants improve on averaged stochastic gradient descent.The proposed bound gives an O(1/N^2) bias term at the price of a potentially slightly worse variance constant; with optimal constants, the algorithm is reported to improve on averaged SGD in all situations.Source: §4.3 · pp. 10–11, §4.4 · p. 12
  • The least-squares analysis covers a semi-stochastic recursion, not standard SGD, because standard SGD’s gradient noise includes a term depending on θ.Applicability to regular SGD is conjectured, with experiments described as encouraging.Source: §4.3 · p. 11

4.4 Related work

  • The paper reports simultaneous attainment of known bias and variance lower bounds only under specified relative-size conditions; attaining both minimax terms in all situations remains open.For the least-squares setting, the stated condition is L∥θ0−θ*∥^2 ≤ dσ^2.Source: §4.4 · p. 12

5 Experiments

Synthetic experiments compare the proposed algorithm with stochastic accelerated methods under structured noise. The reported results favor the proposed method in bias-dominated settings and show similar behavior in least-squares regression.

Experimental setup

  • The synthetic setup uses a matrix with random eigenvectors and eigenvalues 1/k^m, and compares algorithms using their papers’ optimal step sizes with results averaged over 10 replications.The starting point is chosen at distance r = 1 from the optimum unless otherwise specified.Source: §5 · pp. 12–13

Homoscedastic noise

  • In the bias-dominated quadratic-noise setting, the proposed algorithm outperforms all compared methods; when variance dominates, it and Av-GD attain O(σ^2d/n), while other accelerated methods converge at O(1/√n).In the variance-dominated case, Acc-GD neither converges to the optimum nor diverges.Source: §5 · p. 13, Figure 3 · p. 13

Application to least-squares regression

  • For least-squares regression with regular stochastic gradients, the proposed algorithm shows the same reported behavior as under homoscedastic noise; the authors conjecture that their bounds also hold.The experiment uses normally distributed inputs, d = 20, and averages results over 10 replications.Source: §5 · p. 13, Figure 4 · p. 14

6 Conclusion

The paper unifies averaging and acceleration for non-strongly-convex quadratic functions, with and without noisy gradients. It identifies limitations in the current analysis and points to additional experiments in the appendix.

6 Conclusion

  • A joint framework for averaging and acceleration on non-strongly-convex quadratics supports algorithms combining faster forgetting of initial conditions with greater noise robustness when covariance is proportional to the Hessian.The first benefit is associated with acceleration and the second with averaging.Source: §6 · p. 14
  • The analysis is limited to quadratic functions; extension to smooth or self-concordant-like functions and to least-squares regression with natural heteroscedastic gradients remains future work.The latter extension is suggested by the simulations.Source: §6 · p. 14

A Additional experimental results

A.1 Deterministic convergence

The deterministic experiments show how convergence and oscillation vary with step sizes and eigenvalues; with additive noise, the compared algorithms have different precision and early-convergence behavior.

A.1 Deterministic convergence

  • With α = 1/10 in one dimension, the optimal β is the double-coalescent-eigenvalue setting; β above it gives real behavior, while β below it oscillates.HB and Acc-GD oscillate in the classical-algorithm comparison, and Acc-GD leverages strong convexity to converge faster.Source: §A.1 · p. 16, Figure 5 · p. 17
  • For mixed eigenvalues, high-eigenvalue components dominate initially and decay quickly, while small-eigenvalue components oscillate and converge more slowly.In the d = 2 example, Av-GD is O(1/n), while HB and Acc-GD initially oscillate at O(1/n^2); Acc-GD later becomes linear as nµ grows.Source: §A.1 · p. 16, Figure 6 · p. 17
  • For 20-dimensional quadratics, Av-GD converges at O(1/n), HB at O(1/n^2), and Acc-GD is linear for the left spectrum but O(1/n^2) for the right spectrum.Figure 7 compares spectra 1/k^2 and 1/k^8, respectively, for k = 1, . . . , 20.Source: Figure 7 · p. 17, §A.1 · pp. 17–18

A.2 Noisy convergence with unstructured additive noise

  • Under i.i.d. zero-mean noise with variance C = I, accelerated algorithms reach the same precision, while constant-step Av-GD does not converge and Acc-GD diverges.SAGE and AC-SA are faster initially because their step sizes decrease with n and depend on horizon N.Source: §A.2 · p. 18, Figure 8 · p. 18

B Proofs of Section 2

The proof recasts the iterative algorithms using polynomial relations and stationarity, then expresses averaged gradient descent as a two-step algorithm on its averaged iterate.

B.1 Proof of Theorem 1

  • The proof applies the stationarity property to vectors formed using the quadratic Hessian to derive polynomial relations for the iterates.It introduces n-independent polynomials through the n-scalability property.Source: §B.1 · pp. 18–19
  • The proof relates the polynomial representations through coefficient definitions and equations to obtain the stated n-scaled form.The supplied passage identifies the rescaling as P̄_n(X) = n/(n + 1)P(X).Source: §B.1 · pp. 19–20

B.2 Av-GD as two steps-algorithm

  • Av-GD with step-size γ can be represented as a two-step algorithm when its averaged iterate is treated as the main iterate.The update expresses θ_(n+1) through θ_n, θ_(n−1), and the gradient at nθ_n − (n−1)θ_(n−1).Source: §B.2 · p. 20

C.1 Proof of Lemma 1

The eigenvalue analysis separates real, complex, and coalescing cases, relating the parameter constraints to stability and convergence behavior.

C.1 Proof of Lemma 1

  • In the real-root case, the proof checks eigenvalue modulus constraints, including α ≥ 0, α + β ≥ 0, and upper bounds on β involving h_i and α.The stated bounds include β ≤ 2/h_i − α/2 and β ≤ 4/h_i − α.Source: §C.1 · pp. 21–22

C.2 Proof of Lemma 2

  • In the complex-root case, the eigenvalue magnitude satisfies |r_i|^2 = 1 − βh_i, with the eigenvalues parameterized using ρ_i and ω_i.Figure 10 plots the constraints for this case.Source: §C.2 · pp. 22–23, Figure 10 · p. 22

C.3 Coalescing eigenvalues

  • At coalescing eigenvalues, the recurrence has a double real eigenvalue and converges linearly when 0 < α < 4/h_i and h_i > 0.The proof also states a bound for α < 4/h_i to address behavior when h_i is small.Source: §C.3 · p. 23

D.1 Sketch of the proof

The proof sketch combines domain-specific iterate bounds with Lyapunov arguments to establish the theorem's bounds, then gives lower-bound constructions for quadratic functions.

D.3 Proof of Lemma 3

D.1 Sketch of the proof

  • The theorem's domain is covered by intersecting the domains of two lemmas for initial bounds and using a third lemma for its last two bounds.Figure 14 depicts the theorem's area and the included lemma domains.Source: §D.1 · pp. 24–25, Figure 14 · p. 24

D.5 Proof of Lemma 5

D.2 Outline of the proofs of the Lemmas

  • The proofs find a Lyapunov function G from R2 to R whose values decrease along the iterates; for readability, they suppress index i and take h_i = 1 without loss of generality.Source: §D.2 · p. 25

D.4 Proof of Lemma 4

  • Lemma 4 introduces a second Lyapunov function based on η_n, η_(n−1), r, and the discriminant Δ.The proof rewrites its recurrence using r^2 − Δ = 1 − β.Source: Figure 12 · p. 24, §D.4 · p. 26

E Lower bound

  • The lower-bound section constructs quadratic-function sequences showing that either of two terms can make the Corollary 1 bound tight.The constructions cover the conditions α_n + β_n = o(nα_n) and nα_n = o(α_n + β_n).Source: E Lower bound · p. 27

F.1 Proofs of Theorem 3 and Theorem 4

The proofs separate initial-condition bias from noise variance, use characteristic-root bounds to establish convergence results, and show that several stochastic accelerated algorithms share a common form.

F.1 Proofs of Theorem 3 and Theorem 4

  • Initial-condition bias and noise variance are bounded separately to establish Theorems 3 and 4 under step-size restrictions.A further restriction on β simplifies a bound used to prove Theorem 4.Source: §F.1 · p. 30

F.2 Proof of Corollary 3

  • The proof of Corollary 3 uses three regimes to select α and β according to ν relative to 1/L and N/L.The regimes are ν < 1/L, 1/L < ν < N/L, and ν > N/L.Source: §F.2 · p. 31

F.3.1 Proof outline

  • The Proposition 2 proof bounds an expected iterate norm using a characteristic-root expansion and auxiliary lemmas.Its stated step-size range is α ≤ 1/h_i and 0 ≤ β ≤ 2/h_i − α.Source: §F.3.1 · pp. 31–32

F.3.2 Some technical Lemmas

  • The technical lemmas expand the noise term using dynamical-system eigenvalues and establish nonnegativity in both real and complex root cases.The bounds apply for α ≤ 1/h_i and 0 ≤ β ≤ 2/h_i − α.Source: §F.3.2 · pp. 32, 33, 35

G.1 Summary

  • For quadratic objectives and suitable step sizes, AC-SA, SAGE, and Accelerated RDA share a common second-order form; Xiao’s cited result is broader, covering composite optimization and general gradient noise.Lan and Hu consider bounded cases, while Xiao treats the unbounded case.Source: §G.1 · p. 36

G.2 AC-SA

  • Lemma 9 reformulates AC-SA with its step sizes and gradient estimate in the common algorithmic form.The appendix introduces the algorithms as sharing the same form.Source: §G.1 · p. 36, §G.2 · p. 37

G.3 SAGE

  • Lemma 10 states an equivalent common-form representation for SAGE with its specified step sizes.The appendix presents SAGE alongside the other algorithms sharing the same form.Source: §G.1 · p. 36, §G.3 · p. 37

G.4 Accelerated RDA method

  • Lemma 11 states an equivalent common-form representation for Accelerated RDA with its specified step sizes.The stated updates include a fixed β_n = β.Source: §G.1 · p. 36, §G.4 · pp. 38–39

H Lower bound for stochastic optimization for least-squares

The section establishes a lower bound for quadratic optimization with noisy gradient access. It constructs a family of quadratic functions and derives a bound for methods using random gradients, including for N ≤ d.

H Lower bound for stochastic optimization for least-squares

  • The section derives a lower bound for optimizing quadratic functions with noisy gradient access, with a stated result for N ≤ d iterations.The argument applies to any method accessing a random gradient.Source: H Lower bound for stochastic… · pp. 39–40
  • The construction uses quadratic functions whose Hessian eigenvalues are 2c_i/d, with the largest eigenvalue set to L.The functions are indexed by sign vectors, and their minimizers and discrepancy are described in the passage.Source: H Lower bound for stochastic… · p. 40
  • Noisy gradients are formed by sampling independent Bernoulli variables and using the gradient of a random function.The passage also gives the variance of the random gradient.Source: H Lower bound for stochastic… · p. 40

Related papers

Loading 1504.01577v1…