Timezone: »
One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab
Event URL: https://openreview.net/forum?id=ge-z2A8hcWT »
Federated learning is highly studied as an approach to collaboration across large populations, however, little has been explored in how to coordinate resources to maintain such data collaborations over time. Inspired by game theoretic notions, this paper introduces a framework for incentive-aware learning and data sharing in federated learning. Our notions of stable and envy-free equilibria formalize notions of fairness and stability for self-interested agents. For example, in an envy-free equilibrium, no agent would wish to swap their sampling burden with any other agent and in a stable equilibrium, no agent would wish to unilaterally reduce their sampling burden. In addition to formalizing this framework, our contributions include characterizing the structural properties of such equilibria, proving when they exist, and showing how they can be computed. Furthermore, we show that, in the worst case, a $\Omega(\sqrt{k})$ gap exists between the sample-minimizing and equilibrium solutions across realistic learning models.
Federated learning is highly studied as an approach to collaboration across large populations, however, little has been explored in how to coordinate resources to maintain such data collaborations over time. Inspired by game theoretic notions, this paper introduces a framework for incentive-aware learning and data sharing in federated learning. Our notions of stable and envy-free equilibria formalize notions of fairness and stability for self-interested agents. For example, in an envy-free equilibrium, no agent would wish to swap their sampling burden with any other agent and in a stable equilibrium, no agent would wish to unilaterally reduce their sampling burden. In addition to formalizing this framework, our contributions include characterizing the structural properties of such equilibria, proving when they exist, and showing how they can be computed. Furthermore, we show that, in the worst case, a $\Omega(\sqrt{k})$ gap exists between the sample-minimizing and equilibrium solutions across realistic learning models.
Author Information
Richard Phillips (Cornell University)
Han Shao (Toyota Technological Institute at Chicago)
Avrim Blum (Toyota Technological Institute at Chicago)
Nika Haghtalab (University of California, Berkeley)
More from the Same Authors
-
2021 Spotlight: Excess Capacity and Backdoor Poisoning »
Naren Manoj · Avrim Blum -
2021 : One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning »
Richard Phillips · Han Shao · Avrim Blum · Nika Haghtalab -
2021 : On classification of strategic agents who can both game and improve »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : The Strategic Perceptron »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : On classification of strategic agents who can both game and improve »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2021 : The Strategic Perceptron »
Saba Ahmadi · Hedyeh Beyhaghi · Avrim Blum · Keziah Naggita -
2023 Poster: A Unifying Perspective on Multi-Calibration: Game Dynamics for Multi-Objective Learning »
Nika Haghtalab · Michael Jordan · Eric Zhao -
2023 Poster: Jailbroken: How Does LLM Safety Training Fail? »
Alexander Wei · Nika Haghtalab · Jacob Steinhardt -
2023 Poster: Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agents »
Nika Haghtalab · Chara Podimata · Kunhe Yang -
2023 Poster: Provably Efficient Personalized Multi-Objective Decision Making via Comparative Feedback »
Han Shao · Lee Cohen · Avrim Blum · Yishay Mansour · Aadirupa Saha · Matthew Walter -
2023 Poster: Improved Bayes Risk Can Yield Reduced Social Welfare Under Competition »
Meena Jagadeesan · Michael Jordan · Jacob Steinhardt · Nika Haghtalab -
2023 Poster: Strategic Classification under Unknown Personalized Manipulation »
Avrim Blum · Omar Montasser · Han Shao -
2023 Poster: Smoothed Analysis of Sequential Probability Assignment »
Alankrita Bhatt · Nika Haghtalab · Abhishek Shetty -
2023 Oral: Jailbroken: How Does LLM Safety Training Fail? »
Alexander Wei · Nika Haghtalab · Jacob Steinhardt -
2022 : Invited Talk: Nika Haghtalab »
Nika Haghtalab -
2022 Panel: Panel 2C-2: Agreement-on-the-line: Predicting the… & A Theory of… »
Han Shao · Christina Baek -
2022 Poster: Oracle-Efficient Online Learning for Smoothed Adversaries »
Nika Haghtalab · Yanjun Han · Abhishek Shetty · Kunhe Yang -
2022 Poster: On-Demand Sampling: Learning Optimally from Multiple Distributions »
Nika Haghtalab · Michael Jordan · Eric Zhao -
2022 Poster: A Theory of PAC Learnability under Transformation Invariances »
Han Shao · Omar Montasser · Avrim Blum -
2021 : (Live) Invited Talk: Nika Haghtalab (UC Berkeley) on Collaborative Machine Learning: Training and Incentives »
Nika Haghtalab -
2021 Workshop: Learning in Presence of Strategic Behavior »
Omer Ben-Porat · Nika Haghtalab · Annie Liang · Yishay Mansour · David Parkes -
2021 Poster: Excess Capacity and Backdoor Poisoning »
Naren Manoj · Avrim Blum -
2020 Poster: Online Learning with Primary and Secondary Losses »
Avrim Blum · Han Shao -
2014 Poster: Learning Optimal Commitment to Overcome Insecurity »
Avrim Blum · Nika Haghtalab · Ariel Procaccia -
2014 Poster: Learning Mixtures of Ranking Models »
Pranjal Awasthi · Avrim Blum · Or Sheffet · Aravindan Vijayaraghavan -
2014 Poster: Active Learning and Best-Response Dynamics »
Maria-Florina F Balcan · Christopher Berlind · Avrim Blum · Emma Cohen · Kaushik Patnaik · Le Song -
2014 Spotlight: Learning Mixtures of Ranking Models »
Pranjal Awasthi · Avrim Blum · Or Sheffet · Aravindan Vijayaraghavan -
2010 Spotlight: Trading off Mistakes and Don't-Know Predictions »
Amin Sayedi · Avrim Blum · Morteza Zadimoghaddam -
2010 Poster: Trading off Mistakes and Don't-Know Predictions »
Amin Sayedi · Morteza Zadimoghaddam · Avrim Blum -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
2009 Poster: Tracking Dynamic Sources of Malicious Activity at Internet Scale »
Shobha Venkataraman · Avrim Blum · Dawn Song · Subhabrata Sen · Oliver Spatscheck -
2009 Spotlight: Tracking Dynamic Sources of Malicious Activity at Internet Scale »
Shobha Venkataraman · Avrim Blum · Dawn Song · Subhabrata Sen · Oliver Spatscheck -
2008 Workshop: New Challanges in Theoretical Machine Learning: Data Dependent Concept Spaces »
Maria-Florina F Balcan · Shai Ben-David · Avrim Blum · Kristiaan Pelckmans · John Shawe-Taylor