The Stochastic Multi-Proximal Method for Nonsmooth Optimization

Laurent Condat, Elnur Gasanov, Peter RichtárikarXiv 2025 · DOI · arXiv

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/t^2)$ 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.

Introduction

In machine learning and signal processing, practitioners often face a trade-off between speed and robustness. Stochastic Gradient Descent (SGD) is the standard for large-scale datasets due to its low per-iteration cost. However, SGD is fundamentally limited to differentiable functions. When dealing with nonsmooth objectives—such as $L_1$ regularization or hard constraints—proximal algorithms are required. Traditionally, these algorithms require processing the entire dataset at each step, making them computationally prohibitive for massive $n$.

Researchers at KAUST have introduced the Stochastic Multi-Proximal Method (SMPM), a unified framework that bridges the gap between stochastic sampling and proximal splitting. SMPM offers a variance-reduced approach that maintains the robustness of proximal methods while achieving the efficiency of stochastic updates.

The SMPM Framework

The core innovation of SMPM lies in its ability to handle a sum of nonsmooth functions by updating only a random subset at each iteration. The algorithm is characterized by several key features:

  1. Random Activation and Arbitrary Sampling: Instead of computing proximal operators for all $n$ functions, SMPM selects a random minibatch $\Omega^t$. Crucially, it supports arbitrary sampling distributions, allowing for importance sampling where more complex functions are updated more frequently.
  2. Variance Reduction: By maintaining dual variables that act as a memory of previous updates, SMPM ensures that the noise introduced by stochastic sampling eventually cancels out, allowing the algorithm to converge to an exact solution.
  3. A Unified Theory: SMPM acts as a "master" algorithm. By adjusting its parameters, it recovers several well-known methods as special cases, providing a single theoretical proof that covers a wide array of optimization techniques.
Table 1: Particular cases of SMPM, showing how it recovers existing algorithms like Point-SAGA and Proxskip.

Theoretical Insights

The paper provides a rigorous theoretical foundation for SMPM, yielding several significant results:

  • Linear Convergence: The authors prove linear convergence for strongly convex problems, even in the presence of nonsmooth components.
  • Acceleration without Smoothness: A surprising result is the achievement of an $O(1/t^2)$ convergence rate for strongly convex problems without assuming function smoothness—a feat previously considered difficult in stochastic proximal settings.
  • Importance Sampling: The theory demonstrates that picking "sharper" functions (those with larger Lipschitz constants) more frequently can lead to substantial speedups compared to uniform sampling.

Distributed Optimization: FedSMPM

The authors extend SMPM to the federated learning setting with FedSMPM. To address communication bottlenecks, they introduce a novel adaptive scaling (rescale) procedure. This allows a central server to aggregate updates from clients even when those updates are heavily compressed (e.g., using rand-k compressors). Unlike many methods that struggle with the bias introduced by compression, FedSMPM embraces this bias through its rescaling mechanism, leading to superior communication efficiency.

Experimental Validation

The method was validated using several synthetic benchmarks designed to stress-test specific mathematical properties:

  • Heterogeneous Quadratics: Confirmed that importance sampling can achieve the same accuracy as uniform sampling in roughly 1/10th the iterations when function disparity is high.
  • Nonsmooth Strongly Convex Problems: Demonstrated that SMPM handles indicator functions and "hard" nonsmoothness more effectively than predecessors like Point-SAGA.
  • Communication Complexity: In distributed settings, FedSMPM consistently outperformed state-of-the-art baselines like TAMUNA and 5GCS-CC across various levels of data heterogeneity and compression.

Conclusion and Future Work

The Stochastic Multi-Proximal Method provides a powerful, unified approach to nonsmooth optimization. While currently focused on convex problems, the framework's flexibility opens new avenues for efficient large-scale optimization. Future work may involve extending these results to non-convex landscapes, such as deep neural networks, and exploring how other compression techniques like quantization interact with the rescaling procedure.

Summary updated

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.
BibTeX
@misc{condat2025stochastic,
  author = {Laurent Condat and Elnur Gasanov and Peter Richtárik},
  title = {{The Stochastic Multi-Proximal Method for Nonsmooth Optimization}},
  year = {2025},
  eprint = {2505.12409},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.12409},
  howpublished = {arXiv},
}
Figure