Pith. sign in

REVIEW 1 major objections 4 minor 26 references

The Stochastic Multi-Proximal Method for Nonsmooth Optimization

T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A single stochastic proximal algorithm—call a random subset of proximity operators at each step and correct dual variables—converges linearly on nonsmooth sums, and its rates cover Point-SAGA, the Stochastic Decoupling Method, ProxSkip…

desk verdict SMPM is a real unification with new rates, but the nonsmooth similarity result (Theorem 3.3) has a proof gap that needs to be closed before that headline claim is fully honest. read the letter →

arxiv 2505.12409 v1 pith:U2IIK45K submitted 2025-05-18 math.OC

Laurent Condat , Elnur Gasanov , Peter Richtárik This is my paper · ORCID
classification math.OC MSC 90C2590C1565K05
keywords stochasticproximalmethodsvariancereductionnonsmoothconvexoptimizationarbitrarysamplinglinearconvergenceacceleratedO(1/t^2)federatedlearningcommunicationcompression
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes a stochastic algorithm for minimizing a sum of convex functions with nonsmooth terms. At every iteration it calls the proximity operators of a random subset of the functions, drawn from an arbitrary sampling distribution, while maintaining dual variables that steer the iterates to an exact solution. Under strong convexity the method converges linearly when the component functions are smooth or δ-similar, and at an accelerated O(1/$t^{2}$) rate under strong convexity alone, with no smoothness assumptions. Several established methods, including Point-SAGA, the Stochastic Decoupling Method, ProxSkip, and RandProx-Minibatch, are recovered as special cases, so the rates apply to them as well. A distributed variant with compressed communication inherits the analysis and is reported to outperform existing baselines.

What carries the argument

The engine is the proximal residual update: for a randomly sampled set $\Omega_t$, each active component computes $y_i^{t+1}=\operatorname{prox}_{\gamma_t\eta_i h_i}(\hat x_t+\gamma_t\eta_i u_i^t)$, then sets $u_i^{t+1}=u_i^t+(\hat x_t-y_i^{t+1})/(\gamma_t\eta_i)\in\partial h_i(y_i^{t+1})$, and the next iterate $x_{t+1}$ is the average of the $y_i^{t+1}$, or a random mixture of $\hat x_t$ and $x_t$ when the sample is empty. Here $\operatorname{prox}_\phi(x)=\arg\min_y\,\phi(y)+\tfrac12\|y-x\|^2$ is the proximity operator, the nonsmooth analogue of a projection. The dual variables $u_i^t$ store a running subgradient of each component, and the Lyapunov function combining $\|x_t-x^\star\|^2$ with weighted dual errors $\|u_i^t-\nabla h_i(x^\star)\|^2$ contracts by a factor $\rho<1$ at every step under the theorem's assumptions. The key departure from earlier stochastic proximal theory is that $x_{t+1}$ is a biased average of the sampled prox outputs; the bias is absorbed by the dual variables instead of being removed by an unbiased estimator.

What would settle it

Take n identical nonsmooth strongly convex components, say h_i(x)=|x|+\tfrac{\mu}{2}$x^{2}$ for all i, with f=g=0 and uniform sampling; the theorem predicts linear convergence because the components are identical and hence δ-similar with δ=0 even in the L_h=\infty case. If the measured per-iteration contraction factor of $\|x_t-x^\star\|^2$ does not stay bounded away from 1 as iterations grow, the nonsmooth linear-convergence claim of Theorem 3.3 is wrong.

Watch

Extended reading notes

Core claim

The central claim is that a primal–dual stochastic proximal scheme can achieve variance reduction without unbiased stochastic estimates: at each step, an arbitrary subset of component functions is sampled, their proximity operators are applied to a shared prediction, and the outputs are averaged in a deliberately biased way while dual variables are updated from the proximal residuals. This biased averaging is what lets the method handle arbitrary sampling, including empty samples, and the Lyapunov function $$ \Psi_t=(1+\gamma\hat\mu_h)\|x_t-x^\star\|^2+\frac{1-p_\emptyset+\bar p}{n}\sum_{i=1}^n\frac{1}{p_i}\left(\$gamma^{2}$\eta_i+\frac{2\gamma}{L_{h_i}+\mu_{h_i}}\right)\|u_i^t-\nabla h_i(x^\star)\|^2 $$ contracts in expectation. From this contraction the paper obtains linear convergence under strong convexity with smooth or δ-similar components, accelerated O(1/$t^{2}$) convergence under strong convexity alone, and O(1/t) in the general convex case. The full-batch version is a parallel Davis–Yin three-operator splitting, and the special cases recover Point-SAGA, the Stochastic Decoupling Method, ProxSkip, and RandProx-Minibatch.

