Performative Prediction

Juan C. Perdomo; Tijana Zrnic; Celestine Mendler-Dünner; Moritz Hardt

Source-linked AI summary

Performative Prediction

Juan C. Perdomo, Tijana Zrnic, Celestine Mendler-Dünner, Moritz Hardt

arXiv:2002.06673v4Feb 16, 2020cs.LGcs.GTstat.ML

TL;DR

Performative prediction addresses the gap between supervised learning and decisions that change the outcomes being predicted. The paper formalizes model-induced distributions and repeated risk minimization, showing when retraining converges to stable points and how this framework extends to strategic classification.

Problem
Supervised-learning theory typically evaluates predictions against distributions that can change when decisions act on those predictions, while the induced distribution map is generally unknown.
Method
The paper defines performative risk and performative stability, then analyzes repeated risk minimization as retraining on the distribution induced by the previous model.
Results
Under strong convexity and suitable Lipschitz and smoothness assumptions, retraining converges to performative stability, and strong convexity places stable points near performative optima.
Takeaways & Limitations
Performative prediction reframes retraining as a natural equilibrating dynamic and treats strategic classification as a special case with retraining guarantees.
Takeaways & Limitations
The paper leaves open whether a tight gap between procedures reflects a fundamental difference or an artifact of the analysis.

Abstract

from arXiv · show

When predictions support decisions they may influence the outcome they aim to predict. We call such predictions performative; the prediction influences the target. Performativity is a well-studied phenomenon in policy-making that has so far been neglected in supervised learning. When ignored, performativity surfaces as undesirable distribution shift, routinely addressed with retraining. We develop a risk minimization framework for performative prediction bringing together concepts from statistics, game theory, and causality. A conceptual novelty is an equilibrium notion we call performative stability. Performative stability implies that the predictions are calibrated not against past outcomes, but against the future outcomes that manifest from acting on the prediction. Our main results are necessary and sufficient conditions for the convergence of retraining to a performatively stable point of nearly minimal loss. In full generality, performative prediction strictly subsumes the setting known as strategic classification. We thus also give the first sufficient conditions for retraining to overcome strategic feedback effects.

1 Introduction

Performative prediction studies models whose deployment changes the outcomes they predict, turning distribution shift and retraining into an equilibrium problem. The paper formalizes this setting, analyzes repeated risk minimization, and connects it to strategic classification.

1 Introduction: Deploying predictions can change the target distribution, as in credit pricing, traffic management, policing, recommendations, and trading.A high interest rate assigned after predicting elevated default risk can further increase that customer's default risk.
1 Introduction: Ignoring performativity appears as distribution shift, prompting repeated retraining that is often viewed as chasing a moving target.The paper instead treats retraining as potentially reflecting an underlying equilibration process.
1 Introduction: The framework represents each model as inducing a distribution over features and outcomes, then evaluates the model on that induced distribution.This mapping from model parameters to distributions is the framework’s key conceptual device, and the resulting objective is performative risk.
1 Introduction: Repeated risk minimization retrains on the distribution produced by the previous model, and convergence makes the model optimal for the distribution it entails.The paper analyzes both the population procedure and its finite-sample counterpart.
1 Introduction: If the loss is smooth and strongly convex and D(·) is sufficiently Lipschitz, repeated risk minimization converges linearly to performative stability.If any one of these assumptions fails, repeated risk minimization can fail to converge at all.
1 Introduction: Strong convexity also places stable points and performative optima in a small neighborhood, while strategic classification becomes a special case with guarantees for repeated risk minimization.The paper presents strategic classification as a case study and evaluates it in a semi-synthetic setting based on a real dataset.

2 Framework and main definitions

The framework distinguishes performative optimality from performative stability by making the induced distribution part of model evaluation. Stability is a fixed-point condition for retraining, and the two concepts generally differ.

2 Framework and main definitions: Performative risk evaluates model parameters using expected loss under the distribution D(θ) induced by deploying those parameters.Unlike standard supervised learning, the distribution being evaluated depends on the model itself.
2 Framework and main definitions: Performative optimality minimizes performative risk, whereas performative stability minimizes loss on the distribution induced by the deployed model.The paper expresses stability through decoupled performative risk, separating the model inducing the distribution from the model evaluated on it.
2 Framework and main definitions: In the biased-coin example, the performative optimum is θPO = µ/(1 − 2ε), while the stable point is θPS = µ/(1 − ε).The two solutions coincide when ε = 0 and diverge as performative strength increases.
2 Framework and main definitions: A performatively stable model is a fixed point of risk minimization and therefore eliminates the need for retraining after deployment.Stability and optimality are generally distinct: either type of solution need not satisfy the other property.
2 Framework and main definitions: The biased-coin construction has a unique performatively stable point, and stability and optimality coincide there if and only if ε = 0.When D(θ) is constant across θ, performative optima, stable solutions, and static supervised-learning solutions coincide.

