PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Rui Gao

arXiv:2009.04382v3cs.LGmath.PRstat.ML

TL;DR

Generic Wasserstein DRO guarantees have been limited by dimension-sensitive bounds or asymptotic results. This paper develops a non-asymptotic analysis using concentration and localized complexity tools, and shows that a canonical root-n radius bounds true loss by robust loss up to a higher-order residual.

  • Problem

    For generic losses, existing Wasserstein DRO guarantees have been dimension-sensitive or asymptotic, leaving the finite-sample scaling of the ambiguity radius unresolved.

    Source: §1 · p. 2

  • Method

    The analysis combines a concentration inequality controlled by loss variation with function-class bounds using covering numbers and localized Rademacher complexity.

    Source: §1 · pp. 3–4

  • Results

    With the canonical root-n radius, true loss is bounded by Wasserstein robust loss uniformly over solutions up to a higher-order residual, with constants mildly dependent on dimension.

    Source: §1 · p. 3

  • Takeaways & Limitations

    A properly chosen radius balances empirical loss and loss variation, which controls the generalization gap and underlies the paper's bias-variation trade-off.

    Source: §1 · pp. 3–4

    The stated inner-dual minimizer result assumes the loss grows no faster than κ + λ||I||_q for nonnegative κ and λ.

    Source: §2 · p. 5

Abstract

from arXiv · show

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.

1. Introduction

The paper develops finite-sample guarantees for generic Wasserstein DRO, addressing prior guarantees that were dimension-sensitive or asymptotic. It shows how a properly chosen radius links robust loss to the empirical loss and loss variation, and develops concentration and complexity tools for this analysis.

1. Introduction

  • Prior generic guarantees were either dimension-sensitive or asymptotic [14, 13, 16], while finite-sample root-n results covered special structures.The dimension-sensitive radius in shrinks too slowly even at moderate dimensions; the asymptotic result fixes dimension while sample size grows.Source: §1 · p. 2
  • With the canonical root-n radius, the true loss is bounded by the Wasserstein robust loss uniformly over solutions, up to a higher-order residual, with constants mildly dependent on dimension.For supervised learning, the robust objective provides a generalization bound up to that residual.Source: §1 · p. 3
  • A properly chosen radius balances empirical loss against loss variation, measured by a Lipschitz norm for 1-Wasserstein DRO or a gradient norm for 2-Wasserstein DRO.The paper relates this trade-off to a generalization gap controlled by variation.Source: §1 · p. 3
  • A new concentration inequality bounds empirical-loss deviation using the inverse Wasserstein regularizer and loss variation, which directly controls deviation from ground truth.The paper describes this as analogous to variance-based control in Chebyshev or Bernstein inequalities.Source: §1 · p. 3
  • For function classes, the analysis combines covering-number arguments with localized Rademacher complexity over classes whose loss variation is controlled.The framework also gives statistical guarantees for Lipschitz and gradient regularization and is demonstrated in several optimization and learning examples.Source: §1 · pp. 3–4
  • The resulting non-asymptotic framework presents Wasserstein DRO's bias-variation trade-off as a counterpart to the bias-variance trade-off in machine learning.The robust solution generalizes by biasing toward solutions with small variation.Source: §1 · pp. 3–4

Related Work

Prior work studies generalization through robustness and develops performance guarantees for Wasserstein DRO, divergence DRO, and information-theoretic bounds. The cited literature also examines radius calibration and asymptotic or non-asymptotic bias-variance trade-offs.

Related Work

  • Xu and Mannor study generalization of learning algorithms from the viewpoint of robustness.Source: Related Work · p. 4
  • Several works develop Wasserstein DRO generalization bounds with a fixed radius rather than one varying with sample size.Source: Related Work · p. 4
  • For divergence DRO, Lam studies radius calibration, while investigate asymptotic and non-asymptotic bias-variance trade-offs.Source: Related Work · p. 4
  • Wasserstein distance and transportation-information inequalities have also been used to improve information-theoretic generalization bounds for learning algorithms.Source: Related Work · p. 4

2. Wasserstein DRO and Variation Regularization

The section formulates Wasserstein DRO around a nominal distribution and a Wasserstein ball, then connects its robust-loss increment to variation regularization. Appendix results relate that increment to Lipschitz and gradient penalties under stated regularity conditions.

