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 -
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 Poster: Efficient Use of Limited-Memory Accelerators for Linear Learning on Heterogeneous Systems »
Celestine Dünner · Thomas Parnell · Martin Jaggi