Pith. sign in

REVIEW 3 major objections 4 minor 54 references

Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2412.16414 v1 pith:MR5OWC4O submitted 2024-12-21 math.OC cs.DCcs.LG

Dmitry Bylinkin , Aleksandr Beznosikov This is my paper · ORCID
classification math.OCcs.DCcs.LG MSC 68W1590C25
keywords distributedoptimizationcommunicationcompressionHessiansimilarityacceleratedgradientmethodsvariancereductionerrorfeedbackcomplexityfederatedlearning
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [Abstract, Table 1, Section 7 (Corollary 2)] 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.
  2. [Section 7, Corollary 2 vs Theorem 2] 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).
  3. [Section 8 and Appendix G] 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.
minor comments (4)
  1. [Section 6, after Algorithm 2] 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.
  2. [Notation, Section 2] 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.
  3. [Section 7, Corollary 2] 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.
  4. [Algorithm 4, Line 6] 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}).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the complexity proofs are self-contained reductions from stated assumptions using standard external lemmas.

full rationale

The paper's derivation chain (Lemma 1 -> Theorem 1 -> Corollary 1 for OLGA; Lemma 5 -> Theorem 2 -> Corollary 2 for EF-OLGA) is a genuine mathematical argument. Lemma 1 and Lemma 5 are proved from Definition 1/2 of the compressors, Definition 3 of Hessian similarity, and standard inequalities (Nesterov smoothness, three-point identity, Allen-Zhu's geometric lemma), not from the target complexity bounds. The CC-3 bounds follow by optimizing the tuning parameters p, tau, alpha in the contraction inequalities; no fitted parameter is renamed as a prediction and no quantity is defined in terms of the result it is supposed to establish. The authors' own prior work appears only as (i) a source for the standard facts gamma_omega >= omega and gamma_beta >= beta about practical compressors and (ii) comparison baselines (Three Pillars Algorithm, Optimistic MASHA) in Table 1; neither is load-bearing for the derivation of the new algorithms. The discrepancy between Corollary 2's O(1 + gamma_beta^{1/4} sqrt(delta/mu)) and the abstract/Table 1's O(1 + beta^{1/4} sqrt(delta/mu)) is a presentation or correctness issue (the advertised bound is stronger than the proved one since gamma_beta >= beta), not a circular dependence. The derivation remains self-contained against external benchmarks.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central claim rests on the Hessian similarity and strong convexity assumptions plus properties of compressors. The hyperparameters p, θ, τ, and α are chosen by the theory, not fitted to experimental outcomes. No new physical or conceptual entities are postulated.

free parameters (4)
  • p = 1/γω for OLGA, 1/γβ for EF-OLGA
    Probability of epoch length in geometric distribution; set to balance inner and outer communication cost, not fitted to outcome data.
  • θ = min{√p√M/(8δ√ω), 1/(2δ)} for OLGA; min{p^{3/2}/(24δ), 1/(6δ)} for EF-OLGA
    Inner step size; chosen to satisfy Lemma 1 or Lemma 5 conditions.
  • τ = min{√μ θ^{1/2} p^{-1/2}/4, 1/4} for OLGA; min{θ^{1/2} p^{-1/2}/18, 1/18} for EF-OLGA
    Momentum parameter; chosen to optimize the convergence rate.
  • α = θ p^{-1}/(8τ) for OLGA; θ p^{-1}/(36τ) for EF-OLGA
    Outer step size; chosen to satisfy the contraction condition in Theorems 1 and 2.
