Pith. sign in

REVIEW 2 major objections 5 minor 44 references

Enhancing Parallelism in Decentralized Stochastic Convex Optimization

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read By evaluating stochastic gradients at slowly evolving averages of past iterates rather than at raw local iterates, decentralized SGD can use up to $M \leq O(\rho \sqrt{N})$ machines before the convergence rate degrades, matching…

desk verdict A real advance in decentralized SCO parallelism, with a repairable but genuine gap in the printed proof of Lemma C.2 that a referee should insist on fixing. read the letter →

arxiv 2506.00961 v1 pith:OL3CHLKA submitted 2025-06-01 cs.LG stat.ML

Ofri Eisen , Ron Dorfman , Kfir Y. Levy This is my paper
classification cs.LGstat.ML MSC 68W4090C2590C15
keywords decentralizedlearningstochasticconvexoptimizationparallelismboundgossipaveragingAnytimeSGDconsensusdistancespectralgaplinearspeedup
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

The paper claims that a simple modification of decentralized SGD—evaluate every stochastic gradient not at the current local iterate but at a slowly evolving weighted average of past iterates, and gossip both sequences—raises the number of machines that can be used without degrading the convergence rate. In the stochastic convex optimization setting, the proposed DAT-SGD algorithm achieves error $O(\sigma D_1/\sqrt{M T} + D_1^{3/2}\sqrt{L \tilde{\sigma}}/(\rho T) + L D_1^2/T)$, which lets the network grow up to $M \leq O(\rho \sqrt{N})$ machines while keeping linear speedup. This beats the previous best decentralized parallelism bound of $O(\rho^{1/2} N^{1/4})$ and, on complete or near-complete topologies where the spectral gap $\rho = \Omega(1)$, matches the centralized Mini-batch SGD ceiling. The reason the improvement is possible is that the averaged query points used for gradient evaluation spread apart more slowly than raw iterates, so the consensus distance—the term that previously forced learning rates to shrink with the cube root of $\rho/T$—is controlled at a much smaller cost.

What carries the argument

The central mechanism is the Anytime SGD two-sequence structure: alongside the standard iterate sequence $w_t$ updated by $w_{t+1} = w_t - \eta\alpha_t g_t$, the algorithm maintains query points $x_t$ formed as $\alpha$-weighted averages of past iterates, and gradients are evaluated at $x_t$ rather than $w_t$. In DAT-SGD, every machine keeps local copies of both sequences and broadcasts both through gossip averaging. The property that carries the argument is that the query points evolve more slowly than the iterates, so the query-point consensus distance $\Gamma_t = \frac{1}{M}\sum_i \|x_t^i - \bar{x}_t\|^2$ satisfies a recursion whose inhomogeneous term is damped by a factor of $1/t^2$ per round; unrolling that recursion yields $\Gamma_t = O(\tilde{\sigma}^2 \eta^2 / \rho^4)$. Injecting this into the bias bound $B_T = \sum_t \alpha_t^2 \|E\bar{g}_t - \nabla f(\bar{x}_t)\|^2 \leq L^2 \sum_t \alpha_t^2 \Gamma_t$ (Lemma 4.3) is what converts the consensus error from a $O(\eta^2/\rho)$ contribution, which forced the learning rate $\eta \lesssim (\rho/T)^{1/3}$ in prior analyses, into a $O(\eta^2/\rho^3)$ contribution that only costs an extra $1/(\rho T)$ in the final rate.

What would settle it

