Pith. sign in

REVIEW 6 minor 31 references

Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework

T0 review · 0 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper claims that fully asynchronous decentralized SGD converges for non-convex objectives at rate $O(1/K^{1/3})$ with step sizes independent of the computation-delay bound, achieved through a block-coordinate descent reformulation.

desk verdict Solid theory paper with a real first: computation-delay-independent step sizes for nonconvex async decentralized SGD, but the analyzed double-step-size variant is not what the experiments run. read the letter →

arxiv 2505.10322 v1 pith:2D3AOXVY submitted 2025-05-15 cs.LG math.OC

Yijie Zhou , Shi Pu This is my paper · ORCID
classification cs.LGmath.OC MSC 90C2690C1590C06
keywords asynchronousdecentralizedSGDblockcoordinatedescentnon-convexoptimizationcomputationdelaycommunicationgossipaveragingdelay-independentstepsizesstochasticgradient
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 claims that a fully asynchronous decentralized SGD, in which a node averages its own model with neighbors' models only after finishing a gradient step, converges for non-convex objectives at rate $O(1/K^{1/3})$ with step sizes that ignore the computation-delay bound while scaling with the communication-delay bound $D$ and total steps $K$. The guarantee needs no bounded data heterogeneity, only each local loss bounded below. The argument works by viewing ADSGD as a special case of asynchronous stochastic block coordinate descent on a modified objective, then introducing a double-step-size trick to control noise accumulation. If correct, this is the first non-convex convergence guarantee for asynchronous decentralized SGD using a computation-delay-independent step size, and it comes with a simple closed-form schedule.

What carries the argument

The load-bearing object is the equivalence between ADSGD and asynchronous stochastic block coordinate descent. Defining $F(x) = \sum_i f_i(x_i)$ and the augmented objective $L_\alpha(x) = F(x) + x^\top(I-W)x/(2\alpha)$, the ADSGD update (6) is exactly one block update of ASBCD with step size $\alpha$ on $L_\alpha$, because each node mixes its own block with the stale neighbor blocks in its buffer. Because $L_\alpha$ is itself step-size-dependent, the paper introduces a double-step-size scheme (7): taking a step of size $\beta$ on $L_\alpha$ is equivalent to mixing with $\tilde{W} = (1-\beta/\alpha)I + (\beta/\alpha)W$ followed by a step-$\beta$ local gradient update. As long as $\beta \le \alpha$, $\tilde{W}$ inherits symmetry and stochasticity from $W$, so the ASBCD convergence machinery transfers to ADSGD, with the rate determined by the consensus-error term of size $O(\alpha)$.

What would settle it

Take a 9-agent grid network with uniform gossip weights ($W_{ii} = 0.2$ at the center node), set $D = 1$ and $B = 1$, and run the Corollary 3.12 schedule out to $K = 20{,}000$ iterations. Then $\beta/\alpha = K^{1/3}/(8(D+1/2)) \approx 2.26$, and the constructed matrix has center-node diagonal entry $1 - \beta/\alpha + (\beta/\alpha)(0.2) \approx -0.81$, a negative value that violates stochasticity. Simply computing $\tilde{W}$ for these parameters and checking nonnegativity and row sums settles whether the theorem analyzes a legal instance of Algorithm 2.

Watch

Extended reading notes

Core claim

On its own terms, the paper establishes the convergence of double-step-size ADSGD: under bounded computation delay $B$ and communication delay $D$, $L$-smooth local losses, unbiased gradient estimators with bounded variance, and a symmetric stochastic gossip matrix $W$, the update (7) with $\alpha = 2/(L_F K^{1/3})$ and $\beta = 1/(4 L_F (D+1/2) K^{2/3})$ satisfies $\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}\|\nabla f(\bar{x}^k)\|^2 \le O(1/K^{1/3})$, with both step sizes independent of $B$. A companion theorem states that ASBCD converges at rate $O(1/\sqrt{K})$ under a suitably chosen step size, matching standard non-convex SGD and claimed as the first such result for asynchronous coordinate descent with stochastic gradients. The analysis also removes the bounded-data-heterogeneity assumption common in prior DSGD analyses. Empirically, the paper reports that ADSGD reaches target test accuracy faster than asynchronous and synchronous baselines under several delay and straggler scenarios.