2. Wasserstein DRO and Variation Regularization

  • Wasserstein DRO minimizes over a loss class the worst-case expected loss among distributions within radius d of a nominal distribution.Source: §2 · p. 5
  • The Wasserstein regularizer is the difference between robust and nominal loss, and prior results connect it to Lipschitz regularization for order 1 and gradient regularization for order 2.Source: §2 · p. 5

Appendix A.

  • Under the stated conditions, the order-1 regularizer is at most d times the loss's Lipschitz norm, with equality under an additional attainment assumption.Source: Appendix A · p. 5
  • For order 2, the appendix assumes losses have Lipschitz gradients and states a gradient-regularization result for the Wasserstein regularizer.Source: Appendix A · p. 5

3. Variation-based Concentration Inequality

The section develops a variation-based concentration result for a single loss and relates its deviation control to the Wasserstein regularizer. It then connects the result to transportation-information assumptions and derives bounds for Lipschitz and gradient regularization.

3.1. Inverse of the Wasserstein Regularizer

  • For small radius, the inverse of the Wasserstein regularizer is precisely the function I? described in the proposition when the dual optimizer exceeds its limiting value.Source: §3.1 · p. 6

3.2. Transportation-Information Inequalities

  • The required transportation-information condition is presented for orders 1 and 2, with examples including bounded-support distributions for order 1 and strongly log-concave distributions for order 2.Source: §3.2 · p. 6

3.3. Concentration for a Single Loss Function

  • Under a transportation-information inequality and growth conditions on the loss, the single-loss theorem controls deviation probabilities through the inverse Wasserstein regularizer.Source: §3.3 · p. 7
  • The variation-regularization corollary gives deviation bounds in terms of empirical loss and either the Lipschitz norm or the gradient norm; order 2 can yield a tighter bound under a stronger distributional assumption.Source: §3.3 · p. 7

4. Finite-Sample Guarantees

This section extends a single-loss concentration result to uniform finite-sample guarantees over a loss family. It develops covering-number and localized Rademacher-complexity approaches for Wasserstein DRO and related regularization problems.

4. Finite-Sample Guarantees

  • The section seeks a radius scaling that makes robust loss uniformly upper-bound true loss across the function class, extending concentration from a single loss.For finite classes, a union bound suffices; infinite classes require a complexity argument.Source: §4 · p. 8

4.1. Covering Number Arguments

  • The covering-number approach establishes uniform true-loss upper bounds for Wasserstein DRO and related regularizers under stated smoothness and tail assumptions.For q=1 and q=2, Corollary 2 gives respective remainder orders 1/n and d/n; Assumption 1(II) may be restrictive, though Example 1 gives a guarantee without it.Source: §4.1 · pp. 8–9
  • A 2-Wasserstein empirical bound controls true loss using the empirical gradient norm and complexity terms under additional distribution and smoothness assumptions.Corollary 3 states bounds in terms of the empirical gradient norm or the 2-Wasserstein robust loss.Source: §4.1 · p. 9

4.2. Local Rademacher Complexity Arguments

  • Localized Rademacher complexity can improve dimension dependence over covering-number bounds, and examples include dimension-independent bounds.Localization restricts analysis to a low-complexity subset around the optimum, with a sub-root function's fixed point controlling the bound.Source: §4.2 · pp. 9–10
  • With a radius of order 1/sqrt n, localized-complexity results make the robust loss an upper bound on true loss with an order 1/n gap for Lipschitz regularization and 1-Wasserstein DRO.The probability bound includes a log n term that is nearly independent of sample size.Source: §4.2 · pp. 10–11
  • For 2-Wasserstein DRO, gradient-regularized loss bounds true loss, and a bounded-gradient condition permits an empirical counterpart.When the Rademacher complexity is order 1 and the localized fixed point is order 1/n, the gap is order 1/n.Source: §4.2 · pp. 11–12
  • Under mild conditions, the robust and true optimal solutions have losses differing by order 1/sqrt n; quadratic growth also bounds their solution distance by a multiple of the loss gap.The solution-distance conclusion is conditional on the Polyak–Łojasiewicz or quadratic-growth condition.Source: §4.2 · p. 12

5. Applications

This section illustrates finite-sample guarantees for Wasserstein DRO and generalization bounds for variation regularization across newsvendor, prediction, portfolio, kernel, and neural-network settings. It also identifies limits in the loss and distribution families, Wasserstein orders, and scope of the variation-based complexity theory.

