PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

Xiaoyu Li, Francesco Orabona

arXiv:1805.08114v3stat.MLcs.LGmath.OC

TL;DR

Adaptive SGD lacks a satisfactory convergence theory in the non-convex setting, despite the widespread use of adaptive stepsizes. The paper analyzes generalized AdaGrad stepsizes while excluding the current noisy gradient from the stepsize, and proves almost sure convergence plus noise-adaptive rates in convex and non-convex settings. These results aim to narrow the gap between theory and practice for adaptive optimization algorithms.

  • Problem

    Adaptive stepsizes are widely used, but conditions for generalized AdaGrad convergence and improvement over decreasing-stepsize SGD remain unclear, especially in non-convex optimization.

  • Method

    The paper theoretically analyzes generalized global and coordinate-wise AdaGrad stepsizes, with the stepsize based on past rather than the current stochastic gradient.

  • Results

    The analysis proves almost sure gradient convergence in non-convex settings and noise-adaptive finite-time rates in convex and non-convex settings, interpolating between GD and SGD rates in the convex case.

  • Takeaways & Limitations

    The results provide a possible explanation for the empirical success of adaptive optimization algorithms and help close the gap between theory and practice.

  • Takeaways & Limitations

    The analysis implies high-probability bounds that depend polynomially on 1

Abstract

from arXiv · show

Stochastic gradient descent is the method of choice for large scale optimization of machine learning objective functions. Yet, its performance is greatly variable and heavily depends on the choice of the stepsizes. This has motivated a large body of research on adaptive stepsizes. However, there is currently a gap in our theoretical understanding of these methods, especially in the non-convex setting. In this paper, we start closing this gap: we theoretically analyze in the convex and non-convex settings a generalized version of the AdaGrad stepsizes. We show sufficient conditions for these stepsizes to achieve almost sure asymptotic convergence of the gradients to zero, proving the first guarantee for generalized AdaGrad stepsizes in the non-convex setting. Moreover, we show that these stepsizes allow to automatically adapt to the level of noise of the stochastic gradients in both the convex and non-convex settings, interpolating between $O(1/T)$ and $O(1/\sqrt{T})$, up to logarithmic terms.

1 INTRODUCTION

The paper studies generalized AdaGrad stepsizes to address missing convergence theory for adaptive SGD, especially in non-convex optimization. It establishes almost sure convergence and noise-adaptive rates in convex and non-convex settings.

  • Motivation: Adaptive stepsizes depend on past stochastic gradients, but their improved non-convex performance lacks a theoretical explanation.Many variants lack convergence guarantees or can fail even on simple one-dimensional convex stochastic problems.
  • Approach: The paper analyzes global and coordinate-wise generalized AdaGrad stepsizes with parameters α > 0 and β, ǫ ≥ 0.Setting ǫ = 0 recovers the coordinate-wise AdaGrad stepsizes, while the additional parameter controls stepsize decrease.
  • Results: The authors prove, for the first time in the non-convex setting, almost sure convergence of SGD gradients to zero with global and coordinate-wise adaptive stepsizes.This result concerns an infinite number of iterations under sufficient conditions.
  • Results: In the convex setting, generalized global AdaGrad stepsizes adapt to noise and interpolate between GD and SGD convergence rates, up to polylogarithmic terms.The analysis removes strong assumptions used in previous analyses.
  • Results: In the non-convex setting, the generalized global stepsizes provide a finite-time noise-adaptive rate, with lower noise yielding faster convergence.The paper presents these as the first theoretical results showing an advantage over plain SGD in this setting.

2 RELATED WORK

Prior work established adaptive methods mainly under convex or restrictive assumptions, while non-convex adaptive-step analyses remained limited. This paper positions its results as addressing that gap.

  • Convex adaptive methods: Convex adaptive-gradient studies often assume optimization over a bounded convex set, an assumption that may be false in applications.Earlier analyses include convergence and sparsity advantages under constrained settings.
  • Non-convex SGD: Non-convex SGD convergence has been studied through random-iterate results and additional regularity or directional assumptions.Alternative conditions can require updates to move toward the origin or gradients never to oppose the global optimum.
  • Non-convex adaptive methods: Early non-convex adaptive-step studies required function values, strict gradient-direction conditions, deterministic gradients, bounded expected squared gradients, or extreme sparsity.These restrictions limited the scope of their guarantees.
  • Positioning: The paper claims a less restrictive non-convex analysis, assuming smoothness and Lipschitz continuity in its most restrictive asymptotic case.This contrasts with a prior condition requiring gradients never to point opposite the global optimum.

