On Federated Averaging with Partial Participation under a General Variance Condition
Organizations: School of Data Science, The Chinese University of Hong Kong, Shenzhen, China · Department of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, and Digital Futures, Stockholm, Sweden
Abstract
In this paper, we study the convergence of Federated Averaging (FedAvg) with partial participation under a general variance condition. In each communication round, the server samples of the clients uniformly at random without replacement. The stochastic gradients are assumed to satisfy the so-called ABC condition, which allows their variance to grow with the local objective gaps. For smooth nonconvex objectives, we establish a finite-time stationarity bound in terms of the heterogeneity measure and the client sampling factor . Here, and denote the infima of the global average objective and client 's local objective, respectively. The bound exhibits a linear speedup in the number of sampled clients and recovers the full-participation result when . Under diminishing stepsizes, we further prove that the gradient norm converges to zero both in expectation and almost surely. Notably, compared with existing analyses of FedAvg with partial participation, our results require no additional data heterogeneity assumption such as bounded gradient dissimilarity (BGD), and the sampling-induced term in our bound is not amplified by the number of local updates at the leading order. The importance of removing the BGD assumption is illustrated by an example that is smooth and lower bounded but violates BGD, yet is covered by our analysis.
Figures & tables
| Paper | Noise | Heterogeneity | Rate | a.s. | |
| Assumption | Measure | ||||
| Full Participation ( ) | |||||
| [ 19 ] | -BGD | N | |||
| [ 10 ] | -BGD | N | |||
| [ 20 ] | -BGD | N | |||
| [ 21 ] | -BGD | N | |||
| 20 | 0.956 | 4.838 | |||
| 50 | 0.998 | 12.809 | |||
| 100 | 0.998 | 26.096 | |||
| 200 | 0.998 | 52.675 | |||
Federated Learning
Federated learning trains shared models across data holders without requiring them to pool their raw data.
See all 1,027 papers