5.1.1. Big-data Newsvendor

  • In the newsvendor example, choosing the Wasserstein radius at the stated rate ensures a good performance guarantee despite the loss satisfying Assumption 1(I) but not 1(II).The analysis uses a uniform lower bound on the Rademacher complexity relative to the Lipschitz norm of the loss.Source: §5.1.1 · p. 13

5.1.2. Linear Prediction

  • The 1-Wasserstein bound controls true loss by robust loss at an inflated radius, without a higher-order error term, and the radius is dimension-independent.Unlike typical results (e.g.), this bound does not require boundedness assumptions on the loss or domain.Source: §5.1.2 · p. 14
  • For 2-Wasserstein DRO, the linear-prediction example gives a finite-sample true-loss bound using a complexity term and an additional remainder under smoothness and tail conditions.The assumptions include a Lipschitz gradient for the loss and a T2 condition on the feature distribution.Source: §5.1.2 · p. 14

5.1.3. Portfolio Optimization

  • The portfolio example bounds true mean-variance by robust mean-variance up to a higher-order term, restricting to a bounded parameter set that contains an optimum with high probability.This addresses the unbounded decision parameter D in the original formulation.Source: §5.1.3 · p. 16

5.2.1. Kernel Method

  • For kernel classes, the Lipschitz-regularization generalization bound is dimension-independent and places distributional uncertainty on the original data space.The passage distinguishes this setup from prior work that places uncertainty on the feature space [74, Section 3.3].Source: §5.2.1 · p. 17

5.2.2. Neural Networks

  • The neural-network example sets up gradient-regularization analysis for a two-layer network with orthonormal weight constraints and smooth loss and activation functions.The stated conditions also include a positive lower bound on the loss derivative and a lower bound on an expected squared gradient quantity.Source: §5.2.2 · p. 17

6. Concluding Remarks

  • The paper establishes finite-sample, non-asymptotic performance guarantees for Wasserstein DRO and associated variation regularization without suffering from the curse of dimensionality.The authors say these results help explain the empirical success of Wasserstein DRO and Lipschitz and gradient regularization.Source: §6 · p. 18
  • The results restrict loss families to those satisfying Lemmas 1 and 2 and use transportation inequalities covering most subgaussian distributions and linear- or quadratic-growth losses.The authors point to non-smooth losses [39] and a follow-up work, and suggest other transportation-information inequalities for broader distribution and loss families; they contrast this with, which allows any distribution admitting Wasserstein concentration but suffers from the curse of dimensionality.Source: §6 · p. 18
  • The analysis focuses on Wasserstein orders in [1] because Theorem 1 relies on a tensorization lemma, leaving other orders, including order 1, for future work.The authors note that order 1 has been widely considered in adversarial robust learning.Source: §6 · p. 18
  • The paper develops local Rademacher complexity theory based on loss variation and proposes investigating its use in other statistical learning problems.Source: §6 · p. 18

Appendix A: Proofs for Section 2

The proofs use strong duality and sequences of distributions to establish bounds connecting Wasserstein robust loss with the loss’s Lipschitz variation.

Appendix A: Proofs for Section 2

  • A limiting argument shows the robust term converges to d times the Lipschitz norm as the parameter approaches 1.Source: Appendix A · p. 19
  • The strong-duality argument gives an upper bound of d times the loss’s Lipschitz norm for the 1-Wasserstein robust term.The proof also uses a sequence of distributions to establish a matching lower-bound argument.Source: Appendix A · p. 19
  • The lower-bound proof constructs distributions concentrating on a region with positive probability and uses a sequence of points with large separation.Source: Appendix A · p. 19

Appendix B: Proofs for Section 3

These appendices provide proof machinery for the concentration and generalization results, including transportation inequalities, covering arguments, and Rademacher-complexity tools.

Appendix B: Proofs for Section 3

  • The proof of Proposition 1 uses strong duality and dual optimality conditions to connect the robust quantity with its associated conjugate expression.Source: Appendix B · p. 20

B.1. Proof of Theorem 1

  • Theorem 1’s proof derives concentration through a transportation-information inequality for product distributions and exponential tilting.The proof invokes tensorization and Kantorovich duality before applying the resulting concentration bound to the empirical loss.Source: §B.1 · pp. 21–23

C.1. Proof for Section 4.1

  • The Section 4.1 proofs combine covering arguments and concentration inequalities to extend bounds across a family of losses.The proofs also use duality and the paper’s variation-regularization lemmas.Source: §C.1 · pp. 24–25

