PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Two Faces of Adam in Separable Linear Classification

Chen Fan, Csaba Szepesvári

arXiv:2609.33904v1cs.LG

TL;DR

Prior analyses describe different limiting margins for Adam with zero versus positive stability constant, but leave open how a small fixed positive constant shapes the trajectory between them. This paper quantifies that trajectory and shows that update transition precedes Euclidean-margin accuracy by a schedule-dependent timescale.

  • Problem

    Prior analyses identify max-norm-margin behavior at ε = 0 and Euclidean-margin behavior for positive ε, but do not describe how a small fixed positive ε moves a trajectory between these limits.

    Source: §1 · p. 1

  • Method

    The paper analyzes deterministic, full-batch, bias-corrected Adam on separable classification with polynomially decreasing stepsizes, bounding margin gaps at the update transition and the additional training needed for Euclidean-margin accuracy.

    Source: §1 · pp. 1–2

  • Results

    For 1/3 < a < 1, the update transition has polylogarithmic scale in 1/ε while prescribed Euclidean-margin accuracy takes polynomial scale; for a = 1, the scales are polynomial and exponential, respectively.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The classifier can remain nearly max-norm optimal after updates become gradient-like, and its later change can improve or worsen generalization after training examples are correctly classified.

    Source: §1 · p. 2

    The guarantees require finite positive ε and data- and algorithm-dependent sufficient conditions; the polynomial exponent for Euclidean-margin time when a < 1 is left undetermined.

    Source: §1 · p. 2

Abstract

from arXiv · show

We consider the behavior of deterministic, full-batch, bias-corrected Adam in separable linear classification with softmax parametrization under log-loss. In this setting, under a wide range of conditions Adam is known to approach max-norm-margin optimality when its stability constant $\epsilon$ is zero, while with a positive $\epsilon$, it is known to approach Euclidean-margin optimality. Our main contribution is the quantitative description of Adam's behavior for small fixed positive $\epsilon$. We give sufficient conditions under which an Adam-trained classifier nearly maximizes the max-norm margin before the updates become gradient-like. We also show that the classifier reaches a fixed target Euclidean margin only much later. Specifically, we show that for polynomially decreasing stepsizes with exponent \(a\), where \(1/3<a<1\), the updates become approximately proportional to the negative gradient after $\Theta(\log(1/\epsilon)^{1/(1-a)})$ iterations. At that time, the classifier still nearly maximizes the max-norm margin. Reaching a fixed target Euclidean margin above that of every max-norm-optimal classifier, but below the optimum, is shown to require $\epsilon^{-\Theta(1)/(1-a)}$ iterations. Under inverse-linear stepsize decay (\(a=1\)), the update transition takes polynomially many iterations, whereas reaching the target margin takes exponentially many. Experiments support these predictions. The later change in the classifier can improve or worsen generalization after training error reaches zero, connecting the analysis to grokking and its reverse.

1 INTRODUCTION

The paper quantifies how deterministic Adam with small positive stability parameter ε moves between max-norm and Euclidean-margin behavior in separable classification. It shows that the updates become gradient-like while the classifier remains nearly max-norm optimal, with the stepsize schedule governing how much longer Euclidean-margin accuracy takes.

1 INTRODUCTION

  • The transition reconciles the two limiting descriptions: ε = 0 leads to max-norm-margin maximization, whereas positive ε ultimately leads to Euclidean-margin maximization.The early sign-like updates and later gradient-like updates provide an intuitive account of the change.Source: §1 · p. 1
  • For deterministic, full-batch, bias-corrected Adam on separable linear classification, the analysis tracks how a fixed positive ε changes the trajectory between two limiting margin geometries.The setting uses logistic loss for binary classification, with an extension to multiclass softmax cross-entropy.Source: §1 · pp. 1–2
  • At the update transition, the classifier’s max-norm margin gap is small, with a bound that vanishes as ε decreases.The paper also bounds how long this near-optimality persists as post-transition movement remains small relative to the weight norm.Source: §1 · p. 2
  • For 1/3 < a < 1, the update transition occurs on a polylogarithmic scale in 1/ε, while reaching prescribed Euclidean-margin accuracy takes a polynomial scale.For a = 1, these scales become polynomial and exponential, respectively.Source: §1 · p. 2
  • After training examples are classified correctly, the later classifier change can improve or worsen generalization, connecting the trajectory to grokking and its reverse.The connection is to delayed improvement or deterioration in predictive performance associated with changing implicit bias.Source: §1 · p. 2
  • The guarantees require finite positive ε and data- and algorithm-dependent sufficient conditions, and the polynomial exponent for Euclidean-margin time when a < 1 remains undetermined.The authors also describe their sufficient conditions as conservative.Source: §1 · p. 2

