Tight Lower Bounds and Improved Convergence in Performative Prediction

Pedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien *, Gauthier Gidel · 2024

Read Tight Lower Bounds and Improved Convergence in Performative Prediction by Pedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien *, Gauthier Gidel (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03671.txt.

Introduction

Pedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien, and Gauthier Gidel sharpen the math of prediction systems that change the data they predict. Their 2024 paper works in performative prediction, where a deployed model shifts the very spread of inputs it faces. Fast settling at a stable point matters most in changing settings.

Their method reuses data from past retraining rounds, not just the latest one. That reuse widens the class of problems that provably settle. New bounds for last-round-only methods are proven tight for the first time here. History-aware variants beat the old floor and settle faster in tests. Benchmark runs back the speed gain across several performative tasks.

Catalog record

CREATORPedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien *, Gauthier Gidel
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE105 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-03671

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Tight Lower Bounds and Improved Convergence in Performative Prediction Pedram Khorsandi, Rushil Gupta, Mehrnaz Mofakhami, Simon Lacoste-Julien *, Gauthier Gidel Abstract Performative prediction is a framework accounting for the shift in the data distribution induced by the prediction of a model deployed in the real world. Ensuring convergence to a stable solution—one at which the post - deployment data distribution no longer changes—is crucial in settings where model predictions can influence future data. This paper, for the first time, extends the Repeated Risk Minimization (RRM) algorithm class by utilizing historical datasets from previous retraining snapshots, yielding a class of algorithms that we call Affine Risk Minimizers that converges to a performatively stable point for a broader class of problems. We introduce a new upper bound for methods that use only the final iteration of the dataset and prove for the first time the tightness of both this new bound and the previous existing bounds within the same regime. We also prove that our new algorithm class can surpass the lower bound for standard RRM, thus breaking the prior lower bound, and empirically observe faster convergence to the stable point on various performative prediction benchmarks. We offer at the same time the first lower bound analysis for RRM within the class of Affine Risk Minimizers, quantifying the potential improvements in convergence speed that could be achieved with other variants in our scheme. 1 Introduction Decision-making systems are increasingly integral to critical judgments in sectors such as public policy ( Fire and Guestrin, 2019 ) , healthcare ( Bevan and Hood, 2006 ) , and education ( Nichols and Berliner, 2007 ) . However, as these systems become more reliant on quantitative indicators, they become vulnerable to the effects described by Goodhart’s Law: “When a measure becomes a target, it ceases to be a good measure” ( Goodhart, 1984 ) . This principle is particularly relevant when predictive models not only forecast outcomes but also influence the behavior of individuals and organizations, leading to performative effects that can subvert the original goals of these systems. For example, in environmental regulation, companies might manipulate emissions data to meet regulatory targets without truly reducing pollution, thus distorting the intended environmental protection efforts ( Fowlie et al., 2012 ) . In healthcare, hospitals may modify patient care practices to improve performance metrics, potentially prioritizing score improvements over actual patient health outcomes ( Bevan and Hood, 2006 ) . Similarly, in education, the emphasis on standardized test scores can lead schools to focus narrowly on test preparation, compromising the broader educational experience ( Nichols and Berliner, 2007 ) . These examples demonstrate how decision systems, when overly focused on specific indicators, can be manipulated, resulting in the corruption of the very processes they aim to enhance. Figure 1 : An example showing that using older snapshots (purple) speeds up convergence to the stable point (orange star) compared to only the latest snapshot (red). The implementation is provided in the code. Given these challenges, it is essential to develop predictive models that are not only accurate but also robust against the performative shifts they may provoke. The work by Perdomo et al. (2020) addresses this challenge within the framework of Repeated Risk Minimization (RRM) , where they explore the dynamics of model retraining in the presence of performative feedback loops. In their approach, the authors propose an iterative method that adjusts the predictive model based on the distributional shifts caused by prior model deployments, aiming to stabilize the model performance despite the continuous evolution of the underlying data distribution. By characterizing the convergence properties of their method, they provide a theoretical guarantee for the stability of the model at a performative equilibrium. Our work extends this framework by leveraging the datasets collected at each snapshot during the retraining process, introducing a new class of algorithms called Affine Risk Minimizers (ARM). By utilizing historical data from previous updates, we show that it is possible to converge to a stable point for a broader class of problems that were previously unsolvable, extending beyond the bounds established in prior analyses ( Mofakhami et al., 2023 ) . We derive a new upper bound under less restrictive assumptions than Mofakhami et al. (2023) and provide the first tightness analysis for the framework in Perdomo et al. (2020) as well as for our newly established rate. Our method, which incorporates historical datasets, demonstrates superior convergence properties both theoretically and experimentally. Converging to a stable point is essential in decision-dependent learning systems. Without stability, iterative retraining may lead to persistent fluctuations, preventing reliable long-term predictions. Prior work has examined convergence rates and the range of problem classes in which iterative schemes can achieve stability ( Li and Wai, 2024 ; Narang et al., 2024 ; Perdomo et al., 2020 ) . This paper provides the first analytical techniques for examining the tightness of the upper bounds for these methods. In addition, we show that the ARM framework ensures convergence to a stable solution for a broader class of problems, mitigating the limitations of existing approaches. Contributions. 1 We establish a new upper bound, enhancing the convergence rate of RRM under less restrictive conditions than ( Mofakhami et al., 2023 ) ; 2 We establish the tightness of the analysis in both the framework proposed by ( Perdomo et al., 2020 ) and our modification of the framework from Mofakhami et al. (2023) ; 3 We introduce a new class of algorithms, named Affine Risk Minimizers (ARM), that provides convergence for a wider class of problems by utilizing linear combinations of datasets from earlier training snapshots; 4 We provide both theoretical and experimental enhancements, showcasing scenarios where ARM improves convergence; 5 Finally, we present the first lower bound techniques for iterative retraining schemes and apply it to both Perdomo et al. (2020) and our modified framework to establish theoretical lower bounds for ARM, detailing the maximum potential improvement in convergence rates achievable through the use of past datasets. 2 Related Work Performative prediction introduces a framework for learning under decision-dependent data ( Perdomo et al., 2020 ) , and has been widely studied in various aspects, from stochastic optimization methods to find stable classifiers ( Li and Wai, 2022 ; Mendler-Dünner et al., 2020 ) to approaches that focus on performative optimal solutions, the minimizer of performative risk ( Miller et al., 2021 ; Jagadeesan et al., 2022 ; Lin and Zrnic, 2024 ) . In this work, we focus our analysis on performative stable solutions, whose deployment removes the need for repeated retraining in changing environments ( Perdomo et al., 2020 ; Mendler-Dünner et al., 2020 ; Jagadeesan et al., 2021 ; Brown et al., 2022 ; Mofakhami et al., 2023 ) . One of the main applications of this framework is strategic classification ( Hardt et al., 2016 ) which involves deploying a classifier interacting with agents who strategically manipulate their features to alter the classifier’s predictions and achieve their favorable outcomes. Strategic Classification has served as a benchmark in the literature of performative prediction ( Perdomo et al., 2020 ; Mendler-Dünner et al., 2020 ; Miller et al., 2021 ; Hardt et al., 2022 ; Mofakhami et al., 2023 ; Narang

Read the complete text