paper-v1.txt

The Implicit Bias of Adam and Muon on Smooth Homogeneous
Neural Networks
Eitan Gronich

Gal Vardi

arXiv:2602.16340v1 [cs.LG] 18 Feb 2026

Weizmann Institute of Science
{eitan.gronich, gal.vardi}@weizmann.ac.il

Abstract
We study the implicit bias of momentum-based optimizers on homogeneous models. We first extend
existing results on the implicit bias of steepest descent in homogeneous models to normalized steepest
descent with an optional learning rate schedule. We then show that for smooth homogeneous models,
momentum steepest descent algorithms like Muon (spectral norm), MomentumGD (ℓ2 norm), and Signum
(ℓ∞ norm) are approximate steepest descent trajectories under a decaying learning rate schedule, proving
that these algorithms too have a bias towards KKT points of the corresponding margin maximization
problem. We extend the analysis to Adam (without the stability constant), which maximizes the ℓ∞
margin, and to Muon-Signum and Muon-Adam, which maximize a hybrid norm. Our experiments
corroborate the theory and show that the identity of the margin maximized depends on the choice of
optimizer. Overall, our results extend earlier lines of work on steepest descent in homogeneous models
and momentum-based optimizers in linear models.

1

Introduction

Deep neural networks show remarkable generalization performance despite often being overparameterized,
and even when trained with no explicit regularization. A well-established line of work attempts to explain
this phenomenon with the notion of the implicit bias (tendency) of gradient-based optimization algorithms to
converge to well-generalizing solutions. This bias is often realized in the form of maximizing a certain margin
for the training points (cf. Vardi (2023)).
While earlier works studied mostly gradient descent and showed its implicit bias towards maximizing
the ℓ2 margin in increasingly complex models, recent years have witnessed an interest in the study of the
implicit bias of other optimizers, such as Adam (Kingma and Ba, 2015), AdamW (Loshchilov and Hutter,
2019), and recently Muon (Jordan et al., 2024), hand-in-hand with their rising popularity. Indeed, as these
algorithms are used near-universally for training large language models (LLMs) and vision transformers, there
is a growing imperative to understand their inner workings.
In this work, we study smooth homogeneous models and show a margin-maximization bias of Adam and
Muon. Previous work analyzed the implicit bias of Adam and Muon on linear predictors (Zhang et al., 2024;
Fan et al., 2025), and we extend these results to the substantially broader class of smooth homogeneous
models. Moreover, our analysis of Muon is a special case of a more general framework that we develop, which
is applicable to all momentum-based optimizers built on top of steepest descent algorithms. All of our results
hold for a family of exponentially tailed losses that includes the logistic and exponential losses.
Our main contributions are as follows:
1. We show that any limit point of ∥θθtt ∥ in a normalized steepest descent trajectory with a learning
R∞
rate schedule η(t) is a KKT point of the ∥·∥-max-margin problem, as long as 0 η(t)dt = ∞. This
1

result holds for any locally Lipschitz, C 1 -stratifiable homogeneous model, including ReLU networks.
It extends a result by Tsilivis et al. (2025) that considered (unnormalized) steepest descent with a
constant learning rate.
2. We show that when ∥θθtt ∥ converges, it converges to the direction of a KKT point of the ∥·∥-maxmargin problem even for trajectories which approximate steepest descent. This allows us to focus on
momentum-based optimizers on smooth homogeneous models and show:
(a) Muon has an implicit bias towards margin maximization with respect to a norm defined using
spectral norms of the weight matrices, under a decaying learning rate regime. In fact, the bias
towards margin maximization holds for any normalized Momentum Steepest Descent (MSD)
algorithm, for the appropriate norm. We show this includes composite MSD algorithms such as
Muon-Signum. In addition, we prove an implicit bias of Muon-Adam.
(b) Adam (without the stability constant) has an implicit bias towards ℓ∞ margin maximization under
a decaying learning rate regime.

Related Work
Soudry et al. (2018) first showed that gradient descent in linear models maximizes the ℓ2 margin. This result
was followed by several works on margin maximization in linear fully-connected, convolutional and diagonal
networks (e.g., Ji and Telgarsky (2018); Gunasekar et al. (2018b); Yun et al. (2020); Moroshko et al. (2020)).
Going beyond linear networks, Chizat and Bach (2020) studied the implicit bias in infinitely-wide two-layer
smooth homogeneous networks, and proved margin maximization w.r.t. a certain function norm, known as
the variation norm. Lyu and Li (2019) studied homogeneous models under gradient descent, demonstrating
that any limit point of the direction of the vector of parameters ∥θθtt ∥ is the direction of a KKT point of
the max-margin problem. In a complementary result, Ji and Telgarsky (2020) showed that directional
convergence of the parameters is indeed guaranteed when optimizing homogeneous models definable in an
o-minimal structure with gradient descent. The implicit bias of gradient descent in certain non-homogeneous
neural networks was studied in Nacson et al. (2019a); Kunin et al. (2022); Cai et al. (2025). For a more
comprehensive survey on the implicit bias of gradient descent, see Vardi (2023).
A general treatment of the implicit bias of the family of steepest descent algorithms was given for linear
models by Gunasekar et al. (2018a), who proved maximization of the appropriate norm-dependent margin.
Tsilivis et al. (2025) generalized that result and the result by Lyu and Li (2019) and proved for homogeneous
models under steepest descent that any limit point of ∥θθtt ∥ is a KKT point of the max-margin problem.
Adam in the context of homogeneous models was studied by Wang et al. (2021), who showed a bias
towards ℓ2 -margin maximization. Notably, this work studied Adam without momentum in the numerator
and with a stability constant ε which asymptotically dominates the denominator, driving behavior to be
similar to gradient descent. Follow-up works have argued that the analysis of the implicit bias with the
stability constant is less faithful to the characteristics of Adam in practice, as the stability constant is typically
negligible throughout the trajectory. Such works on Adam without the stability constant have so far focused
on linear models and include Zhang et al. (2024) and Fan et al. (2025), in the binary and multiclass settings
respectively, who showed ℓ∞ margin maximization, and Baek et al. (2025) who showed that the implicit
bias of Adam under a deterministic batching routine can deviate from the full-batch case. We generalize the
result by Zhang et al. (2024) to smooth homogeneous models. AdamW, contrasting with other algorithms by
its utilization of explicit weight decay, was studied for smooth models and losses by Xie and Li (2024), who
showed that limit points of the trajectory are KKT points of the loss under the constraint that the ℓ∞ norm
of the parameters is bounded.
Fan et al. (2025) studied normalized steepest descent and its momentum counterparts on linear models in
the multiclass setting, including spectral descent and Muon respectively, and showed maximization of the
appropriate margins. We generalize their result, albeit in the binary classification setting.

2

2

Preliminaries

2.1

Setting and Notations

d
Throughout this work, we consider a fixed binary classification dataset {(xi , yi )}m
i=1 ⊆ R × {±1}, a
p
parameterized model f (x; θ) for parameters θ ∈ R , and a log-concave, exponentially tailed loss of the form:

L(θ) =

m
X

ℓ (yi f (xi ; θ)) =

i=1

m
X

e−φ(yi f (xi ;θ)) ,

(1)

i=1

where φ is twice continuously differentiable, strictly monotone increasing and convex, with bounded first
and second derivatives (see Appendix C.1), notably allowing for the exponential (ℓ(u) = e−u ) and logistic
(ℓ(u) = log(1 + e−u )) losses. We denote for brevity zi (θ) = yi f (xi ; θ) and qmin (θ) = mini∈[m] zi (θ). For a
t
trajectory θt we often write zit = zi (θt ), qmin
= qmin (θt ) or zi , qmin when t is clear from context.
n
For a vector v ∈ R we denote by v[j] the j’th coordinate of v. For n ∈ N, we denote [n] = {1, . . . , n}.
We denote by ∥·∥p the ℓp norm for p ∈ [1, ∞]. For an arbitrary norm ∥·∥ we denote by ∥·∥⋆ the dual norm,
defined by ∥x∥⋆ = max∥u∥=1 ⟨u, x⟩. We denote by ∥W ∥sp the standard spectral norm of a matrix W , and
∥(W1 , ..., WK )∥msp := maxk∈[K] ∥Wk ∥sp (short for max-spectral). We use the standard asymptotic notations
O, Ω, Θ, o, ω. We denote by C k (X) for X ⊆ Rn , n ∈ N the class of k-times continuously differentiable
functions from X to R. By log u we refer to the natural logarithm. By ess lim, ess liminf, ess limsup we refer
to essential limits holding up to sets of measure 0.

2.2

Optimizers

The optimization algorithms we study are derivatives of the steepest descent family, a generalization of
gradient descent defined with respect to a norm ∥·∥ (and its dual norm ∥·∥⋆ ). We study the infinitesimal step
size (flow) limit of the optimization trajectories. We define steepest descent and its normalized variant in the
general case of a subdifferentiable model f , allowing for a learning rate schedule η(t) > 0, as follows:
Steepest Descent:


dθt
∈ η(t) · arg min ⟨u, gt ⟩ | gt ∈ ∂L(θt ) ,
(2)
dt
∥u∥=∥gt ∥⋆
Normalized Steepest Descent:
dθt
∈
dt




η(t) · arg min ⟨u, gt ⟩ | gt ∈ ∂L(θt )
∥u∥=1

,

(3)

for almost every t ≥ 0, where ∂L is the Clarke subdifferential of L (see Appendix A), which reduces
to ∇L wherever f is differentiable. Notably, gradient descent and coordinate descent are recovered with
∥·∥ = ∥·∥2 , ∥·∥1 respectively from Equation 2, and sign gradient descent is recovered with ∥·∥ = ∥·∥∞ from
Equation 3.
Introducing momentum-based optimizers, we consider a choice of subgradients gt ∈ ∂L(θt ) along the
trajectory, and denote the momentum estimate by the following ODE with the given explicit solution:
dmt
= c1 (gt − mt ), m0 = 0
dt


Z t
−c1 (t−s)
Explicitly: mt =
c1 e
gs ds .

(4)

0

For the full derivation of the above continuous analogue of momentum, see Appendix B. Here, c1 > 0
is the momentum smoothing parameter, and c11 is the characteristic time frame in which past gradients are
accumulated (c1 is analogous to − log(β1 ) for a discrete momentum parameter β1 ∈ (0, 1), and is roughly
1 − β1 when β1 is close to 1). We now define momentum steepest descent and its normalized counterpart:

3

Momentum Steepest Descent:
dθt
∈
dt




η(t) · arg

min

∥u∥=∥mt ∥⋆

⟨u, mt ⟩

,

Normalized Momentum Steepest Descent:


dθt
∈ η(t) · arg min ⟨u, mt ⟩ .
dt
∥u∥=1

(5)

(6)

Classical gradient descent with momentum, for example, is obtained from Equation (5) with ∥·∥ = ∥·∥2 .
Muon, the recently proposed weight-matrix optimizer (Jordan et al., 2024), applies Newton-Schulz
orthogonalization iterations on a momentum estimate of the matrix. In our work (as in Fan et al. (2025)),
Muon refers to the exact orthogonalization setting rather than the Netwon-Schulz approximation (i.e.,
U ΣV T 7→ U V T where U ΣV T is the SVD of the weight matrix W ). Muon with exact orthogonalization is
recovered from Equation 6 with ∥·∥ = ∥·∥sp for a single-layer network. When running Muon simultaneously
on each weight matrix of a multi-layer network, the resulting trajectory follows Equation 6 with ∥·∥ = ∥·∥msp
(see notations in Subsection 2.1). Bernstein and Newhouse (2024) noted that Shampoo with accumulation
disabled is, too, spectral descent, although accumulation in Shampoo is not identical to momentum. Another
algorithm adhering exactly to Equation (6) is Signum (Bernstein et al., 2018), i.e. momentum sign gradient
descent (∥·∥ = ∥·∥∞ ).
The final optimizer we discuss is Adam, for which we define similarly to the above
dvt
= c2 (gt2 − vt ), v0 = 0
dt


Z t
−c2 (t−s) 2
Explicitly: vt =
c2 e
gs ds ,

(7)

0

where the square is taken element-wise. Following Zhang et al. (2024); Fan et al. (2025); Baek et al. (2025);
Xie and Li (2024), we consider Adam without the stability constant, as this setting more accurately reflects
the behavior of Adam in practice, where the stability constant is typically negligible throughout the trajectory.
Therefore we define Adam as the following:
Adam:

dθt
m̂t
= −η(t) · √ ,
dt
v̂t

(8)

where m̂t = (1 − e−c1 t )−1 mt and v̂t = (1 − e−c2 t )−1 vt are bias-corrected terms, and division and square
root are taken element-wise. Adam in the discrete case (Kingma and Ba (2015)) is defined using parameters
β1 , β2 ∈ [0, 1), where β1 ≤ β2 (see definition for the discrete case in Appendix B).1 Due to the inverse relation
between βi and ci , this is analogous to c1 ≥ c2 , which is the setting we focus on.

2.3

Assumptions

We now introduce the assumptions made in this work. Note that some assumptions overlap, and not all
assumptions are used in all sections of the work.
Model Assumptions.

Our main contributions include the following assumptions on f :

(M1) f is smooth in θ, i.e. ∀x ∈ Rd : f (x; ·) ∈ C 1 (Rp ).
(M2) f is L-homogeneous for some L ≥ 1, i.e. ∀x ∈ Rd , θ ∈ Rp , α > 0 : f (x; αθ) = αL f (x; θ).
1 Pytorch (Paszke et al., 2019) defaults are β

1 = 0.9, β2 = 0.999.

4

This includes (deep) linear networks, for which implicit bias has been extensively studied (e.g., Ji and
Telgarsky (2018); Gunasekar et al. (2018b); Yun et al. (2020); Moroshko et al. (2020)), but notably also
models with smooth non-linear activations such as assumed in Chizat and Bach (2020). One example for an
activation function that induces non-linear smooth homogeneous networks is ReLUq (z) := max{0, z}q , for
any constant q > 1 (networks with this activation function have been studied in, e.g., Cao et al. (2022); Min
and Vidal (2024, 2025); Chizat and Bach (2020)). Another example for a smooth homogeneous activation
is the quadratic activation z 7→ z 2 , which has been studied in many prior works (e.g., Soltanolkotabi et al.
(2018); Du and Lee (2018); Gamarnik et al. (2019); Sarao Mannelli et al. (2020); Mohamadi et al. (2024);
Martin et al. (2024); Arous et al. (2025); Martin et al. (2026)).
The results for normalized steepest descent have weaker model assumptions:
(M1-Weak) f is locally Lipschitz and Whitney C 1 -stratifiable (thereby admitting a chain rule), see Appendix A.
(M2-Weak) f is L-homogeneous for some L > 0.
In fact, all of our results allow Assumption (M1) to be weakened to (M1-Weak), under a stabilization
condition on the trajectory – see Section 4. Notably, networks with ReLU activations satisfy (M1-Weak) but
not (M1).
Learning Rate Assumptions. We detail the different sets of assumptions on the learning rate schedule
η(t), according to the setting (normalized steepest descent, momentum steepest descent and Adam).
R∞
(LR-NSD) η(t) satisfies 0 η(t)dt = ∞.
 1 
R∞
(LR-MSD) η(t) satisfies 0 η(t)dt = ∞ and η(t) ≤ o t L −1 , where L ≥ 1 is from (M2).
(LR-Adam) η(t) satisfies
increasing.

R∞
0

 1 
η(t)dt = ∞ and η(t) ≤ o t L −1 , where L ≥ 1 is from (M2), and is non-

We note that existing works on Adam and momentum steepest descent in linearP
models (Zhang et al., 2024;
∞
Fan et al., 2025; Baek et al., 2025) assumed a non-increasing learning rate ηt with t=1 ηt = ∞ and ηt = o (1),
as well as additional technical assumptions; our Assumption (LR-Adam) in the linear predictor case (L = 1)
is somewhat weaker than theirs.
Realizability and Trajectory Assumptions. For normalized steepest descent, we assume as in Lyu
and Li (2019); Tsilivis et al. (2025) and others,
(R1) There exists t0 ≥ 0 with L(θt0 ) < ℓ(0).
Assumption (R1) is not assumed in the momentum steepest descent and Adam results; instead we assume
the following:
(T1) Nontrivial trajectory: ∃Nmin > 0, t0 ≥ 0 : ∀t ≥ t0 : ∥θt ∥ ≥ Nmin .
(T2) Directional Convergence: ∥θθtt ∥ converges to some θ̄ with a positive margin γ(θ̄) > 0.
Assumption (T1) guarantees only that θt is eventually bounded away from the origin. In particular this
assumption holds if eventually L(θt ) < m · ℓ(0) − δ for some δ > 0. This is therefore a very mild assumption.
(T1) follows from (R1) when analyzing (normalized) steepest descent, since the loss is proved to decay once
L(θt ) < ℓ(0); momentum steepest descent and Adam, however, only asymptotically approximate steepest
descent, and such a decay is only proved for them in this work under Assumptions (T1) and (T2).
Regarding (T2), we note that the directional convergence assumption can be found in the implicit bias
literature of linear and homogeneous networks (see, for instance, Gunasekar et al. (2018a,b); Chizat and Bach
5

(2020); Nacson et al. (2019b)). The assumption of a strictly positive margin, which also implies realizability,
can also be found in Gunasekar et al. (2018b); Nacson et al. (2019b). We remark that Ji and Telgarsky
(2020) showed that directional convergence in homogeneous models definable in an o-minimal structure is
guaranteed under gradient descent. However, no such result is known for other optimizers, and we found (T2)
to be crucial, as opposed to arguing about arbitrary limit points of ∥θθtt ∥ (as in Lyu and Li (2019) and Tsilivis
et al. (2025)), due to the inherent history-preserving nature of momentum-based optimizers.
Adam Well-Definability Assumption. To discuss Adam without the stability constant and guarantee
that vt [j] > 0 for all j ∈ [p], which is required to prevent division by zero, we introduce the following technical
assumption regarding the initialization. This assumption appears in similar form also in Zhang et al. (2024)
and Fan et al. (2025), while Baek et al. (2025) assume nonzero coordinates of the input in the iterative
batching regime, leading to a similar conclusion.
(A1) There exist τ > 0, ρ > 0 such that for all j ∈ [p] and for almost any t ∈ [0, τ ], we have gt [j]2 > ρ. These
τ and ρ may be arbitrarily small.

2.4

Margin Maximization and KKT Conditions

An important notion when discussing implicit bias is that of the (hard) margin, defined for homogeneous
models with respect to a norm ∥·∥ by


θ
γ(θ) = min yi f xi ;
.
(9)
∥θ∥
i∈[m]
Under Assumption (T2), γ(θt ) converges to γ(θ̄). We also consider the following soft margin


1
φ−1 log L(θ)
γ
e(θ) =
,
L
∥θ∥
as a convenient substitute for γ(θ). The soft margin approximates the hard margin with a O

(10)


log m
∥θ∥L



error

that vanishes whenever ∥θ∥ → ∞ (as is indeed proved in all of our results). The examination of quantities
relating to γ
e prove important in the analysis.
Our results pertain to the following objective, known as margin maximization, which is not directly
optimized by any of the aforementioned algorithms:
min

1

θ∈Rp 2

2

∥θ∥

s.t.

∀i ∈ [m] : yi f (xi ; θ) ≥ 1 .

(11)

Minimizing the norm ∥θ∥ while preserving feasibility (∀i ∈ [m] : yi f (xi ; θ) ≥ 1) is known to be equivalent to
maximizing the margin γ(θ). For general homogeneous models, Problem (11) is non-convex, and the implicit
bias of algorithms towards minimizing it is shown in light of the KKT (Karush-Kuhn-Tucker) conditions,
which are local stationarity conditions:
Definition 2.1. A point θ ∈ Rp with yi f (xi ; θ) ≥ 1 for all i ∈ [m] is said to satisfy the KKT conditions of
2
Problem (11) if there exist k ∈ ∂ 12 ∥θ∥ , coefficients λ1 , ..., λm ≥ 0 and subgradients hi ∈ ∂f (xi ; θ) with:
Pm
1.
i=1 λi yi hi − k = 0;
Pm
2.
i=1 λi (yi f (xi ; θ) − 1) = 0.

3

Results

In this section, we present our main results. We will discuss the proof ideas in Section 5, with all formal
proofs deferred to the appendix.
6

3.1

Normalized Steepest Descent with a LR Schedule

Our first result, assuming only (M1-Weak), (M2-Weak), (R1), (LR-NSD), extends the analysis of Tsilivis et al.
(2025) to the setting of normalized steepest descent with a learning rate schedule. We present this result
both as inherently valuable (for instance, it implies implicit bias of sign gradient descent) and as providing
motivation for the following sections on normalized momentum-based optimizers, which we show approximate
normalized Rsteepest descent. It is worth noting that there are no restrictions on the learning rate schedule
∞
η(t) except 0 η = ∞.
The following theorem, following Lyu and Li (2019); Tsilivis et al. (2025), shows that once the loss
decreases below the interpolation threshold ℓ(0), normalized steepest descent guarantees a monotone increase
of the soft margin γ
e(θt ).
Theorem 3.1. Let θt be a trajectory of normalized steepest descent with respect to a norm ∥·∥ (Equation (3)).
Under Assumptions (M1-Weak), (M2-Weak), (R1), (LR-NSD), the soft margin γ
e(θt ) is non-decreasing on
[t0 , ∞).
Next, we prove that any limit point of ∥θθtt ∥ is a KKT-point of the appropriate max-margin problem.
Theorem 3.2. Let θt be a trajectory of normalized steepest descent with respect to a norm ∥·∥ (Equation (3)).
Under Assumptions (M1-Weak), (M2-Weak), (R1), (LR-NSD), any limit point θ̄ of ∥θθtt ∥ is the direction of a
KKT point of Problem (11) with the same norm ∥·∥.

