PaperlayerView exact revision on arXiv

Source-linked AI summary

Distributionally Robust Stochastic Optimization with Wasserstein Distance

Rui Gao, Anton J. Kleywegt

arXiv:1604.02199v3math.OC

TL;DR

When the true distribution is unknown, DRSO requires an ambiguity set that captures relevant alternatives without sacrificing tractability. The paper studies Wasserstein balls, derives strong-duality and worst-case-distribution results in a general setting, and shows that data-driven DRSO can be approximated through robust optimization, including applications beyond finite-dimensional convex spaces.

  • Problem

    Common φ-divergence ambiguity sets may exclude relevant distributions or generate overly extreme worst-case behavior, while DRSO needs an appropriate and tractable distributional uncertainty set.

  • Method

    The paper analyzes Wasserstein-distance balls around arbitrary nominal distributions using strong duality and constructive characterizations of worst-case distributions.

  • Results

    Data-driven DRSO can be approximated to any accuracy by robust optimization, and the framework applies to non-convex, infinite-dimensional process-control spaces.

  • Takeaways & Limitations

    Wasserstein ambiguity sets provide structured distributional hedging that supports tractable robust-optimization approximations and applications to point processes.

  • Takeaways & Limitations

    φ-divergence alternatives can be highly sensitive to arbitrary support specifications and may fail to include distributions outside the nominal support.

Abstract

from arXiv · show

Distributionally robust stochastic optimization (DRSO) is an approach to optimization under uncertainty in which, instead of assuming that there is a known true underlying probability distribution, one hedges against a chosen set of distributions. In this paper we first point out that the set of distributions should be chosen to be appropriate for the application at hand, and that some of the choices that have been popular until recently are, for many applications, not good choices. We next consider sets of distributions that are within a chosen Wasserstein distance from a nominal distribution. Such a choice of sets has two advantages: (1) The resulting distributions hedged against are more reasonable than those resulting from other popular choices of sets. (2) The problem of determining the worst-case expectation over the resulting set of distributions has desirable tractability properties. We derive a strong duality reformulation of the corresponding DRSO problem and construct approximate worst-case distributions explicitly via the first-order optimality conditions of the dual problem. Our contributions are four-fold. (i) We identify necessary and sufficient conditions for the existence of a worst-case distribution, which are naturally related to the growth rate of the objective function. (ii) We show that the worst-case distributions resulting from an appropriate Wasserstein distance have a concise structure and a clear interpretation. (iii) Using this structure, we show that data-driven DRSO problems can be approximated to any accuracy by robust optimization problems, and thereby many DRSO problems become tractable by using tools from robust optimization. (iv) Our strong duality result holds in a very general setting. As examples, we show that it can be applied to infinite-dimensional process control and intensity estimation for point processes.

1. Introduction

The paper motivates DRSO as a response to uncertainty about the true distribution and argues that Wasserstein ambiguity sets better reflect application-specific proximity while retaining tractability. It develops strong duality, characterizes worst-case distributions, and connects data-driven DRSO to robust optimization in broad settings.

  • Motivation: DRSO hedges against a chosen set of distributions rather than requiring a known true distribution.This addresses settings where the distribution is unknown or where a true underlying distribution may not apply.
  • Motivation: Choosing an ambiguity set requires balancing application-specific distributional realism with tractability.The paper contrasts moment-based and distance-based constructions and focuses on Wasserstein distance to encode closeness between outcomes.
  • Motivation: φ-divergence balls may exclude relevant distributions or hedge against distributions that are too extreme.For example, Kullback–Leibler balls cannot add support where the nominal distribution has zero mass, whereas Burg entropy allows shifts whose amount does not depend on how extreme the destination is.
  • Motivation: Wasserstein distance accounts for how far probability mass moves, distinguishing the true image from a pathological image more appropriately than KL divergence.In the example, KL divergence ranks the true image farther from the nominal image, while Wasserstein distance gives W1(µtrue,ν) = 30.70 < W1(µpathol,ν) = 84.03.
  • Main contributions: The paper establishes strong duality for arbitrary measurable objectives on Polish spaces and uses a constructive approach to characterize worst-case distributions.The approach also supports broader settings than prior results, including arbitrary nominal distributions, higher-order Wasserstein distances, and nonconvex infinite-dimensional uncertainty spaces.
  • Main contributions: Data-driven DRSO problems can be approximated to any accuracy by robust optimization problems, making robust-optimization tools applicable to many such models.The paper also gives a tractable semidefinite-programming approximation for two-stage linear DRSO with linear decision rules.

2. Notation and Preliminaries

