{"id":"ea9910e6-c5f3-4df9-a857-65ffeedcd2d1","arxiv_id":"2412.17082","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"EF21-P and MARINA-P provably achieve optimal O(1/sqrt(T)) subgradient convergence in distributed non-smooth convex optimization with server-to-worker compression under constant, decreasing, and Polyak stepsizes.","lead":"Two compressed federated optimization algorithms, EF21-P and MARINA-P, are shown to converge at the optimal O(1/sqrt(T)) rate on non-smooth convex problems when the server compresses its messages to clients. The paper provides the first distributed non-smooth analysis of server-to-worker compression, but the experimental evidence for the claimed performance advantage is limited to a single tuned synthetic benchmark.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"MARINA-P's O(1/√T) guarantee is stated for an average of per-worker local loss gaps, not for the global objective f(x_T); the advertised rate for distributed non-smooth optimization is stronger than Theorem 2 proves.","rationale":"The reader's synchronization concern is real but is a standard-model repair: synchronous lossless broadcast is the default distributed setting and can be added as an explicit assumption. The metric issue is more load-bearing because it directly affects what Theorem 2 means and whether the abstract's claim of an optimal rate for MARINA-P in distributed non-smooth optimization is true for the global model. The algebra of the proofs appears internally consistent: the Lyapunov derivations for both algorithms check out, and the EF21-P distributed extension is valid because all workers evaluate at the same w_t. The remaining soft spot is that the MARINA-P convergence statement is for 1/n Σ f_i(w_i^T)−f(x*), which is a weaker, personalized-objective quantity, not the usual f(x_T)−f(x*). Because this can be repaired by an honest restatement of the metric or by adding a global-rate theorem, the correct disposition remains conditional; I keep the reader's CONDITIONAL verdict, so no change is needed.","tokens_in":46355,"tokens_out":18877,"duration_ms":174574,"concrete_test":"Re-derive Theorem 2 aiming at E[f(x_T)−f(x*)]≤ε (or at E[f(bar(w)_T)−f(x*)] with bar(w)_T=(1/n)Σ_i w_i^T) using Lemma 5 and the proof's Jensen/Cauchy-Schwarz steps; if a term involving (1/n)Σ_i ||w_i^t−x_t||^2 or ||x_t−x*||^2 must appear and cannot be driven to o(1), the advertised global rate fails. Alternatively, run MARINA-P on the two-worker example f_1(x)=|x|, f_2(x)=|x−10| and compare 1/2(f_1(w_1^T)+f_2(w_2^T))−f(x*) with f(x_T)−f(x*); if the former goes to 0 while the latter does not, the theorem's metric is not the paper's stated objective.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 (Eqs. 20-28) bounds E[1/n Σ_i f_i(w_i^T) − f(x*)] where w_i^T are per-worker ergodic averages. This is not the standard global suboptimality f(w)−f(x*) of any common point. Jensen gives no bridge: for f=(1/n)Σ f_i, the quantity 1/n Σ_i f_i(w_i) can be substantially smaller than f((1/n)Σ_i w_i). For example, with f_1(x)=|x| and f_2(x)=|x−10|, taking w_1=0, w_2=10 gives 1/nΣ f_i(w_i)=0 while f((w_1+w_2)/2)=5. The descent lemma (Lemma 5, Eq. 113) controls only the same averaged gap, and the proof never establishes E[f(x_T)−f(x*)]≤ε for the algorithm's output x_T. The Abstract and Section 2 claim an optimal O(1/√T) rate for distributed non-smooth optimization with MARINA-P; that claim is supportable only for a personalized/average-local-models metric. In contrast, Theorem 1 (EF21-P) uses a common w_t and genuinely bounds f(w_T)−f(x*). The MARINA-P half therefore overstates the strength of the advertised central result unless the metric is explicitly reframed or a global bound is proved.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper considers the non-smooth convex regime of distributed optimization with server-to-worker compression, a setting that is indeed less studied than the smooth case. It extends EF21-P, previously analyzed in a single-node non-smooth setting, to distributed workers, and adapts MARINA-P, originally designed for smooth non-convex problems, to non-smooth convex objectives. For both algorithms, the paper proves O(1/\\sqrt{T}) convergence rates under constant and Polyak stepsizes, O(\\log T/\\sqrt{T}) rates under decreasing stepsizes, and corresponding communication complexity bounds. The experiments compare EF21-P with Top-K compression against MARINA-P with same, independent, and correlated (Perm-K) compressors on a synthetic \\|A_i x\\|_1 finite-sum problem, reporting that correlated compressors perform best.","tokens_in":46657,"tokens_out":6079,"duration_ms":55759,"significance":"If fully supported, the paper would fill a genuine gap: it would provide the first distributed non-smooth convex guarantees with server-to-worker compression and adaptive stepsizes, at the optimal O(1/\\sqrt{T}) rate for constant and Polyak stepsizes. The EF21-P part is a genuine distributed extension and the Lyapunov-style proofs in the appendix are standard and, as far as I verified, algebraically consistent; the constant optimization in Theorem 1 and Corollary 2 checks out. However, the MARINA-P half proves a different, weaker metric than the advertised global suboptimality, and the EF21-P analysis leans on an anonymous, under-review submission. These two issues affect the paper's central claims and require substantial revision before the stated contributions can be accepted.","major_comments":[{"comment":"The guarantee proved for MARINA-P is E[1/n \\sum_i f_i(w_i^T) - f(x^*)], where w_i^T are per-worker ergodic averages, and not the standard global suboptimality E[f(x_T)-f(x^*)] at any common output. The abstract, contributions, and Corollary 2 advertise an optimal rate for distributed non-smooth optimization, which conventionally means global objective suboptimality. The descent lemma (Lemma 5, Eq. (113)) controls only this averaged local-loss gap, and no argument is given that bridges it to f at a common point. Such a bridge cannot hold in general: with f_1(x)=|x| and f_2(x)=|x-10|, taking w_1=0 and w_2=10 gives (1/2)(f_1(w_1)+f_2(w_2))=0 while f((w_1+w_2)/2)=5. The MARINA-P claims and Corollary 2 must either be explicitly reframed as guarantees for the average of local-model losses, or a genuine bound on E[f(\\bar w)-f(x^*)] for a common output must be proved.","section":"Section 4, Theorem 2 and Lemma 5 (Eqs. (20)-(28), (113))"},{"comment":"The distributed EF21-P analysis is explicitly built on the anonymous, under-review submission [Anonymous, 2024]. The paper states that the original proof of Anonymous [2024] 'remains applicable' to the distributed algorithm, and the appendix provides proofs only by 'following the approach' of that unpublished work. Because the central EF21-P guarantees rest on this source, the manuscript is not fully self-contained and its correctness cannot be independently verified from the submitted text. The authors should either cite a publicly available version of the single-node EF21-P analysis or present the single-node proof completely, with all steps, independently of the anonymous submission.","section":"Section 3 and Appendix C"},{"comment":"The distributed EF21-P analysis requires that every worker evaluates its subgradient at the identical point w_t, which is true only if the server's broadcast of the compressed difference is applied synchronously and losslessly by all workers. The algorithm description merely notes that 'this procedure ensures that the states w_t remain synchronized' (Section 3, Algorithm 1, lines 13-15), but no formal assumption of synchronous, reliable broadcast is stated. If workers go offline, receive updates with different delays, or use stale local models, the averaged subgradient is no longer a subgradient of f at a common point and the first bound of Lemma 2 fails. The distributed claim should state this synchronization requirement explicitly as an assumption.","section":"Algorithm 1 and Theorem 1"}],"minor_comments":[{"comment":"In the Polyak-stepsize proof for EF21-P, the displayed denominator of the expectation contains the term 2||\\partial f(w_t)||_2 \\sqrt{||\\partial f(w_t)||_2^2} \\sqrt{(1-p)\\omega/p}, which belongs to the MARINA-P analysis and is not part of the EF21-P stepsize. The subsequent inequality uses the correct denominator B^*||\\partial f(w_t)||_2^2, so this appears to be a copy-paste typo, but it should be corrected for readability.","section":"Appendix C.1, proof of Theorem 3, after Eq. (87)"},{"comment":"Equation (80) and the text around it write E[1/n \\sum_i f_i(w_T) - f(x^*)] in the EF21-P proof, but for EF21-P the quantity being bounded is E[f(w_T)-f(x^*)]. This notational slip should be fixed.","section":"Appendix C.1, Eq. (80) and surrounding text"},{"comment":"The reference [Anonymous, 2024] is cited with an OpenReview URL but is marked 'under review' and is anonymous. Since this work is load-bearing for the EF21-P results, the paper should either replace it with a stable, publicly verifiable reference or clearly indicate its status in the reference entry.","section":"References"},{"comment":"The experiments are limited to a single synthetic benchmark (\\|A_i x\\|_1 with tridiagonal A_i). This is acceptable for a theory paper, but the title and abstract claim 'superior performance'; that claim would be stronger with at least one non-synthetic or second benchmark. The communication-cost model and the tuning procedure are described in sufficient detail, which is appreciated.","section":"Section 5 and Appendix A, Figures 1 and 7"}],"recommendation":"major_revision","confidential_remarks":"The paper's EF21-P results depend on an anonymous submission that is plausibly the authors' own work; if so, the authors should disclose this or provide a public version. The MARINA-P metric issue is substantive: the claimed global O(1/\\sqrt{T}) rate for distributed non-smooth optimization is not what Theorem 2 proves. The experimental evidence is thin, but that is secondary for a theory paper. These issues are addressable within the manuscript's scope, hence major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know before you read it. The EF21-P half is correct and genuinely bounds the global gap: because all workers share the same w_t, the averaged subgradient is a subgradient of f, and Theorem 1 delivers E[f(w_T) − f(x*)] ≤ O(1/√T) as advertised. The MARINA-P half does not. Theorem 2 bounds E[(1/n)Σ_i f_i(w_T^i) − f(x*)] over per-worker ergodic averages w_T^i, not f evaluated at any common point. The average of local gaps can be tiny while the global model is bad — f_1 = |x|, f_2 = |x−10|, w_1 = 0, w_2 = 10 gives a zero average gap while f(5) = 5. A Lipschitz bridge from their descent lemma leaves a non-vanishing term, so the abstract's \"optimal O(1/√T) for both algorithms\" is supportable only for EF21-P. The stress-test note lands.\n\nWhat the paper does well: the proofs are standard Lyapunov/subgradient arguments, and my spot-checks of the constant optimization in Theorem 1 and Corollary 2 match. The authors are honest that the EF21-P part is a distributed relabelling of the anonymous single-node analysis, and they reproduce that proof in the appendix rather than citing it into existence. The related-work survey on s2w compression is careful, and the experiments come with code. The comparison of same, independent, and correlated compressors is a reasonable sanity check, though thin: one synthetic ||Ax||_1 problem, with per-method multiplicative stepsize tuning doing real work in the comparisons.\n\nSoft spots, in proportion. The metric issue above is the big one: the experiments even plot f(x_t) − f(x*) while the MARINA-P theory bounds a different quantity. Remark 1's \"no additional communication\" for Polyak stepsizes is a minor slip: the server needs the scalar values f_i(w_t) or f_i(w_t^i) in addition to the subgradient vectors. And the distributed EF21-P analysis presumes synchronous, lossless broadcast — standard in the literature, but never stated as an assumption. The anonymous dependence is a structural risk until that paper appears, but given the appendix is self-contained I would not call it disqualifying.\n\nWho this is for: anyone working on non-smooth federated optimization or server-to-worker compression. The EF21-P result is solid and the s2w non-smooth direction is genuinely underserved. The MARINA-P part needs either an honest reframing to a personalized metric or a real global bound. That is referee-fixable, so I would send this to peer review rather than desk-reject.","headline":"EF21-P is solid and actually proves the global O(1/√T) rate; MARINA-P proves only an average-of-local-gaps rate, so the advertised 'optimal for both algorithms' overstates Theorem 2.","tokens_in":47168,"tokens_out":8590,"would_cite":true,"duration_ms":72910,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that two server-to-worker compressed federated methods, EF21-P and MARINA-P, achieve the optimal O(1/sqrt(T)) convergence rate on non-smooth convex objectives, the first such distributed guarantees with downlink…","keywords":["non-smooth convex optimization","federated learning","server-to-worker compression","EF21-P","MARINA-P","adaptive stepsizes","Polyak stepsize","communication complexity"],"falsifier":"Run distributed EF21-P on a two-worker non-smooth convex problem such as f(x) = (||x||_1 + ||x-1||_1)/2, with one worker forced to use a one-round-old w_t while the other is current, and compare the empirical suboptimality against the claimed O(1/sqrt(T)) bound; if the averaged subgradient is no longer a subgradient at a common point and the function gap stops shrinking at that rate, the synchronized evaluation premise is load-bearing.","tokens_in":46145,"feed_emoji":"📉","tokens_out":6231,"duration_ms":52058,"temperature":0.7,"pith_summary":"Non-smooth losses are common in federated learning, but theory has mostly covered smooth objectives and focused on uplink compression. This paper tries to close that gap by analyzing two downlink-compressed methods, EF21-P and MARINA-P, in the non-smooth convex setting. It proves that both methods reach the optimal O(1/sqrt(T)) function-suboptimality rate under constant and Polyak stepsizes, with a slightly worse O(log T/sqrt(T)) rate for decreasing stepsizes. The communication complexity per worker matches classical subgradient methods, so compression of the server broadcast does not asymptotically slow convergence. Experiments on synthetic L1-type objectives show MARINA-P with correlated compressors converging faster than EF21-P with Top-K compression.","feed_headline":"First downlink-compressed rates proven for non-smooth federated learning","feed_subtitle":"EF21-P and MARINA-P reach O(1/sqrt(T)) with constant and Polyak stepsizes, matching uncompressed subgradient methods.","key_machinery":"The load-bearing object is a Lyapunov function that couples the distance to the optimum with the compression error: V_t = ||x_t - x*||^2 + (1/($\\lambda$* $\\theta$)) ||w_t - x_t||^2 for EF21-P, and the analogous averaged version for MARINA-P. Two per-iteration bounds feed a descent lemma: a subgradient inequality on the update step and a contraction inequality for the biased (EF21-P) or unbiased (MARINA-P) compressor applied to the broadcast difference. The proof selects the free Young-inequality parameter $\\lambda$ optimally to minimize the constant multiplying the squared subgradient norm, yielding B* = 1 + 2 $\\sqrt$(1-$\\alpha$)/(1-$\\sqrt$(1-$\\alpha$)) for EF21-P. For MARINA-P, the worker-specific compressors allow a variance-decomposition step that keeps only the averaged subgradient norm, and the correlated Perm_K compressor makes (1/n) sum Q_i(x) = x exactly, which is why it performs best in experiments.","core_discovery":"The central claim is Theorem 1 and Theorem 2: under convexity and individual Lipschitz continuity of the client losses, distributed EF21-P and MARINA-P satisfy E[f(wbar_T)-f(x*)] <= $\\sqrt$(B* $L0^{2}$ V0)/$\\sqrt$(T) with optimally tuned constant stepsizes and with Polyak stepsizes, where B* depends only on the compression factor $\\alpha$ (for EF21-P) and on the unbiased-compression parameters omega and p (for MARINA-P). Decreasing stepsizes give E[f(w_hat_T)-f(x*)] <= 2 $\\sqrt$(2 B* $L0^{2}$ V0) $\\sqrt$(log(T+1)/T). These are the first theoretical guarantees for distributed non-smooth optimization with server-to-worker compression, and the proof extends a single-node non-smooth analysis of EF21-P by averaging subgradients at a common broadcast point w_t. A corollary gives T = O($L0^{2}$ $R0^{2}$/($\\alpha$ $epsilon^{2}$)) iterations for EF21-P and a similar epsilon-dependent bound for MARINA-P, with expected communication cost O(d + zeta_C T) per worker.","pith_inferences":["The synchronized-common-point premise suggests a testable robustness question the paper does not address: if a worker's broadcast is delayed or lost, the averaged subgradient is no longer a subgradient at a single point, so the descent lemma may fail; measuring how much staleness the method tolerates in practice would delimit the theorem's reach.","Since the optimal rate is already attained with compression, one could try to push the theory to stochastic subgradient or mini-batch settings, where random subgradient noise enters the same Lyapunov recursion.","The theoretical comparison only uses worst-case constants; the experiments hint that correlated compressors improve real constants substantially, so a sharper analysis tracking the variance reduction from Perm_K could close the gap between theory and the measured advantage.","If the downlink compression is truly free in non-smooth federated settings, system designers could compress server broadcasts aggressively without changing the asymptotic rate, which is a practical prescription worth testing on real non-smooth models."],"forward_implications":["With Top-K compression, EF21-P's communication complexity matches that of the uncompressed distributed subgradient method, so downlink compression can be added without worsening the worst-case rate.","Both methods can use the Polyak stepsize with no extra communication, because the subgradient values needed for the stepsize are already sent to the server.","For non-smooth objectives, the iteration complexity is independent of the number of workers n, in contrast to MARINA-P's smooth non-convex analysis where complexity scales like 1/n.","Decreasing stepsizes retain convergence without knowing T or f(x*) but pay a log T factor, the known limitation of subgradient methods.","MARINA-P with independent or correlated compressors outperforms EF21-P with Top-K in the reported non-smooth convex experiments, especially for many clients."],"supporting_citations":[{"why":"Introduces EF21-P, the server-to-worker compressed primal method whose smooth theory is the base for the non-smooth extension.","marker":"[Gruntkowska et al., 2023]"},{"why":"Introduces MARINA-P and correlated compressors, which the paper extends to non-smooth convex objectives.","marker":"[Gruntkowska et al., 2024]"},{"why":"Provides the single-node non-smooth convex analysis of EF21-P that this paper generalizes to the distributed setting.","marker":"[Anonymous, 2024]"},{"why":"Supplies the EF21 error-feedback machinery and the optimal parameter choice lemma used in the descent proof.","marker":"[Richtárik et al., 2021]"},{"why":"Defines the MARINA algorithm with unbiased compressors on which MARINA-P is built.","marker":"[Gorbunov et al., 2021]"},{"why":"Introduces the Perm_K correlated compressors whose exact averaging property drives MARINA-P's practical advantage.","marker":"[Szlendak et al., 2022]"},{"why":"Establishes the O(1/sqrt(T)) optimal rate for non-smooth convex subgradient methods that the paper matches.","marker":"[Nesterov, 2013]"},{"why":"Provides communication complexity bounds in distributed convex optimization used to contextualize the optimality claims.","marker":"[Arjevani and Shamir, 2015]"}],"fun_headline_variants":["First downlink-compressed rates for non-smooth federated convex optimization","Optimal rates proven for compressed non-smooth federated learning","First theory for server-to-worker compression in non-smooth federated learning","Non-smooth federated compression hits classical subgradient rates"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The analysis requires every worker to evaluate its subgradient at exactly the same synchronized point w_t each round, so a single worker that receives the broadcast late, goes offline, or uses a stale model breaks the descent inequality.","fun_headline_variants_meta":{"raw":{"variants":["First downlink-compressed rates for non-smooth federated convex optimization","Optimal rates proven for compressed non-smooth federated learning","First theory for server-to-worker compression in non-smooth federated learning","Non-smooth federated compression hits classical subgradient rates"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000695,"raw_usage":{"total_tokens":3196,"prompt_tokens":1051,"completion_tokens":2145,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":667,"completion_tokens_details":{"reasoning_tokens":2070}},"tokens_in":667,"tokens_out":2145,"duration_ms":13951,"temperature":1.0,"reasoning_tokens":2070,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:50:15.197514+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run distributed EF21-P on a two-worker non-smooth convex problem such as f(x) = (||x||_1 + ||x-1||_1)/2, with one worker forced to use a one-round-old w_t while the other is current, and compare the empirical suboptimality against the claimed O(1/sqrt(T)) bound; if the averaged subgradient is no longer a subgradient at a common point and the function gap stops shrinking at that rate, the synchronized evaluation premise is load-bearing.","supporting_citations":[],"review_version":1}