3.2

Momentum Steepest Descent, Muon and Muon-Signum

We now consider margin maximization in momentum steepest descent. The following result is based on the
general insight that convergence of ∥θθtt ∥ to a KKT point of Problem (11) holds even when the trajectory is
only an approximation of steepest descent. We elaborate on the appropriate definition and characteristics of
approximate steepest descent in Section 5 and Appendix C.4.
Theorem 3.3. Let θt be a trajectory of normalized or unnormalized momentum steepest descent with respect
to a norm ∥·∥ (Equation (6) or (5)). Under Assumptions (M1), (M2), (LR-MSD), (T1), (T2), the limit
point θ̄ of ∥θθtt ∥ is the direction of a KKT point of Problem (11) with the norm ∥·∥.
Moreover, we show that running multiple normalized (momentum) steepest descent algorithms in parallel
on different parts of the parameter vector with respect to different norms is equivalent to a single run
of normalized (momentum) steepest descent algorithm relative to the maximal norm among them (see
Appendix C.6). As a result we obtain the following corollary on the implicit bias of Muon:
Corollary 3.4. If θ = (W1 , ..., WK ) is a collection of matrices and Muon is run on each matrix simultaneously
with the same schedule η(t), then Muon is a case of normalized momentum steepest descent with ∥·∥ = ∥·∥msp ,
and the statement of Theorem 3.3 holds.
When running Muon in practice, often the non-matrix parameters are optimized using Adam (Jordan
et al. (2024), Liu et al. (2025)). Adam has been compared to sign gradient descent and Signum (see Orvieto
and Gower (2025)) as possible simplifications. Recently, Scion (Pethick et al., 2025) has been proposed,
which uses Muon side-by-side with sign gradient descent. This motivates understanding the implicit bias of
these “composite” algorithms, to which we contribute the following corollary regarding Muon-Signum, and a
theorem for Muon-Adam in Subsection 3.3.
Corollary 3.5. If θ = (W1 , ..., WK , u) is a collection of matrices and additional parameters u, Muon is
run on each matrix independently and Signum is run on u with the same schedule η(t), then Muon-Signum
is a case of normalized momentum steepest descent with ∥θ∥ = max{∥(W1 , ..., WK )∥msp , ∥u∥∞ }, and the
statement of Theorem 3.3 holds.

7

3.3

Adam and Muon-Adam

Notably, Adam is not a normalized momentum steepest descent algorithm, as its updates are ratio terms
of two momentum estimates of different rates. This makes the case of Adam (and hence also Muon-Adam)
especially challenging. Yet, we show that results of the same flavor hold for Adam in the decaying learning
rate regime. As discussed after Equation (8), we focus on the parameter regime c1 ≥ c2 > 0, which is the one
more common in practice, as this is equivalent to β1 ≤ β2 . Here, we will require that η(t) is non-increasing;
we stress that η(t) is chosen externally to the algorithm, and in all practical cases of a decaying learning rate,
η(t) is chosen to be eventually monotonically decreasing.
Theorem 3.6. Let θt be a trajectory of Adam with c1 ≥ c2 (Equation (8)). Under Assumptions (M1), (M2),
(LR-Adam), (T1), (T2), (A1), the limit point θ̄ of ∥θθtt ∥ is the direction of a KKT point of Problem (11) with
∥·∥ = ∥·∥∞ .
Next, we consider Muon-Adam. Here, we allow for different momentum parameters and different base
learning rates for the Muon and Adam algorithms,2 and show the following:
Theorem 3.7. Assume θ = (W1 , ..., WK , u) ∈ Rp is a parameter vector representing a collection of matrices
and additional parameters u. Assume W1 , ..., WK follow a trajectory of Muon and u follows a trajectory of
Adam, with respective learning rates of the form η0M η(t), η0A η(t) for η0M , η0A > 0 and momentum parameters
cM for Muon and c1 ≥ c2 for Adam. Assume (M1), (M2), (LR-Adam), (T1), (T2), (A1). Then, the limit
point θ̄ of ∥θθtt ∥ is the direction of a KKT point of Problem (11) with respect to

∥θ∥ = max

4

η0A
∥(W1 , ..., WK )∥msp , ∥u∥∞
η0M


.

Non-Smooth Models

Our results for momentum steepest descent and Adam are stated under the assumption of smooth models
(M1). However, as our proofs (Appendix C.5, C.7) show, this may be weakened to (M1-Weak), if the
normalized modelP
subgradients converge. More specifically, denote for all t subgradients h(xi ; θt ) ∈ ∂f (xi ; θt )
m
for which gt = − i=1 ℓ (zit ) φ′ (zit )yi h(xi ; θt ). The condition is:
h(xi ;θt )
(T3) ∀i ∈ [m] : ∥θ
converges.
∥L−1
t

Note first that this condition is trivially satisfied for smooth models under (T2): by Theorem B.2(a) in Lyu
h(xi ;θt )
and Li (2019), it holds that ∥θ
∈ ∂f (xi ; ∥θθtt ∥ ). Therefore, for smooth models, i.e., f ∈ C 1 , convergence
∥L−1
t

h(xi ;θt )
is guaranteed from convergence of ∥θθtt ∥ by continuity of ∇f (xi ; θt ).
of ∥θ
∥L−1
t

h(xi ;θt )
For non-smooth models under (M1-Weak), ∥θ
converges whenever ∥θθtt ∥ eventually stays in the same
∥L−1
t

C 1 stratum of f (xi ; ·) (if ∥θθtt ∥ is exactly on a stratum boundary, h can be chosen to conform to any of the
bordering strata; the choice of h should be continuous to ensure convergence). In particular, under (T2),
this holds whenever the limiting direction θ̄ is an inner point of a stratum. In homogeneous ReLU networks,
stratum boundaries are the parameters θt for which a neuron preactivation is exactly 0. Therefore, when
using a consistent choice of ReLU subgradient at 0 (which is always the case in practice), (T3) follows from
(T2) for every trajectory in which signs of neuron preactivations eventually stabilize. It is unclear whether
this is satisfied in practice or under what conditions; it appears to be violated in our experiments on two-layer
ReLU networks with the MNIST dataset, but we leave open the possibility that some settings comply with
this condition.
2 The same generalization can be applied to Muon-Signum, and indeed for the distinct matrices in Muon, in Corollaries 3.5, 3.4.

8

5

Main Proof Ideas

The proofs of Theorems 3.1 and 3.2 follow similar arguments to Tsilivis et al. (2025); hence we skip a detailed
Rt
description. Of note is the explicit characterization of the rates of ∥θt ∥ and φ−1 (− log L(θt )) as 0 η and
R L
t
γ∞ · 0 η
respectively (where γ∞ is the asymptotic margin), lacking in the unnormalized analysis of
Tsilivis et al. (2025) (see Lemma C.10 for details). Also, as noted by Tsilivis et al. (2025) and Ji and Telgarsky
(2020), KKT stationarity of limit points of ∥θθtt ∥ is closely related to alignment of parameters and gradients
D
E
gt
θt
∥θt ∥ , − ∥gt ∥⋆ . We extract this insight into a general blueprint that serves us to prove implicit bias results
on homogeneous models; namely, Theorem C.8 states that regardless of the optimization algorithm, any
n→∞
limit point θ̄ of ∥θθtt ∥ with γ(θ̄) > 0 is guaranteed to be a KKT point of Problem (11), if L(θtn ) −→ 0 and
E
D
n→∞
n→∞
θ
θtn
g tn
−→ 1 on a subsequence tn for which ∥θttn ∥ −→ θ̄.
∥θt ∥ , − ∥gt ∥
n

5.1

n

n

⋆

Approximate Steepest Descent

Our main technical contribution is the extension of the KKT stationarity results to approximate steepest
descent algorithms and specifically momentum-based algorithms, which we describe here. Steepest descent
(normalized or unnormalized) with respect to a norm ∥·∥ may be described succinctly with the following
equation for almost any t ≥ 0:
*
+
dθt
gt
dt
,−
=1.
(12)
dθt
∥gt ∥⋆
dt
Equation (12) is the linchpin of analyses of steepest descent, as it allows to prove eventual alignment of
the (negative) gradients with the parameters themselves. When analyzing momentum-based algorithms,
Equation (12) will not be exactly satisfied, but the hope is that a similar relation will hold asymptotically.
Hence we define:
Definition 5.1 (Approximate Steepest Descent). We say that an arc θt is a trajectory of Approximate
Steepest Descent with respect to ∥·∥ if there exist ν(t) > 0, Rmax > 0 with:
Rt
1. limt→∞ N (t) := limt→∞ 0 ν = ∞;
∥θt ∥
2. lim supt→∞ N
(t) ≤ Rmax ;

3. ess liminf t→∞ r(t) ≥ 1, where
a.e.

r(t) =


sup
gt ∈∂L(θt )

gt
1 dθt
,−
ν(t) dt
∥gt ∥⋆


.

The quantity ν(t) can be chosen in a flexible manner; for momentum steepest descent (and indeed exact
t
steepest descent) ν(t) = dθ
is chosen, but for Adam we choose ν(t) = η(t) (the learning rate). Lemma C.15
dt
shows that the properties in Definition 5.1, taken together with a positive lower bound on the margin, suffice
t→∞
t→∞
to prove that L(θt ) −→ 0, ∥θt ∥ −→ ∞. Building on this result and on Theorem C.8, in Theorem C.17 we
prove that under (T2) and provided that Rmax ≤ 1, the limiting direction θ̄ is a KKT point of Problem (11).

5.2

Asymptotic Momentum-Gradient Relations

Our results for momentum steepest descent (MSD) and Adam rely on the analysis of Approximate Steepest
Descent. To show that MSD and Adam indeed satisfy Definition 5.1, we analyze the properties of the
momentum operator in Appendix B.
In particular, Corollary B.8 offers a key insight, namely that the ratio m(t)
g(t) for a real-valued function g(t)
g
and its momentum estimator m(t) tends to a well-defined limit whenever d log
converges. This is applied in
dt

9

Lemma C.19, which demonstrates, that in our setting of optimization trajectories, when

 1 
≤ o t L −1 , it

dθt
dt

holds that mt [j] = gt [j] (1 ± o (1)) for any coordinate j ∈ [p] which
n is momentarilyoof “significant” magnitude
at time t. This is formalized by observing the set Jε (t) =

t [j]|
j ∈ [p] | |g
∥gt ∥ > ε

for an arbitrary ε > 0.

⋆

t→∞
mt
Lemma C.19 also shows that ∥m
− ∥ggtt∥ −→ 0, which allows proving that MSD is indeed an Approximate
t ∥⋆
⋆

Steepest Descent algorithm.
In the analysis of Adam, Lemma C.19 is again vital, as it implies that √m̂v̂t [j]
= sign (gt [j]) (1 ± o (1))
t [j]
whenever gt [j] is momentarily significant (as above). The approximation of Adam to sign gradient descent is
in fact the essence of showing ℓ∞ margin maximization, as sign gradient
steepest descent

 descent is normalized
dθt
dt
dθt
dt
∞

t→∞

−→ 1. Instead, we
, − ∥ggtt∥
1
∥ ∥
rely on the flexibility of Definition 5.1, choosing ν(t) = η(t). We adapt to our setting an important result
proved by Zhang et al. (2024) in the discrete case for linear models, which shows that even if momentarily
m̂t [j]
√
> 1, the opposite holds on average. Namely, we prove in Lemma B.10 that for any j ∈ [p]

with ∥·∥ = ∥·∥∞ . However, it is not necessarily true for Adam that

v̂t [j]

Rt
0

|θt [j]|
lim sup R t
= lim sup
t→∞
t→∞
η
0

m̂s [j]
η(s) √
ds
v̂s [j]
≤1,
Rt
η
0

allowing us to choose Rmax ≤ 1 for Definition 5.1 and finish the proof.

Experiments
10 1

103

Margin

10 3
2 Margin

100

104

10 2
10 4
10 5
10 6
10 7
103

GD
Signum
Muon
Adam
101 10 1 10 3 10 5 10 7

102
101
100

Cosine Similarity

10 1

msp Margin

6

10 2
10 3
10 4
10 5

10 1

10 6

10 2
103 101 10 1 10 3 10 5 10 7

103 101 10 1 10 3 10 5 10 7

Loss

(a)

1.025
1.000
0.975
0.950
0.925
0.900
0.875
0.850
0.825
0.800

0.00

0.25

0.50

0.75

Normalized Step

1.00

(b)

Figure 1: (a) Margin values vs. loss for different optimizers. A lighter/darker color signifies the squared-ReLU
/ ReLU activations respectively. Dotted lines represent optimizers with momentum disabled. Lines are mean
values over
D 10 random
E seeds, while filled areas are 95% confidence intervals. (b) Cosine similarity to last
iterate

θlast
θt
∥θt ∥2 , ∥θlast ∥2

, plotted on a normalized linear time scale.

To validate our findings we train two-layer (one hidden layer) homogeneous networks to classify m = 2048
MNIST digits (LeCun et al., 2002) as even or odd, using the exponential loss. Since our results hold for
smooth activations, we use squared ReLU (i.e., z 7→ max{0, z}2 ), and also run ReLU for empirical comparison.
We compare the following optimizers: Normalized Gradient Descent (NGD) with and without momentum,
Signum, Adam, Muon (treating the output layer as a matrix with a single row) and Muon-Adam. Training
proceeds until the loss reaches a small target value (10−8 ). The stability constant for Adam is chosen to
−0.8
be negligible with respect to gradient norm values (ε = 10−20 ). A decaying learning
is

 rate η(t) = η0 t
−1/2
−0.8
chosen to comply with Assumptions (LR-MSD) and (LR-Adam) (as t
=o t
). See Appendix D for
additional details.
Results are shown in Figure 1. As expected, NGD (with and without momentum) maximizes the ℓ2
margin, while Signum and Adam maximize the ℓ∞ margin and Muon maximizes ∥·∥msp . These findings seem
10

to hold empirically for ReLU as well as squared ReLU, although the latter tends to achieve a higher margin
value for ℓ∞ -maximizing algorithms. Signum appears to outperform Adam in terms of ℓ∞ margin, which is
expected considering that the ℓ∞ -margin-maximization properties of Adam may hinge on its similarity to
sign gradient descent, of which Signum is a closer approximation. Also, we observe that NGD is second-best
to Muon when maximizing ∥·∥msp , a phenomenon perhaps explained by the fact that the spectral norm of
the output layer is its ℓ2 norm. In Appendix D (Figure 2) we compare Muon-Adam with Muon and Adam,
and show that it maximizes the appropriate margin.
To test the assumptionDof directionalEconvergence (T2), Figure 1b shows the cosine similarity of the
last
iterates to the last iterate, ∥θθtt∥ , ∥θθlast
∥2 . Note that here the x-axis is a linear time scale normalized with
2
respect to the total training time. We observe, for example, that for all algorithms, alignment is above 0.99 for
the entire second half of the trajectory, suggesting that directional convergence indeed holds. All trajectories
have the margin γ(θt ) bounded away from 0 for the entire late phase of training, validating γ(θ̄) > 0. Also,
Assumption (T1) holds in all experiments.

7

Conclusion

In this work we examined the properties of normalized steepest descent in homogeneous models, as well as
those of the popular momentum-based optimizers Adam and Muon on smooth homogeneous models. The
technical bridge between the two is the unifying perspective of approximate steepest descent, a framework we
believe to be general and widely applicable to first-order optimization methods related to the steepest descent
family. In the case of momentum-based optimizers we crucially show that the momentum mechanism is
asymptotically faithful to the significant gradient coordinates, when the learning rate decays. Our treatment
of Muon and Muon-Signum is only a special case of compositions of normalized momentum steepest descent
algorithms, while results for Adam and Muon-Adam rely directly on the framework of approximate steepest
descent.
Several important questions remain open. First, our results for momentum-based optimizers hold also
for non-smooth models under a strong trajectory Assumption (T3), as discussed in Section 4. It is unclear
whether these algorithms have a provable margin-maximization bias for non-smooth models, notably ReLU
networks, with no such assumptions, or whether Assumption (T3) can be formally proved in certain settings.
Second, our results assume directional convergence of the parameters. For gradient descent, the implicit
bias in homogeneous models was analyzed by Lyu and Li (2019) before Ji and Telgarsky (2020) formally
proved directional convergence; a natural question is whether a directional-convergence guarantee can also
be proved for Adam and Muon. Third, the implicit bias of gradient descent was analyzed also for certain
non-homogeneous models (Nacson et al., 2019a; Kunin et al., 2022; Cai et al., 2025), and it would be
interesting to show such results for other optimizers.
Finally, exploring the theoretical and practical implications of our results is an intriguing research direction.
In which settings can generalization of models be deliberately improved with an informed choice of optimizer?
Are training-data reconstruction attacks based on satisfaction of KKT conditions, as shown in Haim et al.
(2022); Buzaglo et al. (2023); Oz et al. (2024) for gradient descent, also feasible for Adam and Muon? What
are the implications of the implicit bias in these optimizers for adversarial robustness (Vardi et al., 2022; Frei
et al., 2023)? We hope that our results will help advance understanding of the above questions.

Acknowledgments
This work was supported by the Israel Science Foundation (grant No. 2574/25), a research grant from
Mortimer Zuckerman (the Zuckerman STEM Leadership Program), and research grants from the Center for
New Scientists at the Weizmann Institute of Science, and the Shimon and Golde Picker – Weizmann Annual
Grant.

11

References
Arous, G. B., Erdogdu, M. A., Vural, N. M., and Wu, D. (2025). Learning quadratic neural networks in high
dimensions: Sgd dynamics and scaling laws. arXiv preprint arXiv:2508.03688. (Cited on page 5.)
Baek, B., Song, M., and Yun, C. (2025). Implicit bias of per-sample adam on separable data: Departure from
the full-batch regime. arXiv preprint arXiv:2510.26303. (Cited on pages 2, 4, 5, and 6.)
Bernstein, J. and Newhouse, L. (2024).
arXiv:2409.20325. (Cited on page 4.)

Old optimizer, new norm: An anthology.

arXiv preprint

Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., and Anandkumar, A. (2018). signsgd: Compressed
optimisation for non-convex problems. In International conference on machine learning, pages 560–569.
PMLR. (Cited on page 4.)
Buzaglo, G., Haim, N., Yehudai, G., Vardi, G., Oz, Y., Nikankin, Y., and Irani, M. (2023). Deconstructing
data reconstruction: Multiclass, weight decay and general losses. Advances in Neural Information Processing
Systems, 36:51515–51535. (Cited on page 11.)
Cai, Y., Zhou, K., Wu, J., Mei, S., Lindsey, M., and Bartlett, P. L. (2025). Implicit bias of gradient descent
for non-homogeneous deep networks. (Cited on pages 2 and 11.)
Cao, Y., Chen, Z., Belkin, M., and Gu, Q. (2022). Benign overfitting in two-layer convolutional neural
networks. Advances in neural information processing systems, 35:25237–25250. (Cited on page 5.)
Chizat, L. and Bach, F. (2020). Implicit bias of gradient descent for wide two-layer neural networks trained
with the logistic loss. In Conference on learning theory, pages 1305–1338. PMLR. (Cited on pages 2 and 5.)
Clarke, F. H. (1975). Generalized gradients and applications. Transactions of the American Mathematical
Society, 205:247–262. (Cited on page 15.)
Clarke, F. H. (1990). Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics.
(Cited on page 15.)
Davis, D., Drusvyatskiy, D., Kakade, S. M., and Lee, J. D. (2020). Stochastic Subgradient Method Converges
on Tame Functions. Found. Comput. Math., 20(1):119–154. (Cited on pages 15 and 16.)
Du, S. and Lee, J. (2018). On the power of over-parametrization in neural networks with quadratic activation.
In International conference on machine learning, pages 1329–1338. PMLR. (Cited on page 5.)
Fan, C., Schmidt, M., and Thrampoulidis, C. (2025). Implicit bias of spectral descent and muon on multiclass
separable data. arXiv preprint arXiv:2502.04664. (Cited on pages 1, 2, 4, 5, and 6.)
Frei, S., Vardi, G., Bartlett, P., and Srebro, N. (2023). The double-edged sword of implicit bias: Generalization
vs. robustness in relu networks. Advances in neural information processing systems, 36:8885–8897. (Cited
on page 11.)
Gamarnik, D., Kızıldağ, E. C., and Zadik, I. (2019). Stationary points of shallow neural networks with
quadratic activation function. arXiv preprint arXiv:1912.01599. (Cited on page 5.)
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. (2018a). Characterizing implicit bias in terms of optimization
geometry. In International Conference on Machine Learning, pages 1832–1841. PMLR. (Cited on pages 2
and 5.)
Gunasekar, S., Lee, J. D., Soudry, D., and Srebro, N. (2018b). Implicit bias of gradient descent on linear
convolutional networks. Advances in neural information processing systems, 31. (Cited on pages 2, 5,
and 6.)

12