assumptions (6)
  • domain assumption The average function f is μ-strongly convex (Assumption 1, Eq (2)).
    Required for the contraction factors in Theorems 1 and 2.
  • domain assumption Each local function fm is δ-related to f (Hessian similarity, Definition 3).
    Yields δ-smoothness of fm-f and controls variance of compressed gradient differences; central to the small-δ advantage.
  • domain assumption Compressors satisfy Definitions 1 and 2, and are independent across machines.
    Independence gives zero cross terms in variance bounds in Lemmas 1 and 5.
  • domain assumption For practical compressors, γω ≥ ω and γβ ≥ β.
    Used to simplify complexity expressions in Table 1 and discussion; overclaim for biased case when using β instead of γβ.
  • standard math Lemma 2 (geometric random variable property) and Lemma 3 (KatyushaX strong convexity lemma) from Allen-Zhu (2018b).
    Used in proofs of Lemmas 1 and 5 to handle random epoch length and outer update.
  • standard math Bregman divergence identities and strong convexity/smoothness bounds for h (Eq. 17).
    Standard convex analysis used throughout the proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity." pith.science (2026). https://pith.science/paper/MR5OWC4O

@misc{pith2026241216414,
  author       = {Pith},
  title        = {Pith review of: Accelerated Methods with Compressed Communications for Distributed Optimization Problems under Data Similarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MR5OWC4O}},
  note         = {Machine review of arXiv:2412.16414}
}
read the original abstract

In recent years, as data and problem sizes have increased, distributed learning has become an essential tool for training high-performance models. However, the communication bottleneck, especially for high-dimensional data, is a challenge. Several techniques have been developed to overcome this problem. These include communication compression and implementation of local steps, which work particularly well when there is similarity of local data samples. In this paper, we study the synergy of these approaches for efficient distributed optimization. We propose the first theoretically grounded accelerated algorithms utilizing unbiased and biased compression under data similarity, leveraging variance reduction and error feedback frameworks. Our results are of record and confirmed by experiments on different average losses and datasets.

Figures

Figures reproduced from arXiv: 2412.16414 by the authors.