2 PROBLEM SETUP AND PRELIMINARIES

The analysis studies separable binary linear classification with logistic loss and deterministic, bias-corrected Adam. It uses a decreasing stepsize schedule and gradient-scale tools to track the optimizer’s update geometry and margin behavior.

2 PROBLEM SETUP AND PRELIMINARIES

  • The setup uses signed examples z_i = x_i y_i, separability, and normalized max-norm and Euclidean margins to describe classifier geometry.The data are required to admit a vector with strictly positive signed margin.Source: §2 · pp. 2–3
  • Adam uses exponential moving averages of gradients and squared gradients, with a fixed positive stability constant ε and bias correction.The analysis assumes 0 ≤ β1 ≤ β2 < 1; whether the results extend beyond this condition is left open.Source: §2 · pp. 3–4
  • The stepsize schedule is η_t = η_0(t + 1)^−a, with η_0 > 0 and 1/3 < a ≤ 1.The schedule has a divergent cumulative stepsize and additional regularity properties used in the analysis.Source: §2 · p. 3
  • The gradient-scale proxy G(w) is used to control gradient norms through the data margins, while bias-corrected moments track the gradient and its coordinatewise magnitude after burn-in.The tracking errors are bounded at scale O(η_t G_t).Source: §2 · p. 3
  • The idealized Adam update follows a soft-sign map, which is gradient-like when gradient coordinates are small relative to ε and can be sign-like when they dominate ε.The analysis measures sign-likeness through relative first-order loss decrease rather than requiring coordinatewise closeness to the sign vector.Source: §2 · pp. 3–4
  • After a reference time, the loss and gradient-scale proxy are comparable and both converge to zero.The stated bounds apply for all t ≥ T* in the proposition’s setting.Source: §2 · p. 4

3 MAIN RESULTS

The main results locate the update crossover and compare classifier margins around it. They show that the update becomes permanently gradient-like while max-norm-margin optimality remains nearly intact, even when the two optimal geometries differ.

3 MAIN RESULTS

  • The stopping times are defined to mark the update’s geometric transition, with T1 serving as the reference crossover time.Their ordering is T−1 < T1 < T+1 for sufficiently small ε.Source: §3 · p. 4
  • The times T−1 and T+1 bracket the update crossover, and T1 marks permanent entry into the gradient-like regime.The update is sign-like at T−1 and gradient-like at T+1; at T1 the gradient residual is bounded by O(δ) plus a term vanishing with ε.Source: §3 · p. 4
  • Theorem 3 bounds the max-norm margin gap as small at the pre-crossover, reference, and post-crossover times, while the Euclidean-margin gap remains bounded below by the separation between the optimal geometries, up to a vanishing error.The geometric separation is positive when no direction is optimal under both norm geometries.Source: §3 · p. 5
  • The margin results at T1 are transferred to the post-crossover time, after which the analysis asks how much additional training achieves a prescribed Euclidean-margin accuracy.The subsequent analysis relates max-norm-margin persistence to post-crossover movement relative to the classifier’s existing size.Source: §3 · p. 5

1. The γ∞constant

A refined stopping-time argument preserves the sharp leading coefficient for the update transition. It separates the trajectory into intervals where either a sharp or uniformly positive descent bound suffices.