3 PROBLEM SET-UP

The setup minimizes a lower-bounded function using a stochastic first-order oracle and generalized assumptions on smoothness, Lipschitz continuity, unbiasedness, and noise.

  • Notation: Conditional expectations are taken with respect to the history of stochastic variables ξ1 through ξt−1.The notation distinguishes full expectation from expectation conditioned on the past.
  • Objective: The optimization problem is minimizing f(x) over R^d, where f is bounded from below.The paper uses different objective assumptions depending on the analysis setting.
  • Objective assumptions: The baseline assumption is that f is M-smooth, with L-Lipschitz continuity imposed in some analyses.The Lipschitz condition is |f(x) − f(y)| ≤ L∥x − y∥ for all x,y ∈ R^d.
  • Oracle: A stochastic first-order oracle returns g(x, ξ), a noisy gradient estimate whose expectation equals the gradient of f.The stochastic variable ξ supplies the oracle noise.
  • Noise assumptions: The analysis alternatively imposes assumptions controlling the variance or higher-moment behavior of stochastic-gradient noise.One condition controls the expectation of the maximum noise term and implies bounded variance by Jensen’s inequality.

4 KEEPING THE UPDATE DIRECTION UNBIASED

The proposed stepsizes exclude the current noisy gradient from the stepsize computation, preserving an unbiased update direction. The paper shows that including it can reverse the expected direction.

  • Unbiasedness: Unlike standard AdaGrad, the generalized stepsizes do not use g(xt, ξt) when computing ηt.Using the current noisy gradient would introduce a spurious bias in the update direction.
  • Unbiasedness: There exist convex smooth examples where including the current noisy gradient makes the expected update inner product with the true gradient negative.The example satisfies the stated additive-noise condition and yields Eξt[⟨ηt+1g(xt, ξt), ∇f(xt)⟩] < 0.
  • Interpretation: The resulting expected direction can deviate by more than 90 degrees from the correct direction, with potentially serious consequences in unconstrained non-convex settings.The paper notes that recovery may occur in convex bounded problems but is less reassuring in broader settings.
  • Analysis trade-off: Excluding the current gradient makes bounding the cumulative squared stochastic-gradient norms more involved.Earlier analyses addressed this using knowledge of the function’s Lipschitz constant, whereas this paper avoids requiring that knowledge for the asymptotic guarantee.
  • Consequences: The paper uses these stepsizes to establish adaptive guarantees in both convex and non-convex settings.Later results include finite-time rates and adaptation to the stochastic-gradient noise level.

5 ALMOST SURE CONVERGENCE FOR NON-CONVEX FUNCTIONS

The paper establishes almost sure convergence of generalized AdaGrad SGD gradients to zero in the non-convex setting under sufficient assumptions. The analysis addresses adaptive stepsizes that may violate classical stochastic-approximation conditions and provides the first such guarantee for these generalized stepsizes.

  • With probability 1, generalized AdaGrad SGD decreases the gradients to zero in the non-convex setting.The result applies to both global and coordinate-wise adaptive stepsizes.
  • The generalized AdaGrad stepsizes need not satisfy the classical decreasing-stepsize conditions, even in expectation.The stochastic gradients may decrease quickly enough to make the relevant series converge.
  • The analysis assumes a Lipschitz function, bounded gradient noise, and conditions ensuring that the sum of the stepsizes diverges.These assumptions are used to establish the required divergence of the stepsize sum.
  • The results are presented as the first almost sure convergence guarantees for generalized AdaGrad stepsizes with ǫ > 0.Theorem 2 additionally supports selecting the last iterate rather than the minimum-gradient iterate over time.
  • The convergence guarantees are asymptotic, while finite-time expected rates and noise adaptation are treated in the subsequent section.The paper distinguishes probability-one asymptotic convergence from the later finite-time analysis.

6 ADAPTIVE CONVERGENCE RATES

