Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory

• URL: http://arxiv.org/abs/2603.26554v1
• Date: Fri, 27 Mar 2026 16:13:18 GMT
• Title: Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory
• Abstract summary: Spectrals such as Muon have recently shown strong empirical performance in large-scale language model training.<n>We study this question through the linear associative memory problem.<n>We show that the storage capacity of Muon significantly exceeds that of SGD.
• Score: 77.27772368491698
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral optimizers such as Muon have recently shown strong empirical performance in large-scale language model training, but the source and extent of their advantage remain poorly understood. We study this question through the linear associative memory problem, a tractable model for factual recall in transformer-based models. In particular, we go beyond orthogonal embeddings and consider Gaussian inputs and outputs, which allows the number of stored associations to greatly exceed the embedding dimension. Our main result sharply characterizes the recovery rates of one step of Muon and SGD on the logistic regression loss under a power law frequency distribution. We show that the storage capacity of Muon significantly exceeds that of SGD, and moreover Muon saturates at a larger critical batch size. We further analyze the multi-step dynamics under a thresholded gradient approximation and show that Muon achieves a substantially faster initial recovery rate than SGD, while both methods eventually converge to the information-theoretic limit at comparable speeds. Experiments on synthetic tasks validate the predicted scaling laws. Our analysis provides a quantitative understanding of the signal amplification of Muon and lays the groundwork for establishing scaling laws across more practical language modeling tasks and optimizers.

Related papers

• SGD in Multiclass Logistic Regression: Sequential Learning and Scaling Laws [55.81298869922287]
  We study the training dynamics of multiclass logistic regression on high-dimensional Gaussian mixture models with a large number of classes.<n>We establish precise scaling laws governing the cross-entropy risk under gradient-based optimization.
  arXiv  Detail & Related papers  (2026-09-07T18:30:09Z)
• Deriving Hyperparameter Scaling Laws via Modern Optimization Theory [55.63126290312615]
  We study modern first-order boundss for methods based on the Linear Minimization Oracle (LMO)<n>Treating bounds in recent literature as a proxy and minimizing them across different tuning regimes yields closed-form power-law schedules for learning rate, momentum, and batch size.<n>Our results draw particular attention to the interaction between momentum and batch-size scaling, suggesting that optimal performance may be achieved with several scaling strategies.
  arXiv  Detail & Related papers  (2026-03-16T22:21:27Z)
• Muon in Associative Memory Learning: Training Dynamics and Scaling Laws [23.350512542598803]
  We study Muon in a linear associative memory model with softmax retrieval and a hierarchical frequency spectrum over query-answer pairs.<n>We show that Muon mitigates this imbalance, leading to faster and more uniform progress.
  arXiv  Detail & Related papers  (2026-02-05T14:49:40Z)
• ECO: Quantized Training without Full-Precision Master Weights [58.97082407934466]
  Error-Compensating (ECO) eliminates master weights by applying updates directly to quantized parameters.<n>We show that ECO converges to a constant-radius neighborhood of the optimum, while naive master-weight removal can incur an error that is inversely proportional to the learning rate.
  arXiv  Detail & Related papers  (2026-01-29T18:35:01Z)
• Breaking the Memory Wall: Exact Analytical Differentiation via Tiled Operator-Space Evolution [3.551701030393209]
  Phase Gradient Flow (PGF) is a framework that computes exact analytical derivatives by operating directly in the state-space manifold.<n>Our method delivers O(1) memory complexity relative to sequence length, yielding a 94% reduction in peak VRAM and a 23x increase in throughput compared to standard Autograd.<n>Our work enables chromosome-scale sensitivity analysis on a single GPU, bridging the gap between theoretical infinite-context models and practical hardware limitations.
  arXiv  Detail & Related papers  (2025-12-28T20:27:58Z)
• A Convergence Analysis of Adaptive Optimizers under Floating-point Quantization [32.97211471008323]
  We introduce the first theoretical framework of adaptive convergences, including Adam and Muon, under floating-point quantization of gradients, weights, and states.<n>We show that both algorithms retain convergence rates close to their full-precision counterparts provided mantissa length scales only logarithmically with the number of iterations.<n>Our analysis further reveals that Adam is highly sensitive to and second-moment quantization weights due to its reliance on $beta to 1$, while Muon requires weaker error control and is thus potentially more robust.
  arXiv  Detail & Related papers  (2025-10-24T10:16:23Z)
• Beyond the Ideal: Analyzing the Inexact Muon Update [54.70108543057578]
  We show first analysis of the inexactized update at Muon's core.<n>We reveal a fundamental coupling between this inexactness and the optimal step size and momentum.
  arXiv  Detail & Related papers  (2025-10-22T18:01:07Z)
• Functional Scaling Laws in Kernel Regression: Loss Dynamics and Learning Rate Schedules [9.332823269318842]
  Scaling laws have emerged as a unifying lens for understanding and guiding the training of large language models.<n>We establish a Functional Scaling Law that captures the full loss trajectory under arbitrary LRSs.<n>We derive explicit scaling relations in both data- and compute-limited regimes.
  arXiv  Detail & Related papers  (2025-09-23T16:05:16Z)
• Winner-Take-All Column Row Sampling for Memory Efficient Adaptation of Language Model [89.8764435351222]
  We propose a new family of unbiased estimators called WTA-CRS, for matrix production with reduced variance. Our work provides both theoretical and experimental evidence that, in the context of tuning transformers, our proposed estimators exhibit lower variance compared to existing ones.
  arXiv  Detail & Related papers  (2023-05-24T15:52:08Z)

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.