Performative prediction

Retraining contracts because strong convexity turns a small change in the gradient into a small move of the minimizer. Fix $\theta,\theta'$ and write $\Delta G=G(\theta)-G(\theta')$. Strong convexity of $\mathrm{DPR}(\theta,\cdot)$ around its minimizer plus first-order optimality of $G(\theta')$ for $\mathrm{DPR}(\theta',\cdot)$ give $$\gamma\|\Delta G\|^2\le\mathbb E_{\mathcal D(\theta')}g(Z)-\mathbb E_{\mathcal D(\theta)}g(Z),\qquad g(z)=\Delta G^\top\nabla_\theta\ell(z;G(\theta')).$$ The right side is one function integrated against two nearby laws; joint smoothness makes $g$ $\beta\|\Delta G\|$-Lipschitz in $z$, so Kantorovich-Rubinstein and sensitivity bound it by $\varepsilon\beta\|\Delta G\|\,\|\theta-\theta'\|$, and Banach's fixed-point theorem completes the proof. Read the constant as in the implicit function theorem: inverse Hessian ($1/\gamma$) times the cross-derivative of the gradient in the data ($\beta$) times the data's response to the model ($\varepsilon$).

Every assumption is needed, and the threshold $\varepsilon\beta/\gamma=1$ is sharp. Each counterexample uses point-mass data moving linearly with $\theta$ and drops one assumption. Without strong convexity, the linear loss $\beta y\theta$ on $[-1,1]$ with $Y=\varepsilon\theta$ gives $\mathrm{DPR}(\theta,\phi)=\varepsilon\beta\theta\phi$, so $G(\theta)=-\mathrm{sign}(\theta)$ and RRM flips between $\pm1$ for every $\varepsilon>0$: the argmin of a merely convex function jumps when the data move a little. Without smoothness, a large hinge term makes the minimizer jump through the kink and RRM cycles. At the threshold, squared loss with $Y=1+\varepsilon\theta$ gives $G(\theta)=1+\varepsilon\theta$, slope exactly $\varepsilon\beta/\gamma$; for $\varepsilon>1$ the stable point exists but repels. The loss $\tfrac\gamma2\theta^2-\beta\theta y$ makes the threshold sharp at every ratio (my note, not in the paper). In static learning strong convexity speeds up convergence; here, without it, retraining need not converge at all.

