# Generalization Bounds with Minimal Dependency on Hypothesis Class via Distributionally Robust Optimization

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 95 references that are in the map.
- First posted on arXiv 21 Jun 2021.

## Builds on (most cited first, 29 of 29)

- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Adversarial Machine Learning at Scale](https://mlsanity.com/paper/1611.01236/) (2016)
- [Robustness May Be at Odds with Accuracy](https://mlsanity.com/paper/1805.12152/) (2018)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Learning Models with Uniform Performance via Distributionally Robust Optimization](https://mlsanity.com/paper/1810.08750/) (2018)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [Generative Moment Matching Networks](https://mlsanity.com/paper/1502.02761/) (2015)
- [Distributionally Robust Stochastic Optimization with Wasserstein Distance](https://mlsanity.com/paper/1604.02199/) (2016)
- [Statistics of Robust Optimization: A Generalized Empirical Likelihood Approach](https://mlsanity.com/paper/1610.03425/) (2016)
- [Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning](https://mlsanity.com/paper/1908.08729/) (2019)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Regularization via Mass Transportation](https://mlsanity.com/paper/1710.10016/) (2017)
- [Distributionally Robust Optimization and Generalization in Kernel Methods](https://mlsanity.com/paper/1905.10943/) (2019)
- [Distributionally Robust Bayesian Optimization](https://mlsanity.com/paper/2002.09038/) (2020)
- [Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality](https://mlsanity.com/paper/2009.04382/) (2020)
- [From Data to Decisions: Distributionally Robust Optimization is Optimal](https://mlsanity.com/paper/1704.04118/) (2017)
- [Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimization](https://mlsanity.com/paper/1605.09349/) (2016)
- [Robust Sample Average Approximation](https://mlsanity.com/paper/1408.4445/) (2014)
- [Confidence Regions in Wasserstein Distributionally Robust Estimation](https://mlsanity.com/paper/1906.01614/) (2019)
- [Stable Adversarial Learning under Distributional Shifts](https://mlsanity.com/paper/2006.04414/) (2020)
- [The Empirical Likelihood Approach to Quantifying Uncertainty in Sample Average Approximation](https://mlsanity.com/paper/1604.02573/) (2016)
- [Distributional Reinforcement Learning via Moment Matching](https://mlsanity.com/paper/2007.12354/) (2020)
- [Sensitivity to Serial Dependency of Input Processes: A Robust Approach](https://mlsanity.com/paper/1606.06645/) (2016)
- [The discrete moment problem with nonconvex shape constraints](https://mlsanity.com/paper/1708.02079/) (2017)
- [Calibration of Distributionally Robust Empirical Optimization Models](https://mlsanity.com/paper/1711.06565/) (2017)
- [Worst-Case Expected Shortfall with Univariate and Bivariate Marginals](https://mlsanity.com/paper/1701.04167/) (2017)

## Built on by (most cited first, 9 of 9)

- [Decision-Focused Learning with Directional Gradients](https://mlsanity.com/paper/2402.03256/) (2024)
- [Group Distributionally Robust Dataset Distillation with Risk Minimization](https://mlsanity.com/paper/2402.04676/) (2024)
- [Exact Generalization Guarantees for (Regularized) Wasserstein Distributionally Robust Models](https://mlsanity.com/paper/2305.17076/) (2023)
- [Smoothed f-Divergence Distributionally Robust Optimization](https://mlsanity.com/paper/2306.14041/) (2023)
- [Universal generalization guarantees for Wasserstein distributionally robust models](https://mlsanity.com/paper/2402.11981/) (2024)
- [Certifiably Robust Model Evaluation in Federated Learning under Meta-Distributional Shifts](https://mlsanity.com/paper/2410.20250/) (2024)
- [Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Ability](https://mlsanity.com/paper/2503.04111/) (2025)
- [Progressive Power Homotopy for Non-convex Optimization](https://mlsanity.com/paper/2601.15915/) (2026)
- [Conservative neural posterior estimation via distributionally robust training](https://mlsanity.com/paper/2605.28516/) (2026)

## Abstract (arXiv)

Established approaches to obtain generalization bounds in data-driven optimization and machine learning mostly build on solutions from empirical risk minimization (ERM), which depend crucially on the functional complexity of the hypothesis class. In this paper, we present an alternate route to obtain these bounds on the solution from distributionally robust optimization (DRO), a recent data-driven optimization framework based on worst-case analysis and the notion of ambiguity set to capture statistical uncertainty. In contrast to the hypothesis class complexity in ERM, our DRO bounds depend on the ambiguity set geometry and its compatibility with the true loss function. Notably, when using statistical distances such as maximum mean discrepancy, Wasserstein distance, or φ-divergence in the DRO, our analysis implies generalization bounds whose dependence on the hypothesis class appears the minimal possible: The bound depends solely on the true loss function, independent of any other candidates in the hypothesis class. To our best knowledge, it is the first generalization bound of this type in the literature, and we hope our findings can open the door for a better understanding of DRO, especially its benefits on loss minimization and other machine learning applications.