# Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality

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

## Key facts

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

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

- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Sinkhorn Distributionally Robust Optimization](https://mlsanity.com/paper/2109.11926/) (2021)
- [Statistical Analysis of Wasserstein Distributionally Robust Estimators](https://mlsanity.com/paper/2108.02120/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Wasserstein distributional robustness of neural networks](https://mlsanity.com/paper/2306.09844/) (2023)
- [Outlier-Robust Wasserstein DRO](https://mlsanity.com/paper/2311.05573/) (2023)
- [Sequential Domain Adaptation by Synthesizing Distributionally Robust Experts](https://mlsanity.com/paper/2106.00322/) (2021)
- [Instance-Dependent Generalization Bounds via Optimal Transport](https://mlsanity.com/paper/2211.01258/) (2022)
- [Unifying Distributionally Robust Optimization via Optimal Transport Theory](https://mlsanity.com/paper/2308.05414/) (2023)
- [Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization](https://mlsanity.com/paper/2106.11180/) (2021)
- [Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Models](https://mlsanity.com/paper/2305.17076/) (2023)
- [Nash Equilibria, Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimization](https://mlsanity.com/paper/2303.03900/) (2023)
- [Smoothed f-Divergence Distributionally Robust Optimization](https://mlsanity.com/paper/2306.14041/) (2023)
- [On Generalization and Regularization via Wasserstein Distributionally Robust Optimization](https://mlsanity.com/paper/2212.05716/) (2022)
- [Universal generalization guarantees for Wasserstein distributionally robust models](https://mlsanity.com/paper/2402.11981/) (2024)
- [Robust Distribution Learning with Local and Global Adversarial Corruptions](https://mlsanity.com/paper/2406.06509/) (2024)
- [Evaluating Model Performance Under Worst-case Subpopulations](https://mlsanity.com/paper/2407.01316/) (2024)
- [Learning Against Distributional Uncertainty: On the Trade-off Between Robustness and Specificity](https://mlsanity.com/paper/2301.13565/) (2023)
- [Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimization](https://mlsanity.com/paper/2605.14019/) (2026)
- [Wasserstein Distributionally Robust Optimization with Wasserstein Barycenters](https://mlsanity.com/paper/2203.12136/) (2022)
- [Out-Of-Domain Unlabeled Data Improves Generalization](https://mlsanity.com/paper/2310.00027/) (2023)
- [Wasserstein Distributionally Robust Bayesian Optimization with Continuous Context](https://mlsanity.com/paper/2503.20341/) (2025)
- [Wasserstein Distributionally Robust Nonparametric Regression](https://mlsanity.com/paper/2505.07967/) (2025)
- [Distributional Robustness Bounds Generalization Errors](https://mlsanity.com/paper/2212.09962/) (2022)
- [A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Set](https://mlsanity.com/paper/2405.20124/) (2024)
- [Decision Making under Model Misspecification: DRO with Robust Bayesian Ambiguity Sets](https://mlsanity.com/paper/2505.03585/) (2025)
- [Statistical and Algorithmic Foundations of Reinforcement Learning](https://mlsanity.com/paper/2507.14444/) (2025)
- [Measure-to-measure Regression with Transformers](https://mlsanity.com/paper/2605.28075/) (2026)
- [Adjusted Wasserstein Distributionally Robust Estimator in Statistical Learning](https://mlsanity.com/paper/2303.15579/) (2023)

## Abstract (arXiv)

Wasserstein distributionally robust optimization (DRO) aims to find robust and generalizable solutions by hedging against data perturbations in Wasserstein distance. Despite its recent empirical success in operations research and machine learning, existing performance guarantees for generic loss functions are either overly conservative due to the curse of dimensionality, or plausible only in large sample asymptotics. In this paper, we develop a non-asymptotic framework for analyzing the out-of-sample performance for Wasserstein robust learning and the generalization bound for its related Lipschitz and gradient regularization problems. To the best of our knowledge, this gives the first finite-sample guarantee for generic Wasserstein DRO problems without suffering from the curse of dimensionality. Our results highlight that Wasserstein DRO, with a properly chosen radius, balances between the empirical mean of the loss and the variation of the loss, measured by the Lipschitz norm or the gradient norm of the loss. Our analysis is based on two novel methodological developments that are of independent interest: 1) a new concentration inequality controlling the decay rate of large deviation probabilities by the variation of the loss and, 2) a localized Rademacher complexity theory based on the variation of the loss.