1. The γ∞constant

  • A direct bound using T1 alone may yield a nonpositive descent coefficient or replace γ∞ with the smaller κδ.The auxiliary cutoff keeps Gt above ϵΛϵ, making dϵ/Gt=o(1) and recovering the coefficient γ∞ − o(1).Source: §1 · p. 5
  • The interval from the auxiliary cutoff to T1 needs only a uniformly positive descent coefficient because Gt decreases by a factor of order Λϵ/δ.The reported stopping-time refinements include an O(log ℓϵ) difference and a Θ(ℓϵ^b) interval.Source: §1 · pp. 5–6
  • The update transition satisfies S_T1 − S_T* = ℓϵ/γ∞ + o(ℓϵ), preserving the sharp leading coefficient.The auxiliary cutoff isolates the interval where the descent coefficient is γ∞ − o(1); a weaker positive coefficient suffices for the shorter remaining interval.Source: §1 · pp. 5–6

2. The weight-norm bound

The weight-norm argument splits the trajectory at kϵ=⌈ℓϵ⌉ to control the contributions before and after that time. This split balances the early iterate size against a stepsize-weighted error term.

2. The weight-norm bound

  • Applying Lemma 1 directly from T* leaves an η_T*Hϵ term of the same order as the leading term ℓϵ/γ∞.That bound therefore does not provide the desired lower-order remainder.Source: §2 · p. 6
  • Splitting at kϵ=⌈ℓϵ⌉ lets the proof bound w_T1 using separate contributions from the early trajectory and the later interval.The split is chosen so Lemma 1 applies on [kϵ,T1), with kϵ between T* and T1.Source: §2 · p. 6
  • The split balances the early iterate norm against the η_kϵHϵ term, with each contribution described as small.The early contribution is bounded using S_kϵ, while the stepsize-weighted term is separately controlled.Source: §2 · p. 6

3. From the ℓ∞-margin to the ℓ2-margin

The analysis transfers near-optimal max-norm margins through the update crossover, then bounds later Euclidean-margin improvement by post-crossover movement. Experiments support the predicted separation between update and classifier transition scales.

3. From the ℓ∞-margin to the ℓ2-margin

  • At T1, the classifier has max-norm margin at least ℓϵ−O(1), and the analysis transfers margin bounds across nearby iterates.For p∈{∞,2}, the normalized-margin change from T−1 to T1 is O(log ℓϵ/ℓϵ).Source: §3 · pp. 6–7
  • For t≥T1, the margin gap is controlled by the initial rϵ gap and the ratio Ht/ℓϵ, which measures post-crossover movement relative to classifier size.The post-T1 trajectory is represented as a normalized-gradient trajectory with a summable perturbation.Source: §3 · p. 7
  • When Δgeom>0, reaching Euclidean-margin accuracy ζ requires effective movement comparable to the classifier norm inherited at T1, which is Θ(ℓϵ).The theorem’s movement comparison is stated for ζ∈(0,Δgeom), and the iteration scales follow by combining it with the stopping-time characterization.Source: §3 · p. 8
  • The analysis extends to separable multiclass classification using the cross-entropy gradient proxy introduced by Fan et al. (2025).The paper places details of this extension in Appendix I.Source: §3 · p. 8

Experiments

  • The normalized max-norm-to-Euclidean gap is 0.831 ± 0.030, so more than 83% of that gap remains even after the update has become strongly gradient-like.Source: Experiments · p. 8
  • The fitted slope of γ∞(S_T1−S_T*) against ℓϵ is 1.036, close to the predicted unit slope.For a=1/2, the reported near-linear dependence of √T1 and log τζ on ℓϵ agrees with the predicted transition scales.Source: Experiments · p. 9
  • The experiments report τζ=ϵ^−Θ(1), supporting a polynomial classifier-transition scale distinct from the polylogarithmic update-transition scale.The cited experimental discussion describes the separation between local-update and classifier transitions.Source: Experiments · p. 9

4 RELATED WORK

Prior work studies implicit bias in gradient and adaptive methods, including Adam’s distinct limiting margins with zero versus positive stability constants. The paper distinguishes its focus on fixed-positive-ϵ trajectory evolution from work on annealed stability constants.

