Theoretical properties of optimizers on a toy problem, and some intuition

Introduction

We want to answer the question: how do optimizers fundamentally differ in their approach to finding a minimum? To explore this question in a controlled environment, we focus on a simple problem: minimizing the matrix error term $\min \lVert AX - B \rVert$.

This problem serves as a toy task for theoretical exploration because it is tractable, in part due to its simplicity. By assuming the matrix $A$ is symmetric and positive definite (SPD), we guarantee a unique, known solution $X^* = A^{-1}B$, allowing us to measure things quite precisely. The problem is convex, which removes the complexities of local minima and lets us focus purely on the dynamics of convergence --- we make this compromise because non-convexity makes theoretical analysis significantly harder, but in no way does this mean that non-convex problems are not important; most interesting optimization problems are non-convex. Furthermore, by allowing the error $\lVert AX - B \rVert$ to be measured by a wide range of norms (both Schatten and element-wise), we can study how the problem's "shape" influences optimizer performance.

Our analysis centers on a family of what we will informally call "geometric optimizers". These are algorithms whose update direction is determined by normalizing the gradient in a manner according to a chosen matrix norm. This family includes well-known methods like Normalized Gradient Descent (which uses a standard Euclidean "geometry"), the Muon optimizer (which uses a spectral "geometry"), and SignSGD (which uses an element-wise "geometry" and is the special case of Adam without moment accumulation and with $\epsilon = 0$).

The good news is that, for this problem, any optimizer in this family is guaranteed to find the exact solution to this toy problem in a finite amount of time. We show that the total convergence time is bounded and is determined by the relationship between the optimizer's chosen update norm, the problem's loss norm, and $A$. In particular, we will see how Muon's theoretical guarantees on rate uniformity are nicer than Adam's.

This post is structured to build this from the ground up. We will:

• Formally define the optimization problem and the class of geometric optimizers.
• Present a general theorem that provides upper and lower bounds on the convergence time.
• Apply this theorem to Normalized Gradient Descent, Muon, and Adam/SignSGD to derive concrete, comparable performance bounds.
• Using these results and otherwise, discuss the different motivations behind these optimizers and build some intuition about their behavior.

Throughout, we omit momentum and use exact polar factors for Muon. It is important to state at the outset that our analysis is set in an idealized continuous-time framework, which has a lot of simplifications at the very outset (no discrete step size pathologies, no noise, very simple loss landscape). The primary goal is to provide a mathematical lens for understanding why and how different optimizers behave differently. The intuition developed here might serve as a valuable foundation for thinking about their discrete-time and stochastic counterparts used in practice. Be warned, though --- intuition built from toy problems can only go so far.

The Setting

The Optimization Problem

We investigate the following convex optimization problem:

$$\min_{X \in \mathbb{R}^{n \times m}} L(X) \coloneqq \lVert AX - B \rVert_{\alpha}$$

Here, the matrix $A \in \mathbb{R}^{n \times n}$ is assumed to be symmetric and positive definite (SPD). This is an important assumption, implying that $A$ is invertible and all its eigenvalues are strictly positive. The matrices $X \in \mathbb{R}^{n \times m}$ and $B \in \mathbb{R}^{n \times m}$ represent the variable and the target, respectively. The objective function $L(X)$ measures the "size" of the residual matrix $AX - B$ using a chosen matrix norm, $\lVert \cdot \rVert_{\alpha}$. Our analysis covers two primary families of norms: Schatten-p norms and element-wise p-norms.

Since $A$ is invertible, a unique solution $X^*$ exists that makes the residual zero: $AX^* - B = 0$. This solution is $X^* = A^{-1}B$. At this point, the loss function attains its global minimum value of $L(X^*) = \lVert A(A^{-1}B) - B \rVert_{\alpha} = \lVert 0 \rVert_{\alpha} = 0$. The goal of an optimizer is to find this unique solution $X^*$.

Subgradient of the Loss Function

To minimize $L(X)$, we need its gradient. However, neither norm family is differentiable at zero, and for $p = 1$ or $p = \infty$ they can also be nondifferentiable at nonzero matrices. For $1 < p < \infty$, both are differentiable away from zero. We therefore use the more general concept of the subgradient.

The subgradient of a convex function $f$ at a point $x$ is a vector $g$ such that $f(y) \ge f(x) + g^T(y-x)$ for all $y$. The set of all such vectors is called the subdifferential, denoted $\partial f(x)$. For our loss function $L(X) = h(g(X))$ where $h(Z) = \lVert Z \rVert_{\alpha}$ and $g(X) = AX - B$, the chain rule for subdifferentials states that $\partial_X L(X) = A^T \partial_Z h(AX-B)$.

