📊 statistics

Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method

This paper introduces Ringmaster LMO, an asynchronous momentum method for LMO-based optimization that extends delay-thresholding techniques to handle heterogeneous distributed systems, offering theoretical convergence guarantees and demonstrating superior performance over synchronous and asynchronous baselines in both synthetic and large-scale language model pretraining tasks.

Original authors: Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin, Peter Richtárik

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin, Peter Richtárik

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the conductor of a massive orchestra (a computer cluster) trying to train a giant AI model. Your goal is to get the music perfect, which means adjusting thousands of instruments (weights) based on feedback from the audience (data).

In the old days, the conductor would wait for every single musician to finish their part before giving the next instruction. This is called synchronous training. The problem? If one musician is slow (maybe their instrument is old, or they are distracted), the entire orchestra sits in silence, waiting. This is a huge waste of time, especially in "heterogeneous" systems where some computers are fast and others are slow.

Recently, a new style of playing called Muon became popular. Instead of treating every instrument as a simple note, Muon looks at the shape and structure of the sound (matrix structure) to make smarter, faster adjustments. However, Muon was still stuck in the "wait for everyone" habit.

This paper introduces Ringmaster LMO, a new method that lets the conductor keep the music flowing even when some musicians are slow. Here is how it works, broken down into simple concepts:

1. The "Ringmaster" Strategy: Don't Wait for the Slowest

Imagine a Ringmaster at a circus. Instead of waiting for the slowest elephant to finish its act before calling the next performer, the Ringmaster has a rule: "If a performer takes too long, we skip them and move on."

The Problem: In a distributed system, some workers (computers) finish their calculations quickly, while others (stragglers) take forever.
The Solution: Ringmaster LMO sets a time limit (a threshold). If a worker sends back a gradient (a piece of feedback) that is "too old" (because they took too long), the system discards it. It's better to use a slightly older, fresher update from a fast worker than to wait for a brand-new update from a slow one.
The Result: The system never sits idle. It keeps moving forward, ignoring the "slow elephants."

2. The "Smart Shape" (LMO)

Most training methods treat the AI model like a long list of numbers. But the paper focuses on Muon, which treats the data like a 3D block or a matrix (like a stack of playing cards rather than a single line).

The Analogy: Imagine trying to straighten a crumpled piece of paper. A standard method might just pull on random corners. Muon looks at the whole sheet and pulls in the direction that smooths it out most efficiently.
Ringmaster LMO combines this "smart shape" approach with the "don't wait for the slow" strategy. It's the first time this specific "smart shape" technique has been made asynchronous (able to ignore slow workers).

3. The "Self-Adjusting" Feature

Usually, to make a system like this work, you have to be a math wizard and tune many knobs (parameters) perfectly for your specific computer setup. If you get it wrong, the training fails.

The paper introduces a Parameter-Agnostic version.

The Analogy: Think of it like a car with adaptive cruise control. You don't need to know exactly how fast the car ahead is or how slippery the road is; the car figures out the right speed and distance automatically as it drives.
Ringmaster LMO automatically adjusts its "time limit" and learning speed as it goes, so you don't need to be a math expert to tune it.

4. What the Experiments Showed

The authors tested this on two things:

A math puzzle (Quadratic problems): They simulated a group of workers with different speeds.
Training a tiny language model (NanoChat): They simulated a real-world chatbot training scenario.

The Findings:

When all workers were roughly the same speed, Ringmaster LMO was just as good as the best existing methods.
When workers had very different speeds (high heterogeneity), Ringmaster LMO pulled ahead significantly. The more "stragglers" (slow workers) there were, the bigger the advantage became. It proved that ignoring the slow updates is the key to speed in messy, real-world computing environments.

Summary

Ringmaster LMO is a new way to train AI models that:

Uses "Smart Shapes": It understands the complex structure of the data (like Muon).
Ignores the Slow: It discards updates that take too long, preventing the whole system from stalling.
Self-Tunes: It adjusts itself automatically without needing complex manual setup.

It's like hiring a conductor who knows exactly when to skip a slow musician to keep the symphony playing at top speed, ensuring the AI learns faster even when the computing power is uneven.

Technical Summary: Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method

Problem Statement

The paper addresses the challenge of training neural networks in heterogeneous distributed systems using Linear Minimization Oracle (LMO)-based optimizers. While LMO-based methods, such as the recently proposed Muon optimizer, have demonstrated superior performance over standard AdamW by explicitly utilizing matrix structures (e.g., via spectral-norm updates), they are currently restricted to synchronous training pipelines.

In synchronous settings, the system must wait for the slowest worker to complete gradient computations before proceeding, creating a bottleneck in heterogeneous environments where worker speeds vary significantly. Existing asynchronous methods (e.g., Ringmaster ASGD) achieve optimal time complexity in Euclidean settings by discarding "stale" gradients that exceed a certain delay threshold. However, these delay-thresholding mechanisms have not been extended to general LMO-based updates, nor have they been analyzed under generalized smoothness assumptions common in modern deep learning.

The central question posed is: Can asynchronous LMO-based methods recover the optimal time complexity known for Euclidean settings under heterogeneous worker computation times?

Methodology: Ringmaster LMO