4 RELATED WORK

  • For separable linear classification, gradient descent converges directionally to the Euclidean max-margin classifier, while normalized and accelerated gradient methods have faster margin-gap rates [Soudry et al., 2018; Ji & Telgarsky, 2019; Nacson et al., 2019; Ji & Telgarsky, 2021; Ji et al., 2021].Related analyses also cover multiclass classification, homogeneous networks, matrix factorization, self-attention, and other descent geometries.Source: §4 · p. 9
  • For Adam, a fixed positive stability constant leads to the Euclidean max-margin direction, whereas removing it yields optimal max-norm margin.Related work examines sampling effects, AdamW, and adaptive methods in homogeneous networks.Source: §4 · p. 9
  • Wang et al. (2026) study annealed stability in memoryless smoothed-sign descent; this paper instead studies update and classifier geometry over time for bias-corrected Adam with fixed stability.The cited work compares endpoint geometries across annealing schedules.Source: §4 · p. 9

5 CONCLUSION

The conclusion describes a long separation between Adam’s update transition and its classifier’s move toward Euclidean optimality. For the analyzed setting, it also identifies extensions to stochastic and constant-step-size Adam and neural networks as future work.

5 CONCLUSION

  • At the update crossover, Adam is gradient-like while its classifier remains nearly max-norm-margin optimal and, when Δgeom > 0, bounded away from Euclidean optimality.Closing this gap requires Θ(log(1/ϵ)) additional effective movement.Source: §5 · p. 9
  • For a ∈ (1/3, 1), transition times scale polylogarithmically while Euclidean-margin progress takes polynomial time; for a = 1, the respective scales are polynomial and exponential.Source: §5 · p. 9
  • Future work includes extending the analysis to stochastic Adam, Adam with constant step sizes, and neural networks.Source: §5 · p. 9

A.2 NONLINEAR EXPERIMENTS

This section concerns nonlinear experiments and related analysis, with the supplied leads describing a qualitative update transition but noting that the passages do not establish iteration-time exponents or report nonlinear experimental findings.

A.2 NONLINEAR EXPERIMENTS

  • The nonlinear experiments are qualitative: constant stepsizes preclude testing the linear iteration-time exponents, and empirical GD and SignGD margins approximate otherwise intractable max-margin references.The GD reference uses the median of its final 10% of checkpoints; SignGD is stopped when training loss first falls below 10^-7.Source: §A.2 · pp. 13–14
  • Median times to sustained 100% training accuracy were only 8, 5, and 5 iterations, even as logistic loss kept falling by many orders of magnitude.Predictive accuracy alone therefore did not reveal either geometric transition.Source: §A.2 · p. 15
  • Median update-transition times T30 upd rose from 1,106 to 2,970 to 4,808 as ϵ fell from 10^-4 to 10^-8 to 10^-12, while gradient residuals were 0.280, 0.241, and 0.212.At these transitions, the updates were gradient-like rather than sign-like.Source: Table 1 · p. 15, §A.2 · p. 15
  • At the update transition, median R2 values were 0.677, 0.765, and 0.818 for ϵ = 10^-4, 10^-8, and 10^-12; by training’s end they remained 0.500, 0.700, and 0.776.Only three of eight seeds at ϵ = 10^-4 reached the half-gap event, and none did at ϵ = 10^-8 or 10^-12; smaller ϵ left a larger empirical Euclidean-margin gap in the gradient-like regime.Source: §A.2 · p. 15

B PRELIMINARIES

  • Under separability and the stated Adam parameter conditions, the preliminary linear-model setup uses ηt = η0(1 + t)^-a with η0 > 0 and a ∈ (1/3, 1].It assumes 0 ≤ β1 ≤ β2 < 1 and ϵ ∈ (0, 1].Source: B PRELIMINARIES · p. 16

B.1 THE LOSS AND THE PROXY

  • For the linear loss proxy G(w), the supplied bounds relate it to ℓ1 and ℓ2 gradient norms and establish G(w) > 0 and g(w) ≠ 0 at finite w.When G(w) ≤ 1/(2n) or L(w) ≤ log 2/n, the passages also state L(w) ≤ 2G(w) and ρ(w) ≥ 0.Source: §B.1 · pp. 16–18