The preliminaries define probability measures, push-forward measures, and Wasserstein distance on Polish spaces. They interpret Wasserstein distance as minimum transport cost and record its convergence and Lipschitz-function properties for the later duality analysis.

  • Measure-theoretic setting: The framework uses a Polish space Ξ with its Borel σ-algebra and probability-measure classes P(Ξ) and Pp(Ξ).Pp(Ξ) contains probability measures with finite p-th moment.
  • Measure-theoretic setting: A push-forward measure T#ν transports ν through a measurable map T by assigning each measurable set the mass of its preimage.The canonical projections on product spaces provide the associated marginal measures.
  • Wasserstein distance: Wasserstein distance Wp(µ,ν) is defined as the minimum transport cost for redistributing mass between probability measures using the metric cost dp.The minimum is attained under the stated continuity and lower-semicontinuity conditions.
  • Wasserstein distance: For discrete measures, Wasserstein distance reduces to a classical transportation problem in linear programming.The transport formulation moves masses between the support points of the two distributions.
  • Wasserstein distance: Wasserstein distance captures the image example’s transport geometry because pathological histograms require moving mass over relatively long distances.This yields W1(µpathol,ν) > W1(µtrue,ν).
  • Duality and continuity: Kantorovich duality provides a dual representation of Wasserstein distance, with a simpler form available for p = 1.For an L-Lipschitz function, the Wasserstein ball bounds expectation differences by Lθ.
  • Duality and continuity: Wasserstein convergence metrizes weak convergence in Pp(Ξ) and additionally controls convergence of the p-th moment.The distance is therefore stronger than weak convergence alone in the relevant moment sense.
  • Connection to DRSO: The later analysis applies these definitions to the inner maximization of DRSO over a Wasserstein ball.The objective is treated pointwise in the decision variable after suppressing x.

3. Tractable Reformulation via Duality

The paper reformulates Wasserstein-based DRSO through strong duality and characterizes when worst-case distributions exist. This structure yields sparse worst-case distributions, robust-optimization approximations, and applications beyond finite-dimensional convex settings.

  • Dual reformulation: The dual problem is a one-dimensional convex minimization over λ, the multiplier of the Wasserstein constraint.Its regularization term is the Moreau-Yosida regularization of −Ψ with parameter 1/λ.
  • Generality and applications: The framework covers arbitrary nominal Borel measures and applies to infinite-dimensional, non-convex process-control and point-process settings.The paper specifically considers spaces of finite counting measures and nominal point-process distributions, beyond assumptions used in earlier finite-dimensional results.
  • Dual reformulation: The paper proves strong duality for finite growth rate κ, with vP = vD < ∞, and handles infinite κ by showing vP = vD = ∞.The result applies to arbitrary p ∈ [1,∞), nominal probability measures, and integrable objectives in the stated setting.
  • Existence and structure: A worst-case distribution exists exactly under conditions determined by the dual minimizer relative to the objective’s growth rate κ.The cases include a dual minimizer strictly above κ, a unique minimizer at positive κ, or a unique zero minimizer with a nonempty maximizer set.
  • Robust-optimization approximation: For Lipschitz Ψ with p = 1, robust-optimization approximations achieve an O(1/N)-approximation, while concave objectives make the approximation exact.The approximation uses an uncertainty set containing equally weighted distributions supported on at most NK points.

4. Applications

The applications extend Wasserstein DRSO to point-process control, intensity estimation, and worst-case risk analysis. These examples use empirical or nominal process distributions and exploit tractable reformulations or structured worst-case distributions.

  • On/Off System Control: On/off control maximizes profit by choosing when an exogenous point-process-driven system is switched on.The system incurs cost c per unit time while on, and each arrival during that time contributes one unit of revenue.
  • On/Off System Control: Wasserstein ambiguity sets avoid the degenerate controls produced by maximizing expected profit under empirical or KL-divergence nominal distributions.The Wasserstein formulation allows nearby arrival times to influence the decision rather than restricting probability to observed paths.
  • On/Off System Control: For empirical point-process data, the optimal control can be restricted to systems switched on over a finite disjoint union of positive-length intervals.The equivalent dual reformulation can be solved by a greedy algorithm.
  • On/Off System Control: With five sample paths in the illustrated instance, the DRSO control is close to the control obtained when the true process is known.The example uses λ = c = 20 and a sinusoidal intensity whose true optimal on-set has three intervals.
  • Intensity Estimation: The intensity-estimation application compares Wasserstein DRSO and maximum likelihood estimators using piecewise-constant intensity functions and cross-validation to select the Wasserstein radius.The numerical study uses 20 sample paths and 20, 50, or 100 pieces.
  • Worst-Case Risk: The paper also derives a unique-equation characterization for worst-case portfolio value-at-risk under a Wasserstein ambiguity set.The result assumes a nominal distribution with positive density and a fixed portfolio allocation.

