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.

InteractiveGoodfellow–Bengio–Courville, Ch. 8: Optimization for Training Deep Models

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 p on a surface f(x,y). In one dimension you can only go left or right, but here you can head off in any direction. Pick a unit vector v. The directional derivative is the slope of f in that direction:

Dvf(p)=limh→0f(p+hv)−f(p)h=∇f(p)⋅v,

the second equality by the chain rule applied to h↦f(p+hv). Since ∇f⋅v=‖∇f‖‖v‖cos⁡ϕ, where ϕ is the angle between v and the gradient, the slope as you turn v all the way round is a cosine wave of height ‖∇f(p)‖:

  • it is largest, +‖∇f‖, at ϕ=0: along the gradient, the steepest way up;
  • it is zero at ϕ=±π/2: along the contour line through p;
  • it is smallest, −‖∇f‖, at ϕ=π: along −∇f, the steepest way down.

That last line is the whole reason gradient descent steps along −∇f. Try it below: drag the direction round and find the minimum of the curve on the right.

Contours of f(x,y)=12x2+y2+13sin⁡(2x)sin⁡(y). Drag the point p, and drag the tip of v round the circle. ∇f(p), −∇f(p).
The slope Dvf(p) for every direction v, by its angle. your v. The lowest point is −∇f.

The idea

The update. To decrease a loss L, step in its steepest downhill direction, −∇L, found above:

wt+1=wt−α∇L(wt).

The gradient says which way to go, not how far: the learning rate α is a choice. In machine learning L(θ)=1N∑i=1Nℓ(fθ(xi),yi) is the average loss over the data, and computing its gradient through the network's layers is backpropagation.

Quadratics, one direction at a time. For L(w)=12(w−w⋆)⊤H(w−w⋆) with H symmetric positive definite, ∇L=H(w−w⋆), so
wt+1−w⋆=(I−αH)(wt−w⋆).
Show the computation

The gradient step is wt+1=wt−αH(wt−w⋆). Subtract w⋆ from both sides: wt+1−w⋆=(wt−w⋆)−αH(wt−w⋆)=(I−αH)(wt−w⋆). If Hu=λu, then (I−αH)u=(1−αλ)u, so the error's component along u is multiplied by 1−αλ at every step, independently of the other components. It shrinks exactly when |1−αλ|<1, that is 0<α<2/λ; for all directions at once, α<2/λmax.

Along an eigenvector of H with eigenvalue λ, the error is multiplied by 1−αλ each step. Steep directions (large λ) need α<2/λmax or the iterates blow up; flat directions (small λ) then crawl at rate 1−αλmin. The ratio κ=λmax/λmin sets the speed: about κ steps per factor of e.
Momentum (heavy ball). Keep part of the previous step:
wt+1=wt−α∇L(wt)+β(wt−wt−1).
In a flat valley the steps all point the same way and add up; across a narrow valley they alternate and cancel. Well tuned, it needs about κ steps instead of κ.
Mini-batches. With millions of data points, use the average gradient over a random batch Bt of |B| of them: gt=1|B|∑i∈Bt∇ℓi. It is unbiased, E[gt]=∇L, but noisy, with variance shrinking like 1/|B|. The noise is the price of cheap steps, and it keeps the iterates jittering near the minimum unless α is decreased.

Explore: descent on a valley

Contours of L(w)=12(w12+κw22); the minimum is at the centre. Drag the start. the first 60 steps.

Worked example

L(w)=12(w12+10w22), so H=diag(1,10). Start at w0=(1,1).

  1. With α=0.1: the per-step factors in each coordinate, and wt.

    1−0.1⋅1=0.9 and 1−0.1⋅10=0. So w1=(0.9,0): the steep coordinate is solved in one step, and wt=(0.9t,0) after that. Reaching |w1|<10−3 takes t≥66 steps.

  2. With α=0.25?

    Factors 0.75 and 1−2.5=−1.5. The second coordinate flips sign and grows by 1.5 each step: divergence, since α>2/λmax=0.2.

  3. What is the best fixed α, and how fast is it?

    Balance the two factors: 1−α=−(1−10α), so α=2/11 and both have size 9/11=κ−1κ+1≈0.82. About 35 steps for three digits. Momentum improves this to roughly κ−1κ+1≈0.52 per step.

