Research map / Bandits and online learning / Online convex optimization and games
Performative Prediction with Bandit Feedback: Learning through Reparameterization
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 a reparameterization-based two-level zeroth-order bandit algorithm for performative prediction with non-convex performative risk, achieving sublinear regret in total performative samples.
Problem
Performative risk minimization when the performative risk is non-convex in the model parameter, the distribution map is unknown, and only noisy loss feedback (bandit feedback) is available.
Approach
Reparameterize the performative risk as a convex function of the induced data-distribution parameter, then run zeroth-order optimization over distribution parameters with an inner loop that learns a model inducing each target distribution via KL-divergence zeroth-order minimization.
Key results
- Regret bound of O~((d_Theta + d_Phi) N_KL^{1/6} N^{5/6}) in total performative samples N with probability at least 1-p.
- Toy experiments show the reparameterized method converges faster than directly minimizing PR over theta.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Optimize performative risk in the distribution parameter space rather than directly in the model parameter | Performative prediction on the toy example · Toy example | convergence rate | Helped |
Limitations
- Double-loop zeroth-order procedure is likely slow in practice.
- Requires convexity of PR in distribution parameter and several structural assumptions (Lipschitz, KL convexity) and a known parametric density family.
- Depends on an off-the-shelf KL-divergence estimator whose sample efficiency affects the bound.
Experimental setup
Datasets: synthetic toy example
Benchmarks: toy performative prediction example
Metrics: convergence rate of performative risk regret
Baselines: direct zeroth-order optimization of PR in theta
Builds on: performative prediction (Perdomo et al.) zeroth-order convex optimization (bandit optimization) repeated risk minimization
Closest papers by meaning
- Plug-in Performative Optimization (ICML 2024 · similarity 0.90)
- Optimal Classification under Performative Distribution Shift (NeurIPS 2024 · similarity 0.87)
- The Stability of Online Algorithms in Performative Prediction (NeurIPS 2026 · similarity 0.87)
- Performative Prediction with Selective Labels (NeurIPS 2026 · similarity 0.86)
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.86)
- Bandit and Delayed Feedback in Online Structured 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.