acceptodds
Under review as a conference paper at ICLR 2027

Sporadic Gradient Tracking over Directed Graphs: A Theoretical Perspective on Decentralized Federated Learning

Abstract

Decentralized Federated Learning (DFL) enables clients with local data to collaborate in a peer-to-peer manner to train a generalized model. In this paper, we propose a novel formulation that unifies two branches of work that have separately solved important challenges in DFL as special cases: (i) push-pull gradient tracking techniques for stable convergence over directed graphs and (ii) resource-aware methods for handling heterogeneous client. We propose *Sporadic Gradient Tracking* (), the first DFL algorithm that incorporates these factors over directed graphs by allowing flexible (i) client-specific gradient computation frequencies and (ii) heterogeneous and asymmetric inter-client communication frequencies. We conduct a rigorous convergence analysis of our methodology with a relaxed assumption on gradient diversity, providing consensus and stationarity guarantees for GT over directed graphs under intermittent client participation. Through numerical experiments on image classification datasets, we demonstrate the efficacy of compared to well-known GT baselines.

Primary area:
optimization
Keywords:
Gradient tracking, directed graphs, decentralized federated learning, sporadicity

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_MLX6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers decentralized federated learning (DFL) problem. In practice, there are heterogeneities in computations and communications of the clients, which hinder the convergence of existing methods. To deal with this issue, the authors propose Spod-GT, which can handle these heterogeneities on directed graph, and prove its convergence guarantee. In numerical experiments on image classification tasks, the proposed method is shown to outperform existing methods.

Critical strengths
  • The problem set-up (heterogeneities in computations and communicaitons) is well-motivated and important in practice.
  • General formulation with sporadicity poses several theoretical challenges (challenges 1&2) for proving the convergence guarantee of the proposed method. The authors address these challenges and provide rigorous convergence guarantee for non-convex functions. Some of the assumptions (e.g. smoothness, gradient diversity) are standard in this field and the rest of them (e.g. Assumption 4.3) seem reasonable.
Critical weaknesses
  • The numerical experiments are conducted on relatively small datasets (FEMIST, CIFAR-10), which are not curated for FL.
  • In practice, client's decisions across steps are not necessarily independent. Thus, Assumption 4.3 may not hold.
Questions for authors
  1. What is the definition of the total delay τ\tau in the numerical experiments? I'm wondering if the comparison w.r.t. τ\tau is fair.
  2. Why did (Sporadic) K-GT perform poorly even in the IID setup of CIFAR-10? In addition, why was AB/Push-Pull not included in the CIFAR-10 experiments?
5 comments

We thank the reviewer for the positive assessment and for the questions on the experiments.

W1: Datasets curated for FL

On FEMNIST, a dataset curated for FL, Spod-GT is the most accurate method at every budget under both delay metrics. We added FEMNIST from LEAF (App. K.5 of the revision) with its natural federated data partition, using 100 randomly chosen clients. The images of each client are split 80/20 into training and test data, and the test data of all clients are pooled. We train a linear SVM over the 62 classes with step size 0.01 for all methods, on the directed geometric graph of App. K.4 with pip_i and p^ij\hat p_{ij} drawn from U(0, 1). Since the reviewer also asked about the delay definition (Q1), the table reports both the initial submission's averaged delay τˉ\bar\tau and the parallel delay τ\tau defined in Q1 below.

FEMNIST, 100 clients, both delay metrics (accuracy %).

Averaged delay τˉ\bar\tau

Methodτˉ=103\bar\tau = 10^3τˉ=3⋅103\bar\tau = 3 \cdot 10^3τˉ=104\bar\tau = 10^4τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull21.832.144.951.5
G-Push-Pull29.840.350.055.1
K-GT28.337.848.052.4
Sporadic K-GT18.728.442.149.6
Spod-GT (ours)34.945.752.756.5

Parallel delay τ\tau

Methodτ=2.5⋅104\tau = 2.5 \cdot 10^4τ=8⋅104\tau = 8 \cdot 10^4τ=2.5⋅105\tau = 2.5 \cdot 10^5τ=8⋅105\tau = 8 \cdot 10^5
AB/Push-Pull11.623.334.045.1
G-Push-Pull26.237.246.953.6
K-GT19.931.541.549.2
Sporadic K-GT6.916.927.239.5
Spod-GT (ours)33.444.952.156.2

App. K.3 already reports Tiny-ImageNet with a ConvNeXt model, and we added runs with 100 and 1000 clients (App. K.4).

W2: Independence across steps

We would like to kindly clarify that, in this work, our focus is sporadic computation and communication over static directed networks, a setting that had not been studied even without temporal dependence. As a result, our paper does not claim to handle time-varying or temporally correlated participation. We note that even in the static setting, sporadicity raises two hurdles, described as Theoretical Challenges 1 and 2 (Sec. 4.1 and 4.2). The per-iteration matrices A^(k)\hat A^{(k)} and B^(k)\hat B^{(k)} are not strongly connected, so they lose the spectral properties of their expectations, and the trackers follow a masked average of the gradients computed in each iteration. Handling these two effects is the core of our proofs.

