A Simple Proof for the Gap Between the Muon and RMNP Descent Directions on Linear Regression

1. Setup

Here I offer a simple example. The corresponding statement for neural networks is much more intricate and requires substantially deeper analysis. The key intuition we want to emphasize is that, for certain weight matrices in neural networks, the descent directions of the two algorithms are asymptotically equivalent. Consider the basic linear-regression loss

whose gradient is $\nabla L = W$. Under this loss, the descent directions of Muon and RMNP are

• Muon: $(WW^T)^{-1/2}\,W$
• RMNP: $\mathrm{diag}(WW^T)^{-1/2}\,W$

The core question is: under random initialization, how large can the gap between these two directions be? Equivalently, we study norms of

Notation.

• $A := WW^T$
• $D := \mathrm{diag}(WW^T)$, with $D_{ii} = |W_{i\ast}|^2$
• $E := A - D$, with $E_{i\ell} = \langle W_{i\ast}, W_{\ell\ast}\rangle$ for $i \neq \ell$

2. Main Theorem

Main theorem. Let $W \in \mathbb{R}^{m \times n}$ with $W_{ij} \stackrel{\text{iid}}{\sim} \mathcal{N}(0,1)$, and keep $m$ fixed. Then there exist positive constants $c_1, c_2, C$, depending only on $m$, such that whenever $n \geq C$:

(A) High-probability operator-norm bound

(B) High-probability Frobenius-norm bound

3. Lemmas

3.1 Balakrishnan integral representation

For any positive definite matrix $X \succ 0$,

Proof. After spectral decomposition, it reduces to the scalar identity

Substitute $t = \lambda u$ to obtain

and use $B(1/2,1/2) = \pi$. $\square$

Reference: Higham, Functions of Matrices (2008).

3.2 A scalar integral

For $a, b > 0$,

Proof. Substitute $t = s^2$, so $dt = 2s\,ds$:

$\square$

3.3 Davidson-Szarek inequality

Let $W \in \mathbb{R}^{m\times n}$ with $m \leq n$ and $W_{ij}\stackrel{\text{iid}}{\sim}\mathcal{N}(0,1)$. For every $t > 0$,

and

Reference: Vershynin, High-Dimensional Probability (2018).

3.4 Laurent-Massart concentration for $\chi^2$

Let $Z \sim \chi^2_n$. For every $x > 0$,

Reference: B. Laurent and P. Massart (2000), Ann. Stat. 28(5), 1302-1338.

3.5 A high-probability event

Define

where $c_0$ depends only on $m$. Then for sufficiently large $n$,

Proof.

(a) Bounds on singular values. Apply Davidson-Szarek from Section 3.3 with $t = \sqrt n/4$. When $n \geq 16m$,

(b) Bounds on row norms. Since $D_{ii} = |W_{i\ast}|^2\sim\chi^2_n$, applying Laurent-Massart from Section 3.4 with $x = n/16$ gives

Taking a union bound over $i = 1, \ldots, m$ yields

(c) A bound on $|E|_{\mathrm{op}}$. Each off-diagonal entry

is a sum of $n$ independent mean-zero sub-exponential random variables. Bernstein’s inequality gives

Choosing $u = c_0’\sqrt n$ with $c_0’$ large enough gives probability at least $1 - e^{-c’n}$. Taking a union bound over the $\binom{m}{2}$ pairs still leaves probability at least $1 - m^2 e^{-c’n}$.

Using the crude bound

with $c_0 = m c_0’$, we conclude the claim.

Finally, combining the three bad events in (a), (b), and (c), each of which has exponentially small probability, shows that for all sufficiently large $n$ their total probability is at most $n^{-2}$. $\square$

3.6 An exact perturbation identity

For positive definite $A, D \succ 0$,

Proof. Apply the Balakrishnan representation from Section 3.1 to both $A$ and $D$, subtract, and use the algebraic identity $X^{-1}-Y^{-1} = -X^{-1}(X-Y)Y^{-1}$ with $X=A+tI$, $Y=D+tI$, and $X-Y=E$. $\square$

3.7 A deterministic operator-norm bound

