Research map / Bandits and online learning / Online convex optimization and games
The Stability of Online Algorithms in Performative Prediction
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that the uniform mixture over iterates of any deterministic no-regret online algorithm, run on losses sampled from performative distributions, is a (mixed) performatively stable solution with gap Regret_T/T, with no assumptions on the distribution map.
Problem
Performative prediction: deployed models shape the data distribution they are retrained on; deterministic stable models may not exist or are PPAD-hard to compute under standard assumptions (strong convexity, Lipschitz distribution maps). The paper asks when online/retraining dynamics converge to sta
Approach
Reduce performative stability to no-regret learning: the uniform mixture over the iterates of any no-regret algorithm run on losses ell(z_t, .) with z_t ~ D(theta_t) is performatively stable, using a martingale argument that exploits adaptive adversary guarantees and removes all continuity or curvature assumptions on D and the loss.
Key results
- Uniform mixture over iterates of any deterministic no-regret algorithm is Regret_T/T performatively stable, in expectation over samples, for arbitrary distribution maps.
- Smoothed retraining (follow-the-leader then mixing) under gamma-strongly convex losses gives stability gap G^2(log T+1)/(2 gamma T).
- Online gradient descent with convex losses gives gap 3GD/(2 sqrt(T)); exp-concave losses via online Newton step give d log T / T rate.
Surprising findings
- Retraining, which can cycle forever on a discontinuous example (0,1,0,1,...), yields a mixture that concentrates near the performatively optimal point 1/2 as T grows.
Limitations
- Stability guarantee is for a randomized mixture of models rather than a single deterministic model.
- Analysis is for the stateless performativity setting; stateful settings are left as future work.
- Online-to-batch high-probability rate is not sharpened to O~(1/T); lazy gradient descent variants are not analyzed.
Experimental setup
Metrics: performative stability gap (Regret_T/T) expected loss excess over best comparator
Baselines: repeated retraining (Perdomo et al. 2020) stochastic gradient descent performative analysis (Mendler-Dunner et al. 2020) multiplayer performative prediction (Narang et al. 2022) online multicalibration reduction (Hu? single-author outcome setting)
Builds on: performative prediction (Perdomo et al. 2020) follow-the-leader online gradient descent online Newton step multiplayer performative prediction
Closest papers by meaning
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.88)
- Performative Prediction with Bandit Feedback: Learning through Reparameterization (ICML 2024 · similarity 0.87)
- Plug-in Performative Optimization (ICML 2024 · similarity 0.87)
- Decentralized Noncooperative Games with Coupled Decision-Dependent Distributions (NeurIPS 2024 · similarity 0.86)
- Bandit and Delayed Feedback in Online Structured Prediction (NeurIPS 2025 · similarity 0.86)
- Tight Lower Bounds and Improved Convergence in Performative Prediction (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.