mlsanityData to 7 Oct 2026

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

arXiv 2009.04382 ↗First posted 9 Sep 2020cs.LG math.PR stat.MLcited by 49

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 4; 2022: 5; 2023: 11; 2024: 7; 2025: 10; 2026: 12.

49 papers.

Sort:

By area:

  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  2. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  3. 2021Sinkhorn Distributionally Robust Optimizationcited by 38
  4. 2021Statistical Analysis of Wasserstein Distributionally Robust Estimatorscited by 27
  5. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  6. 2023Outlier-Robust Wasserstein DROcited by 16
  7. 2023Wasserstein distributional robustness of neural networkscited by 15
  8. 2021Sequential Domain Adaptation by Synthesizing Distributionally Robust Expertscited by 14
  9. 2022Instance-Dependent Generalization Bounds via Optimal Transportcited by 13
  10. 2023Unifying Distributionally Robust Optimization via Optimal Transport Theorycited by 12
  11. 2021Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimizationcited by 9
  12. 2023Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Modelscited by 9
37 more
  1. 2023Nash Equilibria, Regularization and Computation in Optimal Transport-Based Distributionally Robust Optimizationcited by 8
  2. 2022On Generalization and Regularization via Wasserstein Distributionally Robust Optimizationcited by 6
  3. 2023Smoothed f-Divergence Distributionally Robust Optimizationcited by 6
  4. 2024Universal generalization guarantees for Wasserstein distributionally robust modelscited by 5
  5. 2024Robust Distribution Learning with Local and Global Adversarial Corruptionscited by 5
  6. 2024Evaluating Model Performance Under Worst-case Subpopulationscited by 5
  7. 2023Learning Against Distributional Uncertainty: On the Trade-off Between Robustness and Specificitycited by 4
  8. 2022Wasserstein Distributionally Robust Optimization with Wasserstein Barycenterscited by 3
  9. 2023Out-Of-Domain Unlabeled Data Improves Generalizationcited by 3
  10. 2025Wasserstein Distributionally Robust Bayesian Optimization with Continuous Contextcited by 3
  11. 2025Wasserstein Distributionally Robust Nonparametric Regressioncited by 3
  12. 2026Regret Equals Covariance: A Closed-Form Characterization for Stochastic Optimizationcited by 3
  13. 2022Distributional Robustness Bounds Generalization Errorscited by 2
  14. 2024A Geometric Unification of Distributionally Robust Covariance Estimators: Shrinking the Spectrum by Inflating the Ambiguity Setcited by 2
  15. 2025Decision Making under Model Misspecification: DRO with Robust Bayesian Ambiguity Setscited by 2
  16. 2025Statistical and Algorithmic Foundations of Reinforcement Learningcited by 2
  17. 2023Adjusted Wasserstein Distributionally Robust Estimator in Statistical Learningcited by 1
  18. 2025DR-PETS: Learning-Based Control With Planning in Adversarial Environmentscited by 1
  19. 2025Distributionally Robust Optimization with Adversarial Data Contaminationcited by 1
  20. 2026Measure-to-measure Regression with Transformerscited by 1
  21. 2023Nonlinear Distributionally Robust Optimizationcited by 0
  22. 2024Distributionally and Adversarially Robust Logistic Regression via Intersecting Wasserstein Ballscited by 0
  23. 2024Optimal Transport for ε-Contaminated Credal Sets: To the Memory of Sayan Mukherjeecited by 0
  24. 2025Enhancing Distributional Robustness in Principal Component Analysis by Wasserstein Distancescited by 0
  25. 2025Unregularized limit of stochastic gradient method for Wasserstein distributionally robust optimizationcited by 0
  26. 2025Representation-Aware Distributionally Robust Optimization: A Knowledge Transfer Frameworkcited by 0
  27. 2025Wasserstein Distributionally Robust Optimization Through the Lens of Structural Causal Models and Individual Fairnesscited by 0
  28. 2026Concave Certificates: Geometric Framework for Distributionally Robust Risk and Complexity Analysiscited by 0
  29. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  30. 2026Risk-Averse Wasserstein Distributionally Robust Online Learningcited by 0
  31. 2026Statistical Guarantees for Distributionally Robust Optimization with Optimal Transport and OT-Regularized Divergencescited by 0
  32. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  33. 2026Ensemble Distributionally Robust Bayesian Optimisation with Continuous Contextcited by 0
  34. 2026Conservative neural posterior estimation via distributionally robust trainingcited by 0
  35. 2026Generalization Bounds on Optimal Control for Transformer Training and Wasserstein Distributional Robustnesscited by 0
  36. 2026A Unified Perspective on Conformal Prediction and Wasserstein Distributionally Robust Optimization for Uncertainty Quantificationcited by 0
  37. 2026Distributionally robust linear regression through the lens of adversarial trainingcited by 0