In simulation, Spod-GT still works with temporally correlated participation (new App. K.7). Each client's computation and each link's activation follow a two-state Markov chain, P(active at k+1)=λ⋅1[active at k]+(1−λ)pP(\text{active at } k+1) = \lambda \cdot \mathbf{1}[\text{active at } k] + (1-\lambda) p, which keeps the long-run rates pip_i and p^ij\hat p_{ij} but makes on/off periods 1/(1−λ)1/(1-\lambda) times longer. λ=0\lambda = 0 is the independent case.

FMNIST, 100 clients, non-IID data, Markov participation (accuracy %).

λ=0\lambda = 0

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull63.181.1
G-Push-Pull68.282.3
K-GT43.073.5
Sporadic K-GT59.379.0
Spod-GT (ours)69.682.4

λ=0.8\lambda = 0.8

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull63.680.9
G-Push-Pull67.382.0
K-GT43.373.7
Sporadic K-GT58.478.8
Spod-GT (ours)68.982.1

λ=0.95\lambda = 0.95

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull62.480.9
G-Push-Pull63.481.5
K-GT42.073.6
Sporadic K-GT55.378.6
Spod-GT (ours)64.381.4

As shown in the above tables, Spod-GT remains the most accurate method early in training at every λ\lambda, and within 0.1 points of the best at τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4. With 20× longer on/off periods (λ=0.95\lambda = 0.95), it loses about 5 points early in training and 1 point at τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4. AB/Push-Pull and K-GT do not depend on λ\lambda, since all their clients are always active or follow a fixed schedule, and their small differences come from the random draws. A full analysis of such dynamic network settings along with its theory is left as future work, which is now mentioned in the Conclusion of the revision.

Q1: Definition and fairness of the total delay

We apologize that the definition was easy to miss. Because of the page limit, we placed it in App. B.7 (Experiment Settings) of the initial submission, which defines the total delay as τˉtotal=τˉtrans,in+τˉproc+τˉtrans,out\bar\tau_{\mathrm{total}} = \bar\tau_{\mathrm{trans,in}} + \bar\tau_{\mathrm{proc}} + \bar\tau_{\mathrm{trans,out}}, where τˉproc\bar\tau_{\mathrm{proc}} averages vi/piv_i/p_i over the clients and the two transmission terms average v^ij/p^ij\hat v_{ij}/\hat p_{ij} over each client's incoming and outgoing links. The initial submission's averaged delay τˉ\bar\tau is essentially the average time a client spends on computation and communication per iteration, time it cannot use for anything else. We chose it to show how letting each client participate in proportion to its resources reduces this time across the network. The new parallel delay τ\tau measures the actual wall-clock delay of each iteration.

In particular, the revision adds a second metric, the parallel delay τ\tau, and reports both for all new experiments (App. K.4 and K.5). In the parallel delay, clients and links run in parallel, and an iteration ends when the slowest active client finishes.

τ(k)=max⁡i[vi(k)pi+2max⁡j∈Niinv^ij(k)p^ij],τtotal(K)=∑k=0K−1τ(k)\tau^{(k)} = \max_{i} \Big[ \frac{v_i^{(k)}}{p_i} + 2 \max_{j \in \mathcal{N}_i^{\mathrm{in}}} \frac{\hat v_{ij}^{(k)}}{\hat p_{ij}} \Big], \qquad \tau_{\mathrm{total}}^{(K)} = \sum_{k=0}^{K-1} \tau^{(k)}

The factor 2 accounts for the two vectors xjx_j and yjy_j that each active link carries. For the same reason, the initial submission's averaged delay τˉtotal=τˉtrans,in+τˉproc+τˉtrans,out\bar\tau_{\mathrm{total}} = \bar\tau_{\mathrm{trans,in}} + \bar\tau_{\mathrm{proc}} + \bar\tau_{\mathrm{trans,out}} has two transmission terms, one for incoming and one for outgoing messages.

Both metrics are fair: every method pays the same unit costs, 1/pi1/p_i per gradient and 1/p^ij1/\hat p_{ij} per message, through its own indicators, and no method is charged for work it does not do. Nevertheless, they capture different things: τˉ\bar\tau the total resources spent by the clients and the links in the network and τ\tau the time until an iteration completes.

Spod-GT obtains a better performance gain under the parallel delay metric. This is mainly because every baseline waits in each iteration for all of its clients, all of its links, or both, while Spod-GT waits only for those that are active. Against the second-best method, G-Push-Pull, our Spod-GT's lead grows under τ\tau at every budget, on FMNIST from 2.4 and 0.7 points under τˉ\bar\tau to 2.7 and 0.9 points under τ\tau (table below), and on FEMNIST from 5.1, 5.4, 2.7 and 1.4 points to 7.2, 7.7, 5.2 and 2.6 points (App. K.5).

FMNIST, 100 clients, IID data, both delay metrics (accuracy %).

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4τ=2⋅104\tau = 2 \cdot 10^4τ=7⋅105\tau = 7 \cdot 10^5
AB/Push-Pull67.181.136.375.1
G-Push-Pull71.282.469.082.0
K-GT67.778.452.677.1
Sporadic K-GT64.279.926.772.3
Spod-GT (ours)73.683.171.782.9

Q2: K-GT, Sporadic K-GT, and AB/Push-Pull on CIFAR-10

