{"id":"b3cf69b9-ede2-4927-bd33-952dd7e29966","arxiv_id":"2505.06053","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Safe-EF achieves the optimal O(RM/√(δT)) rate, up to constants, for non-smooth convex distributed optimization with contractive compression and safety constraints, and the matching lower bound is established.","lead":"Safe-EF is a new algorithm for federated learning with communication compression that provably handles non-smooth objectives and safety constraints, and the paper proves a matching optimal-rate lower bound. It also shows that two popular error-feedback methods, EF21 and vanilla compressed gradient descent, fail even on a trivial two-variable non-smooth problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 6's hard instance violates Assumption 2 (||h'(0)||>M) and uses d<T for δ<0.2, so the matching lower bound is unproven as written.","rationale":"The reader's verdict is CONDITIONAL, and my stress-test also lands on CONDITIONAL: the upper bounds for Safe-EF in Theorem 2 and the stochastic extension are detailed and largely self-contained, but the lower bound in Theorem 1 is not established as written. My load-bearing concern differs in location from the reader's weakest assumption: the reader focused on Assumption 2 as the load-bearing premise for the upper-bound tuning, whereas I find that the lower-bound construction itself violates Assumption 2. The two are related because both involve the M-bounded-subgradient condition, so I mark agreement as partial. The lower-bound flaw is concrete: h'(0) has norm C>M under the stated parameter choices, so the hard instance is outside H_{R,M}; additionally, the choice d=⌊5Tδ⌋ conflicts with T≤d for δ<0.2. Both issues are likely repairable by standard modifications (constant C, suitable d=Θ(T), small μ), which is why I do not recommend rejection or unverified status. Independent support for the rest of the paper includes the explicit upper-bound proof with virtual iterates, the failure examples for CGD and EF21, and experiments that align with the large-batch requirement. The final recommendation therefore remains CONDITIONAL: the matching lower bound needs a corrected proof before the optimality claim is fully supported.","tokens_in":46761,"tokens_out":16181,"duration_ms":160290,"concrete_test":"Re-derive the hard instance of Theorem 6 with R=M=1, δ=0.1, T=100 and compute the subgradient norm at x=0. The oracle gives h'(0)=C e_1 with C=√100/(1+√(0.1·100))≈2.40, which exceeds M=1, so Assumption 2 fails. Separately, evaluate d=⌊5Tδ⌋=50 and compare with the proof's requirement T≤d. If both checks reproduce these numbers, the lower-bound proof needs a corrected construction (e.g., constant C≈M/2 with μ≈M√δ/(R√T) and d=Θ(T)) before the optimality claim is accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central optimality claim rests on Theorem 1, proved in Appendix E.2 via a hard instance h with C = M√T/(1+√δT) and μ = 2M/(R(1+√δT)). At x=0, the oracle returns h'(0) = C e_k, so ||h'(0)|| = C. For δ≤0.3 and T≥δ^{-2}, C > M; e.g., with R=M=1, δ=0.1, T=100, C = 10/(1+√10) ≈ 2.40 > 1. Thus h∉F_{R,M}, contradicting Assumption 2, and the lower bound is not established for the advertised function class. A second internal inconsistency: the proof assumes T≤d but later sets d=⌊5Tδ⌋, which for δ<0.2 makes d<T (e.g., δ=0.1, T=100 gives d=50), so the max over T coordinates is not even defined. These are not consensus disagreements but internal gaps in the lower-bound argument; the upper-bound analysis may still be sound, but the 'matches the lower bound' claim currently lacks a valid witness.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies distributed nonsmooth convex optimization with safety constraints and contractive communication compression. It first presents two failure examples showing that vanilla compressed gradient descent and the EF21 error-feedback method do not converge on a simple nonsmooth problem, and then proposes Safe-EF, an EF14-type switching-subgradient method with bidirectional compression. The main theoretical claims are a lower bound of order Ω(RM/√(δT)) for zero-respecting first-order compressed algorithms and a matching upper bound for Safe-EF, together with a high-probability stochastic extension and extensive experiments on synthetic problems and a distributed humanoid reinforcement learning task.","tokens_in":47031,"tokens_out":9733,"duration_ms":103734,"significance":"If the main claims held, this would be a significant contribution: it would provide the first optimal complexity rates for error feedback in nonsmooth constrained distributed optimization with practical contractive compressors such as Top-K, and the proposed algorithm is simple and well motivated. The failure examples for CGD and EF21 are explicit and correct, the upper-bound analysis in Appendix D is coherent, and the experimental study is thorough. However, the lower-bound proof contains a load-bearing internal inconsistency: the hard instance violates Assumption 2, so the advertised lower bound is not proved for the function class H_{R,M}. The matching lower bound is the paper's central optimality claim, so this gap prevents acceptance as written.","major_comments":[{"comment":"The hard instance h used in the lower-bound proof does not belong to the class F_{R,M} under Assumption 2. The proof sets C = M√T/(1+√δT) and, at x=0, the oracle returns h'(0)=C e_k, so ||h'(0)||=C. For the claimed parameter regime δ≤0.3 and T≥δ^{-2}, one has C>M; for example, R=M=1, δ=0.1, T=100 gives C≈2.40>1. Since Assumption 2 requires all subgradients of the objective and constraint functions to have norm at most M, the constructed h is not in F_{R,M}, and the lower bound in Theorem 1 is not established for the advertised class H_{R,M}. This is load-bearing because the paper's central claim that Safe-EF matches the lower bound depends on the same M in both bounds.","section":"Appendix E.2, Theorem 6"},{"comment":"The proof assumes T≤d when defining h(x)=C·max_{1≤j≤T} x_j, but then chooses d=⌊5Tδ⌋. For δ<0.2 this choice gives d<T; for instance, δ=0.1 and T=100 give d=50. In that case the coordinate x_T used in the max is not defined, and Lemma 3's probability calculation over T coordinates is not meaningful. The proof should either choose d≥T and redo the probability estimate, or justify a different definition of the hard instance; as written, this is a second internal inconsistency in the lower-bound argument.","section":"Appendix E.2, Step 5 of proof of Theorem 6"}],"minor_comments":[{"comment":"Several displayed rates appear to be missing division slashes: for example, O(RM√δsδT) should likely be O(RM/√(δsδT)), and similarly for the bounds in Corollary 1. Please correct these formulas so the claimed dependencies on δ, δ_s, and T are unambiguous and consistent with the proof.","section":"Theorems 2 and 3, Corollary 1"},{"comment":"The sentence 'We do not require operators {C_i}^n_{i=1} to be neither distinct nor independent' should read 'We do not require operators ... to be distinct or independent.'","section":"Section 4.1"},{"comment":"The table appears to duplicate the row for s=1.0; the third data row should presumably be s=10.0, matching the experiments in Section 6.1.","section":"Table 1"},{"comment":"The phrase 'We follow the standard follow the standard implementation provided in Brax' contains a duplicated phrase and should be corrected.","section":"Appendix I"}],"recommendation":"major_revision","confidential_remarks":"The lower-bound proof in Appendix E.2 is the main obstacle: the hard instance violates Assumption 2, so the claimed matching lower bound is currently unsupported. The upper-bound theory and experiments appear solid, and I see no evidence of circular reasoning or hidden parameter fitting. If the authors can repair the lower-bound construction, or clearly state a corrected lower bound under a different subgradient-bound assumption, the paper could be salvageable; without that repair, the central optimality claim should not be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's the honest read. The paper has a genuinely useful upper-bound contribution: Safe-EF is a clean extension of EF14 that handles nonsmooth convex objectives and functional constraints with bidirectional contractive compression, and the analysis via virtual iterates and a switching subgradient is coherent. The failure examples for vanilla CGD and EF21 on ||x||_1 are instructive, and the stochastic extension is upfront about its large-batch requirement. The citation pattern is thorough.\n\nThe soft spot is the lower-bound argument in Theorem 6, and it is not minor. The hard instance h has subgradient h'(0)=C e_k at the origin with C = M√T/(1+√δT). For δ≤0.3 and T≥δ^{-2}, C>M, so h violates Assumption 2 (M-bounded subgradients). The proof also assumes T≤d and then sets d=⌊5Tδ⌋, which gives d<T for δ<0.2. So the claimed Ω(RM/√(δT)) lower bound is not established for the advertised function class. This is a load-bearing flaw: the main 'matches the lower bound' claim for Safe-EF currently lacks a valid witness. The upper-bound rate itself may still be optimal, but that is exactly what the lower bound was supposed to certify.\n\nProportionally: the rest of the paper is in decent shape. The core upper-bound analysis (Lemmas 1-2, Theorem 5, Corollary 1) is coherent, the examples check out, and the authors are honest about limitations. The issue is isolated to the lower-bound construction, but it affects the central optimality claim.\n\nWho should read this: anyone working on compressed first-order methods for nonsmooth or constrained problems, and people in federated learning theory. It deserves a serious referee: the upper-bound and algorithmic ideas are worth engaging with, and the lower-bound gap is likely fixable with a different construction or reparameterization. I hope the editors send it out, but with a clear request to address the lower-bound proof before any acceptance.","headline":"Solid upper-bound analysis and failure examples, but the lower-bound proof has a load-bearing flaw that leaves the claimed optimality unproven.","tokens_in":47512,"tokens_out":4335,"would_cite":false,"duration_ms":41904,"reading_group":"yes","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C25","90C30","68W15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper establishes that error feedback can work for nonsmooth convex constrained optimization: no zero-respecting first-order algorithm using contractive compressors can beat $\\Omega(RM/\\sqrt{\\delta T})$ iterations, and the proposed…","keywords":["error feedback","nonsmooth convex optimization","constrained optimization","communication compression","contractive compressors","minimax lower bounds","federated learning","stochastic optimization"],"falsifier":"Run the explicit worst-case problem of Theorem 1 ($f_i(x)=C\\cdot\\max_{1\\leq j\\leq T}x_j + (\\mu/2)\\|x\\|^2\\cdot\\max\\{\\|x\\|^2, R^2\\}$, $g_i = f_i - \\min f_i$, $d=\\lceil 5T\\delta\\rceil$, Top-K with $K=\\lceil\\delta d\\rceil$ and shared randomness across workers) with Safe-EF's stated $\\gamma$ and $c$: getting a rate better than $\\Omega(RM/\\sqrt{\\delta T})$ would refute the lower bound, and divergence or violation of the $O(RM/\\sqrt{\\delta_s \\delta T})$ bound would refute the upper bound.","tokens_in":46597,"feed_emoji":"🤖","tokens_out":7428,"duration_ms":67062,"temperature":0.7,"pith_summary":"This paper claims that error feedback, the standard fix for communication-compressed training, can work in nonsmooth, constrained, distributed problems where it was previously known to fail. It proves that no zero-respecting first-order algorithm using contractive compressors can beat $\\Omega(RM/\\sqrt{\\delta T})$ iterations or constraint-violation error, and it introduces Safe-EF, which matches that rate up to a constant. This matters because it gives the first principled guarantee that aggressive compression like Top-K can be used for problems with safety constraints, a regime central to federated reinforcement learning and other safety-critical deployments. The paper also extends the guarantee to stochastic subgradients and function evaluations, at the price of a large batch size for constraint estimation.","feed_headline":"Top-K compression now provably handles nonsmooth safety constraints","feed_subtitle":"Safe-EF matches the nonsmooth lower bound and cuts robot-training communication by about 2000×.","key_machinery":"The load-bearing mechanism is a switch between objective and constraint subgradients: at each round the workers evaluate the average constraint value $g(x_t)$ (one float of communication), and choose $h_t^i = f'_i(x_t)$ when $g(x_t) \\leq c$ and $h_t^i = g'_i(x_t)$ otherwise, where $c$ is a carefully tuned threshold. These directions are transmitted with error feedback of the EF14 form, in which each worker accumulates the error between the true subgradient and the compressed message, and the server uses an EF21-P variant to compress its broadcast. The convergence proof runs on virtual iterates $\\hat{x}_t = w_t - \\gamma e_t$, whose update is an exact subgradient step without compression error, reducing the whole argument to bounding two compression-error terms by constants depending on $\\delta$, $\\delta_s$, and $M$. The lower bound rests on the zero-respecting property: in the worst-case construction each worker can discover at most one new nonzero coordinate per round, and Rand-K with shared randomness needs $1/\\delta$ rounds to pass a coordinate from one worker to all others.","core_discovery":"The central claim is a matching pair of bounds for nonsmooth convex constrained optimization with contractive compression. Theorem 1 states that for any zero-respecting first-order algorithm, there is a problem in the class with subgradients bounded by $M$, initial distance $R$, and compression level $\\delta$ such that both the function suboptimality and constraint violation at the output are at least $\\Omega(RM/\\sqrt{\\delta T})$ after $T$ rounds. Theorem 2 states that Safe-EF, a switching-subgradient error-feedback method with bidirectional compression, achieves $\\mathbb{E}[f(x_T)-f(x^*)] \\leq O(RM/\\sqrt{\\delta_s \\delta T})$ and $\\mathbb{E}[g(x_T)] \\leq O(RM/\\sqrt{\\delta_s \\delta T})$, matching the lower bound when the server compressor accuracy $\\delta_s$ is a constant. Corollary 1 makes the choice explicit: stepsize $\\gamma = R\\sqrt{\\delta_s \\delta}/(M\\sqrt{T})$ and switching threshold $c = 32RM/(\\sqrt{\\delta_s \\delta T})$. In the stochastic setting, Theorem 3 gives high-probability bounds with the same rate up to logarithmic factors, requiring a batch size of order $\\tilde{O}(\\sigma_{fv}^2/(n\\varepsilon^2))$ for $\\varepsilon$-accuracy.","pith_inferences":["The same switching mechanism may extend to nonconvex objectives: the paper's humanoid-experiment results show the algorithm enforcing constraints in a highly nonconvex policy-search problem, suggesting the convexity assumption is a proof artifact rather than an empirical requirement.","The factor $1/\\sqrt{\\delta_s \\delta}$ in the bidirectional bound might be improvable to $1/(\\sqrt{\\delta}+\\sqrt{\\delta_s})$ by allowing multiple communication rounds per iteration, a route the paper explicitly mentions but does not take.","The large batch requirement for constraint estimation is likely the algorithm's main bottleneck; a primal-dual or level-set estimator with a smaller batch could make the stochastic method sample-optimal, but no such compressed method currently exists.","A testable extension: run Safe-EF with adaptive estimation of $M$ (e.g., gradient clipping) on the $\\ell^1$-ball problem from Example 1; if it converges when $M$ is unknown, the bounded-subgradient assumption could be relaxed."],"forward_implications":["With Top-K compression, Safe-EF's total communication for $\\varepsilon$-accuracy is $O(dR^2M^2/\\varepsilon^2)$ in the worst case, matching the uncompressed switching-subgradient method even when compression is very aggressive.","The lower bound implies that in the worst case, adding workers does not improve the convergence rate, so speedups in practice must come from problem structure rather than parallelism alone.","The stochastic guarantee shows the algorithm is robust to noisy gradient and constraint estimates with high probability, and the required batch size of $\\tilde{O}(\\sigma_{fv}^2/(n\\varepsilon^2))$ grows only with the noise variance, not with the dimension.","The analysis covers any contractive compressor, such as sparsification, quantization, or low-rank approximation, as long as its accuracy parameter $\\delta$ is known, which makes the method a drop-in replacement for earlier error-feedback schemes in federated systems.","Because the server-side compression only needs accuracy $\\delta_s$, the bidirectional rate degrades by a factor $\\sqrt{\\delta_s}$, and the paper leaves open whether this dependence can be improved."],"supporting_citations":[{"why":"Defines the EF14 error-feedback update that Safe-EF builds on.","marker":"[Seide et al., 2014]"},{"why":"Introduces EF21, the variant shown to diverge on nonsmooth problems, and provides the smooth-analysis framework this paper extends.","marker":"[Richtárik et al., 2021]"},{"why":"Gives the single-node nonsmooth EF14 analysis that Theorem 2 extends to the distributed, constrained setting.","marker":"[Karimireddy et al., 2019]"},{"why":"Supplies the switching-subgradient method for functional constraints that Safe-EF adapts for safety enforcement.","marker":"[Lan and Zhou, 2020]"},{"why":"Provides the worst-case function construction adapted for the compressed lower bound in Theorem 1.","marker":"[Nesterov, 2014]"},{"why":"Introduces the zero-respecting algorithm class and the distributed compression lower-bound framework used in Theorem 1.","marker":"[Huang et al., 2022]"},{"why":"Establishes the virtual-iterate technique that carries the convergence proof of Safe-EF.","marker":"[Stich and Karimireddy, 2019]"},{"why":"Provides the martingale concentration tools used for the high-probability stochastic convergence bounds.","marker":"[Liu et al., 2023]"}],"fun_headline_variants":["Safe-EF matches lower bound for nonsmooth safe constrained","Tight nonsmooth constrained bounds with Safe-EF","Safe-EF: optimal nonsmooth safe under Top-K","Provably safe and optimal nonsmooth with compression","Communication cut 2000×: Safe-EF provably optimal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof requires that every subgradient of the objective and constraint functions has Euclidean norm at most a known bound $M$, because the stepsize and switching threshold are chosen from $M$ and every error estimate in the analysis uses this bound.","fun_headline_variants_meta":{"raw":{"variants":["Safe-EF matches lower bound for nonsmooth safe constrained","Tight nonsmooth constrained bounds with Safe-EF","Safe-EF: optimal nonsmooth safe under Top-K","Provably safe and optimal nonsmooth with compression","Communication cut 2000×: Safe-EF provably optimal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000549,"raw_usage":{"total_tokens":2640,"prompt_tokens":981,"completion_tokens":1659,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":597,"completion_tokens_details":{"reasoning_tokens":1579}},"tokens_in":597,"tokens_out":1659,"duration_ms":13415,"temperature":1.0,"reasoning_tokens":1579,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:49:41.956222+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the explicit worst-case problem of Theorem 1 ($f_i(x)=C\\cdot\\max_{1\\leq j\\leq T}x_j + (\\mu/2)\\|x\\|^2\\cdot\\max\\{\\|x\\|^2, R^2\\}$, $g_i = f_i - \\min f_i$, $d=\\lceil 5T\\delta\\rceil$, Top-K with $K=\\lceil\\delta d\\rceil$ and shared randomness across workers) with Safe-EF's stated $\\gamma$ and $c$: getting a rate better than $\\Omega(RM/\\sqrt{\\delta T})$ would refute the lower bound, and divergence or violation of the $O(RM/\\sqrt{\\delta_s \\delta T})$ bound would refute the upper bound.","supporting_citations":[],"review_version":1}