Construct a smooth convex problem with two machines whose gradients agree at the optimum but whose heterogeneity grows linearly with distance from it, so Assumption 2.3 fails even though the at-optimum version holds. Run DAT-SGD on a ring (small $\rho$) and measure $E[f(\bar{x}_T) - f^*]$: if the rate degrades relative to the at-optimum-bounded prediction, the pointwise heterogeneity assumption is genuinely load-bearing rather than a technical convenience.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is Theorem 4.1: for $L$-smooth convex losses with bounded gradient noise $\sigma^2$ and bounded heterogeneity $\zeta^2$, DAT-SGD with weights $\alpha_t = t$ and a carefully tuned learning rate converges at rate $O(\sigma D_1/\sqrt{M T} + D_1^{3/2}\sqrt{L \tilde{\sigma}}/(\rho T) + L D_1^2/T)$, with $\tilde{\sigma}^2 = 2\sigma^2 + \zeta^2$. Only the first term is statistical and unavoidable; the second term, which depends on the network's spectral gap $\rho$, is larger than the first by a factor that now scales as $1/(\rho T)$ rather than $1/(\rho^{2/3} T^{2/3})$, and this is what lifts the parallelism limit from $O(\rho^{1/2} N^{1/4})$ to $O(\rho \sqrt{N})$. For dense graphs with $\rho = \Omega(1)$ the decentralized rate coincides with centralized Mini-batch SGD up to constants, closing the gap that prior D-SGD analyses left even in well-connected networks. A corollary extends the bound to each machine's local iterate with an extra $M \tilde{\sigma} D_1/(\rho^2 T^2)$ term that does not change the parallelism limit. The proof's load-bearing step is Lemma 4.3, which bounds the total squared bias of the averaged gradients $B_T$ by $O(\tilde{\sigma}^2 \eta^2 / \rho^4 \cdot \sum_t \alpha_t^2)$ via the consensus distance of the query points.

Load-bearing premise

The load-bearing premise is that the heterogeneity of local gradients is bounded at every point the algorithm visits: Assumption 2.3 requires $\frac{1}{M}\sum_i \|\nabla f_i(x) - \nabla f(x)\|^2 \leq \zeta^2$ for all $x$, and Lemma C.2 uses that pointwise bound to control the gradient-consensus quantity $\Psi_t$ at arbitrary query points. If heterogeneity is only known to be bounded at the optimum, the proof of the bias bound $B_T$ does not go through and the improved parallelism bound could fail.

Editorial extensions

If this is right

  • On complete or near-complete networks ($\rho = \Omega(1)$), DAT-SGD converges at the same rate as centralized Mini-batch SGD, so adding machines no longer carries an intrinsic decentralization penalty in the convex setting.
  • The parallelism bound becomes $M \leq O(\rho \sqrt{N})$: for near-complete graphs that is $O(\sqrt{N})$, for the torus $O(N^{1/4})$, and for the ring $O(N^{1/6})$, strictly improving on the D-SGD bounds of $O(\rho^{1/2} N^{1/4})$, $O(N^{1/6})$, and $O(N^{1/8})$ respectively.
  • The transient iteration complexity, meaning the number of rounds before the statistically optimal term dominates, drops to $O(M/\rho^2)$, a factor of $M^2$ better than D-SGD.
  • Each machine's local iterate also converges at essentially the same rate (Corollary 4.2), with an extra $M \tilde{\sigma} D_1/(\rho^2 T^2)$ term that does not change the parallelism limit.
  • Experiments on synthetic least squares and Fashion MNIST follow the predicted scaling: DAT-SGD improves with more machines on torus and exponential topologies and degrades later than D-SGD on the ring, matching the theory's prediction that the topology-dependent error term eventually dominates.

Reading between the lines

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

  • The slow-query-point mechanism is not tied to convexity in principle, and the paper already uses it heuristically for non-convex neural network training; a natural testable extension is a non-convex upper bound with a parallelism term that scales like $1/(\rho T)$ rather than $1/(\rho T)^{2/3}$.
  • Combining DAT-SGD with gradient tracking, which the conclusion explicitly proposes, would likely remove the $\zeta^2$ dependence from $\tilde{\sigma}^2$ and could yield a parallelism bound that matches centralized learning even when heterogeneity is not bounded pointwise, directly testing whether Assumption 2.3 is removable.
  • The analysis assumes a symmetric doubly stochastic gossip matrix; if the same argument survives for push-style row-stochastic protocols, the parallelism improvement would transfer to directed networks, which are common in practical peer-to-peer settings.
  • Because the query points converge to the optimum while raw iterates may not, DAT-SGD gives a last-iterate convergence guarantee, suggesting a practical diagnostic: monitor the consensus distance of the query points rather than the raw iterates to detect when adding machines starts to hurt.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper proposes Decentralized Anytime SGD (DAT-SGD), which applies the Anytime-SGD idea of gradually shifting query points to decentralized gossip-averaged training. For smooth convex objectives with bounded noise and heterogeneity, the central claim (Theorem 4.1) is that with linear weights alpha_t = t and a tuned learning rate, the excess loss satisfies E[f(xbar_T) - f*] = O(sigma D_1 / sqrt(M T) + D_1^{3/2} sqrt(L sigma_tilde) / (rho T) + L D_1^2 / T), where sigma_tilde^2 = 2 sigma^2 + zeta^2. The proof proceeds by deriving recursions for the query-point consensus distance Gamma_t, the iterate consensus distance Xi_t, and the gradient disagreement Psi_t, then bounding the averaged-gradient bias B_T and concluding a parallelism limit of M <= O(rho sqrt(N)). Experiments on synthetic least squares and Fashion MNIST are reported as supporting the improved scaling with the number of machines M.

