Pith. sign in

REVIEW 2 major objections 5 minor 60 references

This paper claims that scheduling sparse-to-dense communication phases, guided by a convergence bound that depends only on time-averaged mixing strength, minimizes the maximum per-node energy to reach a target accuracy in decentralized fede

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-03 13:31 UTC pith:MAJDEKHJ

load-bearing objection The convergence theorem is a real generalization, but the energy objective rests on a false Hoeffding bound, so the paper's central optimization claim does not hold as written. the 2 major comments →

arxiv 2512.24069 v2 pith:MAJDEKHJ submitted 2025-12-30 cs.LG cs.DCmath.OC

Time-varying Mixing Matrix Design for Energy-efficient Decentralized Federated Learning

Xusheng Zhang , Tuan Nguyen , Ting He This is my paper
classification cs.LG cs.DCmath.OC
keywords decentralized federated learningmixing matrix designtime-varying topologyenergy efficiencybroadcast communicationD-PSGD convergencemulti-phase optimizationstochastic gradient descent
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper wants to show that, in decentralized federated learning over wireless networks, the right way to save energy is to deliberately vary how many nodes communicate as training progresses—starting sparse and ending dense—and that this can be done with a provable convergence guarantee. It derives a convergence theorem for D-PSGD that holds for arbitrarily time-varying random mixing matrices, where the iteration count depends only on time-averaged consensus parameters. On that basis it builds a multi-phase design that picks per-phase communication budgets and durations to minimize the maximum per-node energy until a target accuracy is reached. If correct, it means network designers can trade sparse cheap phases against dense fast phases and balance energy across heterogeneous devices, rather than optimizing a single fixed mixing matrix.

Core claim

The paper's central claim is that a time-varying sequence of random mixing matrices can be engineered to minimize the worst-node energy bill in D-PSGD. The engine is a convergence theorem stating that the required number of iterations is controlled by two ergodic averages of the consensus contraction, the initial consensus error, and the weakest mixing strength, not by every per-iteration spectral gap. Because the bound relies on averages, a phase with almost no communication does not ruin the rate as long as later phases mix densely enough. The paper then casts topology design as per-phase budget allocation and shows a broadcast-compliant randomized construction whose spectral gap can be co

What carries the argument

The mixing matrix W(t)—the doubly stochastic matrix of aggregation weights that D-PSGD applies at each step—controls both consensus speed and communication cost. The paper measures its quality by the divergence ρ(W)=∥E[W⊤W]−J∥, with the ideal all-average matrix J, and defines p(t)=1−ρ(W(t)). The convergence theorem is carried by the cumulative divergence parameters π_j (summing the contraction products after iteration j) and their time averages Π1(T) and Π2(T); the proof unrolls the consensus-distance recursion and shows only these averages enter the dominant O(ǫ^{-3/2}) term. Around this, the optimization framework uses a per-phase budget D_s with an upper bound q(T,D) on expected maximum p

Load-bearing premise

The energy objective's upper bound q(T,D) assumes each per-iteration node energy lies between 0 and D, but under the paper's broadcast model an activated node can spend c_a_i+c_b_i>D, so the objective may understate the true expected maximum per-node energy.

What would settle it

