Research map / Optimization / Implicit bias and generalization
Clipped SGD Algorithms for Performative Prediction: Tight Bounds for Stochastic Bias and Remedies
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.
Studies projected clipped SGD (PCSGD) under decision-dependent (performative) data distributions, proves tight clipping-bias bounds for strongly convex losses and stationarity bias for non-convex losses, and shows DiceSGD removes the bias.
Problem
Clipped SGD with decision-dependent data distributions in performative prediction has a non-smooth, non-gradient dynamic; clipping induces an asymptotic bias that prevents convergence to performative stable (or stationary) solutions, especially under privacy-motivated clipping and distribution shift
Approach
Shows clipping bias in performative settings scales as Θ(1/(µ−Lβ)²) (tight for strongly convex losses), so bias amplifies as distribution sensitivity β approaches µ/L; proposes optimal constant step size design for PCSGD and adapts DiceSGD's double-clipping with error feedback to remove the bias.
Key results
- PCSGD lower and upper bounds on clipping bias match at Θ(1/(µ−Lβ)²) for strongly convex losses, showing bias amplification as β increases toward µ/L.
- DiceSGD converges to the performative stable solution at O(1/t) rate in the quadratic experiment, while PCSGD plateaus at a biased point that grows with β.
- For non-convex losses, PCSGD achieves O(1/√T) stationarity rate plus a bias term controlled by clipping threshold and β; DiceSGD bias reduces to O(1/√T + bβ).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DiceSGD instead of PCSGD | Quadratic minimization · Quadratic minimization | squared distance to PS solution: O(1/t) | Helped |
| Use PCSGD with gradient clipping instead of plain SGD with DP noise | Quadratic minimization · Quadratic minimization | squared distance to PS solution | Hurt |
| Increase distribution sensitivity β | PCSGD · Quadratic minimization | squared distance to PS solution | Hurt |
| Decrease privacy budget ε | PCSGD · Quadratic minimization | squared distance to PS solution | Hurt |
| Use the optimal step size adapted to distribution shifts instead of the non-optimal step size | PCSGD · Quadratic minimization | squared distance to PS solution | Helped |
| Use DiceSGD instead of PCSGD | Logistic regression · GiveMeSomeCredit test set | squared distance to PS solution: O(1/t) | Helped |
| Increase distribution sensitivity β | PCSGD and DiceSGD · GiveMeSomeCredit test set | trajectory stability | Hurt |
| Increase distribution sensitivity β | PCSGD and DiceSGD · GiveMeSomeCredit test set | true positive rate | Hurt |
| Add the DiceSGD error-feedback mechanism with a second clipping operator | PCSGD · Strongly convex performative prediction | squared distance to PS solution: O(1/t) | Helped |
| Use DiceSGD with distribution sensitivity β approximately zero | DiceSGD · Non-convex performative prediction | stationarity measure: O(1/√T + bβ) | Helped |
Surprising findings
- Clipping bias for PCSGD is O(1/(µ−Lβ)²), larger than the O(1/c) scaling of prior work even at β=0.
Experimental setup
Datasets: GiveMeSomeCredit
Benchmarks: GiveMeSomeCredit
Metrics: squared distance to performative stable solution test true negative rate test true positive rate
Baselines: PCSGD plain SGD with DP noise DiceSGD
Builds on: PCSGD (projected clipped SGD) DiceSGD performative stable solution (Perdomo et al., 2020) DP-SGD (Abadi et al., 2016)
Closest papers by meaning
- Stochastic Optimization Schemes for Performative Prediction with Nonconvex Loss (NeurIPS 2024 · similarity 0.92)
- Convergence of Clipped SGD on Convex $(L_0,L_1)$-Smooth Functions (NeurIPS 2025 · similarity 0.90)
- To Clip or not to Clip: the Dynamics of SGD with Gradient Clipping in High-Dimensions (ICLR 2025 · similarity 0.90)
- Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach (ICLR 2024 · similarity 0.90)
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual Perspective (NeurIPS 2024 · similarity 0.88)
- Generalization Analysis of Biased Stochastic Gradient Methods for Minimax Problems (NeurIPS 2026 · 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.