Load-bearing premise

The load-bearing premise is the assertion in Section 3.3 that the effective mixing matrix $\tilde{W} = (1-\beta/\alpha)I + (\beta/\alpha)W$ satisfies Assumption 3.7, namely symmetry and stochasticity, which holds only while the two step sizes obey $\beta \le \alpha$; the paper's own Corollary 3.12 schedule has $\beta/\alpha = K^{1/3}/(8(D+1/2)) > 1$ for large $K$, so in that regime the recursion being analyzed is not a well-defined instance of the algorithm the assumptions describe.

Editorial extensions

If this is right

  • If the bound is right, non-convex asynchronous decentralized SGD no longer needs step sizes that shrink with the computation-delay bound $B$; the schedule $\beta = 1/(4L_F(D+1/2)K^{2/3})$ is explicit and implementable.
  • The convergence guarantee covers arbitrarily skewed data partitions, since only each local loss must be bounded below rather than bounded data heterogeneity being assumed.
  • Per-iteration communication drops to one model broadcast per node update and memory to $O(|N_i|)$ plus the local iterate, about half to a third of the budget of gradient-tracking alternatives.
  • ASBCD achieves the $O(1/\sqrt{K})$ non-convex rate of standard SGD, bringing asynchronous stochastic coordinate descent in line with the synchronous baseline for the first time.
  • In the reported experiments, ADSGD reaches target test accuracy 15–70% faster than asynchronous baselines and 30–85% faster than synchronous ones under straggler settings, with larger advantages under communication delays.

Reading between the lines

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

  • A direct repair of the parameter-schedule gap would be to impose $\beta \le \alpha$ explicitly (equivalently $K^{1/3} \le 8(D+1/2)$) or to extend the proof to signed, non-stochastic mixing weights; the same Lyapunov argument may survive signed weights because only symmetry and spectral properties enter the consensus term.
  • The gap between the $O(1/K^{1/3})$ rate and SGD's $O(1/\sqrt{K})$ is entirely the consensus-error term $O(\alpha)$, so a testable extension is whether a gradient-tracking or momentum variant of the same ASBCD equivalence closes that gap while keeping delay-free step sizes.
  • The equivalence suggests a recipe for other decentralized methods: any update that is a gossip mix plus a local stochastic step can be analyzed as block coordinate descent on an augmented objective, potentially transferring delay-robustness results between algorithms.
  • An easy empirical isolation: run the method with the ratio fixed at $\beta/\alpha = 1$ so that $\tilde{W}$ is always a true averaging matrix, and compare with the unconstrained Corollary 3.12 schedule to see whether the theoretical invalidity at large $K$ shows up in practice.
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

0 major / 6 minor

Summary. This paper studies asynchronous decentralized SGD under bounded computation and communication delays. It first analyzes Asynchronous Stochastic Block Coordinate Descent (ASBCD) with stochastic gradients in non-convex smooth problems, obtaining an O(1/sqrt(K)) rate to a neighborhood (Lemma 3.8 and Corollary C.4). It then maps ADSGD to ASBCD on the surrogate L_alpha(x) = F(x) + x^T(I-W)x/(2 alpha), introduces a double-step-size update (7), and proves an O(1/K^{1/3}) bound on the average squared gradient norm at the average iterate (Theorem 3.9 and Corollary 3.12), with step sizes independent of the computation-delay bound B and without a bounded-data-heterogeneity assumption. The paper also proposes a memory-efficient implementation and reports experiments on MNIST and CIFAR-10 comparing ADSGD with ADPSGD, RFAST, DSGD, and parallel SGD.

Significance. If the analysis holds, the paper delivers a genuinely new guarantee: for non-convex smooth decentralized problems with partial asynchrony, the main corollary's step sizes depend on the communication-delay bound D and the horizon K but not on the computation-delay bound B. The proofs are self-contained, follow a standard Lyapunov argument, and prescribe step sizes in closed form rather than fitting constants to data; there is no circularity in the derivation. The experimental study is broad, covering heterogeneity, scalability, and several delay scenarios. I checked the stress-test concern about the tilde-W ratio: Corollary 3.12 gives beta/alpha = 1/(8(D+1/2)K^{1/3}), so tilde-W is a convex combination of I and W for all K and D, and the reader's inverted-ratio concern does not land. The central convergence claim survives scrutiny; the remaining issues are local presentation and verification details.