Significance. If the proof is correct, the result is a meaningful advance: it closes the gap to centralized minibatch SGD on highly connected topologies and improves the parallelism threshold from O(rho^{1/2} N^{1/4}) to O(rho sqrt(N)) across common topologies. The algorithm is simple, the slow-query-point mechanism is well motivated, and the paper gives detailed recursions with explicit constants. However, the central technical proof currently contains a mismatch in the proof of Lemma C.2, and the theorem statement omits a term that appears in the proof. Both issues are local and likely repairable, but they must be fixed before the main claim can be accepted.

major comments (2)
  1. [Appendix C.1, Lemma C.2] The displayed expansion of g_i^t - gbar_t does not support the five bounds applied to it. The expansion is (g_i - E g_i) + (E g_i - gbar) + (E gbar - E gbar - nabla f_i(xbar)) + (nabla f_i(xbar) - nabla f(xbar)) + nabla f(xbar). Algebraically this equals g_i - gbar, but the bounds used are for g_i - E g_i (sigma^2), gbar - E gbar (sigma^2/M), E g_i - nabla f_i(xbar) (L^2 Gamma_t), E gbar - nabla f(xbar) (L^2 Gamma_t), and nabla f_i(xbar) - nabla f(xbar) (zeta^2). None of the five displayed terms except the first coincides with the quantity whose norm is bounded, so the claimed inequality Psi_t <= 5(2 sigma^2 + zeta^2) + 10 L^2 Gamma_t is not derived as written. Since Lemma C.3 uses this bound to solve for Gamma_t and Lemma 4.3 uses Gamma_t to bound B_T, the gap propagates to Theorem 4.1. The proof should be rewritten with a correct decomposition, and the resulting constants should be rechecked against Lemma C.3 and Theorem 4.3.
  2. [Section B, proof of Theorem 4.1] The final display of the proof contains an additional term 4 K D_1^2 / (rho^2 T^2), which is then absorbed into the O-notation as L D_1^2 / (rho^2 T^2). Theorem 4.1 as stated drops this term and claims the bound for all T >= 1. For rho T < 1, this omitted term can be larger than the retained D_1^{3/2} sqrt(L sigma_tilde) / (rho T) term, so the "for all T >= 1" statement is not justified by the proof. The theorem should either include the extra term or restrict the regime (e.g., T >= c/rho) and state the parallelism conclusion accordingly.
minor comments (5)
  1. [Appendix C.1, Lemma C.3 proof] The lines contain typographical errors: "4 eta alpha_t^2 delta_t^2 / rho" and "16 eta / rho" should be "4 eta^2 alpha_t^2 delta_t^2 / rho" and "16 eta^2 / rho"; the subsequent algebra uses eta^2, confirming the typo.
  2. [Appendix A and B] Cross-references are inconsistent throughout the appendices: Lemma A.1/A.2/A.3 are called "Theorem A.1/A.2/A.3" in proofs, Lemma B.1/C.1/C.2/C.4/C.5 and Lemmas D.4-D.6 are called "Theorem" in several places, and Assumption 2.3 is referred to as "Theorem 2.3" in Lemma C.2. Please harmonize the numbering.
  3. [Appendix A, Lemma A.3] The text says the analysis is "included here for completeness," but the proof invokes Lemma 3 of Dahan & Levy (2024) for the bound on sum_t E||w_t - x*||^2 without proving it. Either prove this auxiliary result or state explicitly that it is imported from prior work.
  4. [Section 5] The experiments use constant weights alpha_t = 1 for DAT-SGD, while Theorem 4.1 is stated for linear weights alpha_t = t; the Fashion-MNIST experiments additionally use a heuristic non-convex variant with gamma_t = 0.9. The relationship between the experiments and the proven theory should be clarified.
  5. [Section 5.1] The synthetic experiments set heterogeneity only at the optimum, whereas Assumption 2.3 requires bounded heterogeneity at every x. This mismatch between the experimental verification and the theoretical condition should be noted explicitly.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 4.1 is proven from stated assumptions; the Anytime-SGD lemmas borrowed from prior work (including Dahan & Levy) are either standard or reproduced with proofs, so the self-citations are not load-bearing.