Load-bearing premise

The strongest advertised result—linear convergence without smoothness—assumes a δ-similarity condition that is formally stated only for differentiable functions, and the paper's footnote merely sketches the subgradient case, so the theorem's nonsmooth conclusion depends on an extension that is not fully proved.

Editorial extensions

If this is right

  • Strongly convex nonsmooth finite-sum problems inherit a linear rate whenever the nonsmooth components are δ-similar, so the method does not need component smoothness for exponential error decay.
  • The varying-stepsize schedule $\gamma_t=2/(\mu(a+t))$ gives an accelerated $O(1/t^2)$ bound under strong convexity alone, and the experiments show it beats a grid-tuned constant stepsize for Point-SAGA-type updates.
  • Recovering ProxSkip, Point-SAGA, the Stochastic Decoupling Method, and RandProx-Minibatch as special cases transfers the new rates to those algorithms, including importance sampling improvements.
  • In the distributed setting, the coordinate-wise rescaling in FedSMPM accommodates arbitrary client participation and empty rounds, and its communication complexity matches TAMUNA and 5GCS-CC while allowing a biased aggregate.
  • Importance sampling tuned to $\bar L_h=(\frac1n\sum_i\sqrt{L_{h_i}})^2$ rather than $\max_i L_{h_i}$ is provably faster when the components have heterogeneous smoothness.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension not developed in the paper is that any aggregation rule whose bias is controlled by the same dual-residual identity—coordinate-wise rescaling, weighted averages, or even sketches of the prox outputs—should fit the same Lyapunov proof.
  • If the subgradient version of δ-similarity is made fully rigorous, SMPM would give the first linearly convergent stochastic proximal method for nonsmooth strongly convex sums under heterogeneous data; hinge and quantile losses are the obvious testbeds.
  • The coordinate-separable argument used for rand-k compression suggests the analysis extends to any unbiased coordinate-wise sparsifier, because only the per-coordinate inclusion probability matters in the proof; the paper proves only the uniform rand-k case.
  • The δ-similarity parameter can be read as a heterogeneity budget: sampling more often the components whose subgradients deviate most from the mean should shrink the effective δ, giving a principled client-sampling rule that the experiments do not explore.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 4 minor

Summary. The paper proposes the Stochastic Multi-Proximal Method (SMPM, Algorithm 1), which minimizes f(x)+g(x)+(1/n)\sum_i h_i(x) by applying proximal operators of a random subset of the h_i according to an arbitrary proper sampling distribution, with dual-variable updates and a possibly empty sample. It recovers Point-SAGA, minibatch Point-SAGA, RandProx-Minibatch, the Stochastic Decoupling Method, ProxSkip, and the Davis--Yin algorithm as special cases. The main theoretical results are: linear convergence with strong convexity when the h_i are smooth (Theorem 3.1); linear convergence under a delta-similarity condition on the h_i (Theorem 3.3), including the claimed nonsmooth case L_h=+infty; linear convergence for n=1 with g a scaled squared norm (Theorem 3.5); accelerated O(1/t^2) convergence under strong convexity alone with time-varying stepsizes (Theorems 4.1 and 4.2); an O(1/t) result in the general convex case (Theorem I.1); and a compressed-communication distributed variant FedSMPM (Section 5, Theorem 5.1). Numerical experiments illustrate importance sampling, accelerated Point-SAGA, and FedSMPM.

Significance. If the proofs are correct, the paper is a substantial contribution to stochastic proximal methods: it supplies a single Lyapunov framework that unifies and extends several existing algorithms, with explicit rates, importance-sampling probabilities, and a compressed distributed implementation. The appendix derivations are detailed and self-contained, and the numerical experiments support the qualitative theoretical predictions. The main caveat is that the headline claim of linear convergence without smoothness in the similarity setting rests on an unproved subgradient extension of Assumption 3.2; this is a load-bearing gap because the nondifferentiable case is central to the paper's stated motivation. The formal results under smooth h_i and the accelerated sublinear results appear sound and are valuable on their own.

