{"id":"fbf0b041-99a1-44dd-8a83-c1f3962eda76","arxiv_id":"2505.12409","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"SMPM is a stochastic multi-proximal method that recovers several existing algorithms as special cases and provides new linear and accelerated sublinear convergence guarantees for nonsmooth convex problems.","lead":"The paper introduces SMPM, a stochastic algorithm for nonsmooth convex optimization that randomly updates a subset of proximal terms at each iteration. It unifies Point-SAGA, ProxSkip, and RandProx under one framework and proves new convergence rates, including accelerated O(1/t^2) results for strongly convex problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's nonsmooth linear convergence is not proven as stated: Assumption 3.2 assumes differentiable h_i, and the footnote's subgradient extension requires a selection-consistency condition that can fail.","rationale":"The reader's conditional verdict is appropriate. I reviewed the main smooth-case proof (Section A and Appendix B), the O(1/t^2) proofs (Appendices G and H), and the distributed setting; the algebra is coherent and the rates are internally consistent in those parts. The single most load-bearing weakness is exactly the transition from Assumption 3.2's differentiability to Theorem 3.3's nonsmooth L_h = +∞ claim. The footnote defers to Sadiev et al., but for nonsmooth h_i the subdifferential is set-valued and the algorithm selects a specific element via the prox update. The proof's use of (5) in Appendix F therefore requires the selected subgradients to satisfy a similarity inequality that is not guaranteed and can be violated, as the |·| example shows. This gap does not invalidate the smooth-case linear convergence, the n=1 result, or the O(1/t^2) results; it means the nonsmooth linear convergence claim is not fully supported as written. Since the reader already conditioned acceptance on clarifying this assumption, my read does not change the verdict; it strengthens the same concern.","tokens_in":38770,"tokens_out":15544,"duration_ms":146201,"concrete_test":"Run the following check: set n=2, X=R, h_1 = h_2 = |·|, f = g = 0, x* = 0, and choose u*_1 = 1, u*_2 = -1. Initialize SMPM-EXT with u_0^1 = -1, u_0^2 = 1, z_0^1 = z_0^2 = 0, and any sampling with p∅ = 0. At every iteration, if both z's remain 0 and u_t^1 = -1, u_t^2 = 1, the subgradient version of inequality (5) gives left side 4 and right side 0, so no finite δ exists. If this configuration is admissible, the footnote's claim that nonsmoothness is solely a notational issue is false, and Theorem 3.3 must be revised with an explicit subgradient-selection condition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline includes linear convergence for nonsmooth h_i via Theorem 3.3, but the theorem's formal assumption, Assumption 3.2, requires each h_i to be differentiable. Theorem 3.3 explicitly allows L_h = +∞, and the only bridge is a footnote saying gradients can be replaced by subgradients following Sadiev et al. This is not a purely notational change. For nonsmooth convex h_i, the subdifferential is set-valued, and the algorithm's prox update selects a particular subgradient u_t^i that is not a continuous function of the auxiliary point z_t^i. The proof in Appendix F relies on the identity u_t^i = ∇h_i(z_t^i) and applies inequality (5) with those selected subgradients. For the subgradient version of (5) to hold, one must impose an additional selection-consistency condition: the particular subgradients produced by the algorithm must satisfy the similarity inequality relative to the chosen u*_i. This is not stated. A concrete failure mode: take n=2, h_1 = h_2 = |·|, f = g = 0, x* = 0, choose u*_1 = 1, u*_2 = -1, and initialize SMPM-EXT with u_0^1 = -1, u_0^2 = 1, z_0^1 = z_0^2 = 0. The algorithm can keep z_t^i = 0 and u_t^1 = -1, u_t^2 = 1, in which case the left side of the subgradient version of (5) is 4 while the right side is 0, so no finite δ exists. Thus the advertised nonsmooth linear convergence is not established by the submitted proof as written; it needs either a precise selection-consistency assumption or a genuinely different argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39145,"tokens_out":26445,"duration_ms":231321,"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":[{"comment":"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).","section":"Theorem 3.3, Assumption 3.2, Appendix F"}],"minor_comments":[{"comment":"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.","section":"Section 5, paragraph after Algorithm 2"},{"comment":"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)).","section":"Appendix F, first paragraph"},{"comment":"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.","section":"Appendices G and H"},{"comment":"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'.","section":"Sections 2.1 and 6.3"}],"recommendation":"major_revision","confidential_remarks":"The main blocker is the gap between Assumption 3.2 (differentiable h_i) and the paper's advertised nonsmooth linear-convergence claims. I would ask the authors either to restrict the claims to the differentiable setting or to provide a rigorous subgradient analysis. The paper leans heavily on prior work by the same group, but the appendix proofs are self-contained, so this is not a circularity problem; still, the novelty claims relative to Sadiev et al. (2024) and Condat and Richtarik (2024) should be checked carefully during revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the core of this paper is solid and valuable: SMPM recovers and extends a batch of known stochastic proximal methods under one arbitrary-sampling, biased-averaging framework, and the paper proves genuinely new rates, including the O(1/t^2) strong-convexity-only result that even improves Point-SAGA. Second, the advertised linear convergence for nonsmooth functions under similarity, Theorem 3.3, is not actually proven as stated. The formal Assumption 3.2 requires differentiability; the footnote says subgradients can replace gradients by following Sadiev et al., but for nonsmooth h_i the algorithm selects particular subgradients, and the proof in Appendix F needs those selections to satisfy a similarity inequality relative to the chosen u*_i. That selection-consistency condition is not stated, and it is not automatic. A concrete example with h1=h2=|x|, f=g=0, x*=0, and suitably initialized u's keeps z_t=0 and u_t constant, so the left side of the subgradient version of (5) is 4 while the right side is 0. So the theorem as written doesn't cover nonsmooth h_i; it needs an explicit assumption on how subgradients are chosen, or a different argument.\n\nWhat's genuinely new and good: the framework itself is a nice contribution. The arbitrary sampling with possibly empty batches, the biased aggregation, and the recovery of Point-SAGA, ProxSkip, RandProx, and SDM as special cases are all clear. The importance sampling corollary and the correction of the SDM mistake are useful. The accelerated O(1/t^2) results under strong convexity alone (Theorems 4.1/4.2) are new even for Point-SAGA, and the proofs look coherent. The Lyapunov analysis is detailed and self-contained; I did not find circularities. The distributed application with compressed communication is a natural extension, and the experiments support the importance-sampling and acceleration claims, though there's no code.\n\nThe soft spots, in proportion: the Theorem 3.3 gap is significant — it is a load-bearing piece of the abstract's claim about nonsmooth linear convergence. The rest of the paper's results seem fine. Minor: experiments are small-scale and no code released, but that's secondary.\n\nWho this is for: anyone working on stochastic proximal methods, variance reduction, or communication-efficient distributed convex optimization. It deserves a serious referee: major revision, not desk reject. I'd ask the authors to either prove the nonsmooth version with a proper subgradient-selection assumption or restrict the similarity theorem to smooth functions and state the nonsmooth case as an open problem.","headline":"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.","tokens_in":39649,"tokens_out":5538,"would_cite":true,"duration_ms":52709,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C15","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["stochastic proximal methods","variance reduction","nonsmooth convex optimization","arbitrary sampling","linear convergence","accelerated O(1/t^2)","federated learning","communication compression"],"falsifier":"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.","tokens_in":38572,"feed_emoji":"⚡","tokens_out":11978,"duration_ms":117474,"temperature":0.7,"pith_summary":"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.","feed_headline":"Stochastic multi-prox method converges linearly on nonsmooth sums","feed_subtitle":"One variance-reduced algorithm unifies four standard proximal methods and adds faster rates for nonsmooth problems.","key_machinery":"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.","core_discovery":"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 $$\n\\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\n$$ 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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the deterministic three-operator splitting that SMPM's full-batch update generalizes to the stochastic multi-prox setting.","marker":"[Davis and Yin, 2017]"},{"why":"Defines Point-SAGA, which SMPM recovers as the special case f=g=0 with uniform single-function sampling; the paper's new rates apply to it.","marker":"[Defazio, 2016]"},{"why":"Introduces ProxSkip, recovered when n=1 and h has zero strong convexity; the paper's n=1 analysis with p∅>0 extends and generalizes that rate.","marker":"[Mishchenko et al., 2022]"},{"why":"Proposes the Stochastic Decoupling Method, recovered when one function is sampled per step; the paper corrects its importance-sampling choice and extends it to minibatches.","marker":"[Mishchenko and Richtárik, 2019]"},{"why":"Presents RandProx/RandProx-Minibatch, the unbiased-randomization proximal framework that SMPM departs from with biased averaging and arbitrary sampling.","marker":"[Condat and Richtárik, 2023]"},{"why":"Provides the expected-similarity analysis used in the footnote to justify replacing gradients by subgradients in the δ-similarity condition.","marker":"[Sadiev et al., 2024]"},{"why":"Gives a Davis–Yin convergence rate used to benchmark the linear rate of SMPM in the deterministic n=1 case.","marker":"[Yi and Ryu, 2022]"},{"why":"Gives the tight Douglas–Rachford rate used to show that the paper's n=1 rate is close to optimal when f=0 and μ_g=0.","marker":"[Giselsson and Boyd, 2017]"}],"fun_headline_variants":["Biased averaging unlocks linear rates for nonsmooth proximal sums","Stochastic multi-prox: four algorithms in one, faster on nonsmooth","Arbitrary sampling, linear or O(1/t²) rates for nonsmooth optimization","Variance reduction without unbiased estimates speeds up proximal methods","New stochastic proximal method recovers and improves four existing ones"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Biased averaging unlocks linear rates for nonsmooth proximal sums","Stochastic multi-prox: four algorithms in one, faster on nonsmooth","Arbitrary sampling, linear or O(1/t²) rates for nonsmooth optimization","Variance reduction without unbiased estimates speeds up proximal methods","New stochastic proximal method recovers and improves four existing ones"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000315,"raw_usage":{"total_tokens":1803,"prompt_tokens":983,"completion_tokens":820,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":729}},"tokens_in":599,"tokens_out":820,"duration_ms":9120,"temperature":1.0,"reasoning_tokens":729,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T20:34:32.463028+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}