We thank the reviewer for pointing this out. We should have stated clearly that, in the plots, AB/Push-Pull was hidden under Sporadic K-GT and that both methods start learning late on the delay axis. The re-plotted figure (App. K.2 of the revision) shows all five methods. With full participation, every iteration costs as much as the slowest client and link, so AB/Push-Pull starts learning only at a total delay of about 10410^4, where Spod-GT's run ends. Within the plotted range, its curve stayed at accuracy 0. We re-plotted the figure with a log delay axis over a longer range, as for Tiny-ImageNet in App. K.3.


We appreciate your time and effort in reviewing our paper. We would be happy to address any remaining questions or concerns the reviewer might have.

Dear Reviewer MLX6,

Thank you again for your time and constructive feedback. Have we addressed your concerns? We would appreciate the opportunity to further clarify any remaining perceived issues as you finalize your assessment.

Reviewer_KXY2OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Spod-GT for decentralized learning when clients and directed links have different resource limits. Clients independently skip gradient evaluations, and links independently skip model and tracker exchanges. The tracker uses current gradients from active clients and zero contributions from skipped clients. The analysis studies consensus and nonconvex stationarity, including the residual error allowed at fixed computation probabilities. Experiments on Fashion-MNIST, CIFAR-10 and Tiny-ImageNet report higher accuracy at the same modeled computation and communication cost.

Critical strengths
  1. Separate probabilities pip_i and p^ij\hat p_{ij} provide a simple way to control gradient work and directed-link use.
  2. Equation (8) makes clear what the sampled tracker represents. The analysis separates model disagreement, tracking error, and the effect of skipped gradients.
  3. The experiments cover three datasets, IID and non-IID data, and five runs. The Tiny-ImageNet results also include accuracy against iterations, alongside the cost-based plots.
Critical weaknesses
  1. The benefit of using zero instead of a skipped client's last gradient is not clear. PPDS [1] keeps the last gradients under random device sampling and directed communication, but is neither discussed nor compared. Its theory assumes convex local losses and a strongly convex global objective, while Spod-GT studies nonconvex losses. At a common model, Eq. (8) weights clients' gradients by pip_i in expectation. Appendix B.4 notes this effect, but the reason for choosing zero remains unclear.
  2. The communication conditions seem too strict to explain the reported savings. For a complete 10-client graph with uniform weights, the sufficient conditions in Proposition 4.8 and Table 2 imply 1−p^ij<2.8×10−351-\hat p_{ij}<2.8\times10^{-35}. This allows almost no communication skipping. Appendix B.7 samples p^ij\hat p_{ij} from Beta(0.5,0.5)\mathrm{Beta}(0.5,0.5), but does not show whether these settings satisfy the theory's conditions.
  3. The delay metric may not reflect actual training time. Appendix B.7 defines τˉtotal\bar\tau_{\mathrm{total}} by averaging computation and communication costs across clients and links. It is unclear how this average relates to time when clients run in parallel. This makes the reported 100-fold speedup in Appendix J.2 difficult to assess.

[1] Hsieh et al. “Push–Pull With Device Sampling.” IEEE Transactions on Automatic Control, 2023.

[2] Pu et al. “Push–Pull Gradient Methods for Distributed Optimization in Networks.” IEEE Transactions on Automatic Control, 2021.

Questions for authors
  1. Why choose zero instead of a skipped client's last gradient? A comparison with PPDS at the same computation and communication cost could help explain the benefit. A version of Spod-GT that keeps the last gradients would also help test this choice.
  2. What communication probabilities do the stated conditions allow on the experimental graphs? Can the authors give less strict conditions that cover the probabilities used in Appendix B.7?
  3. Do the speedups still hold when using measured training time or a model that accounts for parallel execution? For G-Push-Pull, which clients compute new gradients, and does this follow Algorithm 2 of [2]?
6 comments

We thank the reviewer for a precise and constructive review.

W1/Q1: Zeroing skipped gradients, and PPDS

Zeroing skipped gradients makes the tracker average equal the average of the gradients computed in that iteration, an identity our analysis relies on, and its cost vanishes as pi→1p_i \to 1. At a common model, the tracker weights client ii's gradient by pip_i in expectation, which gives the (1−pi)δ0,i2(1-p_i)\delta_{0,i}^2 term of Thm. 4.9, and with pi=1−O(1/K)p_i = 1 - O(1/K) the stationarity gap vanishes at rate O(1/K)O(1/K) (Cor. 4.10). PPDS instead keeps each client's last gradient in its tracker, so that every client enters the tracker sum once, at the cost of random staleness with no deterministic bound.

In a new comparison (App. K.6), Spod-GT is more accurate than PPDS at every budget in all three settings we tested. We implement PPDS as published, following Alg. 1 of Hsieh et al. with the broadcast scheme of their experiments. In each iteration, SS clients are sampled uniformly at random, where SS is the average number of clients that compute per iteration in Spod-GT (the sum of the pip_i, rounded), so that both methods compute equally many gradients on average. Each sampled client refreshes its tracker with the difference between its new and last gradients, takes a local step, and sends (x,y)(x, y) (model parameters and GT parameters) to one random out-neighbor. All new experiments use the directed geometric graphs of App. K.4 of the revision. Both methods pay the same unit costs 1/pi1/p_i and 1/p^ij1/\hat p_{ij} and are tuned over the same step sizes, {0.003, 0.01, 0.03, 0.1, 0.3} on FMNIST and {0.01, 0.03, 0.1} on the synthetic problem. Since the reviewer asked about the delay metric, the tables use the parallel delay τ\tau defined in W3/Q3 below.