Run a single phase with c_a=0, c_b=100, budget D=1, so each node activates with probability 0.01, for T=1000 iterations and m=2 nodes, and measure the expected maximum per-node energy over many trials. If it exceeds q(T,D)=D·(T+m·sqrt(T·π/8))≈1039, the bound in Lemma IV.1 fails; the actual mean of each node's total is 1000 with standard deviation roughly 315, so the expected maximum is likely near 1340.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • A designer can provably run low-communication phases early—when models are still far from consensus and dense mixing is wasteful—and switch to dense phases later, because the bound depends on Π1 and Π2 rather than per-iteration worst-case spectral gaps.
  • Occasional iterations with p(t) near zero, including possibly no node transmitting, enter only through the lower-order pmin term, so aggressive energy-saving phases do not destroy the asymptotic rate.
  • The per-node energy budget becomes a tunable design variable decoupled from topology; the broadcast algorithm maps a budget D to a random mixing matrix with expected per-node cost at most D, and on a clique its divergence is asymptotically 1−(D−c_a)/c_b for homogeneous costs.
  • The same trilevel framework covers unicast communications by optimizing a distribution over random subgraphs with a per-node budget constraint instead of a total-cost constraint.
  • If the local objectives are convex, the theorem needs weaker noise assumptions, extending the same phase-schedule idea to convex decentralized problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Because the theorem allows arbitrarily time-varying mixing, an online controller that adapts phases based on measured progress could likely reuse the same averages-based bound, though the paper itself analyzes offline schedules only.
  • The sparse-to-dense ordering is not forced by the theorem—the averages are time-symmetric—so the improvement seen in experiments is an empirical property of the loss landscape; a testable prediction is that dense-to-sparse ordering should fare worse under the same energy budget.
  • Under the broadcast cost model, activating a node costs one transmission regardless of neighborhood size; in interference-limited settings where that assumption breaks, the paper's unicast variant with highly expanding random subgraphs provides the more conservative design.
  • The budget notion could be made node-specific (D_i instead of D) to handle battery-heterogeneous networks; the activation-probability rule min((D_i−c_a_i)/c_b_i,1) suggests graceful degradation as a node's budget shrinks.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper addresses the design of time-varying mixing matrices for decentralized federated learning (DFL) with the objective of minimizing the expected maximum per-node energy consumption until a target convergence level is reached. The authors prove a convergence theorem for D-PSGD with arbitrarily time-varying random mixing matrices (Theorem III.2), express the required number of iterations as a function of time-averaged mixing parameters, and use this to formulate a multi-phase randomized mixing-matrix design. A central ingredient is Lemma IV.1, which bounds the expected maximum per-node energy over a phase by q(T,D). The paper then proposes a trilevel algorithm (Algorithm 1) that minimizes this bound, together with lower-level budgeted mixing-matrix design algorithms for both broadcast and unicast cost models. Experiments on CIFAR-10 over clique and Roofnet topologies are reported to support the benefits of the multi-phase design.

Significance. If the technical claims were correct, the paper would make a useful contribution: Theorem III.2 is a plausible generalization of the periodic-topology analysis in [34] to arbitrarily time-varying random mixing matrices, and the objective of minimizing worst-case per-node energy under broadcast communications is not well covered by prior work. The paper also provides an explicit asymptotic characterization of the budgeted design on a clique (Theorem V.2) and an SDP-based meta-algorithm for unicast communications. These are valuable ingredients. However, the central energy bound on which the entire multi-phase objective is built, Lemma IV.1 / Eq. (14), is false as stated. Because Algorithm 1 and Eqs. (16),(18) minimize this invalid bound, the paper's main design claim is not currently supported. The flaw is local and fixable, but it is load-bearing, so the manuscript requires major revision before it can be accepted.

major comments (2)
  1. [Lemma IV.1 / Eq. (14)] Lemma IV.1 is false as stated. Its proof (Appendix C) applies Hoeffding's inequality with per-iteration range D, but the lemma only assumes E[c_i(W)] <= D. Under the broadcast cost model (3) and the feasibility assumption (19), an activated node can spend ca_i+cb_i > D, so c_i(W(t)) is not bounded by D. Concrete counterexample: m=10, ca_i=0, cb_i=100, D=1, activation probability 0.01, T=1 gives E[c_i]=1 <= D but E[max_i c_i] = 100(1-0.99^10) ~ 9.56, while q(1,1)=1+10 sqrt(pi/8) ~ 7.27. Since QK in Algorithm 1 and Eqs. (16),(18) are built on this bound, the multi-phase objective can understate the true worst-case energy and is not a valid upper bound. The fix is to use a Hoeffding bound with the actual per-node range (e.g., cb_i or ca_i+cb_i), producing q(T,D)=D T + m (max_i cb_i) sqrt(pi T/8) up to constants, and to propagate this corrected bound through the design optimization.
  2. [Section VII-B.1 (duration normalization)] The experimental validation does not test the algorithm as designed. The paper says that tau_s from the optimization is normalized by tau_s * (T_actual / T_bound) because the optimization is based on an upper bound on the total number of iterations. This post-hoc scaling changes the phase durations after optimization, so the evaluated schedules are not the minimizers of QK, and T_actual is not known in advance in practice. To support the empirical claims, the authors should report the optimized schedule and the realized schedule separately, or justify that this normalization preserves optimality.
minor comments (5)
  1. [Appendix A, Lemma A.2] The proof relies on Lemma 3.1 of the self-cited preprint [15] for a key equivalence of p(t). Please make this step self-contained or state clearly where Lemma 3.1 is proved; readers should not need to consult an unpublished/parallel preprint for a load-bearing equivalence.
  2. [Remark 2 after Theorem III.2] There is a typo: 'dependnece' should be 'dependence'.
  3. [Section VII-B.1] The notation 'tau_s * (T / T)' for duration normalization is ambiguous. Please define the upper bound and the actual number of iterations with distinct symbols, e.g., T_bound and T_actual, and clarify whether the normalization factor is T_actual / T_bound.
  4. [Section VI-A] The sentence 'Problem (24) is similar to problem (19) in [7]' references an equation number in another paper without giving the equation or a clear pointer; consider rephrasing to avoid confusion with Eq. (19) of this manuscript.
  5. [Section IV-B] The notation q(T,D) is used before it is defined in Lemma IV.1; reorder or add a forward reference for clarity.