Let $\lVert \cdot \rVert_\delta$ be the dual norm to the loss norm $\lVert \cdot \rVert_\alpha$. (If $\alpha$ is $S_p$, $\delta$ is $S_q$; if $\alpha$ is $e,p$, $\delta$ is $e,q$). Almost by definition of the dual norm (which we give later), the subdifferential of the norm $\lVert \cdot \rVert_\alpha$ at a matrix $Z \neq 0$ is given below, where ($\langle S, Z \rangle_F = \text{Tr}(S^T Z)$ is the standard Frobenius inner product):

$$\partial_Z \lVert Z \rVert_{\alpha} = \{ S \in \mathbb{R}^{n \times m} \mid \lVert S \rVert_{\delta} = 1 \text{ and } \langle S, Z \rangle_F = \lVert Z \rVert_{\alpha} \}$$

At $Z=0$, the subdifferential is instead $\{S: \lVert S \rVert_\delta \le 1\}$.

Consequently, the subdifferential of our loss function $L(X)$ (for $X \neq X^*$) is: $$\partial_X L(X) = \{ A^T S \mid S \in \mathbb{R}^{n \times m}, \lVert S \rVert_{\delta} = 1, \langle S, AX-B \rangle_F = \lVert AX-B \rVert_{\alpha} \}$$ Since our matrix $A$ is symmetric, $A^T = A$. For the purpose of analyzing a continuous-time gradient flow, we can consider an optimizer that, at each time $t$, selects one specific subgradient $G_t \in \partial_X L(X_t)$ to determine its direction.

The Family of Geometric Optimizers

We define a family of optimizers based on the principle of continuous steepest descent. The direction of steepest descent depends on the geometry of the underlying space, which we define by choosing a norm, $\lVert \cdot \rVert_\beta$, on the space of matrices $\mathbb{R}^{n \times m}$.

It is left to the curious reader to verify that such a mapping is indeed a norm, and all the properties of dual norms mentioned in the previous section.

A Convergence Theorem

Convergence Bounds for Specific Scenarios

We now instantiate the general result of Theorem 3.1 for three specific optimizers. The idea is to derive bounds for $C_{\text{lower}}$ and $C_{\text{upper}}$.

The following lemmas on norm equivalence, which are direct consequences of the generalized mean inequality, will be useful.

Normalized Gradient Descent

We will consider the variant of Normalized Gradient Descent (NGD) which divides the gradient throughout by its Frobenius norm. That is,

$$\frac{dX_t}{dt} = -\eta \frac{G_t}{\lVert G_t \rVert _F}$$

Let's try to identify the geometry of the optimizer. The dual norm is $\lVert G_t \rVert _\gamma = \langle G_t, \frac{G_t}{\lVert G_t \rVert _F} \rangle_F = \lVert G_t \rVert _F$. Since the Frobenius norm is self-dual, the optimizer's defining norm is also Frobenius.

Case 1: Schatten-p Norm Loss

Here $\lVert \cdot \rVert_\alpha = \lVert \cdot \rVert_{S_p}$ and its dual is $\lVert \cdot \rVert_\delta = \lVert \cdot \rVert_{S_q}$. Since both $\gamma$ and $\delta$ are Schatten norms, we use the direct analysis.

Case 2: Element-wise p-Norm Loss

The proof is perfectly analogous to the Schatten case, but since the loss norm is element-wise, we will use the Frobenius-bridging method. The bounds for $\lVert S \rVert_F$ are found using Lemma 4.3, which replaces $k$ with $mn$.

Muon

Note that Muon orthogonalizes the gradient, i.e., if $G_t = U_t \Sigma_t V_t^T$ is a compact SVD containing only positive singular values, then $\frac{dX_t}{dt} = -\eta \cdot U_t V_t^T$. At rank-deficient points, the full dualizer also allows $U_t V_t^T + W$ with $U_t^T W = 0$, $WV_t = 0$, and $\lVert W \rVert_{S_\infty} \le 1$. Let's try to see whether this fits into our definition. The dual norm would be $\lVert G_t \rVert _\gamma = \langle U_t \Sigma_t V_t^T, U_t V_t^T \rangle_F = \text{Tr}(V_t U_t^T U_t \Sigma_t V_t^T) = \text{Tr}(V_t \Sigma_t V_t^T) = \text{Tr}(\Sigma_t) = \lVert G_t \rVert _*$. So the dual norm is the Nuclear norm ($S_1$). Hence the defining norm is the spectral norm ($S_\infty$).

Case 1: Schatten-p Norm Loss

Here, the loss norm is $\lVert \cdot \rVert_\alpha = \lVert \cdot \rVert_{S_p}$ and its dual is $\lVert \cdot \rVert_\delta = \lVert \cdot \rVert_{S_q}$. Both the optimizer's dual norm ($\gamma=S_1$) and the loss's dual norm ($\delta=S_q$) are Schatten norms, so we use the direct analysis for a tighter bound.

