Performative Prediction
A deployed model changes the data it will be retrained on: credit scores change who applies, prices change demand. Retrain a seller whose sales move the price, find where retraining settles and where it should have aimed, let a leader anticipate its follower, and watch retraining spiral in or out as the data become more sensitive.
Built from the reading notes of the Bilevel Performative Games project, which studies S. Lu, “Bilevel Optimization with Coupled Decision-Dependent Distributions” (ICML 2023, PMLR 202, 22758–22789), and W. Yan and X. Cao, “Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions” (NeurIPS 2024). Both build on J. Perdomo, T. Zrnic, C. Mendler-Dünner and M. Hardt, “Performative Prediction” (ICML 2020). Bilevel algorithms follow S. Ghadimi and M. Wang (2018); monotone games follow F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities (Springer, 2003). Results from the papers are labelled with their numbering; the questions and examples are written for this page. For how this subject connects to the others, see the roadmap.
Gradient descent, momentum and mini-batches
Fitting a network means minimizing a loss over its weights. Gradient descent does it by walking downhill: from wherever you are, take a small step in the direction in which the loss decreases fastest. Which direction is that? The directional derivative answers it.
Start here: the directional derivative
Stand at a point
the second equality by the chain rule applied to
- it is largest,
, at : along the gradient, the steepest way up; - it is zero at
: along the contour line through ; - it is smallest,
, at : along , the steepest way down.
That last line is the whole reason gradient descent steps along
The idea
The update. To decrease a loss
The gradient says which way to go, not how far: the learning rate
Show the computation
The gradient step is
Explore: descent on a valley
Worked example
With
: the per-step factors in each coordinate, and . and . So : the steep coordinate is solved in one step, and after that. Reaching takes steps.With
?Factors
and . The second coordinate flips sign and grows by 1.5 each step: divergence, since .What is the best fixed
, and how fast is it?Balance the two factors:
, so and both have size . About 35 steps for three digits. Momentum improves this to roughly per step.
Check your understanding
Why step against the gradient rather than along it?
is smallest at : the loss falls fastest opposite to the gradient.- Along the gradient the step would be too long.Length is set by
; direction is the issue.
On an ill-conditioned quadratic (
must be below for the steep direction, which makes progress in the flat direction tiny.- The gradient points away from the minimum.It points downhill, just not at the minimum: it zigzags across the valley.
Doubling the batch size
That is the variance, not the standard deviation. : the noise comes from the data, not the batch.Averaging more independent samples reduces it.
Practice
The gradient of a quadraticThree lines
For
Outline
.Why?
, using .- So
, and the minimizer solves .Why?
. The gradient vanishes at the minimizer. - Then
.Why?
, using ; subtract .
Momentum on a lineThe characteristic equation
Apply heavy ball to
Outline
- Substituting
gives the recursion.Why?
. - It converges iff both roots of
have modulus below 1.Why?
Solutions are combinations of
and (or for a double root). - For a real quadratic
, that means and (Jury's test).Why?
Here
and , so the condition is . - So
.Why?
Solve
.
Momentum enlarges the stable range from
Contractions and fixed points
Almost every convergence result on this page has the same shape: some update shrinks distances by a fixed factor, so repeating it homes in on a single point. Gradient descent is the first example.
The idea
Gradient descent is a contraction. If
The recipe used below. Every existence result on this page takes the form “(how much a perturbation moves the gradient)
Check your understanding
- To
, halving the distance each step. - To
.Check: . Solve . - It depends on the start.A contraction has one fixed point, and every start converges to it.
Gradient descent on
- Yes, with factor
.Check the steep direction too: . - No: along
the factor is .
An SGD analysis gives
.Here : the recursion only gives . .
Bilevel problems and the hypergradient
In a bilevel problem one optimizer, the leader, is judged at the best response of another, the follower. To do gradient descent on the leader's cost you have to differentiate through the follower's choice.
The idea
Two routes from
Implicit differentiation. There is no formula for
In practice.
Explore
Check your understanding
In the figure, when does the leader's best
- When
or : the follower doesn't react, or the leader doesn't care what it does. - Only when
.The shift is ; it vanishes when either factor does.
Why does the hypergradient formula need
- So that
is invertible and is a single, differentiable point. - So that
is convex. can be nonconvex even then; the condition is about the follower.
Practice
A quadratic followerThe hypergradient by hand
Let
Outline
, so .Why?
.- Directly:
, so .Why?
Substitute
and differentiate; is symmetric. - From the formula:
, , , , giving the same answer.Why?
.
Nash equilibria and monotone games
When several players optimize at once, none of them can simply minimize: each one's best choice depends on the others'. An equilibrium is a profile where nobody wants to move alone.
The idea
Shared constraints. If the players share a constraint such as
Nash versus Stackelberg. A Nash player uses only
Worked example
Row picks U or D, Column picks L or R, at the same time. Payoffs (Row, Column), higher is better:
Find the Nash equilibrium of the simultaneous game.
Row prefers U whatever Column does (
, ). Against U, Column prefers L ( ). So , with payoffs ; in every other cell someone wants to switch.Now Row commits first and Column sees the commitment. What does Row do?
Column replies L to U and R to D. So Row compares U
payoff 2 with D payoff 3, and commits to D, an action it never plays in the simultaneous game. Anticipating the reply is worth 1 to Row.
Check your understanding
Two players,
- Yes, with
: the cross terms cancel in . - No:
is not the gradient of any function.Monotonicity doesn't need to be a gradient.
For one player, a strongly monotone game is the same as:
- A strongly convex cost.
- A smooth cost.Smoothness bounds curvature from above; monotonicity bounds it from below.
Stable versus optimal
When the data depend on the deployed model, “the best model for the data” is ambiguous: best for the data it will produce, or best for the data you would get if you deployed something else? The two questions have different answers.
The idea
A game against the data. Think of the data as a second player that responds to
Explore
Worked example
A seller chooses a quantity
With the data frozen at
, what does retraining choose? , minimized at . So .Find the stable point.
, so . RRM converges to it iff .Find the optimal point.
, so . The stable seller is a price-taker; the optimal seller accounts for its own price impact and sells less, like a monopolist.
Check your understanding
In the figure, set
- It oscillates around
with growing swings: the map has slope , so it is not a contraction. - It converges to
instead.Retraining never knows about ; its only fixed point is .
A platform knows nothing about how users react to its model. Which point can it hope to reach?
- The stable point, by retraining on fresh data.
- The optimal point, by retraining on fresh data.Retraining optimizes against frozen data, so its fixed points are stable, not optimal.
Why retraining converges
Retraining is a contraction when the data are not too sensitive to the model. The proof is three lines, and every existence result in the two papers below is a version of it.
The idea
The proof. Write
One step at a time. RRM solves a full training problem per deployment. Greedy SGD (deploy, take one stochastic step on fresh data, redeploy) also reaches
Check your understanding
In the seller example,
- Contraction factor
; sharp, since has slope exactly . - Contraction factor
.The bound is linear in .
Doubling the strong convexity
- Allows data twice as sensitive.
- Nothing; regularization doesn't affect the data.It doesn't change the data, but it makes the retrained model move less when the data move.
Practice
Sensitivity of a location shiftBoth directions
Let
Outline
- Upper bound: couple the two laws through the same noise.
Why?
Take
and with the same . Then always. - Lower bound: use the 1-Lipschitz test function
.Why?
Duality gives
.
Performative games
Now several players move at once, and each player's data depend on everyone's decisions. Retraining becomes “solve the game on frozen data, redeploy”, and stable and Nash become two different equilibria.
The idea
- The PSE exists, is unique, and is the linear-rate limit of RRM over equilibria if
. The proof is the three-line argument of the previous module with in place of . For identical players with it reduces to . - The distance between PSE and NE is at most (size of
) (monotonicity left after performativity), and vanishes with the sensitivities. It is proved by duality, since a game has no single strongly convex objective. - A decentralized primal–dual algorithm, in which players gossip estimates of each other's decisions and keep a consensus copy of the shared multiplier, has regret
against the PSE, the same order as without performativity.
Worked example
Two symmetric sellers, no constraint. Seller
Find the PSE.
With data frozen, seller
plays . At a symmetric fixed point : .Find the NE.
. Setting gives , so symmetrically .Who sells more, and why does
matter?PSE sellers sell more. The NE seller accounts only for its own price impact, weight
; at it is the single seller of Stable versus optimal, at it internalizes only half the impact. This is a Cournot competitor versus a price-taker.
Check your understanding
In the existence condition, why does
- Because player
's data are moved by a weighted average of everyone's moves, so no single player shifts them by more than the largest weight allows. - It's a normalization with no effect.With
it divides the sum over players by , which is why the condition doesn't get worse as players are added.
If every
- They coincide: with fixed data
. - The NE might not exist.With fixed data the game is strongly monotone by assumption, so its NE exists and is unique.
Bilevel performative prediction
Put performative data into a bilevel problem: the leader's decision moves the follower's data, and the follower's response moves the leader's data. Whether retraining settles now depends on two sensitivities, and they play very different roles.
The idea
What is frozen? As defined, the stable point freezes the follower's data but lets the leader's data
Why
Explore
Worked example
The figure's problem:
Find the follower's response with data frozen at
. .Find the Bi-RRM step
.Minimize
: , so .Find the stable point and the contraction factor, and compare with Thm. 1.
and . Here with , the curvature of , so the bound is exact. The slope is negative, so the iterates alternate sides of , and they diverge once .
Check your understanding
Suppose the follower's data don't depend on the leader at all (
- Yes, in one step: the contraction factor
is 0. - No:
is too large.In Bi-RRM the leader's data respond to the candidate inside the argmin, so they don't depend on the last deployment.
The Bi-SGD condition has a term
- Bi-SGD samples the leader's data from the deployed follower, so comparing with
means moving the leader's data with the follower's direct response, even when . - From the noise in the stochastic gradients.Noise affects the rate's constants, not the sensitivity condition.
Practice
Where stable and optimal part waysA gap from the follower alone
Take
Outline
- The performative response is
, so .Why?
. Then , with derivative . - With the follower's data frozen at
, , so .Why?
The frozen objective
has derivative in , whatever is. - So
, nonzero even though .Why?
The optimal leader accounts for the extra reaction of its follower through the follower's data; the stable leader treats those data as fixed. It is the price-taker example of Stable versus optimal, one level down.
Any bound on the stable–optimal gap in a bilevel problem therefore needs a term in the follower's sensitivity