Circularity Check

0 steps flagged

No material circularity: Theorem III.2 is a genuine convergence theorem proven from external lemmas; same-author citations are technical bridges, not the target result. The Hoeffding gap in Lemma IV.1 is a correctness issue, not a circular reduction.

full rationale

The paper's central first-principles claim is Theorem III.2, which gives a convergence-time bound in terms of Π1, Π2, π0, and pmin. The appendix carries out a proof from Lemmas A.1 and A.2, which are quoted from the external work [34] (Koloskova et al.); the only same-author reliance is [15]'s Lemma 3.1, used to identify the paper's p(t) with the p(t) of [34] (Appendices A and B). That is a technical bridge, not the target result, so it does not make the theorem equivalent to its input. The multi-phase design framework then relaxes the true expected-max-energy objective using q(T,D) from Lemma IV.1. This is a relaxation, not a circular prediction: q is not fed back into Theorem III.2, and the convergence theorem does not depend on q. However, the proof of Lemma IV.1 applies Hoeffding's inequality with per-iteration range D, although under the paper's own broadcast cost model (3) and feasibility assumption (19), an activated node can incur c_a^i + c_b^i > D. This is a missing hypothesis and makes q(T,D) an invalid upper bound in general, so the QK objective is not a theoretically justified energy bound. That is a correctness flaw, not a cycle in the derivation chain. Similarly, Corollary VI.1 leans on a bound from [15], a same-author preprint, but again as an external performance bound for the lower-level algorithm rather than as the paper's conclusion. On the circularity axis, the result is substantially self-contained, with only minor same-author citations.

Axiom & Free-Parameter Ledger

1 free parameters · 8 axioms · 0 invented entities

The central theoretical contribution rests on imported convergence lemmas (mostly from [34] and self-cited [15]), a positivity assumption on p(t), and a concentration bound in Lemma IV.1 that is not valid under the paper's own cost model. No new physical entities are introduced.

free parameters (1)
  • post-hoc duration scaling factor T_actual/T_bound = not reported; depends on measured convergence epoch
    Section VII-B1 rescales optimized phase lengths by the empirically observed actual convergence iteration T, so the energy numbers in Figs. 3/5 depend on this fitted correction.
axioms (8)
  • domain assumption L-smoothness and noise assumptions (1)-(3): Lipschitz gradients, bounded stochastic-gradient noise, bounded heterogeneity.
    Adopted from [34]; stated in Section II-B and used in Theorem III.2.
  • domain assumption Mixing matrices are symmetric and have row/column sums equal to one.
    Section II-B; footnote relaxes double-stochasticity to row/column sums one, relying on [1]'s proof structure.
  • domain assumption Positive spectral-gap parameter p(t) (pmin > 0) for the mixing-matrix sequence.
    Lemma III.1 assumes p(t) ≥ δ; Theorem III.2's first term is infinite if pmin = 0, despite the paper's 'arbitrarily time-varying' claim.
  • domain assumption Broadcast cost model ignores link dynamics and retransmissions.
    Stated in the Remark after Eq. (3).
  • domain assumption Budget feasibility: max_i ca_i ≤ D < max_i(ca_i+cb_i).
    Assumption (19) in Section V-A; needed for a non-trivial budgeted design.
  • standard math Prior lemmas from Koloskova et al. [34] and Zhang et al. [15] are correct.
    Lemma A.2/A.5 and Appendix A/B import Lemmas 11/12 of [34] and Lemma 3.1 of [15] as black boxes.
  • ad hoc to paper Per-iteration energy c_i(W(t)) is bounded by the budget D for the Hoeffding argument.
    Unstated in Lemma IV.1; this boundedness is false under (3) when ca_i+cb_i > D, but the proof's Hoeffding tail bound requires it.
  • domain assumption For Theorem V.2, clique base topology and m→∞ asymptotics, conditioning on U≠∅.
    Section V-B1 uses asymptotic equivalence and treats the U=∅ probability as negligible.

pith-pipeline@v1.3.0-alltime-deepseek · 31 in / 18460 out tokens · 166150 ms · 2026-08-03T13:31:27.529841+00:00 · methodology