Generalized AdaGrad stepsizes adapt convergence to stochastic-gradient noise in both convex and non-convex settings, without requiring prior knowledge of the noise variance. The convex result interpolates between gradient-descent and stochastic-gradient rates, while the non-convex result controls convergence of gradients to zero.

  • Convex setting: Adaptive rates hold independently of the noise variance: convergence is faster for small noise and worst-case optimal for large noise.The paper emphasizes a broad parameter range for α, β, and ǫ.
  • Convex setting: The convex analysis uses global generalized AdaGrad stepsizes without projections onto bounded domains or knowledge of the noise variance.This setting is intended to mirror many machine-learning optimization applications.
  • Convex setting: Up to polylogarithmic terms, the convex rate recovers O(1/T) when σ = 0 and O(1/√T) otherwise.The latter is identified as the worst-case optimal stochastic-gradient rate.
  • Non-convex setting: The non-convex theorem proves a noise-adaptive convergence rate for gradients, rather than for the suboptimality gap.The distinction follows from not assuming convexity.
  • Non-convex setting: For non-convex functions, the guarantee concerns the best iterate over T iterations because SGD is not generally a descent method.A random stopping time is equivalent in expectation, but the theorem is stated for the best iterate.
  • Non-convex setting: The generalized AdaGrad stepsizes automatically reproduce the deterministic-versus-stochastic stepsize behavior without estimating the noise variance.The paper presents this as an advantage over plain SGD.

7 DISCUSSION AND FUTURE WORK

The paper analyzes generalized AdaGrad stepsizes in convex and non-convex settings, establishing adaptive convergence results and almost sure convergence in the non-convex case. It identifies probability-dependence and bounded-support noise as limitations for future work.

  • The analysis establishes adaptive convergence rates for generalized AdaGrad stepsizes in both convex and non-convex settings.
  • In the non-convex setting, the paper proves almost sure convergence and gives the first sufficient convergence condition for a minor AdaGrad variation.
  • The adaptive rates provide a possible explanation for the empirical success of these algorithms in practical machine learning applications.
  • The current high-probability bounds depend polynomially on 1/δ because they use Markov’s inequality.
  • Almost sure convergence requires bounded-support noise, a condition the authors consider theoretically unsatisfying and hope to weaken.

A Appendix

The appendix reports proofs omitted from the main text.

  • The appendix contains proofs that were omitted from the main text.

A.1 Details of Example 1

This appendix section specifies a one-dimensional stochastic-gradient example and notes a parameter choice for which its expression can be negative.

  • The example uses gradient ∇f(x_t) = x_t and stochastic gradient g_t = ∇f(x_t) + ξ_t.
  • For x_t = 1, σ_t = 10, A = 10, and ϵ = 0 or ϵ = 0.1, the expression can be negative.

A.2 Proof of Lemma 2

The proof of Lemma 2 follows immediately from Lemma 9 after summing the resulting bound over the relevant indices.

  • Lemma 9 assumes nonnegative a_i and a nonincreasing function f on [0, +∞).
  • Summing over i = 1, ···, T yields the stated bound.
  • The proof of Lemma 2 is immediate from Lemma 9.

A.3 Proofs of Section 6.1

The appendix proves auxiliary lemmas and convergence results through inequalities, smoothness and Lipschitz assumptions, conditional expectations, and subsequence arguments. The final contradiction establishes that b_t converges to zero.

  • Assumptions and bounds: The analysis assumes Lipschitzness, smoothness, bounded gradient-noise support, and a stated noise condition.These assumptions are used to derive bounds before applying Lemma 1.
  • Auxiliary lemmas: The proofs combine inequalities from earlier lemmas with Jensen’s inequality and bounds involving logarithmic terms to establish the stated auxiliary bounds.The argument explicitly invokes Lemmas 2 and 10, Jensen’s inequality, and inequality (12).
  • Expectation argument: Conditional expectations and the law of total expectation are used before summing over t and lower bounding f(x_T+1) by f⋆.This yields the theorem’s stated bound.
  • Convergence argument: The subsequence contradiction shows that b_t cannot remain bounded below along one subsequence while approaching zero along another, so b_t goes to zero.The proof constructs interleaved subsequences and derives a contradiction with lim_t→∞ φ_t = 0.
Loading 1805.08114v3…