PaperlayerView exact revision on arXiv

Source-linked AI summary

Performative Prediction in a Stateful World

Gavin Brown, Shlomi Hod, Iden Kalemaj

arXiv:2011.03885v3cs.LGcs.GT

TL;DR

Predictions can change the populations they target, yet prior performativity models do not capture how the current population state shapes its response. This paper models that dependence and analyzes retraining algorithms, showing convergence results under stated assumptions and examining groups that adapt at different rates.

  • Problem

    Predictions can change target-population behavior, while classifier-only response models omit dependence on the population’s current state.

    Source: §1 · p. 1

  • Method

    The paper models population response as a state-dependent transition and analyzes repeated risk minimization and a delayed variant.

    Source: §1 · p. 1, §1.2 · p. 3

  • Results

    Under smoothness, strong convexity, and Lipschitz transition assumptions, RRM converges within distance δ in O(log 1/δ) rounds, while equilibrium and optimal pairs lie close under the stated conditions.

    Source: §1.2 · p. 3

  • Takeaways & Limitations

    The model captures groups responding at different rates, and the paper identifies retraining-resource advantages for Delayed RRM in the slow-response setting.

    Source: §3 · pp. 6–7

    The convergence framework focuses on transition maps with ε < 1, which makes repeated application of a fixed classifier contractive.

    Source: §1.2 · p. 3

Abstract

from arXiv · show

Deployed supervised machine learning models make predictions that interact with and influence the world. This phenomenon is called performative prediction by Perdomo et al. (ICML 2020). It is an ongoing challenge to understand the influence of such predictions as well as design tools so as to control that influence. We propose a theoretical framework where the response of a target population to the deployed classifier is modeled as a function of the classifier and the current state (distribution) of the population. We show necessary and sufficient conditions for convergence to an equilibrium of two retraining algorithms, repeated risk minimization and a lazier variant. Furthermore, convergence is near an optimal classifier. We thus generalize results of Perdomo et al., whose performativity framework does not assume any dependence on the state of the target population. A particular phenomenon captured by our model is that of distinct groups that acquire information and resources at different rates to be able to respond to the latest deployed classifier. We study this phenomenon theoretically and empirically.

1 INTRODUCTION

Predictions can alter the populations they target, and this paper extends performative prediction to account for the population’s current state and history. It analyzes when retraining converges in that setting and how response rates can differ across groups.

1.1 Our Framework

  • A stateful response map depends on both the classifier and the previous distribution, extending classifier-only performativity and allowing population history to affect retraining.The paper also notes parameter settings where RRM converges in the stateless model but not the stateful one.Source: §1.1 · p. 2, §1.2 · p. 2
  • Groups that respond to classifiers from different rounds model unequal information-acquisition rates and can sustain distribution shifts under repeated deployment.In the k-group example, each group responds to a classifier from a different number of rounds ago.Source: §1 · p. 1, §1.1 · p. 2

1.2 Our Results

  • Under smoothness, strong convexity, and Lipschitz transition assumptions, RRM converges to an equilibrium pair within distance δ in O(log 1/δ) rounds.Delayed RRM also converges under similar assumptions, within distance δ in O(log2 1/δ) rounds; the paper analyzes a finite-sample version of RRM as well.Source: §1.2 · p. 3
  • Delayed RRM and RRM converge at similar rates in deployment rounds, but Delayed RRM is superior when retraining resources are the concern.The delayed approach waits for k rounds so all groups can catch up to the latest classifier.Source: §1.2 · p. 3
  • Equilibrium pairs and optimal pairs lie close under Lipschitz and strong-convexity assumptions, and RRM can approximate optimal strategies.An equilibrium need not itself be the optimal outcome.Source: §1.2 · p. 3

1.3 Related Work

  • Related stateful work differs in updating population distributions from prior distributions rather than realized samples; other frameworks omit prior-distribution dependence or focus on stochastic optimization.The paper frames performative prediction as a setting where supervised-learning retraining may suffice, rather than requiring the full complexity of reinforcement learning.Source: §1.3 · p. 4

2 FRAMEWORK AND MAIN RESULTS

The framework models population response as a transition from the previous distribution and the deployed classifier. It gives conditions for repeated risk minimization to converge to a stable pair and relates that pair to long-run optimality.

2 FRAMEWORK AND MAIN RESULTS

  • Each round publishes a classifier, applies the transition map to the previous distribution, and incurs loss on the resulting distribution.The initial distribution is publicly known.Source: §2 · p. 4