0 comments
read the original abstract

We consider the design of mixing matrices to minimize the operation cost for decentralized federated learning (DFL) in wireless networks, with focus on minimizing the maximum per-node energy consumption. As a critical hyperparameter for DFL, the mixing matrix controls both the convergence rate and the needs of agent-to-agent communications, and has thus been studied extensively. However, existing designs mostly focused on minimizing the communication time, leaving open the minimization of per-node energy consumption that is critical for energy-constrained devices. This work addresses this gap through a theoretically-justified solution for mixing matrix design that aims at minimizing the maximum per-node energy consumption until convergence, while taking into account the broadcast nature of wireless communications. Based on a novel convergence theorem that allows arbitrarily time-varying mixing matrices, we propose a multi-phase design framework that activates time-varying communication topologies under optimized budgets to trade off the per-iteration energy consumption and the convergence rate while balancing the energy consumption across nodes. Our evaluations based on real data have validated the efficacy of the proposed solution in combining the low energy consumption of sparse mixing matrices and the fast convergence of dense mixing matrices.

Figures

Figures reproduced from arXiv: 2512.24069 by Ting He, Tuan Nguyen, Xusheng Zhang.

Figure 1
Figure 1. Figure 1: Motivating experiment based on MNIST over a 100-node [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Design objective vs. design parameters for clique. [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Training performance on clique (‘proposed/BASS [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Design objective vs. design parameters for Roofnet. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Training performance on Roofnet. • ‘AdaPC’ [45], where all the neighbors communicate peri￾odically, with a period adapted according to [45, Alg. 2]; • ‘BASS’ [12], a state-of-the-art mixing matrix design for broadcast communication with a different objective of minimizing the communication time (by minimizing the number of collision-free transmission slots); • ‘Max Success’ [29], another mixing matrix desi… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

60 extracted references · 3 canonical work pages

  1. [1]

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

    X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. L iu, “Can decentralized algorithms outperform centralized algorit hms? a case study for decentralized parallel stochastic gradient descent,” in Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017, p. 5336–5346

    2017

  2. [2]

    Communication-efficient learning of deep networks from de centralized data,

    H. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arc as, “Communication-efficient learning of deep networks from de centralized data,” in AISTATS, 2017

    2017

  3. [3]

    Kairouz et al

    P . Kairouz et al. , Advances and Open Problems in Federated Learning . Now Foundations and Trends, 2021

    2021

  4. [4]

    Plink: Discovering and exploiting locality for accelerated distr ibuted training on the public cloud,

    L. Luo, P . West, J. Nelson, A. Krishnamurthy, and L. Ceze, “Plink: Discovering and exploiting locality for accelerated distr ibuted training on the public cloud,” in Proceedings of Machine Learning and Systems , vol. 2, 2020, pp. 82–97

    2020

  5. [5]

    Federated learning over multi- hop wireless networks with in-network aggregation,

    X. Chen, G. Zhu, Y . Deng, and Y . Fang, “Federated learning over multi- hop wireless networks with in-network aggregation,” IEEE Transactions on Wireless Communications , vol. 21, no. 6, pp. 4622–4634, 2022. 11

    2022

  6. [6]

    Decentral ized deep learning with arbitrary communication compression,

    A. Koloskova, T. Lin, S. U. Stich, and M. Jagg, “Decentral ized deep learning with arbitrary communication compression,” in The Interna- tional Conference on Learning Representations (ICLR) , 2020

    2020

  7. [7]

    Laplac ian matrix sampling for communication- efficient decentralize d learning,

    C.-C. Chiu, X. Zhang, T. He, S. Wang, and A. Swami, “Laplac ian matrix sampling for communication- efficient decentralize d learning,” IEEE Journal on Selected Areas in Communications , vol. 41, no. 4, pp. 887–901, 2023

    2023

  8. [8]

    SPARQ-SGD: Event- triggered and compressed communication in decentralized o ptimization,

    N. Singh, D. Data, J. George, and S. Diggavi, “SPARQ-SGD: Event- triggered and compressed communication in decentralized o ptimization,” in IEEE CDC , 2020

    2020

  9. [9]

    MA TCHA: A matchi ng- based link scheduling strategy to speed up distributed opti mization,

    J. Wang, A. K. Sahu, G. Joshi, and S. Kar, “MA TCHA: A matchi ng- based link scheduling strategy to speed up distributed opti mization,” IEEE Transactions on Signal Processing , vol. 70, pp. 5208–5221, 2022

    2022

  10. [10]

    E fficient and reliable overlay networks for decentralized federated lea rning,

    Y . Hua, K. Miller, A. L. Bertozzi, C. Qian, and B. Wang, “E fficient and reliable overlay networks for decentralized federated lea rning,” SIAM Journal on Applied Mathematics , vol. 82, no. 4, pp. 1558–1586, 2022

    2022

  11. [11]

    Refined convergence and topology learning for decentraliz ed SGD with heterogeneous data,

    B. Le Bars, A. Bellet, M. Tommasi, E. Lavoie, and A.-M. Ke rmarrec, “Refined convergence and topology learning for decentraliz ed SGD with heterogeneous data,” in International Conference on Artificial Intelligence and Statistics . PMLR, 2023, pp. 1672–1702

    2023

  12. [12]

    Faster conver gence with less communication: Broadcast-based subgraph sampling for dec entralized learning over wireless networks,

    D. P . Herrera, Z. Chen, and E. G. Larsson, “Faster conver gence with less communication: Broadcast-based subgraph sampling for dec entralized learning over wireless networks,” IEEE Open Journal of the Communi- cations Society , pp. 1–1, 2025

    2025

  13. [13]

    Federated learning over wireless device-to-device networks: Algorithms and convergence an alysis,

    H. Xing, O. Simeone, and S. Bi, “Federated learning over wireless device-to-device networks: Algorithms and convergence an alysis,” IEEE Journal on Selected Areas in Communications , vol. 39, no. 12, pp. 3723– 3741, 2021

    2021

  14. [14]

    Toward scalable and robust AIoT via decentralized federated learn ing,

    P . Pinyoanuntapong, W. H. Huff, M. Lee, C. Chen, and P . Wang, “Toward scalable and robust AIoT via decentralized federated learn ing,” IEEE Internet of Things Magazine , vol. 5, no. 1, pp. 30–35, 2022

    2022

  15. [15]

    Energy-efficient decen tralized learn- ing via graph sparsification,

    X. Zhang, C.-C. Chiu, and T. He, “Energy-efficient decen tralized learn- ing via graph sparsification,” 2024, https://arxiv.org/ab s/2401.03083

    Pith/arXiv arXiv 2024

  16. [16]

    d2: Decentralized training over decentralized data,

    H. Tang, X. Lian, M. Y an, C. Zhang, and J. Liu, “ d2: Decentralized training over decentralized data,” in Proceedings of the 35th Interna- tional Conference on Machine Learning, ICML , 2018

    2018

  17. [17]

    Optimal complexity in decentralized training,

    Y . Lu and C. D. Sa, “Optimal complexity in decentralized training,” in International Conference on Machine Learning (ICML) , 2021

    2021

  18. [18]

    A hybrid variance-reduced m ethod for decentralized stochastic non-convex optimization,

    R. Xin, U. Khan, and S. Kar, “A hybrid variance-reduced m ethod for decentralized stochastic non-convex optimization,” i n Proceedings of the 38th International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, M. Meila and T. Zh ang, Eds., vol. 139. PMLR, 18–24 Jul 2021, pp. 11 459–11 469. [Onli ne]. Available: https://proce...

    2021

  19. [19]

    Delay analysis of wireless federated learning based on sad dle point approximation and large deviation theory,

    L. Li, L. Y ang, X. Guo, Y . Shi, H. Wang, W. Chen, and K. B. Le taief, “Delay analysis of wireless federated learning based on sad dle point approximation and large deviation theory,” IEEE Journal on Selected Areas in Communications , vol. 39, no. 12, pp. 3772–3789, 2021

    2021

  20. [20]

    Moniqua: Modulo quantized communica tion in decentralized SGD,

    Y . Lu and C. D. Sa, “Moniqua: Modulo quantized communica tion in decentralized SGD,” in International Conference on Machine Learning (ICML), 2020

    2020

  21. [21]

    Communic ation com- pression for decentralized training,

    H. Tang, S. Gan, C. Zhang, T. Zhang, and J. Liu, “Communic ation com- pression for decentralized training,” in Advances in Neural Information Processing Systems (NeurIPS) , 2018

    2018

  22. [22]

    Communicati on-efficient network-distributed optimization with differential-cod ed compressors,

    X. Zhang, J. Liu, Z. Zhu, and E. S. Bentley, “Communicati on-efficient network-distributed optimization with differential-cod ed compressors,” in IEEE INFOCOM , 2020, p. 317–326

    2020

  23. [23]

    Adaptive communication strategi es to achieve the best error-runtime trade-off in local-update SGD,

    J. Wang and G. Joshi, “Adaptive communication strategi es to achieve the best error-runtime trade-off in local-update SGD,” in Systems for ML, 2019

    2019

  24. [24]

    Federated learning over wireless networks: Optimization model design and analysis,

    N. H. Tran, W. Bao, A. Zomaya, M. N. Nguyen, and C. S. Hong, “Federated learning over wireless networks: Optimization model design and analysis,” in IEEE INFOCOM , 2019

    2019

  25. [25]

    Adaptive federated learning in resource constrai ned edge com- puting systems,

    S. Wang, T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan, “Adaptive federated learning in resource constrai ned edge com- puting systems,” IEEE Journal on Selected Areas in Communications , vol. 37, no. 6, pp. 1205–1221, 2019

    2019

  26. [26]

    Cooperative sgd: A unified framewo rk for the design and analysis of local-update sgd algorithms,

    J. Wang and G. Joshi, “Cooperative sgd: A unified framewo rk for the design and analysis of local-update sgd algorithms,” Journal of Machine Learning Research , vol. 22, no. 213, pp. 1–50, 2021. [Online]. Available: http://jmlr.org/papers/v22/20-147.html

    2021

  27. [27]

    SQuARM-SG D: Communication-efficient momentum SGD for decentralized op timiza- tion,

    N. Singh, D. Data, J. George, and S. Diggavi, “SQuARM-SG D: Communication-efficient momentum SGD for decentralized op timiza- tion,” IEEE Journal on Selected Areas in Information Theory , vol. 2, no. 3, pp. 954–969, 2021

    2021

  28. [28]

    Energy-aware decentral ized learning with intermittent model training,

    M. De V os, A. Dhasade, P . Dini, E. Guerra, A.-M. Kermarre c, M. Miozzo, R. Pires, and R. Sharma, “Energy-aware decentral ized learning with intermittent model training,” in 2024 IEEE International Parallel and Distributed Processing Symposium W orkshops ( IPDPSW), 2024, pp. 1172–1174

    2024

  29. [29]

    Decentralized lear ning over wireless networks: The effect of broadcast with random acce ss,

    Z. Chen, M. Dahl, and E. G. Larsson, “Decentralized lear ning over wireless networks: The effect of broadcast with random acce ss,” in 2023 IEEE 24th International W orkshop on Signal Processing Adva nces in Wireless Communications (SPAWC), 2023, pp. 316–320

    2023

  30. [30]

    Decentraliz ed gradient methods: does topology matter?

    G. Neglia, C. Xu, D. Towsley, and G. Calbi, “Decentraliz ed gradient methods: does topology matter?” in International Conference on Artifi- cial Intelligence and Statistics . PMLR, 2020, pp. 2348–2358

    2020

  31. [31]

    Joi nt model pruning and topology construction for accelerating d ecentralized machine learning,

    Z. Jiang, Y . Xu, H. Xu, L. Wang, C. Qiao, and L. Huang, “Joi nt model pruning and topology construction for accelerating d ecentralized machine learning,” IEEE Transactions on Parallel and Distributed Systems, 2023

    2023

  32. [32]

    Beyond spectral g ap: The role of the topology in decentralized learning,

    T. V ogels, H. Hendrikx, and M. Jaggi, “Beyond spectral g ap: The role of the topology in decentralized learning,” Advances in Neural Information Processing Systems, vol. 35, pp. 15 039–15 050, 2022

    2022

  33. [33]

    Decentralized federated learning: Balancing communication and computing costs,

    W. Liu, L. Chen, and W. Zhang, “Decentralized federated learning: Balancing communication and computing costs,” IEEE Transactions on Signal and Information Processing over Networks , vol. 8, pp. 131–143, 2022

    2022

  34. [34]

    A unified theory of decentralized SGD with changing topology and loca l updates,

    A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Sti ch, “A unified theory of decentralized SGD with changing topology and loca l updates,” in ICML, 2020

    2020

  35. [35]

    Distributed optimization over time-varying directed graphs,

    A. Nedi´ c and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control , vol. 60, no. 3, pp. 601–615, 2015

    2015

  36. [36]

    Achieving geometr ic convergence for distributed optimization over time-varying graphs,

    A. Nedi´ c, A. Olshevsky, and W. Shi, “Achieving geometr ic convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization , vol. 27, no. 4, pp. 2597–2633, 2017. [Online]. Available: https://doi.org/10.1137/16M1084316

    work page doi:10.1137/16m1084316 2017

  37. [37]

    Accelerated gradient tracking over ti me-varying graphs for decentralized optimization,

    H. Li and Z. Lin, “Accelerated gradient tracking over ti me-varying graphs for decentralized optimization,” Journal of Machine Learning Research, vol. 25, no. 274, pp. 1–52, 2024. [Online]. Available: http://jmlr.org/papers/v25/21-0475.html

    2024

  38. [38]

    Optimal complexity in non-convex decentralized learning over time-varying networks,

    X. Huang and K. Y uan, “Optimal complexity in non-convex decentralized learning over time-varying networks,” 2022 . [Online]. Available: https://arxiv.org/abs/2211.00533

    Pith/arXiv arXiv 2022

  39. [39]

    DAdaQuant: Doubly- adaptive quantization for communication-efficient federated learn ing,

    R. H¨ onig, Y . Zhao, and R. Mullins, “DAdaQuant: Doubly- adaptive quantization for communication-efficient federated learn ing,” in Proceedings of the 39th International Conference on Machin e Learning, ser. Proceedings of Machine Learning Research, K. Chaudhur i, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds ., vol

  40. [40]

    Communication - efficient federated learning with adaptive compression und er dynamic bandwidth,

    Y . Zhuansun, D. Li, X. Huang, and C. Sun, “Communication - efficient federated learning with adaptive compression und er dynamic bandwidth,” 2024. [Online]. Available: https://arxiv.or g/abs/2405.03248

    Pith/arXiv arXiv 2024

  41. [41]

    Communication-efficient fed erated learning via dynamic sparsity: An adaptive pruning ratio based on wei ght importance,

    L. Wang, X. Xu, and J. Pei, “Communication-efficient fed erated learning via dynamic sparsity: An adaptive pruning ratio based on wei ght importance,” IEEE Transactions on Cognitive Communications and Networking, pp. 1–1, 2025

    2025

  42. [42]

    Class-wis e adaptive self distillation for federated learning on non-i id data (student abstract),

    Y . He, Y . Chen, X. Y ang, Y . Zhang, and B. Zeng, “Class-wis e adaptive self distillation for federated learning on non-i id data (student abstract),” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 11, pp. 12 967–12 968, Jun. 2022. [Online]. Available: https://ojs.aaai.org/index.php/AAAI/article/view/21620

    2022

  43. [43]

    Communication-efficient federated learning for heteroge neous clients,

    Y . Li, X. Wang, H. Li, P . K. Donta, M. Huang, and S. Dustdar , “Communication-efficient federated learning for heteroge neous clients,” ACM Trans. Internet Technol. , vol. 25, no. 2, Apr. 2025. [Online]. Available: https://doi.org/10.1145/3716870

    work page doi:10.1145/3716870 2025

  44. [44]

    Communication-Efficient Federated Learning wit h Adaptive Parameter Freezing ,

    C. Chen, H. Xu, W. Wang, B. Li, B. Li, L. Chen, and G. Zhang, “ Communication-Efficient Federated Learning wit h Adaptive Parameter Freezing ,” in 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS) . Los Alamitos, CA, USA: IEEE Computer Society, Jul. 2021, pp. 1–11. [Online]. Avail able: https://doi.ieeecomputersociety.org/10....

    arXiv 2021

  45. [45]

    Adaptive period control for communication efficient and fast converg ent federated learning,

    J. Tchaye-Kondi, Y . Zhai, J. Shen, A. Telikani, and L. Zh u, “Adaptive period control for communication efficient and fast converg ent federated learning,” IEEE Transactions on Mobile Computing , vol. 23, no. 12, pp. 12 572–12 586, 2024

    2024

  46. [46]

    Adaptive c lient selection in resource constrained federated learning syst ems: A deep 12 reinforcement learning approach,

    H. Zhang, Z. Xie, R. Zarei, T. Wu, and K. Chen, “Adaptive c lient selection in resource constrained federated learning syst ems: A deep 12 reinforcement learning approach,” IEEE Access , vol. 9, pp. 98 423– 98 432, 2021

    2021

  47. [47]

    Decen tralized machine learning through experience-driven method in edge networks,

    H. Xu, M. Chen, Z. Meng, Y . Xu, L. Wang, and C. Qiao, “Decen tralized machine learning through experience-driven method in edge networks,” IEEE Journal on Selected Areas in Communications , vol. 40, no. 2, pp. 515–531, 2022

    2022

  48. [48]

    Decentralized federated learning with adaptive configura tion for heterogeneous participants,

    Y . Liao, Y . Xu, H. Xu, L. Wang, C. Qian, and C. Qiao, “Decentralized federated learning with adaptive configura tion for heterogeneous participants,” IEEE Transactions on Mobile Computing , vol. 23, no. 6, p. 7453–7469, Jun. 2024. [Online]. Available : https://doi.org/10.1109/TMC.2023.3335403

    arXiv 2024

  49. [49]

    Problem complexity and method efficiency in o ptimization (a. s. nemirovsky and d. b. yudin),

    C. Blair, “Problem complexity and method efficiency in o ptimization (a. s. nemirovsky and d. b. yudin),” SIAM Review , vol. 27, no. 2, pp. 264–265, 1985. [Online]. Available: https://doi.org/10. 1137/1027074

    1985

  50. [50]

    Distributed average co nsensus with time-varying metropolis weights,

    L. Xiao, S. P . Boyd, and S. Lall, “Distributed average co nsensus with time-varying metropolis weights,” 2006, unpublished manu script. [On- line]. Available: https://api.semanticscholar.org/CorpusID:123313438

    2006

  51. [51]

    Communication-efficient a daptive federated learning,

    Y . Wang, L. Lin, and J. Chen, “Communication-efficient a daptive federated learning,” in Proceedings of the 39th International Conference on Machine Learning , ser. Proceedings of Machine Learning Research, K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu, and S. Sabato, Eds., vol. 162. PMLR, 17–23 Jul 2022, pp. 22 802–22 838. [Online]. Available:...

    2022

  52. [52]

    Asyn- chronous decentralized sgd with quantized and local update s,

    G. Nadiradze, A. Sabour, P . Davies, S. Li, and D. Alistar h, “Asyn- chronous decentralized sgd with quantized and local update s,” in Pro- ceedings of the 35th International Conference on Neural Inf ormation Processing Systems , ser. NIPS ’21. Red Hook, NY , USA: Curran Associates Inc., 2021

    2021

  53. [53]

    Communication-efficient decentralized machine learning over heteroge- neous networks,

    P . Zhou, Q. Lin, D. Loghin, B. C. Ooi, Y . Wu, and H. Y u, “Communication-efficient decentralized machine learning over heteroge- neous networks,” in 2021 IEEE 37th International Conference on Data Engineering (ICDE) , 2021, pp. 384–395

    2021

  54. [54]

    Exploring the e rror- runtime trade-off in decentralized optimization,

    J. Wang, A. K. Sahu, G. Joshi, and S. Kar, “Exploring the e rror- runtime trade-off in decentralized optimization,” in 2020 54th Asilomar Conference on Signals, Systems, and Computers , 2020, pp. 910–914

    2020

  55. [55]

    Expander graphs and their applications,

    S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications,” Bull. Amer . Math. Soc., vol. 43, no. 04, p. 439–562, Aug. 2006

    2006

  56. [56]

    Link-level measurements from an 802.11b mesh network,

    D. Aguayo, J. Bicket, S. Biswas, G. Judd, and R. Morris, “ Link-level measurements from an 802.11b mesh network,” in SIGCOMM, 2004

    2004

  57. [57]

    A first look into the carbon footprint of federated learning,

    X. Qiu, T. Parcollet, J. Fernandez-Marques, P . P . B. Gus mao, D. J. Beutel, T. Topal, A. Mathur, and N. D. Lane, “A first look into the carbon footprint of federated learning,” 2021. [Online ]. Available: https://arxiv.org/abs/2102.07627

    Pith/arXiv arXiv 2021

  58. [58]

    On the convergence of decentralized gradient descent,

    K. Y uan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” SIAM Journal on Optimization , vol. 26, no. 3, pp. 1835–1854, 2016. [Online]. Available: https://doi.org/10.1137/130943170 APPENDIX A. Proof of Theorem III.2 We use the following notation for the “consensus distance” at iteration t: Ξt := 1 m I E m∑ i=1 ∥x(t) i − x(0)∥2...

    work page doi:10.1137/130943170 2016

  59. [60]

    Next we prove that there exists C > 0 such that Pr[τ ′ > Cm ]≤ e−Ω(m), from which the lemma follows

    Hence, ∥W− J∥ = max(|λ2(W )|,|λm(W )|) < 1, and this implies that ρτ ′≤ ρ∗≤ (1− ǫ) + ǫ∥W− J∥ < 1. Next we prove that there exists C > 0 such that Pr[τ ′ > Cm ]≤ e−Ω(m), from which the lemma follows. By assumption, there is a constant c > 0 such that for each e∈ E and every iteration k, e /∈ Ek occurs with probability at most 1− c. Then e /∈ Ej for any of ...

  60. [162]

    8852–8866

    PMLR, 17–23 Jul 2022, pp. 8852–8866. [Online]. Availab le: https://proceedings.mlr.press/v162/honig22a.html

    2022