22 papers
A Quadratic Lens on Muon's Polar Update: Benefits, Pitfalls, and the Role of Newton-Schulz
Egor Shulgin, Sam Laing, Antonio Orvieto +1
Muon updates matrix-valued parameters along approximately orthogonalized directions and often trains large language models faster than AdamW, yet it remains unclear when and why or…
Communication-Efficient Gluon in Federated Learning
Xun Qian, Alexander Gaponov, Grigory Malinovsky +1
Recent developments have shown that Muon-type optimizers based on linear minimization oracles (LMOs) over non-Euclidean norm balls have the potential to get superior practical perf…
BiCoLoR: Communication-Efficient Optimization with Bidirectional Compression and Local Training
Laurent Condat, Artavazd Maranjyan, Peter Richtárik
Slow and costly communication is often the main bottleneck in distributed optimization, especially in federated learning where it occurs over wireless networks. We introduce BiCoLo…
First Provable Guarantees for Practical Private FL: Beyond Restrictive Assumptions
Egor Shulgin, Grigory Malinovsky, Sarit Khirirat +1
Federated Learning (FL) enables collaborative training on decentralized data. Differential privacy (DP) is crucial for FL, but current private methods often rely on unrealistic ass…
Beyond the Ideal: Analyzing the Inexact Muon Update
Egor Shulgin, Sultan AlRashed, Francesco Orabona +1
The Muon optimizer has rapidly emerged as a powerful, geometry-aware alternative to AdamW, demonstrating strong performance in large-scale training of neural networks. However, a c…
Drop-Muon: Update Less, Converge Faster
Kaja Gruntkowska, Yassine Maziane, Zheng Qu +1
Conventional wisdom in deep learning optimization dictates updating all layers at every step-a principle followed by all recent state-of-the-art optimizers such as Muon. In this wo…
Non-Euclidean Broximal Point Method: A Blueprint for Geometry-Aware Optimization
Kaja Gruntkowska, Peter Richtárik
The recently proposed Broximal Point Method (BPM) [Gruntkowska et al., 2025] offers an idealized optimization framework based on iteratively minimizing the objective function over…
Error Feedback for Muon and Friends
Kaja Gruntkowska, Alexander Gaponov, Zhirayr Tovmasyan +1
Recent optimizers like Muon, Scion, and Gluon have pushed the frontier of large-scale deep learning by exploiting layer-wise linear minimization oracles (LMOs) over non-Euclidean n…
Local SGD and Federated Averaging Through the Lens of Time Complexity
Adrien Fradin, Peter Richtárik, Alexander Tyurin
We revisit the classical Local SGD and Federated Averaging (FedAvg) methods for distributed optimization and federated learning. While prior work has primarily focused on iteration…
Ringleader ASGD: The First Asynchronous SGD with Optimal Time Complexity under Data Heterogeneity
Artavazd Maranjyan, Peter Richtárik
Asynchronous stochastic gradient methods are central to scalable distributed optimization, particularly when devices differ in computational capabilities. Such settings arise natur…
Convergence Analysis of the ProbAbilistic Gradient Estimator Algorithm for Weakly Convex Finite-Sum Optimization
Laurent Condat, Peter Richtárik
The ProbAbilistic Gradient Estimator algorithm (PAGE), a stochastic algorithm introduced by Li et al. in 2021, was designed to find stationary points for the average of smooth nonc…
Gluon: Making Muon & Scion Great Again! (Bridging Theory and Practice of LMO-based Optimizers for LLMs)
Artem Riabinin, Egor Shulgin, Kaja Gruntkowska +1
Recent developments in deep learning optimization have brought about radically new algorithms based on the Linear Minimization Oracle (LMO) framework, such as and $\sf S…
The Stochastic Multi-Proximal Method for Nonsmooth Optimization
Laurent Condat, Elnur Gasanov, Peter Richtárik
Stochastic gradient descent type methods are ubiquitous in machine learning, but they are only applicable to the optimization of differentiable functions. Proximal algorithms are m…
BurTorch: Revisiting Training from First Principles by Coupling Autodiff, Math Optimization, and Systems
Konstantin Burlachenko, Peter Richtárik
In this work, we introduce BurTorch, a compact high-performance framework designed to optimize Deep Learning (DL) training on single-node workstations through an exceptionally effi…
Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis
Ali Beikmohammadi, Sarit Khirirat, Peter Richtárik +1
Federated reinforcement learning (FedRL) enables collaborative learning while preserving data privacy by preventing direct data exchange between agents. However, many existing FedR…
Smoothed Normalization for Efficient Distributed Private Optimization
Egor Shulgin, Sarit Khirirat, Peter Richtárik
Federated learning enables training machine learning models while preserving the privacy of participants. Surprisingly, there is no differentially private distributed method for sm…
A Novel Unified Parametric Assumption for Nonconvex Optimization
Artem Riabinin, Ahmed Khaled, Peter Richtárik
Nonconvex optimization is central to modern machine learning, but the general framework of nonconvex optimization yields weak convergence guarantees that are too pessimistic compar…
Revisiting Stochastic Proximal Point Methods: Generalized Smoothness and Similarity
Zhirayr Tovmasyan, Grigory Malinovsky, Laurent Condat +1
The growing prevalence of nonsmooth optimization problems in machine learning has spurred significant interest in generalized smoothness assumptions. Among these, the (L0, L1)-smoo…
The Ball-Proximal (="Broximal") Point Method: a New Algorithm, Convergence Theory, and Applications
Kaja Gruntkowska, Hanmin Li, Aadi Rane +1
Non-smooth and non-convex global optimization poses significant challenges across various applications, where standard gradient-based methods often struggle. We propose the Ball-Pr…
ATA: Adaptive Task Allocation for Efficient Resource Management in Distributed Machine Learning
Artavazd Maranjyan, El Mehdi Saad, Peter Richtárik +1
Asynchronous methods are fundamental for parallelizing computations in distributed machine learning. They aim to accelerate training by fully utilizing all available resources. How…
Symmetric Pruning of Large Language Models
Kai Yi, Peter Richtárik
Popular post-training pruning methods such as Wanda and RIA are known for their simple, yet effective, designs that have shown exceptional empirical performance. Wanda optimizes pe…
Ringmaster ASGD: The First Asynchronous SGD with Optimal Time Complexity
Artavazd Maranjyan, Alexander Tyurin, Peter Richtárik
Asynchronous Stochastic Gradient Descent (Asynchronous SGD) is a cornerstone method for parallelizing learning in distributed machine learning. However, its performance suffers und…