5. Discussions

The discussion compares Wasserstein ambiguity sets with φ-divergence alternatives and develops tractable approximations for two-stage DRSO. It emphasizes realistic worst-case distributions, broad applicability, and semidefinite reformulations.

  • Newsvendor Problem: Comparison with φ-divergence: φ-divergence ambiguity sets may exclude relevant distributions or produce worst-case behavior sensitive to arbitrary support choices.For some divergences, nominal zero probabilities force corresponding probabilities to remain zero; for others, mass moves toward a worst scenario at the support boundary.
  • Newsvendor Problem: Comparison with φ-divergence: Wasserstein worst-case distributions allocate probability toward both low and high demand, with smooth intermediate variation for geometric demand.Burg entropy instead creates boundary spikes that are sensitive to the truncation value B.
  • Tractable Approximations: Two-stage DRSO is generally NP-hard, but robust-optimization tools yield tractable approximations under Wasserstein ambiguity sets.The construction uses uncertainty sets around empirical samples and affine recourse decisions.
  • Tractable Approximations: The paper gives an exact semidefinite-program reformulation of the affinely adjustable robust counterpart for a two-stage linear DRSO problem.This provides a tractable approximation when the affine decision-rule approximation is reasonably good.
  • Scope and Generality: The strong-duality framework supports robust-optimization approximations of any accuracy and becomes exact when the objective is concave in the uncertainty.For convex decision dependence, the corresponding DRSO problem can be formulated as a convex-concave saddle-point problem.

Appendix A: Proofs for Section 2

The appendix establishes an inequality for powers and uses it to control growth terms in the dual analysis. The supporting lemmas provide bounds needed for finiteness arguments.

  • Lemma 8: For p ≥ 1 and ε > 0, Lemma 8 establishes a constant C_p(ε) controlling the relevant power-growth inequality.The proof treats x = 0 separately and uses t = y/x when x > 0.
  • Role in the Proof: Together, the lemmas support finiteness properties required in the appendix’s duality and growth-rate analysis.The supplied proof passages establish the auxiliary bounds rather than the paper’s final application results.
  • Lemma 8: The constant C_p(ε) is finite because the asymptotic ratio of (1+t)^p−1 to t^p−1 converges to 1.Monotonicity of the auxiliary function then verifies the inequality for all nonnegative arguments.
  • Lemma 9: Lemma 9 supplies a uniform bound for the dual-growth expressions when λ > λ1 > κ.This lemma is derived from the power-growth inequality in Lemma 8.

B.1.3. Proof of Lemma 2

The proof characterizes when the dual threshold κ is finite by relating it to the objective’s growth relative to the pth power of the metric. It proves both directions through bounds and divergence arguments.

  • Finite κ: If the objective has a global p-growth upper bound from some reference point, then κ is finite.The proof first establishes that the relevant dual function is finite for λ above the growth threshold.
  • Proof Technique: The proof uses the metric inequality (a+b)^p ≤ 2^(p−1)(a^p+b^p) to transfer growth bounds between reference points.This supports the contradiction and finiteness arguments for arbitrary ζ.
  • Infinite κ: If no such global p-growth bound exists, then κ equals infinity.For every λ, the infimum defining the dual expression becomes −∞, forcing κ = ∞.
  • Threshold Characterization: The growth condition is equivalent to an integrable-penalty formulation involving an L1(ν) function M(ζ).This equivalence rewrites the pointwise growth inequality in terms of the infimum appearing in the dual analysis.
  • Threshold Characterization: The threshold κ is bounded below by κ0, including when κ0 is positive and λ lies below κ0.The proof constructs points where λd^p(ξ,ζ) − Ψ(ξ) is arbitrarily negative.

B.1.4. Proof of Lemma 3.

The proof establishes measurability and measurable-selection properties for the auxiliary functions used in the dual formulation. It also derives monotonicity, concavity, and finiteness properties needed for the dual analysis.

  • Measurability: The functions Φ(λ,·), C(λ,·,δ), and D0(λ,·) are measurable by measurable projection arguments.The proof also uses measurability preservation under limsup and liminf.
  • Measurable selections: Aumann’s measurable selection theorem provides ν-measurable selections from the relevant argmin and feasible sets.These selections are constructed for ν-almost all ζ under the stated measurability and Polish-space assumptions.
  • Regularity and monotonicity: For each ζ, Φ(·,ζ) is nondecreasing and upper-semicontinuous, while the derived distance bounds vary monotonically with λ.The proof obtains these properties from Φ being an infimum of nondecreasing, continuous, or affine functions.
  • Dual objective: The dual objective h is convex, lower-semicontinuous, finite for λ>κ, and diverges under the stated growth condition.These properties support existence of a dual minimizer and the equality vP = ∞ = vD in the unbounded case.