Case 2: Element-wise p-Norm Loss

Here $\lVert \cdot \rVert_\alpha = \lVert \cdot \rVert_{e,p}$, so $\lVert \cdot \rVert_\delta = \lVert \cdot \rVert_{e,q}$. The optimizer's dual norm is $\gamma=S_1$. This is a mixed-norm case, so we use the Frobenius bridge.

Adam/SignSGD

As usual, let's try to see whether this algorithm fits in our formulation. The update is $\frac{dX_t}{dt} = -\eta \cdot \text{sign}(G_t)$. The dual norm would be $\lVert G_t \rVert _\gamma = \langle G_t, \text{sign}(G_t) \rangle _F = \text{Tr}(G_t^T \text{sign}(G_t)) = \lVert G_t \rVert_{e, 1}$, the element-wise $L_1$ norm. The geometry is thus induced by the element-wise $L_\infty$ norm, $\lVert \cdot \rVert_{e, \infty}$.

Case 1: Schatten-p Norm Loss

Here $\lVert \cdot \rVert_\alpha = \lVert \cdot \rVert_{S_p}$ and $\lVert \cdot \rVert_\delta = \lVert \cdot \rVert_{S_q}$. This is a mixed-norm case.

Case 2: Element-wise p-Norm Loss

Here $\lVert \cdot \rVert_\alpha = \lVert \cdot \rVert_{e,p}$, so $\lVert \cdot \rVert_\delta = \lVert \cdot \rVert_{e,q}$.

A Note on Bound Tightness and Rate Variation

This note analyzes two key properties of the derived bounds: the potential variation in the convergence rate and the conditions under which the bounds are tight.

Analysis of Rate Variation

The ratio $C_{\text{upper}} / C_{\text{lower}}$ measures the stability of the convergence rate. A value near one implies a nearly constant rate, while a large value indicates substantial possible variation (both in the current path as well as distinct starting guesses). Let's analyze this for the direct Schatten-Schatten analysis, for example, Muon ($\gamma=S_1$) with Schatten loss ($\delta=S_q$). Write $\kappa(A) = \lambda_{\max}(A) / \lambda_{\min}(A)$.

$$\frac{C_{\text{upper}}}{C_{\text{lower}}} \le \kappa(A) k^{1/p}$$

In this case, the bound on rate variation depends on the conditioning of $A$ and a dimensional factor related to the loss geometry. For the more complex bridged analyses, the ratio bound will also include factors from the norm equivalences used. The general structure holds: the bound on rate variation is a product of contributions from the problem's conditioning ($\kappa(A)$), the optimizer's geometry, and the loss function's geometry. In general, the closer the problem geometry is to the optimizer, the better the convergence guarantees there will be --- after all, we are doing some kind of steepest descent under some matrix norm.

Let's compare this to the corresponding bound for the Adam case:

$$\frac{C_{\text{upper}}}{C_{\text{lower}}} \le \kappa(A)\sqrt{mn}\,k^{|1/p - 1/2|}$$

For any Schatten-p norm, we see that Muon gives better convergence guarantees (according to our analysis) as compared to Adam, though it should be kept in mind that the bounds may have different amounts of slack. More precisely, Adam's ratio bound divided by Muon's is $\sqrt{mn/k}$ for $1 \le p \le 2$, and $\sqrt{mn/k}\,k^{1-2/p}$ for $2 \le p \le \infty$.

For element-wise $p$-norm loss, the corresponding comparison is $$\left(\frac{C_{\text{upper}}}{C_{\text{lower}}}\right)_{\text{Muon}} \le \kappa(A) \sqrt{k}\,(mn)^{|1/p - 1/2|},\qquad \left(\frac{C_{\text{upper}}}{C_{\text{lower}}}\right)_{\text{Adam}} \le \kappa(A) \sqrt{mn}\,(mn)^{|1/p-1/2|}.$$

Here Adam's ratio bound divided by Muon's is $\sqrt{mn/k} = \sqrt{\max(n,m)}$ for every $p$, so our analysis again favors Muon. In the scalar case, the bounds coincide.

Analysis of Bound Tightness

We now investigate whether our bounds on $C_{\text{lower}}$ and $C_{\text{upper}}$ are achievable.

Case 1: Schatten-Schatten Analysis (Direct)

This case applies when both the optimizer's dual norm ($\gamma$) and the loss's dual norm ($\delta$) are Schatten norms (e.g., Muon with Schatten-p loss). The analysis uses the direct inequality $\lambda_{\min}(A)\lVert S \rVert_{\gamma} \le \lVert AS \rVert_{\gamma} \le \lambda_{\max}(A)\lVert S \rVert_{\gamma}$ followed by a norm equivalence bound.