FMNIST, 100 clients, pip_i and p^ij\hat p_{ij} from U(0, 1) (accuracy %).

IID data

Methodτ=2⋅104\tau = 2 \cdot 10^4τ=7⋅104\tau = 7 \cdot 10^4τ=2⋅105\tau = 2 \cdot 10^5τ=7⋅105\tau = 7 \cdot 10^5
PPDS54.064.571.275.5
Spod-GT (ours)74.579.381.383.0

Non-IID data

Methodτ=2⋅104\tau = 2 \cdot 10^4τ=7⋅104\tau = 7 \cdot 10^4τ=2⋅105\tau = 2 \cdot 10^5τ=7⋅105\tau = 7 \cdot 10^5
PPDS38.056.668.775.0
Spod-GT (ours)67.875.478.882.1

FMNIST, 10 clients, pip_i and p^ij\hat p_{ij} from Beta(0.5, 0.5) (the resource distribution of the initial submission, accuracy %, log-spaced budgets). PPDS needs a gradient of every client at initialization, which is expensive for the slowest clients under these resources.

IID data

Methodτ=103\tau = 10^3τ=104\tau = 10^4τ=105\tau = 10^5τ=106\tau = 10^6
PPDS14.428.243.861.3
Spod-GT (ours)60.373.580.682.3

Non-IID data

Methodτ=103\tau = 10^3τ=104\tau = 10^4τ=105\tau = 10^5τ=106\tau = 10^6
PPDS12.919.037.854.6
Spod-GT (ours)38.358.068.771.9

1000 clients, synthetic, pip_i and p^ij\hat p_{ij} from U(0, 1) (∥∇F(xˉ)∥2\Vert \nabla F(\bar x) \Vert^2).

Heterogeneous data, σh2=0.2\sigma_h^2 = 0.2

Methodτ=7⋅104\tau = 7 \cdot 10^4τ=2⋅105\tau = 2 \cdot 10^5τ=7⋅105\tau = 7 \cdot 10^5τ=6.5⋅106\tau = 6.5 \cdot 10^6
PPDS8.8e-27.3e-24.8e-22.8e-3
Spod-GT (ours)5.3e-33.3e-42.0e-51.6e-5

Homogeneous data, σh2=0\sigma_h^2 = 0

Methodτ=7⋅104\tau = 7 \cdot 10^4τ=2⋅105\tau = 2 \cdot 10^5τ=7⋅105\tau = 7 \cdot 10^5τ=6.5⋅106\tau = 6.5 \cdot 10^6
PPDS9.1e-25.0e-21.7e-22.8e-4
Spod-GT (ours)8.4e-31.0e-33.9e-52.9e-6

Our design goal is fast convergence under heterogeneous, sporadic resources. With 100 clients, under the Beta(0.5, 0.5) resources of the initial submission, and on the 1000-client problem, Spod-GT is more accurate than PPDS at every budget, with IID and non-IID data. PPDS samples clients regardless of their resources, so slow clients compute as often as fast ones and every iteration waits for them, whereas Spod-GT lets each client and link operate at its own rate. The revision adds PPDS to the related work (Sec. 2) and this comparison as App. K.6. We further note that the analysis of PPDS covers convex local losses with a strongly convex global objective, whereas Spod-GT covers non-convex losses.

W2/Q2: Communication conditions

We would like to clarify that the thresholds r^A\hat r_A, r^B\hat r_B and r^′\hat r' are sufficient, not necessary, conditions for convergence. As is standard in the analysis of decentralized methods over directed graphs (e.g., Pu et al., 2020, Nedić et al., 2025), the contraction constants are bounded through the Cauchy-Schwarz, Jensen's and Young's inequalities and worst-case bounds on the Perron vectors, which makes closed-form conditions rather conservative. Spod-GT converges well outside these thresholds, as in all our experiments. App. J of the revision now states this explicitly.

