Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method

• URL: http://arxiv.org/abs/2605.18174v1
• Date: Mon, 18 May 2026 10:18:02 GMT
• Title: Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
• Abstract summary: Muon has emerged as a strong alternative to AdamW for training neural networks, with encouraging large-scale pretraining results and growing evidence that matrix-structured updates can be faster in practice.<n>Yet Muon, and more generally Linearmization Oracle iteration (LMO) based methods, are typically used synchronously.<n>In this work, we introduce Ringmaster LMO, an asynchronous LMO-based method for unconstrained non optimization.<n> Experiments on quadratic problems and NanoChat language-model pretraining show that the advantages of Ringmaster LMO grow with system complexity and that the method outperforms strong asynchronous baselines.
• Score: 46.028295488626746
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Muon has recently emerged as a strong alternative to AdamW for training neural networks, with encouraging large-scale pretraining results and growing evidence that matrix-structured updates can be faster in practice. Yet Muon, and more generally Linear Minimization Oracle (LMO) based methods, are typically used synchronously. This is problematic in heterogeneous distributed systems, where workers complete gradient computations at different speeds and synchronous training must repeatedly wait for slower workers. In this work, we introduce Ringmaster LMO, an asynchronous LMO-based momentum method for unconstrained stochastic nonconvex optimization. Our method builds on the delay-thresholding idea of Ringmaster ASGD. For SGD-type methods, Ringmaster ASGD achieves optimal time complexity by discarding overly stale gradients. Ringmaster LMO extends this mechanism to general LMO-based updates. We establish convergence guarantees under generalized $(L_0, L_1)$-smoothness and further develop a parameter-agnostic variant with decreasing stepsizes and adaptive delay thresholds. Finally, we translate our iteration guarantees into time complexity bounds under heterogeneous worker computation times. In the classical Euclidean smooth setting, these bounds recover the optimal time complexity of Ringmaster ASGD. Experiments on stochastic quadratic problems and NanoChat language-model pretraining show that the advantages of Ringmaster LMO grow with system heterogeneity and that the method outperforms strong synchronous and asynchronous baselines.

Related papers

• Clipping Makes Distributed and Federated Asynchronous SGD Robust to Stragglers [8.286183477962203]
  parallelization of training is an important strategy for increasing scale.<n>With constant step sizes, the convergence of ASGD is affected negatively by slow workers due to large delays in updates.<n>We show convergence in expectation, and the first time in asynchronous optimization, convergence with high probability.
  arXiv  Detail & Related papers  (2026-06-11T12:43:53Z)
• Ordered Local Momentum for Asynchronous Distributed Learning under Arbitrary Delays [22.743876197077785]
  We propose a novel method, called OrLoMo, for asynchronous distributed learning.<n>In OrLoMo, each worker runs MSGD locally. Then the local momentum from each worker will be aggregated by global in order.
  arXiv  Detail & Related papers  (2026-01-18T09:05:39Z)
• First Provably Optimal Asynchronous SGD for Homogeneous and Heterogeneous Data [0.0]
  dissertation develops a rigorous framework for asynchronous order optimization.<n>We show that with proper design, asynchronous SGD can achieve optimal time complexity, matching guarantees previously known only for synchronous methods.
  arXiv  Detail & Related papers  (2026-01-05T19:51:09Z)
• Better LMO-based Momentum Methods with Second-Order Information [48.580700968416444]
  Hessian-Corrected Momentum (HCM) aims to improve momentum convergence rates.<n>Hessian-Corrected Momentum can adapt to the geometry of the problem and achieve a faster rate than traditional momentum.<n>We extend the Linear Minimization Oracle framework by integrating HCM, and provide convergence guarantees under relaxed smoothness and arbitrary norm settings.
  arXiv  Detail & Related papers  (2025-12-15T11:43:09Z)
• Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity [51.56484100374058]
  We introduce Ringleader ASGD, the first asynchronous algorithm that attains the theoretical lower bounds for parallel computation.<n>Our analysis further establishes that Ringleader ASGD remains optimal under arbitrary gradient and even time-varying speeds.
  arXiv  Detail & Related papers  (2025-09-26T19:19:15Z)
• Adaptive Deadline and Batch Layered Synchronized Federated Learning [66.93447103966439]
  Federated learning (FL) enables collaborative model training across distributed edge devices while preserving data privacy, and typically operates in a round-based synchronous manner.<n>We propose ADEL-FL, a novel framework that jointly optimize per-round deadlines and user-specific batch sizes for layer-wise aggregation.
  arXiv  Detail & Related papers  (2025-05-29T19:59:18Z)
• Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity [92.1840862558718]
  Ringmaster ASGD achieves optimal time complexity under arbitrarily heterogeneous computation times.<n>This makes it the first Asynchronous SGD method to meet the theoretical lower bounds for time complexity in such scenarios.
  arXiv  Detail & Related papers  (2025-01-27T16:07:26Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
  arXiv  Detail & Related papers  (2023-01-28T04:12:56Z)

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.