Check your understanding

Why step against the gradient rather than along it?

  1. ∇L⋅v=‖∇L‖‖v‖cos⁡ϕ is smallest at ϕ=π: the loss falls fastest opposite to the gradient.
  2. Along the gradient the step would be too long.Length is set by α; direction is the issue.
The gradient points uphill, in the direction of fastest increase. Gradient ascent (+α∇L) maximizes, as in policy-gradient methods that maximize expected return.

On an ill-conditioned quadratic (κ=100) plain gradient descent is slow because:

  1. α must be below 2/λmax for the steep direction, which makes progress in the flat direction tiny.
  2. The gradient points away from the minimum.It points downhill, just not at the minimum: it zigzags across the valley.
One learning rate serves all directions. Momentum, preconditioning and adaptive methods (Adam) are different ways around this.

Doubling the batch size |B| changes the mini-batch gradient's standard deviation by a factor of:

  1. 1/2That is the variance, not the standard deviation.
  2. 1/2
  3. 1: the noise comes from the data, not the batch.Averaging more independent samples reduces it.
The average of |B| independent gradients has variance σ2/|B|. Twice the work per step buys only 2 less noise, which is one reason small batches are popular.

Practice

The gradient of a quadraticThree lines

For L(w)=12w⊤Hw−q⊤w with H symmetric, show ∇L=Hw−q, find the minimizer, and rewrite gradient descent as wt+1−w⋆=(I−αH)(wt−w⋆).

Outline
  1. ∇(12w⊤Hw)=Hw.
    Why?

    ∂k12∑ijHijwiwj=12∑j(Hkj+Hjk)wj=(Hw)k, using Hjk=Hkj.

  2. So ∇L=Hw−q, and the minimizer solves Hw⋆=q.
    Why?

    ∂kq⊤w=qk. The gradient vanishes at the minimizer.

  3. Then wt+1−w⋆=(I−αH)(wt−w⋆).
    Why?

    wt+1=wt−α(Hwt−q)=wt−αH(wt−w⋆), using q=Hw⋆; subtract w⋆.

Momentum on a lineThe characteristic equation

Apply heavy ball to L(w)=λ2w2. Show that et=wt satisfies et+1=(1+β−αλ)et−βet−1, and find when it converges for β=0.5, λ=1.