We also now add an analysis with the exact constants (new Appendix J), which keeps the submitted analysis and removes these worst-case steps, each constant being computable from (A,B,p^)(A, B, \hat p). The changes are as follows.

  • Exact constants (Lemma J.1). ρ^A\hat\rho_A and ρ^B\hat\rho_B are the exact contraction factors of the expected matrices A^\hat A and B^\hat B in the ϕ^\hat\phi- and π^\hat\pi-weighted norms, ρ^0,A\hat\rho_{0,A} and ρ^0,B\hat\rho_{0,B} are the exact normalized variances of the random matrices A^(k)\hat A^{(k)} and B^(k)\hat B^{(k)} around them, and ρ~A\tilde\rho_A, ρ~B\tilde\rho_B and ρ^1,B\hat\rho_{1,B} are the exact one-step factors of the random matrices. Each is at most its closed form in the initial submission, and ρ^0,B≤(m−1)(1+max⁡π^i/min⁡π^i)max⁡bij2p^ij(1−p^ij)\hat\rho_{0,B} \le (m-1)(1 + \max \hat\pi_i / \min \hat\pi_i) \max b_{ij}^2 \hat p_{ij} (1-\hat p_{ij}). Hence, the dependence of Thm. 4.9 on p^ij(1−p^ij)\hat p_{ij} (1-\hat p_{ij}) is unchanged.
  • Model mixing (Lemma J.3 (i)). The random matrix A^(k)\hat A^{(k)} contracts in one step with ρ~A≤min⁡{ρ^A+ρ^0,A,1−ϑA}<1\tilde\rho_A \le \min\lbrace \hat\rho_A + \hat\rho_{0,A}, 1 - \vartheta_A \rbrace < 1 for every p^∈(0,1]\hat p \in (0, 1]. The gap ϑA\vartheta_A comes from taking the expectation of the Jensen gap over the link draws, so it depends on E[a^ii(k)a^ij(k)]=aijp^ij(1−aij−∑ℓ≠i,jaiℓp^iℓ)≥aiiaijp^ij\mathbb{E}[\hat a_{ii}^{(k)} \hat a_{ij}^{(k)}] = a_{ij} \hat p_{ij} (1 - a_{ij} - \sum_{\ell \neq i, j} a_{i\ell} \hat p_{i\ell}) \ge a_{ii} a_{ij} \hat p_{ij}, and rarely active links still contribute through p^ij\hat p_{ij}. A version of the dispersion bound of Nguyen et al. (2025) weighted by the Perron vector (Lemma J.2) turns this gap into a contraction.
  • Tracking mixing (Lemma J.3 (ii)). The expected matrix contracts with ρ^B≤1−ϑB<1\hat\rho_B \le 1 - \vartheta_B < 1, and the random matrix B^(k)\hat B^{(k)} contracts in one step with ρ~B=ρ^B+ρ^0,B\tilde\rho_B = \hat\rho_B + \hat\rho_{0,B}. Splitting the trackers into a part with zero column sums and their mean, which B^(k)\hat B^{(k)} preserves, gives the sharper factor ρ^1,B≤ρ~B\hat\rho_{1,B} \le \tilde\rho_B, and when ρ^1,B<1\hat\rho_{1,B} < 1, the bound holds with (1+ρ^1,B)/2<1(1 + \hat\rho_{1,B})/2 < 1. The only condition on p^\hat p is therefore min⁡(ρ~B,ρ^1,B)<1\min(\tilde\rho_B, \hat\rho_{1,B}) < 1.
  • Loss descent (Prop. J.4). The condition p^≥1−r^′\hat p \ge 1 - \hat r' of Prop. 4.8 came from applying Young's inequality to the inner product between ∇F(xˉ)\nabla F(\bar x) and the tracker step with B^(k)\hat B^{(k)} before averaging over the link draws. Taking this expectation first replaces B^(k)\hat B^{(k)} by B^\hat B, so ρ^0,B\hat\rho_{0,B} disappears from this term. Centering the weights ϕ^iηi\hat\phi_i \eta_i then leaves a condition on the learning rates instead of p^\hat p, which holds for any p^\hat p when ϕ^iηi\hat\phi_i \eta_i is the same for all clients.
  • Theorem. Thm. 4.9 then holds with min⁡(ρ~B,ρ^1,B)<1\min(\tilde\rho_B, \hat\rho_{1,B}) < 1 as its only condition on p^\hat p, and every term keeps its order.

Hence, every p^\hat p that met the old conditions meets the new ones. On the reviewer's example (complete graph with m=10m = 10 with uniform weights aij=bij=1/ma_{ij} = b_{ij} = 1/m), we now get ρ~A=(1−p^)2+2p^(1−p^)/m\tilde\rho_A = (1-\hat p)^2 + 2\hat p(1-\hat p)/m and ρ~B=(1−p^)2+2(m−1)p^(1−p^)/m2\tilde\rho_B = (1-\hat p)^2 + 2(m-1)\hat p(1-\hat p)/m^2, both below 1 as intended for every p^∈(0,1]\hat p \in (0, 1] (e.g., 0.91 at p^=0.05\hat p = 0.05).

We note that what the above exact analysis gives up is interpretability. Specifically, the closed forms of the initial submission show explicitly how the contraction factors depend on the mixing weights, the graph diameter D(G)D(G), the edge-utility K(G)K(G) and p^\hat p. The above exact constants are instead defined by maximization problems over XX and YY, i.e., generalized eigenvalue problems in (A,B,p^)(A, B, \hat p). They are tighter and can be computed for any given network, but they no longer give a formula for how the contraction factors grow as p^\hat p decreases, or how this effect depends on mm and the graph. Likewise, the learning-rate condition of Prop. J.4 depends on the Perron vector ϕ^\hat\phi and is only explicit when ϕ^iηi\hat\phi_i \eta_i is the same for all clients.

W3/Q3: Delay metric and G-Push-Pull

Spod-GT is the most accurate method under both the initial submission's averaged delay and a new wall-clock delay, and its margin grows under the latter. The initial submission's averaged delay τˉ\bar\tau is the average time a client spends on computation and communication per iteration, time it cannot use for anything else. We chose it to show how letting each client participate in proportion to its resources reduces this time across the network. The new parallel delay τ\tau measures the actual wall-clock delay of each iteration. To compute the parallel delay, we consider that the clients and links run in parallel, and an iteration ends when the slowest active client finishes, which results in