minor comments (6)
  1. [Section 3.3, Eq. (7)] The assertion that tilde-W 'satisfies Assumption 3.7' is guaranteed only when beta <= alpha, which is not implied by the theorem's condition beta < 1/((D+1/2)L_L). Corollary 3.12 is safe because its schedule gives beta/alpha = 1/(8(D+1/2)K^{1/3}) <= 1, but the theorem statement should either impose beta <= alpha or explicitly note that the proof uses only the original W and does not require tilde-W to be stochastic.
  2. [Appendix C.4] In the display bounding L_L beta, the second term should be 1/(4(D+1/2)K^{1/3}), not 1/(8(D+1/2)K^{1/3}), because (2/alpha)beta = 1/(4(D+1/2)K^{1/3}). The final inequality still holds, but the displayed intermediate inequality is not correct as written.
  3. [Sections 2.2 and 3.3] Algorithm 2 as used in the experiments (with W and with alpha = beta = 0.01) is a special case of the double-step-size family, but it is not the decaying (alpha, beta) schedule analyzed in Corollary 3.12; the paper should state explicitly that the experiments evaluate a fixed-step-size instance of the same family and do not directly test the corollary's schedule.
  4. [Appendix C.4, Corollary C.4] The constant C2 contains 3B^2/D, so the statement should explicitly record that Assumption 3.3 assumes D > 0 or provide a separate handling for the D = 0 case.
  5. [Section 1.1] The citation '[Wu et al.]' appears in the text but has no corresponding entry in the reference list; the bibliography should be completed.
  6. [Eq. (24)] The explanation that the third equality follows from doubly stochasticity of W is terse; since Assumption 3.7 states symmetry and row-stochasticity, it would be clearer to say that column stochasticity follows from symmetry and row stochasticity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the convergence bounds are derived self-contained from stated assumptions, and the double-step-size matrix is a valid stochastic matrix under the corollary's schedule.

full rationale

The paper's central chain is ADSGD viewed as ASBCD applied to L_alpha, with the ASBCD bound (Lemma 3.8) proved in Appendix C.1 via a Lyapunov argument following the external reference [19], not assumed from prior work. The ADSGD-to-ASBCD correspondence is an explicit algebraic rewriting of update (6) into (7), building on the standard DGD-BCD equivalence of [26] and extending it to the asynchronous stochastic setting with a self-contained proof. Lemma C.1, attributed in part to [28], is fully proven in the appendix and is an elementary staleness bound, so the citation is not load-bearing. The reader's concern about tilde W = (1 - beta/alpha)I + (beta/alpha)W is based on an inverted ratio: Corollary 3.12 sets alpha = 2/(L_F K^{1/3}) and beta = 1/(4 L_F (D+1/2) K^{2/3}), so beta/alpha = 1/(8(D+1/2)K^{1/3}) <= 1/4 for K >= 1 and D >= 0; hence tilde W is a convex combination of I and W and inherits symmetry, stochasticity, and nonnegativity. No parameter is fitted to data and then renamed a prediction: the experiments use a fixed step size of 0.01 independent of the theoretical schedule, and the bounds are closed-form functions of problem parameters. The paper therefore contains no step, self-citation chain, or definitional identification that reduces a claimed result to its own inputs.

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

The auxiliary objective L_alpha(x) = F(x) + x^T(I-W)x/(2 alpha) is a mathematical construction introduced for the analysis, not a new physical or algorithmic entity requiring independent falsifiable evidence. The algorithm itself is a variant of existing DSGD with a different step-size schedule, so no new free parameters are fitted to data. The paper's central claim rests on standard smoothness and stochastic-gradient assumptions plus the bounded-delay model.

