Research map / Learning theory and algorithms / Sample complexity
Tight Lower Bounds and Improved Convergence 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.
Extends repeated risk minimization to Affine Risk Minimizers that train on affine mixtures of past snapshot distributions, proving tight lower bounds for RRM and ARM and a faster convergence rate that breaks the prior RRM lower bound.
Problem
Convergence of repeated risk minimization to a performatively stable point is limited to a restricted problem class and rate; prior lower bounds on RRM convergence rates were not shown tight for the class of methods using historical snapshots.
Approach
Replace the latest-snapshot distribution in RRM with an affine (convex) combination of past snapshot distributions (Affine Risk Minimizers), which provably converges on a broader problem class and can exceed the standard RRM lower bound, and derive matching lower bounds via a Nesterov-style construction.
Key results
- Using a 2-snapshot average ARM roughly halves the loss shift compared with standard RRM (window 1 to 2) in the credit scoring experiment, with the gain persisting beyond 50 iterations.
- ARM breaks the standard RRM lower bound and converges for sensitivity ratio below 2/sqrt(3) (about 1.155) versus 1 for RRM.
- The paper proves tight lower bounds for RRM under both the Mofakhami and Perdomo frameworks, and an ARM lower bound that is optimal up to a factor of 2 in the Perdomo setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Average the latest two snapshots instead of using only the latest snapshot | ARM · Give Me Some Credit | loss shift (ΔR_t) | Helped |
| Increase the averaging window beyond two snapshots | ARM · Give Me Some Credit | loss shift (ΔR_t) | Helped |
| Use a window of t/2 or all snapshots rather than a smaller averaging window | ARM · Give Me Some Credit | loss shift (ΔR_t) | No clear effect |
Surprising findings
- Averaging over many past snapshots gives diminishing returns, so windows t/2 and 'all' perform nearly identically.
Limitations
- Results are proven under strong assumptions such as strong convexity and bounded gradients, and the improvement is modest.
- The best ARM result found uses only the last two snapshots; longer windows are proven to converge but do not improve the bound.
- Experiments are limited to semi-synthetic credit scoring and rideshare settings.
Experimental setup
Datasets: Give Me Some Credit
Benchmarks: Give Me Some Credit (RIR semi-synthetic credit scoring)
Metrics: loss shift due to performativity (Delta R_t) distance to performatively stable point
Baselines: Repeated Risk Minimization (tau=1)
Builds on: Repeated Risk Minimization Mofakhami et al. performative prediction framework Perdomo et al. performative prediction Nesterov lower bound for convex smooth functions
Closest papers by meaning
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.88)
- Performative Prediction with Selective Labels (NeurIPS 2026 · similarity 0.87)
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.86)
- Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data (ICML 2024 · similarity 0.86)
- The Stability of Online Algorithms in Performative Prediction (NeurIPS 2026 · similarity 0.86)
- Performative Prediction with Bandit Feedback: Learning through Reparameterization (ICML 2024 · 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.