major comments (1)
  1. [Theorem 3.3, Assumption 3.2, Appendix F] Theorem 3.3 advertises linear convergence when L_h=+infty, and the text after Corollary 3.4 states that SMPM converges linearly even without smoothness. Formally, however, the theorem is stated under Assumption 3.2, which requires each h_i to be differentiable, so the theorem as written may be correct for differentiable but non-Lipschitz-gradient h_i. The problem is the footnote on page 6, which claims that the analysis extends to nondifferentiable h_i by replacing gradients with subgradients following Sadiev et al. This is not a purely notational change. The proof in Appendix F uses the identity u^t_i = \nabla h_i(z^t_i) and applies inequality (5) at z^t_i; for nondifferentiable h_i, the prox update selects an arbitrary element of the set-valued subdifferential, and nothing in the stated assumptions guarantees that the selected subgradients satisfy the similarity inequality. A concrete failure mode is n=2, h_1=h_2=|\cdot|, f=g=0, x^*=0, with u^*_1=1, u^*_2=-1 and initial data x_0=0, z^0_1=z^0_2=0, u^0_1=-1, u^0_2=1. The algorithm then keeps z^t_i=0, u^t_1=-1, u^t_2=1 for all t, and the subgradient analogue of (5) would require 4 \le 0 for any finite delta. Thus the advertised nonsmooth linear-convergence claim is not established by the submitted proof as written; the authors must either state and verify an explicit selection-consistency assumption for the subgradients produced by the algorithm, or provide a genuinely subgradient-based argument that bypasses identity (38).
minor comments (4)
  1. [Section 5, paragraph after Algorithm 2] The displayed formula for the compressed empty probability, \check p_\emptyset := p_\emptyset + \mathbb{E}_{\Omega\sim S}[(1-k/d)^{|\Omega|}], appears to double-count the empty event, because the expectation already contains p_\emptyset \cdot 1 when \Omega=\emptyset. The intended quantity is presumably \mathbb{E}_{\Omega\sim S}[(1-k/d)^{|\Omega|}], or equivalently p_\emptyset + \mathbb{E}_{\Omega\sim S,\Omega\ne\emptyset}[(1-k/d)^{|\Omega|}]; the notation should be corrected.
  2. [Appendix F, first paragraph] The statement that the auxiliary variables are defined so that u^t_i = \nabla h_i(z^{t+1}_i) is inconsistent with the use of u^t_i = \nabla h_i(z^t_i) in inequality (38). The intended identity appears to be u^t_i = \nabla h_i(z^t_i) (or equivalently u^{t+1}_i = \nabla h_i(z^{t+1}_i)).
  3. [Appendices G and H] The proofs of Theorems 4.1 and 4.2 say 'Following the derivations in the beginning of Section A, we have in (18)', but (18) is displayed with finite-L_{h_i} terms. The specialization to L_{h_i}=+\infty (Theorem 4.1) and to \mu_{h_i}\equiv 0 (Theorem 4.2) is straightforward but should be spelled out, since the dual-variable coefficients in the Lyapunov function change.
  4. [Sections 2.1 and 6.3] There are small consistency and typographical issues: 'Stochastic Decoupling Method (SDM)' in Section 2.1 appears as 'Sto. Decoupling Method' in Table 1, and Section 6.3 contains the typo '5GS-CC' instead of '5GCS-CC'.

Circularity Check

1 steps flagged · score 4.0 of 10

Theorem 3.3's nonsmooth linear-convergence claim is imported from a self-citation, while the paper's core convergence proofs are self-contained.

  1. self citation load bearing [Section 3, Assumption 3.2 footnote and Theorem 3.3; Appendix F proof.]
    "Suppose that Assumption 3.2 holds and, for simplicity, that Lhi≡L h for some δ≤L h≤ +∞ ... Then SMPM converges linearly ... (with the second term equal to 1−ps (µˆf+µˆh)/(µˆf+µˆh)+2δ2γ if L h = +∞). ... Differentiability is assumed for simplicity of the notations solely. The functions can be nonsmooth and we can replace the gradients by subgradients in (5), following the example of the anaysis of Point-SAGA under similarity in Sadiev et al. [2024], but dealing with set-valued subdifferentials makes all notations and derivations twice as long, since the subgradients are not unique."

    Assumption 3.2 is stated for differentiable hi and inequality (5) contains gradients, while Theorem 3.3 explicitly allows Lh=+∞ and Appendix F proves the rate using u_t^i=∇h_i(z_t^i) and applying (5) to ∇h_i. The Lh=+∞ case is therefore not derived in the paper; the footnote delegates it to Sadiev et al. [2024], whose author list overlaps with the present paper (Condat, Richtárik). This is a load-bearing self-citation for a headline claim ('SMPM converges linearly even without smoothness'), and the cited subgradient extension is not reproduced or otherwise independently verified in this manuscript.

