Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reduction

Summary

This work establishes a general convergence analysis for a heterogeneous federated learning (FL) algorithm that trains a shared global model using a sequence of time-varying and client-dependent local models. In particular, this work establishes sufficient conditions for the convergence of such a heterogeneous FL algorithm to the neighborhood of a stationary point of the standard FL. Based on the theoretical results, the authors propose practical suggestions for designing heterogeneous FL algorithms and conduct thorough experiments to support their claims.

Strengths

Overall, this paper is well-written. It is the first to provide a general convergence result to the neighborhood of a stationary point for the standard federated learning (FL) framework, specifically for a heterogeneous FL algorithm that trains a shared global model through a sequence of time-varying and client-dependent local models. This result provides a convergence guarantee for several previously proposed heterogeneous FL algorithms. The optimality gap in the result depends on two important parameters: the minimum coverage index and the model reduction noise. These parameters offer valuable insights for designing practical heterogeneous FL algorithms. The experimental results align well with the theoretical findings presented in the paper.

Weaknesses

The last term on the right-hand side of the inequality in Theorem 1 (and similarly for Theorem 2) corresponds to the average of the norms of the global parameters encountered during the optimization process. This term is not necessarily small in a straightforward manner.

Questions

Can the authors provide additional discussions regarding the last term in Theorem 1 (and Theorem 2)? Specifically, it would be helpful to explore whether this term is tight or under what circumstances it can be considered small.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

N/A

Summary

This paper studies federated learning with heterogeneous client models and non-iid client data. By assuming that the client models are pruned versions of a common global model and using the notion of minimum covering index, the paper provides the convergence of FedAvg under client model pruning. Theoretical results show that pruning techniques that more evenly update the parameters and result in smaller model distortion are preferable to aggressive pruning. Such result is also verified through the numerical results on MNIST and Cifar-10, and Cifar-100 datasets.

Strengths

Novelty: this paper provides a first convergence analysis to FedAvg with model pruning. The theoretical proof is sound and clear. Clarity: the paper thoroughly discusses the convergence result in theorems 1 and 2 and verifies the results through numerical experiments.

Weaknesses

1. Term $E\Vert \theta_q\Vert^2$ in the bound. This term appears in all theorems and lemmas in the main paper. However, it is unclear how large this term can be. Neither theoretical discussion nor numerical justification of this term is provided. This undermines the strength of the theoretical results. 2. The connection between the theorem to the general convergence result of FedAvg under the same assumption. When $\delta = 0, \Gamma_{min} = T$, the convergence should recover the rate of standard FedAvg. However, such a discussion is missing, weakening the paper's clarity. 3. The connection between the proof of pruning and lossy compression. Assumption 2 takes the standard assumption of model compression in compressed FL (e.g., [19, 21, 22]). Yet there is a critical difference in the minimum covering index. The connection and difference between the proof technique should be discussed.

Questions

Please address the above weaknesses.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The authors have discussed the limitation of the paper, that partial client participation is not considered, and how the theoretical result guides the design of an optimal model pruning strategy is also limited.

Summary

This paper focuses on the cross-device federated learning setting. The authors introduce a general theoretical framework for analyzing FedAvg with masks on local pruned models. This analysis is particularly valuable in establishing the convergence of federated schemes when the global model is distributed across multiple edge clients. Furthermore, the paper includes numerical illustrations of their algorithm, providing practical insights on its performance.

Strengths

* The paper is well-written and easy to understand, but with few points that might be improved (see "Questions" part). * The paper conducts a thorough theoretical investigation on federated learning with reduced-size models. Specifically, the authors provide novel tools to study the convergence of FL pruned models.

Weaknesses

* Although interesting, some parts may seem to have been rushed. For example, assumptions and lemmas should be referred with ref{}. Further, I also spotted a few errors on the supplement, even though I haven't read the supplementary in detail. It's important to review and correct these typos.

Questions

