- 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
- What is the definition of the total delay in the numerical experiments? I'm wondering if the comparison w.r.t. is fair.
- 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
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 , where averages over the clients and the two transmission terms average over each client's incoming and outgoing links. The initial submission's averaged delay 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 measures the actual wall-clock delay of each iteration.
In particular, the revision adds a second metric, the parallel delay , 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.
The factor 2 accounts for the two vectors and that each active link carries. For the same reason, the initial submission's averaged delay has two transmission terms, one for incoming and one for outgoing messages.
Both metrics are fair: every method pays the same unit costs, per gradient and per message, through its own indicators, and no method is charged for work it does not do. Nevertheless, they capture different things: the total resources spent by the clients and the links in the network and 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 at every budget, on FMNIST from 2.4 and 0.7 points under to 2.7 and 0.9 points under (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 | ||||
|---|---|---|---|---|
| AB/Push-Pull | 67.1 | 81.1 | 36.3 | 75.1 |
| G-Push-Pull | 71.2 | 82.4 | 69.0 | 82.0 |
| K-GT | 67.7 | 78.4 | 52.6 | 77.1 |
| Sporadic K-GT | 64.2 | 79.9 | 26.7 | 72.3 |
| Spod-GT (ours) | 73.6 | 83.1 | 71.7 | 82.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 , 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.
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 pi and 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 τˉ and the parallel delay τ defined in Q1 below.
FEMNIST, 100 clients, both delay metrics (accuracy %).
Averaged delay τˉ
Parallel delay τ
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) and 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−λ)p, which keeps the long-run rates pi and p^ij but makes on/off periods 1/(1−λ) times longer. λ=0 is the independent case.
FMNIST, 100 clients, non-IID data, Markov participation (accuracy %).
λ=0
λ=0.8
λ=0.95
As shown in the above tables, Spod-GT remains the most accurate method early in training at every λ, and within 0.1 points of the best at τˉ=2.9⋅104. With 20× longer on/off periods (λ=0.95), it loses about 5 points early in training and 1 point at τˉ=2.9⋅104. AB/Push-Pull and K-GT do not depend on λ, 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.