Stochastic Optimization for Performative Prediction

Celestine Mendler-Dünner; Juan C. Perdomo; Tijana Zrnic; Moritz Hardt

Source-linked AI summary

Stochastic Optimization for Performative Prediction

Celestine Mendler-Dünner, Juan C. Perdomo, Tijana Zrnic, Moritz Hardt

arXiv:2006.06887v4Jun 12, 2020cs.LGcs.GTstat.ML

TL;DR

Performative prediction studies stochastic optimization where predictions influence future data distributions through consequential actions. The paper analyzes greedy and lazy deployment, showing that their relative performance depends on performative strength and that lazy deployment can reduce deployments while improving sample complexity.

Problem
Performative predictions can trigger actions that change outcomes, making stochastic optimization differ from ordinary parameter updates because deployment changes the data-generating distribution.
Method
The paper analyzes greedy deploy, which updates and redeploys after each sample, and lazy deploy, which performs offline stochastic updates before redeployment.
Results
Greedy deploy is favored when performative effects are weak, whereas lazy deploy can perform better near the convergence threshold and requires fewer deployments for comparable convergence guarantees.
Takeaways & Limitations
Choosing the deployment schedule according to performative strength can reduce deployment costs while preserving convergence, especially because lazy deploy reduces the number of model deployments.
Takeaways & Limitations
The analysis assumes smoothness, strong convexity, and a sufficiently Lipschitz distribution map, with joint smoothness scaling differently from strong convexity under parameter rescaling.

Abstract

from arXiv · show

In performative prediction, the choice of a model influences the distribution of future data, typically through actions taken based on the model's predictions. We initiate the study of stochastic optimization for performative prediction. What sets this setting apart from traditional stochastic optimization is the difference between merely updating model parameters and deploying the new model. The latter triggers a shift in the distribution that affects future data, while the former keeps the distribution as is. Assuming smoothness and strong convexity, we prove rates of convergence for both greedily deploying models after each stochastic update (greedy deploy) as well as for taking several updates before redeploying (lazy deploy). In both cases, our bounds smoothly recover the optimal $O(1/k)$ rate as the strength of performativity decreases. Furthermore, they illustrate how depending on the strength of performative effects, there exists a regime where either approach outperforms the other. We experimentally explore the trade-off on both synthetic data and a strategic classification simulator.

1 Introduction

The paper studies stochastic optimization when deploying a model changes future data, distinguishing parameter updates from deployments. It analyzes greedy and lazy deployment, proving convergence guarantees and identifying a trade-off governed by performative effects and deployment costs.

The setting differs from classical stochastic optimization because deployment actively shifts the data distribution, creating a deployment decision absent from ordinary parameter updates.
Both methods converge to performative stability, but the preferable approach depends on deployment cost and the strength of performativity.
Greedy deploy converges at rate O(1/k) under smoothness, strong convexity, and a sufficiently Lipschitz distribution map.
Lazy deploy performs multiple stochastic updates before deployment, achieving rate O(1/k^α) when O(k^1.1α) samples are collected between deployments.
Lazy deploy can achieve any distance δ > 0 from optimality using (1/δ)^c deployments for arbitrarily small c > 0, at the cost of polynomially many samples.
For small performative effects greedy deploy behaves nearly like classical SGD, whereas lazy deploy is favored when effects approach the convergence threshold.

2 Preliminaries

Performative prediction models a feedback loop in which a deployed predictor induces its data distribution, and stable models remain optimal on the distributions they create. The preliminaries establish the sensitivity threshold governing existence and convergence, including failures of gradient descent outside the strongly convex, low-sensitivity regime.

2.1 The framework of performative prediction: A distribution map D(θ) assigns each deployed model the data-generating distribution it induces, with ε measuring sensitivity to model changes.
2.1 The framework of performative prediction: Performative stability requires a model to minimize loss on the distribution D(θ) that it itself induces.
2.1 The framework of performative prediction: The traffic example illustrates performativity: predictions alter route demand and thereby change travel times under squared loss.
2.2 Population-level results: Under smoothness, strong convexity, and ε < γ/β, a unique stable point exists and repeated gradient descent converges to it linearly.
2.2 Population-level results: Gradient descent can fail to converge when the loss is merely convex or when ε ≥ γ, showing that strong convexity and limited sensitivity are essential.
2.2 Population-level results: The threshold γ/β is sharp for population-level gradient-descent convergence and also governs the existence and algorithmic convergence of stable points.

