PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence and Dynamical Behavior of the ADAM Algorithm for Non-Convex Stochastic Optimization

Anas Barakat, Pascal Bianchi

arXiv:1810.02263v4stat.MLcs.LGmath.CAmath.DSmath.OC

TL;DR

Although Adam is popular, few works have examined its theoretical behavior. This paper models Adam with a non-autonomous ODE and analyzes constant- and decreasing-stepsize variants. It establishes critical-point convergence results for the ODE and the iterates under stated conditions.

  • Problem

    Despite Adam's popularity, few works investigate its behavior from a theoretical point of view.

    Source: §1 · p. 1

  • Method

    The paper introduces a non-autonomous ODE for Adam and analyzes both the constant-stepsize algorithm and a decreasing-stepsize variant.

    Source: §1 · pp. 1–2

  • Results

    The interpolated constant-stepsize iterates converge in probability to the ODE as γ→0, and the decreasing-stepsize iterates converge almost surely to critical points under stated conditions.

    Source: §1 · p. 2, §5.2 · p. 8

  • Takeaways & Limitations

    Under a Łojasiewicz-type condition, the ODE solution converges to a single critical point, with convergence rates established.

    Source: §1 · p. 2

    The ODE solution may not exist for arbitrary initial moment values that are nonzero.

    Source: §3.2 · p. 5

Abstract

from arXiv · show

Adam is a popular variant of stochastic gradient descent for finding a local minimizer of a function. In the constant stepsize regime, assuming that the objective function is differentiable and non-convex, we establish the convergence in the long run of the iterates to a stationary point under a stability condition. The key ingredient is the introduction of a continuous-time version of Adam, under the form of a non-autonomous ordinary differential equation. This continuous-time system is a relevant approximation of the Adam iterates, in the sense that the interpolated Adam process converges weakly towards the solution to the ODE. The existence and the uniqueness of the solution are established. We further show the convergence of the solution towards the critical points of the objective function and quantify its convergence rate under a Lojasiewicz assumption. Then, we introduce a novel decreasing stepsize version of Adam. Under mild assumptions, it is shown that the iterates are almost surely bounded and converge almost surely to critical points of the objective function. Finally, we analyze the fluctuations of the algorithm by means of a conditional central limit theorem.

1. Introduction.

Adam combines inertial updates with coordinate-wise learning rates based on past squared gradients, and bias correction is especially useful early. The paper analyzes Adam through a dynamical-systems framework spanning continuous time and discrete-time algorithms.

1. Introduction.

  • Adam adjusts learning rates coordinate-wise using past squared gradients and includes bias correction, which is especially useful during early iterations.The method combines adaptive per-coordinate learning rates with inertial updates.Source: §1 · p. 1
  • The paper introduces a non-autonomous ODE for Adam and establishes a unique global solution, convergence toward critical points, and rates under a Łojasiewicz-type condition.The ODE also suggests that near the origin the objective is non-increasing along the trajectory.Source: §1 · pp. 1–2
  • As the constant stepsize tends to zero, the interpolated Adam process converges in probability to the ODE solution; under a stability condition, the iterates approach critical points in a doubly asymptotic regime.The limits are n→∞ followed by γ→0.Source: §1 · p. 2
  • The paper proposes a decreasing-stepsize Adam variant with sufficient conditions for stability and almost-sure convergence to critical points.It also establishes a conditional central limit theorem for the stochastic iterates.Source: §1 · p. 2

2. The Adam Algorithm.

The section specifies Adam's state updates and assumptions, then defines a small-stepsize regime in which an interpolated process is compared with a continuous-time ODE.

2.1. Algorithm and Assumptions.

  • Adam updates first- and second-moment estimates from stochastic gradients, then debiases them; the debiased first-moment estimate is a convex combination of past gradients.The state is z_n=(x_n,m_n,v_n), and the debiasing step makes the updates non-homogeneous in n.Source: §2.1 · p. 3
  • The assumptions make F continuously differentiable with locally Lipschitz gradients, require F to be coercive and S(x)>0, and exclude points where the sample gradient is almost surely zero.Here S is the expected squared-gradient map described in the section.Source: §2.1 · pp. 3–4

