# The Stochastic Multi-Proximal Method for Nonsmooth Optimization

arXiv: https://arxiv.org/abs/2505.12409 · HTML: https://mlsanity.com/paper/2505.12409/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 May 2025.

## Built on by (most cited first, 3 of 3)

- [FedAVOT: Exact Distribution Alignment in Federated Learning via Masked Optimal Transport](https://mlsanity.com/paper/2509.14444/) (2025)
- [Decentralized Optimization with Topology-Independent Communication](https://mlsanity.com/paper/2509.14488/) (2025)
- [Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms](https://mlsanity.com/paper/2602.05489/) (2026)

## Abstract (arXiv)

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.