Haim, N., Vardi, G., Yehudai, G., Shamir, O., and Irani, M. (2022). Reconstructing training data from
trained neural networks. Advances in Neural Information Processing Systems, 35:22911–22924. (Cited on
page 11.)
He, K., Zhang, X., Ren, S., and Sun, J. (2015). Delving deep into rectifiers: Surpassing human-level
performance on imagenet classification. In Proceedings of the IEEE international conference on computer
vision, pages 1026–1034. (Cited on page 48.)
Ji, Z. and Telgarsky, M. (2018). Gradient descent aligns the layers of deep linear networks. arXiv preprint
arXiv:1810.02032. (Cited on pages 2 and 5.)
Ji, Z. and Telgarsky, M. (2020). Directional convergence and alignment in deep learning. Advances in Neural
Information Processing Systems, 33:17176–17186. (Cited on pages 2, 6, 9, and 11.)
Jordan, K., Jin, Y., Boza, V., You, J., Cesista, F., Newhouse, L., and Bernstein, J. (2024). Muon: An
optimizer for hidden layers in neural networks. (Cited on pages 1, 4, and 7.)
Kingma, D. P. and Ba, J. (2015). Adam: A Method for Stochastic Optimization. In 3rd International
Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference
Track Proceedings. (Cited on pages 1 and 4.)
Kunin, D., Yamamura, A., Ma, C., and Ganguli, S. (2022). The asymmetric maximum margin bias of
quasi-homogeneous neural networks. arXiv preprint arXiv:2210.03820. (Cited on pages 2 and 11.)
LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. (2002). Gradient-based learning applied to document
recognition. Proceedings of the IEEE, 86(11):2278–2324. (Cited on pages 10 and 48.)
Liu, J., Su, J., Yao, X., Jiang, Z., Lai, G., Du, Y., Qin, Y., Xu, W., Lu, E., Yan, J., Chen, Y., Zheng, H., Liu,
Y., Liu, S., Yin, B., He, W., Zhu, H., Wang, Y., Wang, J., Dong, M., Zhang, Z., Kang, Y., Zhang, H., Xu,
X., Zhang, Y., Wu, Y., Zhou, X., and Yang, Z. (2025). Muon is scalable for llm training. (Cited on page 7.)
Loshchilov, I. and Hutter, F. (2019). Decoupled weight decay regularization. (Cited on page 1.)
Lyu, K. and Li, J. (2019). Gradient descent maximizes the margin of homogeneous neural networks. arXiv
preprint arXiv:1906.05890. (Cited on pages 2, 5, 6, 7, 8, 11, 27, and 28.)
Martin, S., Bach, F., and Biroli, G. (2024). On the impact of overparameterization on the training of a
shallow neural network in high dimensions. In International Conference on Artificial Intelligence and
Statistics, pages 3655–3663. PMLR. (Cited on page 5.)
Martin, S., Biroli, G., and Bach, F. (2026). High-dimensional analysis of gradient flow for extensive-width
quadratic neural networks. arXiv preprint arXiv:2601.10483. (Cited on page 5.)
Min, H. and Vidal, R. (2024). Can implicit bias imply adversarial robustness? arXiv preprint arXiv:2405.15942.
(Cited on page 5.)
Min, H. and Vidal, R. (2025). Gradient flow provably learns robust classifiers for orthonormal gmms. In
Forty-second International Conference on Machine Learning. PMLR. (Cited on page 5.)
Mohamadi, M. A., Li, Z., Wu, L., and Sutherland, D. J. (2024). Why do you grok? a theoretical analysis of
grokking modular addition. arXiv preprint arXiv:2407.12332. (Cited on page 5.)
Moroshko, E., Woodworth, B. E., Gunasekar, S., Lee, J. D., Srebro, N., and Soudry, D. (2020). Implicit
bias in deep linear classification: Initialization scale vs training accuracy. Advances in neural information
processing systems, 33:22182–22193. (Cited on pages 2 and 5.)

13

Nacson, M. S., Gunasekar, S., Lee, J., Srebro, N., and Soudry, D. (2019a). Lexicographic and depth-sensitive
margins in homogeneous and non-homogeneous deep models. In International Conference on Machine
Learning, pages 4683–4692. PMLR. (Cited on pages 2 and 11.)
Nacson, M. S., Lee, J., Gunasekar, S., Savarese, P. H. P., Srebro, N., and Soudry, D. (2019b). Convergence
of gradient descent on separable data. In Chaudhuri, K. and Sugiyama, M., editors, Proceedings of the
Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings
of Machine Learning Research, pages 3420–3428. PMLR. (Cited on page 6.)
Orvieto, A. and Gower, R. M. (2025). In search of adam’s secret sauce. arXiv preprint arXiv:2505.21829.
(Cited on page 7.)
Oz, Y., Yehudai, G., Vardi, G., Antebi, I., Irani, M., and Haim, N. (2024). Reconstructing training data from
real world models trained with transfer learning. arXiv preprint arXiv:2407.15845. (Cited on page 11.)
Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N.,
Antiga, L., et al. (2019). Pytorch: An imperative style, high-performance deep learning library. Advances
in neural information processing systems, 32. (Cited on page 4.)
Pethick, T., Xie, W., Antonakopoulos, K., Zhu, Z., Silveti-Falls, A., and Cevher, V. (2025). Training deep
learning models with norm-constrained lmos. arXiv preprint arXiv:2502.07529. (Cited on page 7.)
Sarao Mannelli, S., Vanden-Eijnden, E., and Zdeborová, L. (2020). Optimization and generalization of shallow
neural networks with quadratic activation functions. Advances in Neural Information Processing Systems,
33:13445–13455. (Cited on page 5.)
Soltanolkotabi, M., Javanmard, A., and Lee, J. D. (2018). Theoretical insights into the optimization landscape
of over-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742–769.
(Cited on page 5.)
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. (2018). The implicit bias of gradient
descent on separable data. Journal of Machine Learning Research, 19(70):1–57. (Cited on page 2.)
Tsilivis, N., Gronich, E., Kempe, J., and Vardi, G. (2025). Flavors of margin: Implicit bias of steepest descent
in homogeneous neural networks. (Cited on pages 2, 5, 6, 7, 9, 28, and 30.)
Vardi, G. (2023). On the implicit bias in deep-learning algorithms. Communications of the ACM, 66(6):86–93.
(Cited on pages 1 and 2.)
Vardi, G., Yehudai, G., and Shamir, O. (2022). Gradient methods provably converge to non-robust networks.
Advances in Neural Information Processing Systems, 35:20921–20932. (Cited on page 11.)
Wang, B., Meng, Q., Chen, W., and Liu, T.-Y. (2021). The implicit bias for adaptive optimization algorithms
on homogeneous neural networks. In International Conference on Machine Learning, pages 10849–10858.
PMLR. (Cited on pages 2 and 17.)
Xie, S. and Li, Z. (2024). Implicit bias of adamw: ℓ∞ -norm constrained optimization. In International
Conference on Machine Learning, pages 54488–54510. PMLR. (Cited on pages 2 and 4.)
Yun, C., Krishnan, S., and Mobahi, H. (2020). A unifying view on implicit bias in training linear neural
networks. arXiv preprint arXiv:2010.02501. (Cited on pages 2 and 5.)
Zhang, C., Zou, D., and Cao, Y. (2024). The implicit bias of adam on separable data. Advances in Neural
Information Processing Systems, 37:23988–24021. (Cited on pages 1, 2, 4, 5, 6, 10, and 22.)

14

A

Clarke Subgradients and Chain Rule

Our notion of the subgradient of a function f = f (θ) : Rp → R is that of Clarke (1975):


∂f (θ) := conv lim ∇f (θk ) | lim θk = θ, f is differentiable at θk ,
k→∞

(13)

k→∞

where conv(·) is the convex hull of a set (the set of finite convex combinations of points from that set).
The following basic chain rule holds for all locally Lipschitz functions.
Theorem A.1 (Theorem 2.3.9 and 2.3.10 in Clarke (1990)). Let f1 , . . . , fm : Rp → R, L : Rm → R be
locally Lipschitz functions and define f = (f1 , . . . , fm ). Let (L ◦ f )(θ) = L(f1 (θ), . . . , fm (θ)) : Rp → R be the
composition of L with f . Then, it holds:
(m
)
X
∂(L ◦ f )(θ) ⊆ conv
αi hi : α ∈ ∂L(f1 (θ), . . . , fm (θ)), hi ∈ ∂fi (θ) .
(14)
i=1

The following corollary holds for a smooth L, and implies in P
our setting for the loss L(θ) =
m
L(f (x1 ; θ), . . . , f (xm ; θ)) that any g ∈ ∂L(θ) is given as a sum g = i=1 ℓ′ (yi f (xi ; θ))yi hi where ℓ′ is
the derivative of the per-sample loss, and hi ∈ ∂f (xi ; θ).
Corollary A.2 (Chain Rule with an Outer Smooth Function). Let f1 , . . . , fm : Rp → R be locally Lipschitz
and L : Rm → R be C 1 . Then
(m
)
X
∂(L ◦ f )(θ) ⊆
αi hi : α ∈ ∂L(f1 (θ), . . . , fm (θ)), hi ∈ ∂fi (θ) .
(15)
i=1

Proof. Denote
A=

(m
X

)
αi hi : α ∈ ∂L(f1 (θ), . . . , fm (θ)), hi ∈ ∂fi (θ)

.

i=1
(j)

Using Theorem A.1, it suffices to show that convA ⊆ A. P
Indeed, let n ∈ N, α(j) ∈ ∂L(f1 (θ), . . . , fm (θ)), hi ∈
n
∂fi (θ) for i ∈ [m], j ∈ [n] and let λj > 0, j ∈ [n] with j=1 λj = 1. Since L ∈ C 1 , ∂L = {∇L} is unique at
any point, so in fact ∀j ∈ [n] : α(j) = ∇L(f1 (θ), ..., fm (θ)) =: α, and
n
X
j=1

λj

m
X

(j) (j)

αi hi

i=1

Since ∂fi (θ) is convex by definition,

=

n
X
j=1

λj

m
X

(j)

αi hi

i=1

=

m
X
i=1

αi

n
X

(j)

λj hi

.

j=1

(j)
j=1 λj hi ∈ ∂fi (θ), so we are finished.

Pn

We also consider the notion of Whitney-C 1 stratifiability. We refer the reader to Section 5.2 in Davis et al.
(2020) for a technical introduction to the topic. For our purposes, it suffices to know that if f : Rp → R is
Whitney-C 1 stratifiable, its graph is a finite union of C 1 manifolds (implying that (T3) follows from (T2) for
some trajectories), with conditions along the boundaries allowing us to assume that f admits a chain rule.
Definition A.3. θt : [0, ∞) → Rp is an arc if it is absolutely continuous on every compact interval, or
equivalently if there exists θt′ : [0, ∞) → Rp which is Lebesgue integrable on every interval [0, t] so that
Z t
∀t ≥ 0 : θt = θ0 +
θs′ ds .
0
t
In all the trajectories we discuss, θt is defined as an integral over dθ
dt , so θt is an arc.

Theorem A.4 (Chain Rule for Arcs and Stratifiable Functions - Theorem 5.8 in Davis et al. (2020)). If
f : Rp → R is locally Lipschitz and Whitney C 1 -stratifiable, then for any arc θt : [0, ∞) → Rp , almost all
t ≥ 0, and all g ∈ ∂f (θt ), it holds:


df (θt )
dθt
= g,
.
(16)
dt
dt
15

Finally, we also need a chain rule for the norm ∥θt ∥. We may circumvent the requirement that ∥·∥ be
C 1 -stratifiable with the following definition and theorem:
Definition A.5 (Subdifferentially Regular Functions - Definition 5.3 in Davis et al. (2020)). f : Rp → R is
said to be subdifferentially regular if ∀θ ∈ Rp , g ∈ ∂f (θ),
f (θ ′ ) ≥ f (θ) + ⟨g, θ ′ − θ⟩ + o (∥θ ′ − θ∥)

as θ ′ → θ .

In particular, any convex function, including any norm, satisfies the above inequality without an error
term o (∥θ ′ − θ∥) and thus is subdifferentially regular.
Theorem A.6 (Chain Rule for Arcs and Subdifferentially Regular Functions - Lemma 5.4 in Davis et al.
(2020)). If f : Rp → R is locally Lipschitz and subdifferentially regular, then for any arc θt : [0, ∞) → Rp ,
almost all t ≥ 0, and all g ∈ ∂f (θt ), it holds:


df (θt )
dθt
.
(17)
= g,
dt
dt
For reference, the following is a standard characterization of the subdifferential of a norm:
∂ ∥θ∥ = {v ∈ Rp | ⟨v, θ⟩ = ∥θ∥ , ∥v∥⋆ ≤ 1} .

(18)

Note that by definition of the dual norm it holds that ⟨v, θ⟩ ≤ ∥θ∥ ∥v∥⋆ , so in fact when θ ̸= 0, ∥v∥⋆ = 1 for
any v ∈ ∂ ∥θ∥.

B

Momentum (EMA)

B.1

Discrete Momentum

For a parameter β ∈ (0, 1) and a real-valued sequence gn , n ≥ 1, discrete momentum mn is defined as follows:
mn = βmn−1 + (1 − β)gn ,

m0 = 0 ,

(19)

with the explicit solution:
mn = (1 − β)

n
X

β n−k gk .

k=1

We give for reference the definition of Adam in the discrete case for a sequence of subgradients gn , parameters
β1 , β2 ∈ (0, 1), a learning rate ηn and a constant ε ≥ 0 (in our analysis ε = 0). Square, division and square
root are taken elementwise.
Adam (Discrete):
mn = β1 mn−1 + (1 − β1 )gn , m0 = 0
vn = β2 vn−1 + (1 − β2 )gn2 ,
m̂n = (1 − β1n )−1 mn ,
∆θn = −ηn √

B.2

v0 = 0

v̂n = (1 − β2n )−1 vn

m̂n
.
v̂n + ε

Continuous Momentum

Notice that Equation (19) shows that the direction of update of mn is gn − mn−1 :
mn − mn−1 = (1 − β)(gn − mn−1 ) .
The natural analogue for a continuous time variable t and a parameter c > 0 is therefore:
dmt
= c(gt − mt ),
dt
16

m0 = 0 .

(20)

This equation has the following explicit solution, clearly of a similar form to the discrete version:
Z t
mt =
ce−c(t−s) gs ds .
0

This form is identical to (Wang et al., 2021), with the caveat that they assumed c = 1 − β, a form restricting
c to small values (note that taking c → ∞ induces the regime mt = gt ). To clearly uncover the connection
between β and c, assume that a discrete momentum iteration takes a unit time ∆t = 1, and that steps are
small enough so that gs is roughly constant on [t, t + 1]. Then
Z t+1
Z t
Z t+1
mt+1 − mt =
ce−c(t+1−s) gs ds −
ce−c(t−s) gs ds = (e−c − 1)mt +
ce−c(t+1−s) gs ds
0
−c

≈ (e

0
−c

− 1)mt + (1 − e

t

)gt = (1 − e

−c

)(gt − mt ) .

So c is analogous to − log β, hence spanning the entire range (0, ∞). When β is close to 1 we obtain c ≈ (1−β).
In the definition of discrete Adam, a multiplicative factor of (1 − β n )−1 is used to correct the initial bias
accrued when initializing m0 = 0. The continuous analogue for the bias correction is (1 − e−ct )−1 , since for
Rt
small t, mt ≈ g0 0 ce−c(t−s) ds = g0 (1 − e−ct ).
Definition B.1. We denote
F = L∞
loc ([0, ∞)),


G = g : [0, ∞) → R | ∃τ > 0, ρ > 0 : g 2 (t) > ρ a.e. on [0, τ ]

,

where L∞
loc ([0, ∞)) is the space of Lebesgue measurable functions g(t) : [0, ∞) → R so that g(t) is essentially
bounded (bounded except on a measure zero set) on every compact interval [a, b]. We denote also for
convenience
M[a,b] (g) := ess sup |g| .
[a,b]
p
It isRa standard fact that L∞
loc ([0, ∞)) ⊆ Lloc ([0, ∞)) for any p ≥ 1, the latter being the space of functions
p
g with [a,b] |g| < ∞ on every compact interval [a, b]. This allows us to define the momentum expression for
g. The class G encapsulates Assumption (A1), facilitating a discussion of the Adam ratio.

Definition B.2 (Momentum/EMA). Let g(t) ∈ F. For a parameter c > 0 denote the following by
EMA (g, c) (t) or A(g, c)(t) for short:
Z t
EMA (g, c) (t) = A(g, c)(t) :=
ce−c(t−s) g(s)ds .
0

Also denote for convenience:
Z t
I(g, c)(t) =

ecs g(s)ds,

I∞ (g, c) = lim I(g, c)(t) ,
t→∞

0

so A(g, c)(t) = ce

−ct

I(g, c)(t).

We prove a series of useful lemmas about the properties of the EMA.
Lemma B.3 (Momentum ODE). Let g(t) ∈ F and c > 0. Then for almost any t ≥ 0,
dA(g, c)
= c (g(t) − A(g, c)(t)) .
dt
Proof. Since g is Lebesgue integrable, by differentiation rules and the fundamental theorem of calculus we
have
dA(g, c)
dI(g, c)
= −c2 e−ct I(g, c)(t) + ce−ct
= −cA(g, c)(t) + ce−ct ect g(t) = c(g(t) − A(g, c)(t))
dt
dt

17

Lemma B.4 (Uniform Bound on Adam Ratio). Let g(t) ∈ F and c1 > c22 > 0. Then,
p
c1
A(g 2 , c2 )(t) .
|A(g, c1 )(t)| ≤ A(|g| , c1 )(t) ≤ p
c2 (2c1 − c2 )
In particular,
A(|g| , c1 )(t) ≤ O

p

A(g 2 , c2 )(t)



,

and
A(|g| , c1 )(t) ≤

p
A(g 2 , c1 )(t) .

Proof. By the triangle inequality and Cauchy-Schwarz on the inner product space of L2 -integrable functions
on [0, t], we get
Z t
Z t
c2
c2
|A(g, c1 )(t)| ≤
c1 e−c1 (t−s) |g(s)| ds =
c1 e−(c1 − 2 )(t−s) e− 2 (t−s) |g(s)| ds
0

0

Z t

 12 Z t
 12
e−(2c1 −c2 )(t−s) ds
e−c2 (t−s) g 2 (s)ds

0

0

≤ c1


1
1 − e−(2c1 −c2 )t 2
c1 p
2
A (g , c2 ) (t)
≤√
c2
2c1 − c2
p
c1
A (g 2 , c2 ) (t)
≤p
c2 (2c1 − c2 )

Lemma B.5 (Asymptotic Relations). Let c > 0 and 0 ≤ g(t) ∈ F. Assume g is not a.e. 0.
t→∞

1. If I∞ (g, c) < ∞ then A(g,c)(t)
−→ cI∞ (g, c) > 0 and
e−ct
∀F ∈ F , I∞ (F, c) < ∞ :

A(F, c)
I∞ (F, c)
−→
.
A(g, c)
I∞ (g, c)

2. If I∞ (g, c) = ∞ then A(g,c)(t)
→ ∞ and
e−ct
(a)
Rt
∀t0 ≥ 0 :

t0

ce−c(t−s) g(s)ds
A(g, c)(t)


−1 ≤O

e−ct
A(g, c)(t)



t→∞

→ 0.

(b) For any F (t) ∈ F and C > 0, t0 ≥ 0:
(∀t ≥ t0 : F (t) ≤ Cg(t)) ⇒ A(F, c)(t) ≤ CA(g, c)(t)(1 + o (1)) ,
(∀t ≥ t0 : F (t) ≥ Cg(t)) ⇒ A(F, c)(t) ≥ CA(g, c)(t)(1 − o (1)) .
t→∞

(t)
(c) If eventually g(t) > 0, for any F (t) ∈ F with Fg(t)
−→ C ∈ [−∞, ∞] it holds that

A(F, c) t→∞
−→ C .
A(g, c)
3. In both cases (I∞ (g, c) = ∞, I∞ (g, c) < ∞), for any 0 ≤ F (t) ∈ F:
F (t) ≤ O (g(t)) ⇒ A(F, c)(t) ≤ O (A(g, c)(t)) ,
F (t) ≥ Ω(g(t)) ⇒ A(F, c)(t) ≥ Ω(A(g, c)(t)) .

18

Proof.

Rt
1. By definition A(g, c)(t) = ce−ct 0 ecs g(s)ds, so

A(g, c)(t)
= lim cI(g, c)(t) = cI∞ (g, c) .
t→∞
t→∞
e−ct
And for any g, F with I∞ (F, c) < ∞,
lim

A(F, c)(t)
A(F, c)(t) ce−ct
I∞ (F, c)
= lim
=
.
t→∞ A(g, c)(t)
t→∞
ce−ct A(g, c)(t)
I∞ (g, c)
lim

2. (a) Note that since g ≥ 0,
Z t
Z t
−c(t−s)
−c(t−t0 )
−ct
ce
g(s)ds ≤ A(g, c)(t) ≤ M[0,t0 ] (g) · (e
−e )+
ce−c(t−s) g(s)ds .
t0

t0

Since I∞ (g, c) = ∞, in particular A(g, c)(t) > 0 for large enough t. Dividing by A(g, c)(t) we get
R t −c(t−s)
ce
g(s)ds
M[0,t0 ] (g) · (e−c(t−t0 ) − e−ct )
1−
≤ t0
≤1,
A(g, c)(t)
A(g, c)(t)
R t −c(t−s)