2.2. Asymptotic Regime.

  • As γ→0, the piecewise-linear interpolation of Adam's iterates converges in probability to a continuous-time ODE when α and β tend to one with rates a,b satisfying b≤4a.The interpolation is defined over successive intervals [nγ,(n+1)γ).Source: §2.2 · p. 4

3. Continuous-Time System.

The paper models Adam in continuous time with a non-autonomous ODE and establishes properties of its solution. The trajectory approaches critical points, and under a Łojasiewicz condition it converges to a single critical point at a quantified rate.

3.1. Ordinary Differential Equation.

  • As γ decreases, the interpolated Adam process is approximated by a non-autonomous ODE whose drift is the limit of the discrete-time drift.The ODE is ˙z(t) = h(t, z(t)).Source: §3.1 · p. 5

3.2. Existence, Uniqueness, Convergence.

  • The ODE has a unique bounded global solution from (x0, 0, 0), although existence is not guaranteed for arbitrary nonzero initial m0 and v0.The vector field is discontinuous at t = 0 and is not locally Lipschitz in z, so standard existence and uniqueness results do not directly apply.Source: §3.2 · p. 5
  • The trajectory approaches the critical-point set S, with m(t) tending to zero and S(x(t)) − v(t) tending to zero.This result assumes F(S) has empty interior.Source: §3.2 · p. 5
  • For all t ≥ 0, F(x(t)) ≤ F(x0), a consequence of Adam’s bias-correction steps.Without debiasing, early iterations could degrade the initial estimate; when ε and the gradient variance at x0 are small, the initial derivative is approximately −∇F(x0)/|∇F(x0)|.Source: §3.2 · pp. 5–6

3.3. Convergence rates.

  • Under the Łojasiewicz property, the trajectory converges to a single critical point, with its convergence rate depending on the exponent at that point.The property holds for real-analytic and semialgebraic functions.Source: §3.3 · p. 6

4. Discrete-Time System: Convergence of Adam.

For constant stepsize, the paper relates interpolated Adam processes to the continuous-time ODE as the stepsize decreases. It also distinguishes this approximation result from long-run almost-sure convergence, which constant stepsize does not provide.

4. Discrete-Time System: Convergence of Adam.

  • The interpolated processes indexed by n and 0 < γ < ¯γ0 are bounded in probability.The stated stability assumption ensures the iterates do not explode in the long run.Source: §4 · p. 7
  • With fixed γ, the iterates cannot converge almost surely as n → ∞; convergence is only stated in the doubly asymptotic regime n → ∞ then γ → 0.A sufficient stability condition is sup_n,γ E∥zγ_n∥ < ∞, while the paper notes that verifying it can be difficult.Source: §4 · p. 7
  • As γ ↓ 0, the family of interpolated Adam processes converges in probability to the unique ODE solution from (x0, 0, 0).The result assumes iid samples and a moment condition on the stochastic gradients.Source: §4 · pp. 6–7

5. A Decreasing Stepsize Adam Algorithm.

The paper introduces a decreasing-stepsize Adam variant to obtain almost-sure convergence. Under stated conditions it is almost surely bounded and approaches critical points; near a limit, its rescaled iterates also have a conditional Gaussian limit.

5.1. Algorithm.

  • Decreasing stepsizes address the lack of almost-sure convergence with constant stepsizes by making Adam’s hyperparameters iteration-dependent and changing its debiasing rescaling.The rescaled moment estimates are intended to be convex combinations of past gradients and squared gradients.Source: §5.1 · pp. 7–8

5.2. Almost sure convergence.

  • Under the theorem’s assumptions, if the decreasing-stepsize iterates are almost surely bounded, then x_n approaches the critical-point set almost surely; if that set is finite or countable, the iterates converge to one of its points.The theorem also states that m_n tends to zero and v_n−S(x_n) tends to zero.Source: §5.2 · p. 8
  • A separate theorem gives almost-sure boundedness of the iterates under its stated assumptions, providing the sufficient condition used alongside the convergence result.Source: §5.2 · p. 8

