# Large-Scale Methods for Distributionally Robust Optimization

arXiv: https://arxiv.org/abs/2010.05893 · HTML: https://mlsanity.com/paper/2010.05893/

## Key facts

- Cited by 179 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2020.

## Built on by (most cited first, 30 of 179)

- [Just Train Twice: Improving Group Robustness without Training Group Information](https://mlsanity.com/paper/2107.09044/) (2021)
- [Towards Out-Of-Distribution Generalization: A Survey](https://mlsanity.com/paper/2108.13624/) (2021)
- [Challenges and Strategies in Cross-Cultural NLP](https://mlsanity.com/paper/2203.10020/) (2022)
- [Correct-N-Contrast: A Contrastive Approach for Improving Robustness to Spurious Correlations](https://mlsanity.com/paper/2203.01517/) (2022)
- [RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold](https://mlsanity.com/paper/2406.14532/) (2024)
- [Spread Spurious Attribute: Improving Worst-group Accuracy with Spurious Attribute Estimation](https://mlsanity.com/paper/2204.02070/) (2022)
- [DoG is SGD's Best Friend: A Parameter-Free Dynamic Step Size Schedule](https://mlsanity.com/paper/2302.12022/) (2023)
- [Discover and Cure: Concept-aware Mitigation of Spurious Correlation](https://mlsanity.com/paper/2305.00650/) (2023)
- [Preserving Fairness Generalization in Deepfake Detection](https://mlsanity.com/paper/2402.17229/) (2024)
- [MaskTune: Mitigating Spurious Correlations by Forcing to Explore](https://mlsanity.com/paper/2210.00055/) (2022)
- [Benchmarking Distribution Shift in Tabular Data with TableShift](https://mlsanity.com/paper/2312.07577/) (2023)
- [Risk-Averse Offline Reinforcement Learning](https://mlsanity.com/paper/2102.05371/) (2021)
- [Diversify and Disambiguate: Learning From Underspecified Data](https://mlsanity.com/paper/2202.03418/) (2022)
- [Learning Debiased Classifier with Biased Committee](https://mlsanity.com/paper/2206.10843/) (2022)
- [Model Agnostic Sample Reweighting for Out-of-Distribution Learning](https://mlsanity.com/paper/2301.09819/) (2023)
- [On Tilted Losses in Machine Learning: Theory and Applications](https://mlsanity.com/paper/2109.06141/) (2021)
- [The Clever Hans Mirage: A Comprehensive Survey on Spurious Correlations in Machine Learning](https://mlsanity.com/paper/2402.12715/) (2024)
- [A Guide Through the Zoo of Biased SGD](https://mlsanity.com/paper/2305.16296/) (2023)
- [Improving Fairness in Deepfake Detection](https://mlsanity.com/paper/2306.16635/) (2023)
- [Non-convex Distributionally Robust Optimization: Non-asymptotic Analysis](https://mlsanity.com/paper/2110.12459/) (2021)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Adapting to Mixing Time in Stochastic Optimization with Markovian Data](https://mlsanity.com/paper/2202.04428/) (2022)
- [Representation Learning for Tabular Data: A Comprehensive Survey](https://mlsanity.com/paper/2504.16109/) (2025)
- [UMIX: Improving Importance Weighting for Subpopulation Shift via Uncertainty-Aware Mixup](https://mlsanity.com/paper/2209.08928/) (2022)
- [Calibrated Selective Classification](https://mlsanity.com/paper/2208.12084/) (2022)
- [Learning Fair Representation via Distributional Contrastive Disentanglement](https://mlsanity.com/paper/2206.08743/) (2022)
- [When AUC meets DRO: Optimizing Partial AUC for Deep Learning with Non-Convex Convergence Guarantee](https://mlsanity.com/paper/2203.00176/) (2022)
- [AI-Face: A Million-Scale Demographically Annotated AI-Generated Face Dataset and Fairness Benchmark](https://mlsanity.com/paper/2406.00783/) (2024)
- [Rank-based Decomposable Losses in Machine Learning: A Survey](https://mlsanity.com/paper/2207.08768/) (2022)
- [Stochastic Bias-Reduced Gradient Methods](https://mlsanity.com/paper/2106.09481/) (2021)

## Abstract (arXiv)

We propose and analyze algorithms for distributionally robust optimization of convex losses with conditional value at risk (CVaR) and chi2 divergence uncertainty sets. We prove that our algorithms require a number of gradient evaluations independent of training set size and number of parameters, making them suitable for large-scale applications. For chi2 uncertainty sets these are the first such guarantees in the literature, and for CVaR our guarantees scale linearly in the uncertainty level rather than quadratically as in previous work. We also provide lower bounds proving the worst-case optimality of our algorithms for CVaR and a penalized version of the chi2 problem. Our primary technical contributions are novel bounds on the bias of batch robust risk estimation and the variance of a multilevel Monte Carlo gradient estimator due to [Blanchet & Glynn, 2015]. Experiments on MNIST and ImageNet confirm the theoretical scaling of our algorithms, which are 9--36 times more efficient than full-batch methods.