One gradient step per deployment also contracts, by co-coercivity of the gradient. Split the change in the expected gradient into a part from moving the model and a part from moving the data. The data part is at least $-\varepsilon\beta\|\Delta\|^2$ by the vector form of Kantorovich-Rubinstein. The model part is bounded below by co-coercivity of smooth strongly convex functions, $$\Delta^\top(\nabla f(\theta)-\nabla f(\theta'))\ge\frac{\beta\gamma}{\beta+\gamma}\|\Delta\|^2+\frac1{\beta+\gamma}\|\nabla f(\theta)-\nabla f(\theta')\|^2,$$ and the spare squared-gradient term absorbs the $\eta^2$ term of the expansion when $\eta\le2/(\beta+\gamma)$. The step differentiates the loss with the data frozen and never differentiates through $\mathcal D$, so its fixed points satisfy the first-order condition for $\mathrm{DPR}(\theta,\cdot)$ at $\theta$, which is stability: RGD finds stable points, the same targets as RRM.

Finite samples cost a factor of 2 in the threshold, through a triangle inequality in $W_1$. Rerun Step 1 with the empirical law, using $$W_1(\mathcal D_{n_t}(\theta_t),\mathcal D(\theta_{PS}))\le W_1(\mathcal D_{n_t}(\theta_t),\mathcal D(\theta_t))+\varepsilon\|\theta_t-\theta_{PS}\|.$$ The Fournier-Guillin rate makes the first term at most $\varepsilon\delta$ once $n_t\gtrsim(\varepsilon\delta)^{-m}\log(t/p)$, with a union bound over rounds; outside the $\delta$-ball the sampling error is smaller than the shift, so the iterate contracts at rate $2\varepsilon\beta/\gamma$, and inside it stays. The $(\varepsilon\delta)^{-m}$ is the curse of dimensionality of empirical $W_1$, inherited from the proof route.

Stable and optimal points are close, by sandwiching one decoupled risk. Compare the two points on the stable point's own data, with $\Delta=\theta_{PO}-\theta_{PS}$. Optimality gives $\mathrm{DPR}(\theta_{PO},\theta_{PO})\le\mathrm{DPR}(\theta_{PS},\theta_{PS})$; stability plus strong convexity gives $\mathrm{DPR}(\theta_{PS},\theta_{PS})+\tfrac\gamma2\|\Delta\|^2\le\mathrm{DPR}(\theta_{PS},\theta_{PO})$; Kantorovich-Rubinstein gives $\mathrm{DPR}(\theta_{PS},\theta_{PO})-\mathrm{DPR}(\theta_{PO},\theta_{PO})\le L_z\varepsilon\|\Delta\|$. Together, $$\tfrac\gamma2\|\Delta\|^2\le L_z\varepsilon\|\Delta\|.$$ The result compares two points and says nothing about dynamics, which is why it needs neither smoothness nor $\varepsilon<\gamma/\beta$. Existence of a stable point (for compact $\Theta$, an $\varepsilon$-sensitive map and a convex loss Lipschitz in $z$) is Kakutani applied to $\theta\mapsto\arg\min_{\theta'}\mathrm{DPR}(\theta,\theta')$, with Berge's maximum theorem for upper hemicontinuity. The concave coin ($\varepsilon\in[\tfrac12,1)$, where $\beta/\gamma=1$) shows the asymmetry: RRM converges there, while $\mathrm{PR}$ is nonconvex, so stable points are easy to find and optima can be hard. For smooth, Lipschitz, convex losses without strong convexity, adding $\tfrac\alpha2\|\theta-\theta_0\|^2$ with $\alpha=\sqrt\varepsilon\beta/(1-\varepsilon)$ makes RRM converge to a point with $\mathrm{PR}\le\min\mathrm{PR}+O(\sqrt\varepsilon/(1-\varepsilon))$ on a $\Theta$ of diameter 1.

The gradient of $\mathrm{PR}$ has two terms, and retraining sees only one. With a density $p_\theta$ for $\mathcal D(\theta)$, $$\nabla\mathrm{PR}(\theta)=\mathbb E_{z\sim\mathcal D(\theta)}\nabla_\theta\ell(z;\theta)+\mathbb E_{z\sim\mathcal D(\theta)}\big[\ell(z;\theta)\nabla_\theta\log p_\theta(z)\big].$$ Stable points zero the first term; optima zero the sum. The second term is the leader's correction for how the followers respond, and it needs to know how $p_\theta$ moves, which deployed data alone do not reveal. Retraining can fail even on an easy problem: with $z\sim N(\varepsilon\theta,1)$ and $\ell=\tfrac12(z-\theta)^2$, $\mathrm{PR}=\tfrac12(\varepsilon-1)^2\theta^2+\tfrac12$ is convex for every $\varepsilon$ with optimum 0, yet retraining runs $\theta_{t+1}=\varepsilon\theta_t$ and diverges for $|\varepsilon|>1$.

A stable point can be the maximizer, because the cross term can outweigh the curvature. Take $z$ a point mass at $\varepsilon\theta$ and $\ell(z;\theta)=-\beta\theta^\top z+\tfrac\gamma2\|\theta\|^2$. Then $$\mathrm{DPR}(\theta,\phi)=-\varepsilon\beta\,\theta^\top\phi+\tfrac\gamma2\|\phi\|^2,\qquad\mathrm{PR}(\theta)=\big(\tfrac\gamma2-\varepsilon\beta\big)\|\theta\|^2.$$ Retraining maps $\theta\mapsto(\varepsilon\beta/\gamma)\theta$, so for $\varepsilon<\gamma/\beta$ the unique stable point is 0, and for $\varepsilon>\gamma/(2\beta)$ it is the unique maximizer of $\mathrm{PR}$. On $(\gamma/(2\beta),\gamma/\beta)$ retraining, and the stochastic-gradient methods built on it, converge to the worst model. In derivatives, $\partial_{22}=\gamma$, $\partial_{12}=-\varepsilon\beta$, $\partial_{11}=0$: retraining's slope is $-\partial_{12}/\partial_{22}$ and the diagonal curvature is $\gamma-2\varepsilon\beta$, the two thresholds side by side. The distance bound gives nothing here, since $L_z=\beta\max\|\theta\|$.

Under mixture dominance the diagonal is convex up to twice the cross term. Use the first-order characterization of $\lambda$-convexity and absorb each gradient term with one convexity. Mixture dominance makes $\mathrm{DPR}(\cdot,\theta)$ convex, which bounds the score term by $\mathrm{DPR}(\theta',\theta)-\mathrm{DPR}(\theta,\theta)$; strong convexity of $\mathrm{DPR}(\theta',\cdot)$ handles the direct term. What is left is one gradient direction integrated against two laws, $$\Big(\mathbb E_{\mathcal D(\theta)}-\mathbb E_{\mathcal D(\theta')}\Big)\nabla_\theta\ell(z;\theta)^\top\Delta\le\varepsilon\beta\|\Delta\|^2,$$ by Kantorovich-Rubinstein, and collecting terms gives $\tfrac12(\gamma-2\varepsilon\beta)$. The factor 2 relative to retraining is the $2\partial_{12}$ of the diagonal: retraining uses the cross term once, as a shift of the minimizer, while the curvature along the diagonal counts it from both arguments.

In location-scale families the moving coordinates add their own curvature, which can cancel $\varepsilon$. Mixture dominance comes from the convex order: by Strassen's theorem it suffices to build a martingale coupling, and pushing $z\sim\mathcal D(\alpha\theta+(1-\alpha)\theta')$ through the affine map to a randomly chosen endpoint is one, by linearity of $\mu$ and $\Sigma(\cdot)$. If $\ell$ is $\gamma_z$-strongly convex in $z$, the convex-order gap is the variance of the martingale step, $$\mathbb E_{\mathrm{mix}}\ell-\mathbb E_{\mathcal D(\alpha\theta+(1-\alpha)\theta')}\ell\ \ge\ \tfrac{\alpha(1-\alpha)\gamma_z}2\,s^2,\qquad s^2=\mathbb E\|\Sigma(\theta-\theta')z_0+\mu(\theta-\theta')\|^2,$$ so $\partial_{11}\gtrsim\gamma_zs^2/\|\Delta\|^2$, while the synchronous coupling bounds the cross term by $\beta s\|\Delta\|$. AM-GM then cancels the cross term against the new curvature and leaves $\gamma-\beta^2/\gamma_z$, whatever the size of the response; keeping the $\varepsilon\beta$ bound instead gives the second entry of $\lambda$. A stronger response moves the data further, and when the loss is curved in those coordinates, the extra movement adds curvature. For $\mathcal D(\theta)=N(\mu,\varepsilon^2\theta^2)$ and $\ell=\tfrac12(z-\theta)^2$, $\lambda=(1-\varepsilon)^2\ge0$ for every $\varepsilon$, yet the stable point is $\mu$ and the optimum $\mu/(1+\varepsilon^2)$.

Estimating the map supplies the missing gradient term, at a parametric rate. Deploying $\theta_i\sim N(0,I)$ gives a regression $z_i=\mu\theta_i+z_{0,i}$, and least squares gives $\|\hat\mu-\mu\|^2\lesssim(d+m+\log(1/\delta))/n$; deploying $\theta=0$ gives clean draws of $z_0$, so $z_j+\hat\mu\theta$ simulates $\mathcal D(\theta)$ for any $\theta$ offline, which is certainty equivalence. For the error, strong convexity gives the Polyak-Lojasiewicz bound $\mathrm{PR}(\hat\theta_n)-\mathrm{PR}(\theta_{PO})\le\|\nabla\mathrm{PR}(\hat\theta_n)\|^2/(2\lambda)$; the gradient splits into model error, of squared size $O(\|\mu\|^2\|\mu-\hat\mu\|^2)$, and optimization error of the plug-in minimizer, which inherits strong convexity by Weyl's inequality and has excess risk $O(1/(\delta n))$ by a stability bound plus Markov's inequality (hence the poor $\delta$ dependence). The comparison with zeroth-order methods counts samples only; random and null deployments are costly when the response is adversarial.

In simulations the convergence condition is conservative, and the two-stage method is unaffected by a strong response. On a credit-scoring dataset with three strategic features, agents shift them by $-\varepsilon\theta_S$ and the learner fits regularized logistic regression. In Perdomo et al., RRM converges in a few rounds for small $\varepsilon$ and diverges for large, RGD likewise but more slowly, while the sufficient condition holds only at $\varepsilon=0.01$ for RRM and never for RGD, so it is very conservative. In Miller et al., when the response is strong ($\varepsilon=100$), retraining-based SGD stalls far from the optimum, a derivative-free method slows or fails, and the two-stage method is essentially unaffected; on the credit simulator it converges within a few thousand samples where the derivative-free method has not converged after a million. At $\varepsilon=10^{-4}$ Miller et al. read an accuracy gap as stable points being worse than optima, but a short bound puts any stable point within 0.02 of the optimal regularized logistic loss, so the gap more likely reflects SGD runs short of their own limit (my note, not in the paper).

Consequences and limits. Retraining is an equilibrium-seeking dynamic: it settles when the model's strong convexity exceeds the product of how far the data move and how strongly the gradient reacts, so regularization stabilizes the loop and a merely convex or nonsmooth learner (a hard margin, a thresholded rule) can cycle at any sensitivity. Its limit is a Nash point, and a stable point can be the worst model; reaching the leader's optimum takes the derivative through $\mathcal D(\theta)$, which means estimating the response. Retraining also ignores anything that depends only on the induced distribution: a convex penalty $f(z)$ on, say, the induced fraud rate leaves every stable point unchanged, while the two-stage recipe can target it. The limits are in the map, a fixed memoryless function of the current model: the population responds instantly and completely, carries no state and does not anticipate the next retrain, the learner sees labeled draws from $\mathcal D(\theta)$, and Miller's guarantees add a location family with every agent shifting by the same $\mu\theta$, exploration by random and null deployments, and no misspecification. Agents who forecast the learner, or know they are being measured, turn the map into an equilibrium object.