τ(k)=max⁡i[vi(k)pi+2max⁡j∈Niinv^ij(k)p^ij],τtotal(K)=∑k=0K−1τ(k)\tau^{(k)} = \max_{i} \Big[ \frac{v_i^{(k)}}{p_i} + 2 \max_{j \in \mathcal{N}_i^{\mathrm{in}}} \frac{\hat v_{ij}^{(k)}}{\hat p_{ij}} \Big], \qquad \tau_{\mathrm{total}}^{(K)} = \sum_{k=0}^{K-1} \tau^{(k)}

The factor 2 accounts for the two vectors xjx_j and yjy_j that each active link carries. For the same reason, the initial submission's averaged delay τˉtotal=τˉtrans,in+τˉproc+τˉtrans,out\bar\tau_{\mathrm{total}} = \bar\tau_{\mathrm{trans,in}} + \bar\tau_{\mathrm{proc}} + \bar\tau_{\mathrm{trans,out}} has two transmission terms, one for incoming and one for outgoing messages. The revision defines τ\tau in App. K.4 and reports both metrics in App. K.4 and K.5.

Spod-GT obtains a better performance gain under the parallel delay metric. This is mainly because every baseline waits in each iteration for all of its clients, all of its links, or both, while Spod-GT waits only for those that are active. Against the second-best method, G-Push-Pull, our Spod-GT's lead grows under τ\tau at every budget, on FMNIST from 2.4 and 0.7 points under τˉ\bar\tau to 2.7 and 0.9 points under τ\tau (table below), and on FEMNIST from 5.1, 5.4, 2.7 and 1.4 points to 7.2, 7.7, 5.2 and 2.6 points (App. K.5).

FMNIST, 100 clients, IID data, both delay metrics (accuracy %).

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4τ=2⋅104\tau = 2 \cdot 10^4τ=7⋅105\tau = 7 \cdot 10^5
AB/Push-Pull67.181.136.375.1
G-Push-Pull71.282.469.082.0
K-GT67.778.452.677.1
Sporadic K-GT64.279.926.772.3
Spod-GT (ours)73.683.171.782.9

Further, we would like to mention that the added G-Push-Pull baseline is Spod-GT with computation sporadicity switched off. Every client computes in every iteration, and each link is active with probability p^ij\hat p_{ij}. The baseline follows the idea of Algorithm 2 of Pu et al. (2020), randomly activated push–pull communication, but under our link model. Their Algorithm 2 wakes one agent per iteration, which pushes to at most one of its out-neighbors, and only the agents involved update their trackers. We instead activate all links independently, so that the comparison isolates the effect of sporadic computation. The revision states this difference in Sec. 5.


We appreciate your time and effort in reviewing our paper. We would be happy to address any remaining questions or concerns the reviewer might have.

Reviewer_PC3wOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a unified framework that integrates two lines of research previously addressing distinct challenges in decentralized federated learning (DFL) and introduces a Sporadic Gradient Tracking (Spod-GT) algorithm. Under a relaxed gradient diversity assumption, the paper provides a rigorous convergence analysis of the proposed method. Numerical experiments on image classification datasets demonstrate the effectiveness of Spod-GT compared with well-established gradient tracking baselines.

Critical strengths
  1. By introducing client-specific gradient computation indicators and communication link activation indicators, this paper allows different clients to perform gradient computations at different frequencies while supporting heterogeneous and asymmetric communication frequencies across different links.

  2. Under a relaxed gradient diversity assumption, this paper provides a systematic convergence analysis for non-convex optimization.

  3. This paper establishes constraints on client gradient computation probabilities, communication probabilities, and learning rate heterogeneity, and relates these constraints to gradient diversity and the spectral properties of directed graphs.

  4. By comparing the proposed method with several representative gradient tracking algorithms, including G-Push-Pull and K-GT, this paper validates the effectiveness of the joint sporadic computation and communication mechanism.

Critical weaknesses
  1. This paper assumes that client gradient computations and communication link activations follow mutually independent Bernoulli distributions with fixed, nonzero participation probabilities. However, the theoretical analysis does not directly accommodate participation mechanisms with temporal dependencies and fluctuating resource availability.

  2. The authors first generate an undirected random geometric graph and then convert all edges into bidirectional connections with heterogeneous weights to construct the directed network used in their experiments. However, this experimental setup does not adequately cover directed topologies containing strictly unidirectional communication links.

  3. This paper controls resource participation frequencies through client computation probabilities pip_i and communication link probabilities p^ij\hat{p}_{ij}. However, the main experiments rely on randomly generated participation probabilities and do not sufficiently investigate how to determine optimal probability configurations under practical resource constraints.

Questions for authors
  1. This paper assumes that client gradient computations and communication link activations follow mutually independent Bernoulli distributions with fixed, nonzero participation probabilities. However, the theoretical analysis does not directly accommodate participation mechanisms with temporal dependencies and fluctuating resource availability.

  2. The authors first generate an undirected random geometric graph and then convert all edges into bidirectional connections with heterogeneous weights to construct the directed network used in their experiments. However, this experimental setup does not adequately cover directed topologies containing strictly unidirectional communication links.

  3. This paper controls resource participation frequencies through client computation probabilities pip_i and communication link probabilities p^ij\hat{p}_{ij}. However, the main experiments rely on randomly generated participation probabilities and do not sufficiently investigate how to determine optimal probability configurations under practical resource constraints.

  4. In Figure 3(c), the number of clients is increased from 10 to 50, but this scale remains considerably smaller than the hundreds or thousands of clients that may be involved in real-world large-scale federated learning systems.