5.3. Central Limit Theorem.

  • Conditioned on convergence to a limit point, the rescaled full iterate converges in distribution to a zero-mean Gaussian with covariance solving a Lyapunov equation; the x-coordinate has covariance Σ1.The stated step-size schedule is γ_n=γ_0/(n+1)^κ for κ∈(0,1], with γ_0>1 additionally required when κ=1.Source: §5.3 · p. 9
  • The limiting covariance Σ1 depends on v_n through its limit S(x*), but not on fluctuations of v_n or parameter b; for large a, it approaches the covariance associated with the no-inertia update.The no-inertia covariance is interpreted as the asymptotic covariance for RMSProp.Source: §5.3 · p. 10

6. Related Works.

Prior analyses of Adam offer limited or conditional convergence guarantees, and the paper distinguishes its original-Adam analysis from contemporaneous continuous-time work. Its focus includes the irregular vector field and discrete-time convergence.

6. Related Works.

  • Adam is less theoretically studied than AdaGrad; the initial paper’s O(1/T) average-regret claim for convex objectives was contradicted by a counterexample.The counterexample implies that Adam’s average regret does not converge to zero; AmsGrad was proposed to recover guarantees in the convex case.Source: §6 · p. 10
  • Other analyses cover noiseless Adam [4], variance-adapted sign descent, or convergence results for Adam and related methods that require specific or hard-to-verify conditions.The paper also notes that the RmsProp Lyapunov approach in does not generalize readily to Adam, which uses debiased estimates.Source: §6 · pp. 10–11
  • Da Silva and Gazeau [10] study a similar continuous-time system but modify Adam for a locally Lipschitz vector field; this paper treats the original algorithm’s irregular field and discrete-time convergence.The cited work leaves discrete-time iterate convergence open.Source: §6 · p. 11

7. Proofs of Section 3.

The proofs in this section are not restricted to the paper’s particular definitions of F and S; they apply to mappings satisfying the stated hypotheses.

7. Proofs of Section 3.

  • The section’s results are stated for general mappings F and S, rather than only those defined in Eq. (2.2).Source: §7.1 · p. 11
  • The proof scope is determined by whether the mappings F and S satisfy the hypotheses required for the results.Source: §7.1 · p. 11
  • The specific definitions in Eq. (2.2) are an instance of the broader mapping-based proof setup, not a restriction on it.Source: §7.1 · p. 11

7.1. Preliminaries.

The preliminaries set assumptions for F and S, then relate a shifted ODE to the original system and its autonomous limit. A strict Lyapunov function supports convergence of the limiting dynamics and the original trajectory.

7.1. Preliminaries.

  • The framework assumes F is continuously differentiable with locally Lipschitz gradient, while S maps into the nonnegative orthant and is locally Lipschitz.Source: §7.1 · p. 11
  • The proof studies time-shifted equations (ODEη) and obtains a solution to the original ODE as a cluster point as η decreases to zero.Equicontinuity and the Arzelà–Ascoli theorem supply the cluster point.Source: §7.1 · p. 11
  • The autonomous limiting ODE has a strict Lyapunov function, and the original ODE solution is an asymptotic pseudotrajectory of that system, yielding convergence to its equilibria.Source: §7.1 · p. 12
  • Solutions from the specified initial condition have initial derivatives for m, v, and x determined by the objective gradient and S(x_0).In particular, the text gives ṁ(0)=a∇F(x_0), v̇(0)=bS(x_0), and ẋ(0)=−∇F(x_0).Source: §7.1 · p. 12
  • For 0<b≤4a, the limiting Lyapunov function has a nonpositive directional derivative along the limiting dynamics.Source: §7.1 · pp. 12–13

7.2. Proof of Th. 3.1.

Under the stated assumptions and 0 < b ≤ 4a, the proof establishes boundedness, existence, and uniqueness of the global continuous-time Adam solution from the prescribed initial condition. The trajectory also does not increase the objective.

7.2.1. Boundedness.

  • Under Assumptions 2.3, 2.4, 7.1, and 7.2 with 0 < b ≤ 4a, Proposition 7.6 bounds the stated trajectories in a compact subset of Z+; for z0=(x0,0,0), F(x(t))≤F(x0).The proof also places {xη(t): t∈[0,T)} in {F≤F(x0)}, which Assumption 2.3 says is bounded.Source: §7.2.1 · pp. 13–14

7.2.2. Existence.

  • For every prescribed initial point, (ODE) admits a global solution under the stated assumptions and 0 < b ≤ 4a.Source: §7.2.2 · p. 15

