11 papers
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…
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…
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…
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,…
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…
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…
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…
A Simple Linear Convergence Analysis of the Point-SAGA Algorithm
Laurent Condat, Peter Richtárik
Point-SAGA is a randomized algorithm for minimizing a sum of convex functions using their proximity operators (proxs), proposed by Defazio (2016). At every iteration, the prox of o…
Stochastic Proximal Point Methods for Monotone Inclusions under Expected Similarity
Abdurakhmon Sadiev, Laurent Condat, Peter Richtárik
Monotone inclusions have a wide range of applications, including minimization, saddle-point, and equilibria problems. We introduce new stochastic algorithms, with or without varian…
Sparse-ProxSkip: Accelerated Sparse-to-Sparse Training in Federated Learning
Georg Meinhardt, Kai Yi, Laurent Condat +1
In Federated Learning (FL), both client resource constraints and communication costs pose major problems for training large models. In the centralized setting, sparse training addr…