A.2 NONLINEAR EXPERIMENTS

  • For logistic loss, log(−ℓ′(x)) is globally 1-Lipschitz because its derivative has absolute value at most 1.The passage gives −ℓ′(x) = 1/(1 + e^x) and log(−ℓ′(x)) = −log(1 + e^x).Source: §B.1 · p. 20
  • If the ratio R of two negative loss derivatives satisfies e^−h ≤ R ≤ e^h, then |R − 1| ≤ e^h − 1.The proof handles separately the cases R ≥ 1 and R < 1.Source: §B.1 · p. 21

B.2 ADAM’S UPDATE AND EMA

The appendix establishes bounds connecting Adam’s bias-corrected exponential moving averages to its regularized-sign update. These estimates support loss convergence and the subsequent analysis of Adam’s update behavior.

B.2 ADAM’S UPDATE AND EMA

  • After the EMA burn-in time, the Adam direction D_t is close to the regularized-sign direction σ_ϵ(g_t), with an error bounded by a constant times η_t G_t.The bound holds for all t ≥ t_ema and ϵ > 0.Source: §B.2 · pp. 24–25
  • A second bound controls the direction error after scaling by ϵ, using the EMA first- and second-moment deviations from the gradient and its coordinatewise magnitude.Source: §B.2 · p. 25
  • The regularized-sign direction retains a large gradient inner product: ⟨g, σ_ϵ(g)⟩ ≥ ∥g∥_1 − dϵ.Source: §B.2 · p. 26
  • For polynomially decreasing stepsizes with a ∈ (1/3, 1], the proof establishes that the loss and G_t converge to zero.It first uses a decreasing potential and the divergence of the cumulative stepsize.Source: §B.2 · p. 27

C SIGN AND GRADIENT RESIDUAL CHARACTERIZATION

This section characterizes sign and gradient residuals in terms of λ_t = G_t/ε and the step size, applying the bounds at stopping times around a target loss level. It also establishes a maximization step using strict concavity and the fact that taking a logarithm preserves the maximizing point.

C SIGN AND GRADIENT RESIDUAL CHARACTERIZATION

  • The gradient residual is bounded above by R1λ_t/(1+R1λ_t)+C0η_t, while the sign residual obeys bounds depending on λ_t and η_t.The sign-residual bounds are 1/(1+R1λ_t)−C0η_t ≤ r_sgn_t ≤ min{1,dγ∞λ_t}+C0η_t.Source: C SIGN AND GRADIENT RESIDUAL… · p. 30
  • The passages establish endpoint findings for the gradient residual: rgrad_t(ε) tends to 1 in one limit case and to 0 in another, without specifying a step-size schedule.Source: C SIGN AND GRADIENT RESIDUAL… · p. 30
  • For sufficiently small ε, the stopping times satisfy T^−(ε;b)<T_δ(ε)<T^+(ε;b), and both outer times and their λ values diverge as ε↓0.The proposition establishes this ordering for every b,δ∈(0,1).Source: C SIGN AND GRADIENT RESIDUAL… · p. 30
  • At T_δ, the sign residual lies between 1−A_δ−o_ε(1) and 1+o_ε(1), while the gradient residual is at most A_δ+o_ε(1).Here A_δ=R1δ/(1+R1δ), and λ_Tδ→δ as ε↓0.Source: C SIGN AND GRADIENT RESIDUAL… · p. 32
  • Strict concavity gives a unique critical point at x = b, and q is identified as the global maximizer because taking the logarithm preserves the maximizing point.Source: C SIGN AND GRADIENT RESIDUAL… · p. 34
  • Substitution into (63) and (64) completes the proof.Source: C SIGN AND GRADIENT RESIDUAL… · p. 34

D PROOF OF LEMMA 1

The proof of Lemma 1 controls Adam’s cumulative update by splitting its coordinatewise history at time r. Matching the auxiliary second-moment bound to the post-r first-moment history preserves a sharp leading coefficient while bounding transient and logarithmic terms.