7.2.3. Uniqueness.

  • That global solution to (ODE) is unique for the prescribed initial condition.Source: §7.2.3 · p. 16
  • Under the same assumptions, (ODE∞) has a unique global solution from every point and defines a semiflow.Source: §7.2.3 · p. 17

7.3. Proof of Th. 3.2.

The proof constructs a strict Lyapunov function for the autonomous semiflow and shows that the non-autonomous ODE solution is its asymptotic pseudotrajectory. Consequently, the semiflow and ODE trajectory approach their respective equilibrium sets.

7.3.1. Convergence of the semiflow.

  • A strict Lyapunov function on the compact invariant set yields convergence of the semiflow toward its equilibrium set.The equilibria are the points with ∇F(x) = 0, m = 0, and v = S(x).Source: §7.3.1 · pp. 18–19

7.3.2. Asymptotic Behavior of the Solution to (ODE).

  • The solution to (ODE) is an asymptotic pseudotrajectory of the autonomous semiflow.The proof establishes this by showing that finite-horizon trajectory discrepancies vanish as time tends to infinity.Source: §7.3.2 · p. 19
  • The ODE trajectory approaches the equilibrium set of the autonomous system as time tends to infinity.Source: §7.3.2 · p. 20

7.4. Proof of Th. 3.4.

The proof uses a modified Lyapunov function and a Łojasiewicz condition to establish convergence of the ODE's parameter trajectory and quantify its rate. The exponent can be localized at the limiting critical point.

7.4. Proof of Th. 3.4.

  • The modified Lyapunov function is shown to be positive and non-increasing, with its derivative bounded above by a negative power of its value.The argument combines the drift inequality with the Łojasiewicz condition.Source: §7.4 · pp. 20–21
  • The Łojasiewicz condition on the compact connected limit set supplies a gradient lower bound near that set.This bound is used to derive the rate estimate for convergence of x(t).Source: §7.4 · pp. 20–21
  • The trajectory x(t) converges to a limit x*, with a rate quantified using the Łojasiewicz exponent.The global exponent may be replaced by an exponent for F at x*.Source: §7.4 · p. 21

8. Proofs of Section 4.

The proofs establish convergence of interpolated constant-stepsize processes to the continuous-time ODE and connect the associated Markov-chain dynamics to the semiflow's equilibria. Tightness and moment bounds support these arguments.

8.1. Proof of Th. 4.3.

  • A uniform integrability bound on stopped increments supports tightness of the interpolated processes.Source: §8.1 · p. 22
  • The stopped interpolated processes are tight, and as the stepsize tends to zero they converge in probability to the ODE solution.The proof establishes tightness using uniform integrability and identifies the limit through consistency of the discrete and continuous dynamics.Source: §8.1 · pp. 22–23

8.2. Proof of Th. 4.5.

  • For the Markov-chain argument, the Birkhoff center of the limiting semiflow equals its equilibrium set.Source: §8.2 · p. 25

9. Proofs of Section 5.

The proofs control the bias-correction and moment sequences, then verify the stochastic-approximation and fluctuation conditions used for Section 5’s results.

9. Proofs of Section 5.

  • Under the stated assumptions, r_n = 1 − ∏_{i=1}^n α_i is nondecreasing and converges to 1.The proof derives the identity by iterating the recursion for r_n.Source: §9 · p. 25

9.1. Proof of Th. 5.2.

  • The proof of Th. 5.2 shows that the remainder terms vanish and the martingale increments converge, making the interpolated process a bounded APT almost surely.It then applies Propositions 7.14 and 7.15.Source: §9.1 · pp. 25–26

9.2. Proof of Prop. 5.4.

  • For Prop. 5.4, convergence of the Lyapunov sequence and coercivity of F yield almost-sure boundedness of x_n; the proof also bounds m_n and v_n.The moment-sequence bounds use the Robbins–Siegmund theorem and the stated assumptions.Source: §9.2 · p. 27

9.3. Proof of Th. 5.7.

  • For Th. 5.7, the proof adapts the fluctuation argument because Q is not positive definite, replacing the inverse square root of Q with its Moore–Penrose inverse.The proof verifies the cited theorem’s assumptions apart from positive definiteness of the limiting covariance matrix.Source: §9.3 · pp. 27, 29
Loading 1810.02263v4…