Lower Bound ($C_{\text{lower}}$): Our bound is $C_{\text{lower}} \ge \lambda_{\min}(A) \inf_{\lVert S\rVert _{\delta}=1} \lVert S \rVert_\gamma$. To achieve this bound, a single matrix $S$ must satisfy two conditions simultaneously:

• $\lVert AS \rVert_\gamma = \lambda_{\min}(A) \lVert S \rVert_\gamma$: This is achieved if the columns of $S$ lie in an eigenspace of $A$ associated with the minimum eigenvalue, $\lambda_{\min}(A)$. For example, if $S=uv^T$ where $u$ is a unit eigenvector for $\lambda_{\min}(A)$ and $v\in\mathbb R^m$ is any unit vector.
• $S$ must be a matrix that achieves the infimum of $\lVert S \rVert_\gamma$ over the unit sphere of $\lVert \cdot \rVert_\delta$. For Muon ($\gamma=S_1$) and any Schatten loss ($\delta=S_q$), this infimum is 1 and is achieved by any rank-one matrix.

This rank-one matrix $S=uv^T$ satisfies both conditions for Muon. Therefore, the lower bound is tight.

Upper Bound ($C_{\text{upper}}$): Our bound is $C_{\text{upper}} \le \lambda_{\max}(A) \sup_{\lVert S\rVert _{\delta}=1} \lVert S \rVert_\gamma$. This requires a matrix $S$ to satisfy:

• $\lVert AS \rVert_\gamma = \lambda_{\max}(A) \lVert S \rVert_\gamma$: For Muon, this requires the columns of $S$ to lie in the eigenspace of $\lambda_{\max}(A)$.
• $S$ must achieve the supremum of $\lVert S \rVert_\gamma$ over the unit sphere of $\lVert \cdot \rVert_\delta$. For Muon ($\gamma=S_1$, $\delta=S_q$), this supremum is $k^{1/p}$ and is achieved by a rank-$k$ matrix whose singular values are all equal (a "spectrally flat" (or whitened) matrix).

For finite $p$, this is achievable if the eigenspace of $\lambda_{\max}(A)$ is large enough (i.e., its multiplicity is at least $k=\min(n,m)$) to construct a spectrally flat, rank-$k$ matrix within it. If $\lambda_{\max}(A)$ is a simple (non-repeated) eigenvalue, this is generally not possible for $k>1$. Thus, the upper bound is tight under certain conditions on $A$, but may be conservative otherwise. For $p=\infty$, the two norms coincide, so a rank-one matrix suffices and the bound is always tight.

Case 2: Element-wise/Element-wise Analysis (Bridged)

This case applies to Adam/SignSGD with an element-wise p-norm loss. The analysis uses the Frobenius norm as a bridge.

Lower Bound ($C_{\text{lower}} \ge \lambda_{\min}(A) \inf_{\lVert S\rVert _{e,q}=1} \lVert S \rVert_F$):

• $\lVert AS\rVert_{e,1}=\lVert AS\rVert_F$: Requires $AS$ to have only one non-zero entry.
• $\lVert AS \rVert_F = \lambda_{\min}(A) \lVert S \rVert_F$: Requires the columns of $S$ to lie in the eigenspace of $\lambda_{\min}(A)$.
• $S$ must achieve $\inf_{\lVert S\rVert _{e,q}=1} \lVert S \rVert_F$. For $q>2$, this is achieved by a matrix with only one non-zero entry (an extremely sparse matrix, e.g., $S=E_{ij}$). For $q<2$, all $mn$ entries must have equal absolute value, and for $q=2$, the Frobenius norm is constant on this sphere.

For $q \ge 2$, the bound is tight only if a coordinate vector $e_i$ is an eigenvector of $A$ for $\lambda_{\min}(A)$. For $q<2$ and $mn>1$, the single-entry and dense requirements conflict, making the lower bound strict.

Upper Bound ($C_{\text{upper}} \le \sqrt{mn}\lambda_{\max}(A) \sup_{\lVert S\rVert _{e,q}=1} \lVert S \rVert_F$):

• $\lVert AS\rVert_{e,1}=\sqrt{mn}\lVert AS\rVert_F$: Requires all entries of $AS$ to have the same absolute value.
• $\lVert AS \rVert_F = \lambda_{\max}(A) \lVert S \rVert_F$: Requires the columns of $S$ to lie in the eigenspace of $\lambda_{\max}(A)$.
• $S$ must achieve $\sup_{\lVert S\rVert _{e,q}=1} \lVert S \rVert_F$. For $q>2$, this is achieved by a matrix whose entries all have the same absolute value (a "dense" matrix, like the all-ones matrix $J$). For $q<2$, only one entry can be non-zero; for $q=2$, the Frobenius norm is constant on this sphere.

