Performative Learning Theory

AI summary

Overview

Research area: Statistical machine learning theory, specifically the theory of performative prediction — settings where a model's predictions change the data distribution the model is trying to predict.

Technical level: Advanced. The paper works with Wasserstein distances, covering-number entropy integrals, empirical process theory, strong convexity, and distributionally robust optimization. It assumes familiarity with Vapnik–Chervonenkis-style learning theory.

Scope: The paper initiates "performative learning theory" (PLT) by embedding performative predictions into statistical learning theory and proving generalization, excess-risk and generalization-gap bounds when performative effects act on a sample, on the population, or on both.

What This Paper Is About

Existing performative prediction work (Perdomo et al., 2020; Brown et al., 2022) studies the stability and optimality of models when predictions shift the whole population, but does not ask how well a model trained on a finite sample generalizes under performativity. This paper asks exactly that question: if a model changes the sample it is trained on, the population it is deployed on, or both, what can still be guaranteed about its generalization error? The authors build a learning-theoretic framework that answers this, and illustrate it with real German labor-market data on prediction-informed assignments to job trainings.

Key Contributions

1. A conceptual framework for performative generalization. Section 2 formalizes what generalization means when the sample, the population, or both react to predictions, and derives four research questions (RQ1–RQ4) spanning excess risk under sample performativity, performative excess risk, cumulative performative excess risk, and the inferential gap between repeated empirical risk minimization (RERM) and repeated risk minimization (RRM). A table maps how classical ERM, online learning and the established performative prediction (PP) setup fit into this taxonomy, including a note that one configuration was partly answered by Kirev et al. (2025) and another was asymptotically answered by Li et al. (2025b).

2. Generalization bounds under generic performative effects. The paper proves bounds on excess risk (Theorem 3.7, RQ1), performative excess risk (Theorem 3.10, RQ2), and the generalization gap (Theorems 3.13 and 3.15), requiring only a compact convex parameter space plus Conditions 3.1–3.3 (strong convexity of the loss in the parameter, Wasserstein sensitivity of the transition map, and Lipschitz/continuity assumptions on the loss). No specific functional form of the transition map is assumed.

3. A practical corollary for tightening bounds. Corollary 3.11 states that if predictions have performative effects on both sample and population, one should use the initial fit θ̂₀ on out-of-sample data and estimate the shift it will cause from observed sample shifts, in order to obtain the tightest generalization guarantees.

4. An illustration on real administrative data. Section 4 applies the bounds to prediction-informed assignment to job trainings, using German Federal Employment Agency administrative labor market records from 1975 to 2017 (raw data with over 60 million rows).

Main Findings

• Worst case: a self-negating population and a self-fulfilling sample. The authors' central intuition is that in the worst case the population negates predictions while the sample deceptively fulfills them, creating what they call an "empirical echo chamber." Technically, self-negating and self-fulfilling predictions are cast as min-max and min-min risk functionals in Wasserstein space, respectively, which lets the authors use empirical process theory for dual characterizations of locally distributionally robust learning (Gao and Kleywegt, 2023) and favorable learning (Jiang and Xie, 2025).

• A trade-off between changing the world and learning about it. For fixed T, the bound in Theorem 3.7 goes to zero as n → ∞ if and only if m = o(n), where m is the maximum number of sample units that change across iterations. The bound generally grows in m, so helping more people in Example (B) (increasing m among n clients) costs generalization to new, unseen clients. Figure 1.3 shows this trade-off on the job-seeker data: the generalization gap bound grows as more people are assigned to job trainings.

• The amplification factor ε(1 + L_a). The "performative term" in the bound is governed by ε(1 + L_a). It grows exponentially in the number of performative sample updates T when ε(1 + L_a) > 1, linearly in T when ε(1 + L_a) = 1, and is bounded otherwise.

• Two opposing effects of retraining. (I) Without knowledge of the transition map Tr, retraining on d̂₀, …, d̂_T produces models that generalize worse than the initial θ̂₀, because the bounds grow in T both through m and through the geometric factor ([ε(1 + L_a)]^T − 1) / (ε(1 + L_a) − 1). (II) Retraining can nevertheless improve the bounds, because observing d̂₁, …, d̂_T allows more efficient estimation of Tr than the conservative Lemma 3.9, which uses only the single iteration with the most reacting units; the bound in Theorem 3.10 is thereby tightened via Corollary 3.11.

• Rates are comparable across scenarios. The proof in Appendix D.5 gives explicit expressions for A(m, n), C(n) and K(T, m, n), showing that the bounds in Theorems 3.7 and 3.10 grow at similar rates.

• Wider applicability than prior partial answers. The results cover all Lipschitz-continuous transition maps as in Perdomo et al. (2020) and Brown et al. (2022), and subsume performative shifts on any subsets of Y and X — generalizing Kirev et al. (2025), who addressed binary classification under linear performative shift of Y | X and marginal X.

• The inferential gap question (RQ4) is answered only asymptotically by prior work. Li et al. (2025b) shows √n(θ̂_t − θ_t) converges in distribution to N(0, Σ_t) for stateless performativity; the paper states that finite-sample analysis and extension to the stateful case are yet to be conducted.

Methodology in Plain English

