# Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Oct 2023.

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

- [Nonlinear Performative Prediction](https://mlsanity.com/paper/2509.01139/) (2025)
- [SPRINT: Stochastic Performative Prediction With Variance Reduction](https://mlsanity.com/paper/2509.17304/) (2025)
- [Achieve Performatively Optimal Policy for Performative Reinforcement Learning](https://mlsanity.com/paper/2510.04430/) (2025)
- [Dissecting Performative Prediction: A Comprehensive Survey](https://mlsanity.com/paper/2602.10176/) (2026)
- [Partially Performative Prediction](https://mlsanity.com/paper/2606.07890/) (2026)
- [Learning-Based Surrogate Method for Stochastic Optimization under Decision-Dependent Uncertainty with Adaptive Random Designs](https://mlsanity.com/paper/2505.07298/) (2025)
- [Towards Performatively Stable Equilibria in Decision-Dependent Games for Arbitrary Data Distribution Maps](https://mlsanity.com/paper/2509.02619/) (2025)
- [When Predictions Shape Reality: A Socio-Technical Synthesis of Performative Predictions in Machine Learning](https://mlsanity.com/paper/2601.04447/) (2026)
- [Self-Consuming Generative Models with Co-Evolving Human Preferences](https://mlsanity.com/paper/2610.09415/) (2026)
- [Partially Informed Stochastic Optimization via Zeroth-Order Residual Tracking](https://mlsanity.com/paper/2610.13871/) (2026)

## Abstract (arXiv)

This paper studies the performative prediction problem where a learner aims to minimize the expected loss with a decision-dependent data distribution. Such setting is motivated when outcomes can be affected by the prediction model, e.g., in strategic classification. We consider a state-dependent setting where the data distribution evolves according to an underlying controlled Markov chain. We focus on stochastic derivative free optimization (DFO) where the learner is given access to a loss function evaluation oracle with the above Markovian data. We propose a two-timescale DFO(λ) algorithm that features (i) a sample accumulation mechanism that utilizes every observed sample to estimate the overall gradient of performative risk, and (ii) a two-timescale diminishing step size that balances the rates of DFO updates and bias reduction. Under a general non-convex optimization setting, we show that DFO(λ) requires cal O( 1 /ε3) samples (up to a log factor) to attain a near-stationary solution with expected squared gradient norm less than ε > 0. Numerical experiments verify our analysis.