Adam Can Converge Without Any Modification On Update Rules

1 Introduction

• Fixing the problem before tuning (β1, β2) matches practice, whereas Reddi et al. (2018) select hyperparameters before constructing problems that can diverge.The authors identify this order of selection as a mismatch between theory and practice.Source: §1 · p. 2
• When β2 is large, Adam has small optimization error for almost all β1 values; when both are small, error rises, reaching 70 times higher on function (2).The experiments also report 1.4-times higher error in the red region on MNIST and CIFAR-10.Source: §1 · p. 2, Figure 1 · p. 2
• For fixed n, sufficiently large β2 and β1 < √β2 yield convergence to a neighborhood of critical points, whose size is proportional to stochastic-gradient variance.Under the strong growth condition, Adam converges to critical points; increasing β2 lets the result cover any β1 in [0, 1), including 0.9.Source: §1 · p. 3
• For fixed n, some small-β2 settings make Adam diverge to infinity; the size of this region increases with n.The divergence and convergence results use the same fixed-function-class setting, indicating a phase transition as β2 changes.Source: §1 · p. 3
• The authors recommend tuning β2 upward and trying β1 < √β2 when Adam performs poorly.Their convergence and divergence regions depend on the problem, unlike the problem-independent worst-case choice discussed for Reddi et al. (2018).Source: §1 · p. 3
• The convergence analysis covers unbounded gradients and unbounded second-order momentum, including any β1 in [0, 1).The authors describe a new proof method for unbounded momentum in stochastic nonlinear dynamics.Source: §1 · p. 3

2.1 Review of Adam

• Randomly shuffled Adam updates first- and second-order momenta from sampled component gradients, then uses them to update the optimization variable.The momenta are weighted by β1 and β2, respectively; the analysis uses a special initialization that replaces bias correction.Source: §2.1 · pp. 3–4
• The analysis assumes smooth component functions and a lower-bounded objective, with a flexible variance condition that includes the strong growth condition when D0 = 0.When D0 > 0, the cited discussion describes convergence to a bounded region rather than exact critical points.Source: §2.1 · p. 4

2.2 Related Works

• Prior analyses of vanilla Adam impose extra conditions or restrict the setting, while RMSProp results do not capture the joint effects of β1 and β2.The paper identifies unbounded momentum, its interaction with the adaptive stepsize, and statistical dependence between them as analysis challenges.Source: §2.2 · pp. 4–5

2.3 The Importance and Difficulties of Removing Bounded Gradient Assumptions

• Removing bounded-gradient assumptions matters because they rule out gradient divergence in advance, while Adam’s momentum and adaptive stepsize are coupled and random.The paper proposes techniques for handling Adam’s momentum at large β1 regardless of gradient magnitude.Source: §2.3 · p. 5

3.1 Convergence Results

• When β2 is sufficiently large and β1 < √β2, Adam converges to a neighborhood of critical points whose size depends on stochastic-gradient variance.The threshold γ1(n) is sufficient, and the paper notes a possible gap between this theoretical bound and practical β2 choices.Source: §3.1 · p. 6
• As β2 increases, the convergence result covers β1 values throughout [0, 1), including the common setting β1 = 0.9.For β2 = 0.999, the stated threshold is β1 < 0.9995; the result does not require bounded gradients.Source: §3.1 · p. 6
• Under the strong growth condition, Adam converges to critical points, with a rate comparable to SGD under the same condition.The paper reports zero gradient norm after convergence on function (2), which satisfies the condition.Source: §3.1 · p. 6

3.2 Divergence Results

• For small β2, a wide range of β1 can produce divergence; the paper’s counterexample is a lower-bounded convex smooth function that permits iterates and gradients to diverge.The theoretical result states that iterates and function values diverge under analytic conditions on β1 and β2.Source: §3.2 · p. 7
• The divergence region depends on n and expands as n increases, while the convergence and divergence results use the same fixed-function-class setting.For n = 20, Figure 2 plots the region where Adam diverges; the blue curve satisfies β1 = √β2.Source: §3.2 · p. 7, Figure 2 · p. 7

