{"id":"71897110-05a7-46f7-9f8a-712598cb6d08","arxiv_id":"2507.12091","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"SignSGD with momentum attains O(d^{1/2}T^{-1/4}) gradient-norm convergence under standard L2 smoothness and O(T^{-1/4}) under L-infinity smoothness, with improved distributed majority-vote rates.","lead":"This paper proves faster convergence rates for sign-based optimization algorithms that use momentum updates, improving the dependence on problem dimension and removing the need for large batches or restrictive noise assumptions. The results matter for communication-efficient distributed training, where only one-bit gradient signs are exchanged between workers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorems 3–4 contains a non-vanishing O(d√n) term, so the stated distributed rates do not follow as written.","rationale":"The Reader's CONDITIONAL verdict is reasonable: Lemma 1 is indeed false as stated, and the claim that l∞-smoothness is strictly weaker than separable smoothness needs correction. However, the most load-bearing problem for the paper's distributed claims is an internal proof error, not the bounded-gradient assumption. Assumption 9 is a strong but standard assumption; if it holds, the unbiasedness of S_G is valid, so the Reader's weakest_assumption is more about assumption compliance than an inconsistency in the argument. The Appendix D algebra error, by contrast, is an internal inconsistency: the displayed proof of Theorems 3 and 4 yields a non-vanishing 2dG√n term or, after correcting the bias calculation, fails to produce the advertised d/√n term. Since the distributed rates are a headline contribution (abstract and Tables 1–2), this requires a fix before acceptance. I would still keep the disposition CONDITIONAL rather than REJECT because Theorems 1 and 2 appear internally consistent and the distributed gap may be repairable with a corrected derivation or a revised rate statement; the authors should be given the opportunity to fix the proof and restate the theorems precisely.","tokens_in":19346,"tokens_out":18716,"duration_ms":200676,"concrete_test":"Recompute the passage in Appendix D from the line before (19) to the final displayed bound: evaluate sqrt(1/n² Σ_{j=1}^n E||S_G(v_j^t)||²) with ||S_G(v)||²=d, then substitute β=1/2 and η=O(T^{-1/2}d^{-1/2}) into the summed bound and check whether any O(d/√n) or O(d√n) term remains. If the corrected term is 2ηGd/√n and all other terms are O(√d/√T + √d/√n), then Theorems 3–4 need a revised rate or a new argument for the d/√n term.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In Appendix D, the proof of The Theorems 3 and 4 bounds the unbiased-sign bias by the chain 2ηG√d · sqrt(1/n² Σ_j E||S_G(v_j^t)||²). Since each S_G(v_j^t) has d entries in {±1}, this equals 2ηGd/√n. The manuscript instead continues with 2ηdG√n, and the final summed display before setting β=1/2 contains the term 2dG√n, which is constant in T. With the stated η=O(T^{-1/2}d^{-1/2}), no displayed term produces the advertised d/√n component of the rate: the momentum-variance term in (20) contributes only √d/√n, and the corrected sign-bias term contributes √d/(√T√n). Thus Theorems 3 and 4 are not established as printed: either the proof has a non-vanishing O(d√n) error floor, or, after correcting the algebra, the rate does not contain the claimed d/√n term. This is a load-bearing defect in a main distributed contribution, distinct from the Lemma 1 issue flagged by the Reader.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies sign-based stochastic optimization with momentum updates. In the centralized setting it proposes SMM and claims an O(d^{1/2}T^{-1/4}) l1-gradient convergence rate under l2-smoothness and bounded noise, and an O(T^{-1/4}) rate under l∞-smoothness with separable bounded noise and constant batch size. In the distributed setting it proposes two variants of MVSM using unbiased sign operations and claims rates O(d^{1/2}T^{-1/2}+dn^{-1/2}), O(n^{1/2}T^{-1}+dn^{-1/2}), and O(max{d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5}}) under node-wise smoothness, bounded noise, and uniform gradient bounds. The proofs are contained in Appendices A-E.","tokens_in":19554,"tokens_out":36546,"duration_ms":416880,"significance":"The claimed rates are potentially valuable: Theorem 1 improves the dimension dependence of momentum-based signSGD under standard l2-smoothness from O(d) to O(d^{1/2}) for the l1 norm, and Theorem 5 offers a substantially better distributed l2-norm rate than the earlier O(d^{3/8}T^{-1/8}) of Jin et al. The derivations are explicit, the parameter settings are stated, and I see no circularity or rate-fitting. However, the paper contains a false assumption-ordering claim around l∞-smoothness and an algebraic error in the distributed proof. These issues are load-bearing but appear fixable, so the underlying ideas remain worth considering after revision.","major_comments":[{"comment":"Lemma 1 is false as stated, and its proof does not establish Assumption 3. The proof derives only the quadratic upper bound f(y) <= f(x) + <grad f(x), y-x> + (1/2)(sum_i L_i)||y-x||_infty^2, which is not the gradient Lipschitz condition ||grad f(x)-grad f(y)||_1 <= L_infty ||x-y||_infty. A one-dimensional counterexample is f(x) = -x^4 + (L/2)x^2: it is separable smooth with L_1 = L because f(x) - (L/2)x^2 = -x^4 is concave, but its second derivative is unbounded below, so no finite L_infty satisfies Assumption 3. In fact Assumption 3 implies Assumption 1 with L_i = L_infty by the standard descent lemma, so the paper's claim that l∞-smoothness is weaker than separable smoothness is backwards. This affects the Introduction, the remark after Assumption 3, and Table 1. Theorem 2 itself is valid under Assumption 3, but it should not be advertised as a weakening of prior smoothness assumptions.","section":"Lemma 1 / Appendix A"},{"comment":"The proof of Theorems 3 and 4 contains a factor error. In the chain after Eq. (19), the term 2 eta G sqrt(d) sqrt(n^{-2} sum_j E||S_G(v_j^t)||^2) equals 2 eta G sqrt(d) sqrt(d/n) = 2 eta G d / sqrt(n), not 2 eta d G sqrt(n). In addition, when the per-step sum is formed, the factor eta is dropped: the displayed 2 d G sqrt(n) should still carry the factor eta. With the stated eta = O(T^{-1/2} d^{-1/2}), the printed nonvanishing O(d sqrt(n)) term is incorrect and does not lead to the claimed rates. The theorems can likely be repaired by correcting this factor and by using sigma = O(G sqrt(d)) from Assumption 9, but the proof as submitted does not establish them.","section":"Appendix D, Eq. (19) and final displayed bound"},{"comment":"Even after the algebraic correction, the d n^{-1/2} term in Theorem 3 is not visible in the displayed bound without an additional estimate. From Eq. (20), the term 2 sqrt(d) sqrt(sigma^2 beta / n) with beta = 1/2 contributes O(sigma sqrt(d) / sqrt(n)), which is O(d / sqrt(n)) only if sigma = O(G sqrt(d)). The proof never states or uses this consequence of Assumption 9. Since ||grad f_j(x; xi)||_infty <= G indeed implies sigma <= 2 G sqrt(d), the theorem is salvageable, but the derivation as printed is incomplete.","section":"Theorem 3 and Eq. (20)"}],"minor_comments":[{"comment":"The proof of Theorem 2 uses E[n_{s,i} n_{t,i}] = 0 for s != t; this requires an independence assumption across iterations that is not stated in Assumptions 4 or 5.","section":"Assumptions 4/5 and Appendix C"},{"comment":"The notation is inconsistent: sign vs. Sign, and S_R, S_G, S_1 are introduced without a unified convention.","section":"Notation throughout"},{"comment":"There is a minor typo: 'forth inequality' should be 'fourth inequality'.","section":"Appendix D"},{"comment":"The distributed rates depend on the strong uniform bound of Assumption 9 and require G to be known to the algorithm; this limitation should be stated explicitly in the introduction and in the experimental discussion.","section":"Distributed setting"}],"recommendation":"major_revision","confidential_remarks":"The two technical errors are substantive but fixable: the assumption-ordering claim around Lemma 1 is wrong, and the distributed proof has a factor error. I see no circularity, data-driven rate fitting, or inappropriate citation behavior. The paper fits the journal's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The single-node results are the real content: Theorem 1 gets O(d^{1/2}T^{-1/4}) under standard l2-smoothness and bounded variance, improving Sun et al.'s O(dT^{-1/4}) under the same conditions. Theorem 2 gets O(T^{-1/4}) under l∞-smoothness with a constant batch and no unimodal-noise assumption. I checked the momentum-variance recursions in Appendices B and C; they balance correctly and the rates follow. That part looks like honest, publishable work.\n\nThe paper has two genuine problems. First, Lemma 1 is false as stated. Separable smoothness, as defined by the quadratic upper bound with coordinate constants L_i, does not imply the l1-Lipschitz condition in Assumption 3. The proof only gives an l∞-quadratic upper bound; that does not give ||∇f(x)-∇f(y)||_1 ≤ L∞||x-y||∞. A one-dimensional f(x) = -x^2 is separable smooth with L_1 = 0, yet |f'(x)-f'(y)| = 2|x-y|. So the claim that l∞-smoothness is weaker than separable smoothness is unsupported. It does not feed into Theorems 1 or 2, so it is a positioning error, but it should be fixed or removed.\n\nSecond, the stress-test on Appendix D is right. In the bias chain, E||S_G(v_j)||^2 = d, so the sign-bias term is 2ηGd/√n, not 2ηdG√n; and the final summed display then drops η, leaving a non-vanishing 2dG√n. As printed, Theorems 3 and 4 are not established. This is an algebra slip rather than a fundamental flaw: with the corrected term, Theorem 3's bound would actually be stronger in n, and Theorem 4's d/√n term comes from the momentum-variance term. But a referee needs to see the corrected display.\n\nAssumption 9 (uniform l∞ gradient bound) is strong, but it is the standard price for the unbiased sign operator; I would not hold it against the paper.\n\nNet: the single-node rates deserve to be in the literature, and the distributed rates likely survive a fix. This paper should go to review, not be desk-rejected, but it is not acceptable as-is. I would ask for a corrected Lemma 1 and a corrected Appendix D before any acceptance.","headline":"The single-node rates are a real improvement, but the paper is not ready as written: Lemma 1 is false and the distributed proof has an algebra slip that leaves a non-vanishing floor.","tokens_in":20131,"tokens_out":13532,"would_cite":true,"duration_ms":151667,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C26","90C15","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under standard L2-smoothness, signSGD with momentum converges at rate $O(d^{1/2} T^{-1/4})$, a $\\sqrt{d}$ improvement over prior momentum signSGD, and under $L_\\infty$-smoothness it reaches the dimension-free $O(T^{-1/4})$ with constant…","keywords":["signSGD","momentum updates","non-convex optimization","stochastic gradient methods","communication-efficient distributed optimization","majority vote","convergence analysis","sign-based compression"],"falsifier":"Run SMM on $f(x) = \\frac{1}{2}\\|x\\|^2$ in dimension $d$ with coordinate noise drawn from a $t$-distribution with 3 degrees of freedom (finite variance, heavy tails, neither unimodal-symmetric nor bounded) and constant batch size 1; if $\\mathbb{E}[\\|\\nabla f(x_\\tau)\\|_1]$ does not follow $O(T^{-1/4})$ independently of $d$, Theorem 2's dimension-free claim is refuted. For the distributed theorems, the direct test is to let a single sampled gradient exceed the claimed uniform bound $G$ on one coordinate and check whether the iterate sequence still converges at the promised rate despite the failure of $\\mathbb{E}[S_G(v)] = v/G$.","tokens_in":19144,"feed_emoji":"📉","tokens_out":12731,"duration_ms":116283,"temperature":0.7,"pith_summary":"This paper tries to show that sign-based gradient methods with momentum can recover the $O(T^{-1/4})$ convergence rate of ordinary stochastic gradient methods without the two crutches earlier signSGD proofs leaned on: large batch sizes and the assumption that the gradient noise is unimodal and symmetric. The main quantitative claim is that under standard $L_2$-smoothness the method achieves $\\mathbb{E}[\\|\\nabla f(x_\\tau)\\|_1] \\leq O(d^{1/2}T^{-1/4})$, a factor $\\sqrt{d}$ better than the previous momentum signSGD bound, and that under the weaker $L_\\infty$-smoothness assumption the same algorithm achieves the dimension-free rate $O(T^{-1/4})$ with constant batch size and no noise-shape assumptions. A second set of results covers distributed majority-vote settings, where an unbiased sign operation plus momentum improves the best known rates from $O(d T^{-1/4} + d n^{-1/2})$ to $O(d^{1/2}T^{-1/2} + d n^{-1/2})$ and from $O(d^{3/8}T^{-1/8})$ to $O(\\max\\{d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5}\\})$. Why a reader should care: sign-based methods transmit only one bit per coordinate, and these results say that compression no longer has to cost a worse rate or a special noise model.","feed_headline":"Momentum signSGD hits O(T^{-1/4}) with constant batch size","feed_subtitle":"New analysis drops the large-batch and noise-symmetry crutches, improving the dimension factor by √d.","key_machinery":"The paper's engine is a momentum-corrected sign descent. Each step forms the exponential moving average $v_t = (1-\\beta)v_{t-1} + \\beta \\nabla f(x_t;\\xi_t)$ and updates $x_{t+1} = x_t - \\eta\\,\\mathrm{sign}(v_t)$. The analysis rests on the sign discrepancy bound $\\langle \\nabla f(x_t), \\mathrm{sign}(\\nabla f(x_t)) - \\mathrm{sign}(v_t)\\rangle \\leq 2\\|\\nabla f(x_t) - v_t\\|_1$, which converts the loss decrease into a descent term $-\\eta\\|\\nabla f(x_t)\\|_1$ plus a term controlled by the momentum error $\\|\\nabla f(x_t) - v_t\\|$. That error follows a geometric recursion whose steady-state square root $(\\sigma^2/(\\beta T) + \\eta^2 L^2 d/\\beta^2 + \\beta\\sigma^2)^{1/2}$ is what produces the $\\sqrt{d}$ factor under $L_2$-smoothness, and a coordinate-weighted variant under $L_\\infty$-smoothness produces the dimension-free rate. For the distributed theorems the load-bearing object is the unbiased sign operator $S_R(v)$, defined componentwise by $[S_R(v)]_k = 1$ with probability $(R+[v]_k)/(2R)$ and $-1$ otherwise, so that $\\mathbb{E}[S_R(v)] = v/R$; this is what lets each node send one bit while keeping the server-side aggregate unbiased under the uniform bound $\\|v\\|_\\infty \\leq G$.","core_discovery":"SignSGD with momentum updates — the SMM algorithm, which tracks $v_t = (1-\\beta)v_{t-1} + \\beta \\nabla f(x_t;\\xi_t)$ and updates $x_{t+1} = x_t - \\eta\\,\\mathrm{sign}(v_t)$ — converges with $\\mathbb{E}[\\|\\nabla f(x_\\tau)\\|_1] \\leq O(d^{1/2}T^{-1/4})$ under the standard $L_2$-smoothness assumption, improving the previous $O(d T^{-1/4})$ bound of momentum signSGD by a factor of $d^{1/2}$ and reducing sample complexity from $O(d^4\\epsilon^{-4})$ to $O(d^2\\epsilon^{-4})$. Under the strictly weaker $L_\\infty$-smoothness assumption the same method achieves the dimension-free rate $O(T^{-1/4})$ with a constant batch size, without assuming unimodal symmetric noise. In the distributed majority-vote setting, the MVSM algorithm uses the unbiased sign operator $S_R$ and obtains rates $O(d^{1/2}T^{-1/2} + dn^{-1/2})$, $O(n^{1/2}T^{-1} + dn^{-1/2})$, and $O(\\max\\{d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5}\\})$, the latter two improving on the previous $O(dT^{-1/4} + dn^{-1/2})$ and $O(d^{3/8}T^{-1/8})$ results.","pith_inferences":["Editorial inference: the $\\sqrt{d}$ improvement suggests the earlier $O(d)$ factor was an artifact of how the momentum error was measured, and the same second-moment square-root technique could sharpen rates for other compressed-gradient methods with bounded compressors.","Editorial inference: the unbiased sign operator $S_R$ is a general recipe for de-biasing any vector quantizer with a known bound; the distributed analysis may transfer to unbiased random-$k$ sparsification under the same uniform-bound assumption on the gradients.","Editorial inference: a testable consequence is that the dimension dependence should be directly visible — at fixed $T$, doubling $d$ should multiply the expected $\\ell^1$ gradient norm by about $\\sqrt{2}$ under $L_2$-smoothness but leave it unchanged under $L_\\infty$-smoothness; the paper's CIFAR experiments do not isolate this scaling.","Editorial note: the manuscript states that all proofs are deferred to the supplementary material; until those proofs are checked, Theorems 1-5 should be read as claimed rather than verified results."],"forward_implications":["SMM matches the $O(T^{-1/4})$ rate of SGD under $L_\\infty$-smoothness with constant batch size, removing both the large-batch requirement and the unimodal-symmetric-noise assumption of earlier signSGD analyses.","Under $L_2$-smoothness, sample complexity drops from $O(d^4\\epsilon^{-4})$ to $O(d^2\\epsilon^{-4})$, so the method becomes quadratically cheaper in the problem dimension.","MVSM keeps 1-bit communication in both directions while improving the distributed rates to $O(d^{1/2}T^{-1/2}+dn^{-1/2})$ and $O(\\max\\{d^{1/4}T^{-1/4}, d^{1/10}T^{-1/5}\\})$, beating both Sto-signSGD and MV-sto-signSGD-SIM on their own assumptions.","Theorem 4's rate $O(n^{1/2}T^{-1}+dn^{-1/2})$ is better than Theorem 3's whenever $T \\geq n/d$, a condition that holds for large $d$; the two rates trade off the number of nodes against the dimension."],"supporting_citations":[{"why":"Supplies the original signSGD and Signum analyses with large batch size $O(\\sqrt{N})$, the baseline whose crutches Theorem 2 removes.","marker":"[Bernstein et al., 2018]"},{"why":"Supplies the constant-batch rate $O(T^{-1/4})$ under unimodal symmetric noise, the assumption Theorem 2 eliminates.","marker":"[Bernstein et al., 2019]"},{"why":"Supplies the prior momentum signSGD rate $O(dT^{-1/4})$ that Theorem 1 improves by $\\sqrt{d}$, plus the distributed MV-sto-signSGD-SIM baseline.","marker":"[Sun et al., 2023]"},{"why":"Supplies the Sto-signSGD distributed method with rate $O(d^{3/8}T^{-1/8})$ that Theorem 5 outperforms.","marker":"[Jin et al., 2021]"},{"why":"Supplies Lemma E.2, the coordinate-weighted bound the proof of Theorem 2 uses to control the $\\ell^1$ momentum error under separable bounded noise.","marker":"[Liu et al., 2025]"}],"fun_headline_variants":["Constant batch signSGD momentum: √d better rate, no extra assumptions","SignSGD momentum without noise symmetry or large batches","Dimension-free rate for signSGD momentum under L∞ smoothness","Momentum signSGD: faster rates in distributed majority vote","Sign-based momentum: √d improvement, constant batch"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the distributed results, the proofs assume a known constant $G$ such that every sampled gradient coordinate at every node lies in $[-G, G]$; the unbiased sign estimator is unbiased only inside that box, so a single coordinate exceeding $G$ breaks the identity $\\mathbb{E}[S_G(v)] = v/G$ that the proof's central step depends on.","fun_headline_variants_meta":{"raw":{"variants":["Constant batch signSGD momentum: √d better rate, no extra assumptions","SignSGD momentum without noise symmetry or large batches","Dimension-free rate for signSGD momentum under L∞ smoothness","Momentum signSGD: faster rates in distributed majority vote","Sign-based momentum: √d improvement, constant batch"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000821,"raw_usage":{"total_tokens":3695,"prompt_tokens":1146,"completion_tokens":2549,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":762,"completion_tokens_details":{"reasoning_tokens":2462}},"tokens_in":762,"tokens_out":2549,"duration_ms":22720,"temperature":1.0,"reasoning_tokens":2462,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T16:57:28.418378+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SMM on $f(x) = \\frac{1}{2}\\|x\\|^2$ in dimension $d$ with coordinate noise drawn from a $t$-distribution with 3 degrees of freedom (finite variance, heavy tails, neither unimodal-symmetric nor bounded) and constant batch size 1; if $\\mathbb{E}[\\|\\nabla f(x_\\tau)\\|_1]$ does not follow $O(T^{-1/4})$ independently of $d$, Theorem 2's dimension-free claim is refuted. For the distributed theorems, the direct test is to let a single sampled gradient exceed the claimed uniform bound $G$ on one coordinate and check whether the iterate sequence still converges at the promised rate despite the failure of $\\mathbb{E}[S_G(v)] = v/G$.","supporting_citations":[],"review_version":1}