assumptions (5)
  • domain assumption Assumption 3.3: each agent updates at least once every B iterations, and all read staleness is bounded by D.
    This partial-asynchrony model is the core modeling premise; the proof's delay telescope and step-size conditions depend on it.
  • standard math Assumptions 3.1 and 3.5: objective functions are L-smooth and lower bounded.
    Standard smoothness assumption used throughout the descent lemmas.
  • standard math Assumptions 3.2 and 3.6: gradient estimators are unbiased with variance bounded by sigma squared.
    Standard stochastic approximation assumption used in the variance and descent bounds.
  • domain assumption Assumption 3.7: the mixing matrix W is symmetric doubly stochastic with connected support.
    Used to ensure L_alpha is lower bounded and to bound consensus error via lambda_min(I-W) = 1 - lambda_2(W) > 0.
  • standard math W.L.O.G. identical initialization in the proof of Theorem 3.9.
    Used to set the initial Lyapunov value xi^0_Lalpha = sum_i f_i(x0). Non-identical starts would add a consensus term (1/(2 alpha)) x0^T(I-W)x0, which is nonnegative and would enter the final bound as an extra vanishing term.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework." pith.science (2026). https://pith.science/paper/2D3AOXVY

@misc{pith2026250510322,
  author       = {Pith},
  title        = {Pith review of: Asynchronous Decentralized SGD under Non-Convexity: A Block-Coordinate Descent Framework},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2D3AOXVY}},
  note         = {Machine review of arXiv:2505.10322}
}
read the original abstract

Decentralized optimization has become vital for leveraging distributed data without central control, enhancing scalability and privacy. However, practical deployments face fundamental challenges due to heterogeneous computation speeds and unpredictable communication delays. This paper introduces a refined model of Asynchronous Decentralized Stochastic Gradient Descent (ADSGD) under practical assumptions of bounded computation and communication times. To understand the convergence of ADSGD, we first analyze Asynchronous Stochastic Block Coordinate Descent (ASBCD) as a tool, and then show that ADSGD converges under computation-delay-independent step sizes. The convergence result is established without assuming bounded data heterogeneity. Empirical experiments reveal that ADSGD outperforms existing methods in wall-clock convergence time across various scenarios. With its simplicity, efficiency in memory and communication, and resilience to communication and computation delays, ADSGD is well-suited for real-world decentralized learning tasks.

Figures

Figures reproduced from arXiv: 2505.10322 by the authors.

