Research map / Optimization / Nonconvex and smooth optimization
Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data
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.
Proposes DFO(λ), a two-timescale derivative-free optimization algorithm with sample accumulation for performative risk minimization under a controlled Markov chain, achieving O(1/ε³) sample complexity for ε-stationarity.
Problem
Minimizing performative risk (expected loss under a decision-dependent, Markovian data distribution) to a near-stationary point without structural assumptions on the distribution map or convexity.
Approach
A one-point zeroth-order gradient estimator updated online within each epoch, with a forgetting factor λ that accumulates samples from a controlled Markov chain, paired with two-timescale step sizes (query radius decays slower than the model step size) to balance bias and variance.
Key results
- DFO(λ) attains an average squared gradient norm rate of O(1/T^{1/3}), i.e., O(d^2 ε^{-3} log(1/ε)) samples to reach ε-stationarity under smoothness, bounded loss, and geometric mixing assumptions.
- In the 1-D quartic experiment, the measured gradient-norm decay was ~O(1/S^{0.312}), consistent with the predicted O(1/S^{1/3}) rate, while DFO-GD and SGD-GD did not converge to a stationary point.
- On the Markovian pricing and regression experiments, DFO(λ) converged to near-optimal solutions where DFO-GD and SGD-GD failed.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the two-timescale DFO(λ) algorithm with sample accumulation | Performative prediction with Markovian data · Performative prediction with Markovian data | sample complexity: O(d^2/ε^3 log(1/ε)) | Helped |
| use DFO(λ) instead of DFO-GD or SGD-GD | 1-D Quartic Loss · 1-D Quartic Loss | stationarity | Helped |
| use DFO(λ) instead of SGD-GD or DFO-GD | Markovian Pricing · Markovian Pricing | expected revenue | Helped |
| use DFO(λ) instead of DFO-GD or SGD | Markovian Performative Regression · Markovian Performative Regression | stationarity | Helped |
| set λ = 0.5 (ablation) | DFO(λ) · 1-D Quartic Loss | early-phase convergence rate | Helped |
| set λ = 0.5 instead of a smaller λ such as λ = 0.25 (ablation) | DFO(λ) · 1-D Quartic Loss | steady-phase fluctuation | Hurt |
| replace the one-point estimator with two-point I (ablation) | DFO(λ) · 1-D Quartic Loss | stationarity | Hurt |
| replace the one-point estimator with two-point II (ablation) | DFO(λ) · 1-D Quartic Loss | stationarity | Helped |
| use two independent samples in the two-point II estimator (ablation) | DFO(λ) · 1-D Quartic Loss | samples per update: twice as many samples | Hurt |
Surprising findings
- The two-point estimator (2pt-I) is biased under decision-dependent sampling and converges to a non-stationary point in experiments.
- Miller's two-phase algorithm did not reach the optimal objective with 10^4 Markovian samples in the first phase.
Limitations
- Convergence rate O(1/T^{1/3}) is slower than the O(1/sqrt(T)) achieved in the decision-independent setting.
- Requires Lipschitz distribution map and geometric mixing and kernel smoothness assumptions.
- Experiments are small-scale synthetic problems in low dimensions (d=1 and d=5).
Experimental setup
Datasets: synthetic AR(1) Markovian samples (quartic loss, pricing, linear regression)
Benchmarks: 1-D quartic loss minimization Markovian pricing (d=5) Markovian performative linear regression
Metrics: squared gradient norm expected revenue mean squared prediction error
Baselines: DFO-GD SGD-GD two-point estimator (2pt-I) two-point estimator (2pt-II) Miller two-phase algorithm
Builds on: zeroth-order optimization (Nesterov-Spokoiny style smoothing) burn-in sampling for Markovian data repeated risk minimization
Closest papers by meaning
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.89)
- Plug-in Performative Optimization (ICML 2024 · similarity 0.87)
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.86)
- Tight Lower Bounds and Improved Convergence in Performative Prediction (NeurIPS 2025 · similarity 0.86)
- Performative Prediction with Bandit Feedback: Learning through Reparameterization (ICML 2024 · similarity 0.86)
- Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies (ICML 2025 · similarity 0.85)
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.