For $q\ge2$, this is tight only if the columns of a matrix of constant-magnitude entries (like $J$) lie in the maximum-eigenvalue eigenspace of $A$. This is true for highly structured matrices (e.g., $A=c_1I+c_2J_n$ with $c_1>0$, $c_2\ge0$, and $J_n$ the $n\times n$ all-ones matrix) but not for general $A$. For $q<2$ and $mn>1$, the equality conditions conflict, so the upper bound is strict.

Case 3: Mixed-Norm Analysis (Bridged) This case applies to Adam/SignSGD with Schatten loss or Muon with element-wise loss. The analysis involves inequalities bridging between Schatten and element-wise norms (e.g., $\lVert Z \rVert_{e,1} \le \sqrt{mn} \lVert Z \rVert_F$ or $\lVert Z \rVert_F \le \lVert Z \rVert_*$).

Lower Bound ($C_{\text{lower}}$): Consider Adam/SignSGD with Schatten loss, where $C_{\text{lower}} \ge \lambda_{\min}(A) \inf_{\lVert S\rVert _{S_q}=1} \lVert S \rVert_F$.

• $\lVert AS\rVert_{e,1}=\lVert AS\rVert_F$: Requires $AS$ to have only one non-zero entry.
• $\lVert AS \rVert_F = \lambda_{\min}(A) \lVert S \rVert_F$: Requires the columns of $S$ to be in the $\lambda_{\min}(A)$ eigenspace.
• $S$ must achieve $\inf_{\lVert S\rVert _{S_q}=1} \lVert S \rVert_F$. This requires $S$ to be rank-one (if $q>2$) or to have $k$ equal singular values (if $q<2$); at $q=2$, the Frobenius norm is constant on this sphere.

For $q\ge2$, the bound is tight when a coordinate vector lies in the $\lambda_{\min}(A)$ eigenspace, so that all three conditions hold at the same matrix. For $q<2$ and $k>1$, the spectral-flatness requirement conflicts with the single-entry requirement, making this lower bound strict.

Upper Bound ($C_{\text{upper}}$): Consider Adam/SignSGD again, with the bound $C_{\text{upper}} \le \sqrt{mn} \lambda_{\max}(A) \sup_{\lVert S\rVert _{S_q}=1} \lVert S \rVert_F$.

• $\lVert AS \rVert_{e,1} \le \sqrt{mn} \lVert AS \rVert_F$: The first bridging step. Equality requires all entries of $AS$ to have equal absolute magnitude.
• $\lVert AS \rVert_F \le \lambda_{\max}(A) \lVert S \rVert_F$: The spectral bound. Equality requires the columns of $S$ to be in the $\lambda_{\max}(A)$ eigenspace.
• $S$ must maximize $\lVert S\rVert_F$ on the Schatten-$q$ unit sphere. This requires rank one for $q<2$, $k$ equal singular values for $q>2$, and imposes no additional condition at $q=2$.

This requires all three equalities at the same matrix $S$. Requiring its columns to lie in the $\lambda_{\max}(A)$ eigenspace while satisfying both entrywise and spectral conditions can make the bound conservative. For Muon with element-wise loss, the same reasoning applies: equality in $\lVert Z\rVert_F\le\lVert Z\rVert_*$ requires rank one, while equality in $\lVert Z\rVert_*\le\sqrt{k}\lVert Z\rVert_F$ requires $k$ equal singular values.

In summary, the direct analysis for matching Schatten norms avoids additional norm conversions. An analysis that must bridge between element-wise and Schatten "geometries" introduces additional, potentially conflicting requirements, leading to bounds that are more likely to be conservative estimates. Equality in a convergence-time bound also requires the extremal rate to persist almost everywhere along the trajectory.

Using This In Practice: A Comparison of Optimizers

The theoretical framework developed provides another lens through which to compare familiar optimization algorithms. By understanding their underlying geometry, we can move beyond empirical performance and attempt to reason about why they behave differently.

Let us reiterate the warning from the beginning - intuition built from toy problems can only go so far.

The Problem with Vanilla Gradient Descent on the Squared Loss

Standard Gradient Descent (GD) does not belong to the family of "geometric optimizers" analyzed here. Its continuous-time flow is given by:

$$\frac{dX_t}{dt} = -\eta G_t = -\eta A S_t$$

For the unsquared loss studied here, $\lVert G_t\rVert_F$ is bounded away from zero before arrival, by Theorem 3.1 with $\beta=F$. Since $dL/dt=-\eta\lVert G_t\rVert_F^2$ almost everywhere, ordinary subgradient flow also reaches the solution in finite time. For the unsquared Frobenius loss, $G_t=A(AX_t-B)/\lVert AX_t-B\rVert_F$.

