Skip to main content
Back

University of Toulouse Proves Muon and Shampoo Can Train Asynchronously Without Losing Speed

A new theoretical framework proves asynchronous AdaGrad, Muon, and Shampoo converge at O(1/√t) — the first such guarantee for adaptive methods in heterogeneous parallel systems.

Paper, Full Access
  • First convergence proof for asynchronous AdaGrad, Shampoo, and Muon on non-convex objectives, achieving O(1/√t) rate.
  • Framework (ASADPREC) assigns each model block to a dedicated worker; blocks update asynchronously using stale but bounded-delay gradients.
  • Momentum-less and MM-momentum variants require no step-size restriction; MG-momentum needs a small step size or bounded gradient norms.
  • Inexact Newton-Schulz normalization (used in Muon) is explicitly supported — approximate orthogonalization preserves the convergence rate.
  • Experiments on 6 benchmarks show asynchronous adaptive methods match or beat synchronous baselines, with speedups up to 1.43x on heterogeneous workloads.
  • Paper: arxiv.org/abs/2606.01787; companion synchronous theory: arxiv.org/abs/2604.17423.

Modern large-scale ML systems are messy. Different layers of a neural network take wildly different amounts of time to update , a Muon step on a large weight matrix can take 100x longer than an AdaGrad step on a bias vector. Synchronous training handles this by making every worker wait for the slowest one, which wastes compute. Asynchronous training lets workers run freely, but until now, nobody had proven that adaptive optimizers like AdaGrad, Shampoo, or Muon actually converge when running asynchronously. A new paper from researchers at the University of Toulouse and the University of Namur fills that gap , and the results are cleaner than expected.

The gap nobody had closed

Asynchronous SGD has been well-studied since the Hogwild! paper in 2011. The core idea: multiple processors share a model in memory, each reads the current weights, computes a gradient, and writes an update , all without waiting for each other. The math works out because the "stale" gradients only introduce bounded delays. But Hogwild! and its descendants all use plain gradient steps. The main limitation of prior asynchronous methods is that pure gradient steps can lead to very slow convergence on ill-conditioned problems , a problem long addressed by adaptive preconditioning in the synchronous case, in methods like AdaGrad, Adam, Shampoo, or Muon. Nobody had proven that these adaptive methods could be made asynchronous with convergence guarantees.

The paper introduces a new class of asynchronous adaptive first-order optimization methods, comprising asynchronous variants of several popular algorithms, and shows that their convergence on non-convex functions is of order O(1/√t) under reasonable assumptions. That's the same rate you'd expect from synchronous adaptive methods , asynchrony doesn't hurt the asymptotic rate.

What "adaptive" and "preconditioned" actually mean here

To understand what's new, it helps to know what these terms mean in practice. A plain gradient step moves in the direction of steepest descent under the Euclidean norm. An adaptive preconditioned step rescales the gradient using accumulated history , AdaGrad divides by the square root of past squared gradients, Shampoo uses full matrix preconditioners per layer, and Muon orthogonalizes the momentum matrix using a Newton-Schulz iteration. These methods converge faster on ill-conditioned problems because they effectively normalize the curvature of the loss landscape.

The paper's key insight is to treat each layer's parameters as a separate