full rationale

No step in the derivation of Theorems 3.1, 4.1, 4.2, or the appendix inequalities fits a parameter to a target and then reports it as a prediction; the Lyapunov functions are explicit functions of the algorithm's state and the contraction factors follow from stated strong-convexity and smoothness or similarity assumptions. The particular-case recoveries (Point-SAGA, ProxSkip, RandProx-Minibatch) are identifications, not disguised inputs. The only load-bearing self-citation is the subgradient extension of δ-similarity used to advertise Lh=+∞ linear convergence; the formal assumption and Appendix F use differentiable gradients, so that extension is not self-contained. Since most results are independently derived and the smooth version of the similarity theorem is proven in the paper, the circularity score is moderate.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard convex analysis and explicitly stated structural assumptions. The algorithm has hyperparameters gamma_t, eta_i, and p_i that are prescribed by the theory rather than fitted to data. No invented physical or mathematical entities are introduced. The main fragility is the unformalized extension of the delta-similarity assumption to nonsmooth subgradients.

free parameters (4)
  • step size gamma_t = Constant gamma in Theorems 3.1, 3.3, 3.5; gamma_t = 2/(mu(a+t)) in Theorems 4.1 and 4.2; optimized choices in…
    The step size is an algorithmic parameter whose range or optimal value is prescribed by the theory; it is not fitted to the experimental outcomes.
  • dual scaling eta_i = eta_i = (1-p_empty+pbar)/(n * tilde_p_i * (1-p_empty)) in Theorem 3.1; eta_i = 1/(n * tilde_p_i) in Corollary C.1…
    The dual scaling is chosen to make the Lyapunov contraction work; it depends on the sampling probabilities and problem data, not on observed convergence.
  • sampling probabilities p_i = Uniform p_i = s/n or importance p_i = b_i / b in Corollary C.4.
    The importance sampling distribution is computed from the smoothness constants L_{h_i}; this is a theoretically motivated choice, not a fit to the target accuracy.
  • constant a in accelerated stepsize = a > 5
    Any a > 5 satisfies the technical condition gamma_0 <= 2/(L_f+mu_f); the constant is a free choice in the schedule but does not affect the O(1/t^2) rate.