3 Stochastic optimization results

The paper introduces greedy and lazy deployment variants of stochastic gradient optimization for performative prediction, proving convergence guarantees under smoothness, strong convexity, and Lipschitz distribution shifts. Their relative advantages depend on performative strength, initialization, and deployment cost: greedy deploy can achieve O(1/k), while lazy deploy can reduce deployments and better tolerate strong effects or poor initialization.

Algorithm variants: Greedy deploy updates and publishes the model after every stochastic gradient step, while lazy deploy performs multiple updates on samples from the last deployed distribution before publishing.The number of updates between deployments is n(k)=1 for greedy deploy and a tunable n(k) for lazy deploy.
Greedy deploy: Under smoothness, strong convexity, and sufficiently Lipschitz distribution shifts, greedy deploy converges to performative stability at the classical O(1/k) rate.The result matches the stochastic gradient rate without performativity.
Lazy deploy: Lazy deploy approximates repeated risk minimization by keeping the data distribution fixed between deployments, with n(k) growing as n_0k^α for any α>0.Its convergence follows from offline iterates approaching the risk minimizer for the previously deployed distribution and then approximating the repeated-risk-minimization trajectory.
Dependence on performativity: When performative effects are weak, greedy deploy contracts strongly and behaves nearly like classical SGD, whereas near the convergence threshold lazy deploy can perform better because its offline convergence is unaffected by ε.The bounds therefore yield qualitatively different regimes as performative strength changes.
Initialization sensitivity: Lazy deploy is more robust to poor initialization because its initial distance decays linearly rather than polynomially, according to the upper-bound analysis and empirical observations.The paper explicitly notes that the empirical investigation supports these theoretical observations.
Sample and deployment trade-off: Lazy deploy can approach greedy deploy’s sample complexity while requiring O(1/δ^α) deployments instead of O(1/δ), reducing the cost of repeatedly publishing models.The deployment reduction is motivated by social adaptation costs and technical deployment challenges.

4 Experiments

The experiments compare greedy and lazy deployment on synthetic Gaussian data and a strategic classification simulator, showing that the preferable schedule depends on performative strength and deployment choices.

Synthetic data: Greedy deploy outperforms lazy deploy under weak performative effects, whereas lazy deploy better handles strong distribution shifts.The experiments report this trade-off across synthetic and strategic classification settings.
Synthetic data: Shorter deployment schedules accelerate early progress, while longer schedules perform better later and substantially reduce the number of deployments.The comparison covers n(k) proportional to k^α for α in {0.5,1,2}.
Strategic classification: The strategic-classification experiments sample one manipulated-feature example at a time rather than observing the full manipulated-feature distribution.The stable point is estimated empirically by running repeated risk minimization until convergence.
Strategic classification: In strategic classification with ε = 0.001, greedy deploy is preferred in the provable-convergence regime because performative effects are small relative to the problem condition.The experiment has γ/β approximately 10^-2 and uses ε = 10^-3.
Strategic classification: Outside the provable-convergence regime, lazy deploy significantly outperforms greedy deploy, and larger deployment schedules improve its performance.This setting uses ε much larger than γ/β and evaluates strategic classification convergence.

A Additional evaluations and details on experimental setup

Additional evaluations examine convergence across samples and deployments, vary performativity and deployment schedules, and report uncertainty across repeated runs.

Additional evaluations: Figure 4 compares lazy deploy across ε values using samples collected and deployments as the two convergence axes, with greedy deploy and RRM as references.The synthetic Gaussian experiment uses μ = 10 and σ = 0.1; stars mark outcomes after 50k SGD updates.
Additional evaluations: Figure 5 evaluates strategic-classification convergence for ε = 0.001 using samples, deployments, and excess performative risk relative to θPS.The right panel uses stochastic gradient updates as its horizontal axis.
Experimental setup: The experiments use theory-based step-size schedules, while ε = 100 requires an empirically adjusted greedy-deploy step-size factor.Lazy deployment uses n(k) = n0k^α with n0 = 1.
Experimental setup: All experiments are repeated 30 times, with means and shaded intervals computed using 90% Gaussian-error coverage.The interval uses z = 1.645 and the standard deviation across runs.

