Research map / Optimization / Implicit bias and generalization
Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss
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.
Analyzes greedy-deployment SGD (SGD-GD) and lazy-deployment SGD for performative prediction with smooth non-convex losses, showing convergence to biased stationary performative stable (SPS) solutions under Wasserstein-1 or TV distribution sensitivity.
Problem
Performative prediction with smooth but possibly non-convex loss, where the data distribution depends on the deployed model and standard stochastic gradient methods lack convergence guarantees beyond strongly convex losses.
Approach
Introduces stationary performative stable (SPS) solutions as a non-convex relaxation of PS solutions and a time-varying Lyapunov function J(.; theta_t) to analyze the non-gradient SGD recursion; shows bias scales with sensitivity epsilon and gradient variance, and lazy deployment reduces the bias to O((L~ eps)^2).
Key results
- SGD-GD converges in expectation at rate O(T^{-1/2}) to an O(eps)-SPS solution under Lipschitz loss with W1 sensitivity, and O(eps^2) bias with exact gradients.
- Under TV sensitivity with bounded loss, SGD-GD also reaches a biased SPS solution with bias O(sigma_0 eps + (1+sigma_1^2) eps^2).
- Lazy deployment with epoch length K reduces the bias to O((L~ eps)^2 (K+sigma_1^2)/K), so bias decreases as K grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the lazy deployment epoch length K | Lazy deployment with SGD · Synthetic data, linear model | SPS stationarity | Helped |
| Use lazy deployment instead of greedy deployment | SGD-GD · Spambase, neural network | SPS stationarity: 10^{-4} | Helped |
| Increase the distribution shift parameter ε_L | SGD-GD · Synthetic data, linear model | SPS stationarity | Hurt |
| Increase the distribution shift parameter ε_L | SGD-GD · Synthetic data, linear model | training and testing accuracy | No clear effect |
| Increase the sensitivity parameter ε_NN | SGD-GD · Spambase, neural network | SPS stationarity | No clear effect |
| Increase the sensitivity parameter ε_NN | Trained neural network · Spambase | training/testing accuracy | No clear effect |
| Use deterministic gradients instead of stochastic gradients | SGD-GD · Performative prediction | SPS stationarity bias: O(ε) -> O(ε^2) | Helped |
| Increase minibatch size to reduce stochastic-gradient variance | SGD-GD · Performative prediction | SPS stationarity bias | Helped |
Surprising findings
- The bias level of greedy SGD is sensitive to stochastic gradient noise: O(eps) with noisy gradients versus O(eps^2) with exact gradients.
- Increasing the shift parameter does not consistently degrade test/train accuracy in the experiments, so the effect on accuracy is unpredictable when only biased SPS is guaranteed.
Limitations
- Guarantees only a biased SPS solution, not an exact stationary point of the performative risk V(theta).
- Requires the loss to be Lipschitz in data (W1 case) or bounded (TV case), and bounded stochastic gradients for lazy deployment.
- Experiments are small-scale (linear model on synthetic data and a 3-layer NN on spambase).
Experimental setup
Datasets: spambase synthetic data (uniform features, 10% label flips)
Metrics: squared norm of decoupled partial gradient (SPS stationarity performative risk J(theta_t; theta_t) training and testing accuracy
Baselines: greedy deployment SGD (SGD-GD)
Builds on: performative prediction repeated risk minimization stochastic gradient descent
Closest papers by meaning
- Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies (ICML 2025 · similarity 0.92)
- Data-Dependent Stability of Stochastic Gradient Descent (ICML 2018 · similarity 0.91)
- Two-timescale Derivative Free Optimization for Performative Prediction with Markovian Data (ICML 2024 · similarity 0.89)
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.89)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · similarity 0.88)
- Tight Lower Bounds and Improved Convergence in Performative Prediction (NeurIPS 2025 · similarity 0.88)
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.