The article is interesting, could you address the following points so that I can raise my score? * It is unclear whether $\Gamma_q^{(i)}$ is defined or if it refers to $N_{q}^{(i)}$ mentioned on line 177. Similarly, does $\Gamma^*$ denote the same quantity as $\Gamma_{min}$? * The proposed update in the equation on line 134 is not exactly the same implemented in the "Update.py" script. I think the mask is not applied to the gradient. * I haven't looked at the supplementary paper, but it seems to me that an expectation is missing on Eq.(20). * Is it necessary to use $\delta<1$ in assumption 2? Since I don't see $1/(1-\delta)$ in your bounds, I wonder if this constraint is useful. **Requested Changes:** * Line 59: "will it converge" inside Figure 1 legend. * Line 75: client is denoted by $i$, then latter by $n$ at the end of page 2. * Line 95: "models are to share". * Lines 108: "works like Hermes can". * Definition of $I_0$ in Theorem 1 and Theorem 2 is different, there is maybe an additional $\delta^2$. * Some punctuation is missing, e.g., Eq. (9). * Conclusion seems little heavy.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors did not address the potential negative societal implications of their research, but this does not seem critical for this particular theoretical and numerical study.

Summary

In this work, the authors provide a general theoretical framework to analyze the convergence of Federated training schemes conducted over local models of heterogeneous network structures. Such structures can usually be obtained through different model reduction methods, such as model pruning/sparsification or model extraction. The proposed framework introduces the minimum covering index concept to conduct the analysis, representing the number of local models concurrently updating the same set of parameter indices. The paper is well written, but a couple of clarifications are necessary.

Strengths

Very well-written paper with clear objectives and contributions. Generalized framework to encapsulate different model reduction algorithms. The introduction of the minimum coverage index concept and its interplay with model reduction noise can lead to very promising and interesting insights.

Weaknesses

Further elaboration is needed on terms and concepts used during the theoretical analysis. Empirical evaluation needs improvement.

Questions

From my understanding, your framework seems to consider reduced model structures when these structures are obtained when the global model is reduced (pruned). Will your analysis hold even in the case of local model reduction, i.e., client-side reduction, not server-side? Will the model reduction noise (assumption 2) and bounded gradient (assumption 3) still hold? Your analysis shows that local model training is performed over the entire network. How would that affect your analysis if you were to enforce training over the parameters of the reduced model (enforce masks during training)? The proof outline does not clarify how the mask is constructed. Is it always static, or can it be dynamically changing? In PruneFL, masks can periodically increase to accommodate model regrowth. Similarly, FedDST[1] performs local model regrowth with a fixed pruning degree during model communication. Analogously, FedSparsify[2] performs progressive model reduction (progressive sparsification), where the global or local model is progressively pruned. Can your framework capture such dynamic mask construction? Please expand your related work and discuss whether your framework can also accommodate such dynamic pruning approaches. The model settings through which the model reduction level is obtained in Table 1 are not clear. Can you please elaborate on what are the methods you used to perform the greedy pruning, pruning-optimized, static subnet subtraction, and homogeneous methods? Did you use structured or unstructured pruning? Random weight magnitude or based on magnitude? Can you report the noise reduction (percentage-wise) in the models learned at every model reduction level? Such an analysis could lead to key insights with respect to the index coverage vs. noise reduction tradeoff. Can your analysis be extended to activations and/or neuron pruning as part of your future work? Also, have you considered extending your framework for asynchronous federated settings? [1] Federated Dynamic Sparse Training: Computing Less, Communicating Less, Yet Learning Better Sameer Bibikar, Haris Vikalo, Zhangyang Wang, Xiaohan Chen. https://ojs.aaai.org/index.php/AAAI/article/view/20555/20314 [2] Federated Progressive Sparsification (Purge-Merge-Tune)+. Dimitris Stripelis, Umang Gupta, Greg Ver Steeg, Jose Luis Ambite. https://openreview.net/pdf?id=GLQqPTRrQMx

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No.