full rationale

The central result (Theorem 4.1) is derived in the paper itself from Assumptions 2.1-2.3. The Anytime-SGD backbone (Lemma A.3) is stated with a full proof in Appendix A; Lemmas A.1 and A.2 are cited to Cutkosky (2019) as well as Dahan & Levy (2024), but they are standard weighted-average and regret identities, not the paper's novel decentralized claim. Lemma 4.3 (the bias bound B_T) is proved in Section B.2 using the paper's own consensus lemmas C.1-C.3, whose proofs are included in Appendix C. The learning rate in Theorem 4.1 is chosen by balancing displayed terms rather than fitted to data, and no fitted parameter is later relabeled as a prediction. The experiments compare algorithms against baselines on fixed problems and do not back-fit the theory. The self-reference to Dahan & Levy (2025) is used only for a non-convex experimental heuristic (fixed gamma_t=0.9), not for the convex theorem, so it is not load-bearing. For these reasons the proof chain is not circular. A separate correctness concern, not a circularity: in Lemma C.2, the five-term expansion of g_i^t - g_bar_t is not the expansion that the subsequent five bounds apply to, e.g., the second bound bounds g_bar_t - E[g_bar_t], not E[g_i^t] - g_bar_t, and the third and fifth bounds correspond to different terms than those displayed. This is an apparent algebraic mismatch in the derivation of Psi_t <= 5(2 sigma^2 + zeta^2) + 10 L^2 Gamma_t, which feeds into the B_T bound in Lemma 4.3 and hence into Theorem 4.1. It is a proof-gap risk rather than circularity because it does not reduce the theorem to its inputs by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The theorem rests on three standard SCO assumptions, the gossip-matrix assumption, and two imported Anytime SGD results (Cutkosky 2019, Dahan & Levy 2024). The bounded-heterogeneity assumption is the most restrictive and is the weakest point. No new entities are postulated; the query point x_t is part of the Anytime SGD framework.

free parameters (2)
  • learning rate η (experimental grid search) = 0.0001 to 0.1 in Section 5.1; 0.001, 0.01, 0.1 in Section 5.2
    Chosen by hand per method and topology in the experiments; not part of the theoretical rate, which sets η from problem constants.
  • momentum parameter β (experiments) = 0.9
    Used for DAT-SGD and D-SGD in Section 5.2; heuristic, not in the analyzed algorithm.
assumptions (5)
  • domain assumption Assumption 2.1: each fi is L-smooth
    Used to bound gradient differences via L∥x−y∥ and to apply ∥∇f(x)∥² ≤ 2L(f(x)−f*).
  • domain assumption Assumption 2.2: bounded noise variance σ² for each machine's gradient estimator
    Used to bound the variance of the averaged gradient and in Lemma C.2's decomposition of Ψ_t.
  • domain assumption Assumption 2.3: bounded heterogeneity ζ² for all x
    Stronger than some prior work; used to bound Ψ_t at arbitrary query points, load-bearing for the bias bound.
  • domain assumption Gossip matrix P is symmetric, doubly stochastic with known spectral gap ρ
    Needed for Property 2.6 (contraction of consensus distance) and for setting the learning rate η ≤ ρ²/K.
  • domain assumption Lemma 3 of Dahan & Levy (2024), bounding Σ E∥w_t − x*∥² for biased Anytime SGD
    Imported without proof, used in Lemma A.3 to derive the main regret bound; the result is prior work by co-author Levy.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Enhancing Parallelism in Decentralized Stochastic Convex Optimization." pith.science (2026). https://pith.science/paper/OL3CHLKA

