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

1. Setup

Here I only discuss the simplest possible example. The corresponding statement for neural networks is much more intricate and requires substantially deeper analysis. 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.