Case I

• When the function class changes with each hyperparameter pair, Adam’s iterates and function values can diverge for any (β1, β2) in [0, 1)^2.The divergence construction uses a different n for different pairs, so the function class is constantly changing.Source: §4 · p. 8

Case II

• For a fixed function class, Adam converges when β2 is large and β1 < √β2, while some hyperparameter pairs in the orange region admit divergence to infinity.The authors describe this setting as closer to practical applications and as potentially useful for hyperparameter tuning.Source: §4 · p. 8
• In Case II, some parameter regions remain unclassified, leaving Adam’s behavior unknown there.The paper lists these regions as future work.Source: §4 · p. 8

Issue I

• The analysis must handle massive momentum, since historical signals in m can distort the trajectory from the gradient direction when β1 is large.Prior approaches cited in the passage set β1 approximately to zero, unlike the large-momentum cases studied here.Source: §5 · pp. 8–9

Issue II

• The normalized gradient component is random and statistically dependent, so its expectation cannot be handled separately from the associated stochastic dynamics.This dependence makes direct analysis of the update direction difficult.Source: §5 · p. 9

Proof approach

• The proposed proof approach does not require bounded gradient magnitude, and its key lemma holds regardless of gradient norm.The authors note that a naive bounded-gradient estimate δ(β1) = O(G) does not show that δ(β1) is close to zero.Source: §5 · p. 9

Solution to Issue I

• Errors from successive epochs can cancel, keeping momentum roughly in the descent direction even for any β1 ∈ [0, 1).The paper presents this property as a key feature of its proof for Algorithm 1.Source: §5 · p. 9

Solution to Issue II

• Large β2 shrinks changes in √v, making the normalized gradient component behave asymptotically like the epoch error term for sufficiently large gradient components.Lemma 5.2 applies under Assumptions 2.1 and 2.2 when β1 < √β2; small gradient components are handled separately as a bounded-gradient case.Source: §5 · pp. 8–9

Convergence to bounded region when D0 > 0

• With D0 > 0, large-β2 Adam converges to a bounded region rather than an exact critical point, and the region shrinks as β2 increases.Even with a diminishing stepsize, the effective stepsize ηk/√vk,i may not decay.Source: §6 · p. 10, Figure 4 · p. 10

Convergence to critical points when D0 = 0

• When D0 = 0, Adam converges to critical points for large β2 and β1 < √β2 in experiments with n = 20.The experiments also used n = 5, 10, and 15, with those results reported in the appendix.Source: §6 · p. 10, Figure 4 · p. 10

Gradient norm of iterates can be unbounded when β2 is small

• With small β2 on function (2), gradient norms of Adam iterates increase dramatically and can become unbounded.The experiment used initialization x = −5 and n = 20.Source: §6 · p. 10, Figure 4 · p. 10

Real-data experiments

• MNIST, CIFAR-10, and Transformer XL training on WikiText-103 show results matching the reported large- and small-β2 performance patterns.On MNIST and CIFAR-10, the transition from low to higher loss has a convex-shaped boundary that roughly matches the condition in Theorem 3.1.Source: §6 · p. 10, Figure 4 · p. 10

Conclusions

• For large β2, Adam can converge when β1 < √β2.The conclusion presents this as a result on Adam’s convergence without modifying its update rules.Source: §7 · p. 10
• For small β2, Adam might diverge to infinity for a wide range of β1.Source: §7 · p. 10

Future work

• Proving faster convergence of Adam than SGD is left for future work.The paper states that its focus is the fundamental issue of convergence.Source: §7 · p. 10

• The checklist marks the abstract and introduction claims as scope-accurate and reports that limitations, societal impacts, and ethics guidelines are addressed.Source: Checklist · p. 13
• The authors report stating the full assumptions for theoretical results and including complete proofs.Source: Checklist · p. 13
• The checklist reports that code, data, and reproduction instructions, error bars, compute totals, and resource types were not provided.Source: Checklist · p. 13
• Existing asset creators are cited, but licenses are not mentioned; no new assets are reported, and human-subject items are marked not applicable.Source: Checklist · pp. 13–14