assumptions (5)
  • domain assumption f is L_f-smooth and g, h_i are proper closed convex functions on a finite-dimensional Hilbert space.
    This is the standard setting for the problem in equation (1) and is stated in Section 1.1.
  • domain assumption There exists x* and subgradients u_i* in partial h_i(x*) satisfying the optimality condition (2).
    This is a standard necessary and sufficient condition for convex optimality and is assumed throughout.
  • domain assumption Assumption 3.2 (delta-similarity): each h_i is differentiable and the gradient deviations are bounded by delta times the squared distance to x*.
    This is the key structural condition for Theorem 3.3. The formal assumption requires differentiability, but the theorem claims applicability for L_h = +infty via a footnote that extends to subgradients.
  • domain assumption The sampling distribution S is proper: p_i > 0 for every i, and the tilde p_i weights exist via equation (3).
    Every component must have a positive chance of being selected, and equation (3) defines the effective averaging weights used in the proof.
  • standard math Standard convex analysis inequalities: cocoercivity of gradients, strong convexity inequalities, and properties of proximal operators (e.g., Bubeck's Lemma 3.11).
    These are unproved background results used throughout the appendix proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Stochastic Multi-Proximal Method for Nonsmooth Optimization." pith.science (2026). https://pith.science/paper/U2IIK45K

@misc{pith2026250512409,
  author       = {Pith},
  title        = {Pith review of: The Stochastic Multi-Proximal Method for Nonsmooth Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/U2IIK45K}},
  note         = {Machine review of arXiv:2505.12409}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2505.12409 by the authors.

Figure 1
Figure 1. Comparison of importance and uniform sampling strategies in [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 2
Figure 2. Comparison between SMPM and Point-SAGA. Point-SAGA is run with a fixed stepsize, where the best-performing stepsize is selected from a predefined grid. The configuration of SMPM follows the setup specified in Theorem 4.2, employing a pre-defined adaptive stepsize schedule that requires no tuning. As shown in the plot, SMPM consistently outperforms Point-SAGA, in line with the theoretical predictions. In this experim… view at source ↗
Figure 3
Figure 3. Comparison of FedSMPM, 5GCS-CC, and TAMUNA in the distributed setting. FedSMPM and 5GCS-CC use the rand-k compressor, while TAMUNA employs the scheme proposed by Condat et al. [2023a]. All algorithm parameters are set according to their theoretical values. For FedSMPM and 5GCS-CC, we report the best-performing value of k from the candidate set. In TAMUNA, the sparsity parameter s is fixed to 2. Somewhat unexpectedly… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 15 canonical work pages

  1. [1]

    Albasyoni, M

    A. Albasyoni, M. Safaryan, L. Condat, and P. Richtárik. Optimal gradient compression for distributed and federated learning. preprint arXiv:2010.03246,

    arXiv 2010

  2. [8]

    Grudzień, G

    M. Grudzień, G. Malinovsky, and P. Richtárik. Improving accelerated federated learning with compression and importance sampling. arXiv:2306.03240, 2023a. 17 M. Grudzień, G. Malinovsky, and P. Richtárik. Can 5th Generation Local Training Methods Support Client Sampling? Yes! InProc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), Apr. 2023b...

    arXiv

  3. [10]

    Y. He, X. Huang, and K. Yuan. Unbiased compression saves communication in distributed optimization: When and how much? preprint arXiv:2305.16297,

    work page Pith review arXiv

  4. [11]

    Khaled, K

    A. Khaled, K. Mishchenko, and P. Richtárik. Tighter theory for local SGD on identical and heterogeneous data. InProc. of 23rd Int. Conf. Artificial Intelligence and Statistics (AISTATS), PMLR 108, 2020a. A. Khaled, O. Sebbouh, N. Loizou, R. M. Gower, and P. Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimiza...

    arXiv 2006

  5. [12]

    Konečný, H

    J. Konečný, H. B. McMahan, D. Ramage, and P. Richtárik. Federated optimization: distributed machine learning for on-device intelligence. arXiv:1610.02527, 2016a. J.Konečný, H.B.McMahan, F.X.Yu, P.Richtárik, A.T.Suresh, andD.Bacon. Federatedlearning: Strategies for improving communication efficiency. InNIPS Private Multi-Party Machine Learning Workshop, 20...

    arXiv

  6. [14]

    Mishchenko, E

    K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik. Distributed learning with compressed gradient differences. arXiv:1901.09269,

    arXiv 1901

  7. [15]

    Reisizadeh, A

    A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani. FedPAQ: A communication-efficient federated learning method with periodic averaging and quantization. InProc. of Int. Conf. Artificial Intelligence and Statistics (AISTATS), pages 2021–2031,

    work page 2021

  8. [17]

    Traoré, V

    C. Traoré, V. Apidopoulos, S. Salzo, and S. Villa. Variance reduction techniques for stochastic proximal point algorithms.J. Optim. Theory Appl., 203:1910–1939,

    work page 1910

Show all 26 references
  1. [18]

    Wang et al

    J. Wang et al. A field guide to federated optimization. preprint arXiv:2107.06917,

    arXiv

  2. [19]

    Xiao and T

    L. Xiao and T. Zhang. A proximal stochastic gradient method with progressive variance reduction.SIAM J. Optim., 24(4):2057–2075,

  3. [22]

    Almost sure convergence ofxt and theut i follows

    Moreover, using classical results on supermartingale convergence [Bertsekas, 2015, Proposition A.4.5], it follows from(19) thatΨ t→ 0almost surely. Almost sure convergence ofxt and theut i follows. C Corollaries of Theorem 3.1 First, we consider the casep∅ = 0in which at least...

    2015

  4. [23]

    This is better than uniform sampling withp1 =··· =pn = 1 n as in Corollary C.3 withs= 1, since the complexity now depends on¯Lh instead ofmaxiLhi

    andpi := bi b for everyi∈[n], the iteration complexity ofSMPMis O Lf µf +µg +n+ s n¯Lh µf +µg ! log Ψ0 ϵ ! ,(29) where ¯Lh = 1 n Pn i=1 p Lhi 2 . This is better than uniform sampling withp1 =··· =pn = 1 n as in Corollary C.3 withs= 1, since the complexity now depends on¯Lh ins...

    2019

  5. [24]

    InSMPM, suppose thatγt≡γ for some0 <γ < 2 Lf (or justγ >0if f = 0), ˆp= 1−p∅ 1−p∅+γµh1 and η1 = 1 1−p∅

    Then the solutionx⋆ of (1) exists and is unique. InSMPM, suppose thatγt≡γ for some0 <γ < 2 Lf (or justγ >0if f = 0), ˆp= 1−p∅ 1−p∅+γµh1 and η1 = 1 1−p∅ . Define the Lyapunov function, for everyt≥0, Ψt := 1−p ∅ +γµ h1 1−p ∅ xt−x⋆ 2 + 1 1−p ∅ γ2 1−p ∅ + 2γ Lh1 +µh1 ut 1−∇h 1(x⋆)...

    2023

  6. [25]

    Almost sure convergence ofxt and theut i follows

    Moreover, using classical results on supermartingale convergence [Bertsekas, 2015, Proposition A.4.5], it follows from(37) thatΨ t→ 0almost surely. Almost sure convergence ofxt and theut i follows. F Proof of Theorem 3.3 We considerSMPM-EXT, an extended version ofSMPMwith addi...

    2015

  7. [26]

    We can compare our linear rates to known rates in the literature, keeping in mind that they are not for the same Lyapunov function

    ThenSMPMreverts to theDavis–Yin algorithm, as discussed in Section 2.1. We can compare our linear rates to known rates in the literature, keeping in mind that they are not for the same Lyapunov function. Our rate in (35) is ρ= max max(1−γµ f,γLf−1) 2 (1 +γµg)(1 +γµh) , γ(Lh +µ...

    2022

  8. [2013]

    20 Appendix A General Convergence Analysis We begin the analysis ofSMPMin the general case. Letx⋆ and u⋆ i∈∂h i(x⋆), i = 1,...,n , form a solution to (2), and let a constantˆµh be such that0≤ˆµh≤min i∈[n] 2ηiµhiLhi Lhi+µhi (where the fraction is replaced by2ηiµhi ifL hi = +∞)....

    2015

  9. [2014]

    Yi and E

    S. Yi and E. K. Ryu. Convergence analyses of Davis-Yin splitting via scaled relative graphs II: Convex optimization problems. preprint arXiv:2211.15604,

    arXiv

  10. [2015]

    Beznosikov, S

    A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan. On biased compression for distributed learning. preprint arXiv:2002.12410,

    2002 arXiv

  11. [2016]

    Sadiev, L

    A. Sadiev, L. Condat, and P. Richtárik. Stochastic proximal point methods for monotone inclusions under expected similarity. preprint arXiv:2405.14255,

    arXiv

  12. [2017]

    Mishchenko and P

    K. Mishchenko and P. Richtárik. A stochastic decoupling method for minimizing the sum of smooth and non-smooth functions. preprint arXiv:1905.11535v2,

    1905 arXiv

  13. [2018]

    Fatkhullin, I

    I. Fatkhullin, I. Sokolov, E. Gorbunov, Z. Li, and P. Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. preprint arXiv:2110.03294,

    arXiv

  14. [2019]

    R. M. Gower, M. Schmidt, F. Bach, and P. Richtárik. Variance-reduced methods for machine learning.Proc. of the IEEE, 108(11):1968–1983, Nov

    1968

  15. [2020]

    Bonawitz, V

    K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth. Practical secure aggregation for privacy-preserving machine learning. InProc. of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175–1191,

    2017

  16. [2021]

    Hanzely and P

    F. Hanzely and P. Richtárik. One method to rule them all: Variance reduction for data, parameters and many new methods. preprint arXiv:1905.11266,

    1905 arXiv

  17. [2023]

    Condat and P

    L. Condat and P. Richtárik. A simple linear convergence analysis of the Point-SAGA algorithm. preprint arXiv:2405.19951,

    arXiv

  18. [2024]

    Condat, I

    L. Condat, I. Agarský, and P. Richtárik. Provably doubly accelerated federated learning: The first theoretically successful combination of local training and compressed communication. preprint arXiv:2210.13277, 2022a. L. Condat, K. Li, and P. Richtárik. EF-BV: A unified theory...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.