The authors propose Ringmaster LMO, an asynchronous momentum method for unconstrained stochastic nonconvex optimization. The method integrates three core components:

LMO-Based Momentum: The update direction is determined by a Linear Minimization Oracle (LMO) over the unit ball of a chosen norm. For a momentum vector $m_{k+1}$ , the update is $x_{k+1} = x_k + \eta_k \text{lmo}(m_{k+1})$ . This framework generalizes various optimizers; for instance, choosing the spectral norm recovers Muon, while the max-norm recovers SignSGD.
Delay-Thresholding: To mitigate the degradation caused by stale gradients in asynchronous settings, the server accepts a gradient $g_k$ (computed at iterate $x_{k-\delta_k}$ ) only if its delay $\delta_k$ is below a threshold $R_k$ . Gradients exceeding this threshold are discarded.
Generalized Smoothness Analysis: The theoretical analysis operates under $(L_0, L_1)$ -smoothness, where the local smoothness constant can grow with the gradient norm. This is a more general assumption than standard $L_0$ -smoothness and better captures the behavior of losses in modern machine learning.

The algorithm maintains a central server that manages the iterate and momentum, while $n$ workers compute stochastic gradients in parallel. The server updates the momentum and applies the LMO step only upon receiving a "fresh" gradient (delay $< R_k$ ).

Key Contributions

1. First Asynchronous LMO-Based Method with Time Complexity Guarantees

The paper introduces the first asynchronous LMO-based method that provides rigorous time complexity guarantees under heterogeneous worker computation times. It extends the delay-control principle of Ringmaster ASGD from Euclidean SGD updates to general LMO-based updates.

2. Convergence under Generalized Smoothness

The authors establish convergence rates for Ringmaster LMO under $(L_0, L_1)$ -smoothness.

Fixed-Parameter Regime: They derive iteration complexity bounds that recover standard stochastic LMO-type dependence while accommodating delayed gradients. In the classical Euclidean smooth setting ( $L_1=0$ ), the bounds match the optimal lower bounds for first-order stochastic non-convex optimization.
Parameter-Agnostic Regime: A variant is developed with decreasing stepsizes and adaptive delay thresholds ( $R_k = 1/\alpha_k$ ). This variant removes the need to tune hyperparameters based on problem constants (like $L_0, L_1, \sigma$ ), a feature previously absent in Ringmaster ASGD analyses.

3. Time Complexity Analysis

The paper translates iteration complexity into time complexity under two models:

Fixed Computation Model: Assuming constant computation times per worker, the time complexity bounds recover the optimal scaling of Ringmaster ASGD in the Euclidean setting. The bounds explicitly depend on the harmonic mean of the fastest $m$ workers, demonstrating that the method effectively adapts to system heterogeneity.
Universal Time-Varying Model: The analysis is extended to scenarios where worker speeds change over time, providing recursive time bounds that hold even under fluctuating loads.

4. Experimental Validation

Experiments were conducted on:

Stochastic Quadratic Problems: Using a Nesterov tridiagonal quadratic objective.
NanoChat Language Model Pretraining: A 6-layer, 192-hidden transformer model.

The results compare Ringmaster LMO (specifically Ringmaster Muon) against synchronous and asynchronous baselines (Rennala Muon, Delay-adaptive Muon). The experiments demonstrate that while the method is competitive in nearly homogeneous settings, its advantage grows significantly as worker-speed heterogeneity increases. In highly heterogeneous regimes (linear delay profiles), Ringmaster LMO achieves the lowest training loss and fastest convergence.

Results and Significance

Theoretical Results:

The method achieves an iteration complexity of $\tilde{O}(\Psi^4 / \epsilon^4)$ in the parameter-agnostic setting, where $\Psi$ encapsulates problem constants and noise.
In the fixed-parameter setting, the time complexity to reach an $\epsilon$ -stationary point is $O(\min_m H_m \cdot (\dots))$ , where $H_m$ is the harmonic mean of the first $m$ worker times. This confirms that the method avoids the "straggler" problem by discarding overly stale updates, thereby recovering the optimal time complexity known for Euclidean asynchronous SGD.

Empirical Results:

Heterogeneity Sensitivity: The performance gap between Ringmaster LMO and baselines widens as the delay heterogeneity increases. In the "linear delay" regime (where some workers are significantly slower), Ringmaster Muon outperforms all baselines.
Robustness: The parameter-agnostic variant performs competitively without requiring manual tuning of the delay threshold based on problem parameters.

Significance:
The paper claims to bridge the gap between the empirical success of matrix-structured optimizers (like Muon) and the theoretical efficiency of asynchronous distributed training. By proving that delay-thresholding can be successfully applied to non-Euclidean, LMO-based updates, the work enables the use of these advanced optimizers in large-scale, heterogeneous distributed environments without sacrificing convergence guarantees. The authors note that while their analysis assumes homogeneous data distributions, the method's ability to handle system heterogeneity is a critical step toward practical, large-scale training.

Limitations Acknowledged:
The authors modestly note that lower bounds for the asynchronous time complexity of general LMO-based methods in arbitrary norms remain an open problem, as matching lower bounds are not even known for the synchronous case. Additionally, the current theory assumes homogeneous data distributions across workers, leaving data-heterogeneous settings as a natural next step.