3 When retraining converges to stable points

The paper analyzes retraining as an equilibrating dynamic in performative prediction, identifying conditions under which repeated risk minimization and gradient descent converge to stable points. Finite-sample variants remain near stable points with sufficiently large samples, while removing key regularity assumptions can cause divergence.

Optimization procedures: Repeated risk minimization (RRM) repeatedly minimizes loss on the distribution induced by the previous model, while repeated gradient descent (RGD) takes one gradient step on that induced objective.Both procedures are analyzed at the population level and extended to finite samples.
Assumptions: Convergence requires regularity of the distribution map, formalized as ε-sensitivity measured using Wasserstein-1 distance.ε-sensitivity captures how much the induced distribution changes when model parameters change.
Repeated risk minimization: Under joint smoothness, strong convexity, and sufficiently small sensitivity, RRM converges to a unique performatively stable point at a linear rate.The analysis attributes contraction to strong convexity, with smoothness and sensitivity controlling distribution-shift effects.
Failure conditions: RRM can fail to converge when strong convexity or joint smoothness is absent, and the analysis shows these convergence assumptions are tight.A constructed example produces alternating iterates 1,−1,1,−1 despite positive ε and β.
Repeated gradient descent: RGD also converges linearly to a unique stable point when ε < γ (β+γ)(1+1.5ηβ) and η satisfies the stated step-size bound.This result relaxes RRM’s requirement for an exact optimization oracle.
Finite-sample analysis: Finite-sample RRM and gradient descent converge with high probability to a small neighborhood around a stable point when each iteration uses sufficiently many samples.Outside the neighborhood, large samples preserve contraction; inside it, sampling noise prevents guaranteed contraction but limits escape.

4 Relating performative optimality and stability

The paper separates performative stability from performative optimality and studies when stable points exist and approximate minimal performative risk. Stable points exist under weaker assumptions on compact parameter spaces, while strong convexity and Lipschitz conditions bring the two solution concepts close.

Existence: If the parameter space is compact and the loss is convex and jointly continuous, a performatively stable point exists under ε-sensitivity.This establishes existence under weaker loss assumptions than the main convergence results.
Performative risk: A performative risk objective can be non-convex or even concave despite smooth, strongly convex losses and an ε-sensitive distribution map.This makes directly minimizing performative risk more challenging than finding stable points.
Approximate optimality: When the loss is Lipschitz in data and strongly convex, stable points and performative optima lie in a small neighborhood of each other.Quadratic regularization can extend approximate convergence to smooth convex losses that are not strongly convex.

5 A case study in strategic classification

The case study casts strategic classification as performative prediction, where agents adapt features after deployment and induce a model-dependent distribution. It analyzes retraining theoretically and empirically, finding convergence for sufficiently small sensitivity and divergence when sensitivity is too large.

Strategic classification is a two-player game in which an institution deploys a classifier and agents adapt features to improve their outcomes.
The institution’s Stackelberg equilibrium classifier exactly matches performative optimality: minimal loss on the distribution induced by strategic adaptation.
Repeated retraining on induced distributions is repeated risk minimization, for which the paper gives sufficient conditions to overcome strategic effects.
The simulations use dynamic credit scoring with logistic regression, strategic and non-strategic features, and agent feature manipulation governed by sensitivity ε.
During RRM, the experiments track performative risk and accuracy across optimization and post-deployment distribution-shift phases.
For small ε, RRM converges in a few iterations, whereas large ε causes divergence; RGD shows the same convergence-versus-divergence pattern but at a slower rate.

6 Discussion and Future Work

The discussion reframes retraining as an equilibrating dynamic for performative prediction and connects the framework to strategic classification, reinforcement learning, and concept drift. It also identifies a convergence gap between exact risk minimization and gradient descent and outlines broader applications.

Performative prediction is presented as a formal framework combining causality and game theory for models whose deployment changes observed data distributions.
Retraining fixed points are performatively stable points, and strong convexity supports convergence, whereas weak convexity alone is insufficient.
Exact repeated risk minimization converges for every ε < γ/β, while the corresponding bound for vanishing-step-size repeated gradient descent is ε < γ/(β+γ).
The paper connects performative prediction to strategic classification, where retraining can overcome strategic effects under stated conditions.
Reinforcement learning can be viewed as performative prediction, with policy choices affecting visited-state and action distributions; RRM then resembles offline off-policy learning.
The discussion identifies performativity across fraud detection, predictive policing, recommendations, and adaptive online games as sources of concept drift.
In a two-feature visualization, small ε leads RRM toward a stable point near the performative optimum, while large ε produces oscillation and failure to converge.

B.2 Experimental details

