Source-linked AI summary
Wasserstein Distributionally Robust Optimization: Theory and Applications in Machine Learning
Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, Soroosh Shafieezadeh-Abadeh
TL;DR
Data-driven decisions must perform under an unknown distribution inferred from finitely many samples, while nominal optimization can amplify estimation error. The tutorial studies Wasserstein distributionally robust optimization, which optimizes over distributions near a sample-based nominal model and often yields convex reformulations with out-of-sample and asymptotic guarantees. It also connects robustification to regularization and learning tasks including classification and regression.
Problem
Finite-sample data-driven decisions face unknown distributions, high-dimensional estimation difficulty, and an optimizer’s curse that can make nominal risk optimistic.
Method
The tutorial uses Wasserstein ambiguity sets around sample-based nominal distributions to robustify risk evaluation and decision problems.
Results
Wasserstein distributionally robust problems often admit finite convex reformulations and provide finite-sample out-of-sample bounds and asymptotic optimizer consistency.
Takeaways & Limitations
Wasserstein robustification offers probabilistic interpretations of regularization and motivates approaches to classification, regression, maximum likelihood estimation, and minimum mean square error estimation.
Takeaways & Limitations
Estimator accuracy remains fundamentally limited in some families, and Wasserstein estimation rates can suffer from the curse of dimensionality.
Abstract
from arXiv · showhide
Many decision problems in science, engineering and economics are affected by uncertain parameters whose distribution is only indirectly observable through samples. The goal of data-driven decision-making is to learn a decision from finitely many training samples that will perform well on unseen test samples. This learning task is difficult even if all training and test samples are drawn from the same distribution -- especially if the dimension of the uncertainty is large relative to the training sample size. Wasserstein distributionally robust optimization seeks data-driven decisions that perform well under the most adverse distribution within a certain Wasserstein distance from a nominal distribution constructed from the training samples. In this tutorial we will argue that this approach has many conceptual and computational benefits. Most prominently, the optimal decisions can often be computed by solving tractable convex optimization problems, and they enjoy rigorous out-of-sample and asymptotic consistency guarantees. We will also show that Wasserstein distributionally robust optimization has interesting ramifications for statistical learning and motivates new approaches for fundamental learning tasks such as classification, regression, maximum likelihood estimation or minimum mean square error estimation, among others.
1. Introduction
Wasserstein distributionally robust optimization addresses estimation error and the optimizer’s curse by optimizing against distributions near a sample-based nominal model. The approach offers tractable reformulations, finite-sample and asymptotic guarantees, and regularization interpretations.
- 1. Introduction: Unknown distributions make nominal risk estimates and decisions vulnerable to estimation error, which optimization can amplify.The resulting optimizer’s curse produces optimistic in-sample risk and larger out-of-sample risk.
- 1. Introduction: Estimator tuning cannot overcome fundamental accuracy limits, so mitigating the optimizer’s curse may require robustifying the risk evaluation and decision problems.For some settings, increasing the sample size is the remaining way to reduce estimation error, although it may be expensive or impossible.
- 1. Introduction: The empirical distribution is essentially optimal among N-point estimators, with high-confidence type-1 Wasserstein error decaying at rate N^-1/m.This rate is optimal for approximating arbitrary distributions supported on a compact subset of R^m with N atoms.
- 1. Introduction: Distributionally robust optimization replaces nominal risk and decision problems with worst-case problems over an ambiguity set containing plausible true distributions.The ambiguity set is defined using known support information and uncertainty around the nominal distribution.
- 1. Introduction: Distributionally robust models can provide out-of-sample risk guarantees, polynomial-time convex reformulations, and asymptotic convergence of their optimizers.These benefits depend on suitable ambiguity-set calibration and problem structure.
- 1. Introduction: Wasserstein robustification is often equivalent to regularization, adding norm penalties that penalize hypothesis complexity and producing shrinkage estimators in some likelihood models.The tutorial connects this interpretation to classification, regression, and other statistical learning tasks.
2. Computation
Wasserstein worst-case risk can be bounded or exactly reformulated through convex optimization, with tractability depending on the nominal distribution, loss structure, and Wasserstein order. The section also identifies computational and attainment limits, including hardness for general distributions and non-attainment when p = 1.
- Computational limits: #P-hardness applies even to computing type-p Wasserstein distance between a hypercube-uniform distribution and a two-point distribution.The hardness holds under the Euclidean norm.
- Tractable bounds: For p = 2 with the Euclidean norm, a moment-based analytical lower bound is exact for elliptical distributions with the same density generator.The bound depends only on first- and second-order moments, although it may be loose for different density generators.
- Tractable bounds: Jensen’s inequality yields efficiently computable upper bounds, while Lipschitz regularization converts worst-case risk control into a convex optimization problem when the loss class is convex.The Lipschitz-regularized nominal risk provides the upper bound, and the resulting objective is convex in the loss function.
- Empirical nominal distributions: Strong duality reformulates worst-case risk as a convex minimization problem through the Moreau-Yosida regularization, and empirical nominal distributions admit finite convex reformulations under suitable loss assumptions.The reformulation is jointly convex in the regularization parameter and loss, while piecewise concave losses yield explicit finite programs.
- Attainment and exactness: For piecewise concave losses, the empirical robust lower bound is exact when the loss is globally concave, but worst-case distributions may fail to exist for p = 1.For p > 1, the worst-case risk is attained; for p = 1, Example 4 constructs only an asymptotically optimal sequence.
- Attainment and exactness: For convex losses with p = 1 and unrestricted support, worst-case risk equals the Lipschitz-regularized empirical loss exactly.This makes the upper bound exact under the stated support and convexity conditions.
3. Performance Guarantees
Wasserstein ambiguity sets provide finite-sample upper confidence bounds for true and out-of-sample risk, while calibrated radii support asymptotic consistency. The guarantees depend on distributional assumptions, and empirical Wasserstein radii can suffer a fundamental curse of dimensionality.
- Under suitable calibration, Wasserstein worst-case optimal risk converges almost surely to the true optimal risk as N tends to infinity.
- The empirical Wasserstein distribution converges to the data-generating distribution in probability, enabling finite-sample and asymptotic guarantees.
- For dimensions m > 2, the critical radius decays as O(N −1/m), and halving it requires increasing the sample size by 2^m.
- Wasserstein balls with calibrated radii provide upper confidence bounds on true risk uniformly across admissible loss functions.
- The optimal value of the distributionally robust decision problem provides an upper confidence bound on the out-of-sample performance of its optimizers.
- Gelbrich risk offers analogous finite-sample upper confidence bounds, but asymptotic consistency requires elliptical distributions, Ξ = Rm, and quadratic loss functions.
4. Distributionally Robust Optimization in Machine Learning
The tutorial applies Wasserstein distributional robustness to classification, regression, and maximum likelihood estimation, yielding convex reformulations and regularization interpretations. It also develops a Wasserstein shrinkage estimator with structural properties for precision-matrix estimation.
- Wasserstein distributionally robust optimization motivates approaches to classification, regression, maximum likelihood estimation, and minimum mean square error estimation.
- Classification and regression: Unknown data distributions make optimal classification and regression rules inaccessible, motivating worst-case expected-loss optimization over Wasserstein ambiguity sets.
- Classification: For classification, the robust model admits finite convex reformulations under convexity and piecewise-linearity conditions, and reduces to empirical or regularized risk minimization in special cases.
- Regression: For regression, convex reformulations are available under stated conditions, while p = 2 with square error yields a specialized reduction.
- Regularization by robustification: Robustification is equivalent to regularization when there is no output uncertainty, with the regularizer determined by the dual norm and weighted by the Wasserstein radius.
- Maximum likelihood estimation: Robust maximum likelihood estimation produces a precision matrix sharing eigenvectors with the sample covariance while transforming its eigenvalues through a nonlinear shrinkage rule.
- Maximum likelihood estimation: The Wasserstein shrinkage estimator remains invertible, is rotation-equivariant, and improves its condition number monotonically toward 1 as ambiguity increases.
A. Elliptical Distributions
The section defines elliptical distributions through a density generator, location, and covariance structure, and points to examples including t-distributions. It also notes the role of degrees of freedom in the t-distribution.
- An elliptical distribution has density determined by a location vector, covariance matrix, normalization constant, and nonnegative density generator.
- Table 3 provides examples of elliptical distributions.
- For the t-distribution, ν denotes degrees of freedom and Γ denotes the gamma function.
B. Conjugates, Support Functions and Dual Norms
This section introduces conjugates, support functions, indicators, and dual norms as convex-analytic tools used in Wasserstein optimization reformulations.
- Conjugates: The conjugate of a function is formed by taking the supremum of a linear term minus that function; proper convex lower-semicontinuous functions equal their biconjugates.
- Support functions: An indicator function records set membership through values 0 and ∞, while the support function takes the supremum of a linear form over the set.
- Dual norms: The dual norm is defined by maximizing an inner product over the unit ball, and taking the dual norm twice recovers the original norm.