C.2. Proofs for Section 4.2

  • The Section 4.2 appendix introduces symmetrization and contraction properties of Rademacher complexity as tools for the subsequent proofs.Source: §C.2.1 · p. 25

C.2.1. Auxiliary Results

The auxiliary results build uniform deviation bounds using Rademacher complexity, peeling, and localized complexity arguments, with parallel treatment of Lipschitz and gradient variation.

C.2.1. Auxiliary Results

  • The auxiliary toolkit includes symmetrization and contraction lemmas for families of functions.Source: §C.2.1 · p. 25
  • A uniform bound controls the loss deviation over the function class using its Rademacher complexity.Source: §C.2.1 · p. 26
  • Peeling removes dependence on the largest Lipschitz norm, while localized complexity arguments replace expected complexity with a fixed point.Source: §C.2.1 · p. 27
  • Theorem 2’s proof chooses a fixed-point scale and applies the peeled bound to the resulting localized function class.Source: §C.2.1 · pp. 27–28
  • For gradient variation, the proofs use T2 transportation assumptions and peeling to obtain bounds over classes with controlled gradient norms.Source: §C.2.3 · pp. 29–31
  • The gradient-based theorem selects a fixed-point scale and applies the resulting bound to functions whose gradient norms fall within that scale.Source: §C.2.3 · p. 31

Appendix D: Proofs for Section 5

This appendix proves Lemma 15 under Example 1 by combining two inequalities, including one obtained from the duality result.

Appendix D: Proofs for Section 5

  • The proof establishes Lemma 15 under Example 1 by combining two inequalities.One inequality follows from Lemma 1; the other uses the duality result (1).Source: §D.1 · p. 32
  • One bound in the proof is obtained by applying Lemma 1.The displayed bound's symbols are not legible enough to state its terms reliably.Source: §D.1 · p. 32
  • The proof also invokes duality before combining the bounds.The passage refers to duality result (1).Source: §D.1 · p. 32

D.2. Proofs for Section 5.1.2

The appendix supplies proofs of supporting lemmas for Examples 2 and 3, with one proof using Rademacher variables and standard inequalities.

D.2. Proofs for Section 5.1.2

  • A lemma introduced for Example 2 is proved using i.i.d. Rademacher random variables, Cauchy–Schwarz, and Jensen’s inequality.The displayed result is not legible enough to report its bound.Source: §D.2 · p. 32
  • The Example 2 proof presents two displayed expressions after applying the stated inequalities.Their contents are not legible enough to characterize.Source: §D.2 · p. 32
  • The appendix introduces Lemma 17 under the setting of Example 3.The statement's bound is not legible enough to summarize.Source: §D.2 · p. 33

D.3. Proofs for Section 5.1.3

These appendix proofs cover subgaussian results and supporting bounds for Example 4, including Rademacher-complexity calculations and a high-probability gradient-norm comparison.

D.3. Proofs for Section 5.1.3

  • The appendix provides proofs of two stated results on subgaussian distributions for the reader’s convenience.It recalls the definition of an f-subgaussian random variable.Source: §D.3 · p. 33
  • The proof invokes weak compactness of the Wasserstein ball and Sion’s minimax theorem, then identifies the inner minimizer with an expectation.The expectation's integrand is not legible enough to specify.Source: §D.3 · p. 33
  • The appendix computes Rademacher complexities for Example 4 and introduces Lemma 19 in that setting.The displayed bound is not legible enough to report.Source: §D.3 · p. 33
  • A lemma is used to relate the population gradient norm to its empirical estimate under a T1(g) assumption.The stated probability threshold is more than 1 − 4^-C, but the bound itself is not legible.Source: §D.3 · p. 35

D.4. Proofs for Section 5.2.2

The appendix proves supporting results for Example 6, including a vector-valued contraction lemma and bounds used to establish a gradient-Lipschitz property.

D.4. Proofs for Section 5.2.2

  • Lemma 23 gives a contraction result for a Lipschitz scalar function composed with a family of vector-valued functions.It also states a particular case for a linear function class.Source: §D.4 · p. 37
  • The appendix introduces Lemmas 24 and 25 under the setting of Example 6.Their displayed bounds are not legible enough to report.Source: §D.4 · p. 37
  • The Example 6 argument concludes that the gradient has a parameter-dependent Lipschitz bound.The bound's symbols are not legible enough to reproduce reliably.Source: §D.4 · p. 38
Loading 2009.04382v3…