- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies communication efficiency in nonconvex agnostic federated learning (AFL). The authors propose AFL-BR, which updates the dual weights using KL-based online mirror ascent with blockwise restarts, reducing the dependence of synchronization rounds on the number of workers from polynomial to logarithmic order. Building on AFL-BR, the authors further develop AFL-COM by incorporating bidirectional compression with error feedback applied to dual-weighted gradients. They establish convergence guarantees under general -approximate compressors and obtain a sharper dependence on for additive-and-idempotent compressors with shared randomness. Experiments demonstrate the improved synchronization efficiency of AFL-BR and further communication savings achieved by AFL-COM.
Critical strengths
-
The paper provides substantial theoretical improvements for nonconvex AFL. AFL-BR reduces the -dependence of synchronization rounds from polynomial to logarithmic order, and AFL-COM reduces total communication complexity with convergence guarantees under general compressors and sharper results under additional compressor properties and shared randomness.
-
The theoretical analysis is well-supported by detailed proofs. The authors also revisit the convergence guarantees of SGDA and DRFA, making their hidden -dependence explicit.
Critical weaknesses
The theoretical analysis relies on relatively strong assumptions, including uniformly bounded local gradients (Assumption 3) and sub-Gaussian stochastic loss noise (Assumption 4). The strong assumptions may limit the generality of the theoretical guarantees.
Questions for authors
-
The convergence analysis relies on uniformly bounded local gradients (Assumption 3) and sub-Gaussian stochastic loss noise (Assumption 4). Could the authors clarify why these assumptions are needed in the theoretical analysis and discuss whether there are potential ways to relax either of them?
-
Both AFL-BR and AFL-COM consider full participation. Could the authors briefly discuss how partial participation may affect the convergence guarantees of the proposed methods?
2 comments
Thank you for the detailed response. I maintain the positive score.
We thank the reviewer for the constructive review and positive assessment of our paper. We have uploaded our revised paper, with the changes highlighted in blue for ease of reference.
Q1. The bounded-gradient and sub-Gaussian loss-noise assumptions may limit the generality of the guarantees. Why are these assumptions needed, and whether there are potential ways to relax either of them?
Response. We thank the reviewer for raising this point. These assumptions serve different purposes in our convergence analysis.
For the primal variable w, Assumption 3 ensures that local risks are Lipschitz in the model, allowing us to control the effect of changes in the worst-case worker distribution as the model evolves. It also controls the accumulated error-feedback residuals. For the dual variable q, the sub-Gaussian condition in Assumption 4 controls stochastic loss fluctuations in the KL-based mirror-ascent analysis, allowing us to bound the stochastic terms without requiring uniformly bounded losses in the full-participation setting.
These assumptions may be relaxed, but typically at the cost of additional structural conditions or algorithmic modifications. For w, possible alternatives to bounded gradients include strong convexity with sample-wise smoothness (Nguyen et al., 2018) or expected smoothness (Khaled and Richtárik, 2023). For q, robust or clipped estimators offer a potential route to handling heavy-tailed loss noise under weaker moment assumptions (Liu et al., 2024). Establishing comparable guarantees under these relaxations remains an interesting direction for future work.
Q2. Both AFL-BR and AFL-COM consider full participation. Could the authors briefly discuss how partial participation may affect the convergence guarantees of the proposed methods?
Response. We thank the reviewer for this question. We have added partial-participation algorithms for both methods in Algorithm 3 (Appendix G.1) and established their convergence in Theorem 4 (Appendix G.2) under an additional bounded-local-risk assumption. Partial participation introduces additional sampling noise whose variance depends on the magnitudes of local expected losses, which Assumption 4 alone does not control. We therefore introduce bounded local expected losses (Assumption 5), which is also used by Deng et al., (2020).
Empirically, we have added partial-participation experiments in Figure 8 of the revised manuscript. With 30 Fashion-MNIST workers, AFL-Com(T) achieves 70.51 ± 1.90% accuracy at 50% participation versus 71.86 ± 1.40% at full participation, while reducing communication by 30.18%. At 16.7% participation, it achieves 68.54 ± 3.47% with a 71.87% communication reduction. These results provide empirical evidence that our methods support partial participation, maintaining competitive worst-worker accuracy while substantially reducing communication.
Yuyang Deng, Mohammad Mahdi Kamani, Mehrdad Mahdavi. Distributionally Robust Federated Averaging. NeurIPS 2020.
Lam Nguyen, PHUONG HA NGUYEN, Marten Dijk, Peter Richtarik, Katya Scheinberg, Martin Takac. SGD and Hogwild! Convergence Without the Bounded Gradients Assumption. ICML 2018.
Ahmed Khaled, Peter Richtárik. Better Theory for SGD in the Nonconvex World. TMLR 2023.
Langqi Liu, Yibo Wang, Lijun Zhang. High-Probability Bound for Non-Smooth Non-Convex Stochastic Optimization with Heavy Tails. ICML 2024.