A.1 Synthetic Gaussian experiments

The synthetic experiments estimate a Gaussian mean under a performative distribution map, while the strategic-classification setup models strategic feature manipulation and stochastic sampling.

Synthetic Gaussian experiments: The Gaussian distribution is D(θ) = N(μ + θε, σ^2), with μ = 10 and σ = 0.1 used in experiments.The optimization procedures start at θ1 = μ to reduce initialization effects.
Strategic classification setup: The strategic-classification dataset contains 18,357 normalized examples with ten features, three of which are treated as strategic.The strategic dimensions are features 1, 6, and 8, including attributes such as open credit lines.
Strategic classification setup: The stochastic experiments sample one dataset example according to the strategic distribution-generating process rather than using the full empirical distribution at each step.The empirical distribution over the dataset is treated as the true distribution.
Strategic classification setup: The institution uses logistic loss with ℓ2 regularization, while individuals respond to classifier choices through linear utility and quadratic manipulation costs.The simulator is based on a credit-scoring setting with binary loan-default labels.

C.1 Proof of Proposition 2.5

This proof constructs a one-dimensional performative example and characterizes when a stable point exists. It then shows repeated gradient descent diverges when performative sensitivity is too large or strong convexity is absent.

The example uses a point-mass distribution at 1+εθ, making the distribution map ε-sensitive.
For β ⩾ γ, the loss is convex in θ and β-jointly smooth, with a unique stable point when the stated ε, γ, and β condition holds.
When γ = 0, the loss is convex but repeated gradient descent diverges for every positive ε, β, and positive step-size sequence.
When ε exceeds γ/β, strong convexity does not prevent divergence, and at the boundary there is no stable solution.

C.2 Proof of Proposition 2.6

This proof analyzes greedy-deploy stochastic updates by expanding the projected update, bounding its cross-term through smoothness and distribution sensitivity, and controlling the gradient second moment.

The proof begins from a projected stochastic-gradient distance recursion around the performatively stable point.
The analysis uses an independent sample from D(θPS) to compare the deployed trajectory with the stable distribution.
The resulting recursion is unrolled with a decreasing step size, and setting its bound to δ yields the convergence statement.
The cross-term is bounded using conditional expectation, Cauchy–Schwarz, joint smoothness, and ε-sensitivity of the distribution map.
Strong convexity supplies the main contraction term, while the gradient second moment or variance assumption controls the remaining stochastic term.

D.2 Proof of Theorem 3.2

The proof of Theorem 3.2 derives a recursion for greedy deploy and establishes its rate by induction under a step size tied to the effective curvature γ−εβ.

The proof starts from the recursion supplied by Lemma 3.1 for the greedy-deploy iterates.
It chooses ηk = 1/((γ−εβ)(k+k0)) and defines k0 = 8L2/(γ−εβ)2.
Induction verifies the claimed bound by applying Lemma 3.1 and comparing consecutive quadratic denominators.

E Lazy deploy: proofs

These proofs establish lazy-deploy bounds by deriving within-deployment recursions, controlling deployment cross-terms, and selecting block sizes and auxiliary parameters so the recursion contracts.

The lazy-deploy analysis first invokes the classical static-distribution SGD convergence result for updates made between deployments.
It derives a recursion by bounding the update cross-term with convex optimality and strong convexity, then controlling the final term through a gradient second-moment assumption.
The proof combines these bounds into a recursion valid across deployment blocks and uses induction with ηk,j = 1/(γ(j+k0)).
Identities relating the deployment operator to the stable point allow the cross-term to be bounded using Jensen’s and AM-GM inequalities.
Choosing n0 so that an auxiliary α0 gives c < 1, then unrolling the recursion, produces the final bound as α0 approaches 1 with growing n0.

F Proof of Corollary 3.4

The proof derives asymptotic convergence results by inverting the greedy- and lazy-deploy bounds, relating deployments to collected samples.

For lazy deployment, collecting Θ(j^α) samples at deployment j yields Θ(k^(α+1)) total samples after k deployments.
The lazy-deploy convergence exponent uses ω = 1 − o(1), which is independent of k and approaches 1 as n0 grows.
The corollary follows by inverting the convergence bounds for greedy and lazy deployment.The greedy-deploy bound comes from Theorem 3.2, while the lazy-deploy bound comes from Theorem 3.3.