Muon learns balanced solutions in matrix factorization without slow saddle-to-saddle dynamics

• URL: http://arxiv.org/abs/2606.30509v1
• Date: Mon, 29 Jun 2026 16:17:38 GMT
• Title: Muon learns balanced solutions in matrix factorization without slow saddle-to-saddle dynamics
• Abstract summary: Matrix factorization is a problem of the form $min_mathbfP,mathbfQ |mathbfMstar - mathbfPtopmathbfQ|_mathrmF2$.<n>We study how trajectories under the Muon parameter differ from those of gradient descent.
• Score: 0.9798289347944394
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix factorization (i.e., problems of the form $\min_{\mathbf{P},\mathbf{Q}} \|\mathbf{M}^\star - \mathbf{P}^\top\mathbf{Q}\|_\mathrm{F}^2$) is a minimal learning problem that exhibits both nonlinear parameter dynamics and representation learning. In this setting, we study how parameter trajectories under the Muon optimizer differ from those of gradient descent. We identify three main dynamical differences: 1) Muon avoids the slow saddle-to-saddle dynamics from small initialization. Muon instead learns all the top modes of $\mathbf{M}^\star$ at the same rate, with the smaller modes converging first. 2) Muon remains stable even when the learning rate exceeds the critical threshold set by the local loss sharpness. This frees the learning rate from the condition number of the problem, enabling rapid convergence via exponential learning rate annealing. 3) Once the weights are aligned with each other and the target, Muon flow conserves the matrix quantity $\sqrt{\mathbf{P}^\top \mathbf{P}}-\sqrt{\mathbf{Q}^\top \mathbf{Q}}$, while gradient flow is known to conserve the matrix $\mathbf{P}^\top\mathbf{P} - \mathbf{Q}^\top\mathbf{Q}$. Despite having distinct conserved quantities, both optimizers find the so-called \textit{balanced} solution from vanishing initialization. When training from small random initialization, the weights spontaneously align early in training. We derive the alignment rates in simple settings and show that they predict the empirical alignment rates in general. Finally, we exploit structural properties of Muon to construct a learning rate schedule that achieves near-perfect alignment in only two optimization steps.

Related papers

• Low-Rank Prompt Learning for Vision-Language Models with Fixed-Token Bases [11.437689514839333]
  We study a dense prompt matrix $mathbfPinmathbbRmtimes d$ trained from only a few examples per class.<n>We find that the token-side factor need not be learned at all.<n>In the CLIP prompt setting, the embedding-side coefficients carry the adaptation while the token basis can simply be fixed.
  arXiv  Detail & Related papers  (2026-09-08T21:26:37Z)
• Beyond the Matrix Sign: Quadratic Spectral Descent [6.589542614722917]
  We show that curvature can change both the singular values and the singular directions of the optimal update.<n>Experiments on GPT pre-training show that QSD consistently improves validation loss over Muon and recent Muon variants.
  arXiv  Detail & Related papers  (2026-09-07T15:07:24Z)
• Mousse: Rectifying the Geometry of Muon with Curvature-Aware Preconditioning [72.62839712454196]
  Recent advances in spectral optimization, notably Muon, have demonstrated that constraining update steps to the Stiefel manifold can significantly accelerate training and improveimation.<n>We argue that this "egalitarian" constraint is suboptimal for Deep Neural Networks, where the curvature spectrum is known to be highly heavy-tailed and ill-conditioned.<n>We propose textbfMousse (textbfMuon textbfOptimization textbfUtilizing textbfShampoo's textbfStruct
  arXiv  Detail & Related papers  (2026-03-10T14:03:49Z)
• Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning [51.820005667020354]
  We study a simple but effective Q-learning algorithm for average-reward MDPs with finite state and action spaces under the weakly communicating assumption.<n>We prove that collaboration reduces the per-agent sample complexity to $widetildeOleft(frac|mathcalA||hstar|_mathsfsp3Mvarepsilon3right)$, with only $widetildeOleft(frac|hstar|_mathsfsp3Mvareps
  arXiv  Detail & Related papers  (2026-01-20T06:21:54Z)
• The Price equation reveals a universal force-metric-bias law of algorithmic learning and natural selection [0.0]
  I show that a simple notational partitioning of change by the Price equation reveals a universal force-metric-bias (FMB) law.<n>The FMB law provides a principled foundation for understanding, comparing, and designing learning algorithms across disciplines.
  arXiv  Detail & Related papers  (2025-07-24T16:13:56Z)
• Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping [21.865728815935665]
  We provide the first convergence under heavy-tailed noises but without clipping.<n>We also establish first $mathcalO(Tfrac1-mathfrakp3mathfrakp-2)$ convergence rate in the case where the tail index $mathfrakp$ is unknown in advance.
  arXiv  Detail & Related papers  (2024-12-27T08:46:46Z)
• Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes [29.466981306355066]
  We show that gradient descent with a fixed learning rate $eta$ can only find local minima that represent smooth functions. We also prove a nearly-optimal MSE bound of $widetildeO(n-4/5)$ within the strict interior of the support of the $n$ data points.
  arXiv  Detail & Related papers  (2024-06-10T22:57:27Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• Near Optimal Heteroscedastic Regression with Symbiotic Learning [29.16456701187538]
  We consider the problem of heteroscedastic linear regression. We can estimate $mathbfw*$ in squared norm up to an error of $tildeOleft(|mathbff*|2cdot left(frac1n + left(dnright)2right)$ and prove a matching lower bound.
  arXiv  Detail & Related papers  (2023-06-25T16:32:00Z)
• Over-Parameterization Exponentially Slows Down Gradient Descent for Learning a Single Neuron [49.45105570960104]
  We prove the global convergence of randomly gradient descent with a $Oleft(T-3right)$ rate. These two bounds jointly give an exact characterization of the convergence rate. We show this potential function converges slowly, which implies the slow convergence rate of the loss function.
  arXiv  Detail & Related papers  (2023-02-20T15:33:26Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  We study the asymmetric low-rank factorization problem: [mathbfU in mathbbRm min d, mathbfU$ and mathV$.
  arXiv  Detail & Related papers  (2021-06-27T17:25:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.