14 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…
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…
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…
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…
Muon is Provably Faster with Momentum Variance Reduction
Xun Qian, Hussein Rammal, Dmitry Kovalev +1
Recent empirical research has demonstrated that deep learning optimizers based on the linear minimization oracle (LMO) over specifically chosen Non-Euclidean norm balls, such as Mu…
Better LMO-based Momentum Methods with Second-Order Information
Sarit Khirirat, Abdurakhmon Sadiev, Yury Demidovich +1
The use of momentum in stochastic optimization algorithms has shown empirical success across a range of machine learning tasks. Recently, a new class of stochastic momentum algorit…
Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise
Adrien Fradin, Abdurakhmon Sadiev, Laurent Condat +1
We study stochastic nonconvex optimization under heavy-tailed noise. In this setting, the stochastic gradients only have bounded -th central moment (-BCM) for some $p \in (1,…
Improved Convergence in Parameter-Agnostic Error Feedback through Momentum
Abdurakhmon Sadiev, Yury Demidovich, Igor Sokolov +3
Communication compression is essential for scalable distributed training of modern machine learning models, but it often degrades convergence due to the noise it introduces. Error…
Second-order Optimization under Heavy-Tailed Noise: Hessian Clipping and Sample Complexity Limits
Abdurakhmon Sadiev, Peter Richtárik, Ilyas Fatkhullin
Heavy-tailed noise is pervasive in modern machine learning applications, arising from data heterogeneity, outliers, and non-stationary stochastic environments. While second-order m…