Research map / Optimization / Optimizers

Sharp Capacity Scaling of Spectral Optimizers in Learning Associative Memory

NeurIPS 2026 · Optimization › Optimizers · approach: Memory-efficient LLM optimizers · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes one-step and multi-step recovery of Muon, SGD and Newton's method on a linear associative memory with Gaussian embeddings and power-law fact frequencies, showing Muon stores far more facts than SGD and matches Newton's one-step recovery.

Problem

Understanding why spectral optimizers like Muon outperform SGD in factual recall: prior associative-memory analyses of Muon assume orthogonal embeddings, which caps storage at N ≤ d, whereas superposition with random embeddings allows ~d^2 items.

Approach

Study linear associative memory with i.i.d. isotropic Gaussian embeddings (N ≫ d) and power-law item frequencies; prove sharp one-step recovery rates via a Daleckii–Krein add-back-in argument for a stabilized polar map h_λ(z)=z/sqrt(z²+λ²), and derive a deflation-based multi-step recursion for Muon and SGD.

Key results

• One Muon step recovers ~d^{1+1/(2α)} items versus ~d^{1/(2α)} for one SGD step in the population regime, matching Newton's method.
• SGD's capacity saturates at batch size ~sqrt(d) whereas Muon saturates at ~d^{α+1/2}.
• Multi-step Muon recovery exponent 2-(1-1/(2α))^t converges exponentially to the information-theoretic maximum 2 under a thresholded-gradient heuristic.

Surprising findings

• Muon matches Newton's method for one step without second-order information.
• The polar map (λ→0) is not expected to improve over the stabilized variant for one-step recovery, since the average singular-value blow-up is limited by the spectrum.

Limitations

• Multi-step results rely on a deflation/thresholded-gradient heuristic; end-to-end guarantee for exact Muon is only a conjecture.
• Anisotropic embeddings break Muon's match with Newton's method.
• Transformer experiments use a simplified in-context recall task, with a critical-batch-size gap versus theory.

Experimental setup

Datasets: synthetic associative memory data (Gaussian embeddings, power-law frequencies)

Benchmarks: synthetic linear associative memory synthetic in-context recall task

Metrics: storage capacity (number of recovered items) out-of-distribution accuracy memory recall accuracy loss

Baselines: SGD Newton's method AdamW SOAP

Builds on: Muon Daleckii-Krein formula associative memory (orthogonal embeddings)

Closest papers by meaning

• Towards Understanding the Power and Limits of the Muon Optimizer: A River-Valley Perspective (NeurIPS 2026 · similarity 0.90)
• Scaling Laws for Associative Memories (ICLR 2024 · similarity 0.88)
• Phases of Muon: When Muon Eclipses SignSGD (NeurIPS 2026 · similarity 0.88)
• Factual recall in linear associative memories: sharp asymptotics and mechanistic insights (NeurIPS 2026 · similarity 0.88)
• Learning Associative Memories with Gradient Descent (ICML 2024 · similarity 0.88)
• MuLoCo: Muon is a Practical Inner Optimizer for DiLoCo (ICML 2026 · similarity 0.87)