{"id":"8c37c8f0-e98b-471f-8da7-87538e5eb796","arxiv_id":"2506.13974","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For separable logistic regression, Local GD with any step size and any communication interval converges at rate O~(1/(eta K R)) after O~(eta K M) unstable rounds, beating the general O(1/R) worst-case bound.","lead":"Local gradient descent for distributed logistic regression is shown to converge for any positive step size and any number of local steps, with a rate that improves on previously known worst-case bounds after a short unstable phase. The result helps explain why non-monotonic loss behavior, normally seen as dangerous, can still lead to convergence in federated learning.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.2's transition time τ is understated: applying Lemma B.6 to Eq. (128) gives log(1 + √K/(√η γ ψ)), not log(1 + √K√(η γ ψ)); the stated τ does not satisfy the paper's own sufficient condition.","rationale":"The reader's weakest-assumption analysis focuses on separability and the γ-dependence, which are real but explicitly scoped limitations. My stress-test found a more concrete internal issue: the transition time τ in Theorem 4.2, and hence the stable-phase argument underlying Corollary 4.3, does not follow from the displayed inequality and the stated lemma. The proof of Lemma 4.9 needs a logarithmic term that is missing from the printed τ, so the last-iterate guarantee starting at r ≥ τ is not established as written. I do not claim the main phenomenon is false: the convergence-rate claim may be repairable with a corrected log factor or a sharper averaging argument, and the paper's detailed split-comparator construction is a substantial contribution. But because the explicit theorems are the paper's central deliverable, the manuscript should be accepted only conditional on fixing this derivation or explicitly weakening the stated τ. This is why I recommend CONDITIONAL rather than REJECT or UNCHANGED.","tokens_in":29737,"tokens_out":21172,"duration_ms":207438,"concrete_test":"Re-derive the transition time by applying Lemma B.6 exactly to Eq. (128), and evaluate the implied sufficient condition at the printed τ for the explicit instance n = M = K = 1, γ = 1, η = 0.01, w0 = 0, ψ = 0.5. Compute τ_printed from Eq. (140) and then evaluate the RHS of Eq. (128) at r = τ_printed. If the RHS exceeds ψ, the stated proof of Lemma 4.9 fails, and the theorem's transition time must be corrected before the stable-phase guarantee can be accepted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 4.9 and Theorem 4.2 rest on the claim that Eq. (128) is satisfied at the printed τ. In the proof of Lemma 4.9, with A = (2γ‖w0‖ + √2 + η)/(η γ² ψ), B = 1/(η γ² ψ), and C = η γ² K, Lemma B.6 gives the sufficient value r ≥ 2A + B log(1 + B√C), i.e. r ≥ 2A + (1/(η γ² ψ)) log(1 + √K/(√η γ ψ)). Theorem 4.2 instead states τ with the logarithm log(1 + √K √(η γ ψ)). Since ψ = min(γ/(140ηKM), 1/(2Mn)), the printed logarithmic argument is O(1) when ψ = γ/(140ηKM), whereas the required argument can grow like √η K^{3/2} M / γ². Thus the claimed τ can be far too small. Concretely, for n = M = K = 1, γ = 1, η = 0.01, w0 = 0, and ψ = 0.5, the printed τ is about 571, but the RHS of Eq. (128) at r = 571 is approximately (√2 + η + log(1 + η r²))/(η r) ≈ 1.67, which is larger than ψ = 0.5. So the proof does not establish the existence of r ≤ τ with the required small objective. Corollary 4.3 inherits this through its condition R ≥ τ. The paper's rate may survive with a corrected logarithmic factor, since the tilde notation can absorb it, but Theorem 4.2 and Corollary 4.3 as stated are unsupported by the supplied derivation.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper analyzes constant-stepsize Local GD for distributed logistic regression on linearly separable, heterogeneous data. The main results are Theorem 4.1, an average-iterate bound valid for every step size eta > 0 and communication interval K >= 1; Theorem 4.2, a last-iterate bound F(w_r) = O(1/(eta K (r - tau))) after a transition time tau; and Corollary 4.3, which derives the error O~(M/(gamma^5 R^2)) after tuning eta K ~ gamma^3 R/M. The proof decomposes a Local GD round into per-data-point coefficients beta^m_{r,i}, compares the trajectory with gradient descent via a split-comparator argument, and uses a gradient potential to show that the objective eventually enters a stable phase with monotone decrease. Experiments on synthetic, MNIST, and CIFAR-10 data support the qualitative phenomenon of acceleration through instability.","tokens_in":1502,"tokens_out":3435,"duration_ms":235690,"significance":"If the results are correct, the paper gives the first convergence guarantee for vanilla Local GD with unrestricted step size and communication interval in a non-worst-case problem class, improving on the worst-case O(1/R) rate for general smooth convex objectives. The appendix contains detailed proofs with explicit constants, and the paper is candid about its limitations: the rate is worse than single-machine GD in M and 1/gamma, no advantage of K > 1 is shown, and the separability assumption gamma > 0 is essential. These strengths make the contribution worth preserving, but one load-bearing point in the transition-time argument needs repair before the stated theorems are supported.","major_comments":[{"comment":"The transition time tau printed in Theorem 4.2 does not satisfy the sufficient condition derived in Lemma 4.9. With A = (2 gamma ||w0|| + sqrt(2) + eta)/(eta gamma^2 psi), B = 1/(eta gamma^2 psi), and C = eta gamma^2 K, Lemma B.6 requires r >= 2A + B log(1 + B sqrt(C)), i.e., an additive term (1/(eta gamma^2 psi)) log(1 + sqrt(K)/(sqrt(eta) gamma psi)). The manuscript instead writes log(1 + sqrt(K) sqrt(eta gamma psi)) in Eq. (6) and Eq. (130). These arguments differ by the factor 1/(eta gamma^2 psi), which can be arbitrarily large, so the stated tau is not guaranteed to satisfy Eq. (128), and the proof of Lemma 4.9 does not establish the existence of r <= tau with F(w_r) <= gamma/(70 eta K M). Theorem 4.2 and Corollary 4.3 are therefore unsupported as printed. The fix appears local: replace the logarithmic term by log(1 + sqrt(K)/(sqrt(eta) gamma psi)); the tilde-rate in Corollary 4.3 should survive.","section":"Appendix A.2, Lemma 4.9 / Theorem 4.2"},{"comment":"In the proof of Lemma 4.4, the transition from Eq. (64) to Eq. (65) appears to drop a factor of 2: the bound derived in Eq. (64) is (2 log(1 + eta gamma^2 K r^2) + eta + sqrt(2))/gamma, while Lemma 4.4 claims (log(1 + eta gamma^2 K r^2) + eta + sqrt(2))/gamma. Either the proof must justify the reduction or the lemma should state the larger bound. Since the term is logarithmic, the asymptotic results are unaffected, but the proof as written does not establish the stated lemma.","section":"Appendix A.1, Eq. (64)-(65)"}],"minor_comments":[{"comment":"Equation (120) uses |ell'(<w^m_{r,k}, x^{m,i}>)| inside the beta-weighted term without a summation over k and with an unspecified k; consistency with the definition of beta^m_{r,i} requires |ell'(<w_r, x^{m,i}>)|. This appears to be an indexing typo.","section":"Appendix A.2, Eq. (120)"},{"comment":"Lemma 4.7's condition F(w_r) <= 1/(eta K M) does not imply the condition F(w_r) <= 1/(4 eta M) needed to invoke Lemma 4.6 when K < 4. The later applications of Lemma 4.7 use the stronger threshold gamma/(70 eta K M), so the main proof is unaffected, but the lemma statement or proof should be adjusted.","section":"Lemma 4.7"},{"comment":"Theorem 4.1 is stated for every r >= 0, but the left-hand side is an average over r rounds and is undefined at r = 0; it should state r >= 1. Similarly, the transition time tau in Theorem 4.2 should be read as an integer ceiling.","section":"Theorem 4.1"},{"comment":"The abstract says the unstable phase lasts O~(eta K M) rounds, but the proof of Corollary 4.3 gives tau = O~(max(eta K M/gamma^3, M n/gamma^2)); the dependence on gamma and the second term should be reflected in the abstract for accuracy.","section":"Abstract"},{"comment":"Equation (16) has mismatched parentheses in <w_r, x^m_i)>; it should be <w_r, x^m_i>.","section":"Section 4.2, Eq. (16)"}],"recommendation":"major_revision","confidential_remarks":"The main technical issue is localized to the transition-time logarithm and seems fixable without changing the core approach. I see no grounds for rejection, but the theorem statements as printed are not supported by the supplied derivation. The reliance on lemmas from the authors' prior paper (Crawshaw et al., 2025) is acceptable because those lemmas are proven there."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper does something genuinely new: it gives the first convergence guarantee for vanilla Local GD on separable logistic regression with any step size η > 0 and any communication interval K ≥ 1. The beta-coefficient decomposition that relates the local trajectory back to a linear combination of data points is a clean way to adapt Wu et al.'s single-machine instability analysis, and the plotted experiments honestly probe both the benefit and the limitations of local steps. The authors also state plainly that their guarantee does not show an advantage for K > 1 and that parallelized GD beats this bound in theory. That is good scientific hygiene.\n\nThe central proof is mostly well built—split comparator, gradient potential, and stable-phase descent are all there with explicit constants—but there is a load-bearing bug in the transition time. In the proof of Lemma 4.9, the sufficient condition from Lemma B.6 yields a logarithmic term log(1 + B√C) with B√C = √K/(√η γ ψ). The paper instead prints log(1 + √K √(η γ ψ)). These are not interchangeable; the printed argument can be O(1) while the required argument grows like √η K^{3/2} M/γ². Concretely, with n = M = K = 1, γ = 1, η = 0.01, w₀ = 0, ψ = 0.5, the printed τ ≈ 583, but the condition that must hold is r ≥ (2γ‖w₀‖ + √2 + η + log(1 + η γ² K r²))/(η γ² ψ), whose RHS at r = 583 is around 1911. So Lemma 4.9 as stated does not go through, and Theorem 4.2 and Corollary 4.3 inherit the gap. This is not a cosmetic typo; it is an error in the derivation of the claimed transition time.\n\nThat said, the damage is proportionate. The rate M/(γ⁵ R²) depends on the tilde notation, which can absorb logarithmic factors, and the corrected τ still looks like O( (η + log(...)) KM/γ³ ), so the main qualitative conclusion—acceleration after instability—likely survives. The fix is to correct τ and re-check the conditions for the corollary. There are also smaller issues exactly as the reader flagged: Eq. (120) has an indexing typo in the beta-weighted update, and the abstract's \"unstable phase lasting eO(ηKM)\" is loose because τ also depends on inverse powers of γ and on M n.\n\nThe citation pattern is fine; the self-citation to Crawshaw et al. (2025) is appropriate since that paper contains the lemmas being reused and the prior two-stage analysis. No invented entities and no fitted constants.\n\nThis paper deserves a serious referee. It is not desk-reject material. But it is not \"accept after small revision\" either; the transition-time bug must be fixed before the main theorem can be trusted. I would send it to review with the expectation of a major revision.","headline":"Real result, solid proof structure, but the transition time τ in Theorem 4.2 is understated by a misapplied log factor, making Lemma 4.9 (and hence Theorems 4.2 and Corollary 4.3) unproven as stated; the rate likely survives with a corrected τ.","tokens_in":30687,"tokens_out":6645,"would_cite":true,"duration_ms":61834,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W40","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Local GD on separable logistic regression converges for every positive step size and every communication interval, and the instability of large updates accelerates the tail rate.","keywords":["local gradient descent","federated averaging","logistic regression","constant step size","linear separability","heterogeneous data","convergence rate","instability"],"falsifier":"Train Local GD on a linearly separable synthetic dataset with known margin $\\gamma$, choose $\\eta K = c\\gamma^3 R/M$ for large $R$, and measure $F(w_R)$; if the error does not decay like $1/R^2$ (or if the loss diverges for very large $\\eta$ with $K$ fixed), the central acceleration-by-instability claim fails.","tokens_in":29567,"feed_emoji":"⚡","tokens_out":6608,"duration_ms":60493,"temperature":0.7,"pith_summary":"Local gradient descent, where clients take K gradient steps before averaging, has only been analyzed under small step sizes that keep the loss monotonically decreasing. This paper claims that for separable logistic regression no such restriction is needed: any positive step size and any communication interval converge. The mechanism is that instability itself accelerates the algorithm: large local updates produce an initial phase of non-monotonic loss, followed by a stable phase of monotone decrease. If correct, the result gives an O~(1/$R^{2}$) rate after a short unstable phase, improving on the O(1/R) worst-case bound for general convex objectives and matching a known phenomenon in single-machine large-stepsize gradient descent.","feed_headline":"Local GD converges for any step size on separable logistic loss","feed_subtitle":"Even huge step sizes converge; after a brief unstable phase the loss drops at 1/R^2 speed.","key_machinery":"The load-bearing object is the coefficient $\\beta^m_{r,i}=\\frac1K\\sum_{k=0}^{K-1}|\\ell'(\\langle w^m_{r,k},x^m_i\\rangle)|/|\\ell'(\\langle w_r,x^m_i\\rangle)|$, which measures how much a single data point's contribution grows during $K$ local steps. Lower bounding $\\beta$ by $1/K$ and upper bounding it by $\\exp(\\|w_r\\|)$ lets the authors adapt the split-comparator and gradient-potential arguments from large-stepsize single-machine gradient descent to the distributed setting during the unstable phase. In the stable phase, the refined descent inequality $F_m(w')\\le F_m(w)+\\langle\\nabla F_m(w),w'-w\\rangle+4F_m(w)\\|w'-w\\|^2$, together with $\\|\\nabla^2F_m(w)\\|\\le F_m(w)$ and $\\|\\nabla F_m(w)\\|\\le F_m(w)$, turns a small objective value into monotone decrease.","core_discovery":"The central claim is that Local GD on linearly separable, heterogeneous logistic regression converges for every positive step size $\\eta$ and every number of local steps $K$. Averaging over the first $r$ rounds, the objective is at most $O((\\|w_0\\|^2+1+\\log^2(K+\\eta K\\gamma^2 r)+\\eta^2K^2)/(\\eta \\gamma^4 r))$; after a transition time $\\tau$, it decreases monotonically and $F(w_r)\\le 16/(\\eta\\gamma^2 K(r-\\tau))$. Choosing $\\eta K=\\tilde\\Theta(\\gamma^3 R/M)$ yields $F(w_R)\\le \\tilde O(M/(\\gamma^5 R^2))$, which improves on the $O(1/R)$ worst-case baseline. The proof compares the trajectory of Local GD to that of single-machine GD by writing each round's update as a weighted sum of data points and bounding the per-data-point coefficient ratios.","pith_inferences":["If the rate is tight, the practical recipe for separable federated problems is to push the product $\\eta K$ into the unstable regime; the loss spikes early but the tail convergence is faster than any monotone small-step schedule.","Because the bound treats $\\eta$ and $K$ only through the product $\\eta K$, it does not distinguish local steps from a single larger global step; the experiments suggest $K$ may shorten the unstable phase, so a sharper transition-time analysis could be the place to prove a genuine benefit of local steps.","A natural extension is to Local SGD: the same $\\beta$-coefficient comparison should carry over, since a stochastic analogue of the single-machine large-stepsize analysis exists for logistic regression.","The reliance on margin suggests a testable boundary: as data approach non-separability ($\\gamma\\to 0$), the predicted time to stability diverges, so large-stepsize Local GD should visibly slow down or diverge on nearly non-separable datasets."],"forward_implications":["For any fixed step size and communication interval, the average loss over the first $r$ rounds tends to zero, so no step-size cap is needed for convergence.","Once the loss falls below a small threshold, every subsequent round decreases the objective monotonically, at rate $16/(\\eta\\gamma^2 K(r-\\tau))$.","With $\\eta K$ chosen as $\\tilde\\Theta(\\gamma^3 R/M)$, the error after $R$ rounds is $\\tilde O(M/(\\gamma^5 R^2))$, an improvement over the $O(1/R)$ worst-case rate for general smooth convex objectives.","The rate depends on the global margin $\\gamma$, not on how the data are distributed among clients; heterogeneous splits do not change the bound.","The transition time to the stable phase is proportional to $\\eta K$ and scales with $1/(\\gamma^2\\psi)$, so large step sizes and long intervals delay stability but still pay off in the final rate."],"supporting_citations":[{"why":"Supplies the split-comparator and gradient-potential techniques for large-stepsize GD that the proof adapts to Local GD.","marker":"Wu et al., 2024a"},{"why":"Introduces the two-stage Local GD baseline and the problem-specific lemmas and datasets that this analysis reuses.","marker":"Crawshaw et al., 2025"},{"why":"Establishes the worst-case Local SGD rate with $\\eta\\le O(1/K)$ that this paper shows is overly restrictive for logistic regression.","marker":"Woodworth et al., 2020b"},{"why":"Provides another worst-case baseline requiring $\\eta=1/K$, used for comparison in Table 1.","marker":"Koloskova et al., 2020"},{"why":"Gives the worst-case lower bound for Local SGD on a convex class, showing the $O(1/R)$ barrier that this paper breaks for separable logistic regression.","marker":"Patel et al., 2024"}],"fun_headline_variants":["Local GD converges for any step size on separable logistic loss","No step size limit: Local GD on separable logistic regression","Instability fuels faster convergence for Local GD on logistic loss","Acceleration by instability: Local GD beats O(1/R) for logistic loss","Huge steps fine: Local GD converges fast on separable logistic data"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The global dataset is linearly separable, so the margin $\\gamma$ is positive; all the rates scale with inverse powers of $\\gamma$, and without separability the guarantees become vacuous.","fun_headline_variants_meta":{"raw":{"variants":["Local GD converges for any step size on separable logistic loss","No step size limit: Local GD on separable logistic regression","Instability fuels faster convergence for Local GD on logistic loss","Acceleration by instability: Local GD beats O(1/R) for logistic loss","Huge steps fine: Local GD converges fast on separable logistic data"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00083,"raw_usage":{"total_tokens":3602,"prompt_tokens":897,"completion_tokens":2705,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":2617}},"tokens_in":513,"tokens_out":2705,"duration_ms":18982,"temperature":1.0,"reasoning_tokens":2617,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:56:34.016052+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train Local GD on a linearly separable synthetic dataset with known margin $\\gamma$, choose $\\eta K = c\\gamma^3 R/M$ for large $R$, and measure $F(w_R)$; if the error does not decay like $1/R^2$ (or if the loss diverges for very large $\\eta$ with $K$ fixed), the central acceleration-by-instability claim fails.","supporting_citations":[{"cited_title":"Local steps speed up local gd for heterogeneous distributed logistic regression","cited_arxiv_id":null,"evidence_quote":"Introduces the two-stage Local GD baseline and the problem-specific lemmas and datasets that this analysis reuses."},{"cited_title":"K., Glasgow, M., Zindari, A., Wang, L., Stich, S","cited_arxiv_id":null,"evidence_quote":"Gives the worst-case lower bound for Local SGD on a convex class, showing the $O(1/R)$ barrier that this paper breaks for separable logistic regression."}],"review_version":2}