Client Heterogeneity in Federated Learning Systems
Angelo RODIO
July 3, 2024
Centre Inria d'Université Côte d'Azur
Outline
Motivations: "ML models need data"
WE ARE HERE
Hestness, et al. "Deep learning scaling is predictable, empirically.", arXiv, 2017
error: smaller is better
dataset size: note log axis
Villalobos, et al. "Position: Will we run out of data? Limits of LLM scaling based on human-generated data." ICML, 2024
1
Motivations: "Data production at end-devices"
ML model
Data
Clients
Cloud server
2
A shift of paradigm:
Data
Clients
ML model
Data
Centralized optimization
loss function
data sample
from centralized data
to decentralized data
Cloud server
Data may be sensitive
Sending data may be costly
3
Federated Learning as a solution
[McM’16; Kon’16]
Data
Clients
where
loss function
data sample
global objective
local objective
local objective
ML model
Cloud server
4
Federated Learning as a solution
5
Cross-silo FL
Cross-device FL
Hospitals
Organizations
smartphones, voice assistants, social media
Github: Pold87/academic-keyword-occurrence
[McM’16; Kon’16]
A baseline algorithm: FedAvg
Data
Clients
Cloud server
initial model
Objective:
6
[McM’16; Kon’16; Red’19]
A baseline algorithm: FedAvg
Clients
Cloud server
client optimization
Objective:
6
[McM’16; Kon’16; Red’19]
A baseline algorithm: FedAvg
Clients
Cloud server
client update
Objective:
6
[McM’16; Kon’16; Red’19]
A baseline algorithm: FedAvg
Clients
Cloud server
server optimization
Objective:
6
server aggregation
set of participating clients
client update
[McM’16; Kon’16; Red’19]
Statistical heterogeneity
System heterogeneity
Heterogeneous network
Heterogeneous hardware
Heterogeneous power, etc
Challenges & Contributions
7
+
from
from
from
Client participation heterogeneity
results into
[INFOCOM’23]
[TON’23]
[SIGMETRICS SRC’24]
[arXiv’24]
[WPMC’23]
[arXiv’24]
*bold: first author
Other challenges:
- personalization�- fairness�- robustness�- privacy
PART 1
PART 2
PART 3 (overview)
[Wang’20; Kai’20; Li’20]
In this presentation
8
Statistical heterogeneity
System heterogeneity
Heterogeneous network
Heterogeneous hardware
Heterogeneous power, etc
+
from
from
from
Client participation heterogeneity
results into
Client participation heterogeneity
Publications
In this presentation
Problem
Key idea
Algorithm
variance from correlation
variance from low participation
leverage optim-bias tradeoff
leverage stale client updates
Correlation-Aware FL (CaFed)
Staleness-Aware FL (FedStale)
8
[IEEE INFOCOM 2023]
[IEEE/ACM Trans. On Net. 2023]
[ACM SIGMETRICS SRC 2024]
[European Conf. AI 2024]
PART 1
Heterogeneous and correlated client participation
8
Heterogeneous and correlated client participation
Common Assumption [Li’19, Kar’20]
Communication rounds
Clients
Communication rounds
Our work
client participation
sampled client
In our work, participation is heterogeneous, correlated over time (temporal) &�among clients (spatial)
temporal correlation
spatial correlation
[Wan’20, Red’21]
temporal correlation
spatial correlation
When the population �is large, the server can �work with K/N clients.
Common assumption:
9
Assumption to model the heterogeneous �and correlated client participation
E.g., client participations are independent:
avg. participation
correlation
Client i
not participating
participating
10
Related work
Spatial correlation
Temporal correlation
11
General FL algorithm
server aggregation
server optimization
Objective:
WE CAN CHOOSE
Clients
Cloud server
12
Problem: client heterogeneity
12
Before, we considered IID data distributions…
"happy" & "sad"
"happy" & "sad"
Problem: client heterogeneity
Statistical heterogeneity
"sad" client
"happy" client
12
Problem: client heterogeneity
Statistical heterogeneity
Participation heterogeneity
Model Bias�in favor of the more participating client
+
=
"sad" client
"happy" client
12
Problem: client heterogeneity
13
Problem: client heterogeneity
13
Problem: client heterogeneity
biased objective
14
Bias error (def.)
Bias Error
where we should have converged
where we eventually converge
15
Bias error (theorem)
total variation
statistical heterogeneity
15
Bias error (guideline)
Unbiased FedAvg
total variation
statistical heterogeneity
Guideline 1:
15
Unbiased FedAvg
16
Unbiased FedAvg
16
Unbiased FedAvg
16
Unbiased FedAvg
16
Optimization error
No Correlation ( )
17
Client 1 ONLY
Client 2 PARTICIPATES CONSECUTIVELY
Large variability
Low variability
Correlation ( )
Optimization error (def.)
where we actually stop
where we eventually converge
18
: #rounds
: #rounds
avg. participation
correlation
Optimization error (theorem)
WE CAN CHOOSE
WE CAN CONTROL
first convergence analysis!
18
Exclude ( ) "more correlated" clients
correlation
Optimization error (guidelines)
WE CAN CHOOSE
WE CAN CONTROL
Exclude ( ) "less participating" clients
Guideline 2:
Guideline 3:
18
: #rounds
avg. participation
Minimize the green term for large
: #rounds
avg. availability
correlation
Optimization error (guidelines)
Minimize the blue term large for large
WE CAN CHOOSE
WE CAN CONTROL
Total error (def.)
Total Error
where we actually stop
where we should have converged
Total error (theorem)
Total Error
Correlation-Aware FL (CaFed)
1) The server
19
Correlation-Aware FL (CaFed)
1) The server
(G1)
19
Correlation-Aware FL (CaFed)
2) For , starting from the
"Less Participating", "More Correlated" clients:
(G2)
(G3)
19
Correlation-Aware FL (CaFed)
2) For , starting from the
"Less Participating", "More Correlated" clients:
(G2)
(G3)
19
Correlation-Aware FL (CaFed)
confirm decision
2) For , starting from the
"Less Participating", "More Correlated" clients:
(G2)
(G3)
19
Experimental setting
More Participating
Minimize the optimization error
Faster convergence to a biased objective
Unbiased
Minimize the bias error
Slower convergence to target objective
20
Experimental results
CaFed entirely excludes "Less Participating", "More Correlated" clients
21
When data distribution is intra-group homogeneous, inter-group homogeneous
CASE 1
Experimental results
CaFed excludes some of the "Less Participating", "More Correlated" clients
23
When data distribution is intra-group homogeneous, inter-group heterogeneous
CASE 2
Experimental results
21
spatial correlation
temporal correlation
Experimental results
CaFed excludes some "Less Participating", "More Correlated" clients adaptively over time
21
CaFed achieves higher accuracy within training time
Experimental results
21
CIFAR-10
Part 1. Conclusions
the "less participating", "more correlated" clients
22
PART 2
Leveraging Stale Updates for Non-Participating Clients
23
Variance from participation heterogeneity
Unbiased FedAvg [Rod’23; Wang’22,24]
set of �participating �clients
(asymptotic)�participation probability of client i
Cloud server
24
Cloud server
set of �participating �clients
Variance from participation heterogeneity
24
(asymptotic)�participation probability of client i
Unbiased FedAvg [Rod’23; Wang’22,24]
Variance from participation heterogeneity
Client 1 ONLY
Client 2 PARTICIPATES
Client 1 ONLY
Client 2 PARTICIPATES
25
Large variance
U-FedAvg
Q: Why?
Q: Can we reduce this variance?
U-FedAvg (Convergence)
Upper bound. Under Assumptions 1-3, for smooth, non-convex objectives:
26
Variance Reduction. Leverage stale updates �for non-participating clients [Gu’21; Jhu’22]
Cloud server
memory term: stale update of client i
27
[Yang’22; Yan’24]
Related work
27
memory term: stale update of client i
Variance Reduction. Leverage stale updates �for non-participating clients [Gu’21; Jhu’22]
[Yang’22; Yan’24]
Related work
Cloud server
Q: Why?
Client 2 quits participation
Suboptimal trajectory
Variance Reduction
Client 1 ONLY
IF Client 2 HAD PARTICIPATED
Ideal trajectory
Stale Update
Ideal trajectory
28
U-FedVARP
U-FedAvg
Convergence
Upper bound. Under Assumptions 1-3, for smooth, non-convex objectives:
Lower bound. The term is necessary:
Our findings.
29
FedStale
30
30
Staleness-Aware FL (FedStale)
Q: Why does it work?
Staleness-Aware FL (FedStale)
A convex combination of �"fresh" and "stale" updates
Cloud server
31
weight to stale updates
Convergence
Upper bound. Under Assumptions 1-3, for smooth, non-convex objectives:
Minimizing the bound:
32
Experimental results
33
Part 2. Conclusions
34
Client participation heterogeneity
Publications
Comparison
Problem
Key idea
Algorithm
variance from correlation
variance from participation
leverage optim-bias tradeoff
leverage stale client updates
Correlation-Aware FL (CaFed)
Staleness-Aware FL (FedStale)
[IEEE INFOCOM 2023]
[IEEE/ACM Trans. On Net. 2023]
[ACM SIGMETRICS SRC 2024]
[arXiv 2024]
PART 1
PART 2
35
PART 3
36
Statistical heterogeneity
System heterogeneity
Heterogeneous network
Heterogeneous hardware
Heterogeneous power, etc
Challenges & Contributions
+
from
from
from
Client participation heterogeneity
results into
[INFOCOM’23]
[TON’23]
[SIGMETRICS SRC’24]
[ArXiv’24]
[WPMC’23]
[arXiv’24]
PART 3 (overview)
37
Heterogeneous network resources
39
80 rounds
+10%
residual errors
Heterogeneous network resources
38
[YAN’20; ERI’21]
[CHE’21; YE’22]
[XIN’16; MIS’19]
[MAL’16; PHI’19]
[WPMC’23]
Heterogeneous hardware resources
39
[REN’23; SIS’24]
[ArXiv’24]
Client Participation in Federated Learning Systems
Incentivizing client participation through personalization[MAN’20; DEN’20]
Decentralized or �semi-decentralized topologies[KOL’20; KIN’21]
Future Research Directions
40
Client
Federation
What do �I gain?
Personalization:
Server
Client
Neighbors
I can’t talk to the server
but I can talk to my neighbors
Remote�server
Heterogeneous network resouces
Heterogeneous energy resouces
Heterogeneous client participation
Incentivizing client participation through personalization
Decentralized or �semi-decentralized topologies
Retransmissions? When? How many?
Correlated client participation driven by energy contraints
Future Research Directions
35
References
41
Machine Learning models are data-hungry��[HES’17] J. Hestness et al., “Deep Learning Scaling is Predictable, Empirically.” arXiv, Dec. 01, 2017.
[VIL’24] P. Villalobos, A. Ho, J. Sevilla, T. Besiroglu, L. Heim, and M. Hobbhahn, “Will we run out of data? Limits of LLM scaling based on human-generated data,” presented at the Forty-first International Conference on Machine Learning, Jun. 2024��Federated Learning
[MCM’17] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas, “Communication-Efficient Learning of Deep Networks from Decentralized Data,” in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, PMLR, Apr. 2017, pp. 1273–1282.
[KON’17] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated Learning: Strategies for Improving Communication Efficiency.” arXiv, Oct. 2017.
[RED’21] S. J. Reddi et al., “Adaptive Federated Optimization,” in International Conference on Learning Representations, 2021.�
Federated Learning Surveys�
[WAN’21] J. Wang et al., “A Field Guide to Federated Optimization.” arXiv, Jul. 14, 2021. doi: 10.48550/arXiv.2107.06917.
[KAI’21] P. Kairouz et al., “Advances and Open Problems in Federated Learning,” Foundations and Trends® in Machine Learning, vol. 14, no. 1–2, pp. 1–210, Jun. 2021, doi: 10.1561/2200000083.
[LI’20] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated Learning: Challenges, Methods, and Future Directions,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 50–60, May 2020, doi: 10.1109/MSP.2020.2975749.
�Convergence analysis of FL algorithms��[LI’20] X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang, “On the Convergence of FedAvg on Non-IID Data,” in International Conference on Learning Representations, Apr. 2023.
[WAN’20] J. Wang, Q. Liu, H. Liang, G. Joshi, and H. V. Poor, “Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2020.
[KAR’20] S. P. Karimireddy, S. Kale, M. Mohri, S. Reddi, S. Stich, and A. T. Suresh, “SCAFFOLD: Stochastic Controlled Averaging for Federated Learning,” in Proceedings of the 37th International Conference on Machine Learning, PMLR, Nov. 2020.
�
42
Federated Learning with Cyclic Client Participation�
[EIC’19] H. Eichner, T. Koren, B. Mcmahan, N. Srebro, and K. Talwar, “Semi-Cyclic Stochastic Gradient Descent,” in Proceedings of the 36th International Conference on Machine Learning, PMLR, May 2019, pp. 1764–1773.
[ZHU’21] C. Zhu, Z. Xu, M. Chen, J. Konečnỳ, A. Hard, and T. Goldstein, “Diurnal or nocturnal? Federated learning from periodically shifting distributions,” in NeurIPS 2021 Workshop on Distribution Shifts, 2021.
[CHO’23] Y. J. Cho, P. Sharma, G. Joshi, Z. Xu, S. Kale, and T. Zhang, “On the Convergence of Federated Averaging with Cyclic Client Participation,” in Proceedings of the 40th International Conference on Machine Learning, PMLR, Jul. 2023.��Federated Learning with Temporal and Spatial Correlation
[RIB’20] M. Ribero, H. Vikalo, and G. de Veciana, “Federated Learning Under Intermittent Client Availability and Time-Varying Communication Constraints,” IEEE Journal of Selected Topics in Signal Processing, vol. 17, no. 1, pp. 98–111, Jan. 2023, doi: 10.1109/JSTSP.2022.3224590.
[SUN’18] T. Sun, Y. Sun, and W. Yin, “On Markov Chain Gradient Descent,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2018.
[DOA’20] T. T. Doan, “Local Stochastic Approximation: A Unified View of Federated Learning and Distributed Multi-Task Reinforcement Learning Algorithms,” arXiv:2006.13460, Jun. 2020, doi: 10.48550/arXiv.2006.13460.��
43
Unbias FedAvg due to Heterogeneous Client Participation
[WAN’22] S. Wang and M. Ji, “A Unified Analysis of Federated Learning with Arbitrary Client Participation,” Advances in Neural Information Processing Systems, vol. 35, pp. 19124–19137, Dec. 2022.
[WAN’24] S. Wang and M. Ji, “A Lightweight Method for Tackling Unknown Participation Statistics in Federated Averaging.” arXiv, Jan. 2024.��Federated Learning with Variance Reduction
[GU’21] X. Gu, K. Huang, J. Zhang, and L. Huang, “Fast Federated Learning in the Presence of Arbitrary Device Unavailability,” in Advances in Neural Information Processing Systems, Curran Associates, Inc., 2021, pp. 12052–12064.
[JHU’22] D. Jhunjhunwala, P. Sharma, A. Nagarkatti, and G. Joshi, “Fedvarp: Tackling the Variance due to Partial Client Participation in Federated Learning,” in Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR, Aug. 2022, pp. 906–916.
[YAN’22] H. Yang, X. Zhang, P. Khanduri, and J. Liu, “Anarchic Federated Learning,” in Proceedings of the 39th International Conference on Machine Learning, PMLR, Jun. 2022, pp. 25331–25363.
[YAN’24] Y. Yan et al., “Federated Optimization Under Intermittent Client Availability,” INFORMS Journal on Computing, vol. 36, no. 1, pp. 185–202, Jan. 2024, doi: 10.1287/ijoc.2022.0057.
44
Federated Learning with Lossy Communication Channels
[ERI’21] M. C. Eriş, B. Kantarci, and S. Oktug, “Unveiling the Wireless Network Limitations in Federated Learning,” in 2021 IEEE International Symposium on Dynamic Spectrum Access Networks (DySPAN), Dec. 2021.
[YAN’20] H. H. Yang, Z. Liu, T. Q. S. Quek, and H. V. Poor, “Scheduling Policies for Federated Learning in Wireless Networks,” IEEE Transactions on Communications, vol. 68, no. 1, pp. 317–333, Jan. 2020.
[YE’22] H. Ye, L. Liang, and G. Y. Li, “Decentralized Federated Learning With Unreliable Communications,” IEEE Journal of Selected Topics in Signal Processing, vol. 16, no. 3, pp. 487–500, Apr. 2022.
[CHE’21] M. Chen, Z. Yang, W. Saad, C. Yin, H. V. Poor, and S. Cui, “A Joint Learning and Communications Framework for Federated Learning Over Wireless Networks,” IEEE Transactions on Wireless Communications, Jan. 2021.��Federated Learning is robust to intermediate errors�
[XIN’16] E. P. Xing, Q. Ho, P. Xie, and D. Wei, “Strategies and Principles of Distributed Machine Learning on Big Data,” Engineering, vol. 2, no. 2, pp. 179–195, Jun. 2016.��[MIS’23] K. Mishchenko, E. Gorbunov, M. Takáč, and P. Richtárik, “Distributed Learning with Compressed Gradient Differences.” arXiv, Dec. 28, 2023. doi: 10.48550/arXiv.1901.09269.
�
45
[MIS’22] K. Mishchenko, G. Malinovsky, S. Stich, and P. Richtarik, “ProxSkip: Yes! Local Gradient Steps Provably Lead to Communication Acceleration! Finally!,” in Proceedings of the 39th International Conference on Machine Learning, Jun. 2022.
[PHI’22] C. Philippenko and A. Dieuleveut, “Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees.” arXiv, Jun. 19, 2022. doi: 10.48550/arXiv.2006.14591.��Cooperative Inference Systems for Distributed Machine Learning �
[REN’23] W.-Q. Ren et al., “A Survey on Collaborative DNN Inference for Edge Intelligence,” Mach. Intell. Res., vol. 20, no. 3, pp. 370–395, Jun. 2023, doi: 10.1007/s11633-022-1391-7.
[SIS’24] T. Si Salem, G. Castellano, G. Neglia, F. Pianese, and A. Araldo, “Toward Inference Delivery Networks: Distributing Machine Learning With Optimality Guarantees,” IEEE/ACM Transactions on Networking, vol. 32, no. 1, pp. 859–873, Feb. 2024.��Incentives to Federated Learning through Personalization
[DON’20] K. Donahue and J. Kleinberg, “Model-sharing Games: Analyzing Federated Learning Under Voluntary Participation.” arXiv, Dec. 17, 2020. doi: 10.48550/arXiv.2010.00753.
[GRI’21] F. Grimberg, M.-A. Hartley, S. P. Karimireddy, and M. Jaggi, “Optimal Model Averaging: Towards Personalized Collaborative Learning.” arXiv, Oct. 25, 2021. doi: 10.48550/arXiv.2110.12946.
����
�
46
[MAN’20] Y. Mansour, M. Mohri, J. Ro, and A. T. Suresh, “Three Approaches for Personalization with Applications to Federated Learning.” arXiv, Jul. 19, 2020. doi: 10.48550/arXiv.2002.10619.
�[DEN’20] Y. Deng, M. M. Kamani, and M. Mahdavi, “Adaptive Personalized Federated Learning.” arXiv, Nov. 05, 2020. doi: 10.48550/arXiv.2003.13461.��Decentralized and Semi-Decentralized Topologies for Federated Learning �
[KOL’20] A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich, “A Unified Theory of Decentralized SGD with Changing Topology and Local Updates,” in Proceedings of the 37th International Conference on Machine Learning, PMLR, Nov. 2020.
[LIN’21] F. P.-C. Lin, S. Hosseinalipour, S. S. Azam, C. G. Brinton, and N. Michelusi, “Semi-Decentralized Federated Learning With Cooperative D2D Local Model Aggregations,” IEEE Journal on Selected Areas in Communications, vol. 39, no. 12, pp. 3851–3869, Dec. 2021, doi: 10.1109/JSAC.2021.3118344.
[COS’23] M. Costantini, G. Neglia, and T. Spyropoulos, “FedDec: Peer-to-peer Aided Federated Learning.” arXiv, Jun. 11, 2023. doi: 10.48550/arXiv.2306.06715.
[CHE’24] E. Chen, S. Wang, and C. G. Brinton, “Taming Subnet-Drift in D2D-Enabled Fog Learning: A Hierarchical Gradient Tracking Approach.” arXiv, Jan. 09, 2024. doi: 10.48550/arXiv.2312.04728.
�
�
47
Problem
Publications
system heterogeneity
variance from participation
Take-home
variance from correlation
leverage optim-bias tradeoff
leverage stale client updates
Correlation-Aware FL (CaFed)
Staleness-Aware FL (FedStale)
[IEEE INFOCOM 2023]
[IEEE/ACM Trans. On Net. 2023]
[ACM SIGMETRICS SRC 2024]
[arXiv 2024]
PART 1
PART 2
PART 3
Heterogeneity-Aware FL
convergence analysis
[WPMC 2023]
[arXiv 2024]
Key idea
Algorithm
48
BACKUP
Client participation heterogeneity
Approach
Comparison
Problem
Assumptions
Algorithm
variance from correlation
variance from participation
smoothness; strong-convexity
only smoothness
strongly relies on bound
loosely relies on bound
PART 1
PART 2
top-down
bottom-up
Characterization of 2-state MC
Proof intuition
Participation Estimation (CaFed)
Participation Estimation (FedStale)
More experiments (FedStale)
Future Research Directions (Personalization)