Figure 1
Figure 1. Schematics of s k ij for ASBCD (left) and ADSGD (right), with the computation and communication of primary focus highlighted in a darker shade. Algorithm 1 ASBCD 1: Initialization: All blocks agree on α > 0. 2: Each block chooses xi , creates a local buffer Bi , shares xi , and calculates g f i (xi). 3: All Blocks Do In Parallel: 4: while The termination criterion is met do 5: repeat 6: Keep receiving xj from other … view at source ↗
Figure 2
Figure 2. Loss plot of Logistic Regression on MNIST. Case 5 is excluded for clarity. See the appendix [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Loss plot of VGG on CIFAR10. Case 5 is excluded for clarity. See the appendix for details. [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figures from the paper (13 more)
Figure 4
Figure 4. Figure 4: Speedup of ADSGD w.r.t. number of agents under a ring topology. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Logistic Regression - No Straggler - Training Loss - [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Logistic Regression - One Straggler - Training Loss - [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Logistic Regression - No Straggler - Test Accuracy - [PITH_FULL_IMAGE:figures/full_fig_p015_7.png]
Figure 8
Figure 8. Figure 8: Logistic Regression - One Straggler - Test Accuracy - [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Relative time (lower is better) to achieve 89% test accuracy for Non-convex Logistic Regression on MNIST, normalized w.r.t. the runtime of ADSGD Case 1). N/A indicates the algorithm did not reach 89% accuracy. ζ = 1 (a) Case 1&2 - ζ = 0 (b) Case 3&4 - ζ = 0 (c) Case 1&…
Figure 10
Figure 10. Figure 10: Logistic Regression under smaller data heterogeneity levels [PITH_FULL_IMAGE:figures/full_fig_p015_10.png]
Figure 11
Figure 11. Figure 11: and 12 present the training loss w.r.t. runtime for different algorithms. With a combined strag￾gler (Fig. 12c), ADSGD maintains its lead by a significant amount, consistent with its performance in logistic regression [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: VGG - One Straggler - Training Loss - ζ = 1 0.0 0.2 0.4 0.6 0.8 1.0 Time 1e6 20 30 40 50 60 70 80 90 Acc ADSGD-Case 1 SGD-Case 1 DSGD-Case 1 ADPSGD-Case 1 RFAST-Case 1 (a) Base 0.0 0.2 0.4 0.6 0.8 1.0 Time 1e6 30 40 50 60 70 80 90 Acc ADSGD-Case 2 SGD-Case 2 DSGD-Case…
Figure 13
Figure 13. Figure 13: and 14 present the test accuracy w.r.t. runtime for different algorithms. When there is no straggler, parallel SGD reaches a higher test accuracy given the same amount of time, followed by ADSGD. Note that the loss function of VGG model is highly non-convex, resulting…
Figure 14
Figure 14. Figure 14: VGG - One Straggler - Test Accuracy - ζ = 1 Case 1 Case 2 Case 3 Case 4 Case 5 0 2 4 6 8 10 12 14 Relative Time ADSGD ADPSGD RFAST DSGD SGD N/A [PITH_FULL_IMAGE:figures/full_fig_p017_14.png]
Figure 15
Figure 15. Figure 15: Relative time (lower is better) to achieve 85% test accuracy for VGG11 on CIFAR-10, normalized w.r.t. the runtime of ADSGD Case 1). N/A indicates the algorithm did not reach 85% accuracy. ζ = 1 C Convergence Proof C.1 Proof of Lemma 3.8 Following a similar way as in […
Figure 16
Figure 16. Figure 16: VGG training under smaller data heterogeneity levels [PITH_FULL_IMAGE:figures/full_fig_p017_16.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

31 extracted references · 25 canonical work pages

  1. [1]

    S., and Huang, F

    Bornstein, M., Rabbani, T., Wang, E., Bedi, A. S., and Huang, F. (2022). Swift: Rapid decentral- ized federated learning via wait-free model communication

    work page 2022

  2. [2]

    Cannelli, L., Facchinei, F., Scutari, G., and Kungurtsev, V . (2020). Asynchronous optimization over graphs: Linear convergence under error bound conditions. IEEE Transactions on Automatic Control, 66(10):4604–4619

    work page 2020

  3. [3]

    and Wang, L

    Kazemi, E. and Wang, L. (2019). Asynchronous delay-aware accelerated proximal coordinate descent for nonconvex nonsmooth problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1528–1535

    work page 2019

  4. [4]

    Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. (2020). A unified theory of decentralized sgd with changing topology and local updates. In International conference on machine learning, pages 5381–5393. PMLR

    work page 2020

  5. [5]

    U., and Jaggi, M

    Koloskova, A., Stich, S. U., and Jaggi, M. (2022). Sharper convergence guarantees for asyn- chronous sgd for distributed and federated learning

    work page 2022

  6. [6]

    Krizhevsky, A., Hinton, G., et al. (2009). Learning multiple layers of features from tiny images

    2009

  7. [7]

    Kungurtsev, V ., Morafah, M., Javidi, T., and Scutari, G. (2023). Decentralized asynchronous non-convex stochastic optimization on directed graphs. IEEE Transactions on Control of Network Systems

    work page 2023

  8. [8]

    Leblond, R., Pedregosa, F., and Lacoste-Julien, S. (2017). Asaga: Asynchronous parallel saga. In Artificial Intelligence and Statistics, pages 46–54. PMLR

    work page 2017

Show all 31 references
  1. [9]

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

    1998

  2. [10]

    Lian, X., Zhang, W., Zhang, C., and Liu, J. (2018). Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pages 3043–3052. PMLR

    2018

  3. [11]

    and Wright, S

    Liu, J. and Wright, S. J. (2015). Asynchronous stochastic coordinate descent: Parallelism and convergence properties. SIAM Journal on Optimization, 25(1):351–376

    2015

  4. [12]

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

    2017

  5. [13]

    B., Harada, N., Sawada, H., and Fujino, A

    Niwa, K., Zhang, G., Kleijn, W. B., Harada, N., Sawada, H., and Fujino, A. (2021). Asyn- chronous decentralized optimization with implicit stochastic variance reduction. In International Conference on Machine Learning, pages 8195–8204. PMLR

    2021

  6. [14]

    Peng, Z., Xu, Y ., Yan, M., and Yin, W. (2016). Arock: an algorithmic framework for asyn- chronous parallel coordinate updates. SIAM Journal on Scientific Computing, 38(5):A2851–A2879

    2016

  7. [15]

    Pu, S., Shi, W., Xu, J., and Nedi ´c, A. (2020). Push–pull gradient methods for distributed optimization in networks. IEEE Transactions on Automatic Control, 66(1):1–16

    2020

  8. [16]

    Samarakoon, S., Bennis, M., Saad, W., and Debbah, M. (2019). Distributed federated learning for ultra-reliable low-latency vehicular communications. IEEE Transactions on Communications, 68(2):1146–1159. 10

    2019

  9. [17]

    and Zisserman, A

    Simonyan, K. and Zisserman, A. (2014). Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556

    2014 arXiv

  10. [18]

    Spiridonoff, A., Olshevsky, A., and Paschalidis, I. C. (2020). Robust asynchronous stochastic gradient-push: Asymptotically optimal and network-independent performance for strongly convex functions. Journal of machine learning research, 21(58):1–47

    2020

  11. [19]

    Sun, T., Hannah, R., and Yin, W. (2017). Asynchronous coordinate descent under more realistic assumptions. Advances in Neural Information Processing Systems, 30

    2017

  12. [20]

    Tang, Z., Wang, Y ., He, X., Zhang, L., Pan, X., Wang, Q., Zeng, R., Zhao, K., Shi, S., He, B., et al. (2023). Fusionai: Decentralized training and deploying llms with massive consumer-level gpus. arXiv preprint arXiv:2309.01172

    2023 arXiv

  13. [21]

    Tian, Y ., Sun, Y ., and Scutari, G. (2020). Achieving linear convergence in distributed asyn- chronous multiagent optimization. IEEE Transactions on Automatic Control, 65(12):5264–5279

    2020

  14. [22]

    Tseng, P. (1991). On the rate of convergence of a partially asynchronous gradient projection algorithm. SIAM Journal on Optimization, 1(4):603–619

    1991

  15. [23]

    and Hale, M

    Ubl, M. and Hale, M. T. (2022). Faster asynchronous nonconvex block coordinate descent with locally chosen stepsizes. In 2022 IEEE 61st Conference on Decision and Control (CDC), pages 4559–4564. IEEE. [Wu et al.] Wu, X., Liu, C., Magnusson, S., and Johansson, M. Delay-agnostic...

    2022

  16. [25]

    Yuan, K., Ling, Q., and Yin, W. (2016). On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 26(3):1835–1854

    2016

  17. [26]

    and Yin, W

    Zeng, J. and Yin, W. (2018). On nonconvex decentralized gradient descent. IEEE Transactions on signal processing, 66(11):2834–2848

    2018

  18. [27]

    and You, K

    Zhang, J. and You, K. (2019). Fully asynchronous distributed optimization with linear conver- gence in directed networks. arXiv preprint arXiv:1901.08215

    2019 arXiv

  19. [28]

    Zhou, Y ., Liang, Y ., Yu, Y ., Dai, W., and Xing, E. P. (2018). Distributed proximal gradient algorithm for partially asynchronous computer clusters. Journal of Machine Learning Research, 19(19):1–32

    2018

  20. [29]

    Zhu, Z., Tian, Y ., Huang, Y ., Xu, J., and He, S. (2023). Robust fully-asynchronous methods for distributed training over general architecture. arXiv preprint arXiv:2307.11617. 11 Appendix A Algorithm Comparison Table 2 represents all decentralized stochastic gradient algorit...

    2023 arXiv

  21. [30]

    SC ✓(2) 3|Ni| + 3 |Ni|

  22. [31]

    However, in [18], they use a diminishing step size rule to reach an asymptotic result, whereas we use a fixed step size

    NC 4|Ni| + 5 2 |Ni| Ours NC ✓ |Ni| + 2 |Ni| A.1 On Step Sizes Only [18] and this work adopt a computation-delay-independent step size. However, in [18], they use a diminishing step size rule to reach an asymptotic result, whereas we use a fixed step size. As mentioned in Secti...

  23. [32]

    (11) 18 We define the filtrationFk as a sequence of σ-algebra that captures all the randomness up to and including thek-th iteration. Take conditional expectation of (11), by Assumption 3.2, E[f(xk+1)|Fk]− f(xk) (9) ≤⟨∇ f(xk)−∇ f(ˆxk), E[∆k|Fk]⟩ + L 2 E[∥∆k∥2|Fk]− 1 α∥E[∆k|Fk]...

Pith tools

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