D PROOF OF LEMMA 1

  • The coordinatewise argument splits d_t into R_t and the bias-correction residual (χ_t − 1)R_t, bounding the latter’s cumulative contribution by C_bcη_r.The proof first controls R_t and then the difference d_t − R_t.Source: D PROOF OF LEMMA 1 · pp. 35, 36, 40
  • Because the second-moment history includes pre-r terms, the proof introduces Q_k with the same post-r initial condition as M_k to enable clean recurrence and logarithmic cancellation.The proof uses Q_k as a lower bound on the denominator quantity.Source: D PROOF OF LEMMA 1 · pp. 35–36
  • The weighted main term contributes exactly S_r,T, while geometric and logarithmic terms contribute O(η_r) and O(η_r H_ϵ), preserving leading coefficient 1.The combined bound is stated as a main-term sum plus an η_r(1 + H_ϵ) error.Source: D PROOF OF LEMMA 1 · pp. 36, 39

E ADAM’S LOCAL UPDATE TRANSITION

  • The local-update-transition analysis assumes separable data, 0 ≤ β1 ≤ β2 < 1, ϵ ∈ (0, 1], and η_t = η0(t + 1)^−a for a ∈ (1/3, 1].It also defines R1 and R2 as maximum per-example feature norms in the L1 and L2 norms.Source: E ADAM’S LOCAL UPDATE TRANSITION · p. 41

E.1 PROOF OF THEOREM 4

The proof develops loss-decay and update-ratio bounds around the crossover, locating associated stopping times in the S-clock and relating loss, gradient norm, and cumulative step size. Under the stated separability and Adam conditions, it also establishes feasibility and margin bounds for analyzing max-norm margin gaps, including a nonempty feasible characterization of the max-norm-optimal set.

Stopping-time estimates

  • All three stopping times diverge as ϵ↓0, and their corresponding learning rates converge to zero.Source: §E.1 · p. 42

Proof Sketch of Theorem 4

  • Before the crossover, loss decays exponentially in the S-clock; afterward, reciprocal loss grows linearly in S_t/ϵ.Source: §E.1 · p. 42

Part 2: Characterization of S_Tδ−S_T−

  • The additional S-clock interval from T− to Tδ is O(log ℓϵ), negligible compared with the leading ℓϵ scale.Source: §E.1 · pp. 43, 47

Part 1: Characterization of S_T−

  • S_T−−S_T* has leading scale ℓϵ/γ∞, with matching upper and lower bounds as the proof parameters are sent to their limits.The upper-bound coefficient tends to 1/γ∞ as ζ↓0, and the lower bound is 1/γ∞.Source: §E.1 · pp. 45–47

E.1 PROOF OF THEOREM 4

  • For every t ≥ τ, the loss remains bounded by L_t ≤ 2δϵ.The proof closes an induction using bounds on the update and the Taylor remainder.Source: §E.1 · p. 48

E.2 IMPLICATIONS OF THEOREM 4

  • For p + q = 1 and sufficiently small ϵ, Corollary 23 gives rgrad_t ≤ p and rsgn_t ≥ q under its stated δ bound.It requires 0 < δ < min{1, p/(2R1q)}; the proof bounds the ratios using the learning rate at the threshold time τ.Source: §E.2 · p. 50

E.3 PROOF OF PROPOSITION 3.1

  • After τ, the proof establishes G_t ≍δ ϵ/(1 + V_t) and H_t ≍δ log(1 + V_t).Here V_t is the cumulative stepsize after τ; the argument applies under sufficiently small-ϵ conditions that control the stepsize at τ.Source: §E.3 · pp. 53–54

