{"id":"a6bf04cd-fef9-4dd0-a35e-c097855da631","arxiv_id":"2412.16414","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"OLGA and EF-OLGA are the first accelerated distributed optimization methods to combine compression with Hessian similarity, achieving record communication-time complexity.","lead":"This paper designs two new distributed optimization algorithms, OLGA and EF-OLGA, that combine communication compression, local steps, and acceleration under a data-similarity condition, and proves they reduce communication time compared to previous methods. The result matters because communication time, not computation, is often the main bottleneck when training machine learning models across many machines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract and Table 1 state EF-OLGA CC-3 as O(1+β^{1/4}√(δ/μ)), while Corollary 2 proves O(1+γβ^{1/4}√(δ/μ)); since γβ≥β can be much larger, the advertised record for biased compression is not established as stated.","rationale":"I read the proofs of Lemma 1, Lemma 5, Theorem 1, and Theorem 2. The unbiased-core derivation is internally consistent: the centered variance term is genuinely unbiased because E[Q(ĝ)] = ĝ = ∇(f1-f)(x0)-∇(f1-f)(xk), and the θ restrictions follow from the δ-smoothness of f1-f. The biased proof is more intricate but I did not find a fatal gap in the error-feedback recursion. The real problem is the gap between the theorem and the advertised result: Corollary 2's CC-3 depends on γβ, while the abstract and Table 1 replace it with β. Because γβ ≥ β and the paper supplies no upper bound, the abstract's β-only expression is not a proven consequence. The reader's weakest assumption (Hessian similarity) is explicit and acknowledged in Section 5, and the paper itself notes that δ can be set to L for heterogeneous data; I therefore do not regard it as the most load-bearing issue. The strongest concern is the EF-OLGA complexity misstatement, which the reader also flagged in the rationale but not as the weakest assumption. The absence of EF-OLGA experiments further weakens empirical support, but that is secondary to the correctness of the stated complexity. The verdict remains conditional: the core algorithms and proofs appear salvageable, but the central quantitative claim for biased compression must be corrected or qualified.","tokens_in":39276,"tokens_out":32354,"duration_ms":251845,"concrete_test":"Check the EF-OLGA rows of Table 1 and the abstract against Corollary 2 by recomputing the CC-3 expression from the proof in Appendix F with p=1/γβ. Then instantiate a specific biased compressor, say top-K with K=d/4, compute its β and γβ, and compare the corrected EF-OLGA bound O(1+γβ^{1/4}√(δ/μ)) with ECLK's O(1+β^{1/2}√(L/μ)) in the δ≪L regime. If γβ^{1/4}√(δ/μ) is not ≤ β^{1/2}√(L/μ), the advertised superiority of EF-OLGA fails and the abstract and Table 1 need to be corrected to the γβ version.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim for the biased-compression half of the paper is a communication-time record for EF-OLGA. The formal result that supports it, Corollary 2 (Section 7), gives CC-3 complexity O(1+γβ^{1/4}√(δ/μ)) with p=1/γβ. However, the abstract states O(1+β^{1/4}√(δ/μ)) and Table 1 repeats this, dropping the compressor's practical compression force γβ. The paper only proves γβ ≥ β, not equality; for standard biased compressors (e.g., top-K sparsification) γβ can exceed β by a factor that grows with dimension and compression ratio. If γβ is large, the stated bound is not a consequence of the theorem, and the comparison against ECLK's O(1+β^{1/2}√(L/μ)) can reverse. This is an internal inconsistency in the headline contribution, not merely a typo: the claimed record for EF-OLGA depends on an unproven identification γβ≈β. The unbiased OLGA results do not have this problem; their γω appears correctly in Corollary 1. The proof of Theorem 2 itself appears coherent, so the issue is localized to the presentation of the biased complexity, but it is load-bearing because the paper's central first-and-record claim for EF-OLGA is exactly the quantity that is misstated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes two accelerated algorithms, OLGA and EF-OLGA, for distributed optimization under the Hessian similarity condition, using unbiased and biased compressors respectively. Both methods combine acceleration, variance reduction, and local steps, and the paper analyzes them in terms of three communication complexity measures (CC-1, CC-2, CC-3). The main advertised results are CC-3 complexities of O(1 + (M^{-1/4}+omega^{-1/2}) sqrt(delta/mu)) for OLGA and O(1 + beta^{1/4} sqrt(delta/mu)) for EF-OLGA, claimed to be records among methods exploiting similarity and compression. The paper includes detailed proofs, corollaries with parameter choices, and numerical experiments for OLGA on ridge and logistic regression problems.","tokens_in":1316,"tokens_out":5007,"duration_ms":99012,"significance":"If the claims hold, this is a meaningful step: it provides the first accelerated methods that simultaneously exploit Hessian similarity and compressed communication, with a communication-time rate that improves on existing similarity-based methods by a factor of M^{1/4} in the unbiased case. The unbiased part (OLGA) is supported by a coherent and self-contained proof, with explicit parameter settings and a clear comparison to prior work. The biased part (EF-OLGA) is more problematic: the headline bound stated in the abstract and Table 1 does not follow from the theorem as written, because the corollary's bound contains an extra factor gamma_beta. This is a load-bearing inconsistency for the claimed record in the biased setting. The derivation itself appears structurally sound, so the issue is correctable.","major_comments":[{"comment":"The abstract and Table 1 state EF-OLGA's CC-3 complexity as O(1 + beta^{1/4} sqrt(delta/mu)), but Corollary 2 proves O(1 + gamma_beta^{1/4} sqrt(delta/mu)) with p = 1/gamma_beta. The paper only establishes gamma_beta >= beta, not equality. For common biased compressors (e.g., top-K sparsification) gamma_beta can exceed beta substantially, so the advertised bound is not a consequence of the theorem. This is not a cosmetic typo: the comparison with ECLK in Table 1 (O(1 + beta^{1/2} sqrt(L/mu))) could reverse if gamma_beta is large relative to beta and delta is much smaller than L. The paper must either prove gamma_beta = O(beta) for the compressors under consideration, or change the headline bounds to use gamma_beta.","section":"Abstract, Table 1, Section 7 (Corollary 2)"},{"comment":"Corollary 2 chooses theta <= p^{3/2}/(12 delta), while Theorem 2 requires theta <= p^{3/2}/(24 delta). The corollary's stated parameter range is not covered by the theorem, so the corollary's guarantee is formally unjustified. This condition should be corrected to match the theorem (or the theorem's condition relaxed, if possible).","section":"Section 7, Corollary 2 vs Theorem 2"},{"comment":"The numerical experiments validate only OLGA; no experiments for EF-OLGA are reported. The conclusion that 'experiments confirm the superiority of our method' thus overstates the empirical support for the biased-compression algorithm. If EF-OLGA is a central contribution, the experiments should include it, at least on the same synthetic or LibSVM tasks.","section":"Section 8 and Appendix G"}],"minor_comments":[{"comment":"The sentence 'On average, we have O(1/gamma_omega + p) CC-3 for a single iteration' would benefit from a brief derivation, since the cost of sending y_{k+1} to each device (Algorithm 2, Line 5) and collecting full gradients (Line 6) is not explicitly accounted for in the definition of CC-3.","section":"Section 6, after Algorithm 2"},{"comment":"The quantities gamma_omega and gamma_beta are introduced informally ('the value showing how much the operator compresses the input vector on average'). A formal definition with the bit-count model would improve precision, especially because the corollaries rely on p = 1/gamma.","section":"Notation, Section 2"},{"comment":"The proof of Corollary 2 is not provided; the text says it repeats Corollary 1 with other constants. Since Corollary 2 contains a different dependence (gamma_beta instead of beta) and a different parameter condition, a short proof sketch or at least the explicit calculation of the resulting rates would help the reader verify the claim.","section":"Section 7, Corollary 2"},{"comment":"The displayed line 'Collect grad f(y_{k+1}) = 1/M sum grad f(y_{k+1})' is missing the subscript m on the summand; it should be grad f_m(y_{k+1}).","section":"Algorithm 4, Line 6"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this paper deserves a serious referee, but the biased-compression half needs a correction before the advertised record is credible. The OLGA results for unbiased compression look solid and are genuinely new. Combining acceleration, unbiased compression, and Hessian similarity in one method closes the gap you'd expect from the related-work table, and the proof of Lemma 1 plus Theorem 1 is detailed and coherent. The CC-3 rate O(1 + (M^{-1/4} + γω^{-1/2})√(δ/μ)) is stated correctly in Corollary 1, and the discussion comparing against Accelerated ExtraGradient and Three Pillars is fair.\n\nThe soft spot is exactly where the stress-test note lands. Corollary 2 proves EF-OLGA's CC-3 complexity as O(1 + γβ^{1/4}√(δ/μ)), but the abstract and Table 1 say O(1 + β^{1/4}√(δ/μ)). The paper only establishes γβ ≥ β, not equality, and gives no caveat for the biased case analogous to the \"γω ∼ ω\" remark in Section 6. If γβ can exceed β by a factor that grows with dimension or compression ratio, then the EF-OLGA comparison against ECLK and the \"record\" claim for biased compression do not follow from the theorem as stated. This is a presentation-level flaw, but it is load-bearing for half the paper's headline contribution.\n\nA smaller issue: EF-OLGA has no experiments at all. The experiments cover only OLGA, on two datasets and a few values of M and ω. That is fine for an illustrative check, but the reproducibility checklist explicitly says no code, no seeds, no statistical details, with the justification \"simple experiments.\" That is a weak excuse and should be addressed in revision.\n\nThe assumptions—strong convexity of f and Hessian similarity with δ ≪ L—are strong but stated honestly, and the paper explicitly notes the heterogeneous-data case δ = L. I don't think the assumptions are a flaw given the paper's scope. The citation pattern is appropriate; the authors' own prior work appears only as a comparison baseline and as a suggested extension.\n\nWho should read this: anyone working on communication-efficient distributed or federated optimization, especially on combining local steps, compression, and acceleration. The unbiased OLGA result is the main value. The biased EF-OLGA result is plausible but needs a corrected rate or a clear statement of the regime where γβ and β coincide. I would send it to peer review, with instructions that the referee should verify the biased complexity claim and ask for EF-OLGA experiments or at least a precise characterization of γβ vs β.","headline":"OLGA is a real contribution to communication-efficient distributed optimization; the biased EF-OLGA half is over-advertised because the abstract and Table 1 drop the γβ factor that actually appears in Corollary 2.","tokens_in":40126,"tokens_out":2490,"would_cite":true,"duration_ms":26484,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W15","90C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims two new accelerated algorithms, OLGA and EF-OLGA, are the first to combine compressed communication with Hessian similarity in distributed optimization, achieving record communication-time complexity.","keywords":["distributed optimization","communication compression","Hessian similarity","accelerated gradient methods","variance reduction","error feedback","communication complexity","federated learning"],"falsifier":"Run OLGA on a synthetic strongly convex quadratic problem with $M$ nodes and exactly known $\\delta$, using random sparsification RandK with compression ratio $\\omega$, and count total transmitted bits (CC-3) to reach $\\|\\nabla f(x)\\|^2\\le\\varepsilon$; the theory predicts the time scales like $1+\\sqrt{\\delta/\\mu}(M^{-1/4}+\\gamma_\\omega^{-1/2})$. If, in the similarity-dominated regime $\\delta\\ll\\mu$, doubling $M$ at fixed $\\omega$ does not shrink the similarity-dominated term by about the factor $2^{-1/4}$, the claimed $M$-dependence fails. The same check applies to the variance bound in Lemma 1: the averaged compressed difference must have variance at most $4\\omega\\delta^2/M$, and an explicit compressor plus $\\delta$-related losses violating that bound would break the proof mechanism.","tokens_in":39050,"feed_emoji":"📡","tokens_out":12551,"duration_ms":96488,"temperature":0.7,"pith_summary":"This paper attacks the communication bottleneck of distributed training, where sending gradients from many machines to a server often dominates wall-clock time. Its central claim is that data similarity — local losses whose Hessians are close to the Hessian of the average loss — can be combined with gradient compression and acceleration in a single method, something no earlier algorithm had done. The paper proposes OLGA for unbiased compressors and EF-OLGA for biased compressors, and proves communication-time (CC-3) complexities of $\\tilde O(1+\\sqrt{\\delta/\\mu}(M^{-1/4}+\\gamma_\\omega^{-1/2}))$ and $\\tilde O(1+\\beta^{1/4}\\sqrt{\\delta/\\mu})$, where $\\delta$ is the similarity constant, $\\mu$ the strong-convexity parameter, $M$ the number of nodes, and $\\gamma_\\omega,\\beta$ compression parameters. If these bounds are correct, the methods would be the fastest known in communication time for strongly convex problems with nearly homogeneous data. Experiments on ridge and logistic regression over two standard datasets support the predicted advantage.","feed_headline":"OLGA and EF-OLGA cut communication time in distributed training","feed_subtitle":"Exploiting similar local Hessians plus compression, the methods beat prior algorithms in wall-clock communication.","key_machinery":"The load-bearing object is Hessian similarity (Definition 3): every local function $f_m$ satisfies $\\|\\nabla^2 f_m(x)-\\nabla^2 f(x)\\|\\le\\delta$, which implies that each residual $f_m-f$ is $\\delta$-smooth and makes the variance of a compressed averaged gradient difference proportional to $\\omega\\delta^2/M$ instead of $\\omega L^2$. The second piece is a randomly long inner epoch, $N\\sim\\mathrm{Geom}(p)$, whose anchor point $x_0$ creates the variance-reduction effect; its analysis rests on a Bregman-divergence descent lemma for $h=f_1-f+\\frac{1}{2\\theta}\\|\\cdot\\|^2$ (Lemma 1 for unbiased, Lemma 5 for biased). The outer accelerated loop converts the epoch descent into contraction using the KatyushaX-style interpolation structure and potential functions $Y_k=\\frac{\\alpha}{\\tau}[f(y_k)-f(x^*)]$, $Z_k=\\frac{1+\\mu\\alpha}{2}\\|z_k-x^*\\|^2$. For EF-OLGA, the additional machinery is the error-feedback term $e_m^k$ stored at each node and the virtual sequence $\\tilde x_k=x_k-e_k$, which together make biased compressors analyzable.","core_discovery":"The paper's discovery is that variance reduction makes compressed gradient differences compatible with acceleration under Hessian similarity. In the unbiased case, each node sends a compressed version of $\\hat g_m^k=\\nabla f_m(x_k)-\\nabla f_1(x_k)-\\nabla f_m(x_0)+\\nabla f_1(x_0)$, anchored at a reference point $x_0$; because $f_m-f$ is $\\delta$-smooth, the variance of the averaged compressed signal is controlled by $\\omega\\delta^2/M$ rather than by the full smoothness constant $L$, so the server needs the full gradient only twice per outer iteration. This inner epoch feeds an outer accelerated framework whose Lyapunov potential yields a geometric contraction, giving OLGA. For biased compressors, EF-OLGA adds per-node error-feedback terms $e_m^k$ and a virtual iterate $\\tilde x_k=x_k-e_k$, coupling the error feedback to the accelerated outer loop and yielding the $\\beta^{1/4}$ communication-time dependence. The paper states these are the first accelerated methods combining both compression families with Hessian similarity, and the resulting CC-3 bounds are the record among the methods compared in Table 1.","pith_inferences":["Extrapolating beyond the paper: the same anchor-plus-compression mechanism should extend to client sampling, yielding a method that is simultaneously CC-2-optimal like AccSVRS and CC-3-competitive like OLGA; Appendix H sketches the modification but does not analyze it.","Extrapolating beyond the paper: because the whole advantage requires $\\delta\\ll L$, the practical sweet spot is federated learning with statistically similar (near-IID) data shards; on strongly heterogeneous shards the method would need a fallback that does not assume similarity, and the paper gives no guidance on when to switch.","Extrapolating beyond the paper: the paper leaves the lower bound for biased compression under similarity open, so EF-OLGA's $\\beta^{1/4}$ rate may not be final; a matching lower bound would certify optimality, while a faster method would point to the error-feedback coupling in Algorithm 4 as the place to relax.","Extrapolating beyond the paper: adding Gaussian noise to the compressed differences, as sketched in Appendix H, would plausibly yield differentially private variants of OLGA and EF-OLGA, but the privacy-accuracy trade-off is not quantified."],"forward_implications":["With the optimal compression strength $\\gamma_\\omega=\\Theta(\\sqrt M)$, OLGA's CC-3 complexity becomes $\\tilde O(1+\\sqrt{\\delta/\\mu}\\,M^{-1/4})$, a factor $M^{1/4}$ better than Accelerated ExtraGradient's $\\tilde O(\\sqrt{\\delta/\\mu})$; for large machine counts this is a large wall-clock saving.","EF-OLGA is the first accelerated method with biased compression under similarity, with CC-3 complexity $\\tilde O(1+\\beta^{1/4}\\sqrt{\\delta/\\mu})$, improving on the compression-only ECLK rate $\\tilde O(1+\\beta^{1/2}\\sqrt{L/\\mu})$ when $\\delta\\ll L$.","Both algorithms invoke the full gradient only twice per outer iteration; all other client-to-server messages are compressed, so the communication cost per round depends on the compression strength rather than on the dimension of the raw gradients.","The theory allows each local function $f_m$ to be nonconvex; only the average $f$ is required to be $\\mu$-strongly convex, so the method applies beyond plain quadratic losses.","Experiments on ridge and logistic regression with a9a and mushrooms datasets, with parameters taken from the theory without tuning, show OLGA converging faster in communication time than AccSVRS, Accelerated ExtraGradient, ADIANA, and LoCoDL at machine counts from 20 to 100."],"supporting_citations":[{"why":"Supplies Accelerated ExtraGradient, the similarity-plus-acceleration baseline whose CC-3 complexity OLGA improves by a factor $M^{1/4}$.","marker":"Kovalev et al. 2022"},{"why":"Supplies AccSVRS and the variance-reduction/interpolation framework under similarity that Algorithm 1 generalizes.","marker":"Lin et al. 2024"},{"why":"Supplies Three Pillars Algorithm, the best prior CC-3 method combining similarity and compression without acceleration, which OLGA dominates.","marker":"Beznosikov, Takác, and Gasnikov 2024"},{"why":"Introduces DIANA, the variance-reduction template for unbiased compressed gradient differences.","marker":"Mishchenko et al. 2019"},{"why":"Introduces ADIANA, the accelerated unbiased-compression baseline that OLGA competes against.","marker":"Li et al. 2020"},{"why":"Introduces EF21, the error-feedback framework EF-OLGA extends to biased compressors under similarity.","marker":"Richtárik, Sokolov, and Fatkhullin 2021"},{"why":"Provides the theoretical analysis of error feedback without unnatural assumptions that justifies analyzing biased compressors.","marker":"Stich and Karimireddy 2019"},{"why":"Supplies the KatyushaX outer-acceleration structure that OLGA adapts with a Bregman divergence.","marker":"Allen-Zhu 2018b"}],"fun_headline_variants":["First accelerated compressed methods exploit data similarity","OLGA and EF-OLGA set record communication complexity","Variance reduction accelerates compressed distributed training","Data similarity unlocks faster compressed distributed optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result stands or falls on the similarity constant $\\delta$ being genuinely small relative to the strong-convexity parameter $\\mu$ (and to the smoothness constant $L$); the paper itself notes that for heterogeneous data one can set $\\delta=L$, and in that case the claimed benefit over methods that ignore similarity disappears.","fun_headline_variants_meta":{"raw":{"variants":["First accelerated compressed methods exploit data similarity","OLGA and EF-OLGA set record communication complexity","Variance reduction accelerates compressed distributed training","Data similarity unlocks faster compressed distributed optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001669,"raw_usage":{"total_tokens":6595,"prompt_tokens":891,"completion_tokens":5704,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":5649}},"tokens_in":507,"tokens_out":5704,"duration_ms":33672,"temperature":1.0,"reasoning_tokens":5649,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T10:38:59.992327+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OLGA on a synthetic strongly convex quadratic problem with $M$ nodes and exactly known $\\delta$, using random sparsification RandK with compression ratio $\\omega$, and count total transmitted bits (CC-3) to reach $\\|\\nabla f(x)\\|^2\\le\\varepsilon$; the theory predicts the time scales like $1+\\sqrt{\\delta/\\mu}(M^{-1/4}+\\gamma_\\omega^{-1/2})$. If, in the similarity-dominated regime $\\delta\\ll\\mu$, doubling $M$ at fixed $\\omega$ does not shrink the similarity-dominated term by about the factor $2^{-1/4}$, the claimed $M$-dependence fails. The same check applies to the variance bound in Lemma 1: the averaged compressed difference must have variance at most $4\\omega\\delta^2/M$, and an explicit compressor plus $\\delta$-related losses violating that bound would break the proof mechanism.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Accelerated ExtraGradient, the similarity-plus-acceleration baseline whose CC-3 complexity OLGA improves by a factor $M^{1/4}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies Three Pillars Algorithm, the best prior CC-3 method combining similarity and compression without acceleration, which OLGA dominates."}],"review_version":1}