Negative Social Impact

• The script may guide neural-network training, with a stated potential negative impact if neural networks are deployed for illegal use.Source: Negative Social Impact · p. 15

Appendix Organization

• The appendices provide color-ball proof models, supporting experiments and tuning suggestions, related-work discussion, and detailed proofs and technical lemmas.Source: Appendix Organization · p. 15

• For Issue I, the proof seeks to show that δ(β1) vanishes with k, using conditional expectations and cancellation across epochs.The toy-model calculation enumerates two possible realizations and reduces the repeated calculation to its highest-order term.Source: A Introduction to the “Color-Ball”… · pp. 15–17
• The first color-ball model samples two labeled balls without replacement each epoch, then replaces them, defining random quantities that mimic momentum and stochastic gradients.The two quantities share the same sample order within each epoch.Source: A Introduction to the “Color-Ball”… · pp. 15–16
• Lemma A.1 offers a proof idea for Equation (7), but its idealized setting differs from Adam because the iterates evolve while the toy model's balls remain fixed.The analysis also abstracts vector iterates as scalar labels, requiring further technical lemmas to bridge the gap.Source: A Introduction to the “Color-Ball”… · pp. 16–17
• For Issue II, the second color-ball model introduces a sequence whose successive values differ by 1/√j and conditions each value on the history through that round.The proof uses it to help derive (6) from (5).Source: A Introduction to the “Color-Ball”… · pp. 17–18
• The second model's proof repeatedly takes conditional expectations and shifts leftover terms from r_k to r_{k−1} so that cancellation can be applied across epochs.The steps culminate in Lemma A.2.Source: A Introduction to the “Color-Ball”… · pp. 18–19
• The second model still omits a gradient-norm condition required by Lemma 5.2, in addition to the earlier idealization gaps.The authors say further technical lemmas are needed to address these gaps.Source: A Introduction to the “Color-Ball”… · pp. 17, 19

B More experiments

• On MNIST and CIFAR-10, the reported maxima satisfy ρ1 < 25, ρ2 < 400, and ρ3 < 0.1, giving ρ ≈ O(n).The estimates use β1 = 0.9, β2 = 0.99, and batch size 64.Source: B More experiments · pp. 19–20, Figure 9 · p. 20, Figure 10 · p. 20
• On MNIST, smaller batch sizes require larger β2 to reach small loss, consistent with a β2 threshold that rises with n.The paper relates smaller batches to larger n in the finite-sum setting.Source: B More experiments · p. 20, Figure 11 · p. 20
• As n increases, the observed convergence region shrinks while the divergence region expands, matching the paper's stated threshold trends.The experiments vary n and show optimality gaps after 50,000 iterations.Source: B More experiments · p. 20, Figure 12 · p. 21
• Starting from x = −5 lets the run reach the quadratic side of function (2), where the gradient is unbounded, and the gradient norm becomes large.Source: B More experiments · p. 21, Figure 13 · p. 21
• As β2 increases from 0 toward 1, gradient norms that rise rapidly at small β2 give way to a divergence-to-convergence phase transition.The experiment uses β1 = 0.1 and plots gradient-norm changes over iterations.Source: B More experiments · p. 21, Figure 14 · p. 21
• With D0 = 0, Adam reaches an exact critical point and the reported gradient norm after convergence is zero.The experiment uses function (2) with n = 20 and initialization x = −5.Source: B More experiments · p. 21, Figure 15 · p. 22
• With D0 > 0, Adam does not reach zero gradient norm in the reported example, instead converging to a bounded region that shrinks as β2 increases.Source: B More experiments · pp. 21–22

B.1 Experimental Settings

• The experiments use function (2), MNIST, CIFAR-10, and WikiText-103, with task-specific models, batch sizes, learning rates, and schedules.Source: §B.1 · p. 22

C Some Potential Implications for Practical Users