For all positive definite $A, D \succ 0$,

Proof. Take operator norms in the exact perturbation identity from Section 3.6, use $\lVert XYZ\rVert_{\mathrm{op}}\leq\lVert X\rVert_{\mathrm{op}}\lVert Y\rVert_{\mathrm{op}}\lVert Z\rVert_{\mathrm{op}}$, and then apply the scalar integral from Section 3.2. $\square$

4. Proof of the Main Theorem

4.1 Proof of (A): the operator-norm bound

On the event $\Omega_n$ from Section 3.5,

• $\lambda_{\min}(A) = \sigma_{\min}(W)^2 \geq n/4$
• $\lambda_{\min}(D) \geq n/2$
• $|E|_{\mathrm{op}}\leq c_0\sqrt n$
• $|W|_{\mathrm{op}}\leq 2\sqrt n$

Substituting into the deterministic bound from Section 3.7, the denominator satisfies

so

Since $\Delta = (A^{-1/2}-D^{-1/2})W$, we get

Because $\mathbb{P}(\Omega_n) \geq 1 - n^{-2}$ by Section 3.5, this proves part (A). $\square$

4.2 Proof of (B): the Frobenius-norm bound

The matrix $\Delta$ has size $m\times n$, with $m$ fixed. Hence

Therefore, on $\Omega_n$,

The same probability bound $1-n^{-2}$ then proves part (B). $\square$

5. Conclusion and Discussion

5.1 Summary

All constants $c_i$ depend only on the fixed row dimension $m$, and not on $n$.

5.2 Intuition

Returning to the basic linear-regression loss $L(W) = \tfrac{1}{2}|W|_F^2$, when $n\to\infty$ with $m$ fixed, the Muon descent direction $(WW^T)^{-1/2}W$ and the RMNP descent direction $\mathrm{diag}(WW^T)^{-1/2}W$ become asymptotically identical in probability, with gap size $\Theta(1/\sqrt n)$.

The source of the gap is exactly the off-diagonal part $E$ of $WW^T$. The entry $E_{i\ell} = \langle W_{i\ast}, W_{\ell\ast}\rangle$ measures the correlation between row $i$ and row $\ell$. In high dimension, when $n\gg m$, independent random vectors are nearly orthogonal, so these off-diagonal terms are of relative order $O(1/\sqrt n)$.

The source of the gap is exactly the off-diagonal part $E$ of $WW^T$. The entry $E_{i\ell} = \langle W_{i\ast}, W_{\ell\ast}\rangle$ measures the correlation between row $i$ and row $\ell$. In high dimension, when $n\gg m$, independent random vectors are nearly orthogonal, so these off-diagonal terms are of relative order $O(1/\sqrt n)$.

Intuitively, RMNP normalizes each row independently and produces $m$ unit vectors. Muon then applies a small correction to make them exactly orthogonal. Once pairwise inner products are already of order $O(1/\sqrt n)$, that correction must itself also be of order $O(1/\sqrt n)$.

6. Numerical Experiment

6.1 Experimental setup

• Let $m \in {3, 5, 10, 20}$, and run one experiment for each fixed value of $m$
• For each $m$, let $n$ range over ${50, 100, 200, 500, 1000, 2000, 5000, 10000, 20000}$
• Run 500 Monte Carlo samples for each $(m, n)$ pair
• Sample each $W_{ij}$ independently from $\mathcal{N}(0,1)$
• Compute $(WW^T)^{-1/2}$ by symmetric eigendecomposition: if $WW^T = U\Lambda U^T$, then $(WW^T)^{-1/2} = U\Lambda^{-1/2}U^T$

6.2 Results

$m = 3$:

$m = 5$:

$m = 10$:

$m = 20$:

6.3 Conclusion

For each fixed $m$, both norms are parallel to the reference line $1/\sqrt n$ in log-log coordinates, verifying

The curves for different values of $m$ are themselves parallel to one another, with the same slope $-1/2$ and only different constant factors. This further confirms that the asymptotic regime of “fixed $m$, $n\to\infty$” is independent of the particular value of $m$.

The experimental results match the theoretical prediction exactly.