MATH Seminar
| Title: Stability, Optimality, and Fairness in Federated learning |
|---|
| Seminar: CODES@Emory |
| Speaker: Kate Donahue of Cornell University |
| Contact: Elizabeth Newman, elizabeth.newman@emory.edu |
| Date: 2022-10-20 at 10:00AM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: Federated learning is a distributed learning paradigm where multiple agents, each only with access to local data, jointly learn a global model. There has recently been an explosion of research aiming not only to improve the accuracy rates of federated learning, but also provide certain guarantees around social good properties such as total error or fairness. In this talk, I describe two papers analyzing federated learning through the lens of cooperative game theory (both joint with Jon Kleinberg). In the first paper, we discuss fairness in federated learning, which relates to how error rates differ between federating agents. In this work, we consider two notions of fairness: egalitarian fairness (which aims to bound how dissimilar error rates can be) and proportional fairness (which aims to reward players for contributing more data). For egalitarian fairness, we obtain a tight multiplicative bound on how widely error rates can diverge between agents federating together. For proportional fairness, we show that sub-proportional error (relative to the number of data points contributed) is guaranteed for any individually rational federating coalition. The second paper explores optimality in federated learning with respect to an objective of minimizing the average error rate among federating agents. In this work, we provide and prove the correctness of an efficient algorithm to calculate an optimal (error minimizing) arrangement of players. Building on this, we give the first constant-factor bound on the performance gap between stability and optimality, proving that the total error of the worst stable solution can be no higher than 9 times the total error of an optimal solution (Price of Anarchy bound of 9). Relevant Links: https://arxiv.org/abs/2010.00753, https://arxiv.org/abs/2106.09580, https://arxiv.org/abs/2112.00818 |
See All Seminars