Notice the absence of the $\text{dualizer}$ map. The update magnitude is directly proportional to the norm of the gradient, $\lVert G_t \rVert$. For a squared norm loss, as the optimizer approaches the solution $X^*$, the residual $AX_t-B$ shrinks, causing the gradient norm to approach zero. This leads to ever-slowing convergence.

For the classic case of the squared Frobenius loss $\tfrac12\lVert AX-B\rVert_F^2$, the gradient is $G_t = A(AX_t - B)$. The flow becomes a linear ODE, whose exact solution is:

$$X_t - X^* = e^{-A^2 \eta t} (X_0 - X^*)$$

This explicitly shows that the error term decays exponentially but only vanishes as $t \to \infty$. On this squared loss, standard GD offers infinite-time asymptotic convergence for nonzero initial error.

Geometric Optimizers as the Solution

The geometric optimizers studied in this post --- NGD, Muon, and Adam/SignSGD --- all "fix" this problem of vanishing updates for the squared loss. Their normalized flows for $L$ and $\tfrac12L^2$ agree away from the minimum, because positive rescaling of a nonzero gradient does not change its dualizer. They achieve this by normalizing the gradient, ensuring the update step has a constant size with respect to a norm. The update rule $\frac{dX_t}{dt} = -\eta \cdot \text{dualizer}_{\lVert \cdot \rVert_\beta}(G_t)$ has the property that $\lVert \frac{dX_t}{dt} \rVert_\beta = \eta$, a constant. Together with the descent identity and positive lower rate bound, this fixed-size progress in the chosen norm forces the optimizer to reach the zero-loss solution in a finite amount of time. However, fixed discrete step sizes can cause oscillations: even $x_{j+1}=x_j-h\mathrm{sign}(x_j)$ with $h>0$ cycles between $h/2$ and $-h/2$ when started at $h/2$. Discrete convergence requires a separate step-size or stopping analysis.

Comparing the structure for Normalized Gradient Descent, Muon, and Adam/SignSGD

While all three ensure finite-time convergence, their performance characteristics, revealed by the convergence bounds, are quite different because they are associated with different norms.

• Normalized Gradient Descent (NGD): This optimizer uses a Euclidean norm ($\beta=F$). It normalizes the entire gradient matrix $G_t$, scaling it down to have a Frobenius norm of 1. It scales all entries and all singular values of the gradient by the same factor, preserving their relative sizes. It is a good baseline but may be blind to more nuanced structures in the problem.

• Muon: This optimizer uses the spectral norm ($\beta=S_\infty$). If the gradient has a compact SVD of $G_t = U\Sigma V^T$, the update direction is the matrix $-UV^T$. This update is a partial isometry that encapsulates the "pure orientation" of the gradient, stripped of all singular value scaling. It's a whitened update that respects the singular vector spaces of the gradient. This makes it highly sensitive to the spectral properties of the error, treating every singular direction present in the gradient with equal update magnitude.

• SignSGD and Adam: The optimizer uses an element-wise norm ($\beta=e,\infty$, so $\gamma=e,1$). Its dualizer is the element-wise sign function, so every nonzero-gradient entry of the update is either $+1$ or $-1$ (scaled by $\eta$), with zero entries handled as in Remark 4.8. This geometry considers each matrix entry independently, which may be useful when the relevant structure is coordinate-wise rather than spectral.

A final note on momentum. While we have not studied it here, momentum can be added to any of these gradient flows by adding a coupled differential equation. It often accelerates convergence but can also introduce oscillations, as it gives the optimizer "mass" and inertia. It is possible to do such an analysis but we will leave it for another time, since it is mathematically much more involved. Gabriel Goh's article on momentum at distill.pub explains the key intuitions around momentum quite well, explaining how suitably tuned momentum on positive-definite quadratic objectives can improve the convergence-rate dependence on the Hessian condition number from $\kappa_H$ to $\sqrt{\kappa_H}$.

The Nature of the Updates

The choice of the geometry dictates the very structure of the update direction, $\dot X_t = -\eta \cdot \text{dualizer}(G_t)$ before arrival.

• Muon (with $\beta=S_\infty$, $\gamma=S_1$) produces a spectrally flat update matrix on the active singular subspaces, $UV^T$, where $G_t=U\Sigma V^T$. This update preserves the singular vector spaces of the gradient but replaces all non-zero singular values with 1. For a compact SVD, it is a partial isometry with the same rank as the gradient, and is orthogonal in the square full-rank case. It captures the gradient's orientation without preferentially scaling any active spectral direction.

