# SPRINT: Stochastic Performative Prediction With Variance Reduction

arXiv: https://arxiv.org/abs/2509.17304 · HTML: https://mlsanity.com/paper/2509.17304/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 32 references that are in the map.
- First posted on arXiv 22 Sep 2025.

## Builds on (most cited first, 26 of 26)

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1603.06160/) (2016)
- [The Heavy-Tail Phenomenon in SGD](https://mlsanity.com/paper/2006.04740/) (2020)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [How to Learn when Data Reacts to Your Model: Performative Gradient Descent](https://mlsanity.com/paper/2102.07698/) (2021)
- [Stochastic optimization with decision-dependent distributions](https://mlsanity.com/paper/2011.11173/) (2020)
- [State Dependent Performative Prediction with Stochastic Approximation](https://mlsanity.com/paper/2110.00800/) (2021)
- [Group Retention when Using Machine Learning in Sequential Decision Making: the Interplay between User Dynamics and Fairness](https://mlsanity.com/paper/1905.00569/) (2019)
- [Anticipating Performativity by Predicting from Predictions](https://mlsanity.com/paper/2208.07331/) (2022)
- [Performative Prediction with Neural Networks](https://mlsanity.com/paper/2304.06879/) (2023)
- [Making Decisions under Outcome Performativity](https://mlsanity.com/paper/2210.01745/) (2022)
- [Decision-Dependent Risk Minimization in Geometrically Decaying Dynamic Environments](https://mlsanity.com/paper/2204.08281/) (2022)
- [From Predictions to Decisions: Using Lookahead Regularization](https://mlsanity.com/paper/2006.11638/) (2020)
- [Towards Return Parity in Markov Decision Processes](https://mlsanity.com/paper/2111.10476/) (2021)
- [Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss](https://mlsanity.com/paper/2405.17922/) (2024)
- [Addressing Polarization and Unfairness in Performative Prediction](https://mlsanity.com/paper/2406.16756/) (2024)
- [Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data](https://mlsanity.com/paper/2310.05792/) (2023)
- [Algorithmic Decision-Making under Agents with Persistent Improvement](https://mlsanity.com/paper/2405.01807/) (2024)
- [Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Clipping Bias and Remedies](https://mlsanity.com/paper/2404.10995/) (2024)
- [ProFL: Performative Robust Optimal Federated Learning](https://mlsanity.com/paper/2410.18075/) (2024)

## Built on by (most cited first, 2 of 2)

- [When and How Human Curation Backfires: Preference Alignment under Multi-Model Self-Consuming Loop](https://mlsanity.com/paper/2605.29267/) (2026)
- [Self-Consuming Generative Models with Co-Evolving Human Preferences](https://mlsanity.com/paper/2610.09415/) (2026)

## Abstract (arXiv)

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.