Research map / Optimization / Nonconvex and smooth optimization
Distributionally Robust Optimization with Bias and Variance Reduction
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 Prospect, a single-learning-rate stochastic gradient method for distributionally robust optimization over spectral risk measures with f-divergence penalty, combining loss-table bias reduction and SAGA-style control variates, with linear convergence for any positive shift cost on regularized smooth convex losses.
Problem
Stochastic optimization of spectral risk measure (e.g., CVaR, extremile, ESRM) distributionally robust objectives over reweightings of training data, where existing stochastic methods are biased, fail to converge for small shift costs, or need multiple hyperparameters.
Approach
Maintain a table of losses and gradients for each training example, use the most-adversarial distribution computed from the stale loss table (via PAV isotonic regression) as an asymptotically unbiased importance weight, and apply a SAGA-style control variate to reduce variance without decaying the step size.
Key results
- Prospect converges to 1e-8 suboptimality for CVaR on concrete and extremile on power within about half the passes LSVRG needs.
- On diabetes CVaR, LSVRG gives statistical parity 1.38 ± 0.25% over the last ten passes versus 0.82 ± 0.00% for Prospect (about 40% relative improvement).
- On amazon extremile, Prospect has worst group error 77.38 ± 0.00% versus 77.53 ± 1.57% for Saddle-SAGA.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Prospect instead of LSVRG | Diabetes CVaR classification · Diabetes CVaR | statistical parity score: 1.38 \pm 0.25\% -> 0.82 \pm 0.00\%; 40\% relative improvement | Helped |
| Use Prospect instead of SaddleSAGA | Amazon Reviews extremile classifier · Amazon Reviews extremile | worst group error: 77.53 {\pm} 1.57 \% -> 77.38 {\pm} 0.00 \% | Helped |
| Use Prospect instead of LSVRG | spectral risk optimization on concrete CVaR · concrete | oracle passes to reach suboptimality 10^{-8}: within half the number of passes | Helped |
| Use Prospect instead of SaddleSAGA | spectral risk optimization on yacht ESRM · yacht | epochs to reach the same precision: 64 epochs ... 40 epochs | Helped |
| Use Prospect instead of SGD or SRDA | tabular regression spectral risk objectives · regression benchmarks | training objective convergence | Helped |
| Use Prospect instead of LSVRG | fair classification · Diabetes | training objective convergence | Helped |
| Use Prospect instead of SaddleSAGA | fair regression · Adult Census (acsincome) | training objective convergence | Helped |
| Use Prospect instead of LSVRG | Amazon Reviews and iWildCam classifiers · Amazon Reviews and iWildCam | training suboptimality | Helped |
| Use Prospect instead of SaddleSAGA | iWildCam classifier · iWildCam | median group misclassification rate: nearly 1pp better | Helped |
| Use SGD instead of Prospect | Adult Census (acsincome) CVaR model · Adult Census (acsincome) | statistical parity score | Helped |
Surprising findings
- SGD and SRDA are biased and fail to converge for any learning rate on the spectral risk objectives.
- Suboptimality and statistical parity are not always aligned: SGD, at only 1e-1 suboptimality on acsincome CVaR, achieves lower fairness score than Prospect.
Limitations
- Convergence analysis assumes convex, smooth (regularized) losses; non-convex setting left to future work.
- Non-smooth case handled via Moreau envelope variant rather than the main guarantee.
- Linear convergence for nu=0 holds only when losses are separated at the optimum.
Experimental setup
Datasets: yacht energy concrete kin8nm power diabetes 130-hospitals acsincome Amazon Reviews (WILDS) iWildCam (WILDS)
Benchmarks: yacht energy concrete kin8nm power diabetes acsincome amazon iwildcam
Metrics: suboptimality of DR objective statistical parity score worst group misclassification error median group misclassification error
Baselines: SGD SRDA Saddle-SAGA LSVRG
Builds on: SAGA LSVRG Saddle-SAGA stochastic regularized dual averaging Pool Adjacent Violators
Closest papers by meaning
- Distributionally Robust Performative Optimization (NeurIPS 2025 · similarity 0.90)
- Drago: Primal-Dual Coupled Variance Reduction for Faster Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.90)
- Large-Scale Non-convex Stochastic Constrained Distributionally Robust Optimization (AAAI 2024 · similarity 0.90)
- Bayesian Nonparametrics Meets Data-Driven Distributionally Robust Optimization (NeurIPS 2024 · similarity 0.89)
- Outlier-Robust Distributionally Robust Optimization via Unbalanced Optimal Transport (NeurIPS 2024 · similarity 0.89)
- Wasserstein Distributionally Robust Optimization through the Lens of Structural Causal Models and Individual Fairness (NeurIPS 2024 · similarity 0.89)
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.