B.1.8. Proof of Corollary 1.

The proof characterizes when a worst-case distribution exists and constructs one from measurable transport maps. It also shows that these maps can yield an optimal transport coupling and a concise pushforward representation.

  • Construction: Measurable selections from the dual argmin sets generate primal-feasible distributions that attain the dual value.First-order optimality conditions determine the mixing needed in the cases with λ* > κ or λ* = κ > 0.
  • Existence conditions: A primal optimal distribution exists under one of three conditions involving the dual minimizer: λ* > κ, a unique λ* = κ > 0, or a unique λ* = κ = 0 with an attained objective maximum.The converse proof shows these conditions are also necessary when a primal optimum exists.
  • Optimality structure: Any primal optimum must use conditional transport distributions supported on arg minξ∈Ξ{λ*dp(ξ,ζ)−Ψ(ξ)} for ν-almost all ζ.This support condition follows from complementary slackness in the Wasserstein coupling formulation.
  • Transport representation: The constructed pushforward distribution T#ν has an associated joint distribution γT whose marginals and transport cost establish optimality in the Wasserstein definition.Thus the worst-case distribution can be represented through a measurable transport map, with mixtures used when required.

B.2. Proofs for Section 3.2

The proof establishes attainment for an optimization over distributions minimizing mass on a set C. Boundary mass can be moved just outside C while maintaining the Wasserstein constraint.

  • Existence: A worst-case distribution minimizing μ(int(C)) exists by applying the preceding existence corollary.This provides an optimizer for the interior of C before comparing it with optimization over C itself.
  • Interior case: If the optimizer assigns full mass to int(C), then the infimum over C equals the minimum over int(C).The equality follows directly from the inclusion int(C) ⊂ C and the optimizer’s unit interior mass.
  • Boundary case: When boundary mass remains, a measurable map moves boundary points to points outside C within distance ε.The map fixes points in int(C) and outside C while perturbing points in C \ int(C).
  • Boundary case: Choosing qε = 1 −θp/(ε + θ)p yields Wp(με,ν) ≤θ, so the perturbed distributions remain feasible.This perturbation supports the equality between the infimum over C and the minimum over int(C).

C.1. Proofs for Section 4.1

The proofs reduce the relevant optimization over binary functions and point-process distributions to finite structures tied to the observed sample paths. The resulting constructed distribution is optimal under the stated conditions.

  • Existence: The inner distributional problem is reduced to the form analyzed in Example 7, so an optimal distribution exists.The reduction uses Theorem 1 together with Proposition 3.
  • Point-process construction: A point-process distribution supported on 2n sample paths is constructed and satisfies the Wasserstein feasibility condition.The proof then identifies it as an optimal solution for the distributionally robust expectation problem.
  • Optimality: The constructed optimizer also makes the corresponding bound an equality.This follows by applying the same boundary-mass argument used in Proposition 3.
  • Reduction: It suffices to optimize over binary functions whose connected components of x^-1(1) each contain at least one observed sample point.Components without sample points can be removed or adjusted without worsening the objective.

C.2. Proofs for Section 4.3

The proof characterizes worst-case distributions through probability transport to a threshold boundary and derives data-dependent Wasserstein concentration bounds under bounded support.

  • Worst-case distribution construction: Worst-case distributions transport probability from the threshold set Cq to its boundary, where the intrinsic metric makes this transport least costly.The construction moves mass greedily from points closest to ∂Cq.
  • Worst-case distribution construction: For ζ in Cq, the constructed point ξζ lies outside Cq and minimizes the distance from ζ to Ξ \ Cq.Its transport distance is (q − s)/∥w∥∗, matching the lower bound for any feasible destination.
  • Radius selection: The Wasserstein radius can be selected using an exponential concentration bound for the empirical distribution based on N i.i.d. observations.The bound depends on constants, the radius, and a covering number for the support.
  • Radius selection: Under bounded support, the truncation step is unnecessary, and the support covering number becomes N(δ/2) = ¯B/δ.The bounded-support assumption simplifies the concentration result used to calibrate the Wasserstein ball.
  • Numerical implementation: In the numerical experiment, δ minimizes the right side of (56), while θ is chosen so that this right side equals 0.05.This specifies the reported parameter-selection procedure rather than an outcome comparison.
Loading 1604.02199v3…