The authors keep the assumptions as weak as possible. They assume data live in a compact subset of Euclidean space and that the transition map describing how predictions change the distribution is "Wasserstein sensitive" — meaning small changes in the current distribution or in the model parameter lead to bounded changes in the next distribution, without pinning down any particular functional form.

The proof strategy is twofold. First, they bound the Wasserstein distance between the initial empirical sample and the true population (Lemma 3.4, applying Fournier and Guillin, 2015), giving a high-probability statement of the form 1 − C_a exp(−C_b n β₀^ν). Second, they bound the in-sample performative drift across iterations (Lemma 3.5) and the population-level performative shift (Lemma 3.9, derived via Wald's method by treating the observed sample response rate m/n as an estimate of an unobserved Bernoulli parameter s). These divergence bounds are then converted into bounds on differences of expected losses using the Kantorovich–Rubinstein lemma, and combined by a union bound.

Because predictions may shift mass outside the support of the original distribution, the authors use covering numbers (Kolmogorov and Tikhomirov, 1959; Talagrand, 2021) rather than Rademacher or Gaussian complexity as the measure of hypothesis-class richness. The worst-case generalization error is written as a supremum of risk over a Wasserstein ball around the true distribution, and the conceptual difference from ordinary distributionally robust optimization is that the performative generalization gap also involves the best-case (infimum) risk on the sample.

Why This Matters

Impact on research. The paper reframes performative prediction from a question about stability and equilibria into a question about learnability, opening a route for classical tools from statistical learning theory (covering numbers, empirical process theory, Wasserstein geometry) to be applied to models that change their own data. It also supplies a precise statement of when repeated retraining helps or hurts, and shows that observed sample responses can be used as a signal about the unobserved population response.

Real-world applications (from the paper).

• Routing and navigation apps: drivers avoid routes with predicted congestion, making those predictions less accurate; the bounds speak to whether a model tested on users in San Francisco generalizes to all users in the Bay Area.
• Public employment services: German job centers assign scarce job training programs based on predicted long-term unemployment risk; because training raises the probability of finding a job, the predictions have a performative effect. The bounds speak to generalizing from trial job centers in Bavaria to all job centers in Germany.
• Recommender systems: the paper cites gaming of recommender systems as an instance of performative prediction.
• Early warning systems in high schools and strategic behavior in selection processes (e.g., credit/insurance selection), which the paper cites as established performative settings.

The bounds make the "performative response rate" m/n — the observable fraction of units that changed behavior in response to the predictions — a central, estimable quantity, which is the kind of number an organization can actually track.

Industry relevance. Any organization that A/B tests or pilots a predictive model on a subset of users before a full rollout is in the setting this paper formalizes. The practical takeaway is counterintuitive and actionable: when performativity is present, the initial fit evaluated out-of-sample plus an estimate of the shift it will cause can give tighter guarantees than a model repeatedly retrained on its own distorted data.

Future Directions

• Finite-sample analysis of the inferential gap. RQ4 is currently answered only asymptotically, via the central limit theorem of Li et al. (2025b) in the stateless case. The paper states that finite-sample analysis and the extension to the stateful case remain to be conducted.
• Tighter bounds under additional structure. The authors acknowledge that the price of not assuming a functional form for the transition map is looser bounds, and that adding conditions yields tighter results (as Conditions 3.12 and 3.14 do). Further structural assumptions could tighten the bounds more.
• Extending the theory to the fully stateful, multi-round population case. RQ3 (cumulative performative excess risk when a model is trained T times on the sample and then T̃ − T times on the population) and scenarios where retraining happens sequentially or simultaneously on both sample and population are framed as open research questions.
• Estimating the transition map better. Corollary 3.11 exploits multiple observed sample shifts to estimate the performative shift more efficiently than Lemma 3.9; developing sharper estimators of the transition map and of the population-level response rate is a natural continuation.

Target Audience

Researchers in machine learning theory and statistical learning theory who study generalization, distribution shift, or performative prediction; methodologists working on distributionally robust and favorable optimization; and quantitatively trained practitioners — data scientists in charge of phased model rollouts, and analysts in public employment services, transportation, and recommender systems — who need to reason about what a model's performance on a pilot population implies for the wider population it will itself influence.

Authors’ abstract

Performative predictions influence the very outcomes they aim to forecast. We study performative predictions that affect a sample (e.g., only existing users of an app) and/or the whole population (e.g., all potential app users). This raises the question of how well models generalize under performativity. For example, how well can we draw insights about new app users based on existing users when both of them react to the app's predictions? We address this question by embedding performative predictions into statistical learning theory. We prove generalization bounds under performative effects on the sample, on the population, and on both. A key intuition behind our proofs is that in the worst case, the population negates predictions, while the sample deceptively fulfills them. We cast such self-negating and self-fulfilling predictions as min-max and min-min risk functionals in Wasserstein space, respectively. Our analysis reveals a fundamental trade-off between performatively changing the world and learning from it: the more a model affects data, the less it can learn from it. Moreover, our analysis results in a surprising insight on how to improve generalization guarantees by retraining on performatively distorted samples. We illustrate our bounds in a case study on prediction-informed assignments of unemployed German residents to job trainings, drawing upon administrative labor market records from 1975 to 2017 in Germany.