@misc{pith2026250600961,
  author       = {Pith},
  title        = {Pith review of: Enhancing Parallelism in Decentralized Stochastic Convex Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OL3CHLKA}},
  note         = {Machine review of arXiv:2506.00961}
}
read the original abstract

Decentralized learning has emerged as a powerful approach for handling large datasets across multiple machines in a communication-efficient manner. However, such methods often face scalability limitations, as increasing the number of machines beyond a certain point negatively impacts convergence rates. In this work, we propose Decentralized Anytime SGD, a novel decentralized learning algorithm that significantly extends the critical parallelism threshold, enabling the effective use of more machines without compromising performance. Within the stochastic convex optimization (SCO) framework, we establish a theoretical upper bound on parallelism that surpasses the current state-of-the-art, allowing larger networks to achieve favorable statistical guarantees and closing the gap with centralized learning in highly connected topologies.

Figures

Figures reproduced from arXiv: 2506.00961 by the authors.

Figure 1
Figure 1. Final error on synthetic least squares problem for dif￾ferent numbers of machines and various gradient noise variance (σ 2 ) and heterogeneity (ζ 2 ) levels over ring, torus, and expo￾nential graph topologies. We plot 1 M PM i=1 ∥x i T − x ∗ ∥ 2 and 1 M PM i=1 ∥w i T − x ∗ ∥ 2 for DAT-SGD and D-SGD, respectively. and 1-peer exponential graph (Ying et al., 2021). The exponential graph is a fast-mixing topology for wh… view at source ↗
Figure 3
Figure 3. , similar to [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the ring topology. 24 [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figures from the paper (2 more)
Figure 5
Figure 5. Figure 5: Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the torus topology. 10 0 10 1 10 2 10 3 10 4 10 5 Iterations 10 6 10 5 10 4 10 3 10 2 10 1 10 0 10 1 Error 2=1, 2=1 10 0 10 1 10 2 10 3 10 4 10 5 Iterations 10 6 10 …
Figure 6
Figure 6. Figure 6: Error curves for the least squares problem with varying noise, data heterogeneity, and # of machines in the 1-peer exponential graph topology. 25 [PITH_FULL_IMAGE:figures/full_fig_p025_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 30 canonical work pages

  1. [1]

    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 format.date year duplicate empty "emp...

  2. [2]

    L., Ravikumar, P., and Wainwright, M

    Agarwal, A., Bartlett, P. L., Ravikumar, P., and Wainwright, M. J. Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization. IEEE Transactions on Information Theory, 58 0 (5): 0 3235--3249, 2012

    work page 2012

  3. [3]

    Q., Cevher, V., Levy, K., and Mertikopoulos, P

    Antonakopoulos, K., Vu, D. Q., Cevher, V., Levy, K., and Mertikopoulos, P. Undergrad: A universal black-box optimization method with almost dimension-free convergence rate guarantees. In International Conference on Machine Learning, pp.\ 772--795. PMLR, 2022

    work page 2022

  4. [4]

    Stochastic gradient push for distributed deep learning

    Assran, M., Loizou, N., Ballas, N., and Rabbat, M. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp.\ 344--353. PMLR, 2019

    2019

  5. [5]

    Z., Hakimi, I., Schuster, A., and Levy, K

    Aviv, R. Z., Hakimi, I., Schuster, A., and Levy, K. Y. Asynchronous distributed learning: Adapting to gradient delays without prior knowledge. In International Conference on Machine Learning, pp.\ 436--445. PMLR, 2021

    work page 2021

  6. [6]

    Randomized gossip algorithms

    Boyd, S., Ghosh, A., Prabhakar, B., and Shah, D. Randomized gossip algorithms. IEEE transactions on information theory, 52 0 (6): 0 2508--2530, 2006

    work page 2006

  7. [7]

    Anytime online-to-batch, optimism and acceleration

    Cutkosky, A. Anytime online-to-batch, optimism and acceleration. In International conference on machine learning, pp.\ 1446--1454. PMLR, 2019

    work page 2019

  8. [8]

    and Levy, K

    Dahan, T. and Levy, K. Y. SL owcal SGD : Slow Query Points Improve Local- SGD for Stochastic Convex Optimization . In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https://openreview.net/forum?id=B29BlRe26Z

    work page 2024

Show all 44 references
  1. [9]

    and Levy, K

    Dahan, T. and Levy, K. Y. Do Stochastic, Feel Noiseless: Stable Stochastic Optimization via a Double Momentum Mechanism . In The Thirteenth International Conference on Learning Representations, 2025. URL https://openreview.net/forum?id=zCZnEXF3bN

    2025

  2. [10]

    Optimal distributed online prediction using mini-batches

    Dekel, O., Gilad-Bachrach, R., Shamir, O., and Xiao, L. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13 0 (1), 2012

    2012

  3. [11]

    and Scutari, G

    Di Lorenzo, P. and Scutari, G. Next: In-network nonconvex optimization. IEEE Transactions on Signal and Information Processing over Networks, 2 0 (2): 0 120--136, 2016

    2016

  4. [12]

    L., and Vladu, A

    Ene, A., Nguyen, H. L., and Vladu, A. Adaptive gradient methods for constrained convex optimization and variational inequalities. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp.\ 7314--7321, 2021

    2021

  5. [13]

    P., and Jaggi, M

    He, L., Karimireddy, S. P., and Jaggi, M. Byzantine-robust decentralized learning via clippedgossip. arXiv preprint arXiv:2202.01545, 2022

    2022 arXiv

  6. [14]

    H., Qi, H., and Brown, M

    Hsu, T.-M. H., Qi, H., and Brown, M. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.06335, 2019

    1909 arXiv

  7. [15]

    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. Advances and open problems in federated learning . Foundations and Trends in Machine Learning , 14 0 (1--2): 0 1--210, 2021

    2021

  8. [16]

    Y., Bach, F., and Cevher, V

    Kavis, A., Levy, K. Y., Bach, F., and Cevher, V. Unixgrad: A universal, adaptive algorithm with optimal guarantees for constrained optimization. Advances in neural information processing systems, 32, 2019

    2019

  9. [17]

    Gossip-based computation of aggregate information

    Kempe, D., Dobra, A., and Gehrke, J. Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings., pp.\ 482--491. IEEE, 2003

    2003

  10. [18]

    Decentralized stochastic optimization and gossip algorithms with compressed communication

    Koloskova, A., Stich, S., and Jaggi, M. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp.\ 3478--3487. PMLR, 2019

    2019

  11. [19]

    A unified theory of decentralized sgd with changing topology and local updates

    Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp.\ 5381--5393. PMLR, 2020

    2020

  12. [20]

    Koloskova, A., Lin, T., and Stich, S. U. An improved analysis of gradient tracking for decentralized machine learning . Advances in Neural Information Processing Systems, 34: 0 11422--11435, 2021

    2021

  13. [21]

    Consensus control for decentralized deep learning

    Kong, L., Lin, T., Koloskova, A., Jaggi, M., and Stich, S. Consensus control for decentralized deep learning. In International Conference on Machine Learning, pp.\ 5686--5696. PMLR, 2021

    2021

  14. [22]

    Gradient-based learning applied to document recognition

    LeCun, Y., Bottou, L., Bengio, Y., and Haffner, P. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86 0 (11): 0 2278--2324, 1998

    1998

  15. [23]

    G., Smola, A

    Li, M., Andersen, D. G., Smola, A. J., and Yu, K. Communication efficient distributed machine learning with the parameter server. Advances in Neural Information Processing Systems, 27, 2014

    2014

  16. [24]

    Learning to collaborate in decentralized learning of personalized models

    Li, S., Zhou, T., Tian, X., and Tao, D. Learning to collaborate in decentralized learning of personalized models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp.\ 9766--9775, 2022

    2022

  17. [25]

    Communication-efficient local decentralized sgd methods

    Li, X., Yang, W., Wang, S., and Zhang, Z. Communication-efficient local decentralized sgd methods. arXiv preprint arXiv:1910.09126, 2019

    1910 arXiv

  18. [26]

    Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent

    Lian, X., Zhang, C., Zhang, H., Hsieh, C.-J., Zhang, W., and Liu, J. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017

    2017

  19. [27]

    and De Sa, C

    Lu, Y. and De Sa, C. Optimal complexity in decentralized training. In International conference on machine learning, pp.\ 7111--7123. PMLR, 2021

    2021

  20. [28]

    McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication-efficient learning of deep networks from decentralized data. In Artificial intelligence and statistics, pp.\ 1273--1282. PMLR, 2017

    2017

  21. [29]

    and Ozdaglar, A

    Nedic, A. and Ozdaglar, A. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54 0 (1): 0 48--61, 2009

    2009

  22. [30]

    Achieving geometric convergence for distributed optimization over time-varying graphs

    Nedic, A., Olshevsky, A., and Shi, W. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27 0 (4): 0 2597--2633, 2017

    2017

  23. [31]

    Robust stochastic approximation approach to stochastic programming

    Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19 0 (4): 0 1574--1609, 2009

    2009

  24. [32]

    Nemirovski, A. S. and Yudin, D. B. Problem complexity and method efficiency in optimization. 1983

    1983

  25. [33]

    and Nedi \'c , A

    Pu, S. and Nedi \'c , A. Distributed stochastic gradient tracking methods. Mathematical Programming, 187 0 (1): 0 409--457, 2021

    2021

  26. [34]

    Pu, S., Olshevsky, A., and Paschalidis, I. C. A sharp estimate on the transient time of distributed stochastic gradient descent . IEEE Transactions on Automatic Control, 67 0 (11): 0 5900--5915, 2021

    2021

  27. [35]

    On the linear convergence of the admm in decentralized consensus optimization

    Shi, W., Ling, Q., Yuan, K., Wu, G., and Yin, W. On the linear convergence of the admm in decentralized consensus optimization. IEEE Transactions on Signal Processing, 62 0 (7): 0 1750--1761, 2014

    2014

  28. [36]

    Beyond exponential graph: Communication-efficient topologies for decentralized learning via finite-time convergence

    Takezawa, Y., Sato, R., Bao, H., Niwa, K., and Yamada, M. Beyond exponential graph: Communication-efficient topologies for decentralized learning via finite-time convergence . Advances in Neural Information Processing Systems, 36: 0 76692--76717, 2023

    2023

  29. [37]

    Communication compression for decentralized training

    Tang, H., Gan, S., Zhang, C., Zhang, T., and Liu, J. Communication compression for decentralized training. Advances in Neural Information Processing Systems, 31, 2018 a

    2018

  30. [38]

    D^2 : Decentralized training over decentralized data

    Tang, H., Lian, X., Yan, M., Zhang, C., and Liu, J. D^2 : Decentralized training over decentralized data . In International Conference on Machine Learning, pp.\ 4848--4856. PMLR, 2018 b

    2018

  31. [39]

    Tsitsiklis, J. N. Problems in decentralized decision making and computation. PhD thesis, Massachusetts Institute of Technology, 1984

    1984

  32. [40]

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

    2020

  33. [41]

    Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms

    Xiao, H., Rasul, K., and Vollgraf, R. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017

    2017 arXiv

  34. [42]

    and Boyd, S

    Xiao, L. and Boyd, S. Fast linear iterations for distributed averaging. Systems & Control Letters, 53 0 (1): 0 65--78, 2004

    2004

  35. [43]

    Exponential graph is provably efficient for decentralized deep training

    Ying, B., Yuan, K., Chen, Y., Hu, H., Pan, P., and Yin, W. Exponential graph is provably efficient for decentralized deep training. Advances in Neural Information Processing Systems, 34: 0 13975--13987, 2021

    2021

  36. [44]

    Decentlam: Decentralized momentum sgd for large-batch deep training

    Yuan, K., Chen, Y., Huang, X., Zhang, Y., Pan, P., Xu, Y., and Yin, W. Decentlam: Decentralized momentum sgd for large-batch deep training. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp.\ 3029--3039, 2021

    2021

Pith tools

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