2.1 Repeated Risk Minimization and Stable Pairs

  • A stable pair combines a fixed-point distribution with a classifier that minimizes loss on that distribution.At that distribution, the institution can continue using the classifier without retraining.Source: §2.1 · p. 5
  • When α < 1, RRM has a unique stable pair and converges to it at a linear rate.The theorem assumes a jointly sensitive transition map and a jointly smooth, strongly convex loss.Source: §2.1 · p. 5
  • The paper also analyzes finite-sample RERM, which retrains using samples from the previous distribution and can approach a stable pair with high probability.The theorem excerpt specifies a convergence radius δ and probability 1 − p, but does not provide the full sample-size bound in these passages.Source: §2.1 · pp. 5–6
  • Our conditions for convergence of RRM and RERM are similar to, but stricter than, those of Perdomo et al. (2020); their RRM results require only ε < γ β, and Example 4 shows our requirement is necessary.Source: §2.1 · p. 6

2.2 Optimality

  • Under ε < 1, each classifier has a unique fixed-point distribution, and RRM's stable classifier is within 2Lzε/[γ(1 − ε)] of an optimal classifier.Optimality is defined by minimizing a classifier's long-run loss on its corresponding fixed-point distribution.Source: §2.2 · p. 6

3 k GROUPS RESPOND SLOWLY

The section models groups that respond strategically to classifiers from different numbers of rounds earlier, then compares RRM with k-Delayed RRM. The stated theorem gives convergence for both algorithms, while the example illustrates how response sensitivity affects classifier changes.

3 k GROUPS RESPOND SLOWLY

  • k-Delayed RRM updates only after k rounds, when all groups have caught up to the latest classifier; its convergence rate is k times the stateless rate.The algorithm performs RRM on the response map every k rounds.Source: §3 · p. 6
  • Figure 1 presents convergence of RRM and k-Delayed RRM for varying ε at k = 3, plotting the distance between successive θ values against the number of retraining rounds.Source: Figure 1 · p. 7
  • Under the theorem's assumptions, both RRM and k-Delayed RRM converge to θS.The assumptions include a Lipschitz strategic response map and a jointly smooth, strongly convex loss.Source: §3 · p. 7
  • k-Delayed RRM may use fewer retraining rounds, but RRM does not require prior knowledge of the number of groups.The comparison concerns a population partitioned into k subgroups that respond to classifiers from different rounds.Source: §3 · pp. 6–7

4 SIMULATION

The simulation adapts a loan-application model to groups that respond to classifiers at different rates, then compares RRM and k-Delayed RRM. It examines classifier convergence, accuracy, and group-level negative rates.

4 SIMULATION

  • The simulation adapts a loan-application setting and GiveMeSomeCredit dataset to include group-specific responses, then runs RRM and k-Delayed RRM for k = 3, ε ∈ {1, 25, 75}, and 300 rounds.The baseline is a uniform distribution over 18,357 individuals; ε controls the strength of strategic response.Source: §4 · p. 7
  • Larger ε produces a larger feature update by the initially responding advantaged group and a greater distance between the first two trained classifiers.The initial distribution comprises k copies of the baseline, so only the most advantaged group responds strategically at first.Source: §4 · p. 7
  • RRM converged in fewer elapsed rounds than k-Delayed RRM across all parameter settings considered, while the practitioner’s choice depends on whether elapsed time or retraining resources matter more.The paper notes that this comparison is not depicted.Source: §4 · p. 8
  • For ε < 75, both algorithms reach high accuracy much faster than they converge to a stable pair, with little difference in accuracy dynamics.At ε = 75, k-Delayed RRM’s accuracy increases much more slowly than RRM’s.Source: §4 · p. 8
  • Over the first 10 rounds at ε = 25, the most advantaged group received 2.37% more negative predictions than the most disadvantaged group with RRM, and 2.09% more with k-Delayed RRM.The negative rate is the proportion predicted unlikely to default; the gap later converged to the same value across groups, with no clear algorithm advantage in disparity.Source: §4 · p. 8
  • The authors deliberately abstract the model’s operationalization of disadvantage and information access, and do not claim to fully capture these societal concepts.The additional experiments vary groups’ initial distributions.Source: §4 · p. 8

5 DISCUSSION

The discussion connects stateful performativity to social questions about structural change and disparate effects over time. It also limits the practical interpretation of the convergence guarantees and identifies success measures and applications for future study.

5 DISCUSSION

  • Adding population state opens discussion of how prediction histories shape behavior, including structural changes and disparate impacts across groups over time.The authors identify the slowly responding groups setting as a starting point for studying performativity, fairness, and information disparities.Source: §5 · p. 8
  • The convergence guarantees are conditional because the theory constrains the loss or transition function, while practical verification of a fixed deterministic transition function and its sensitivity is unclear.The authors view RRM as sensible when the world’s response is not too sensitive to history or institutional choices.Source: §5 · p. 8
  • Future work could study measures of institutional success beyond convergence and other applications of performativity.The discussion notes that regret lacks a clear interpretation when the adversary adapts to the player.Source: §5 · p. 8

6 SOCIETAL IMPACT