5 comments

We thank the reviewer for the positive assessment and the concrete suggestions.

W1/Q1: Temporal dependence

We would like to kindly clarify that, in this work, our focus is sporadic computation and communication over static directed networks, a setting that had not been studied even without temporal dependence. As a result, the paper does not claim to handle time-varying or temporally correlated participation. We note that, even in the static setting, sporadicity raises two hurdles, described as Theoretical Challenges 1 and 2 (Sec. 4.1 and 4.2). The per-iteration matrices A^(k)\hat A^{(k)} and B^(k)\hat B^{(k)} are not strongly connected, so they lose the spectral properties of their expectations, and the trackers follow a masked average of the gradients computed in each iteration. Handling these two effects is the core innovation of our proofs.

Nevertheless, we now show that Spod-GT still works with temporally correlated participation (new App. K.7). In this setting, each client's computation and each link's activation follow a two-state Markov chain, P(active at k+1)=λ⋅1[active at k]+(1−λ)pP(\text{active at } k+1) = \lambda \cdot \mathbf{1}[\text{active at } k] + (1-\lambda) p, which keeps the long-run rates pip_i and p^ij\hat p_{ij} but makes on/off periods 1/(1−λ)1/(1-\lambda) times longer (λ=0\lambda = 0 is the independent case).

FMNIST, 100 clients, non-IID data, Markov participation (accuracy %).

λ=0\lambda = 0

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull63.181.1
G-Push-Pull68.282.3
K-GT43.073.5
Sporadic K-GT59.379.0
Spod-GT (ours)69.682.4

λ=0.8\lambda = 0.8

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull63.680.9
G-Push-Pull67.382.0
K-GT43.373.7
Sporadic K-GT58.478.8
Spod-GT (ours)68.982.1

λ=0.95\lambda = 0.95

Methodτˉ=103\bar\tau = 10^3τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull62.480.9
G-Push-Pull63.481.5
K-GT42.073.6
Sporadic K-GT55.378.6
Spod-GT (ours)64.381.4

As shown in the above tables, Spod-GT remains the most accurate method early in training at every λ\lambda, and within 0.1 points of the best at τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4. With 20× longer on/off periods (λ=0.95\lambda = 0.95), it loses about 5 points early in training and 1 point at τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4. AB/Push-Pull and K-GT do not depend on λ\lambda, since all their clients are always active or follow a fixed schedule, and their small differences come from the random draws. A full analysis of such dynamic network settings along with its theory is left as future work, which we now mention in the Conclusion of the revision.

W2/Q2: Strictly unidirectional links

Spod-GT already treats every link as one-way. In the initial submission, the support graph was symmetric, but the two directions of an edge were separate links, each with its own mixing weight (bij≠bji)(b_{ij} \neq b_{ji}) and its own activation probability (p^ij≠p^ji)(\hat p_{ij} \neq \hat p_{ji}), activated independently. All new experiments of the revision go further and run on strictly directed graphs, where Spod-GT keeps its advantage. We use a directed geometric graph with heterogeneous transmit power. Client ii draws a transmit radius rir_i from U(0.5rˉ,1.5rˉ)U(0.5 \bar r, 1.5 \bar r), and link i→ji \to j exists if and only if dist(i,j)≤ri\mathrm{dist}(i, j) \le r_i. We redraw until the graph is strongly connected, with no planted ring (App. K.4). On this graph, we train a linear SVM on FMNIST with step size 0.01 for all methods, pip_i and p^ij\hat p_{ij} drawn from U(0, 1).

FMNIST, 100 clients, directed geometric graph (accuracy %).

IID data

Methodτˉ=103\bar\tau = 10^3τˉ=3⋅103\bar\tau = 3 \cdot 10^3τˉ=104\bar\tau = 10^4τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull67.173.078.581.1
G-Push-Pull71.276.780.382.4
K-GT67.772.877.778.4
Sporadic K-GT64.270.677.379.9
Spod-GT (ours)73.678.681.383.1

Non-IID data

Methodτˉ=103\bar\tau = 10^3τˉ=3⋅103\bar\tau = 3 \cdot 10^3τˉ=104\bar\tau = 10^4τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull63.172.178.381.1
G-Push-Pull68.275.880.182.3
K-GT43.055.668.073.5
Sporadic K-GT59.368.275.979.0
Spod-GT (ours)69.676.180.082.4

As shown in the tables above, Spod-GT is the most accurate method at every budget with IID data. With non-IID data, it is ahead of G-Push-Pull or within 0.1 points of it, and ahead of the other baselines.

W3/Q3: Choosing the probabilities

