More Like this

1. Stochastic Optimization for Performative Prediction

   Mendler-Dünner, Celestine; Perdomo, Juan C.; Zrnic, Tijana; Hardt, Moritz (July 2020, Advances in Neural Information Processing Systems 33 (NeurIPS 2020))

   null (Ed.)

   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. 

   more » « less
2. How the map becomes the territory: prediction, performativity and the process of taking digital twins for granted

   https://doi.org/10.1007/s41469-024-00164-2  

   Leonardi, Paul_M; Leavell, Virginia (February 2024, Journal of Organization Design)

   Abstract A growing body of literature argues that digital models do not just help organizational leaders to predict the future. Models can inadvertently produce the very future they purport to describe. In this view,performativityis a side-effect of digital modeling. But digital twins turn such thinking on its head. Digital twins are digital models that are designed to be performative—changes in the model are supposed to produce corresponding changes in the world the model represents. This is what makes digital twins useful. But for decision-makers to act in ways that align the world outside the model with the predictions contained within, they must first believe that the model is a faithful representation. In other words, for a digital twin to become performative, it must first be taken-for-granted as “real”. In this paper, we explore the technological and organizational characteristics that are likely to shape the level of taken-for-grantedness of a digital twin. 

   more » « less
3. Multiplayer Performative Prediction: Learning in Decision-Dependent Games

   Narang, Adhyyan; Faulkner, Evan; Drusvyatskiy, Dmitriy; Fazel, Maryam; Ratliff, Lillian J. (January 2023, Journal of Machine Learning Research)

   Learning problems commonly exhibit an interesting feedback mechanism wherein the population data reacts to competing decision makers’ actions. This paper formulates a new game theoretic framework for this phenomenon, called multi-player performative prediction. We focus on two distinct solution concepts, namely (i) performatively stable equilibria and (ii) Nash equilibria of the game. The latter equilibria are arguably more informative, but are generally computationally difficult to find since they are solutions of nonmonotone games. We show that under mild assumptions, the performatively stable equilibria can be found efficiently by a variety of algorithms, including repeated retraining and the repeated (stochastic) gradient method. We then establish transparent sufficient conditions for strong monotonicity of the game and use them to develop algorithms for finding Nash equilibria. We investigate derivative free methods and adaptive gradient algorithms wherein each player alternates between learning a parametric description of their distribution and gradient steps on the empirical risk. Synthetic and semi-synthetic numerical experiments illustrate the results. 

   more » « less
4. Performative Federated Learning: A Solution to Model-Dependent and Heterogeneous Distribution Shifts

   Jin, Kun; Yin, Tongxin; Chen, Zhongzhu; Sun, Zeyu; Zhang, Xueru; Liu, Yang; Liu, Mingyan (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider a federated learning (FL) system consisting of multiple clients and a server, where the clients aim to collaboratively learn a common decision model from their distributed data. Unlike the conventional FL framework that assumes the client's data is static, we consider scenarios where the clients' data distributions may be reshaped by the deployed decision model. In this work, we leverage the idea of distribution shift mappings in performative prediction to formalize this model-dependent data distribution shift and propose a performative FL framework. We first introduce necessary and sufficient conditions for the existence of a unique performative stable solution and characterize its distance to the performative optimal solution. Then we propose the performative FedAvg algorithm and show that it converges to the performative stable solution at a rate of O(1/T) under both full and partial participation schemes. In particular, we use novel proof techniques and show how the clients' heterogeneity influences the convergence. Numerical results validate our analysis and provide valuable insights into real-world applications. 

   more » « less
5. Performative Federated Learning: A Solution to Model-Dependent and Heterogeneous Distribution Shifts

   https://doi.org/10.1609/aaai.v38i11.29191  

   Jin, Kun; Yin, Tongxin; Chen, Zhongzhu; Sun, Zeyu; Zhang, Xueru; Liu, Yang; Liu, Mingyan (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We consider a federated learning (FL) system consisting of multiple clients and a server, where the clients aim to collaboratively learn a common decision model from their distributed data. Unlike the conventional FL framework that assumes the client's data is static, we consider scenarios where the clients' data distributions may be reshaped by the deployed decision model. In this work, we leverage the idea of distribution shift mappings in performative prediction to formalize this model-dependent data distribution shift and propose a performative FL framework. We first introduce necessary and sufficient conditions for the existence of a unique performative stable solution and characterize its distance to the performative optimal solution. Then we propose the performative FedAvg algorithm and show that it converges to the performative stable solution at a rate of O(1/T) under both full and partial participation schemes.In particular, we use novel proof techniques and show how the clients' heterogeneity influences the convergence. Numerical results validate our analysis and provide valuable insights into real-world applications. 

   more » « less