The experimental analysis uses a balanced credit-scoring dataset, verifies the induced distribution map’s sensitivity and objective smoothness, and implements RRM and RGD with regularized logistic loss. The appendix also details the contraction proof underlying RRM convergence.

Experimental setup: The base dataset contains n = 18,357 approximately balanced examples, 10 features, and 3 designated strategic features.
Sensitivity verification: The induced distribution map shifts each feature vector from x−εθ to x−εθ′, yielding transport distance at most ε∥θ−θ′∥2.
Objective regularity: The experiments use regularized logistic loss with γ = 1000/n and verify joint smoothness while accounting for parameter-dependent strategic feature norms.
Optimization details: RRM approximates exact minimization to tolerance 10^-8 using gradient descent with backtracking line search, while RGD uses a fixed step size.
Convergence proof: The proof establishes the update map’s contraction using strong convexity, joint smoothness, optimal transport sensitivity, and first-order optimality conditions.

D.2 Proof of Proposition 3.6

The proposition’s counterexamples distinguish strong from weak convexity and show that excessive sensitivity can eliminate stability or make repeated risk minimization oscillate or diverge.

These constructions establish that the convergence bound is tight and that strong convexity is necessary for general RRM convergence guarantees.
A regularized hinge-loss construction makes RRM alternate between 2 and −1/(2ε), demonstrating oscillation under weak convexity.
With squared loss and β = γ, RRM does not contract when ε ≥ γ/β.
In a linear fixed-point example, θPS = 1/(1−ε) for ε > 1, while ε = 1 admits no performatively stable point and ε > 1 can drive iterates to ±∞.

D.3 Proof of Theorem 3.8

The proof establishes convergence of retraining by showing the relevant update map is contractive under suitable step-size and sensitivity conditions, then extends the argument to finite-sample iterates and proves existence of a stable fixed point.

Fixed point: Contractivity yields a unique fixed point θPS satisfying the population gradient condition and hence performative stability.The argument invokes the Banach fixed-point theorem and convexity of the loss.
Finite-sample convergence: With high probability, repeated empirical risk minimization contracts toward θPS when iterates lie outside a δ-ball.The proof uses Wasserstein concentration, ε-sensitivity, and a union bound across iterations.
Finite-sample convergence: Inside the δ-ball, empirical retraining cannot move iterates far from θPS except with negligible probability.The argument bounds the next iterate using the triangle inequality and a tighter Wasserstein-distance estimate.
Existence: A set-valued best-response map has a fixed point because it is upper hemicontinuous with nonempty compact convex values.Berge’s Maximum Theorem and Kakutani’s Theorem provide the existence argument.

D.6 Proof of Proposition 4.2

The proposition constructs an example where performative risk is concave even though the loss is strongly convex and the distribution map is less sensitive than the convexity parameter.

Construction: The example uses a binary feature, a Bernoulli outcome model, an affine classifier, and squared loss.The parameter domain is Θ = [0,1], with constraints on μ and ε.
Risk shape: The example’s performative risk is quadratic in θ.This follows from direct calculation under the specified distribution and model.
Risk shape: The performative risk is concave in θ even though ε < γ.This establishes the proposition under the stated smoothness and strong-convexity conditions.

D.8 Proof of Corollary 5.1

The corollary connects retraining to strategic classification by showing that convergence to a performatively stable classifier also yields proximity to the institution’s Stackelberg equilibrium.

Convergence: Repeated risk minimization converges at a linear rate to a performatively stable point θPS.The result is attributed to Theorem 3.5.
Strategic classification: The performatively stable point is close in parameter space to the institution’s Stackelberg equilibrium classifier θSE.The connection follows from Theorem 4.3.
Strategic classification: Lipschitzness of the loss implies closeness in objective value between the stable classifier and the Stackelberg equilibrium.The proof bounds the objective difference using the Kantorovich-Rubinstein Lemma.

E Approximately minimizing performative risk via regularization

Adding quadratic regularization makes repeated risk minimization converge in settings where the original objective is convex but not strongly convex, while retaining near-optimal performative risk.

Motivation: Regularization addresses cases where smooth convex objectives may not make repeated risk minimization converge.The regularized objective adds a quadratic penalty centered at θ0.
Guarantee: Under the proposition’s Lipschitz, smoothness, sensitivity, boundedness, and convexity assumptions, an α choice guarantees convergence to a stable point θregPS.The parameter space has diameter 1 and ε < 1.
Special case: When ε = 0, the regularized repeated-risk-minimization limit is performatively optimal.In the insensitive-distribution case, stability and optimality coincide for the limit point.
Regularization choice: The regularized loss is α-strongly convex and α + β-jointly smooth, enabling an α choice that satisfies the contraction requirement.One stated choice is α = √εβ/(1 −ε).
Guarantee: The regularized stable point approximately minimizes the original performative risk.The proof compares its objective value with that of an original performative optimum.