Figure 3
Figure 3. Comparison of state-of-the-art distributed methods. The [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Comparison of state-of-the-art distributed methods. The [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Comparison of state-of-the-art distributed methods. The [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figures from the paper (31 more)
Figure 6
Figure 6. Figure 6: Comparison of state-of-the-art distributed methods. The [PITH_FULL_IMAGE:figures/full_fig_p007_6.png]
Figure 7
Figure 7. Figure 7: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p021_7.png]
Figure 8
Figure 8. Figure 8: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p022_8.png]
Figure 9
Figure 9. Figure 9: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p022_9.png]
Figure 10
Figure 10. Figure 10: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p022_10.png]
Figure 11
Figure 11. Figure 11: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p023_11.png]
Figure 12
Figure 12. Figure 12: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p023_12.png]
Figure 13
Figure 13. Figure 13: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p023_13.png]
Figure 14
Figure 14. Figure 14: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p024_14.png]
Figure 15
Figure 15. Figure 15: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p024_15.png]
Figure 16
Figure 16. Figure 16: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p024_16.png]
Figure 17
Figure 17. Figure 17: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p025_17.png]
Figure 18
Figure 18. Figure 18: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p025_18.png]
Figure 19
Figure 19. Figure 19: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p025_19.png]
Figure 20
Figure 20. Figure 20: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p026_20.png]
Figure 21
Figure 21. Figure 21: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p026_21.png]
Figure 22
Figure 22. Figure 22: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p026_22.png]
Figure 23
Figure 23. Figure 23: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p027_23.png]
Figure 24
Figure 24. Figure 24: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p027_24.png]
Figure 25
Figure 25. Figure 25: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p027_25.png]
Figure 26
Figure 26. Figure 26: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p028_26.png]
Figure 27
Figure 27. Figure 27: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p028_27.png]
Figure 28
Figure 28. Figure 28: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p028_28.png]
Figure 29
Figure 29. Figure 29: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p029_29.png]
Figure 30
Figure 30. Figure 30: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p029_30.png]
Figure 31
Figure 31. Figure 31: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p029_31.png]
Figure 32
Figure 32. Figure 32: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p030_32.png]
Figure 33
Figure 33. Figure 33: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p030_33.png]
Figure 34
Figure 34. Figure 34: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p030_34.png]
Figure 35
Figure 35. Figure 35: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p031_35.png]
Figure 36
Figure 36. Figure 36: Comparison of state-of-the-art distributed methods. The comparison is made on [PITH_FULL_IMAGE:figures/full_fig_p031_36.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

54 extracted references · 43 canonical work pages

  1. [1]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.a...

  2. [2]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...

  3. [3]

    Alacaoglu, A.; and Malitsky, Y. 2022. Stochastic variance reduction for variational inequality methods. In Conference on Learning Theory, 778--816. PMLR

    work page 2022

  4. [4]

    Alistarh, D.; Grubic, D.; Li, J.; Tomioka, R.; and Vojnovic, M. 2017. QSGD: Communication-efficient SGD via gradient quantization and encoding. Advances in neural information processing systems, 30

    work page 2017

  5. [5]

    Alistarh, D.; Hoefler, T.; Johansson, M.; Konstantinov, N.; Khirirat, S.; and Renggli, C. 2018. The convergence of sparsified gradient methods. Advances in Neural Information Processing Systems, 31

    work page 2018

  6. [6]

    Allen-Zhu, Z. 2018 a . Katyusha: The first direct acceleration of stochastic gradient methods. Journal of Machine Learning Research, 18(221): 1--51

    work page 2018

  7. [7]

    Allen-Zhu, Z. 2018 b . Katyusha x: Practical momentum method for stochastic sum-of-nonconvex optimization. arXiv preprint arXiv:1802.03866

    work page Pith review arXiv 2018

  8. [8]

    Alqahtani, S.; and Demirbas, M. 2019. Performance analysis and comparison of distributed machine learning systems. arXiv preprint arXiv:1909.02061

    work page Pith review arXiv 2019

Show all 54 references
  1. [9]

    Arjevani, Y.; and Shamir, O. 2015. Communication complexity of distributed convex learning and optimization. Advances in neural information processing systems, 28

    2015

  2. [10]

    Bai, H. 2022. Modern distributed data-parallel large-scale pre-training strategies for nlp models. In Proceedings of the 6th International Conference on High Performance Compilation, Computing and Communications, 44--53

    2022

  3. [11]

    Beznosikov, A.; Horv \'a th, S.; Richt \'a rik, P.; and Safaryan, M. 2023. On biased compression for distributed learning. Journal of Machine Learning Research, 24(276): 1--50

    2023

  4. [12]

    Beznosikov, A.; Richt \'a rik, P.; Diskin, M.; Ryabinin, M.; and Gasnikov, A. 2022. Distributed methods with compressed communication for solving variational inequalities, with theoretical guarantees. Advances in Neural Information Processing Systems, 35: 14013--14029

    2022

  5. [13]

    Beznosikov, A.; Scutari, G.; Rogozin, A.; and Gasnikov, A. 2021. Distributed saddle-point problems under data similarity. Advances in Neural Information Processing Systems, 34: 8172--8184

    2021

  6. [14]

    Beznosikov, A.; Tak \'a c, M.; and Gasnikov, A. 2024. Similarity, compression and local steps: three pillars of efficient communications for distributed variational inequalities. Advances in Neural Information Processing Systems, 36

    2024

  7. [15]

    Bidollahkhani, M.; and Kunkel, J. M. 2024. Revolutionizing System Reliability: The Role of AI in Predictive Maintenance Strategies. arXiv preprint arXiv:2404.13454

    2024 arXiv

  8. [16]

    Bylinkin, D.; Degtyarev, K.; and Beznosikov, A. 2024. Accelerated Stochastic ExtraGradient: Mixing Hessian and gradient similarity to reduce communication in distributed and federated learning. arXiv preprint arXiv:2409.14280

    2024 arXiv

  9. [17]

    Chang, C.-C.; and Lin, C.-J. 2011. LIBSVM: a library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 1--27

    2011

  10. [18]

    Condat, L.; Agarsk \`y , I.; Malinovsky, G.; and Richt \'a rik, P. 2023. Tamuna: Doubly accelerated federated learning with local training, compression, and partial participation. arXiv preprint arXiv:2302.09832

    2023 arXiv

  11. [19]

    Condat, L.; Maranjyan, A.; and Richt \'a rik, P. 2024. LoCoDL: Communication-Efficient Distributed Learning with Local Training and Compression. arXiv preprint arXiv:2403.04348

    2024 arXiv

  12. [20]

    Defazio, A.; Bach, F.; and Lacoste-Julien, S. 2014. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. Advances in neural information processing systems, 27

    2014

  13. [21]

    P.; Li, Z.; and Richt \'a rik, P

    Gorbunov, E.; Burlachenko, K. P.; Li, Z.; and Richt \'a rik, P. 2021. MARINA: Faster non-convex distributed learning with compression. In International Conference on Machine Learning, 3788--3798. PMLR

    2021

  14. [22]

    Gorbunov, E.; Hanzely, F.; and Richt \'a rik, P. 2020. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In International Conference on Artificial Intelligence and Statistics, 680--690. PMLR

    2020

  15. [23]

    He, Y.; Huang, X.; and Yuan, K. 2024. Unbiased compression saves communication in distributed optimization: when and how much? Advances in Neural Information Processing Systems, 36

    2024

  16. [24]

    Hendrikx, H.; Xiao, L.; Bubeck, S.; Bach, F.; and Massoulie, L. 2020. Statistically preconditioned accelerated gradient method for distributed optimization. In International conference on machine learning, 4203--4227. PMLR

    2020

  17. [25]

    Johnson, R.; and Zhang, T. 2013. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26

    2013

  18. [26]

    I.; Lee, J

    Jordan, M. I.; Lee, J. D.; and Yang, Y. 2019. Communication-efficient distributed statistical inference. Journal of the American Statistical Association

    2019

  19. [27]

    B.; Avent, B.; Bellet, A.; Bennis, M.; Bhagoji, A

    Kairouz, P.; McMahan, H. B.; Avent, B.; Bellet, A.; Bennis, M.; Bhagoji, A. N.; Bonawitz, K.; Charles, Z.; Cormode, G.; Cummings, R.; et al. 2021. Advances and open problems in federated learning. Foundations and trends in machine learning , 14(1--2): 1--210

    2021

  20. [28]

    R.; and Johansson, M

    Khirirat, S.; Feyzmahdavian, H. R.; and Johansson, M. 2018. Distributed learning with compressed gradients. arXiv preprint arXiv:1806.06573

    2018 arXiv

  21. [29]

    B.; Yu, F

    Kone c n \`y , J.; McMahan, H. B.; Yu, F. X.; Richt \'a rik, P.; Suresh, A. T.; and Bacon, D. 2016. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492

    2016 arXiv

  22. [30]

    Kovalev, D.; Beznosikov, A.; Borodich, E.; Gasnikov, A.; and Scutari, G. 2022. Optimal gradient sliding and its application to optimal distributed optimization under similarity. Advances in Neural Information Processing Systems, 35: 33494--33507

    2022

  23. [31]

    Kovalev, D.; Horv \'a th, S.; and Richt \'a rik, P. 2020. Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop. In Algorithmic Learning Theory, 451--467. PMLR

    2020

  24. [32]

    Li, Z.; Kovalev, D.; Qian, X.; and Richt \'a rik, P. 2020. Acceleration for compressed gradient descent in distributed and federated optimization. arXiv preprint arXiv:2002.11364

    2020 arXiv

  25. [33]

    Lin, D.; Han, Y.; Ye, H.; and Zhang, Z. 2024. Stochastic distributed optimization under average second-order similarity: Algorithms and analysis. Advances in Neural Information Processing Systems, 36

    2024

  26. [34]

    M.; and Nesterov, Y

    Lu, H.; Freund, R. M.; and Nesterov, Y. 2018. Relatively smooth convex optimization by first-order methods, and applications. SIAM Journal on Optimization, 28(1): 333--354

    2018

  27. [35]

    McDonald, G. C. 2009. Ridge regression. Wiley Interdisciplinary Reviews: Computational Statistics, 1(1): 93--100

    2009

  28. [36]

    Mishchenko, K.; Gorbunov, E.; Tak \'a c , M.; and Richt \'a rik, P. 2019. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09269

    2019 arXiv

  29. [37]

    Nesterov, Y. 2013. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media

    2013

  30. [38]

    Nozari, E.; Tallapragada, P.; and Cort \'e s, J. 2016. Differentially private distributed convex optimization via functional perturbation. IEEE Transactions on Control of Network Systems, 5(1): 395--408

    2016

  31. [39]

    Qian, X.; Richt \'a rik, P.; and Zhang, T. 2021. Error compensated distributed SGD can be accelerated. Advances in Neural Information Processing Systems, 34: 30401--30413

    2021

  32. [40]

    Richt \'a rik, P.; Sokolov, I.; and Fatkhullin, I. 2021. EF21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34: 4384--4396

    2021

  33. [41]

    Robbins, H.; and Monro, S. 1951. A stochastic approximation method. The annals of mathematical statistics, 400--407

    1951

  34. [42]

    Seide, F.; Fu, H.; Droppo, J.; Li, G.; and Yu, D. 2014. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Interspeech, volume 2014, 1058--1062. Singapore

    2014

  35. [43]

    Shamir, O.; Srebro, N.; and Zhang, T. 2014. Communication-efficient distributed optimization using an approximate newton-type method. In International conference on machine learning, 1000--1008. PMLR

    2014

  36. [44]

    U.; and Karimireddy, S

    Stich, S. U.; and Karimireddy, S. P. 2019. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350

    2019 arXiv

  37. [45]

    Sun, H.; Shao, Y.; Jiang, J.; Cui, B.; Lei, K.; Xu, Y.; and Wang, J. 2019. Sparse gradient compression for distributed SGD. In International Conference on Database Systems for Advanced Applications, 139--155. Springer

    2019

  38. [46]

    Tian, Y.; Scutari, G.; Cao, T.; and Gasnikov, A. 2022. Acceleration in distributed optimization under similarity. In International Conference on Artificial Intelligence and Statistics, 5721--5756. PMLR

    2022

  39. [47]

    Verbraeken, J.; Wolting, M.; Katzy, J.; Kloppenburg, J.; Verbelen, T.; and Rellermeyer, J. S. 2020. A survey on distributed machine learning. Acm computing surveys (csur), 53(2): 1--33

    2020

  40. [48]

    P.; and Jaggi, M

    Vogels, T.; Karimireddy, S. P.; and Jaggi, M. 2019. PowerSGD: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32

    2019

  41. [49]

    Weeraddana, P.; and Fischione, C. 2017. On the privacy of optimization. IFAC-PapersOnLine, 50(1): 9502--9508

    2017

  42. [50]

    Woodworth, B.; Mishchenko, K.; and Bach, F. 2023. Two losses are better than one: Faster optimization using a cheaper proxy. In International Conference on Machine Learning, 37273--37292. PMLR

    2023

  43. [51]

    Wu, Y.; Zeng, D.; Wang, Z.; Shi, Y.; and Hu, J. 2022. Distributed contrastive learning for medical image segmentation. Medical Image Analysis, 81: 102564

    2022

  44. [52]

    Yuan, X.-T.; and Li, P. 2020. On convergence of distributed approximate newton methods: Globalization, sharper bounds and beyond. Journal of Machine Learning Research, 21(206): 1--51

    2020

  45. [53]

    Zhang, Y.; and Lin, X. 2015. Disco: Distributed optimization for self-concordant empirical loss. In International conference on machine learning, 362--370. PMLR

    2015

  46. [54]

    Zhu, W.; Luo, J.; and White, A. D. 2022. Federated learning of molecular properties with graph neural networks in a heterogeneous setting. Patterns, 3(6)

    2022

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.