ce
g(s)ds
M[0,t0 ] (g) · (e−c(t−t0 ) − e−ct )
e−ct
t0
−1 ≤
=O
= o (1) .
A(g, c)(t)
A(g, c)(t)
A(g, c)(t)
(b) Let C > 0, t0 ≥ 0 with ∀t ≥ t0 : F (t) ≤ Cg(t). Then,
A(F, c)(t) ≤ M[0,t0 ] (F ) · (e

−c(t−t0 )

−e

−ct

Z t
)+C

ce−c(t−s) g(s)ds .

t0

Therefore by item 2(a),


A(F, c)(t) ≤ O e−ct +CA(g, c)(t)(1+o (1)) ≤ o (A(g, c))+CA(g, c)(t)(1+o (1)) = CA(g, c)(t)(1+o (1)) .
The other direction is completely symmetrical.
(c) First address the case C ∈ (0, ∞). Since C > 0, by the previous item,
A(F, c)(t)
t→∞
≤ C(1 + o (1)) −→ C ,
A(g, c)(t)
so
lim sup
t→∞

In the same fashion
lim inf
t→∞

A(F, c)(t)
≤C .
A(g, c)(t)
A(F, c)(t)
≥C ,
A(g, c)(t)
t→∞

showing the limit. If C = 0, then fixing ε > 0, |F |+εg
−→ ε, implying by the previous case
g
A(|F | , c)
A(|F | , c) + εA(g, c)
A(|F | + εg, c) t→∞
+ε=
=
−→ ε ,
A(g, c)
A(g, c)
A(g, c)
and so

A(F, c)
A(|F | , c) t→∞
≤
−→ 0 .
A(g, c)
A(g, c)

For C ∈ (−∞, 0), applying the case C > 0 with −F suffices, since −F
g → −C > 0 and A(−F, c) =
′
−A(F, c). This finishes for a finite C. If C = ∞ then the above shows lim inf t→∞ A(F,c)(t)
A(g,c)(t) ≥ C

for any C ′ > 0, showing lim inf t→∞ A(F,c)(t)
A(g,c)(t) = ∞, and symmetrically for C = −∞.

19

3. If I∞ (g, c) = ∞ then the result follows from item 2(b). Assume I∞ (g, c) < ∞. If F (t) ≤ O (g(t)) then
I∞ (F, c) < ∞, so the result follows from item 1. If F (t) ≥ Ω(g(t)), consider two cases: if I∞ (F, c) < ∞
I(F,c)(t)
then the result again follows from item 1, and if I∞ (F, c) = ∞ then A(F,c)
A(g,c) = I(g,c)(t) → ∞ and in
particular A(F, c) ≥ Ω(A(g, c)).
Corollary B.6. Let c > 0 and g ∈ F.
1. If eventually g(t) ≤ M for some M ∈ R then A(g, c)(t) ≤ M + o (1), and if eventually g(t) ≥ M then
A(g, c)(t) ≥ M − o (1).
2. If limt→∞ g(t) = C ∈ [−∞, ∞] then limt→∞ A(g, c)(t) = C.
Proof. Let M ∈ R, and t0 with ∀t ≥ t0 : g(t) ≤ M . Then
A(g, c)(t) ≤ M[0,t0 ] (g)(e−c(t−t0 ) − e−ct ) + M (1 − e−c(t−t0 ) ) ≤ M + o (1) .
The lower bound is symmetrical.
For the limit, choose h ≡ 1 ∈ F. Clearly I∞ (h, c) = ∞, and A(h, c) = 1 − e−ct . If limt→∞ g(t) =
g(t)
A(g,c)
limt→∞ h(t)
= C then limt→∞ A(h,c)
= C by Lemma B.5, implying limt→∞ A(g, c)(t) = C.
The following lemma gives sufficient conditions for A(g,c)
converging to a constant ratio; see the following
g
corollary for a simpler condition for differentiable functions.
Lemma B.7. Let c > 0 and 0 < g(t) ∈ F . Assume that
−ct

1. limt→∞ eg(t) = 0.
t→∞

−→ eku .
2. There exists k ∈ [0, c) so that for every fixed u > 0, g(t−u)
g(t)
3. There exists M (u) ≥ 0 with
M (u).

R∞
0

ce−cu M (u)du < ∞, and t0 ≥ 0 so that ∀t ≥ t0 , 0 < u < t − t0 : g(t−u)
g(t) ≤

c
Then A(g,c)(t)
→ c−k
.
g(t)

Proof. Denote Ht (u) = 1{u≤t−t0 } · ce−cu g(t−u)
g(t) . For any t ≥ t0 ,
Z t0
Z t
1
g(s)
A(g, c)(t)
−c(t−s)
=
ce
g(s)ds +
ce−c(t−s)
ds =
g(t)
g(t) 0
g(t)
t0
 Z t−t0
M[0,t0 ] (g)  −c(t−t0 )
g(t − u)
≤
e
− e−ct +
ce−cu
du =
g(t)
g(t)
0
 Z ∞
M[0,t0 ] (g)  −c(t−t0 )
e
− e−ct +
Ht (u)du .
=
g(t)
0
And since g(t) > 0, A(g, c)(t) > 0,
A(g, c)(t)
≥
g(t)
−ct

Z t−t0
0

ce−cu

g(t − u)
du =
g(t)

t→∞

Z ∞
Ht (u)du .
0

Recall that by hypothesis eg(t) −→ 0. Also, by hypothesis, Ht (u) ≤ ce−cu M (u) with
t→∞

R∞
0

ce−cu M (u)du < ∞.

Finally note Ht (u) −→ ce−(c−k)u pointwise. Therefore by the dominated convergence theorem on [0, ∞):
Z ∞
Z ∞
Z ∞
A(g, c)(t)
c
lim
= lim
Ht (u)du =
lim Ht (u)du =
ce−(c−k)u du =
t→∞
t→∞ 0
t→∞
g(t)
c
−
k
0
0

20

The following useful corollary is stated for g(t) > 0, but if g(t) < 0 it applies to −g and A(−g, c) = −A(g, c).
′
Therefore for g(t) ̸= 0 with a constant sign, the condition − gg = − d log|g|
→ k implies items 1-3 as written.
dt
Corollary B.8 (Asymptotic Momentum-Function Ratio ). Let c > 0 and 0 < g(t) ∈ F. Assume g(t) is
′
(t)
differentiable almost everywhere, locally absolutely continuous and ess limt→∞ − gg(t)
= ess limt→∞ − d logdtg(t) =
k ∈ [0, ∞). Then:
t→∞

1. If k > c then A(g,c)(t)
−→ cI∞ (g, c) < ∞ and in particular A(g,c)(t)
→ ∞.
e−ct
g(t)
Rt

G t→∞

0
2. If k = c then A(g,c)(t)
= c · G(t)
−→ ∞ for G(t) = ect g(t).
g(t)

t→∞

c
.
3. If k < c then A(g,c)(t)
−→ c−k
g(t)
t→∞

g
Proof. For any k ∈ [0, ∞), if − d log
−→ k then, since g is locally absolutely continuous, we have by
dt
integration on [0, t]
log g(t) = −kt + o(t) ⇒ g(t) = e−kt+o(t)
R ∞ ct
This implies 0 e g(t)dt < ∞, thus the case k > c is simply a reiteration of Lemma B.5 item 1.
t→∞

G
−→ c − c = 0 and:
For the case k = c, denote G(t) = ect g(t), so it holds that d log
dt
Z t
A(g, c)(t) = ce−ct
G(s)ds
0

Rt

G(s)ds
A(g, c)(t)
=c· 0
g(t)
G(t)
We claim this expression tends to ∞. Indeed, for any ε > 0 there exists t0 ≥ 0 with for almost all
G(t)
G
t ≥ t0 : d log
≤ ε(t − s),
≤ ε, hence it holds by integration on any interval [s, t], t ≥ s ≥ t0 that log G(s)
dt
hence G(t) ≤ G(s)eε(t−s) and
Z t
Z t
Z t

G(s)
G(s)
1
t→∞ 1
ds ≥
ds ≥
1 − e−ε(t−t0 ) −→ .
e−ε(t−s) ds =
ε
ε
0 G(t)
t0 G(t)
t0
R t G(s) t→∞
Since ε was arbitrary this proves 0 G(t) ds −→ ∞.
−ct

For the case k < c we use Lemma B.7. First note that eg(t) = e−(c−k)t+o(t) → 0. Also, for any fixed u,
Z t
g(t − u)
d log g(s) t→∞
log
=−
ds −→ ku ,
g(t)
ds
t−u
g(t − u) t→∞ ku
−→ e .
g(t)
log g
And there exists t0 and k < c′ < c for which ∀t ≥ t0 : −ddt
< c′ , so ∀t ≥ t0 , 0 < u < t − t0 :

log

g(t − u)
≤ c′ u ,
g(t)

′
g(t − u)
≤ ec u =: M (u) .
g(t)

With

R∞
0

t→∞

c
ce−cu M (u)du < ∞. Thus the conditions of Lemma B.7 hold, implying A(g,c)(t)
−→ c−k
.
g(t)

Lemma B.9 (Adam Ratio is Bounded at Initialization). Let g(t) ∈ F ∩ G, and let ρ, τ > 0 for which g 2 (t) > ρ
a.e. on [0, τ ]. Denote mt = A(g, c1 )(t), vt = A(g 2 , c2 )(t) for c1 ≥ c2 > 0, and m̂t = (1 − e−c1 t )−1 mt , v̂t =
(1 − e−c2 t )−1 vt . Then √m̂v̂t is bounded on (0, τ ].
t

21

Proof. For any s ∈ (0, τ ] it holds that
Rs
Rs
c e−c1 (s−r) |gr | dr
M[0,τ ] (g) 0 c1 e−c1 (s−r) dr
|ms |
0 1
|m̂s | =
≤
≤
= M[0,τ ] (g) < ∞ .
1 − e−c1 s
1 − e−c1 s
1 − e−c1 s
And that
Rs
Rs
c e−c2 (s−r) g 2 (r)dr
ρ 0 c2 e−c2 (s−r) dr
vs
0 2
=
≥
=ρ>0.
v̂s =
1 − e−c2 s
1 − e−c2 s
1 − e−c2 s
Therefore
M[0,τ ] (g)
m̂s
∀s ∈ (0, τ ] : √
≤
<∞.
√
ρ
v̂s

Lemma B.10 (Adaptation
of Lemma A.4 in Zhang et al. (2024)). Let c1 ≥ c2 > 0 and 0 < η(t) ∈ F
R∞
non-increasing with 0 η(t)dt = ∞. Let gt = g(t) ∈ F ∩ G with g 2 (t) < 1 − δ eventually for some δ > 0.
Denote mt = A(g, c1 )(t), vt = A(g 2 , c2 )(t) for c1 ≥ c2 > 0, and m̂t = (1 − e−c1 t )−1 mt , v̂t = (1 − e−c2 t )−1 vt .
Then
 21 !
Z t
Z t
Z t
m̂s
η(s)ds
η(s)ds + O
.
η(s) √ ds ≤
v̂s
0
0
0
And therefore,
Rt

η(s) √m̂v̂s ds
s
≤ 1 + o(1) .
Rt
η(s)ds
0

0

2
Proof. From the hypothesis g ∈ G let τ > 0, ρ > 0 with g 2 (t) > ρ a.e. on [0, τ ], and choose t0 < min{τ, log
c1 }.
m̂
By Lemma B.9 and since η ∈ F, we have that η(s) √v̂s is bounded on (0, t0 ], so
s
Z t0
m̂s
η(s) √ ds < ∞ .
v̂s
0
√
1−e−c2 s
Thus we focus now on [t0 , t]. Denote q(s) = 1−e−c1 s . By Cauchy-Schwarz,

 12 


Z t

Z t

ms


η(s)q(s) √ ds ≤ 
η(s)q 2 (s)ds
vs
 t0

t0
|
{z
}
⋆

 21

Z t
m2 


η(s) s ds

vs 
 t0
|
{z
}

.

⋆⋆

R∞

Rt

It suffices to show that ⋆, ⋆⋆ are each at most 0 η(s)ds + O (1). Since 0 η(s)ds = ∞, this is equivalent to
Rt
showing that ⋆, ⋆⋆ are each at most ta η(s)ds + O (1) for a fixed ta .
2
1
1
2
−c1 t
For ⋆, using ∀x ∈ [0, 12 ] : (1−x)
for all t ≥ log
2 ≤ 1 + 6x, notice that q (t) ≤ (1−e−c1 t )2 ≤ 1 + 6e
c1 , so
2
for all t ≥ log
c1 it holds that

Z t

2
Z log
c

2

1

η(s)q (s)ds ≤

Z t

2

η(s)q (s)ds +

η(s)ds + 6
log 2
c1

t0

t0

Z t

η(s)e−c1 s ds .

log 2
c1

2
The first term is fixed and finite since η(s)q 2 (s) is bounded on the fixed interval [t0 , log
c1 ]. The third term is
R∞
O (1) since η(t) is bounded, so log 2 η(s)e−c1 s ds converges. This finishes for ⋆.

For ⋆⋆, by Lemma B.4,

c1

m2t = A(g, c1 )2 ≤ A(g 2 , c1 ) ,

22

so
Z t

Z
Z t
m2s
η(s) s
η(s)
c1 e−c1 (s−r) gr2 drds .
ds ≤
vs
t0
0
t0 vs
Rt
It suffices to show that (21) is at most t0 η(s)ds + O (1).
r
By Lemma B.3, gr2 = c12 dv
dr + vr , and integration by parts gives


Z s
Z s
s
c1 −c1 (s−r) dvr
c1
c1 e−c1 (s−r) vr dr
e
dr =
vr e−c1 (s−r) −
dr
c2
0
0
0 c2


Z s
v0 =0 c1
−c1 (s−r)
=
vs −
c1 e
vr dr .
c2
0
So,
Z s

c1 e−c1 (s−r) gr2 dr =

Z s
0

0

(21)



Z s
c1 −c1 (s−r) dvr
c1
c1
c1 e−c1 (s−r) vr dr ,
e
+ c1 e−c1 (s−r) vr dr = vs −
−1
c2
dr
c2
c2
0

and
Z t

Z s
Z
c1 t
vr
c1
η(s)
−1
c1 e−c1 (s−r) drds
η(s)ds −
c2 t0
c2
vs
t0
0

Z t
Z t

Z t
Z s
c1
c1
vr
=
η(s)ds +
−1
−1
η(s)ds −
η(s)
c1 e−c1 (s−r) drds
c2
c2
vs
t0
t0
t0
0
Z t

Z t
Z t
Z s
c1 − c 2
v
r
=
η(s)ds +
η(s)ds −
η(s)
c1 e−c1 (s−r) drds
c2
vs
t0
t0
t0
0
Z t
 

Z t
Z s
c1 − c 2
−c1 (s−r) vr
=
dr ds
η(s)ds +
η(s) 1 −
c1 e
c2
vs
t0
t0
0
Z t

 
Z t
Z s
Z s
c1 − c 2
−c1 s
−c1 (s−r)
−c1 (s−r) vr
=
η(s)ds +
η(s) e
+
c1 e
dr −
c1 e
dr ds
c2
vs
t0
t0
0
0
Z t



Z t
Z t
Z s
c1 − c 2
vr
=
η(s)ds +
η(s)e−c1 s ds +
η(s)
drds .
c1 e−c1 (s−r) 1 −
c2
vs
t0
t0
t0
0
Rt
Since η is bounded, t0 η(s)e−c1 s ds ≤ O (1). Therefore it suffices to show


Z t
Z s
vr
−c1 (s−r)
η(s)
c1 e
1−
drds ≤ O (1)
(22)
vs
t0
0
RHS of (21) =

Indeed, it holds for any positive x, y that 1 − xy ≤ log xy . Applying this and a crucial change of summation
order {t0 ≤ s ≤ t, 0 ≤ r ≤ s} 7→ {t0 ≤ r ≤ t, r ≤ s ≤ t},


Z t
Z s
Z t
Z s
vr
drds ≤
η(s)
c1 e−c1 (s−r) (log vs − log vr ) drds
LHS of (22) ≤
η(s)
c1 e−c1 (s−r) 1 −
v
s
t0
0
t0
0
Z t
Z t
Z s
=
η(s) log vs (1 − e−c1 s )ds −
η(s)
c1 e−c1 (s−r) log vr drds
t0

t0

sum order

Z t

=

0

η(s) log vs (1 − e−c1 s )ds −

t0
r↔s

Z t

=

t0

Z t
log vs

t0



−c1 s

Z t
)−

η(r)c1 e
s

23

η(s)c1 e−c1 (s−r) dsdr

r

Z t

η(s) log vs (1 − e−c1 s )ds −

