Timezone: »
Poster
Stochastic Optimization for Performative Prediction
Celestine Mendler-Dünner · Juan Perdomo · Tijana Zrnic · Moritz Hardt
In performative prediction, the choice of a model influences the distribution of future data, typically through actions taken based on the model's predictions. We initiate the study of stochastic optimization for performative prediction. What sets this setting apart from traditional stochastic optimization is the difference between merely updating model parameters and deploying the new model. The latter triggers a shift in the distribution that affects future data, while the former keeps the distribution as is. Assuming smoothness and strong convexity, we prove rates of convergence for both greedily deploying models after each stochastic update (greedy deploy) as well as for taking several updates before redeploying (lazy deploy). In both cases, our bounds smoothly recover the optimal $O(1/k)$ rate as the strength of performativity decreases. Furthermore, they illustrate how depending on the strength of performative effects, there exists a regime where either approach outperforms the other. We experimentally explore the trade-off on both synthetic data and a strategic classification simulator.
Author Information
Celestine Mendler-Dünner (UC Berkeley)
Juan Perdomo (University of California, Berkeley)
Tijana Zrnic (UC Berkeley)
Moritz Hardt (University of California, Berkeley)
More from the Same Authors
-
2021 : Alternative Microfoundations for Strategic Classification »
Meena Jagadeesan · Celestine Mendler-Dünner · Moritz Hardt -
2021 : Alternative Microfoundations for Strategic Classification »
Meena Jagadeesan · Celestine Mendler-Dünner · Moritz Hardt -
2022 : Causal Inference out of Control: Identifying the Steerability of Consumption »
Gary Cheng · Moritz Hardt · Celestine Mendler-Dünner -
2022 : Valid Inference after Causal Discovery »
Paula Gradu · Tijana Zrnic · Yixin Wang · Michael Jordan -
2023 Poster: Collaborative Learning via Prediction Consensus »
Dongyang Fan · Celestine Mendler-Dünner · Martin Jaggi -
2022 : Panel »
Meena Jagadeesan · Avrim Blum · Jon Kleinberg · Celestine Mendler-Dünner · Jennifer Wortman Vaughan · Chara Podimata -
2022 : Causal Inference out of Control: Identifying the Steerability of Consumption »
Gary Cheng · Moritz Hardt · Celestine Mendler-Dünner -
2022 Poster: Performative Power »
Moritz Hardt · Meena Jagadeesan · Celestine Mendler-Dünner -
2022 Poster: Globally Convergent Policy Search for Output Estimation »
Jack Umenberger · Max Simchowitz · Juan Perdomo · Kaiqing Zhang · Russ Tedrake -
2022 Poster: Anticipating Performativity by Predicting from Predictions »
Celestine Mendler-Dünner · Frances Ding · Yixin Wang -
2021 : Microfoundations of Algorithmic decisions »
Moritz Hardt -
2021 Workshop: Learning and Decision-Making with Strategic Feedback (StratML) »
Yahav Bechavod · Hoda Heidari · Eric Mazumdar · Celestine Mendler-Dünner · Tijana Zrnic -
2021 Oral: Retiring Adult: New Datasets for Fair Machine Learning »
Frances Ding · Moritz Hardt · John Miller · Ludwig Schmidt -
2021 Poster: Retiring Adult: New Datasets for Fair Machine Learning »
Frances Ding · Moritz Hardt · John Miller · Ludwig Schmidt -
2021 Poster: Who Leads and Who Follows in Strategic Classification? »
Tijana Zrnic · Eric Mazumdar · Shankar Sastry · Michael Jordan -
2021 Poster: Individual Privacy Accounting via a Rényi Filter »
Vitaly Feldman · Tijana Zrnic -
2021 Poster: Test-time Collective Prediction »
Celestine Mendler-Dünner · Wenshuo Guo · Stephen Bates · Michael Jordan -
2021 Poster: Stabilizing Dynamical Systems via Policy Gradient Methods »
Juan Perdomo · Jack Umenberger · Max Simchowitz -
2020 : Invited Talk 7: Prediction Dynamics »
Moritz Hardt -
2020 : Tutorial: A brief tutorial on causality and fair decision making »
Moritz Hardt -
2019 Poster: Model Similarity Mitigates Test Set Overuse »
Horia Mania · John Miller · Ludwig Schmidt · Moritz Hardt · Benjamin Recht -
2019 Poster: A Meta-Analysis of Overfitting in Machine Learning »
Becca Roelofs · Vaishaal Shankar · Benjamin Recht · Sara Fridovich-Keil · Moritz Hardt · John Miller · Ludwig Schmidt -
2019 Poster: SySCD: A System-Aware Parallel Coordinate Descent Algorithm »
Nikolas Ioannou · Celestine Mendler-Dünner · Thomas Parnell -
2019 Spotlight: SySCD: A System-Aware Parallel Coordinate Descent Algorithm »
Nikolas Ioannou · Celestine Mendler-Dünner · Thomas Parnell -
2018 Poster: Snap ML: A Hierarchical Framework for Machine Learning »
Celestine Dünner · Thomas Parnell · Dimitrios Sarigiannis · Nikolas Ioannou · Andreea Anghel · Gummadi Ravi · Madhusudanan Kandasamy · Haralampos Pozidis -
2017 : Safety beyond Security: Societal Challenges for Machine Learning »
Moritz Hardt -
2017 Poster: Avoiding Discrimination through Causal Reasoning »
Niki Kilbertus · Mateo Rojas Carulla · Giambattista Parascandolo · Moritz Hardt · Dominik Janzing · Bernhard Schölkopf -
2017 Poster: Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems »
Celestine Dünner · Thomas Parnell · Martin Jaggi -
2017 Tutorial: Fairness in Machine Learning »
Solon Barocas · Moritz Hardt -
2016 Poster: Equality of Opportunity in Supervised Learning »
Moritz Hardt · Eric Price · Eric Price · Nati Srebro -
2015 Workshop: Adaptive Data Analysis »
Adam Smith · Aaron Roth · Vitaly Feldman · Moritz Hardt -
2015 Poster: Generalization in Adaptive Data Analysis and Holdout Reuse »
Cynthia Dwork · Vitaly Feldman · Moritz Hardt · Toni Pitassi · Omer Reingold · Aaron Roth -
2015 Poster: Differentially Private Learning of Structured Discrete Distributions »
Ilias Diakonikolas · Moritz Hardt · Ludwig Schmidt -
2014 Workshop: Fairness, Accountability, and Transparency in Machine Learning »
Moritz Hardt · Solon Barocas -
2014 Poster: The Noisy Power Method: A Meta Algorithm with Applications »
Moritz Hardt · Eric Price -
2014 Spotlight: The Noisy Power Method: A Meta Algorithm with Applications »
Moritz Hardt · Eric Price