F ADAM’S ℓ∞-MARGIN OPTIMALITY

  • The proof assumes separable data, 0 ≤ β1 ≤ β2 < 1, ϵ ∈ (0, 1], and ηt = η0(t + 1)^−a for η0 > 0 and a ∈ (1/3, 1].Source: F ADAM’S ℓ∞-MARGIN OPTIMALITY · p. 54
  • The proof invokes Hoffman’s error bound and a margin-difference bound, then identifies Theorem 31, Theorem 29, and Corollary 32 as results on the margin gaps at T−1 (ϵ; b).The error-bound lemma cites Hoffman (1952) and Peña et al. (2021).Source: F ADAM’S ℓ∞-MARGIN OPTIMALITY · pp. 54–55
  • M∞ equals the feasible set {u : AHu ≤ cH}, and the proof establishes that this system is feasible, so M∞ is nonempty.The characterization follows by showing both set inclusions; compactness of [−1, 1]^d and continuity of ρ ensure the maximum defining γ∞ is attained.Source: F ADAM’S ℓ∞-MARGIN OPTIMALITY · p. 55
  • The margin function ρ is R1-Lipschitz in max norm and R2-Lipschitz in 2-norm, providing bounds used to compare margins of vectors.The proof applies these Lipschitz properties to derive margin-difference bounds in both norms.Source: F ADAM’S ℓ∞-MARGIN OPTIMALITY · pp. 55–56

F.1 MARGIN GAP AT T1

This section characterizes the classifier’s scale and margin properties at the stopping and crossover times: as ε decreases, its normalized margin approaches the max-norm optimum, while at T1 it retains a positive Euclidean-margin gap when Δ_geom > 0. It also bounds post-crossover change and carries these margin-gap properties to T+.

F.1 MARGIN GAP AT T1

  • The infinity norm at τϵ satisfies ∥wτϵ∥∞ ≤ Sτϵ−ST* + O(ωa(ℓϵ)), and thus is bounded by ℓϵ/γ∞ up to lower-order corrections.This bound combines the radius estimate with the cumulative-scale bound.Source: §F.1 · p. 63
  • For 1/3<a<1, the rate rϵ = ℓϵ^-a tends to zero as ℓϵ→∞, which the passage attributes to a>0 and ℓϵ→∞.Source: §F.1 · p. 63
  • For Δ_geom > 0, lim inf_{ε↓0}[γ2 − ˆγ2(w_T1δ(ε))] ≥ Δ_geom, and for sufficiently small ε the gap is at least Δ_geom/2.Source: §F.1 · p. 65
  • At T1δ(ε), the max-norm margin gap is at most C∞,δ rε, while the Euclidean-margin gap is at least Δ_geom − C2,δ rε.Source: §F.1 · p. 67

F.3 MARGIN GAP AT T +

  • After crossover, the accumulated bound Ht is at most CHV log(1 + Vt), supporting margin-gap bounds at T +.The post-crossover bounds preserve near-max-norm optimality and a positive Euclidean-margin gap at T + for sufficiently small ε.Source: §F.3 · pp. 68–69

G ADAM’S EUCLIDEAN OPTIMALITY

The section bounds the Euclidean-margin gap after crossover and characterizes how much accumulated update time is needed to reach a smaller target gap.

G ADAM’S EUCLIDEAN OPTIMALITY

  • After crossover, the Euclidean-margin gap is bounded by a constant multiple of (1 + ||w_τ||2)/(1 + H_t).The proof handles separately the cases where H_t is above or below a fixed threshold.Source: G ADAM’S EUCLIDEAN OPTIMALITY · pp. 73–74
  • The accumulated update quantity H_t grows comparably to log(1 + V_t), while the loss decreases exponentially in H_t.The proof also bounds the margin and classifier norm in terms of H_t.Source: G ADAM’S EUCLIDEAN OPTIMALITY · pp. 70, 74
  • For any target gap ζ with 0 < ζ < Δ, the first time τ_ζ reaching that gap is finite.The proof upper-bounds H at this hitting time using a threshold A_ζ and the bounded update size.Source: G ADAM’S EUCLIDEAN OPTIMALITY · p. 74
  • At τ_ζ, the cumulative quantity V is bounded between powers of 1/ε, giving an ε-dependent delay to reach the target gap.The bounds are stated with exponents depending on δ and ζ.Source: G ADAM’S EUCLIDEAN OPTIMALITY · pp. 74–75

H PROOF OF COROLLARY 6

