Performative prediction (PP) is an algorithmic framework for optimizing machine learning (ML) models where the model's deployment affects the distribution of the data it is trained on. Compared to traditional ML with fixed data, designing algorithms in PP converging to a stable point -- known as a stationary performative stable (SPS) solution -- is more challenging than the counterpart in conventional ML tasks due to the model-induced distribution shifts. While considerable efforts have been made to find SPS solutions using methods such as repeated gradient descent (RGD) and greedy stochastic gradient descent (SGD-GD), most prior studies assumed a strongly convex loss until a recent work established O(1/T) convergence of SGD-GD to SPS solutions under smooth, non-convex losses. However, this latest progress is still based on the restricted bounded variance assumption in stochastic gradient estimates and yields convergence bounds with a non-vanishing error neighborhood that scales with the variance. This limitation motivates us to improve convergence rates and reduce error in stochastic optimization for PP, particularly in non-convex settings. Thus, we propose a new algorithm called stochastic performative prediction with variance reduction (SPRINT) and establish its convergence to an SPS solution at a rate of O(1/T). Notably, the resulting error neighborhood is independent of the variance of the stochastic gradients. Experiments on multiple real datasets with non-convex models demonstrate that SPRINT outperforms SGD-GD in both convergence rate and stability.
Figures & tables
Literature
Loss function ℓ
Convergence rate
Error neighborhood
Comments
Mendler-Dünner et al. (2020)
Strongly convex
O(T1)
None
No error due to strong convexity
Li and Wai (2024)
Nonconvex
O(T1)
O(σ0ϵ+σ12ϵ2)
Variance-dependent error neighborhood
This work: SPRINT-SVRG
Nonconvex
O(T1)
O(ϵ2+ϵ4)
Variance-independent error neighborhood
Table 1: SPRINT-SVRG compared to prior SGD-GD-based methods for PP. Since our goal is to improve existing SGD-GD-based PP methods, we do not include algorithms targeting PO solutions ( Izzo et al., 2021 ; Miller et al., 2021 ) or those based on repeated risk minimization (RRM) ( Perdomo et al., 2021 ; Mofakhami et al., 2023 ) ; we refer readers to Table 1 of Li and Wai (2024) for a detailed comparison with these methods.
Figure 1: Squared gradient norm ∥∇J(θs;θs)∥2 . From top to bottom are Credit dataset, MNIST dataset and Spambase dataset.
Figure 2: Mini-batch gradient snapshot experiments on the Credit and MNIST datasets. We plot the squared gradient norm ∥∇J(θs;θs)∥2 over epochs for SPRINT-SVRG with a full gradient snapshot and with mini-batch snapshot sizes B∈{256,512} . A larger batch size yields a snapshot estimate closer to the true full gradient and thus a convergence curve nearer to the full-gradient baseline. The results demonstrate that SPRINT-SVRG degrades only mildly under moderate snapshot approximation, suggesting practical deployability in large-population settings.
Figure 3: Empirical validation of variance-independent error neighborhood on the Credit dataset (left) and MNIST dataset (right). We vary the batch size B∈{1,32,128} (Credit) and B∈{64,128,256} (MNIST) to control the stochastic gradient variance σ02 . A larger batch size corresponds to smaller variance. If the error neighborhood were variance-dependent (as in SGD-GD), the converged gradient norm ∥∇J(θ~s,θ~s)∥2 would decrease as batch size increases. The results show that the converged gradient norms of SPRINT remain approximately constant across different batch sizes, providing empirical evidence consistent with the variance-independent error neighborhood established in Theorem 5.4 .
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: CIFAR-10 dataset: training accuracy (first row) and training loss (second row) of SGD-GD and SPRINT-SVRG under different α . Larger α means more intense retention dynamics and the shadow demonstrates standard errors.
Figure 5: Credit dataset: training accuracy (first row) and training loss (second row) of SGD-GD and SPRINT-SVRG under different α . Larger α means more intense strategic behaviors and the shadow demonstrates standard errors.
Figure 6: MNIST dataset: training accuracy (first row) and training loss (second row) of SGD-GD and SPRINT-SVRG under different α . Larger α means more intense retention dynamics and the shadow demonstrates standard errors.
Figure 7: MNIST dataset: training accuracy (first row) and training loss (second row) of SGD-GD and SPRINT-SVRG under different learning rate γ .
Figure 8: Out-of-sample evaluation accuracy of SGD-GD and SPRINT-SVRG on the Credit and SpamBase datasets under different performativity strengths α . From top to bottom are Credit dataset and SpamBase dataset. SPRINT-SVRG consistently achieves competitive or superior evaluation accuracy compared to SGD-GD, demonstrating that faster convergence to an SPS solution does not come at the cost of generalization.
When algorithmic predictions inform people's decisions, the models we deploy are performative and actively shape the data we see. This feedback loop between algorithms and their broader environments introduces a challenge in the mechanics of social prediction: If different predictive models induce different distributions, is it possible to efficiently learn a prediction rule that is optimal for the distribution that it induces? Formally, this solution concept is known as performative stability. A core challenge in learning a performatively stable predictor is that, unlike supervised learning where distributions are fixed, the learner must deploy different predictors and observe their induced distributions. The main contribution of our work is a new algorithmic procedure that, in the high-accuracy regime, finds a performatively stable model in nearly the minimum number of model deployments without making any assumptions regarding how predictions shape distributions. In particular, our procedure succeeds at finding a randomized performatively stable predictor using exponentially fewer model deployments than prior approaches. Our second main contribution is a structural result showing how this recent randomized notion of stability achieved by our algorithm can be derandomized into a single predictor satisfying the prior deterministic notion if one is willing to assume that the loss is well-conditioned and that performative effects are weak, as in early work in this area. On a technical level, our results come from building on an underexplored technical connection between performative stability and expected variational inequalities.
We study optimization under performative prediction, where deploying a model affects the future data distribution. For this setting, several gradient-based approaches have been proposed. However, they typically assume specific data distributions or loss functions, which limit their practical applicability. To overcome these limitations, we propose a gradient-based optimization method with convergence guarantees under substantially weaker assumptions. Our method explicitly estimates the induced distribution shift through finite differences. It enables higher-dimensional optimization across broader classes of loss functions and data distributions. We also propose a practical variant that reduces the number of samples required. Numerical experiments demonstrate that our proposed algorithms converge faster and more consistently than existing ones.
Hiroki Hamaguchi, Yuya Hikima, Hiroshi Sawada +1
Graduate School of Information Science and Technology, The University of Tokyo · Department of Industrial Engineering and Economics, Institute of Science Tokyo · Communication Science Laboratories, NTT, Inc. +1
The use of algorithmic predictions in decision-making leads to a feedback loop where the models we deploy actively influence the data distributions we see, and later use to retrain on. This dynamic was formalized by Perdomo et al. 2020 in their work on performative prediction. Our main result is an unconditional reduction showing that any no-regret algorithm deployed in performative settings converges to a (mixed) performatively stable equilibrium: a solution in which models actively shape data distributions in ways that their own predictions look optimal in hindsight. Prior to our work, all positive results in this area imposed strong restrictions on how models influenced distributions. By using a martingale argument and allowing randomization, we avoid any assumption on how populations respond to predictions and sidestep recent hardness results showing that deterministic stable models are in general PPAD-hard to compute. Lastly, on a more conceptual note, our connection sheds light on why common algorithms, like gradient descent, are naturally stabilizing and prevent runaway feedback loops. We hope our work enables future technical transfer of ideas between online optimization and performativity.