• Adam/SignSGD (with $\beta=e,\infty$, $\gamma=e,1$) produces an update matrix whose entries at nonzero-gradient coordinates are all $\pm \eta$. It modifies every parameter with a nonzero gradient, with the magnitude of the change being independent of the magnitude of the gradient for that entry.

• NGD (with $\beta=F$, $\gamma=F$) produces an update of the same rank as the gradient that is a scaled version of it, preserving its relative structure completely.

However, in practice, this is a different situation (this is also why we should take all intuition from toy problems with a grain of salt). The gradients $G_t$ used by standard methods like SGD or Adam are often empirically ill-conditioned or "spectrally spiky". This means their singular value spectrum is dominated by a few very large values, with a long tail of small ones, making the gradient matrix effectively low-rank. Adam/SignSGD's approach is to bet on element-wise whitening, which does not generally remove this spectral imbalance. Muon explicitly performs the spectral whitening (i.e., orthogonalization) which discards information from the singular values and updates based on all active singular vectors equally --- the idea is to increase the contribution of rare but nevertheless important directions.

Also note that since the weights themselves are EMAs of updates with weight decay, this might also lead to more effective use of the capacity of the network if the weight decay is too fast.

Building Intuition from the Convergence Bounds

The bounds derived in Theorem 3.1 and instantiated in Section 4 can provide some intuition about how to choose and reason about optimizers.

The Meaning of $C_{\text{lower}}$ and $C_{\text{upper}}$

The main result gives $T_{\text{final}}=L(X_0)/(\eta\bar C)$ for positive convergence time, where $\bar C$ is the time average of $C(t)=\lVert AS_t\rVert_\gamma$. $C$ can be thought of as a speed. Specifically, $C = \lVert AS \rVert_\gamma$ measures the loss-decay speed divided by $\eta$, using the optimizer's dual norm ($\gamma$), given a unit-sized residual subgradient $S$ in the loss's dual geometry ($\delta$).

The constants $C_{\text{lower}}$ and $C_{\text{upper}}$ represent the worst-case and best-case scenarios for this rate.

• $C_{\text{lower}}$ is the slowest possible rate of convergence. A large $C_{\text{lower}}$ gives a strong worst-case guarantee.
• $C_{\text{upper}}$ is the fastest possible rate. It tells you the best you can hope for.

Rate Stability and Comparing Optimizers

The ratio $C_{\text{upper}} / C_{\text{lower}}$ is a measure of the stability or robustness of the convergence rate across error directions. It is independent of the learning rate.

• A ratio close to 1 means the optimizer makes steady, predictable progress regardless of the specific error structure at any given time/state, or the starting-point.
• A large ratio implies the convergence can be highly variable: sometimes very fast, sometimes very slow. This happens when the optimizer's geometry is poorly matched to certain error structures.

When comparing two optimizers, vaguely speaking, one can normalize the learning rate $\eta$ such that their upper loss-decay rates match, e.g., $\eta C_{\text{upper}} = 1$ (or make some measure of an average $\eta C$ or some norm of the update equal for both). The comparison then boils down to which one has a larger normalized lower rate, $\eta C_{\text{lower}}=C_{\text{lower}}/C_{\text{upper}}$. The optimizer with the better worst-case guarantee (lower rate) is often preferable, as it is more reliable. For instance, our analysis for Schatten loss bounds the rate variation for Muon by $\kappa(A)k^{1/p}$, while the corresponding (though potentially looser) bound for Adam/SignSGD includes additional factors, suggesting Muon's convergence rate might be more stable (or just have better mathematical properties). In the case of $p = 2$, the ratio bounds are $\kappa(A)\sqrt{k}$ for Muon and $\kappa(A)\sqrt{mn}$ for Adam, so Muon has the better guarantee from these estimates. For Schatten-$\infty$ loss, Muon's bound is $\kappa(A)$, approaching one as $\kappa(A)$ approaches one.

Also, ideally, if you know the geometry of the problem, the choice of the optimizer should be directly derived from that. If not, it may be chosen in a way that does not have a lot of deviation at any given point from the actual geometry of the problem, in some sense. The ideal ratio is one: this occurs precisely when $\lVert AE\rVert_\alpha=c\lVert E\rVert_\beta$ for all error matrices $E$, for some $c>0$, by duality. In light of the smaller ratio bounds derived here, in particular for the Schatten geometry with large $p$, the spectral norm (and hence Muon) seems to be a good choice among the geometries considered.

Appendix: existence of the set-valued flow

We prove existence for the flow in Definition 2.5. Write $c=C_{\text{lower}}$, $C=C_{\text{upper}}$, and $\Psi(V)=\tfrac12\lVert V\rVert_\beta^2$. First construct an auxiliary curve satisfying $$G(s)\in\partial L(Y(s)),\qquad -G(s)\in\partial\Psi(\dot Y(s)).$$