Outline
  1. Substituting ∇L=λw gives the recursion.
    Why?

    wt+1=wt−αλwt+β(wt−wt−1)=(1+β−αλ)wt−βwt−1.

  2. It converges iff both roots of z2−(1+β−αλ)z+β have modulus below 1.
    Why?

    Solutions are combinations of z1t and z2t (or tzt for a double root).

  3. For a real quadratic z2+a1z+a0, that means |a0|<1 and |a1|<1+a0 (Jury's test).
    Why?

    Here a0=β=0.5 and a1=−(1.5−α), so the condition is |1.5−α|<1.5.

  4. So 0<α<3.
    Why?

    Solve |1.5−α|<1.5.

Momentum enlarges the stable range from α<2 to α<2(1+β).

Read and checkPerdomo et al. (2020), §3; Banach's fixed-point theorem

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

Contraction. A map G is a contraction with factor q<1 if ‖G(x)−G(x′)‖≤q‖x−x′‖ for all x,x′. Applying G brings any two points closer by at least the factor q.
Banach's fixed-point theorem. A contraction of a complete metric space (for instance Rd, or a closed subset of it) has exactly one fixed point x∗=G(x∗), and the iterates xk+1=G(xk) satisfy ‖xk−x∗‖≤qk‖x0−x∗‖ from any start.

Gradient descent is a contraction. If f is m-strongly convex and L-smooth, the map G(x)=x−α∇f(x) has Jacobian I−α∇2f, whose eigenvalues lie in [1−αL,1−αm]. So G is a contraction with factor q=max(|1−αm|,|1−αL|), which is 1−αm when α≤1/L. Its fixed point is where ∇f=0: the minimizer. Existence, uniqueness and the linear rate of the convergence-rates module on the Gradient Descent page all follow at once.

The recipe used below. Every existence result on this page takes the form “(how much a perturbation moves the gradient) ÷ (curvature) <1”. The curvature is strong convexity m for one learner, and the monotonicity constant μ for a game.

Stochastic steps. With noisy gradients the squared error typically obeys ek+1≤(1−cαk)ek+Kαk2: each step contracts by 1−cαk but adds noise Kαk2. With αk=a/k this gives ek=O(1/k), the usual SGD rate, provided ac>1; for smaller a it only gives O(k−ac).

Check your understanding

G(x)=12x+3 on R. Where do the iterates xk+1=G(xk) go, from any start?

  1. To 6, halving the distance each step.
  2. To 3.Check: G(3)=4.5≠3. Solve x=12x+3.
  3. It depends on the start.A contraction has one fixed point, and every start converges to it.
|G(x)−G(x′)|=12|x−x′|, so q=12, and the fixed point solves x=12x+3, i.e. x=6.

Gradient descent on f(x)=12(x12+10x22) with α=0.25. Is the update a contraction?

  1. Yes, with factor 0.75.Check the steep direction too: 1−αL=1−2.5.
  2. No: along x2 the factor is |1−0.25⋅10|=1.5>1.
The step must be below 2/L=0.2 for the steep direction to shrink; at 0.25 the x2 coordinate is multiplied by −1.5 each step and blows up.

An SGD analysis gives ek+1≤(1−αk)ek+αk2 (so c=K=1). Which step size gives ek=O(1/k)?

  1. αk=0.5/k.Here ac=0.5<1: the recursion only gives O(k−1/2).
  2. αk=2/k.
The contraction ∏(1−a/j)≈k−a must beat the accumulated noise, which decays like 1/k; that needs a>1. Papers often write “αk=Θ(1/k)” and leave this constant implicit.
InteractiveGhadimi–Wang (2018), §2; Lu (2023), Remark 1

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

Bilevel problem.
minx F(x):=f(x,y∗(x))wherey∗(x)=arg⁡miny ℓ(x,y).
The upper level (UL, leader) picks x with cost f; the lower level (LL, follower) responds with y∗(x) with cost ℓ. Examples: meta-learning, where x is a shared initialization and y the model adapted to one task, e.g. ℓ(x,y)=loss(y)+λ2‖y−x‖2; and Stackelberg games, where x is a commitment and y∗(x) the reply (Nash equilibria and monotone games).

Two routes from x to the cost. x enters F directly and through the follower, so the chain rule gives

∇F(x)=∇xf(x,y∗)⏟follower held fixed+Dy∗(x)⊤∇yf(x,y∗)⏟follower reacts.

Implicit differentiation. There is no formula for y∗(x), but it satisfies ∇yℓ(x,y∗(x))=0 for every x. Differentiating that identity in x gives ∇yx2ℓ+∇yy2ℓDy∗=0.

The hypergradient. If ℓ(x,⋅) is strongly convex, so that ∇yy2ℓ is invertible,
∇F(x)=∇xf−∇xy2ℓ[∇yy2ℓ]−1∇yf,all evaluated at (x,y∗(x)).

In practice. y∗(x) is replaced by a running estimate y, giving the surrogate ∇―f(x,y) (the same formula at y), and the inverse Hessian is approximated, for example by a truncated Neumann series. Double-loop methods run several inner steps on y per outer step on x, each warm-started from the last y. Single-loop methods take one step on each per iteration and track the follower's error ‖yk−y∗(xk)‖, whose target moves by O(step size) whenever x moves.

Explore

f=12(x−1)2+cy, ℓ=12(y−bx)2, so y∗(x)=bx. the leader's true cost F(x)=f(x,y∗(x)) and its minimizer. the cost with the follower frozen at its reply to x=1; its minimizer, x=1, is what a leader ignoring the reaction plays.

Check your understanding

In the figure, when does the leader's best x equal the naive x=1?

  1. When b=0 or c=0: the follower doesn't react, or the leader doesn't care what it does.
  2. Only when b=c.The shift is −bc; it vanishes when either factor does.
∇F=x−1+bc, so x∗=1−bc. The reaction term Dy∗⊤∇yf=b⋅c is the whole difference between a Nash player and a leader.

Why does the hypergradient formula need ℓ(x,⋅) to be strongly convex?

  1. So that ∇yy2ℓ is invertible and y∗(x) is a single, differentiable point.
  2. So that F is convex.F can be nonconvex even then; the condition is about the follower.
With several minimizers the follower's response isn't a function of x, and the implicit function theorem needs the Hessian in y to be invertible.

Practice

A quadratic followerThe hypergradient by hand

Let ℓ(x,y)=12y⊤Ay−y⊤Bx with A≻0, and f(x,y)=12‖x‖2+g⊤y. Find y∗(x), Dy∗ and ∇F, directly and from the formula.

Outline
  1. y∗(x)=A−1Bx, so Dy∗=A−1B.
    Why?

    ∇yℓ=Ay−Bx=0.

  2. Directly: F(x)=12‖x‖2+g⊤A−1Bx, so ∇F=x+B⊤A−1g.
    Why?

    Substitute y∗ and differentiate; A−1 is symmetric.

  3. From the formula: ∇xf=x, ∇xy2ℓ=−B⊤, ∇yy2ℓ=A, ∇yf=g, giving the same answer.
    Why?

    x−(−B⊤)A−1g=x+B⊤A−1g.

Read and checkFacchinei–Pang (2003), §§1.4, 2.3

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

Nash equilibrium. Player i picks ai and pays Ji(ai,a−i), where a−i collects everyone else's actions. Its best response is BRi(a−i)=arg⁡minaiJi(ai,a−i). A profile a∗ is a Nash equilibrium (NE) if ai∗∈BRi(a−i∗) for every i: a fixed point of the best-response map.
Pseudogradient and monotonicity. With actions θi∈Rd and convex costs, stack each player's gradient in its own variable: Φ(θ)=(∇θ1J1(θ),…,∇θnJn(θ)). The game is μ-strongly monotone if ⟨Φ(θ)−Φ(θ′),θ−θ′⟩≥μ‖θ−θ′‖2. For one player this is exactly μ-strong convexity.
Equilibria as variational inequalities (Facchinei–Pang, Thm. 2.3.3). On a nonempty, closed, convex set K, the NE are the points with ⟨Φ(θ∗),θ−θ∗⟩≥0 for all θ∈K. If Φ is continuous and strongly monotone there is exactly one, and gradient play θk+1=θk−αΦ(θk) contracts toward it like gradient descent.

Shared constraints. If the players share a constraint such as ∑igi(θi)≤0 (a market capacity, say), equilibria are usually not unique. The standard target is the variational equilibrium, the solution of the inequality above on the joint feasible set, in which all players share one Lagrange multiplier.

Nash versus Stackelberg. A Nash player uses only ∇θiJi and treats the others as fixed. A Stackelberg leader anticipates the follower's reply and uses the hypergradient of the previous module. A Stackelberg game is a bilevel problem.

Worked example

Row picks U or D, Column picks L or R, at the same time. Payoffs (Row, Column), higher is better: (U,L)→(2,1), (U,R)→(4,0), (D,L)→(1,0), (D,R)→(3,2).

  1. Find the Nash equilibrium of the simultaneous game.

    Row prefers U whatever Column does (2>1, 4>3). Against U, Column prefers L (1>0). So (U,L), with payoffs (2,1); in every other cell someone wants to switch.

  2. 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, J1=12θ12+θ1θ2, J2=12θ22−θ1θ2. Is the game strongly monotone?

  1. Yes, with μ=1: the cross terms cancel in ⟨Φ(θ)−Φ(θ′),θ−θ′⟩.
  2. No: Φ is not the gradient of any function.Monotonicity doesn't need Φ to be a gradient.
Φ(θ)=(θ1+θ2, θ2−θ1), whose Jacobian (11−11) has symmetric part I. Monotonicity only sees the symmetric part, so μ=1 and the unique NE is θ=0.

For one player, a strongly monotone game is the same as:

  1. A strongly convex cost.
  2. A smooth cost.Smoothness bounds curvature from above; monotonicity bounds it from below.
With one player Φ=∇J, and ⟨∇J(θ)−∇J(θ′),θ−θ′⟩≥μ‖θ−θ′‖2 is a standard characterization of μ-strong convexity.
InteractivePerdomo et al. (2020), Defs. 2.2–2.3, §3

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

Distribution map. Deploying θ produces data Z∼D(θ). The performative risk PR(θ)=EZ∼D(θ)ℓ(Z;θ) has θ in two places, the loss and the data. The decoupled risk DR(θ,θ′)=EZ∼D(θ)ℓ(Z;θ′) separates them: data from θ, loss at θ′.
Optimal and stable. θPO is performatively optimal if it minimizes PR. θPS is performatively stable if θPS∈arg⁡minθ′DR(θPS,θ′): it is optimal for the data it itself produces.
Repeated risk minimization (RRM). Retrain on the current data and redeploy: θt+1=G(θt):=arg⁡minθ′DR(θt,θ′). Its fixed points are exactly the stable points.

A game against the data. Think of the data as a second player that responds to θ through D. A stable point is the Nash notion: best-respond to the data, which in turn come from you. An optimal point is the Stackelberg notion: anticipate how the data respond. Stable points need no model of D, since retraining finds them; optimal points need one.

Explore

retraining map G(θ)=1−εθ, the diagonal, and the iterates. They meet the diagonal at the stable point.
θt by round. θPS, where retraining settles. θPO, what the seller should aim for.

Worked example

A seller chooses a quantity θ and sees a price Z∼N(m−εθ,1): selling more lowers the price. Its loss is cost minus revenue, ℓ(Z;θ)=12θ2−Zθ. (The figure has m=1.)

  1. With the data frozen at D(θ), what does retraining choose?

    DR(θ,θ′)=12θ′2−θ′EZ=12θ′2−θ′(m−εθ), minimized at θ′=m−εθ. So G(θ)=m−εθ.

  2. Find the stable point.

    θ=m−εθ, so θPS=m/(1+ε). RRM converges to it iff |G′|=ε<1.

  3. Find the optimal point.

    PR(θ)=12θ2−θ(m−εθ)=(12+ε)θ2−mθ, so θPO=m/(1+2ε). 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 ε=1.2. What happens to retraining?

  1. It oscillates around θPS with growing swings: the map has slope −1.2, so it is not a contraction.
  2. It converges to θPO instead.Retraining never knows about θPO; its only fixed point is θPS.
The stable point still exists (1/2.2), but retraining can't reach it: each round overshoots by more than the last.

A platform knows nothing about how users react to its model. Which point can it hope to reach?

  1. The stable point, by retraining on fresh data.
  2. The optimal point, by retraining on fresh data.Retraining optimizes against frozen data, so its fixed points are stable, not optimal.
Reaching θPO needs ∇PR, which includes how D(θ) moves with θ: a model of the users.
Read and checkPerdomo et al. (2020), Def. 3.1, Thms. 3.5, 4.3

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

Wasserstein-1 distance. W1(P,Q)=infE‖Z−Z′‖ over all ways of pairing Z∼P with Z′∼Q: the least average distance mass has to move to turn P into Q. Its key property (Kantorovich–Rubinstein duality): if z↦g(z) is β-Lipschitz, then ‖EPg−EQg‖≤βW1(P,Q). The Gradient Flows page covers the Wasserstein-2 relative.
ε-sensitivity. D is ε-sensitive if W1(D(θ),D(θ′))≤ε‖θ−θ′‖: moving the model by Δ moves the data by at most ε‖Δ‖. Example: Z=Z0+εAθ with ‖A‖≤1, a location shift.
RRM contracts (Perdomo et al., Thm. 3.5). If ℓ(z;⋅) is γ-strongly convex, z↦∇θℓ(z;θ) is β-Lipschitz, and D is ε-sensitive, then ‖G(θ)−G(δ)‖≤εβγ‖θ−δ‖. So if εβ/γ<1, there is a unique stable point and RRM converges to it linearly.

The proof. Write θ′=G(θ), δ′=G(δ), Δ=θ′−δ′ and gθ(⋅)=ED(θ)∇ℓ. Optimality gives ⟨gθ(θ′),Δ⟩≤0≤⟨gδ(δ′),Δ⟩. Then

γ‖Δ‖2≤⟨gθ(θ′)−gθ(δ′),Δ⟩strong convexity≤⟨gδ(δ′)−gθ(δ′),Δ⟩the two optimality conditions≤βW1(D(δ),D(θ))‖Δ‖≤βε‖θ−δ‖‖Δ‖.same point, two data laws
The third line is the one to compare in every later version: which Lipschitz constant multiplies W1, and what the sensitivity is measured against.

Stable is close to optimal (Perdomo et al., Thm. 4.3). If moreover z↦ℓ(z;θ) is Lz-Lipschitz, then ‖θPO−θPS‖≤2Lzε/γ.

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 θPS, at rate O(1/t) (Mendler-Dünner et al., NeurIPS 2020). That is the template for the single-loop algorithms in the next two modules.

Check your understanding

In the seller example, γ=1, β=1 and D is ε-sensitive. What does the theorem predict, and is it sharp?

  1. Contraction factor ε; sharp, since G(θ)=1−εθ has slope exactly −ε.
  2. Contraction factor ε2.The bound is linear in ε.
∇θℓ=θ−z is 1-Lipschitz in z, ℓ is 1-strongly convex in θ, and a shift of the mean by εΔ is a W1 distance of exactly ε|Δ|.

Doubling the strong convexity γ of the loss (say, by adding a regularizer) does what to the condition εβ/γ<1?

  1. Allows data twice as sensitive.
  2. 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.
More curvature means a given gradient shift moves the minimizer less, so retraining reacts less to each data shift.

Practice

Sensitivity of a location shiftBoth directions

Let D(θ)=N(m−εθ,1) on R. Show W1(D(θ),D(θ′))=ε|θ−θ′|.

Outline
  1. Upper bound: couple the two laws through the same noise.
    Why?

    Take Z=m−εθ+N and Z′=m−εθ′+N with the same N∼N(0,1). Then |Z−Z′|=ε|θ−θ′| always.

  2. Lower bound: use the 1-Lipschitz test function h(z)=z.
    Why?

    Duality gives W1≥|Eh(Z)−Eh(Z′)|=ε|θ−θ′|.

Read and checkYan–Cao (2024), §§2–4

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 game. Player i chooses θi∈Ωi and solves minθiEξi∼Di(θ)Ji(ξi;θi,θ−i) subject to a shared constraint ∑jgj(θj)≤0. Sensitivity is weighted by an influence matrix P=(pij), rows summing to 1: W1(Di(θ),Di(θ′))≤εi(∑jpij‖θj−θj′‖2)1/2. The frozen-data pseudogradient is assumed μ-strongly monotone.
Two equilibria. At a Nash equilibrium (NE) each player's data respond to its own deviation. At a performatively stable equilibrium (PSE) all data are frozen at the deployed profile. In gradient form,
∇PR(θ)=Gθ(θ)⏟data frozen at θ+Hθ(θ)⏟own move shifts own data,
and the PSE solves the equilibrium condition for G, the NE for G+H. PSE players are price-takers; NE players see their own price impact.
Results (Yan–Cao, Thms. 3.3, 3.5, 4.2).
  • The PSE exists, is unique, and is the linear-rate limit of RRM over equilibria if 1μ(∑iLi2εi2maxjpij)1/2<1. The proof is the three-line argument of the previous module with Φ in place of ∇ℓ. For identical players with pij=1/n it reduces to Lε/μ<1.
  • The distance between PSE and NE is at most (size of H) ÷ (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 O(T3/4) against the PSE, the same order as without performativity.

Worked example

Two symmetric sellers, no constraint. Seller i has Ji=12θi2−ξiθi with price ξi∼N(m−ε(pθi+(1−p)θj),1), p∈[12,1]: its own sales weigh p, the rival's 1−p.

  1. Find the PSE.

    With data frozen, seller i plays Eξi=m−ε(pθi+(1−p)θj). At a symmetric fixed point θ=m−εθ: θipse=m/(1+ε).

  2. Find the NE.

    PRi=12θi2−θi(m−εpθi−ε(1−p)θj). Setting ∂θiPRi=0 gives (1+2εp)θi+ε(1−p)θj=m, so symmetrically θine=m/(1+ε+εp).

  3. Who sells more, and why does p matter?

    PSE sellers sell more. The NE seller accounts only for its own price impact, weight p; at p=1 it is the single seller of Stable versus optimal, at p=12 it internalizes only half the impact. This is a Cournot competitor versus a price-taker.

Check your understanding

In the existence condition, why does maxjpij appear rather than 1?

  1. Because player i'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.
  2. It's a normalization with no effect.With pij=1/n it divides the sum over n players by n, which is why the condition doesn't get worse as players are added.
Bounding ∑jpij‖Δj‖2≤maxjpij‖Δ‖2 is the step that turns per-player sensitivities into one contraction factor for the whole profile.

If every εi=0, how are the PSE and NE related?

  1. They coincide: with fixed data H=0.
  2. The NE might not exist.With fixed data the game is strongly monotone by assumption, so its NE exists and is unique.
H measures how a player's own move shifts its own data; with no performativity it vanishes, and both notions are the ordinary Nash equilibrium.
InteractiveLu (2023), §§3–6

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

The problem (Lu, eq. (1)).
minx EZ∼Dx(y∗(x))f(x,y∗(x);Z)s.t.y∗(x)=arg⁡miny EZ∼Dy(x)ℓ(x,y;Z).
Dy(x) feeds the follower and is moved by the leader, with sensitivity εy; Dx(y∗) feeds the leader and is moved by the follower's response, with sensitivity εx. The motivating case is meta-learning where each task's users react to the deployed models.
Optimal and stable (Lu, Defs. 1–2). Let y∗(x;x′) be the follower's response to the candidate x with its data frozen at the deployed x′. The bilevel optimal point xO minimizes the true UL risk. The bilevel stable point xS minimizes the UL risk with the follower's data frozen at xS.

What is frozen? As defined, the stable point freezes the follower's data but lets the leader's data Dx(y∗(x;xS)) still move with the candidate x. The paper's analysis of its stochastic algorithm instead characterizes the limit with the leader's data frozen at Dx(y∗(xS)) too. The two agree when εx=0; it is worth being explicit about which one is meant.

Bilevel retraining contracts (Lu, Thm. 1). Bi-RRM solves the bilevel problem with the follower's data frozen at the last deployment. Under strong convexity at both levels and data-Lipschitz gradients, Jacobians and Hessians, it contracts with factor Cxyεxεy+Cyεy, for constants Cxy,Cy built from these.

Why εy multiplies everything. The leader's last deployment affects its next decision only through the follower's data: deploy x, the follower's data move (εy), the follower's response moves, and that either enters the leader's loss directly or moves the leader's data (a further εx). Every path starts with εy, so there is no term in εx alone.

Bi-SGD (Lu, Thm. 2). One stochastic step on y and one on x (along a biased surrogate hypergradient) per deployment, single loop. If Cxεx+Cxyεxεy+Cyεy≤LF4(LF+γx) and the step sizes are Θ(1/r), then E‖xr−xS‖2+E‖yr−y∗(xS)‖2=O(1/r). The new εx-only term appears because the leader's data now come from the current follower iterate.

Explore

the Bi-RRM map R(x)=1−εyx2, the diagonal and the iterates.
xr by round, and the stable point xS=1/(2+εy).

Worked example

The figure's problem: f(x,y;Z)=12(x−a)2+12y2 (no data, so εx plays no role), ℓ(x,y;Z)=12(y−x−Z)2, Dy(x)=N(εyx,1), and a=1.

  1. Find the follower's response with data frozen at x′.

    y∗(φ;x′)=φ+EZ=φ+εyx′.

  2. Find the Bi-RRM step R(xr).

    Minimize g(φ)=12(φ−a)2+12(φ+εyxr)2: 2φ−a+εyxr=0, so R(xr)=(a−εyxr)/2.

  3. Find the stable point and the contraction factor, and compare with Thm. 1.

    xS=a/(2+εy) and |R′|=εy/2. Here Cy=1/γx with γx=2, the curvature of g, so the bound Cyεy=εy/2 is exact. The slope is negative, so the iterates alternate sides of xS, and they diverge once εy>2.

Check your understanding

Suppose the follower's data don't depend on the leader at all (εy=0) but the leader's data are very sensitive (εx large). Does Bi-RRM converge?

  1. Yes, in one step: the contraction factor Cxyεxεy+Cyεy is 0.
  2. No: εx 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.
With εy=0, nothing in the retraining problem depends on the previous deployment, so R is constant.

The Bi-SGD condition has a term Cxεx that the Bi-RRM condition lacks. Where does it come from?

  1. Bi-SGD samples the leader's data from the deployed follower, so comparing with xS means moving the leader's data with the follower's direct response, even when εy=0.
  2. From the noise in the stochastic gradients.Noise affects the rate's constants, not the sensitivity condition.
The follower reacts to x through its loss (‖Dy∗‖≤Cℓxy/γy) even with fixed data, and that reaction moves the leader's data by εx times as much.

Practice

Where stable and optimal part waysA gap from the follower alone

Take f(x,y;Z)=12(x−a)2+cy, ℓ(x,y;Z)=12(y−x−Z)2 and Dy(x)=N(εyx,1). The leader's loss doesn't involve Z, so εx=0. Compute xO and xS.

Outline
  1. The performative response is y∗(x)=(1+εy)x, so xO=a−c(1+εy).
    Why?

    y∗(x)=x+EDy(x)Z=x+εyx. Then F(x)=12(x−a)2+c(1+εy)x, with derivative x−a+c(1+εy).

  2. With the follower's data frozen at xS, y∗(x;xS)=x+εyxS, so xS=a−c.
    Why?

    The frozen objective 12(x−a)2+c(x+εyxS) has derivative x−a+c in x, whatever xS is.

  3. So |xO−xS|=|c|εy, nonzero even though εx=0.
    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 εy, not only the leader's εx.