Source-linked AI summary
Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations
Peyman Mohajerin Esfahani, Daniel Kuhn
TL;DR
The paper tackles stochastic optimization with an unknown distribution observed only through finite data. It builds Wasserstein ambiguity sets around the empirical distribution and shows that many resulting worst-case problems have tractable convex or linear reformulations with finite-sample guarantees.
Problem
The distribution of uncertain parameters is unknown, while existing Wasserstein-robust formulations can require computationally burdensome global optimization.
Method
The paper centers a Wasserstein ambiguity ball at the empirical distribution and reformulates worst-case expectations using finite-dimensional convex optimization.
Results
Worst-case expectations become finite convex programs under broad loss-function conditions and explicit linear programs for several cases involving 1-norm or ∞-norm metrics.
Takeaways & Limitations
The resulting distributionally robust solutions combine tractable computation with confidence-based out-of-sample performance guarantees.
Takeaways & Limitations
For arbitrary convex uncertainty sets, the paper uses a conservative approximation rather than a simple exact reformulation.
Abstract
from arXiv · showhide
We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of the worst-case distribution within this Wasserstein ball. The state-of-the-art methods for solving the resulting distributionally robust optimization problems rely on global optimization techniques, which quickly become computationally excruciating. In this paper we demonstrate that, under mild assumptions, the distributionally robust optimization problems over Wasserstein balls can in fact be reformulated as finite convex programs---in many interesting cases even as tractable linear programs. Leveraging recent measure concentration results, we also show that their solutions enjoy powerful finite-sample performance guarantees. Our theoretical results are exemplified in mean-risk portfolio optimization as well as uncertainty quantification.
1. Introduction
The paper addresses data-driven stochastic optimization when the unknown distribution is inferred from finite samples and classical formulations suffer from overfitting and computationally hard integration. It uses Wasserstein ambiguity sets to obtain tractable reformulations with statistical guarantees.
- Motivation: Finite data can produce disappointing out-of-sample decisions, while evaluating stochastic-program objectives may be #P-hard.These difficulties motivate distributionally robust alternatives that account for distributional uncertainty and computational complexity.
- Distributionally robust modeling: Distributionally robust optimization minimizes worst-case expected cost over an ambiguity set of plausible probability distributions.The worst-case approach can mitigate the optimizer’s curse and may replace intractable integrals with tractable optimization problems.
- Ambiguity sets: A useful ambiguity set should contain the true distribution with high confidence, exclude pathological distributions, be data-parameterizable, and admit tractable reformulations.These requirements create a trade-off between statistical coverage, conservativeness, and computational solvability.
- Wasserstein ambiguity sets: The paper centers Wasserstein balls at the empirical distribution and uses measure concentration to guarantee containment of the unknown distribution with confidence 1 − β.The balls include continuous and discrete distributions sufficiently close to the empirical distribution under transportation cost.
- Contributions: The paper further develops efficient constructions of extremal distributions and investigates theoretical and experimental out-of-sample performance as training-sample size varies.The results target practical computation and finite-sample reliability for data-driven decisions.
- Contributions: Wasserstein worst-case expectations admit finite-dimensional convex reformulations for maxima of finitely many concave functions and explicit linear programs for several function classes under 1-norm or ∞-norm metrics.The paper extends tractability beyond finite-support uncertainty without space tessellation or discretization.
2. Data-Driven Stochastic Programming
The paper replaces the unknown data-generating distribution with a Wasserstein ambiguity set built from finite training samples. Its resulting distributionally robust decisions provide confidence certificates, asymptotic consistency, and tractable formulations under stated conditions.
- Problem setup: The stochastic program minimizes expected loss over decisions x, but the true distribution is unknown and only partially observed through N independent samples.The training dataset is itself a random object governed by the product distribution induced by the unknown distribution.
- Performance guarantees: Out-of-sample performance is evaluated under a new sample independent of training data, so exact performance cannot be computed when the distribution is unknown.The paper therefore seeks a low certificate with high reliability rather than the unattainable exact optimum.
- Sample-average approximation: The sample-average approximation replaces the unknown distribution with the uniform empirical distribution on the observed samples.Under compactness and uniform continuity assumptions, its optimal value and solutions converge almost surely as N increases.
- Wasserstein approach: The paper constructs a Wasserstein ball around the empirical distribution to define a high-confidence ambiguity set and an upper certificate for out-of-sample performance.This approach explicitly accounts for ignorance of the true distribution when acquiring additional samples is impossible or expensive.
- Guarantees: For a carefully chosen ambiguity-set size, the certificate gives a 1 − β confidence bound on the data-driven solution’s out-of-sample performance.The guarantee is stated as a finite-sample property.
- Guarantees: As N tends to infinity, the certificate and data-driven solution converge to the true stochastic program’s optimal value and an optimizer, respectively.This establishes the paper’s asymptotic consistency claim.
- Tractability: For many loss functions and feasible sets, the distributionally robust problem is computationally tractable and admits a reformulation resembling the sample-average approximation.The paper identifies tractability as its main contribution relative to global-optimization approaches.
3. Wasserstein Metric and Measure Concentration
The Wasserstein metric measures distributional distance through optimal transportation and supports ambiguity balls centered at empirical data. Under light-tailed distributions, measure concentration yields finite-sample guarantees and asymptotic consistency for distributionally robust solutions, although the prescribed radius can be over-conservative in practice.
- Wasserstein metric: The Wasserstein metric is defined through the minimum transportation cost between probability distributions, with the norm determining transportation costs.Its dual characterization relates Wasserstein proximity to agreement on functions with uniformly bounded slopes.
- Ambiguity set: The paper constructs a Wasserstein ambiguity ball around the empirical distribution and interprets its radius as a confidence set for the unknown distribution.The radius is selected using a measure concentration bound under a light-tail assumption.
- Asymptotic consistency: As the sample size increases, the Wasserstein radius tends to zero for fixed β, and the distributionally robust optimal value converges downward to the stochastic program’s optimal value.This requires the stated regularity and growth conditions on the loss function.
- Asymptotic consistency: Any accumulation point of the distributionally robust optimizers is almost surely optimal for the original stochastic program under the theorem’s additional closedness and lower-semicontinuity assumptions.The convergence result depends on the full set of regularity conditions; relaxing them can invalidate asymptotic convergence.
- Practical limitation: The theoretically calibrated Wasserstein radius can produce over-conservative solutions because it may define a ball larger than necessary and ignores the training data.Random, data-dependent radii are identified as a more efficient alternative.
4. Solving Worst-Case Expectation Problems
The paper converts worst-case expectation problems over Wasserstein ambiguity sets from infinite-dimensional distribution optimization into finite convex programs under a pointwise-maximum concavity assumption. It also characterizes when worst-case distributions exist and how to construct distributions attaining the supremum asymptotically.
- Convex reduction: A worst-case expectation over a Wasserstein ambiguity set equals a finite convex program when the loss is a pointwise maximum of finitely many concave functions.The reduction relies on convexity of the uncertainty set and proper, convex, lower-semicontinuous negative constituent losses.
- Convex reduction: The reformulation uses conjugates, the support function of the uncertainty set, dual norms, and epigraph variables to replace distributional optimization with finite constraints.The resulting program is already finite after the conjugacy-based reformulation, and the semi-infinite constraint admits a robust counterpart.
- Approximation: If the convexity assumption fails, the same finite program remains a conservative upper bound rather than an exact reformulation.Exactness is recovered under the stated convexity assumption through strong duality and minimax arguments.
- Extremal distributions: Worst-case distributions may not exist; instead, the paper constructs sequences of distributions in the Wasserstein ball whose expectations approach the supremum.Existence is guaranteed when the uncertainty set is compact or the loss is concave, because the constructed sequence has an accumulation point.
- Extremal distributions: The extremal distributions can place support outside the training-sample support, distinguishing Wasserstein ambiguity sets from total-variation and Kullback-Leibler sets.This feature supports robustness against perturbations of observed data points.
5. Special Loss Functions
The paper specializes its convex reduction to piecewise affine losses, safety-event probabilities, and related stochastic-programming models. Under 1-norm or ∞-norm Wasserstein metrics, many resulting formulations become linear programs with size governed by the data and loss complexity.
- Piecewise affine losses: Piecewise affine convex and concave losses over polyhedral uncertainty sets admit explicit finite conic reformulations.These losses arise in option pricing, risk management, and two-stage stochastic programming.
- Uncertainty quantification: For data-dependent sets and radius εN(β), the probability formulations provide 1 − β confidence bounds on the unknown distribution’s event probabilities.This follows when the true distribution belongs to the Wasserstein ball with probability 1 − β.
- Uncertainty quantification: Worst-case and best-case probabilities of polyhedral safety events can be computed by representing indicator functions as maxima of concave functions.The resulting formulations use the same convex-reduction machinery as the loss-expectation problem.
- Uncertainty quantification: At Wasserstein radius ε = 0, the probability formulations reduce to empirical fractions of samples outside or inside the relevant polytope.The open-polytope formulation concerns samples outside A, while the closed-polytope formulation concerns samples inside A.
- Piecewise affine losses: For 1-norm or ∞-norm Wasserstein metrics, the piecewise affine formulations reduce to linear programs scaling with the number of samples and affine pieces.Except for two-stage right-hand-side uncertainty, the resulting linear programs scale polynomially in the problem dimensions.
- Computational tractability: The convex programs studied have computational complexity independent of the Wasserstein-ball radius ε.
6. Tractable Extensions
The paper extends tractable Wasserstein reformulations to separable stochastic-process losses and general convex losses. Separable models retain finite convex structure, while arbitrary convex losses generally yield upper bounds that become exact under unrestricted uncertainty.
- Separable loss functions: Under the convexity assumptions, the separable convex program equals the worst-case expectation, and constructed product distributions attain the supremum asymptotically.The distributions can be generated efficiently through a convex program despite having NKT discretization points.
- Separable loss functions: Separable losses over stochastic processes admit a finite convex reformulation with O(NKT) decision variables and constraints.The direct maximum representation would require O(K^T) variables and constraints, so the modified formulation avoids exponential dependence on the time horizon.
- Separable loss functions: If each separable constituent is affine and the base norm is 1-norm or ∞-norm, the reformulation becomes a tractable linear program.
- Convex loss functions: For proper, convex, lower-semicontinuous losses, the worst-case expectation is bounded by the empirical average plus the correction term κε.The parameter κ captures the loss’s steepness and the bound is exact when the uncertainty set is R^m.
- Convex loss functions: The convex-loss reformulation is generally conservative because arbitrary convex uncertainty sets lack a simple exact reformulation of the relevant support-function expression.Replacing the support function with that of R^m produces a conservative approximation.
- Convex loss functions: When the loss’s Lipschitz modulus is independent of the decision, distributionally robust and sample-average optimization share the same minimizers for every Wasserstein radius.The paper gives the newsvendor loss as an example.
7. Numerical Results
The numerical studies examine Wasserstein distributionally robust portfolio optimization and uncertainty quantification, including how radius selection affects performance, reliability, and convergence. Results support theoretical predictions about equal weighting under high ambiguity and shrinking radii with larger samples.
- Portfolio setup: The portfolio experiments use 10 assets whose returns combine a common systematic factor with asset-specific independent normal risks.Returns are modeled as ξ_i = ψ + ζ_i, with ψ and ζ_i independent normal random variables.
- Performance and reliability: Out-of-sample performance improves until a critical radius εcrit, then deteriorates, while certificate reliability increases with ε and rises sharply near εcrit.The authors report this pattern consistently across simulations but could not validate it theoretically.
- Performance and reliability: SAA is over-optimistic in-sample, whereas LCX and Wasserstein methods are cautious; cross-validation slightly improves robust methods’ out-of-sample performance but increases computational cost by a factor of k.The reliability of the robust certificates also increases significantly relative to the naïve holdout method.
- Radius calibration: Optimizing out-of-sample performance can sacrifice reliability, motivating radius selection that instead targets a prescribed reliability level.Bootstrap-based radius estimates may be biased because resamples are not independent.
- Uncertainty quantification: Data-driven Wasserstein radii tend to zero as N increases, with an approximately N^-1/2 convergence rate that may be optimal in the singleton-decision case.The observed rate suggests the a priori N^-1/m rate from Theorem 3.4 is overly pessimistic in practice.
- Uncertainty quantification: For a data-dependent event set, the supremum and infimum probabilities over the Wasserstein ball provide upper and lower confidence bounds, respectively.The upper bound has confidence 1 − β under the stated construction.
- Uncertainty quantification: Confidence intervals for the excess bounds shrink toward zero as the sample size increases, although evaluating the true probability may require a much larger dataset.The data-driven bounds use only the N training samples, whereas P[A] can be difficult to estimate for rare events.
Appendix A.
Appendix A establishes a constructive approximation result for upper semicontinuous functions with linear growth. It builds Lipschitz continuous majorants that decrease pointwise to the target function.
- An upper semicontinuous function with linear growth admits a non-increasing sequence of Lipschitz continuous majorants converging pointwise to it.The majorants preserve the same linear growth bound.
- The approximation is constructive, with each majorant defined through a maximization involving the target function and a norm-based penalty.The construction ensures each approximant dominates the target function.
- Each approximant remains bounded by the target linear-growth envelope and is Lipschitz continuous with constant kL.The index k controls the Lipschitz constant while the sequence converges toward the target.
- The proof establishes convergence by showing the maximizing points ξ_k approach ξ as k tends to infinity.Upper semicontinuity supplies the final inequality needed for pointwise convergence.