REVIEW 3 major objections 5 minor 31 references
Convergence of Agnostic Federated Averaging
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read This paper proves that agnostic Federated Averaging converges at the standard $\mathcal{O}(1/\sqrt{T})$ rate for convex losses even when client participation is unknown, non-uniform, and random.
desk verdict A useful but incomplete characterization of the objective of agnostic FedAvg; the convergence proof is plausible, but the participation assumption is narrower than the abstract suggests. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the survival distribution $\{p_i\}_{i=1}^N$ together with the sample-to-model inequality of Lemma 4. The distribution summarizes a two-stage random experiment: first an availability subset $S_t$ is drawn from $q$, then one client is drawn uniformly from $S_t$, so $p_i$ measures how often client $i$ would be the randomly selected representative of the available group. Lemma 4 shows $\mathbb{E}[\lVert \hat{\theta}_t-\theta^*\rVert^2 \mid \mathcal{F}_{t-1}] \le \sum_{i=1}^N p_i \lVert \theta_i^{t-1}-\theta^*\rVert^2$, which is the bridge between the server's unweighted average and a weighted descent on the global objective. Composing this inequality with the per-client progress bounds of Lemmas 2 and 3 yields the recursive descent inequality that produces the $\mathcal{O}(1/\sqrt{T})$ rate.
What would settle it
Run Algorithm 1 on a convex problem with skewed, non-uniform availability while freezing all clients that are not selected for upload, so they perform no local SGD and do not receive the broadcast; if the expected suboptimality gap does not decrease at the claimed $\mathcal{O}(1/\sqrt{T})$ rate or diverges, the theorem's coverage of intermittent participation would be falsified for that regime.
Extended reading notes
Core claim
The central claim is that projected agnostic Federated Averaging (Algorithm 1) minimizes the global objective $\inf_{\theta\in\Theta}\sum_{i=1}^N p_i f_i(\theta)$, where $p_i = \sum_{A\subseteq[N], i\in A} q(A)/|A|$ is the chance that client $i$ is selected uniformly from a realized availability subset $A$, and $q$ is an arbitrary distribution over client subsets. Theorem 4 states that, for convex and possibly nonsmooth losses satisfying bounded-gradient and bounded-variance assumptions, the average of the server models over $T$ aggregation rounds has an expected suboptimality gap of order $\mathcal{O}(1/\sqrt{T})$ with step size $\eta = \Theta(1/\sqrt{TH})$. The proof turns the random subset aggregation into a deterministic $p_i$-weighted problem by way of Lemma 4, which bounds the squared error of the unweighted server average by the $p_i$-weighted sum of client squared errors.
Load-bearing premise
The proof assumes every client, whether or not it is selected for upload, performs all $H$ local SGD steps and resets its local copy to the server broadcast at every communication round; if non-selected clients are genuinely offline and frozen, the per-client recursion that powers the descent argument no longer holds.
Editorial extensions
If this is right
- A server needs no participation statistics: on convex problems, simply averaging the parameters of whichever clients are reachable achieves the standard $\mathcal{O}(1/\sqrt{T})$ error rate.
- The global objective is availability-weighted: each client's influence is set by how often and in what group sizes it is available, not by its dataset size or label diversity.
- The result covers random subset sizes at every round, so variable numbers of participating clients require no special handling or known sampling probabilities.
- Weighted aggregation using estimated participation weights can underperform the plain unweighted rule, and the paper's experiments show the gap widens as participation skew grows.
- The rate matches the usual $\mathcal{O}(1/\sqrt{T})$ of convex stochastic optimization, with the proof's constants absorbing the local steps $H$, the gradient bound $G$, and the Lipschitz constant $\ell$.
Reading between the lines
- The proof's broadcast-reset requirement implies a practical deployment constraint: clients absent at upload time must still be reachable for updates; scheduling background local updates for unavailable devices would keep agnostic FedAvg inside the theorem's scope.
- Because the implicit objective is availability-weighted, a fairness-oriented deployment could use the same $p_i$ model to quantify how much the global model favors frequent participants, a consequence the paper leaves undeveloped.
- The paper's results suggest that correcting participation bias should happen at the sampling-design stage rather than by post-hoc reweighting of aggregates, since the experiments show reweighting made things worse.
- A direct extension would vary the availability distribution over time (periodic, Markovian, or bursty) and test whether the same $p_i$-weighted objective and rate persist; the current analysis assumes i.i.d. subsets each round.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies agnostic Federated Averaging (Algorithm 1) under random, non-uniform, and unknown client availability. It defines marginal inclusion weights p_i via Eq. (2), shows in Lemma 4 that the server's unweighted averaging step satisfies a Jensen-type inequality against the p-weighted squared distance, and claims in Theorem 4 that agnostic FedAvg converges at O(1/sqrt(T)) for convex, possibly nonsmooth losses to the minimum of the p-weighted global objective (Eq. (3)). The paper also reports experiments on MNIST and a synthetic linear regression task comparing agnostic FedAvg with a weighted FedAvg variant. Full proofs of the central lemmas are deferred to a forthcoming submission, as stated in the note after the abstract.
Significance. If correct, this would be the first convergence guarantee for FedAvg under entirely unknown, non-uniform client participation, and the induced-objective perspective (the p_i weights arising from availability rather than from data importance) is a useful conceptual contribution. The proof of Lemma 4 is clear and self-contained, and the empirical comparison with weighted FedAvg is a meaningful sanity check. However, the central convergence proof is not included in the manuscript, and the stated assumptions do not match the advertised setting of intermittent participation as commonly understood, so the significance can only be assessed after a substantial revision that addresses the points below.
major comments (3)
- [Algorithm 1 and §3.3, Eqs. (7)–(8)] The convergence proof assumes that every client, including clients not in the availability set S_t, performs H local SGD steps and receives the server broadcast each round (Algorithm 1, lines 6 and 8–9). The equality θ_i^{(T−1)H} = \hat θ_{(T−1)H} used in Eq. (7) and the p_i-weighting in Eq. (6) depend on this. If “intermittent participation” is interpreted in the standard federated-learning sense—unavailable clients are offline and do not compute or receive the model—the theorem does not apply. The paper should either state explicitly that the result covers only the all-clients-update model and adjust the abstract and introduction accordingly, or extend the analysis to the case where only available clients update.
- [Lemma 2, Eq. (l1-(1))] The lemma states a per-client inequality using the global variance bound σ² = Σ_k p_k σ_k², but Assumption 2 provides only the per-client bound σ_i². Since σ² is a weighted average, it need not dominate each σ_i², so the inequality is not justified as written. The proof is deferred, so the reader cannot verify whether the intended statement uses σ_i² and later passes to σ² after weighting, or whether σ² is meant to be a uniform upper bound. This needs correction or clarification because this σ² term appears in the final rate expression (Eq. (9)).
- [§3 and Theorem 4] The main theorem relies on Lemma 2, Lemma 3, and the derivation of Eq. (7), none of which are proven in the manuscript; the note after the abstract says full proofs are deferred. For a paper whose central claim is a convergence guarantee, this is a load-bearing omission: the reader cannot check the correctness of the descent inequality, the coupling argument, or the final rate. The manuscript should include complete proofs of these steps, or clearly repackage the claim as a proof sketch with the full proof provided in an appendix or companion document.
minor comments (5)
- [§3.3, Eq. (7)] The derivation refers to “Lemma 3.1”, but the correct reference appears to be Corollary 1 (Local Value Divergence) rather than Lemma 3. Please fix the cross-reference.
- [§4] The text says “discrepacy” in the second paragraph; it should be “discrepancy”.
- [§4] The implementation details are said to be available in an accompanying GitHub repository, but no URL is provided.
- [§2, Eq. (4)] The term “Bayesian interpretation” is a slight misnomer; the expression is simply the law of total probability. Consider rephrasing to avoid confusion.
- [References] Reference [22] is a survey on non-IID data and does not obviously contain the claimed convergence proof for FedAvg under full participation; please cite the original analysis (e.g., McMahan et al. [1] or subsequent work) instead.
Circularity Check
No circularity: the convergence analysis is self-contained and does not assume its target objective.
full rationale
The derivation chain is self-contained. The paper defines the p_i weights in Eq. (2) from the availability distribution q, states the global objective in Eq. (3), and proves in Theorem 4 that Algorithm 1 converges to that objective at rate O(1/sqrt T) under Assumptions 1-3. Lemma 4 is a one-step Jensen bound that follows directly from the definition of p_i; it is an identity, not an assumed conclusion. The recursive descent inequality (8) uses Algorithm 1's broadcast rule (line 6) and the Lipschitz/projection bounds, and the final telescoping rate is standard. No parameter is fitted, and the theorem's target objective is not used as an input to the algorithm or to the proof. The manuscript defers full proofs to a forthcoming journal submission, and the proof assumes every client performs local SGD and receives the broadcast each round; these are completeness and scope limitations, not circularity. The only self-citation, [19], is a contextual pointer to prior availability models and is not load-bearing. Therefore no circular step is present.
Assumptions & free parameters
assumptions (5)
- domain assumption Local loss functions f_i are convex on Theta (Assumption 1).
- domain assumption Each client's stochastic gradient has bounded variance sigma_i^2 and bounded norm G^2 (Assumptions 2 and 3).
- domain assumption Client subsets S_t are drawn i.i.d. at each global round from a fixed distribution q with q(empty set)=0.
- ad hoc to paper Every client, including unavailable ones, performs local SGD steps every round and is reset to the server broadcast (Algorithm 1 lines 8-9 and line 6).
- standard math C is convex compact and an optimal solution theta* to problem (3) exists.
Cite this review
Pith. "Pith review of Convergence of Agnostic Federated Averaging." pith.science (2026). https://pith.science/paper/P6KWUUWY
@misc{pith2026250710325,
author = {Pith},
title = {Pith review of: Convergence of Agnostic Federated Averaging},
year = {2026},
howpublished = {\url{https://pith.science/paper/P6KWUUWY}},
note = {Machine review of arXiv:2507.10325}
}
abstract
Federated learning (FL) enables decentralized model training without centralizing raw data. However, practical FL deployments often face a key realistic challenge: Clients participate intermittently in server aggregation and with unknown, possibly biased participation probabilities. Most existing convergence results either assume full-device participation, or rely on knowledge of (in fact uniform) client availability distributions -- assumptions that rarely hold in practice. In this work, we characterize the optimization problem that consistently adheres to the stochastic dynamics of the well-known \emph{agnostic Federated Averaging (FedAvg)} algorithm under random (and variably-sized) client availability, and rigorously establish its convergence for convex, possibly nonsmooth losses, achieving a standard rate of order $\mathcal{O}(1/\sqrt{T})$, where $T$ denotes the aggregation horizon. Our analysis provides the first convergence guarantees for agnostic FedAvg under general, non-uniform, stochastic client participation, without knowledge of the participation distribution. We also empirically demonstrate that agnostic FedAvg in fact outperforms common (and suboptimal) weighted aggregation FedAvg variants, even with server-side knowledge of participation weights.
Reference graph
Works this paper leans on
-
[1]
Convergence of Agnostic Federated Averaging
INTRODUCTION Federated Learning (FL) is an established decentralized machine learning paradigm in which clients collaboratively train a global model without sharing their raw data, thereby preserving privacy and ensuring compliance with data protection regulations [1, 2]. Each client performs local updates on its private dataset and transmits model parame...
work page Pith review arXiv 2025
-
[2]
DISCOVERING THE PROBLEM SETUP We model a realistic FL system in which only a subset of clients is available for communication at any given round. Let there be N clients indexed by [N ] = {1, . . . , N}. At each global round t, a random subset St ⊆ [N ] of clients becomes available to transmit their updated models to the server. This stochastic availabilit...
-
[3]
1 |St| X i∈St θt−1 i − θ∗ 2 Ft−1 # ≤ ESt
CONVERGENCE ANALYSIS OF AGNOSTIC FEDA VG We develop a convergence analysis of agnostic FedAvg under stan- dard assumptions. The algorithm incorporates two sources of ran- domness: First, for each user i ∈ [N ], the random element ξi de- notes a mini-batch of size b sampled uniformly without replacement from their local dataset. At time t, we denote this b...
-
[4]
EXPERIMENTAL EV ALUA TION While the convergence of FedAvg under full-device participation has long been established [22], our experiments below reveal that the convergence behavior of commonly employed weighted FedAvg under partial participation—particularly with imbalanced user selec- tion probabilities—is clearly suboptimal (relative to the objective of...
-
[5]
CONCLUSION In this work, we analyzed the convergence behavior of FedAvg under general, unknown, random and possibly non-uniform device partici- pation We rigorously showed thatagnostic FedAvgoptimizes a well- defined objective governed by user availability (not arbitrary pref- erences) and achieves convergence under this objective for convex nonsmooth los...
-
[6]
Communication-efficient learning of deep networks from de- centralized data,
H. B. McMahan, E. Moore, D. Ramage, S. Hampson et al., “Communication-efficient learning of deep networks from de- centralized data,” Proceedings of AISTATS, 2017
work page 2017
-
[7]
Advances and open prob- lems in federated learning,
P. Kairouz, H. B. McMahan et al., “Advances and open prob- lems in federated learning,” Foundations and Trends in Ma- chine Learning, 2021
work page 2021
-
[8]
Fed- erated learning for mobile keyboard prediction,
A. Hard, K. Rao, R. Mathews, S. Ramaswamy, F. Beaufays, S. Augenstein, H. Eichner, C. Kiddon, and D. Ramage, “Fed- erated learning for mobile keyboard prediction,” inICLR Work- shop, 2018
work page 2018
Show all 31 references
-
[9]
Federated learning with differential privacy: Algorithms and performance analysis,
S. Ramaswamy, R. Mathews, C. Kiddon, and D. Ramage, “Federated learning with differential privacy: Algorithms and performance analysis,” in NeurIPS Workshop on Privacy Pre- serving Machine Learning, 2019
2019
-
[10]
Federated learn- ing with edge computing: A communication-efficient architec- ture,
Q. Yang, Y . Liu, T. Chen, and Y . Tong, “Federated learn- ing with edge computing: A communication-efficient architec- ture,” in IEEE Edge Computing, 2019
2019
-
[11]
Exploiting unintended feature leakage in collaborative learning,
L. Melis, C. Song, E. D. Cristofaro, and V . Shmatikov, “Exploiting unintended feature leakage in collaborative learning,” in 2019 IEEE Symposium on Security and Privacy (SP). IEEE, 2019, pp. 691–706. [Online]. Available: https://ieeexplore.ieee.org/document/8835245
2019
-
[12]
Differentially private federated learning: A client level perspective,
R. C. Geyer, T. Klein, and M. Nabi, “Differentially private federated learning: A client level perspective,” arXiv preprint arXiv:1712.07557 , Dec 2017. [Online]. Available: https://arxiv.org/abs/1712.07557
2017 arXiv
-
[13]
Federated learning: Strategies for improving communication efficiency,
J. Kone ˇcn´y, H. B. McMahan, F. X. Yu, P. Richt ´arik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, Oct 2016. [Online]. Available: https: //arxiv.org/abs/1610.05492
2016 arXiv
-
[14]
A field guide to federated optimization,
J. Wang, Z. Charles, Z. Xu, G. Joshi, and H. B. McMahan, “A field guide to federated optimization,” IEEE Transactions on Signal Processing, Sep. 2021
2021
-
[15]
Client selection for federated learning with heterogeneous resources in mobile edge,
T. Nishio and R. Yonetani, “Client selection for federated learning with heterogeneous resources in mobile edge,” inICC. IEEE, 2019
2019
-
[16]
Towards federated learning at scale: System design,
K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. In- german, V . Ivanov, C. Kiddon, J. Konecny, S. Mazzocchi, B. McMahan, T. Van Overveldt, D. Petrou, D. Ramage, and J. Roselander, “Towards federated learning at scale: System design,” in Proceedings of the 2nd SysML Conferen...
2019
-
[17]
Feder- ated learning with superquantile aggregation for heterogeneous data,
K. Pillutla, Y . Laguel, J. Malick, and Z. Harchaoui, “Feder- ated learning with superquantile aggregation for heterogeneous data,” Machine Learning, vol. 113, pp. 1–68, 05 2023
2023
-
[18]
Optimal client sampling for feder- ated learning,
M. Chen, R. Zhang et al., “Optimal client sampling for feder- ated learning,” in NeurIPS, 2020
2020
-
[19]
Federated op- timization in heterogeneous networks,
T. Li, A. K. Sahu, A. Talwalkar, and V . Smith, “Federated op- timization in heterogeneous networks,” in MLSys, 2020
2020
-
[20]
Semi-cyclic stochastic gradient descent,
H. Eichner, T. Koren, B. McMahan, N. Srebro, and K. Tal- war, “Semi-cyclic stochastic gradient descent,” in Interna- tional Conference on Machine Learning . PMLR, 2019, pp. 1764–1773
2019
-
[21]
Client selection in federated learning: Con- vergence analysis and power-of-choice selection strategies,
Y . Cho and J. Lee, “Client selection in federated learning: Con- vergence analysis and power-of-choice selection strategies,” in IEEE/ACM Transactions on Networking, vol. 30, no. 1, 2020, pp. 376–389
2020
-
[22]
Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization,
A. Reisizadeh, A. Mokhtari, H. Hassani, A. Jadbabaie, and R. Pedarsani, “Fedpaq: A communication-efficient federated learning method with periodic averaging and quantization,” in ICML, 2020
2020
-
[23]
Federated learning with com- pression: Unified analysis and sharp guarantees,
F. Haddadpour and M. Mardani, “Federated learning with com- pression: Unified analysis and sharp guarantees,” in AISTATS, 2021
2021
-
[24]
Federated learning under restricted user avail- ability,
P. Theodoropoulos, K. E. Nikolakakis, and D. Kaloge- rias, “Federated learning under restricted user avail- ability,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Pro- cessing (ICASSP) . IEEE, 2024. [Online]. Available: https://ieeexplore...
2024
-
[25]
Scaffold: Stochastic controlled aver- aging for federated learning,
S. P. Karimireddy et al., “Scaffold: Stochastic controlled aver- aging for federated learning,” in ICML, 2020
2020
-
[26]
Adaptive federated optimization,
S. J. Reddi et al., “Adaptive federated optimization,” in ICLR, 2021
2021
-
[27]
Federated learning with non-iid data: A survey,
Z. Lu, H. Pan, Y . Dai, X. Si, and Y . Zhang, “Federated learning with non-iid data: A survey,”IEEE Internet of Things Journal, vol. PP, pp. 1–1, 06 2024
2024
-
[28]
On the generalization of wasserstein robust federated learning,
T. A. Nguyen, T. D. Nguyen, L. T. Le, and C. T. Dinh, “On the generalization of wasserstein robust federated learning,” arXiv preprint arXiv:2206.01432 , 2022. [Online]. Available: https://arxiv.org/abs/2206.01432
2022 arXiv
-
[29]
Aide: Fast and communication efficient distributed opti- mization,
S. J. Reddi, J. Kone ˇcn´y, P. Richt´arik, B. P´ocz´os, and A. Smola, “Aide: Fast and communication efficient distributed opti- mization,” arXiv preprint arXiv:1608.06879 , 2016. [Online]. Available: https://arxiv.org/abs/1608.06879
2016 arXiv
-
[30]
Communication efficient distributed optimization using an approximate newton-type method,
O. Shamir, N. Srebro, and T. Zhang, “Communication efficient distributed optimization using an approximate newton-type method,” 31st International Conference on Machine Learning, ICML 2014, vol. 3, 12 2013
2014
-
[31]
Federated td learning over finite-rate erasure channels: Linear speedup under markovian sampling,
N. Dal Fabbro, A. Mitra, and G. J. Pappas, “Federated td learning over finite-rate erasure channels: Linear speedup under markovian sampling,” IEEE Control Systems Letters , vol. PP, pp. 1–1, 2023. [Online]. Available: https://ieeexplore. ieee.org/document/10174262
2023
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.