• If a trial point above the blue curve converges, points above it also converge, and increasing β2 or decreasing β1 at fixed β2 preserves a convergence guarantee.If it diverges, avoid points with β1 < √β2 and β2 below the trial β2.Source: C Some Potential Implications for… · p. 23
• If a point below the blue curve diverges, do not try points to its left or most points below it; instead, fix β1 and increase β2.The passage also recommends fixing β2 and trying smaller β1 as a way to move toward the guaranteed-convergence region.Source: C Some Potential Implications for… · p. 23
• For a starting point above the blue curve, increasing β2 sufficiently ensures convergence under Theorem 3.1, which applies when β1 < √β2.The theorem’s applicability to any β1 < √β2 means sufficiently large β2 can cover any β1 in [0,1).Source: C Some Potential Implications for… · p. 23

D.1 More Related Works on the Convergence Analysis of Adam Family

• Adam variants modify hyperparameters, second-moment estimates, effective step sizes, or momentum, while some convergence analyses require bounded gradients or bounded effective step sizes.The cited work also includes warm-up and partial adaptivity; the authors note that bounded effective step sizes make Adam resemble AdaBound.Source: §D.1 · p. 23

D.2 A Brief Introduction to (Reddi et al., 2018)

• The re-stated Reddi et al. (2018) example is constrained to x ∈ [−1, 1], where the authors distinguish its non-convergence from divergence to infinity.They describe the earlier result as iterates staying in a large region of the feasible set.Source: §D.2 · p. 24
• Reddi et al. (2018) show that for fixed β1 < √β2, a sufficiently large n permits a function on which Adam converges to the highly suboptimal x = 1.Their separate result for β1 = 0 and β2 = 1/(n^2 + 1) also gives convergence to x = 1.Source: §D.2 · p. 24
• Reddi et al. (2018) choose n depending on (β1, β2), so the function class changes across hyperparameter choices.Their fixed-n theorem covers only the single point (β1, β2) = (0, 1/(n^2 + 1)), leaving behavior elsewhere unclear.Source: §D.2 · p. 24

E Proof of Proposition 3.3

• For any fixed n > 2, the proof identifies an orange region of (β1, β2) choices that causes divergence to x = ∞ rather than the optimum.The divergence region is the intersection of conditions (C1) and (C2), and its size increases with n.Source: E Proof of Proposition 3.3 · pp. 24, 27
• For the fixed-n convex function, Adam diverges from initialization x = 1 when Proposition E.1’s conditions hold.The function has optimal solution x* = −2, and the proof shows an outer-loop update from xk,0 = 1 to xk+1,0 > 1; the gradient remains constant beyond 1, driving the iterates to infinity.Source: E Proof of Proposition 3.3 · pp. 24–25
• The proof’s divergence argument studies Adam’s trajectory within an outer loop and establishes conditions making positive terms outweigh a negative term.The authors state that sufficiently small η1 keeps the iterates in the linear region used by the argument.Source: E Proof of Proposition 3.3 · pp. 25–27

F.1 More notations

• The appendix defines epoch and inner-loop indices for iterates and uses random-shuffle indices to represent sampling without replacement.It also denotes ηk as the epoch stepsize and focuses on diminishing stepsizes, especially ηk = η1/√(nk).Source: §F.1 · pp. 27, 29

F.2 Some useful lemmas

• The appendix introduces preliminary lemmas under Assumptions 2.1 and 2.2, including bounds indexed by inner-loop position.The supplied passage states the lemma conditions but does not give the full bounds.Source: §F.2 · p. 30

G.1 A roadmap of the proof