log vs η(s)(1 − e

=

Z t
log vr

t0

t0

Z t

Z t

η(r)c1 e−c1 (r−s) drds

s
−c1 (r−s)


dr ds .

Since η is non-increasing,
η(s)(1 − e−c1 s ) −

Z t

η(r)c1 e−c1 (r−s) dr ≥ η(s)(1 − e−c1 s ) − η(s)

Z t

c1 e−c1 (r−s) dr

s

s

= η(s)(1 − e−c1 s ) − η(s)(1 − e−c1 (t−s) )


= η(s) e−c1 (t−s) − e−c1 s
≥ −η(s)e−c1 s .
Since eventually gt2 < 1 − δ, there exists t1 with ∀t ≥ t1 : vt ≤ 1 (Corollary B.6), hence log vt ≤ 0. So,


Z t
Z t
Z t
−c1 s
−c1 (r−s)
log vs η(s)(1 − e
)−
η(r)c1 e
dr ds ≤
− log vs η(s)e−c1 s ds .
t1

s

t1

Rt
Since gt ̸= 0 on an initial interval, vt ≥ e−c2 t 0 c2 ec2 s gs2 ds ≥ Ω(e−c2 t ), so there exists C > 0 with
log vt ≥ −c2 t − C, therefore,
Z t
Z ∞
−c1 s
− log vs η(s)e
ds ≤
(c2 s + C)η(s)e−c1 s ds < ∞ .
t1

t1

And since on [t0 , t1 ] the integral is also finite (the integrand is bounded), we are finished showing (22) and
therefore finished altogether.

C

Proof Details

C.1

Losses

In this work we consider log-concave, exponentially-tailed losses. Namely, we consider a loss of the form
L(θ) =

m
X

ℓ(yi f (xi ; θ)) ,

i=1

where ℓ(u) = e−φ(u) , and φ ∈ C 2 (R) with ∃Φ′M , Φ′′M > 0 : ∀u ∈ R : 0 < φ′ (u) ≤ Φ′M , 0 ≤ φ′′ (u) ≤ Φ′′M .
Note that ℓ ∈ (ℓexp , ℓlog ) satisfy this:
ℓexp (u) = e−u = e−φexp (u) ,

ℓlog (u) = log(1 + e−u ) = e−φlog (u) ,

for
φexp (u) = u,

φlog (u) = − log log(1 + e−u ) .

The conditions on φ imply the following:
1. φ is strictly monotone increasing and ℓ is strictly monotone decreasing. Also u 7→ φ′ (u)u is strictly
monotone increasing on [0, ∞):
dφ′ (u)u
= φ′′ (u)u + φ′ (u) ≥ φ′ (u) > 0 .
du
2. For any u0 ∈ R, φ has at least a linear growth rate on [u0 , ∞):
Z u
φ(u) − φ(u0 ) =
φ′ (w)dw ≥ φ′ (u0 )(u − u0 ) .

(23)

u0
u→∞

In particular φ(u) −→ ∞.
3. φ has a strictly monotone increasing inverse φ−1 defined on φ(R). In particular φ−1 is defined on

′
u→∞
1
−1
[φ(0), ∞), φ−1 (u) −→ ∞, and (φ−1 )′ is nonincreasing since φ−1 (u) = φ′ (φ−1
, φ′ are
(u)) and φ
−1 ′
increasing. This implies also that (φ ) is bounded on [φ(0), ∞).
24

4. For any a ∈ R ∪ {±∞}, limu→a ℓ(u) = 0 implies limu→a φ(u) = ∞, implying a = ∞, since φ is bounded
on any compact interval and monotone increasing. Note that since the same is true of φ−1 , this implies
also that if limu→a φ−1 (u) = ∞ then a = ∞.

C.2

Algorithm-Independent KKT Stationarity

In this section we provide general insight into properties of trajectories of homogeneous models, culminating
in Theorem C.8 which shows that KKT stationarity of a limit point of ∥θθtt ∥ with respect to Problem (11)
follows from decay of the loss and alignment between gradients and parameters.
Definition C.1 (Hard and Soft Margins). Let f (x; θ) be a model satisfying (M1-Weak), (M2-Weak). We
denote the “hard” and “soft” margins γ(θ), γ
e(θ) for θ ̸= 0 as follows:


1


φ−1 log L(θ)
θ
γ(θ) := min yi f xi ;
, γ
e(θ) :=
.
L
∥θ∥
i∈[m]
∥θ∥
1
1
Note that γ
e is well defined whenever log L(θ)
∈ φ(R), and in particular whenever log L(θ)
> φ(0).
t
Recall the notations from Subsection 2.1; in particular qmin
= mini∈[m] zit = mini∈[m] yi f (xi ; θt ) =
L
γ(θt ) ∥θt ∥ .

Lemma C.2 (Properties of Any Trajectory ). Let θt be any arc of parameters of a model f (x; θ) assuming
(M1-Weak), (M2-Weak). Then the following hold for any norm ∥·∥:
1. For any t ≥ 0:




t
t
ℓ qmin
≤ L(θt ) ≤ m · ℓ qmin
.
1
2. For any t ≥ 0 with θt ̸= 0 and log L(θ
> φ(0):
t)

γ
e(θt ) ≤ γ(θt ) .
t
For any t ≥ 0 with θt ̸= 0 and φ(qmin
) − log m > φ(0):

γ(θt ) −
t→∞

t
(φ−1 )′ (φ(qmin
) − log m) · log m
L

∥θt ∥
t→∞

≤γ
e(θt ) ,

t→∞

Finally, if L(θt ) −→ 0, then ∥θt ∥ −→ ∞ and |e
γ (θt ) − γ(θt )| −→ 0.
3. For almost any t ≥ 0 with θt ̸= 0:
d ∥θθtt ∥
dt

≤

2

dθt
dt

.

(24)

L(θt ) .

(25)

∥θt ∥

4. There exists M > 0 so that for any t ≥ 0 with θt ̸= 0,
L−1

∥gt ∥⋆ ≤ M ∥θt ∥
Also, for any t ≥ 0,

LL(θt ) · min φ′ (zit )zit ≤ ⟨−gt , θt ⟩ ≤ ∥gt ∥⋆ ∥θt ∥ .
i∈[m]

1
> φ(0) then
If log L(θ
t)
1
φ−1 (log L(θ
)
t)

≤ LL(θt ) · min φ′ (zit )zit ≤ ⟨−gt , θt ⟩ .

(26)

φ′ (q)LL(θt )γ(θt ) ∥θt ∥ ≤ LL(θt ) · min φ′ (zit )zit ≤ ⟨−gt , θt ⟩ .

(27)

LL(θt )

1
)
(φ−1 )′ (log L(θ
t)

i∈[m]

t
If qmin
> q > 0 and θt ̸= 0 then
L

i∈[m]

25

5. If for all large enough t, ∥θt ∥ ≥ Nmin > 0 and γ(θt ) > γmin > 0 then
L−1

∥gt ∥⋆ = Θ(∥θt ∥

L(θt )) = Θ(∥θt ∥

L−1



t
ℓ qmin
).

And in particular ∥gt ∥⋆ is bounded.
Proof.

1. This follows directly from the definition of the loss,
L(θt ) =

m
X

ℓ (yi f (xi ; θt )) ,

i=1
t
noting that qmin
= mini∈[m] yi f (xi ; θt ) by definition, and ℓ is monotone decreasing, giving




t
t
ℓ qmin
≤ L(θt ) ≤ m · ℓ qmin

2. From item 1, when θt ̸= 0,

t
t
1
1 φ(qmin
)
e
≤
≤ eφ(qmin ) ,
m
L(θt )




1
t
t
− log m + φ qmin
≤ log
≤ φ qmin
.
L(θt )

(28)

1
Whenever log L(θ
> φ(0), we may apply φ−1 to the right inequality (recall φ−1 is increasing) and
t)
L

divide by ∥θt ∥ , getting
γ
e(θt ) ≤ γ(θt ) .
t
t
Whenever − log m + φ (qmin
) ∈ φ(R), and in particular whenever − log m + φ (qmin
) > φ(0), we may
−1

also apply φ

to the left inequality of Equation (28):

t
φ−1 (φ (qmin
) − log m)
L

∥θt ∥

≤γ
e(θt ) .

t
t
Applying the mean value theorem, for some u ∈ [φ(qmin
) − log m, φ(qmin
)] it holds that








t
−1
t
−1
t
−1
t
qmin − φ
φ qmin − log m = φ (φ(qmin )) − φ
φ qmin − log m = (φ−1 )′ (u) · (log m) .

And since (φ−1 )′ is monotone decreasing,




t
t
t
qmin
− φ−1 φ qmin
− log m ≤ (φ−1 )′ (φ(qmin
) − log m) · log m .
Altogether
γ(θt ) −

t
(φ−1 )′ (φ(qmin
) − log m) · log m
L

∥θt ∥

t→∞

≤γ
e(θt ) .
L

(29)

t→∞

t
t
Now assume L(θt ) −→ 0. In particular ℓ(qmin
) = ℓ(γ(θt ) ∥θt ∥ ) −→ 0, implying φ(qmin
) =
L t→∞
L t→∞
φ(γ(θt ) ∥θt ∥ ) −→ ∞ and therefore γ(θt ) ∥θt ∥ −→ ∞. In particular this means γ(θt ) > 0 for
t→∞
t→∞
t
all large enough t, and since γ(θt ) is bounded, also ∥θt ∥ −→ ∞. Since φ(qmin
) − log m −→ ∞ we have
t→∞
t→∞
t
Equation (29) for all large enough t. Finally, since φ(qmin
) −→ ∞, ∥θt ∥ −→ ∞ and (φ−1 )′ is bounded
on [φ(0), ∞) it holds that
t→∞
|γ(θt ) − γ
e(θt )| −→ 0 .

3. Let nt ∈ ∂ ∥θt ∥, so by the chain rule for arcs (Theorem A.6), and using ∥nt ∥⋆ ≤ 1 from Equation (18):


d ∥θt ∥
dθt
dθt
dθt
≤ nt ,
≤
∥nt ∥⋆ ≤
.
dt
dt
dt
dt
Therefore
d ∥θθtt ∥
dt

1 dθt
=
+ θt
∥θt ∥ dt

d ∥θt ∥
−
2
dt
∥θt ∥
1

26

!
≤

dθt
dt

∥θt ∥

+

dθt
1 d ∥θt ∥
≤ 2 · dt .
∥θt ∥
dt
∥θt ∥

4. By the chain rule (Corollary A.2), let hti ∈ ∂f (xi ; θt ) with
gt = −

m
X

ℓ(zit )φ′ (zit )yi hti .

i=1

For the upper bound, using Theorem B.2(a) of (Lyu and Li, 2019),
gt = −

m
X

m
X




L−1
ℓ zit φ′ (zit )yi hti = − ∥θt ∥
ℓ zit φ′ (zit )yi h̄ti ,

i=1

i=1

where h̄ti ∈ ∂f (xi ; ∥θθtt ∥ ). On the unit sphere, which is a compact set, f is Lipschitz, hence ∃M ′ > 0 :
h̄ti ⋆ ≤ M ′ for any t. So, using |φ′ (zit )| ≤ Φ′M ,
L−1

∥gt ∥⋆ ≤ M ′ Φ′M ∥θt ∥

L−1

L(θt ) =: M ∥θt ∥

L(θt ) .

For the lower bounds,
*
∥θt ∥ ∥gt ∥⋆ ≥ ⟨θt , −gt ⟩ =

θt ,

m
X

+
ℓ

zit




′

φ (zit )yi hti

i=1

=

m
X



ℓ zit φ′ (zit )yi θt , hti

i=1
m
X

=L



ℓ zit φ′ (zit )zit .

i=1

Where the last equality uses Theorem B.2 from (Lyu and Li, 2019) (Euler’s Theorem for homogeneous
functions). Continuing, we use that fact that u 7→ φ′ (u)u is increasing on [0, ∞), that log L1 > φ(0),
t
that zit ≥ qmin
≥ φ−1 (log L1 ) by previous items, and finally that φ′ (φ−1 (u)) = (φ−11)′ (u) . Altogether,
φ−1 (log 1 )

this gives φ′ (zit )zit ≥ φ′ (φ−1 (log L1 )) · φ−1 (log L1 ) = (φ−1 )′ (logL 1 ) , so we continue with
L

′

≥ LL min φ (zit )zit
i∈[m]
≥ LL

φ−1 (log L1 )
.
(φ−1 )′ (log L1 )
L

t
Also note that if qmin (θt ) > q > 0 then ∀i ∈ [m] : φ′ (zit ) ≥ φ′ (q) > 0, and recall zit ≥ qmin
= γ(θt ) ∥θt ∥ ,
so
L
φ′ (q)LL(θt )γ(θt ) ∥θt ∥ ≤ LL min φ′ (zit )zit ≤ ⟨−gt , θt ⟩ ,
i∈[m]

finishing the lower bounds.
t
L
5. Note that qmin
≥ Nmin
γmin =: q > 0, so we use Equations (25), (27) to conclude
L−1

φ′ (q)γmin LL(θt ) ∥θt ∥

L−1

≤ ∥gt ∥⋆ ≤ M ∥θt ∥

L(θt ) .

We claim the RHS is bounded. Since it is strictly positive, so we show that its logarithm is bounded
L
from above. Indeed, L(θt ) ≤ me−φ(qmin (θt )) ≤ me−φ(γmin ∥θt ∥ ) , so
L−1

log ∥θt ∥

L

L(θt ) ≤ (L − 1) log ∥θt ∥ + log m − φ(γmin ∥θt ∥ ) .

On any compact interval ∥θt ∥ ∈ [Nmin , N ] this expression is bounded from above by continuity, and by
L
L
Equation (23), choosing 0 < u < q, φ(γmin ∥θt ∥ ) ≥ φ(u) + φ′ (u)(γmin ∥θt ∥ − u), so the expression
tends to −∞ as ∥θt ∥ → ∞.
In this work we prove KKT stationarity using the notion of approximate KKT points.
27

Definition C.3. We say θ is a feasible point of Problem (11) if ∀i ∈ [m] : yi f (xi ; θ) ≥ 1, or equivalently if
qmin (θ) ≥ 1.
Definition C.4. A feasible point θ of Problem (11) is called an (ε, δ)-approximate KKT point if there exist
2
λ1 , ..., λm ≥ 0, hi ∈ ∂f (xi ; θ) and k ∈ ∂ 21 ∥θ∥ with
Pm
1. ∥ i=1 λi yi hi − k∥2 ≤ ε.
Pm
2.
i=1 λi (yi f (xi ; θ) − 1) ≤ δ.
Definition C.5. We say that a feasible point of Problem (11) satisfies the Mangasarian-Fromovitz Constraint
Qualifications if there exists v ∈ Rp such that for all i ∈ [m] with 1 − yi f (xi ; θ) = 0 and for all h ∈
∂ (1 − yi f (xi ; θ)), it holds:
⟨v, h⟩ > 0.
(30)
Lemma C.6 (Lemma A.11 in Tsilivis et al. (2025)). The MFCQ constraints are satisfied by any feasible
point θ of Problem (11) for f satisfying, (M1-Weak), (M2-Weak).
Theorem C.7 (Theorem C.4 in Lyu and Li (2019) + Lemma C.6). Let θn → θ be a converging sequence so
that θn is a (εn , δn )-approximate KKT point of Problem (11), where εn → 0, δn → 0. Then θ is a KKT point
of Problem (11).
Theorem C.8 (KKT Stationarity Derived from Alignment). Let θt be any arc of parameters of a model
f (x; θ) assuming (M1-Weak), (M2-Weak), and denote gt ∈ ∂L(θt ) any choice of subgradient along the
trajectory. Let θ̄ with θ̄ = 1, γ(θ̄) > 0. Assume that there exists a sequence tn with θtn ̸= 0, gtn ̸= 0 and:
n→∞

1. L(θtn ) −→ 0
n→∞

θ

2. ∥θttn ∥ −→ θ̄
n
D
E
n→∞
θ
g
3. ∥θttn ∥ , − ∥gttn∥
−→ 1.
n

n

⋆

Then θ̄ is the direction of a KKT point of Equation (11).
n→∞

n→∞

n→∞

tn
−→ ∞. Since γ(θtn ) converges
Proof. First, note that since L(θtn ) −→ 0, it holds that ∥θtn ∥ −→ ∞, qmin
1
to γ(θ̄) > 0, in particular for large enough n, γ(θtn ) > 2 γ(θ̄) > 0. Therefore it holds by Lemma C.2 that for
large enough n, there exists C > 0 with

∥gtn ∥⋆ ≥ CL(θtn ) ∥θtn ∥

L−1

.

Now, any θ with γ(θ) > 0 has for all i ∈ [m] that yi f (xi ; θ) > 0 and therefore there exists a feasible point θe
e = 1, given by
of Equation (11) along its direction with qmin (θ)
θe :=

θ
θ
θ
=
.
=
1/L
1/L
1/L
qmin (θ)
γ(θ)
∥θ∥
mini∈[m] (yi f (xi ; θ))

ē =
θ̄
Denote θ̂ := θ
. We claim θ̂ is the desired KKT point. We show that in fact θ̂ is itself a
γ(θ̄)1/L
(εs , δs )-approximate KKT point for arbitrarily small (εs , δs ), allowing us to use Theorem C.7 with the constant
sequence θ̂.
First note that by continuity and scale-invariance of γ(θ), it holds that
θetn =

1

θtn n→∞
1
−→
θ̄ = θ̂ .
1/L
∥θtn ∥
γ(θtn )
γ(θ̄)1/L


L−1
1
Take subgradients hti ∈ ∂f (xi , θt ) defining gt by the chain rule as in Lemma C.2. Since qmin (θt )− L
=
1
1
−1
t
−1
t
e
e
qmin (θt ) L , it holds by Theorem B.2(a) in Lyu and Li (2019) that h := qmin (θt ) L h ∈ ∂f (xi ; θt ). Since
i

28

i

f is locally Lipschitz, it holds that ∂f (xi ; ·) is bounded and has a closed graph around θ̂, so for every
e (ts ) → ĥi for some ĥi ∈ ∂f (xi ; θ̂). By iteratively choosing
i ∈ [m] there exists a subsequence ts of tn with h
i
e (ts ) → ĥi for all i ∈ [m]. Take a Bolzano-Weierstrass
subsequences for i = 1, ..., m we may assume that h
i
s→∞
g ts
g
⋆
limit u of − ∥gt ∥ , and again abuse notation by assuming w.l.o.g − ∥gtts∥ −→ u⋆ . It therefore holds that
s ⋆
s ⋆
∥u⋆ ∥⋆ = 1 and


gts
⋆
θ̄, u = lim θ̄, −
=1.
s→∞
∥gts ∥⋆
Denote
⋆

k := θ̂ u ,

∀i ∈ [m], s ∈ N : λs,i :=



1
θ̂ qmin (θts )1− L ℓ zits φ′ (zits )

≥0.
∥gts ∥⋆
o
n
D
E
2
θ̂ = θ̂ · ∂ θ̂ = θ̂ v | v, θ̂ = θ̂ , ∥v∥⋆ ≤ 1

2

Note that k ∈ ∂ 21 θ̂ since by the chain rule ∂ 12
D
E D
E
and indeed u⋆ , θ̂ = u⋆ , θ̂ θ̄ = θ̂ and ∥u⋆ ∥⋆ = 1. Choosing ĥi , i ∈ [m] as the subgradients from
Definition C.4, it remains to show that the errors are bounded by εs , δs → 0. Beginning from εs , first note
that
m
m
m
θ̂
X
X
X
1


gts
(t )
(t )
L −1
e (ts ) =
λs,i yi h
λs,i qmin
ℓ zits φ′ (zits )yi hi s = − θ̂
.
yi hi s =
i
∥g
∥
∥g
ts ⋆ i=1
ts ∥⋆
i=1
i=1
So,
εs :=

m
X

⋆

λs,i yi ĥi − θ̂ u

m
X

≤

i=1

λs,i yi



e (ts )
ĥi − h
i

i=1

2



+
2

m
X

e (ts ) − θ̂ u⋆
λs,i yi h
i

i=1

.

(31)

2
(t )

g

e s → ĥi and show
The second term goes to 0 since − ∥gtts∥ → u⋆ . To show the first term goes to 0, we use h
i
s

⋆

L−1

λs,i are bounded. We use ∥gts ∥⋆ ≥ CL(θts ) ∥θts ∥

:

1

θ̂ qmin (θts )1− L ℓ (zit ) φ′ (zit )

λs,i =

∥gts ∥⋆

1

≤

Φ′M θ̂ γ(θts )1− L ∥θts ∥

L−1

L

∥gts ∥⋆

1
1− L

≤

Φ′M θ̂ γ(θts )
C

<∞,

since γ is bounded. For δs ,
δs =

m
X
i=1

λs,i (yi f (xi ; θ̂) − 1) ≤

m
X

λs,i (yi f (xi ; θ̂) − yi f (xi ; θets )) +

m
X

λs,i (yi f (xi ; θets ) − 1)

(32)

i=1

i=1

The first term goes to 0 from continuity of f and boundedness of λs,i . As for the second term, note that each

29

summand is non-negative. Plugging in λs,i (here zi = zits , and similarly for qmin , L),
m
X



λs,i yi f (xi ; θets ) − 1 =

i=1



m
X
1
zi
1− L
′
ℓ (zi ) φ (zi )
−1
q
∥gts ∥⋆ i=1 min
qmin
θ̂

m
X

θ̂
=

1/L

qmin ∥gts ∥⋆ i=1

φ′ (zi )ℓ (zi ) (zi − qmin )
m
X

θ̂
≤

∥θts ∥ γ(θts )1/L CL ∥θts ∥
θ̂ e

=

−φ(qmin )

m
X
L

Cγ(θts )1/L L ∥θts ∥

L
Cγ(θts )1/L ∥θts ∥ i=1

θ̂
=

φ′ (zi )e−(φ(zi )−φ(qmin )) (zi − qmin )

φ′ (zi )e−(φ(zi )−φ(qmin )) (zi − qmin )

φ′ (zi )e−(φ(zi )−φ(qmin )) (φ(zi ) − φ(qmin ))

L
i:zi >qmin

θ̂
≤

i=1

X

Cγ(θts )1/L ∥θts ∥

X

Cγ(θts )1/L ∥θts ∥

φ′ (zi )e−φ(zi ) (zi − qmin )

i=1
m
X

θ̂
≤

L−1

L
i:zi >qmin

zi − qmin
φ(zi ) − φ(qmin )

zi − qmin
φ′ (zi )
e φ(zi ) − φ(qmin )

s→∞

−→ 0
L−1

The first inequality is again by ∥gt ∥⋆ ≥ CL ∥θt ∥
, and the second by e−φ(qmin ) ≤ L. In the last inequality
s→∞
s→∞
we used the fact ∀z ≥ 0 : ze−z ≤ 1/e. The limit holds since ∥θts ∥ −→ ∞, γ(θts ) −→ γ(θ̄) > 0, φ′ is
ts
bounded, and since for all large enough s, qmin > 1, so by Equation (23):
ts
∀i ∈ [m], zits > qmin
:

C.3

ts
ts
zits − qmin
zits − qmin
1
≤
= ′
<∞
ts
ts
ts
ts
′
φ (1)
φ(zi ) − φ(qmin )
φ (1)(zi − qmin )

Normalized Steepest Descent with a LR Schedule

In this section we follow the proof ideas of Tsilivis et al. (2025) to extend both main results: monotonicity of
the soft margin and convergence to KKT points, to normalized steepest descent with a learning rate schedule
η(t).
Theorem C.9 (Monotonicity of the Soft Margin - Theorem 3.1). Let θt follow a trajectory of Equation (3),
under Assumptions (M1-Weak), (M2-Weak), (R1), (LR-NSD). Then γ
e(θt ) is non-decreasing on [t0 , ∞).
Proof. By the chain rule, for almost any t ≥ t0 and for any gt ∈ ∂L(θt ):


dL(θt )
dθt
= gt ,
.
dt
dt
In particular this holds for gt ∈ ∂L(θt ) from the definition of normalized steepest descent for which


1 dθt
1 dL(θt )
−∥gt ∥⋆ =
, gt =
.
(33)
η(t) dt
η(t) dt


1
1
−1
>
φ(0),
Notice that (R1) is equivalent to log L(θ
or
φ
log
e(θt ) > 0,
L(θt ) > 0, so for t = t0 we have γ
t)
30

and log γ
e is well defined. For any t ≥ t0 let nt ∈ ∂ ∥θt ∥ (with ∥nt ∥⋆ ≤ 1) and any gt ∈ ∂L(θt ). For almost
any t ≥ t0 with γ
e(θt ) > 0 it holds that


d log γ
e(θt )
d
1
d
=
log φ−1 log
− L log ∥θt ∥
dt
dt
L(θt )
dt


1
−1 ′
dL(θt ) (φ ) (log L(θt ) )
nt dθt
=−
−
L
,
1
dt L(θt )φ−1 (log L(θ
∥θt ∥ dt
)
t)

Chain Rule

1
−1 ′
dθt
dL(θt ) (φ ) (log L(θt ) )
dt
−
L
≥−
1
dt L(θt )φ−1 (log L(θt ) )
∥θt ∥

= ∥gt ∥⋆ η(t)

1
)
(φ−1 )′ (log L(θ
t)

−
1
L(θt )φ−1 (log L(θ
)
t)

Def. of dual norm

Lη(t)
∥θt ∥

Equation (33)

Lη(t)∥gt ∥⋆
Lη(t)
−
⟨θt , −gt ⟩
∥θt ∥
≥0.

≥

Equation (26)
Def. of Dual Norm

This shows that log γ
e(θt ) is non-decreasing whenever γ
e(θt ) > 0. Since γ
e(θt0 ) > 0, we get that log γ
e(θt ) and
hence γ
e(θt ) are non-decreasing on [t0 , ∞).
Lemma C.10 (Descent Lemma for NSD). Let θt follow a trajectory of Equation (3) under Assumptions (M1t→∞
t)
Weak), (M2-Weak), (R1), (LR-NSD). Then for almost any t ≥ t0 : dL(θ
0, and it holds that L(θt ) −→ 0,
<
dt

t→∞

t→∞

∥
R tt −→ 1,
∥θt ∥ −→ ∞, that γ, γ
e both converge to some γ∞ > 0 and ∥θ
η
0

1
φ−1 log L(θ
)
t

γ∞ ∥θt ∥L

t→∞

−→ 1.

Proof. By Equation (33) and Equation (26), for almost any t ≥ t0 , there exists gt ∈ ∂L(θt ) with
φ−1 (log 1 )
1
dL(θt )
= −η(t)∥gt ∥⋆ ≤ −
η(t)LL −1 ′ L 1 < 0 .
dt
∥θt ∥
(φ ) (log L )

(34)

Note that φ−1 (log L1 ) > 0 since by Theorem C.9, γ
e(θt ) ≥ γ
e(θt0 ) > 0. Rearranging,


1/L


 L1 −1


φ−1 log L1
1
1
1 dL(θt ) 1
−1
−1 ′
φ
log
≥ η(t)
= η(t)e
γ (θt )1/L .
(φ ) log
−
L dt L
L
L
∥θt ∥
Since γ
e is non-decreasing, positive and bounded by above (from Lemma C.2 item 2, γ
e ≤ γ, and γ is bounded
by continuity of f and compactness of the unit ∥·∥-sphere), it converges to some γ∞ > 0. Therefore, for every
ε > 0 there exists some tε with ∀t ≥ tε : γ
e ≥ γ∞ − ε. Integrating on [tε , t]:


1/L 

1/L
Z t
1
1
−1
1/L
−1
φ
log
− φ
log
≥ (γ∞ − ε)
η.
(35)
L(θt )
L(θtε )
tε
1
By Assumption (LR-NSD), the RHS tends to ∞ as t → ∞, showing that φ−1 (log L(θ
) → ∞, and therefore
t)
t→∞
t→∞
1
C.2, it holds since ∥θt ∥ → ∞
L(θt ) −→ ∞, L(θt ) −→ 0 and in particular ∥θt ∥ → ∞. Note that by Lemma



that |γ − γ
e| → 0, so also γ → γ∞ . Moreover, we get that lim inf t→∞

1
φ−1 log L(θ
t)
Rt L
( 0 η)

≥ γ∞ − ε, but since this

holds for any ε > 0 it holds that


1
φ−1 log L(θ
t)
lim inf
≥ γ∞ .
R L
t→∞
t
η
0

31

(36)

Note that by definition of γ
e,



1
φ−1 log L(θ
)
t
L

∥θt ∥

t→∞

=γ
e(θt ) −→ γ∞ .

(37)

Putting together Equations (36), (37) implies



 1/L
1

1/L
−1
φ
log
L(θt ) 
1
∥θt ∥
∥θ ∥

 t

=1.
≥
γ
lim inf R t = lim inf 

∞
R L
t→∞
t→∞
1
γ∞
t
−1 log
η
φ
0
η
L(θt )
0
L

It also holds by the triangle inequality and by Assumption (LR-NSD) that
Rt
Rt
s
ds
∥θ0 ∥ + 0 dθ
∥θ0 ∥ + 0 η
∥θt ∥
ds
lim sup R t ≤ lim sup
= lim sup
=1.
Rt
Rt
t→∞
t→∞
t→∞
η
η
η
0
0
0
Proving
∥θt ∥
lim R t = 1 .
η
0

t→∞

Theorem C.11 (KKT Stationarity for NSD - Theorem 3.2). Let θt be a trajectory of normalized steepest
descent with respect to a norm ∥·∥ (Equation (3)) under Assumptions (M1-Weak), (M2-Weak), (R1), (LRNSD). Then any limit point θ̄ of ∥θθtt ∥ is the direction of a KKT point of Problem (11) with the same norm
∥·∥.
t→∞

Proof. Let θ̄ be a limit point of ∥θθtt ∥ . By Theorem C.8, and since by Lemma C.10, L(θt ) −→ 0 and
E
D
t→∞
n→∞
n→∞
θ
g
θ
γ(θt ) −→ γ∞ > 0, it suffices to find a sequence tn −→ ∞ for which ∥θttn ∥ −→ θ̄ and ∥θttn ∥ , − ∥gttn∥ → 1.
n
n
n ⋆
We construct a sequence tn by induction, taking t0 as the base. Suppose t0 < t1 < ... < tn−1 have already
been constructed. By Lemma C.10, γ
e(θt ) → γ∞ > 0. Using this together with the fact that θ̄ is a limit point
of ∥θθtt ∥ , there exists sn > tn−1 + 1 with the following:
θsn
1
− θ̄ ≤
∥θsn ∥
n

and

Z ∞ d∥θt ∥

Z ∞

Notice that since ∥θt ∥ → ∞,
Z ∞ dθt
dt

sn

∥θt ∥

dt

dt ≥

∥θt ∥

sn

Therefore, there exists s′n > sn with

sn

d log ∥θt ∥
∥θt ∥
dt = lim log
=∞.
t→∞
dt
∥θsn ∥

dθt
dt

∥
1
∥θt ∥ dt = n . Now, from the proof of Theorem C.9, it holds that

R s′n ∥
sn

dt =

1
γ∞
1
log
≤ 2 .
L
γ
e(θsn )
n



t
L dθ
Lη(t)∥gt ∥⋆
d log γ
e(θt )
Lη(t)
dt
≥
−
=
dt
⟨θt , −gt ⟩
∥θt ∥
∥θt ∥


1

D
E − 1 .
gt
θt
− ∥gt ∥ , ∥θt ∥
⋆

Therefore, rearranging terms and integrating on [sn , s′n ]:
γ
e(s′n )

1
log
≥
L
γ
e(sn )

Z s′n

dθt
dt

sn

∥θt ∥





1
D
E − 1 dt .
gt
− ∥gt ∥ , ∥θθtt ∥
⋆

32

By a standard proof by contradiction there exists a (non-zero measure set of points) tn ∈ (sn , s′n ) with
γ
e(s′ )

n
1 log γe(sn )
1
E −1≤ R
D
≤ ,
dθ
gtn
θtn
s′n ∥ dtt ∥
L
n
dt
∥θtn ∥ , − ∥gtn ∥⋆
sn ∥θt ∥

1

because otherwise for almost every t ∈ (sn , s′n ) we have the opposite inequality, and so


γ
e(s′n )
Z s′n dθt
Z s′n dθt
1
1 log γe(sn )
1
γ
e(s′n )
dt
dt
D

E − 1 dt > R
dt
=
log
,
dθ
∥θt ∥
L s′n ∥ dtt ∥
∥θt ∥
L
γ
e(sn )
sn
sn
− ∥ggtt∥ , ∥θθtt ∥
dt
sn ∥θt ∥
⋆
D
E
n→∞
θtn
gtn
a contradiction. Thus, ∥θt ∥ , − ∥gt ∥ ≥ 1+1 1 −→ 1. The opposite inequality follows from the definition
n
n ⋆
E n
D
n→∞
g
θ
θ
−→ 1. Furthermore, we claim the sequence ∥θttn ∥ converges to
of the dual norm, so in fact ∥θttn ∥ , − ∥gttn∥
n

n

n

⋆

θ̄:
θt n
θsn
θt n
1
θtn
θsn
θsn
+
+
− θ̄ ≤
−
− θ̄ ≤
−
∥θtn ∥
∥θtn ∥ ∥θsn ∥
∥θsn ∥
∥θtn ∥ ∥θsn ∥
n
Z tn d θt
Z tn dθt
1
1
3
∥θt ∥
dt
dt ≤ + 2
≤ +
dt ≤ → 0 ,
n
dt
n
∥θ
∥
n
t
sn
sn
where we used Equation (24) in the second to last inequality.

C.4

Approximate Steepest Descent

In this section we prove a KKT result for trajectories θt approximating steepest descent. We provide the
following definition:
Definition C.12 (Approximate Steepest Descent). We say an arc θt is a trajectory of Approximate Steepest
Descent with respect to a norm ∥·∥ if eventually ∃gt ̸= 0 ∈ ∂L(θt ) for almost any t, and there exist
ν(t) > 0, Rmax > 0 with:
Rt
1. limt→∞ N (t) := limt→∞ 0 ν = ∞
∥θt ∥
2. lim supt→∞ N
(t) ≤ Rmax

3. ess liminf t→∞ r(t) ≥ 1, where
a.e.

r(t) =


sup
gt ∈∂L(θt )\{0}

1 dθt
gt
,−
ν(t) dt
∥gt ∥⋆


.

Note that as ∂L(θt ) is a compact set for any locally Lipschitz L, the supremum in the definition of r(t) is
attained by some gt ∈ ∂L(θt ).
t
Some motivation is in order. A possible and natural choice of ν(t) is ν(t) = dθ
dt . This choice is motivated
by the fact that for exact Steepest Flow, we have by definition for almost any t


1 dθt
gt
r(t) =
,−
=1,
ν(t) dt
∥gt ∥⋆
and

Z t
∥θt ∥ ≤ ∥θ0 ∥ +

ν.
0

33

Also, the following type of trajectory, which is a simpler and more “natural” definition of Approximate
t
Steepest Descent, is also covered by our definition when choosing ν(t) = dθ
dt :
*
+
dθt
gt
t→∞
dt
,−
−→ 1 .
dθt
∥g
∥
t
⋆
dt
It is crucial in our analysis for an inner product of this type to tend to 1. However, we can allow ν(t) to
t
be momentarily larger than dθ
dt , as long as on average it is not so (condition 2, when Rmax ≤ 1). Thus
the definition allows more flexibility for adaptive algorithms such as Adam, since we can choose ν(t) as an
t
external learning rate, with dθ
dt affected both by ν(t) and by the dynamics. In particular this flexibility will
be invaluable for the main result of KKT convergence for Adam.
Lemma C.13. If θt is an Darc with eventually
∃gt ̸= 0 ∈ ∂L(θt ) for almost any t, ess liminf r(t) ≥ 1
E
R t t→∞
a.e.
gt
1 dθt
t
,
ν(t)
for r(t) = supgt ∈∂L(θt )\{0} ν(t)
,
−
= dθ
dt
∥gt ∥⋆
dt , and 0 ν −→ ∞, then θt is a trajectory of
Approximate Steepest Descent with Rmax ≤ 1.
Rt
∥θt ∥
Proof. According to Definition C.12, it remains to show that lim supt→∞ N
(t) ≤ 1 where N (t) = 0 ν =
R t dθs
t→∞
ds. By the triangle inequalities, ∥θt ∥ ≤ ∥θ0 ∥ + N (t), and since N (t) −→ ∞,
ds
0


∥θt ∥
∥θ0 ∥
lim sup
≤ lim sup 1 +
=1
N (t)
t→∞ N (t)
t→∞

Lemma C.14. If θt is a trajectory of Approximate Steepest Descent, then for almost all t ≥ 0 there exists
gt ∈ ∂L(θt ) with:
−dL
dθt
,
r(t)ν(t) = dt ≤
∥gt ∥⋆
dt
and in particular, dL
dt < 0 for almost all large enough t.
E
D
gt
1 dθt
Proof. For almost any t, let gt ̸= 0 ∈ ∂L(θt ) be such that r(t) = ν(t)
,
−
dt
∥gt ∥⋆ . By the chain rule, for
almost any t,


dθt
dL
= gt ,
,
dt
dt
so


dL
dθt
dθt
dL
−
≤ ∥gt ∥⋆
≤
= gt ,
,
dt
dt
dt
dt
and
−

dL
=
dt


−gt ,

dθt
dt


= r(t)ν(t)∥gt ∥⋆ ,

(38)

so dL
dt < 0 for all t with r(t) > 0, which occurs for almost all large enough t since ess liminf t→∞ r(t) ≥ 1.
Lemma C.15 (Descent Lemma for Approximate SD). Assume θt is a trajectory of Approximate Steepest
Descent, and assume that there exists t0 ≥ 0, γmin > 0 with ∀t ≥ t0 : θt ̸= 0 and γ(θt ) > γmin > 0. Then
t→∞
t→∞
L(θt ) −→ 0, ∥θt ∥ −→ ∞.
Proof. Take t1 ≥ t0 with:
∀t ≥ t1 : r(t) ≥

1
a.e. ,
2

34

γ(θt ) > γmin

By Lemma C.14, for almost any t ≥ t1 we have dL
dt < 0, so
Z t


dL
L
L(θt ) = L(θt1 ) +
ds < L(θt1 ) ≤ m · ℓ γmin ∥θt1 ∥ < m · ℓ(0) .
t1 ds
In particular, this implies that ∥θt ∥ ≥ Ω(1), because if towards a contradiction there existed a sequence
n→∞
n→∞
tn −→ ∞ with θtn −→ 0, this would imply by continuity of f that ∀i ∈ [m] : f (xi ; θtn ) → f (xi ; 0) = 0 and
n→∞
therefore L(θtn ) −→ m · ℓ(0), a contradiction. Therefore denote Nmin = inf t≥t1 ∥θt ∥ > 0. By Lemma C.2,
L−1
there exists C > 0 with ∥gt ∥⋆ ≥ CL(θt ) ∥θt ∥
.
So, by Lemma C.14, for almost any t ≥ t1 :
dL
L−1
= r(t)ν(t)∥gt ∥⋆ ≥ r(t)ν(t)C ∥θt ∥
L
dt
N L−1 C
≥ min ν(t)L .
2
Dividing by L and integrating both sides on [t1 , t] we get
−

− log L(θt ) − (− log L(θt1 )) ≥

L−1
Nmin
C
t→∞
(N (t) − N (t1 )) −→ ∞ ,
2

implying L → 0 and therefore ∥θt ∥ → ∞.
Lemma C.16. Assume θt is a trajectory of Approximate Steepest Descent with Rmax ≤ 1, and assume
that eventually θt ̸= 0 and limt→∞ ∥θθtt ∥ = θ̄ with γ(θ̄) > 0. Then there exists a sequence tn → ∞ with
E
D
g tn
θtn
,
−
→ 1.
∥θt ∥
∥gt ∥
n

n

⋆

Proof. Since limt→∞ ∥θθtt ∥ = θ̄ with γ(θ̄) > 0, eventually γ(θt ) > 12 γ(θ̄) > 0, so from Lemma C.15, L(θt ) →
0, ∥θt ∥ → ∞. By Lemma C.2 we conclude |γ(θt ) − γ
e(θt )| → 0, so γ(θt ), γ
e(θt ) both converge to γ(θ̄) > 0,
hence also log γ
e(θt ) converges. We build a sequence tn by induction. Choose t0 with ∀t ≥ t0 : L(θt ) < ℓ(0),
and suppose t0 < ... < tn−1 have been chosen. Choose τ1 > tn−1 + 1 with


γ
e(θτ2 )
L
sup log
≤
γ
e
(θ
)
n
τ1
τ2 ≥τ1
∀t > τ1 : r(t) > 1 −

1
a.e.
n

For almost any t ≥ t0 , ∃gt ̸= 0 ∈ ∂L(θt ) with:


d log γ
e
d
1
d
−1
=
log φ
log
− L log ∥θt ∥
dt
dt
L(θt )
dt
=−

1
−1 ′
dL(θt ) (φ ) (log L(θt ) )
d
− L log ∥θt ∥
1
dt L(θt )φ−1 (log L(θ
dt
)
t)

= ν(t)∥gt ∥⋆ r(t)
≥

1
(φ−1 )′ (log L(θ
)
t)

d

− L log ∥θt ∥
1
dt
L(θt )φ−1 (log L(θ
)
t)

Lν(t)
r(t)
d
D
E − L log ∥θt ∥ .
gt
θt
∥θt ∥
dt
,−
∥θt ∥

∥gt ∥⋆

φ−1 (log

1

)

In the last inequality we used Equation (26), namely ⟨θt , −gt ⟩ ≥ LL(θt ) (φ−1 )′ (logL(θt1) ) , implying
1
(φ−1 )′ (log L(θ
)
)

t
1
L(θt )φ−1 (log L(θ
)
t)

L(θt )

L
≥ ⟨θt ,−g
.
t⟩

35

So, rearranging terms and integrating on [τ1 , τ2 ] for any τ2 > τ1 ,


Z τ2
γ
e(θτ2 )
∥θτ2 ∥
ν(t)
r(t)
1
D
E dt .
log
+ log
≥
θt
L
γ
e(θτ1 )
∥θτ1 ∥
τ1 ∥θt ∥
, − gt
∥θt ∥

∥gt ∥⋆

In particular, by a standard proof-by-contradiction argument (see Theorem C.11), for every τ2 there exists a
non-zero measure set of points tn ∈ (τ1 , τ2 ) with


∥θτ2 ∥
γ
e(θτ2 )
1
L log γ
e(θτ1 ) + log ∥θτ ∥
r(tn )
1
E .
≥D
R τ2 ν(t)
θtn
gtn
dt
,
−
∥θ
∥
τ1
t
∥θt ∥
∥gt ∥
n

n

⋆

In particular tn can be chosen with r(tn ) > 1 − n1 .
Rt
R∞
F
F
Note that for any F (t), G(t) with lim sup G
≤ 1 and 0 G = ∞ it holds that lim sup R0t G ≤ 1. Indeed,
0
R tε
R
R tε
R
Rt
F +(1+ε) t G t→∞
F+ t F
F
for any ε > 0 take tε with ∀t ≥ tε : F (t) ≤ (1 + ε)G(t), so R0t G = R0tε G+Rttε G ≤ 0 R tε G+R t Gtε −→ 1 + ε.

tε
tε
0
0
R∞
R 0∞
F
Also, note that if lim sup G
≤ 1 and 0 F = ∞ then in particular 0 G = ∞.
R ∞ ν(t)
ν(t)  ν(t)
∥θt ∥
N (t)
In our case, since lim supt→∞ N
(t) ∥θt ∥ = lim supt→∞ N (t) ≤ 1, and τ1 N (t) dt = limt→∞ log N (τ1 ) = ∞
R ∞ ν(t)
τ2 →∞
(implying also τ1 ∥θt ∥ dt = ∞), there exists q(τ2 ) with q(τ2 ) −→ 1 and


Z τ2
Z τ2
N (τ2 )
ν(t)
ν(t)
dt ≥ q(τ2 )
dt = q(τ2 ) log
.
N (τ1 )
τ1 N (t)
τ1 ∥θt ∥
R τ2 ν(t)
∥θt ∥
Since ∥θt ∥ , N (t) → ∞ and again since lim supt→∞ N
(t) ≤ 1 there exists large enough τ2 with τ1 ∥θt ∥ dt ≥ 1
and
∥θτ ∥
log θ 2
1
∥ τ1 ∥
1+ ≥
.
N (τ2 )
n
q(τ2 ) log N
(τ1 )

Altogether for such τ2 and tn ∈ (τ1 , τ2 ) as above,


γ
e(θτ2 )
∥θτ2 ∥
1


log
L
γ
e(θτ1 ) + log ∥θτ ∥
1
2
1
1
=1+ .
≤ + 1+
R τ2 ν(t)
n
n
n
dt
τ1 ∥θt ∥
So,


θt n
gtn
,−
∥θtn ∥ ∥gtn ∥⋆


≥

1 − n1 n→∞
−→ 1 .
1 + n2

And the other direction is immediate by the definition of the dual norm, implying

D

θtn
gtn
∥θtn ∥ , − ∥gtn ∥⋆

E

n→∞

−→ 1.

Theorem C.17 (KKT Stationarity for Approximate SD ). Assume θt is a trajectory of Approximate Steepest
Descent with Rmax ≤ 1, and assume that eventually θt ̸= 0 and θt converges in direction to some θ̄ with
γ(θ̄) > 0. Then θ̄ is along the direction of a KKT point of Equation (11).
Proof. Follows from Theorem C.8 using Lemma C.16 and Lemma C.15.

C.5

Momentum Steepest Descent

In this section we show that under Assumptions (M1-Weak), (M2), (LR-MSD), (T1), (T2), (T3), normalized
and unnormalized momentum steepest descent are approximate steepest descent algorithms, which allows
us to infer Theorem C.21, namely that the directional limit point is a KKT point of the ∥·∥-max-margin
problem. Recall that (T3) is implied if strengthening (M1-Weak) to (M1).

36

Definition C.18. We denote for a choice h(xi ; θt ) ∈ ∂f (xi ; θt ) and ∀i, i′ ∈ [m], j ∈ [p] (see Definition B.2
for the definition of A):
h̄t [i, j] :=
gt [i, j] = − ∥θt ∥

L−1

1
L−1

∥θt ∥

h(xi ; θt )[j],

ℓ(zit )φ′ (zit )yi h̄t [i, j],

h̄∞ [i, j] := lim h̄t [i, j]
t→∞

gt∞ [i, j] = − ∥θt ∥

L−1

ℓ(zit )φ′ (zit )yi h̄∞ [i, j]

∞
m∞
t [i, j] = A(gt [i, j], c1 )

mt [i, j] = A(gt [i, j], c1 ),
vt [i, i′ , j] = A(gt [i, j]gt [i′ , j], c2 ),

vt∞ [i, i′ , j] = A(gt∞ [i, j]gt∞ [i′ , j], c2 )

The notations derived from h̄∞ are well-defined for every i ∈ [m] under (T3). Note that
X
X
X
gt [j] =
gt [i, j], mt [j] =
mt [i, j], vt [j] =
vt [i, i′ , j] .
i∈[m]

i,i′ ∈[m]

i∈[m]

The following is a key lemma showing that under certain conditions, the momentum estimates follow
the asymptotically significant gradients with ratio approaching 1. Note that the lemma is independent of a
specific optimization algorithm.
Lemma C.19 (Asymptotic Momentum-Gradient Relations Under a Decaying Update). Assume θt is an
arc of parameters of a model f (x; θ) and let ∥·∥ be a norm. Let gt ∈ ∂L(θt ) be a choice of subgradients
and mt , vt the appropriate momentum estimates for gt , gt2 with
rates c1 , c2 > 0. Assume that
 momentum

1
t
L −1 , then:
(M1-Weak), (M2), (T1), (T2), (T3) are satisfied. If dθ
≤
o
t
dt
1. For every ε > 0, denoting Jε (t) =

n
o
t [j]|
j ∈ [p] : |g
>
ε
there exist for every j ∈ [p] vanishing error
∥gt ∥
⋆

t→∞

terms ej (t), e′j (t) −→ 0 with
∀t ≥ 0, j ∈ Jε (t) :

mt [j] = gt [j](1 + ej (t)),

p

vt [j] = |gt [j]| (1 + e′j (t)) .

2. It holds that
∥mt − gt ∥⋆ ≤ o (∥gt ∥⋆ ) ,

∥mt ∥⋆ t→∞
−→ 1,
∥gt ∥⋆

mt
gt t→∞
−→ 0 ,
−
∥mt ∥⋆
∥gt ∥⋆



gt2 ⋆ ,

∥vt ∥⋆ t→∞
−→ 1,
∥gt2 ∥⋆

vt
g2 t→∞
− 2t −→ 0 .
∥vt ∥⋆
∥gt ∥⋆

vt − gt2 ⋆ ≤ o
We first prove an auxiliary lemma.

Lemma C.20. Let u, w ∈ Rp be nonzero vectors and let ∥·∥⋆ a norm. Let ξ > 0 with
∥u − w∥⋆ ≤ ξ∥w∥⋆
Then

∥u∥⋆
− 1 ≤ ξ,
∥w∥⋆

w
u
−
∥u∥⋆
∥w∥⋆

≤ 2ξ
⋆

Proof. Since by the triangle inequalities
∥w∥⋆ − ∥u − w∥⋆ ≤ ∥u∥⋆ ≤ ∥w∥⋆ + ∥u − w∥⋆
This gives
∥u∥⋆
∥u − w∥⋆
−1 ≤
≤ξ
∥w∥⋆
∥w∥⋆

37

Now,
u
w
−
∥u∥⋆
∥w∥⋆

≤
⋆

u
u
−
∥u∥⋆
∥w∥⋆

+
⋆

u
w
−
∥w∥⋆
∥w∥⋆

⋆

∥u − w∥⋆
1
1
+
= ∥u∥⋆
−
∥u∥⋆
∥w∥⋆
∥w∥⋆
∥u∥⋆
∥u∥⋆
∥u − w∥⋆
=
1−
+
∥u∥⋆
∥w∥⋆
∥w∥⋆
≤ 2ξ


Proof of Lemma C.19. Denote ∀j ∈ [p], Ij := i ∈ [m] : h̄∞ [i, j] ̸= 0 . For every i, j with i ∈ Ij , it holds that
gt∞ [i, j], gt [i, j] eventually have a constant (nonzero) sign and
gt∞ [i, j] t→∞
−→ 1 .
gt [i, j]

(39)

d log|g∞ [i,j]|

t
We analyze
. One has for almost any t (using the chain rule theorems A.4, A.6) that
dt
∥θt ∥ , ℓ(zit ), φ′ (zit ) and therefore gt∞ [i, j] are differentiable w.r.t t. Note

dφ(zit )
dz t
d log ℓ (zit )
=−
= −φ′ (zit ) · i ,
dt
dt
dt
and for almost any t,
dzit
dyi f (xi ; θt )
=
=
dt
dt




dθt
L−1 dθt
, yi h(xi ; θt ) ≤ ∥θt ∥
dt
dt

∥h(xi ; θt )∥⋆ t→∞
−→ 0 .
L−1
∥θt ∥

∥h(x ;θ )∥

t
⋆
The limit holds since ∥θ i∥L−1
≤ O (1) (f is locally Lipschitz, see the proof of Equation (25)) and
t
 1 


dθt
≤ o t L −1 , implying ∥θt ∥ ≤ o t1/L , therefore
dt

L−1

∥θt ∥

dθt
dt



1
≤ o t(1/L)(L−1) t L −1 = o (1) .

d log ℓ(zit )
Since φ′ is bounded, it also holds that ess limt→∞
= 0. Also, since for large enough t, γ(θt ) ≥
dt
1
γ(
θ̄)
>
0
and
∥θ
∥
≥
N
>
0
(Assumptions
(T1),
(T2)),
and since φ′ is non-decreasing, φ′ is bounded
t
min
2
′
L
′′
from below by φ (Nmin γmin ) > 0. φ too is bounded, so
dz t

ess lim
t→∞

φ′′ (zit ) dti
d log φ′ (zit )
=0.
= ess lim
t→∞
dt
φ′ (zit )

Altogether
d log ∥θt ∥ d log ℓ (zit ) d log φ′ (zit )
d log |gt∞ [i, j]|
= (L − 1)
+
+
dt
dt
dt
dt
dθt
dt

d log ℓ (zit )
d log φ′ (zit ) t→∞
≤ (L − 1)
+
+
−→ 0 .
∥θt ∥
dt
dt

(40)

t
The first term goes to 0 since dθ
= o (1) and ∥θt ∥ = Ω(1) by Assumption (T1), and the rest of the terms
dt
have already been shown to go to 0.
d log|gt∞ [i,j]|
Therefore, for every i, i′ , j with i, i′ ∈ Ij , it holds that ess limt→∞
= 0 and
dt
d log|gt∞ [i,j]gt∞ [′ i,j]|
t
′
ess limt→∞
= 0. Also, since zi is locally Lipschitz w.r.t θt and ℓ, φ are C 1 , all of
dt
t
′ t
∥θt ∥ , ℓ(zi ), φ (zi ) are locally Lipschitz w.r.t θt . Furthermore θt is eventually Lipschitz w.r.t t because

38

d∥θt ∥
dt

t
≤ dθ
≤ o (1). Altogether gt∞ [i, j] is locally Lipschitz w.r.t t and in particular locally absolutely
dt
continuous with regard to t. Therefore by Corollary B.8,

m∞
t [i, j]
→ 1,
gt∞ [i, j]
Also, the fact that

vt∞ [i, i′ , j]
→1.
gt∞ [i, j]gt∞ [i′ , j]

(41)

d log|gt∞ [i,j]|
→ 0 implies that ∀c > 0 and ∀i, i′ ∈ Ij ,
dt
Z ∞
Z ∞
cs ∞
ecs |gs∞ [i′ , j]gs∞ [i′ , j]| ds = ∞ .
e |gs [i, j]| ds = ∞,
0
0

So by Lemma B.5 2(c) and Equation (39),
vt [i, i,′ j]
→1.
vt∞ [i, i′ , j]

(42)

vt [i, i′ , j] t→∞
−→ 1 .
gt [i, j]gt [i′ , j]

(43)

mt [i, j]
→ 1,
m∞
t [i, j]
Putting together (39), (41), (42), we get ∀i, i′ ∈ Ij :
mt [i, j] t→∞
−→ 1,
gt [i, j]
L−1

L

t
t
Denote G(t) = ∥θt ∥
ℓ(qmin
) > 0, and notice that since ∀t ≥ 0, ∃i ∈ [m] : qmin
= γ(θt ) ∥θt ∥ =
yi f (xi ; θt ) it holds as in Equation (40) that G is differentiable almost everywhere, locally absolutely continuous
G
and ess limt→∞ d log
= 0, implying by Corollary B.8 that A(G,c)
→ 1 for any c > 0.
dt
G
L−1
Since γ(θ̄) > 0 and by Assumption (T1), by Lemma C.2 we have ∥gt ∥⋆ = Θ(∥θ
L) = Θ(G(t)).
Also
 t∥

L−1

note that for every j ∈ [p] and ī ∈
/ Ij it holds that h̄∞ [ī, j] = 0, so |gt [ī, j]| ≤ o ∥θt ∥

L(θt ) ≤ o (G(t)).

By Lemma B.5, item 2(c) (applied with g = G, F = gt [ī, j]), it follows also that |mt [ī, j]| ≤ o (A(G, c1 )(t)) ≤
o (G(t)) ≤ o (∥gt ∥⋆ ).
Therefore, for any j ∈ [p],
∀ī ∈
/ Ij : |mt [ī, j] − gt [ī, j]| ≤ |mt [ī, j]| + |gt [ī, j]| = o (∥gt ∥⋆ ) .


L−1
Also, for any i ∈ [m], j ∈ [p] : |gt [i, j]| ≤ O ∥θt ∥
L = O (∥gt ∥⋆ ). Therefore by Equation (43),
∀i ∈ Ij : |mt [i, j] − gt [i, j]| = o (gt [i, j]) = o (∥gt ∥⋆ ) .
So altogether, for any j ∈ [p]
|mt [j] − gt [j]| ≤

X

|mt [i, j] − gt [i, j]| = o (∥gt ∥⋆ ) .

(44)

i∈[m]
t [j]|
Therefore, denoting Jε (t) = {j ∈ [p] : |g
∥gt ∥ > ε} we have:
⋆

∀j ∈ Jε (t) :

o (∥gt ∥⋆ ) t→∞
mt [j]
|mt [j] − gt [j]|
−1 =
≤
−→ 0 ,
gt [j]
|gt [j]|
ε∥gt ∥⋆

2
which gives item 1 for mt . We repeat the argument
/ Ij we have

 with vt and gt . Whenever i ∈ [m], ī ∈
2

gt [i, j]gt [ī, j] = o ∥gt ∥⋆

2

and vt [i, ī, j] = o ∥gt ∥⋆

by applying Lemma B.5 2(c) (with g = G2 , F =

gt [i, j]gt [ī, j]), so




2
2
∀i ∈ [m], ī ∈
/ Ij : |vt [i, ī, j] − gt [i, j]gt [ī, j]| ≤ o ∥gt ∥⋆ + o ∥gt ∥⋆ ,
and by Equation (43)


2
∀i, i′ ∈ Ij : |vt [i, i′ , j] − gt [i, j]gt [i′ , j]| = o (gt [i, j]gt [i′ , j]) = o ∥gt ∥⋆ ,

39

so



2
∀j ∈ [p] : vt [j] − gt2 [j] ≤ o ∥gt ∥⋆ .

(45)

Hence,


2
o ∥gt ∥⋆ t→∞
vt [j] − gt2 [j]
vt [j]
≤
∀j ∈ Jε (t) : 2 − 1 =
−→ 0
2
gt [j]
|gt2 [j]|
ε2 ∥gt ∥⋆
This gives the result of item 1 for vt .


2
2
Notice that from norm equivalence, ∥gt ∥⋆ ≤ O ∥gt ∥∞ = O



gt2 ∞ ≤ O



gt2 ⋆ . Therefore Equa-

t→∞

tions (44), (45) imply that there exists a vanishing e(t) −→ 0 with
vt − gt2 ⋆ ≤ e(t) gt2 ⋆ .

∥mt − gt ∥⋆ ≤ e(t)∥gt ∥⋆ ,

Thus item 2 follows from Lemma C.20 (note that gt ̸= 0 since ∥gt ∥⋆ ≥ Ω(L ∥θt ∥
tions (T1),(T2) and Lemma C.2, and therefore mt , vt ̸= 0 by Equations (44), (45)).

L−1

) > 0 by Assump-

Theorem C.21 (KKT Stationarity for Momentum SD - Implies Theorem 3.3). Assume θt follows a trajectory
of normalized or unnormalized momentum steepest descent under Assumptions (M1-Weak), (M2), (LR-MSD),
(T1), (T2), (T3). Then θ̄ = limt→∞ ∥θθtt ∥ is along the direction of a KKT point of the ∥·∥-max-margin problem
(Equation (11)).
 1 
t
o
t L −1 . In
Proof. We claim that in both the normalized and unnormalized cases it holds that dθ
≤
dt
 1 
t
the normalized case this is straightforward since dθ
= η(t) ≤ o t L −1 . In the unnormalized case, by
dt
(T1),(T2), it holds that ∥gt ∥⋆ = Θ(∥θt ∥
dθt
dt

L−1

L) is bounded (Lemma C.2), so
 ∥mt ∥⋆ is bounded (Corollary B.6),
1

implying that also in this case
= η(t)∥mt ∥⋆ ≤ O (η(t)) ≤ o t L −1 .
Note that for any α > 0 it holds that

arg min ⟨u, mt ⟩ = arg min ⟨αu, mt ⟩ = α arg min ⟨u, mt ⟩ ,
∥u∥=α

∥u∥=1

∥u∥=1

so in both the normalized and unnormalized cases, it holds that
dθt
dt
dθt
dt

Thus
*

dθt
dt
dθt
dt

gt
,−
∥gt ∥⋆

+

= arg min ⟨u, mt ⟩ .
∥u∥=1



 

gt
mt
mt
gt
= arg min ⟨u, mt ⟩ , −
= arg min ⟨u, mt ⟩ , −
+
−
∥gt ∥⋆
∥mt ∥⋆
∥mt ∥⋆
∥gt ∥⋆
∥u∥=1
∥u∥=1


mt
gt
−
.
= 1 + arg min ⟨u, mt ⟩ ,
∥mt ∥⋆
∥gt ∥⋆
∥u∥=1

t
We claim that θt is an approximate steepest descent trajectory (Definition C.12) with ν(t) = dθ
dt
and Rmax ≤ 1. We have
 already seen ∥gt ∥⋆ ̸= 0. By Lemma C.13, it suffices to show that

ess limt→∞

∥

dθt
dt
dθt
dt

∥

, − ∥ggtt∥

= 1. It therefore suffices to show that
⋆


ess lim arg min ⟨u, mt ⟩ ,
t→∞

∥u∥=1

mt
gt
−
∥mt ∥⋆
∥gt ∥⋆

And since arg min∥u∥=1 ⟨u, mt ⟩ = 1, it suffices to show that
mt
gt t→∞
−
−→ 0 .
∥mt ∥⋆
∥gt ∥⋆
40


=0.

And this is a result of Lemma C.19. Now the KKT result follows from Theorem C.17.

C.6

Composite MSD Algorithms, Muon and Muon-Signum

In this section we prove a simple lemma showing that by partitioning the parameters of a model and training
each part with a different normalized SD/MSD algorithm, the resulting algorithm is itself normalized SD/MSD
with respect to the maximum among the norms. This allows formulating Muon (on multi-layer networks)
and composite algorithms (such as running Muon on matrices and Signum on non-matrix parameters) as
normalized momentum steepest descent algorithms.
Lemma
Norm). Let θ = (u1 , ..., uK ) be a product representation of Rp , with uk ∈
P C.22 (Dual of Max
pk
K
R , k pk = p. Let {∥·∥(k) }k=1 be norms on Rpk with dual norms {∥·∥(k),⋆ }K
k=1 . Denote ∥θ∥ = maxk ∥uk ∥.
P
Then ∥·∥ is a norm, and its dual norm is ∥θ∥⋆ = k ∥uk ∥(k),⋆ .
Proof. First, it is a standard result that ∥·∥ is a norm (one can easily verify that ∥·∥ satisfies positive
definiteness, homogeneity and the triangle inequality). Note that
∥θ∥⋆ := max {⟨x, θ⟩ | ∥x∥ = 1}
(
)
X
⟨xk , uk ⟩ | max ∥xk ∥(k) = 1
= max
k

k

= max

(
X

)
∥xk ∥(k) ∥uk ∥(k),⋆ | max ∥xk ∥(k) = 1
k

k

=

X

∥uk ∥(k),⋆ .

k

The third equality holds since for each k, by definition of the dual norm ⟨xk , uk ⟩ is upper bounded by
∥xk ∥(k) ∥uk ∥(k),⋆ and this bound is attained by choosing xk in the direction that defines ∥uk ∥(k),⋆ . The last
equality holds by choosing ∀k : ∥xk ∥(k) = 1.
Lemma C.23 (Composing SD and
P MSD Algorithms). Let θt = (u1 (t), ..., uK (t)) be an arc of parameters of
a model f (xi ; θt ) with uk ∈ Rpk , k pk = p. Denote a choice of subgradients gt = (g1 (t), ..., gK (t)) ∈ ∂L(θt ),
pk
and momentum estimates mt = (m1 (t), ..., mK (t)). Let {∥·∥(k) }K
with dual norms
k=1 be norms on R
K
{∥·∥(k),⋆ }k=1 . Assume there exists η(t) > 0 so that for all k ∈ [K] one of the following hold:
1. (Normalized SD) For almost any t,
duk (t)
∈ η(t) arg min ⟨u, gk (t)⟩ .
dt
∥u∥(k) =1
2. (Normalized MSD) For almost any t,
duk (t)
∈ η(t) arg min ⟨u, mk (t)⟩ .
dt
∥u∥(k) =1
Then, θt is a trajectory of normalized SD / normalized MSD respectively, with respect to the norm ∥θ∥ =
maxk ∥uk ∥.
Proof. By definition of the dual norm it holds that
min ⟨u, gk (t)⟩ = − ∥gk (t)∥(k),⋆ ,

∥u∥(k) =1

min ⟨u, mk (t)⟩ = − ∥mk (t)∥(k),⋆ .

∥u∥(k) =1

Therefore in the case of SD, for almost any t,

 X

X
1 dθt
1 duk (t)
Lemma C.22
, gt =
, gk (t) = −
∥gk (t)∥(k),⋆
=
−∥gt ∥⋆ .
η(t) dt
η(t) dt
k

k

41

Similarly in the case of MSD,

 X

X
1 dθt
1 duk (t)
Lemma C.22
, mt =
, mk (t) = −
∥mk (t)∥(k),⋆
=
−∥mt ∥⋆ .
η(t) dt
η(t) dt
k

k

The following is a more general lemma pertaining to approximate SD algorithms.
Lemma C.24 (Composing Approximate
P SD Algorithms). Let θt = (u1 (t), ..., uK (t)) be an arc of parameters
of a model f (xi ; θt ) with uk ∈ Rpk , k pk = p. Denote a choice of subgradients gt = (g1 (t), ..., gK (t)) ∈
∂L(θt ), with eventually gi (t) ̸= 0 for almost any t. Assume there exists ν(t) > 0, R1 , .., RK > 0 and norms
K
{∥·∥(k) }K
k=1 (with dual norms {∥·∥(k),⋆ }k=1 ) so that:
1.

Rt
0

t→∞

ν −→ ∞

2. ∀k ∈ [K] : lim supt→∞

∥uk (t)∥(k)
Rt
≤ Rk
ν
0
a.e.

3. ∀k ∈ [K] : ess liminf t→∞ rk (t) ≥ 1 where rk (t) =

D

gk (t)
1 duk (t)
ν(t) dt , − ∥gk (t)∥(k),⋆

E

Then θt is a trajectory of Approximate Steepest Descent with respect to the norm ∥·∥ = maxk ∥·∥(k) , ν(t) and
Rmax ≤ maxk Rk .
∥
R tt ≤ maxk Rk = Rmax . Therefore it remains to show
Proof. It clearly holds by definition that lim supt→∞ ∥θ
ν
0

ess liminf t→∞ r(t) ≥ 1. Indeed, with the same choice of subgradients gt we have
D
E
1 duk (t)
 P

,
−g
(t)
k
k ν(t) dt
1 dθt
gt
P
r(t) =
,−
=
.
ν(t) dt
∥gt ∥⋆
k ∥gk (t)∥(k),⋆
Now note the following general claim: for any set of functions
q (t), ..., qK (t) and qe1 (t), ..., qeK (t) > 0
P 1
qk
k qk
P
≥ 1. Indeed, for any ε > 0 it holds
with ∀k ∈ [K] : ess liminf t→∞ qek ≥ 1 it holds that ess liminf t→∞
P k qek
P
P
q
eventually for almost any t that qk (t) D≥ qek (t)(1 − ε) for all
k,
so
(t)
≥
ek (t)(1 − ε) = (1 − ε) k qek (t).
k k
kq
E
Applying the claim with qk (t) =

1 duk (t)
ν(t) dt , −gk (t)

and qek (t) = ∥gk (t)∥(k),⋆ finishes.

Below is our definition of Muon in the exact orthogonalization setting:
Definition C.25 (Spectral and Nuclear Norms). For a real-valued matrix W let W = U ΣV T the SVD of
W , for Σ = diag(σ1 , ..., σr ), σi > 0. We denote the spectral and nuclear norms of W respectively as
X
∥W ∥sp = max σi , ∥W ∥nuc =
σi .
i∈[r]

i∈[r]

For a collection of matrices W = (W1 , ..., WK ) we denote (msp short for max-sp, snuc short for sum-nuc)
X
∥W∥msp = max ∥Wk ∥sp , ∥W∥snuc =
∥Wk ∥nuc .
k∈[K]

k∈[K]

It is a standard fact that ∥·∥nuc is the dual norm of ∥·∥sp . By Lemma C.22 this implies that ∥·∥snuc is the
dual norm of ∥·∥msp .
Definition C.26 (Muon). Let θt = (W1 (t), ..., WK (t)) ∈ Rp be a trajectory representing a collection of
matrices, gt = (G1 (t), ..., GK (t)) ∈ ∂L(θt ) a choice of subgradients and mt = (M1 (t), ..., MK (t)) a momentum
dWK
dW1
t
estimate of gt with parameter c1 > 0. The Muon update is defined as dθ
dt = ( dt , ..., dt ) for:
o
dWk n
SVD
∀k ∈ [K] :
∈ −η(t) · Uk (t)VkT (t) | Mk (t) = Uk (t)Σk (t)VkT (t) ,
dt
42

where SVD is the reduced SVD operator, i.e. Σk (t) is a square diagonal matrix with strictly positive diagonal
entries and Uk (t), Vk (t) have orthonormal columns.
Lemma C.27. Muon is a normalized momentum steepest descent algorithm with ∥·∥ = ∥·∥msp .
Proof. By the definition of normalized momentum steepest descent, we need to prove that


1 dθt
1 dθt
= 1,
, mt = −∥mt ∥snuc .
η(t) dt msp
η(t) dt
By definition of these norms, it suffices to show for every k that (omitting t for brevity) Uk Vk⊤ sp = 1 and
Uk Vk⊤ , Mk = ∥Mk ∥nuc . Indeed, Uk Vk⊤ sp = 1 by definition (Uk Vk⊤ is an SVD of itself with singular values
in {1, 0}). Denote Σk = diag(σ1 , ..., σr ) then we must show
Uk Vk⊤ , Mk =

r
X

σi .

i=1

And indeed, since the elementwise dot product between two matrices X, Y is equal to Tr[X ⊤ Y ], using
Uk⊤ Uk = I, Vk⊤ Vk = I we get
⊤
⊤
⊤ ⊤
⊤
⊤
⊤
Uk Vk⊤ , Mk = Tr[Mk⊤ Uk Vk⊤ ] = Tr[Vk Σ⊤
k Uk Uk Vk ] = Tr[Vk Σk Vk ] = Tr[Vk Vk Σk ] = Tr[Σk ] =

r
X

σi

i=1

Corollary C.28 (KKT Stationarity for Muon - Implies Corollary 3.4). Assume θ = (W1 , ..., WK ) ∈ Rp
is a parameter vector representing a collection of matrices, following a trajectory of Muon with a shared
learning rate schedule η(t) under Assumptions (M1-Weak), (M2), (LR-MSD), (T1), (T2), (T3). Then
θ̄ = limt→∞ ∥θθtt ∥ is along the direction of a KKT point of the ∥·∥-max-margin problem (Equation (11)), with
∥·∥ = ∥·∥msp .
Proof. Follows from Theorem C.21 since θt is a trajectory of normalized momentum steepest descent with
∥·∥ = ∥·∥msp (by Lemmas C.23, C.27).
Notice that Lemma C.23 reveals that any collection of momentum steepest descent algorithms may be
run in parallel, resulting in a new momentum steepest descent algorithm with respect to the maximal norm.
In particular, Muon-Signum, i.e. running Muon on weight matrices and Signum on non-matrix parameters,
answers this definition.
Corollary C.29 (KKT Stationarity for Muon-Signum - Implies Corollary 3.5). Assume θ = (W1 , ..., WK , u) =
(W, u) ∈ Rp is a parameter vector representing a collection of matrices and additional parameters u. Assume
W1 , ..., WK follow a trajectory of Muon and u follows a trajectory of Signum, with a shared scheduled learning
rate η(t). Assume (M1-Weak), (M2), (LR-MSD), (T1), (T2), (T3). Then θ̄ = limt→∞ ∥θθtt ∥ is along the
direction of a KKT point of the ∥·∥-max-margin problem (Equation (11)), with ∥θ∥ = max{∥W∥msp , ∥u∥∞ }.
Proof. Follows from Theorem C.21 since θt is a trajectory of normalized momentum steepest descent with
∥θ∥ = max{∥W∥msp , ∥u∥∞ } (by Lemmas C.23, C.27).

C.7

Adam

In this section we show that Adam is an approximate
descent algorithm with ∥·∥ = ∥·∥∞ in the
 1 steepest
 R
∞
−1
L
regime of a non-increasing learning rate η(t) ≤ o t
, 0 η = ∞ (i.e. (LR-Adam)). This allows us to
infer using Theorem C.17 that the assumed directional limit point θ̄ = limt→∞ ∥θθtt ∥ of the trajectory is
the direction of a KKT point of the ℓ∞ -max-margin problem. Recall again that (T3) is implied by (T2) if
strengthening (M1-Weak) to (M1).
43

Theorem C.30 (KKT Stationarity for Adam - Implies Theorem 3.6). Let θt be a trajectory of Adam with
c1 ≥ c2 (Equation (8)), under Assumptions (M1-Weak), (M2), (LR-Adam), (T1), (T2), (T3), (A1). Then
the limit point θ̄ of ∥θθtt ∥ is the direction of a KKT point of Problem (11) with ∥·∥ = ∥·∥∞ .
L−1

Proof. First, by assumptions (T1), (T2), it holds (Lemma C.2) that ∥gt ∥1 = Θ(∥θt ∥

L) and in particular

mt
√
vt

≤ C. This and (LReventually gt ̸= 0. By Lemma B.4, denote C = C(c1 , c2 ) > 0 with ∀t :
∞
 1 
t
Adam) imply that dθ
≤ o t L −1 . Therefore by Lemma C.19 with ∥·∥ = ∥·∥∞ , fixing ε > 0, there exist
dt
t→∞

ej (t), e′j (t) −→ 0 with:
∀j ∈ Jε (t) :

p
vt [j] = |gt [j]| (1 + e′j (t)) .

mt [j] = gt [j](1 + ej (t)),

Recalling m̂t = (1 − e−c1 t )−1 mt , v̂t = (1 − e−c2 t )−1 vt , since the bias correction terms themselves tend to 1
t→∞
there exist ej (t) −→ 0 with (reusing the notation ej )
m̂t [j]
∀j ∈ Jε (t) : √
= sign (gt [j]) · (1 + ej (t)) .
v̂t [j]

√
1−e−c2 t
Again since 1−e−c1 t → 1 there exists t1 ≥ 0 with ∀t ≥ t1 : 2C ≥ √m̂v̂t
. Denote Ĉ :=
t ∞
n
o
max 2C, supt∈(0,t1 ] √m̂v̂t
an upper bound on √m̂v̂t
for all t > 0 (the supremum is finite by Lemma B.9).
t

∞

t

For any j ∈
/ Jε (t) it holds that

gt [j]
√
v̂t [j] ∥gt ∥1
m̂t [j]

∞

≤ εĈ. Also,

P

j∈Jε (t) |gt [j]| ≥

P

j∈[p] |gt [j]| − εp ∥gt ∥1

=

∥gt ∥1 (1 − εp). Therefore,


X m̂t [j] gt [j]
X
m̂
sign (gt [j]) gt [j]
gt
√t ,
√
≥
− εĈp =
(1 + ej (t))
− εĈp
∥gt ∥1
∥gt ∥1
v̂t ∥gt ∥1
v̂
[j]
t
j∈Jε (t)
j∈Jε (t)
P
j∈Jε (t) |gt [j]|
≥ min(1 + ej (t)) ·
− εĈp
j
∥gt ∥1
∥gt ∥1 (1 − εp)
≥ min(1 + ej (t)) ·
− εĈp
j
∥gt ∥1
t→∞

−→ 1 − εp − εĈp .

Since this holds for any ε > 0, this implies

lim inf
t→∞

m̂
gt
√t ,
v̂t ∥gt ∥1


≥1.

Therefore,

lim inf

t→∞

Also, since ∥θt ∥∞ ≤

Rt
0

η(s)

m̂s
√
v̂s

∞

ds ≤ Ĉ

Rt
0

1 dθt
gt
,−
η(t) dt
∥gt ∥1


≥1.

η(s)ds it holds that

∥θt ∥
lim sup R t ∞ ≤ Ĉ .
t→∞
η
0
t→∞

Therefore, by Lemma C.15, L(θt ) → 0, ∥θt ∥ → ∞. This in turn implies that ∀j ∈ [p] : |gt [j]| −→ 0 (by


L−1
Equation (25), noting that ∥θt ∥
= o L−1 ), so by Lemma B.10 it follows that in fact
∥θt ∥∞
≤1.
Rt
t→∞
η
0

lim sup

44

Therefore by Theorem C.17 with ν(t) = η(t) we get the result.

C.8

Muon-Adam

Muon-Adam differs from Muon-Signum in that it does not adhere to the definition of normalized momentum
steepest descent (due to the presence of Adam). Therefore the treatment of Muon-Adam relies directly on
the framework of Approximate Steepest Descent, drawing main techniques from both Theorem C.30 and
Theorem C.21. In addition to those, the key technical step is dividing [0, ∞) into times t when the dual norm
has a significant contribution from the ∥·∥1 norm of the gradient w.r.t u, and times when there is a significant
contribution from the ∥·∥snuc norm of the gradient w.r.t W (these subsets may overlap).
Theorem C.31 (KKT Stationarity for Muon-Adam - Implies Theorem 3.7). Assume θ = (W1 , ..., WK , u) =
(W, u) ∈ Rp is a parameter vector representing a collection of matrices and additional parameters u. Assume
W1 , ..., WK follow a trajectory of Muon and u follows a trajectory of Adam, with respective learning rates
of the form η0M η(t), η0A η(t) for η0M , η0A > 0 and momentum parameters cM for Muon and c1 ≥ c2 for Adam.
Assume (M1-Weak), (M2), (LR-Adam), (T1), (T2), (T3), (A1). Then θ̄ = limt→∞ ∥θθtt ∥ is along the direction
of a KKT point of the ∥·∥-max-margin problem (Equation (11)), with
 A

η0
∥θ∥ = max
∥W∥
,
∥u∥
.
msp
∞
η0M
(u)

Proof. Denote gt = (Gt , gt ), Gt = (G1 (t), ..., Gk (t)) the choice of subgradients along the trajectory.
(u) 2

(u)

Denote Mt , µt , ωt the momentum estimates of Gt , gt , gt
with parameters cM , c1 , c2 respectively, and
e t the momentum estimate for the whole gradient vector gt with cM . We retain the notations mt , vt for
m
the momentum estimates of gt , gt2 with c1 , c2 . Denote JM ∪ JA = [p] a partition of [p] into the indices
ηA

0
optimized by Muon and by Adam respectively. Define α = ηM
, ∥·∥α·msp = α∥·∥msp , and its dual norm by
0

∥·∥ 1 ·snuc = α1 ∥·∥snuc . We aim to show that θt is a trajectory of Approximate Steepest Descent with respect
α
to the norm ∥θ∥ = max{∥W∥α·msp , ∥u∥∞ }, ν(t) = η0A η(t) and Rmax ≤ 1. First, by assumptions (T1), (T2),
L−1

it holds (Lemma C.2) that ∥gt ∥⋆ = Θ(∥θt ∥
L) and in particular eventually gt ̸= 0.
First note that we can write the update for Muon and Adam separately as
dWt
∈ η0M η(t) · arg min ⟨W, Mt ⟩ ,
dt
∥W∥msp =1

dut
µ̂t
= −η0A η(t) √ .
dt
ω̂t

But since by definition ∀W, ∥W∥α·msp = α∥W∥msp , we can also write
dWt
∈ η0A η(t) · arg
min
⟨W, Mt ⟩ = η0A η(t) · arg
min
⟨W, Mt ⟩ .
M
η0
dt
∥W∥α·msp =1
∥W∥
=
msp

A
η0

So we consider the optimization of Wt as normalized momentum steepest descent with respect to ∥·∥α·msp
and learning rate ν(t) = η0A η(t). In particular this implies

1 dWt
ν(t) dt

= 1.
α·msp

We observe the quantity of interest for Definition C.12, with the choice of subgradients fixed to be the
subgradients chosen by the momentum:
+ 

 *

(u)
1 dθt
gt
1 dut −gt
1 dWt
Gt
,−
=
,
+
,−
r(t) =
ν(t) dt
∥gt ∥⋆
ν(t) dt ∥gt ∥⋆
ν(t) dt
∥gt ∥⋆
D
E D
E
(46)
(u)
1 dWt
√µ̂t , g
+ ν(t)
t
dt , −Gt
ω̂t
=
.
(u)
∥Gt ∥ 1 ·snuc + gt
α

Our main goal is showing that ess liminf t→∞ r(t) ≥ 1.
45

1

n
o
1
t [j]|
2
Fix 2p
> ε > 0 and denote Jε2 (t) = j ∈ [p] | |g
. Also denote
∥gt ∥ > ε
⋆

(
t≥0|

Tε,M =

∥Gt ∥ 1 ·snuc

α

≥ εp ,

α

∥gt ∥⋆

(u)

Since ∥gt ∥⋆ = ∥Gt ∥ 1 ·snuc + gt

1



(u)


gt
1
≥ εp .
Tε,A = t ≥ 0 |


∥gt ∥⋆

)

(Lemma C.22) and εp < 21 it holds that Tε,M ∪ Tε,A = [0, ∞). By

Lemma C.19 (applied separately with cM and with c1 , c2 ) it holds that there exist vanishing error terms
ej (t) → 0 with
m̂ [j]
pt
= sign (gt [j]) (1 + ej (t)) .
v̂t [j]
P
(u)
We first observe the Adam expression. Notice that by definition gt
= j∈JA |gt [j]|, so it holds for
1
t ∈ Tε,A that
X
X
(u)
(u)
(u)
(u)
(u)
|gt [j]| = gt
−
|gt [j]| ≥ gt
−ε2 p∥gt ∥⋆ ≥ gt
−ε gt
= (1−ε) gt
.
e t [j] = gt [j](1 + ej (t)),
∀j ∈ Jε2 (t) : m

1

j∈Jε2 (t)∩JA

1

j∈JA \Jε2 (t)

1

1

1

The first inequality from the definition of Jε2 (t) and the second from the definition of Tε,A . Denoting
Ĉ = supt∈[0,∞)

√µ̂t
ω̂t

as in the proof of Theorem C.30,
*
+ *
(u)
(u)
1 dut −gt
µ̂t
g
∀t ∈ Tε,A :
,
= √ , t
ν(t) dt ∥gt ∥⋆
ω̂t g(u)
∞

t

1

=

(u)

gt
≥

1

1

1

X m̂t [j]
p
gt [j]
v̂t [j]
j∈JA
m̂ [j]
pt
gt [j] − ε2 Ĉp
v̂
[j]
t
j∈J ∩J 2 (t)
X

(u)
gt

1

1

=

+

A

ε

X

(1 + ej (t)) |gt [j]| − ε2 Ĉp

(u)

gt

1

j∈JA ∩Jε2 (t)

≥ min(1 + ej (t))
j

1
(u)
gt

(u)

gt

(1 − ε) − ε2 Ĉp
1

1

t→∞

−→ 1 − O (ε) .

Where O (·) hides uniform constants independent of t and ε. Also
+
*
(u)
(u)
gt
µ̂t gt
1
√ ,
∀t ∈
/ Tε,A :
≤ Ĉ
≤ Ĉεp = O (ε) .
∥gt ∥⋆
ω̂t ∥gt ∥⋆
Considering the Muon expression, by norm equivalence and by Lemma C.19 (and since Mt − Gt is a subvector
e t − gt ), it holds that
of m
e t − gt ∥∞ ) ≤ O (∥m
e t − gt ∥⋆ ) ≤ o (∥gt ∥⋆ ) .
∥Mt − Gt ∥ 1 ·snuc ≤ O (∥Mt − Gt ∥∞ ) ≤ O (∥m
α

t→∞

1
∥G(t)∥ 1 ·snuc so there exists a vanishing e(t) −→ 0 with
For t ∈ Tε,M it holds that ∥gt ∥⋆ ≤ εp
α

∀t ∈ Tε,M : ∥Mt − Gt ∥ 1 ·snuc ≤ e(t)∥Gt ∥ 1 ·snuc .
α

46

α

1
Note that in particular ∥gt ∥⋆ ≤ εp
∥G(t)∥ 1 ·snuc implies Gt ̸= 0. Since e(t) is vanishing this implies that
α
Mt ̸= 0 for all large enough t ∈ Tε,M . Thus by Lemma C.20, for all large enough t,

Mt
Gt
−
∥Mt ∥ 1 ·snuc
∥Gt ∥ 1 ·snuc

∀t ∈ Tε,M :

α

1 dWt
ν(t) dt

For all t large enough with 2e(t) ≤ ε, since
*
∀t ∈ Tε,M :

1 dWt
Gt
,−
ν(t) dt
∥Gt ∥ 1 ·snuc

+

= 1,
α·msp

*
=1−

α


∀t ∈
/ Tε,M :

≤ 2e(t) .
1
α ·snuc

α

1 dWt
Mt
Gt
,
−
ν(t) dt ∥Mt ∥ 1 ·snuc
∥Gt ∥ 1 ·snuc
α

1 dWt
Gt
,−
ν(t) dt
∥gt ∥⋆


≤

+
≥1−ε ,

α

∥Gt ∥ 1 ·snuc
α

∥gt ∥⋆

< εp .

Now observe any such large enough t. From Equation (46),
D
E D
E
(u)
1 dWt


√µ̂t , g
+
,
−G
t
t
ν(t) dt
gt
1 dθt
ω̂t
,−
=
.
r(t) =
(u)
ν(t) dt
∥gt ∥⋆
∥G ∥ 1
+ g
t

t

α ·snuc

1


(u)
If t ∈ Tε,M \ Tε,A then ∥Gt ∥ 1 ·snuc ≥ (1 − εp)∥gt ∥⋆ = (1 − εp) ∥Gt ∥ 1 ·snuc + gt
α

α

r(t) ≥

(1 − ε)∥Gt ∥ 1 ·snuc − O (ε) ∥Gt ∥ 1 ·snuc
α

α

1
1
·snuc
1−εp ∥Gt ∥ α



, so

1

= 1 − O (ε) .

And similarly if t ∈ Tε,A \ Tε,M . Also, if t ∈ Tε,M ∩ Tε,A then
(u)

r(t) ≥

(1 − ε)∥Gt ∥ 1 ·snuc + (1 − O (ε)) gt
α

∥Gt ∥ 1 ·snuc +
α

(u)
gt

1

≥ 1 − O (ε) .

1

Altogether we have r(t) ≥ 1 − O (ε) for almost all large enough t. Since ε > 0 was arbitrarily small, this
implies
ess liminf r(t) ≥ 1 .
t→∞

∥
R tt .
Denote Rmax = lim supt→∞ ∥θ
η
e
0

As in the proof of Theorem C.30, we first show Rmax is finite and then

that Rmax ≤ 1. Since ∥θt ∥ = max{∥W∥α·msp , ∥u∥∞ } and
lim sup

∥W∥α·msp
≤ 1,
Rt
ν
0

∥u∥
lim sup R t ∞ ≤ Ĉ ,
ν
0
t→∞

It holds that Rmax ≤ Ĉ, so by Lemma C.15 it holds that L(θt ) −→ 0, implying that ∥gt ∥⋆ → 0, so by
∥u∥
Lemma B.10, it holds in fact that lim sup R t ν∞ ≤ 1, so Rmax ≤ 1 as required. Therefore we get the result by
0
Theorem C.17.

47

D

Experimental Details

As mentioned in Section 6, we train two-layer (one hidden layer) homogeneous networks to classify m = 2048
MNIST digits (LeCun et al., 2002) as even or odd, using the exponential loss. We compare squared ReLU
and ReLU, and the following optimizers: Normalized Gradient Descent (NGD) with and without momentum,
Signum, Adam, Muon (treating the output layer as a matrix with a single row) and Muon-Adam. Training
proceeds until the loss reaches a small target value (10−8 ). The stability constant for Adam was chosen to be
negligible with respect to gradient norm values (ε = 10−20 ).
Adam momentum parameters are default (β1 = 0.9, β2 = 0.999) and momentum for other optimizers
is also β = 0.9. Network parameters are initialized using Kaiming (He et al., 2015), with no corrections
for non-linearities, and multiplied by a uniform factor α = 0.01. Initial learning rate values η0 are tuned
per-setting to allow for gradual convergence to the target loss value, according to Table 1.
Table 1: Learning Rates
Activation
ReLU
Squared ReLU

NGD w.o. momentum

NGD

Sign GD

Adam

Muon

Muon-Adam

2.0
1.5

8 × 10−1
3 × 10−1

5 × 10−3
3 × 10−3

6 × 10−3
5 × 10−3

2 × 10−1
8 × 10−2

5 × 10−2
5 × 10−2

max{ W msp, u } Margin

Figure 2 presents results for Muon-Adam (the main results are shown in Figure 1). We observe that
compared to Muon and Adam, Muon-Adam maximizes the norm max{∥W ∥msp , ∥u∥∞ } as expected, where
the matrix W is the first layer and the vector u is the output layer.
101
100
10 1
10 2
10 3
10 4
10 5
10 6
103

100

Muon
Adam
Muon-Adam
10 3 10 6

Loss

Figure 2: Margin values vs. loss for different optimizers. A lighter/darker color signifies the squared-ReLU
/ ReLU activations respectively. Lines are mean values over 10 random seeds, while filled areas are 95%
confidence intervals.

48