The Stochastic Multi-Proximal Method for Nonsmooth Optimization

2025/05/18 by Condat, Laurent, Gasanov, Elnur, Richtárik, Peter · 3 citations
#FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2505.12409

Abstract

Stochastic gradient descent type methods are ubiquitous in machine learning, but they are only applicable to the optimization of differentiable functions. Proximal algorithms are more general and applicable to nonsmooth functions. We propose a new stochastic and variance-reduced algorithm, the Stochastic Multi-Proximal Method (SMPM), in which the proximity operators of a (possibly empty) random subset of functions are called at every iteration, according to an arbitrary sampling distribution. Several existing algorithms, including Point-SAGA (2016), Proxskip (2022) and RandProx-Minibatch (2023) are recovered as particular cases. We derive linear convergence results in presence of strong convexity and smoothness or similarity of the functions. We prove convergence in the general convex case and accelerated O(1/t2) convergence with varying stepsizes in presence of strong convexity solely. Our results are new even for the above special cases. Moreover, we show an application to distributed optimization with compressed communication, outperforming existing methods.

Citations

• A Simple Linear Convergence Analysis of the Point-SAGA Algorithm
• Stochastic Proximal Point Methods for Monotone Inclusions under Expected Similarity
• LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression
• Variance reduction techniques for stochastic proximal point algorithms
• Stochastic Controlled Averaging for Federated Learning with Communication Compression
• Improving Accelerated Federated Learning with Compression and Importance Sampling
• Unbiased Compression Saves Communication in Distributed Optimization: When and How Much?
• TAMUNA: Doubly Accelerated Distributed Optimization under Partial Participation
• Can 5th Generation Local Training Methods Support Client Sampling? Yes!
• Convergence Analyses of Davis-Yin Splitting via Scaled Relative Graphs II: Convex Optimization Problems
• CompressedScaffnew: The First Theoretical Double Acceleration of Communication from Local Training and Compression in Distributed Optimization
• Faster federated optimization under second-order similarity
• RandProx: Primal-Dual Optimization Algorithms with Randomized Proximal Updates
• EF-BV: A Unified Theory of Error Feedback and Variance Reduction Mechanisms for Biased and Unbiased Compression in Distributed Optimization
• ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!
• DASHA: Distributed Nonconvex Optimization with Communication Compression, Optimal Oracle Complexity, and No Client Synchronization
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective
• Three Operator Splitting with Subgradients, Stochastic Gradients, and Adaptive Learning Rates
• A Field Guide to Federated Optimization
• EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback
• MURANA: A Generic Framework for Stochastic Variance-Reduced Optimization
• MARINA: Faster Non-Convex Distributed Learning with Compression
• Local SGD: Unified Theory and New Efficient Methods
• Optimal Gradient Compression for Distributed and Federated Learning
• Variance-Reduced Methods for Machine Learning
• PAGE: A Simple and Optimal Probabilistic Gradient Estimator for Nonconvex Optimization
• Federated Learning with Compression: Unified Analysis and Sharp Guarantees
• Unified Analysis of Stochastic Gradient Methods for Composite Convex and Smooth Optimization
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• From Local SGD to Local Fixed-Point Methods for Federated Learning
• Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization
• Advances and Open Problems in Federated Learning
• Proximal Splitting Algorithms for Convex Optimization: A Tour of Recent Advances, with New Twists
• FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization
• Tighter Theory for Local SGD on Identical and Heterogeneous Data
• Federated Learning: Challenges, Methods, and Future Directions
• On the Convergence of FedAvg on Non-IID Data
• Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification,\n and Local Computations
• On the Convergence of SARAH and Beyond
• Natural Compression for Distributed Deep Learning
• A Unified Theory of SGD: Variance Reduction, Sampling, Quantization and\n Coordinate Descent
• A Stochastic Decoupling Method for Minimizing the Sum of Smooth and\n Non-Smooth Functions
• One Method to Rule Them All: Variance Reduction for Data, Parameters and Many New Methods
• Stochastic Distributed Learning with Gradient Quantization and Variance Reduction
• Distributed Learning with Compressed Gradient Differences
• Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are\n Better Without the Outer Loop
• Local SGD Converges Fast and Communicates Little
• Stochastic Three-Composite Convex Minimization
• Federated Learning: Strategies for Improving Communication Efficiency
• Federated Optimization: Distributed Machine Learning for On-Device Intelligence
• A Simple Practical Accelerated Method for Finite Sums
• Variance Reduced Stochastic Gradient Descent with Neighbors
• A Three-Operator Splitting Scheme and its Optimization Applications
• Proximal Algorithms in Statistics and Machine Learning
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly\n Convex Composite Objectives
• Playing with Duality: An Overview of Recent Primal-Dual Approaches for\n Solving Large-Scale Optimization Problems
• Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems
• A Proximal Stochastic Gradient Method with Progressive Variance Reduction
• A Dynamic Programming Algorithm for the Fused Lasso and L 0 -Segmentation
• Optimization with Sparsity-Inducing Penalties
• Proximal Splitting Methods in Signal Processing
• A Stochastic Approximation Method

Cited by

• Bregman Stochastic Proximal Point Algorithm with Variance Reduction
• Decentralized Optimization with Topology-Independent Communication
• FedAVOT: Exact Distribution Alignment in Federated Learning via Masked Optimal Transport

Related

• Stochastic Proximal Methods for Non-Smooth Non-Convex Constrained Sparse Optimization
• A Simple Proximal Stochastic Gradient Method for Nonsmooth Nonconvex Optimization
• New nonasymptotic convergence rates of stochastic proximal pointalgorithm for convex optimization problems
• Proximal-Proximal-Gradient Method
• Asynchronous Stochastic Proximal Methods for Nonconvex Nonsmooth Optimization