• Increasing β2 controls changes in the moving-average factor, allowing it to be approximated by a fixed value; the analysis separates large- and small-gradient coordinates.The approximation error is described as vanishing as β2 approaches 1.Source: §G.1 · pp. 31–32
• For large β1, bounding the expected descent term is difficult because momentum contains historical gradients and the large-coordinate set varies across trajectories.The roadmap identifies three issues, including bounding the difference between current and weighted historical gradients and handling a random coordinate set.Source: §G.1 · pp. 33–34
• Step 1 adapts the color-ball idea by taking conditional expectations at epoch starts and using Lipschitz continuity to relate changing iterates to the fixed x_k,0.The adaptation addresses finite-versus-infinite momentum sums and additional error terms when moving both gradient expressions to match and cancel.Source: §G.1 · p. 34
• Step 2 uses Lemma G.2, under β1 < sqrt(β2), to replace a changing gradient-and-denominator factor with its value at an earlier epoch for conditional expectation.The replacement lets the factor be treated as fixed when taking the earlier epoch’s conditional expectation.Source: §G.1 · p. 35
• Step 3 represents the large-gradient coordinate set with an indicator and uses Lemma G.3, under β1 < sqrt(β2), to handle its trajectory-dependent change across epochs.Combining the three steps yields Lemma G.4’s bound under its stated conditions, with a term reported to go to zero as β2 approaches 1.Source: §G.1 · pp. 35–36
• The proof requires β1 < √β2 < 1 and a sufficiently large β2 threshold; the threshold depends on the problem instance and tends to 1 in the stated bound.The roadmap relates the threshold to the condition in Lemma G.6 and notes that the problem-dependent factor ρ can make the required β2 lower than the worst-case estimate suggests.Source: §G.1 · p. 37

G.2 Proof of Lemma G.1

• The proof of Lemma G.1 bounds component-wise momentum terms by comparing their second-moment denominators and applying a condition on the largest component gradient.The argument uses √v_l,k,i ≥ √(β2^i) and combines two cases to obtain the bound.Source: §G.2 · pp. 38–39

G.3 Proof of Lemma G.2

• The proof of Lemma G.2 handles j = 1 by cases on gradient signs and normalized-gradient ordering, then extends the inequality to j > 1.An associated constant tends to zero as β2 approaches 1.Source: §G.3 · pp. 40–42

G.4 Proof of Lemma G.4

• The proof of Lemma G.4 expands the momentum terms across epochs and introduces an auxiliary sequence to handle a change in the powers of β1.It then separates the difference into parts, bounding two with Lemmas G.11 and G.12 and the remaining part with Lemma G.13.Source: §G.4 · pp. 43, 46

G.7 Proof of Lemma G.13

• The Lemma G.13 proof moves backward across epochs, using conditional expectations and the color-ball method to bound terms while accumulating error terms.It converts variables to the previous epoch’s starting point using Lipschitz continuity before combining the bounds.Source: §G.7 · pp. 52, 53, 55, 56, 57

G.8 Proof of Lemma G.5

• The Lemma G.5 proof derives upper bounds for its components, bounds (d1) and (d2), and substitutes those bounds into the preceding inequality.The derivation uses inequalities to bound terms indexed by coordinates and epochs.Source: §G.8 · pp. 60–61

G.9 Proof of Lemma G.6

• In the Lemma G.6 proof, choosing β2 sufficiently close to 1 makes F3 small enough to satisfy the stated bound, and the proof concludes by combining its cases.Remark G.14 notes that F4 decreases monotonically to 0 as β2 increases to 1, while F5 is used as a cleaner constant.Source: §G.9 · p. 65

G.10 Proof of Lemma G.9

• The Lemma G.9 proof uses the Descent Lemma and specified constants, including ρ1, ρ2, and ρ3, whose bounds depend on coordinate-gradient alignment.In the worst case, 0 ≤ ρ3 ≤ √nρ1 ≤ n; greater alignment of coordinate gradients makes ρ3 larger.Source: §G.10 · pp. 66–67

G.11 Dissussion on Bias Correction Terms and Non-Zero ϵ (Hyperparameter for Numerical Stability)

• Bias correction and non-zero ϵ require only adjustments to the proof and constants; for non-zero ϵ, bounds on the modified second-order momentum decouple gradient and momentum dependencies and can simplify the analysis.Bias correction uses adjusted stepsize bounds and initialization; with positive ϵ, the analysis can reduce to SGD in the cases described.Source: §G.11 · pp. 67–68