The probabilities pip_i and p^ij\hat p_{ij} describe each client's resources and are set before training. Drawing them at random in our experiments only models heterogeneity and is not a step of Spod-GT. In the initial submission, we essentially draw the processing rate cic_i of each client and the transmission rate c^ij\hat c_{ij} of each link from Beta(0.5, 0.5) and set pi=cip_i = c_i and p^ij=c^ij\hat p_{ij} = \hat c_{ij}, so that a gradient of client ii takes time 1/ci1/c_i and a message over link (i,j)(i, j) takes time 1/c^ij1/\hat c_{ij} (App. B.7). The new experiments draw cic_i and c^ij\hat c_{ij} from U(0, 1) instead, a milder heterogeneity than Beta(0.5, 0.5), which puts much of its mass near 0, so they also show that Spod-GT's advantage does not rely on a few extremely slow clients or links.

In a real deployment, one measures cic_i and c^ij\hat c_{ij} and computes pip_i and p^ij\hat p_{ij} from them in a preprocessing step. For example, two simple rules would be (i) proportional to processing and transmission capability as above (pi=ci/max⁡jcjp_i = c_i / \max_j c_j and p^ij=c^ij/max⁡rℓc^rℓ\hat p_{ij} = \hat c_{ij} / \max_{r\ell} \hat c_{r\ell} in general), and (ii) opportunistic, where each client or link acts/participates whenever it can, so pi/p^ijp_i/\hat p_{ij} capture their average availability.

Q4: Scale

We added three large-scale simulation settings (App. K.4 and K.5 of the revision), namely FMNIST with 100 clients (tables in W2/Q2 above), a synthetic non-convex problem with 1000 clients, and FEMNIST with 100 clients. In all three, Spod-GT keeps its advantage. It is the most accurate method at almost every budget on FMNIST and at every budget on FEMNIST, and it reaches the lowest ∥∇F(xˉ)∥2\Vert \nabla F(\bar x) \Vert^2 with 1000 clients until it levels off at the neighborhood of Thm. 4.9.

1000 clients, synthetic non-convex logistic regression (benchmark of Alghunaim & Yuan, 2022, with d=20d = 20, 200 samples per client and full-batch gradients), each method tuned over step sizes {0.01, 0.03, 0.1}. Entries are ∥∇F(xˉ)∥2\Vert \nabla F(\bar x) \Vert^2.

Heterogeneous data, σh2=0.2\sigma_h^2 = 0.2

Methodτˉ=6⋅102\bar\tau = 6 \cdot 10^2τˉ=2⋅103\bar\tau = 2 \cdot 10^3τˉ=6⋅103\bar\tau = 6 \cdot 10^3τˉ=5.9⋅104\bar\tau = 5.9 \cdot 10^4
AB/Push-Pull5.4e-21.6e-22.5e-34.0e-9
G-Push-Pull5.2e-21.6e-22.5e-35.4e-9
K-GT8.1e-25.5e-22.1e-21.1e-4
Sporadic K-GT8.4e-25.7e-22.6e-22.5e-4
Spod-GT (ours)5.8e-31.7e-42.0e-51.6e-5

Homogeneous data, σh2=0\sigma_h^2 = 0

Methodτˉ=6⋅102\bar\tau = 6 \cdot 10^2τˉ=2⋅103\bar\tau = 2 \cdot 10^3τˉ=6⋅103\bar\tau = 6 \cdot 10^3τˉ=5.9⋅104\bar\tau = 5.9 \cdot 10^4
AB/Push-Pull7.0e-22.3e-24.8e-32.7e-6
G-Push-Pull2.4e-23.6e-33.2e-46.4e-11
K-GT7.2e-23.0e-26.5e-31.1e-5
Sporadic K-GT7.8e-22.9e-27.4e-32.3e-5
Spod-GT (ours)9.1e-36.1e-43.1e-52.9e-6

Specifically, as shown in the above tables, Spod-GT has the lowest ∥∇F(xˉ)∥2\Vert \nabla F(\bar x) \Vert^2 of all methods up to τˉ=6⋅103\bar\tau = 6 \cdot 10^3. It then levels off at the (1−pi)δ0,i2(1-p_i)\delta_{0,i}^2 neighborhood of Thm. 4.9, which shrinks with the data heterogeneity and vanishes when pi=1−O(1/K)p_i = 1 - O(1/K) (Cor. 4.10).

FEMNIST, 100 clients. We added FEMNIST from LEAF (App. K.5 of the revision) with its natural federated data partition, using 100 randomly chosen clients. The images of each client are split 80/20 into training and test data, and the test data of all clients are pooled. We train a linear SVM over the 62 classes with step size 0.01 for all methods, on the directed geometric graph of App. K.4 with pip_i and p^ij\hat p_{ij} drawn from U(0, 1).

FEMNIST, 100 clients (accuracy %).

Methodτˉ=103\bar\tau = 10^3τˉ=3⋅103\bar\tau = 3 \cdot 10^3τˉ=104\bar\tau = 10^4τˉ=2.9⋅104\bar\tau = 2.9 \cdot 10^4
AB/Push-Pull21.832.144.951.5
G-Push-Pull29.840.350.055.1
K-GT28.337.848.052.4
Sporadic K-GT18.728.442.149.6
Spod-GT (ours)34.945.752.756.5

As shown in the Table above, Spod-GT is the most accurate method at every budget.


We appreciate your time and effort in reviewing our paper. We would be happy to address any remaining questions or concerns the reviewer might have.

Dear Reviewer PC3w,

Thank you again for your time and constructive feedback. Have we addressed your concerns? We would appreciate the opportunity to further clarify any remaining perceived issues as you finalize your assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.