2020

Stochastic Optimization for Performative Prediction

Mendler-Dünner, Celestine, Perdomo, Juan C., Zrnic, Tijana et al.

Understand

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.

Built on

A Stochastic Approximation Method
Herbert Robbins and Sutton Monro · 1951
Earlier work this paper cites.
Learning Time-Varying Concepts
Anthony Kuh, Thomas Petsche, and Ronald L Rivest · 1991
Earlier work this paper cites.
Learning with a Slowly Changing Distribution
Peter L. Bartlett · 1992
Earlier work this paper cites.
Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning
Ronald J Williams · 1992
Earlier work this paper cites.
On the Complexity of Learning from Drifting Distributions
Rakesh D Barve and Philip M Long · 1997
Earlier work this paper cites.
Learning Changing Concepts by Exploiting the Structure of Change
Peter L. Bartlett, Shai Ben-David, and Sanjeev R. Kulkarni · 2000
Earlier work this paper cites.
Policy Gradient Methods for Reinforcement Learning with Function Approximation
Richard S Sutton, David A McAllester, Satinder P Singh, and Yishay Mansour · 2000
Earlier work this paper cites.

Similar

A Natural Policy Gradient
Sham M Kakade · 2002
Cited alongside, same era.
Stochastic Convex Optimization
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan · 2009
Cited alongside, same era.
Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning
Eric Moulines and Francis R Bach · 2011
Cited alongside, same era.
Give Me Some Credit
Kaggle · 2012
Cited alongside, same era.
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
Alexander Rakhlin, Ohad Shamir, and Karthik Sridharan · 2012
Cited alongside, same era.
No More Pesky Learning Rates
Tom Schaul, Sixin Zhang, and Yann LeCun · 2013
Cited alongside, same era.
Non-Stationary Stochastic Optimization
Omar Besbes, Yonatan Gur, and Assaf Zeevi · 2015
Cited alongside, same era.

Then

Optimization Methods for Large-Scale Machine Learning
Léon Bottou, Frank E Curtis, and Jorge Nocedal · 2018
Later among the works it cites.
The Social Cost of Strategic Classification
Smitha Milli, John Miller, Anca D. Dragan, and Moritz Hardt · 2019
Later among the works it cites.
Optimization for Modern Data Analysis
Benjamin Recht and Stephen J. Wright · 2019
Later among the works it cites.
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes
Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan · 2020
Closest in time.
2020 State of Enterprise Machine Learning
Algorithmia · 2020
Closest in time.
WhyNot, 2020
John Miller, Chloe Hsu, Jordan Troutman, Juan Perdomo, Tijana Zrnic, Lydia Liu, Yu Sun, Ludwig Schmidt, and Moritz Hardt · 2020
Closest in time.
Performative Prediction
Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, and Moritz Hardt · 2020
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…