This appendix develops the technical bounds and multiclass ingredients used in the proof, including asymptotic iteration-time estimates, update properties, and margin-related continuity and solution-set bounds.

H PROOF OF COROLLARY 6

  • For 1/3 < a < 1, the transition time scales as (log(1/ϵ))^(1/(1−a)), while the target-margin time lies between polynomial bounds in ϵ^−1 with exponents α/(1−a) and β/(1−a).Here α and β are positive constants from Theorem 5 for the chosen δ and ζ.Source: H PROOF OF COROLLARY 6 · pp. 76–77
  • With inverse-linear decay, the transition time is polynomial in ϵ^−1, whereas the target-margin time is bounded above and below by exponentials in ϵ^−1.The target-time bounds use powers α and β, respectively, for positive constants determined by δ and ζ.Source: H PROOF OF COROLLARY 6 · p. 77

I.1 SETUP AND NOTATION

  • The multiclass setup assumes separable data, 0 ≤ β1 ≤ β2 < 1, and step sizes ηt = η0(t + 1)^−a for 1/3 < a ≤ 1, with max-norm and Frobenius margins defined.The setup also defines B1 and B2 as the maximum input ℓ1 and ℓ2 norms.Source: §I.1 · p. 78

I.2 SECTION B ANALOGOUS LEMMAS

  • In the multiclass setting, the gradient’s sum norm and Frobenius norm are each bounded above and below by constants times the proxy G(W), so the gradient is nonzero at every finite W.The stated bounds are γmax G(W) ≤ ∥∇L(W)∥sum ≤ R1 G(W) and γF G(W) ≤ ∥∇L(W)∥F ≤ R2 G(W).Source: §I.2 · p. 78

It satisfies

  • The multiclass Hessian is nonnegative and bounded above by R2^2 G(W)∥A∥F^2 for direction A, supporting the Frobenius curvature bound.The proof introduces this lemma as a refinement of Fan et al. (2025, Lemma 14), noting that direct application yields a factor of 2R2^2 in the Frobenius bound.Source: §I.2 · p. 81, It satisfies · p. 82
  • The multiclass Adam update has a bounded entrywise max norm, and its soft-sign map satisfies ⟨A, σ_ϵ(A)⟩F ≥ ∥A∥sum − Kdϵ.The soft-sign inequality follows by summing an entrywise lower bound over all Kd matrix entries.Source: It satisfies · p. 84

I.3 SECTION F ANALOGOUS LEMMAS

  • The multiclass margin function is Lipschitz in both the matrix max norm and Frobenius norm, with constants R1 and R2, respectively.Source: §I.3 · p. 86
  • The multiclass Hoffman system yields a bound involving Frobenius distance to the max-norm solution set, with a finite constant depending only on AH.The max-norm solution set is characterized by the system AH vec(W) ≤ cH.Source: §I.3 · p. 87

I.4 MAIN RESULTS

The multiclass results establish convergence of Adam’s loss and gradient to zero and characterize behavior after crossover, including bounds on accumulated update residuals.

I.4 MAIN RESULTS

  • With uniformly bounded coordinatewise gradients, the multiclass accumulated-radius bound uses a constant depending only on β1 and β2.The multiclass setting permits the gradient bound B_g = R1.Source: §I.4 · p. 88
  • For every fixed ε in (0, 1], the multiclass Adam trajectory has loss and gradient residual tending to zero, with 1/2 L_t ≤ G_t ≤ L_t after T*.The common low-loss time T* and the lower-bound constant are independent of ε.Source: §I.4 · p. 88
  • After the multiclass crossover time, loss and gradient residual have comparable scales, while the accumulated weighted update residual is bounded by a data- and schedule-dependent constant.The residual bound is stated in Frobenius norm.Source: §I.4 · p. 89
  • For sufficiently small positive ε, the multiclass results give a thresholded characterization of when the classifier reaches the stated Euclidean-margin conditions.The theorem applies for ζ below the multiclass geometric separation and supplies constants bounding the classifier norm at the specified stopping time.Source: §I.4 · p. 91
Loading 2609.33904v1…