The paper describes its model as a simple, abstract account of repeated decision-making and states that it does not believe the work has direct ethical or social consequences.

6 SOCIETAL IMPACT

  • The paper uses a simple, abstract model of repeated decision-making and does not claim direct ethical or social consequences.Source: §6 · p. 8

A PROOFS OF THEOREMS

The appendix states lemmas used in the theorem proofs, including a bound relating fixed-point distributions to their classifiers. It also invokes convexity and strong-convexity results in its proof setup.

A PROOFS OF THEOREMS

  • The appendix introduces the lemmas as tools for the theorem proofs and notes that its second lemma follows from Perdomo et al. (2020), Theorem 3.5.Source: A PROOFS OF THEOREMS · p. 11
  • The appendix lists a convex differentiable-function lemma on a closed convex set and a risk-minimization lemma under jointly smooth, strongly convex loss assumptions.Source: A PROOFS OF THEOREMS · p. 11
  • For an ε-jointly sensitive transition map with ε < 1, the Wasserstein distance between fixed-point distributions is bounded by ε/(1 − ε) times the Euclidean distance between their classifiers.Source: A PROOFS OF THEOREMS · p. 11
  • The proof outline derives the fixed-point distribution comparison by applying joint sensitivity to the transition map at the two classifier-distribution pairs.Source: A PROOFS OF THEOREMS · p. 11

A.1 Proof of Theorem 1

This proof establishes convergence guarantees for Delayed RRM under the stated smoothness, strong-convexity, and sensitivity conditions, and shows that a contractive joint update has a unique stable pair.

A.1 Proof of Theorem 1

  • Under the theorem’s stated conditions, Delayed RRM reaches a classifier within distance δ of θS using O(log²(1/δ)) deployments.Each main-loop iteration deploys the same classifier at most logarithmically many times.Source: §A.1 · p. 12
  • Repeated deployment of a fixed classifier approximates its unique fixed-point distribution within the procedure’s tolerance when ε < 1.The proof uses contraction of the transition map to establish the fixed point and bound the approximation error.Source: §A.1 · p. 12

A.2 Proof of Theorem 4

  • The proof of Theorem 4 obtains a unique fixed point when the joint map is contractive, and this point satisfies the stable-pair conditions.The stated contraction coefficient is ε(1 + β/γ) < 1.Source: §A.2 · p. 13

A.3 Proof of Theorem 5

The finite-sample RERM proof establishes conditions for iterates to enter and remain in a neighborhood of a stable pair; the next proof bounds how far a stable classifier can be from an optimal classifier.

A.3 Proof of Theorem 5

  • Under Assumption 1, RERM iterates outside the δ-neighborhood move closer to the stable pair, while iterates inside remain within that neighborhood.The finite-sample update uses an empirical distribution to compute the retrained classifier.Source: §A.3 · pp. 13–14

A.4 Proof of Theorem 6

  • Theorem 6 bounds the distance between stable and optimal classifiers using transition sensitivity, strong convexity, and the loss’s Lipschitzness in z.The proof compares the losses at the stable and optimal classifiers on their respective fixed-point distributions.Source: §A.4 · pp. 14–15

A.5 Proof of Theorem 7

For the slow-response group setting, the proof shows convergence of RRM and k-Delayed RRM, with a rate that depends on the model parameters and the number of groups.

A.5 Proof of Theorem 7

  • At rounds that are multiples of k, k-Delayed RRM’s iterates correspond to RRM in the stateless setting.The groups’ mixture components are identical at those rounds.Source: §A.5 · p. 15
  • For RRM, the classifier-error convergence rate is analyzed through a linear recurrence around the stable classifier.The proof defines δt as the distance between θt and θS before introducing the recurrence.Source: §A.5 · pp. 15–16
  • RRM and k-Delayed RRM converge to the stable classifier at an exponential rate depending on ε, β, γ, and k.The proof states convergence for both algorithm sequences in the slow-response setting.Source: §A.5 · pp. 15–16

B.1 Additional Details

The additional experiments use a credit-score simulation and test whether the reported algorithm behavior persists across different group initializations.

B.1 Additional Details

  • The simulation models loan applicants’ strategic feature changes in a finite population of 18,357 individuals drawn from GiveMeSomeCredit.The dataset supplies both the initial distribution for each group and the baseline distribution.Source: §B.1 · p. 16
  • The response model varies sensitivity ε and restricts individuals to changing a subset of features designated as strategic.The remaining features are unchanged after the individual’s response.Source: §B.1 · p. 17

B.2 Different Initial Distributions

  • Across ten different group initializations, the reported findings mostly persist, with slower RRM convergence for some initializations when ε = 75.Figure 4 compares RRM and k-Delayed RRM across three metrics, with each line representing a random group initialization.Source: §B.2 · p. 17, Figure 4 · p. 17

Related papers

Loading 2011.03885v3…