Here is a finite-dimensional construction. For a convex function $f$, let $f_\varepsilon(x)=\inf_y\{f(y)+\lVert x-y\rVert_F^2/(2\varepsilon)\}$ be its Euclidean Moreau envelope. Regularize the loss to $L_\varepsilon$ and the dissipation to $\Psi_\varepsilon=\mathrm{env}_\varepsilon\Psi+\tfrac\varepsilon2\lVert\cdot\rVert_F^2$. Both are continuously differentiable, and $\Psi_\varepsilon$ is strongly convex. Hence the Lipschitz ordinary differential equation $$\dot Y_\varepsilon=\nabla\Psi_\varepsilon^*(-\nabla L_\varepsilon(Y_\varepsilon)),\qquad Y_\varepsilon(0)=X_0$$ has a global solution. Here the star denotes convex conjugacy.

Put $G_\varepsilon=\nabla L_\varepsilon(Y_\varepsilon)$. Global Lipschitz continuity of $L$ bounds $G_\varepsilon$ uniformly. Norm equivalence gives a uniform quadratic lower bound on $\Psi_\varepsilon$ for sufficiently small $\varepsilon$. Its degree-two homogeneity and the equation give $2\Psi_\varepsilon(\dot Y_\varepsilon)=\langle-G_\varepsilon,\dot Y_\varepsilon\rangle_F$, which bounds the velocities uniformly. Thus, on each finite interval, a subsequence converges uniformly to $Y$, with velocities and $G_\varepsilon$ converging weakly in $L^2$ to $\dot Y$ and $G$.

The proximal points $P_\varepsilon=Y_\varepsilon-\varepsilon G_\varepsilon$ satisfy $G_\varepsilon\in\partial L(P_\varepsilon)$ and converge uniformly to $Y$. Integrating their subgradient inequalities on arbitrary time subsets and passing to the limit gives $G\in\partial L(Y)$ almost everywhere. The regularized energy equality is $$L_\varepsilon(Y_\varepsilon(b))+ \int_0^b[\Psi_\varepsilon(\dot Y_\varepsilon)+\Psi_\varepsilon^*(-G_\varepsilon)]\,ds =L_\varepsilon(X_0).$$ The regularizations and dissipation conjugates converge uniformly on bounded sets. Weak lower semicontinuity of convex integrals therefore yields $$L(Y(b))+\int_0^b[\Psi(\dot Y)+\Psi^*(-G)]\,ds\le L(X_0).$$ The chain rule from the main proof rewrites this as an integral of $\Psi(\dot Y)+\Psi^*(-G)+\langle G,\dot Y\rangle_F$ being nonpositive. Fenchel's inequality makes this integrand nonnegative, so equality holds almost everywhere and $-G\in\partial\Psi(\dot Y)$. A diagonal subsequence over finite intervals supplies a global auxiliary curve.

Since $\Psi^*(G)=\tfrac12\lVert G\rVert_\gamma^2$, equality in Fenchel's inequality gives $$\lVert\dot Y\rVert_\beta=\lVert G\rVert_\gamma,\qquad \dot Y=-\lVert G\rVert_\gamma Z,\quad Z\in D_\beta(G).$$ Before arrival, $c\le\lVert G\rVert_\gamma\le C$ and $dL(Y)/ds=-\lVert G\rVert_\gamma^2\le-c^2$. Thus the auxiliary curve reaches the minimum in finite time. Reparametrize by $$t(s)=\eta^{-1}\int_0^s\lVert G(u)\rVert_\gamma\,du.$$ This has an absolutely continuous inverse before arrival, and $X(t)=Y(s(t))$ satisfies $\dot X=-\eta Z$. Stop at the minimum. This proves the required existence and also supplies ordinary subgradient-flow existence by taking $\beta=F$.

Further reading

On the topic of metrized deep learning, a good introduction is the survey here - I would highly recommend doing a breadth-first search through all the references mentioned there to understand the main ideas better.

After I wrote this post, someone pointed out this paper which also talks about Muon's convergence rate (discrete steps, non-convex problems, but not necessarily finite-time) to approximate stationary points and compares it to gradient descent.

Acknowledgements

I would like to thank Gemini for helping me with writing up parts of this post after I gave it my work and initial drafts.

Cite this post

@online{optimizers-toy-problem-2025,
  author    = {nor},
  title     = {Theoretical properties of optimizers on a toy problem, and some intuition},
  year      = {2025},
  month     = {08},
  day       = {02},
  url       = {https://nor-blog.pages.dev/posts/2025-08-02-optimizers-toy-problem},
}