15 papers · 1 filter
A Sharper Theory of Ball-Proximal Optimization: Convergence and Radius Selection
Peter Richtárik, Hanmin Li
We study the exact Euclidean ball-proximal point method for proper, closed, convex functions, where each iteration minimizes the objective over a ball centered at the current point…
Local LMO is Secretly a Projection Method!
Peter Richtárik, Ammar Mahran
The local linear minimization oracle (Ferris and Zavriev, 1996; arXiv:2605.08850), or Local LMO, solves constrained convex problems without having to compute a projection: it minim…
Convergence Analysis of Muon-type Methods with Inexact LMO in the Degenerate Case
Xun Qian, Peter Richtárik
Muon-type methods have demonstrated potentially superior performance over Adam and its variants, and have shown hyperparameter transferability across model sizes when specific norm…
SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums
Igor Sokolov, Laurent Condat, Peter Richtárik
Empirical risk minimization on massive datasets naturally exhibits a nested double finite-sum structure, where total samples are logically or physically partitioned into …
A Unified Primal-Dual Recipe for Accelerating Three-Operator Splitting Methods
Abdurakhmon Sadiev, Laurent Condat, Peter Richtárik
Composite optimization problems, formulated as the minimization of three functions, are ubiquitous in large-scale machine learning and signal processing. While state-of-the-art spl…
LOSCAR-SGD: Local SGD with Communication-Computation Overlap and Delay-Corrected Sparse Model Averaging
Yassine Maziane, Ammar Mahran, Artavazd Maranjyan +1
Communication is a major bottleneck in distributed learning, especially in large-scale settings and in federated learning environments with slow links. Three standard ways to reduc…
Distance-Aware Muon: Adaptive Step Scaling for Normalized Optimization
Yury Demidovich, Abhishek Chakraborty, Grigory Malinovsky +2
Muon and related normalized optimizers decouple the choice of update direction from the choice of step scale, but their practical performance remains sensitive to the scale of the…
Ringmaster LMO: Asynchronous Linear Minimization Oracle Momentum Method
Abdurakhmon Sadiev, Artavazd Maranjyan, Ivan Ilin +1
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-structure…
Rescaled Asynchronous SGD: Optimal Distributed Optimization under Data and System Heterogeneity
Ammar Mahran, Artavazd Maranjyan, Peter Richtárik
Asynchronous stochastic gradient descent (ASGD) is a standard way to exploit heterogeneous compute resources in distributed learning: instead of forcing fast workers to wait for sl…
Rennala MVR: Improved Time Complexity for Parallel Stochastic Optimization via Momentum-Based Variance Reduction
Zhirayr Tovmasyan, Artavazd Maranjyan, Peter Richtárik
Large-scale machine learning models are trained on clusters of machines that exhibit heterogeneous performance due to hardware variability, network delays, and system-level instabi…
Broximal Gradient Descent: A Projection-Free Sister of Projected Gradient Descent
Peter Richtárik, Kaja Gruntkowska, Hanmin Li
We propose Broximal Gradient Descent (BroxGD), a projection-free sister method to projected gradient descent for constrained optimization. Its forward--backward construction replac…
Broximal Alignment for Global Non-Convex Optimization
Kaja Gruntkowska, Hanmin Li, Xun Qian +1
Most non-convex optimization theory is built around gradient dynamics, leaving global convergence largely unexplored. The dominant paradigm focuses on stationarity, certifying only…
A Nesterov-Accelerated Primal-Dual Splitting Algorithm for Convex Nonsmooth Optimization
Laurent Condat, Abdurakhmon Sadiev, Peter Richtárik
We investigate the integration of Nesterov-type acceleration into primal-dual methods for structured convex optimization. While proximal splitting algorithms efficiently handle com…
Byzantine-Robust and Differentially Private Federated Optimization under Weaker Assumptions
Rustem Islamov, Grigory Malinovsky, Alexander Gaponov +3
Federated Learning (FL) enables heterogeneous clients to collaboratively train a shared model without centralizing their raw data, offering an inherent level of privacy. However, g…
Stabilized Proximal Point Method via Trust Region Control
Hanmin Li, Kaja Gruntkowska, Peter Richtárik
The Proximal Point Method (PPM) (Rockafellar, 1976) is a fundamental tool for nonsmooth convex optimization. However, its convergence is not linear under general convexity in the a…