PaperlayerView exact revision on arXiv

Source-linked AI summary

Wasserstein Distributionally Robust Optimization and Variation Regularization

Rui Gao, Xi Chen, Anton J. Kleywegt

arXiv:1712.06050v3cs.LGmath.OCstat.ML

TL;DR

Existing links between Wasserstein DRO and regularization rely on convexity or smoothness assumptions that exclude many relevant losses. This paper develops variation regularization and establishes results for broader loss classes and spaces, including generalization guarantees for adversarial robust learning.

  • Problem

    Existing Wasserstein DRO regularization results often require convexity or smoothness, assumptions not met by many problems.

    Source: §1 · pp. 1–2

  • Method

    The paper defines variation of loss as a regularizer and develops theory connecting it with Wasserstein DRO.

    Source: §1 · p. 2

  • Results

    For possibly non-convex and non-smooth losses, Wasserstein DRO is asymptotically equivalent to variation regularization in the stated higher-order setting, while 1-Wasserstein DRO admits a sandwich result and adversarial-learning guarantees.

    Source: §1 · p. 2

  • Takeaways & Limitations

    In adversarial learning, generalization behavior depends on both loss-class complexity and slope complexity.

    Source: §1 · p. 2

    In the motivating high-dimensional setting, condition (3) can be difficult to satisfy; under the stated example's assumptions, its qualifying neighborhood has Q-measure only of order d^3.

    Source: §3.3.1 · p. 10

Abstract

from arXiv · show

Wasserstein distributionally robust optimization (DRO) has recently achieved empirical success for various applications in operations research and machine learning, owing partly to its regularization effect. Although connection between Wasserstein DRO and regularization has been established in several settings, existing results often require restrictive assumptions, such as smoothness or convexity, that are not satisfied for many problems. In this paper, we develop a general theory on the variation regularization effect of the Wasserstein DRO - a new form of regularization that generalizes total-variation regularization, Lipschitz regularization and gradient regularization. Our results cover possibly non-convex and non-smooth losses and losses on non-Euclidean spaces. Examples include multi-item newsvendor, portfolio selection, linear prediction, neural networks, manifold learning, and intensity estimation for Poisson processes, etc. As an application of our theory of variation regularization, we derive new generalization guarantees for adversarial robust learning.

1. Introduction

Existing Wasserstein DRO regularization results rely on assumptions that exclude many non-convex, non-smooth, or bounded-support problems. This paper develops variation regularization to connect Wasserstein DRO with regularization across broader loss classes and settings.

1.1. Related work

  • Earlier 1-Wasserstein equivalence results require unbounded support and convex losses, while several higher-order results require smoothness; these conditions limit applicability to many problems.The related-work discussion also notes differentiability requirements in much of the prior work on higher-order Wasserstein DRO.Source: §1 · pp. 1–2, §1.1 · p. 3

1. Introduction

  • Variation of loss measures changes in expected loss under distribution perturbations, generalizing total variation and reducing to Lipschitz or weighted empirical gradient norms in specified cases.The paper presents it as a regularizer closely related to Wasserstein DRO.Source: §1 · p. 2
  • For possibly non-convex and non-smooth losses, Wasserstein DRO is asymptotically equivalent to variation regularization for Wasserstein orders in (1, 2], up to a higher-order remainder.For orders below 2, the stated remainder bound is tight; the paper also gives examples for order 2 and non-Euclidean spaces.Source: §1 · p. 2
  • For 1-Wasserstein DRO, a sandwich theorem bounds the robust problem between variation-regularized problems, so minimizing robust loss also controls loss variation.The paper illustrates this with linear prediction using Lipschitz losses and extends prior equivalence results to a broader class of non-convex functions.Source: §1 · p. 2
  • Adversarial robust learning is equivalent to empirical total-variation regularization, and its generalization behavior depends on both loss-class complexity and slope complexity.The paper derives guarantees quantifying the gap between empirical and population adversarial risk.Source: §1 · p. 2

2. Wasserstein Distributionally Robust Optimization

This section sets up Wasserstein DRO using a metric on the data space and introduces its regularizer as the difference between robust and nominal loss.

2. Wasserstein Distributionally Robust Optimization

  • The Wasserstein DRO setup considers distributions near a nominal distribution within a radius measured using a Wasserstein metric.The data space is described as a metric space, and the distributional problem is formulated for a family of losses and a nominal distribution.Source: §2 · pp. 3–4
  • The Wasserstein regularizer is the difference between Wasserstein robust loss and nominal loss, and with an empirical nominal distribution it is data-dependent.The empirical distribution is formed from independently sampled observations of the underlying true distribution.Source: §2 · p. 4
  • Under upper semi-continuity and a growth condition, the Wasserstein regularizer converges to zero as the radius shrinks.The text states that upper semi-continuity ensures the regularizer is zero at radius zero, while the growth condition ensures finiteness of the robust loss.Source: §2 · p. 4

3. Variation Regularization Effect of Wasserstein DRO

This section develops function variation as a regularization quantity for Wasserstein DRO, studying its relation to the robust regularizer for smooth and non-smooth losses, including the distinct 1-Wasserstein case. It establishes when this relation takes the form of a sandwich bound, extends the theory to general metric spaces, and describes how assumptions and worst-case perturbations depend on the Wasserstein order.

3. Variation Regularization Effect of Wasserstein DRO

  • The section focuses first on subsets of Banach spaces and identifies variation as the quantity characterizing how the Wasserstein regularizer converges as its radius tends to zero.It also notes that extensions to general metric spaces are presented in Section 3.4.Source: §3 · p. 5

3.1. Variation

  • Variation is a weighted average of gradient norms over the data support, reducing to classical total variation for differentiable univariate functions and relating to the Lipschitz norm.For Lipschitz functions, variation is bounded by the Lipschitz norm and equals it when the support of Q is the whole domain.Source: §3.1 · p. 5

3.2.2. Non-smooth Losses

  • For non-smooth losses, the p-Wasserstein regularizer is controlled by variation under assumptions on piecewise smoothness, gradient growth and jumps, and data mass near non-differentiable points.The results require additional conditions on the loss class and true distribution; the resulting guarantee is probabilistic, unlike the smooth-loss result.Source: §3.2 · p. 5, §3.2.2 · pp. 7–8

3.2.1. Smooth Losses

  • For smooth losses, the Wasserstein regularizer has a first-order expansion around radius times variation, with an O(n^-1) remainder for p in [2,∞] at radius O(n^-1/2).For p in (1,2), the O(n^-p/2) remainder cannot generally be improved.Source: §3.2.1 · p. 6

3.2. ?-Wasserstein DRO (? > 1)

  • For p > 1, Wasserstein DRO regularization is asymptotically equivalent to empirical variation regularization when the stated non-smoothness assumptions hold and the near-boundary probability term is O(1/n).The non-smooth result is probabilistic; for smooth losses, the regularizer admits a first-order expansion, with an O(n^-1) remainder for p in [2,∞] under the radius choice d = O(n^-1/2).Source: §3.2.1 · p. 6, §3.2.2 · p. 8

3.3.1. A Motivating Example

  • For 1-Wasserstein DRO, a smooth convex example shows the remainder from radius times variation can be linear in the radius, rather than O(d^2).The example motivates a weaker uniform guarantee: under mild conditions, the regularizer still controls a fraction of variation.Source: §3.3.1 · pp. 9–10

3.3.2. A Sandwich Theorem

  • For 1-Wasserstein DRO, a sandwich theorem bounds the regularizer between a fraction of radius times variation and radius times variation, under a perturbation condition.The paper gives data-driven and Lipschitz-regularization corollaries; in the latter case it reports exact equivalence under the stated Lipschitz-norm attainment condition.Source: §3.3.2 · pp. 10–11
  • Condition (L) can hold for convex Lipschitz losses and for non-convex losses, including the illustrated one-dimensional example.The paper also illustrates the corollary for linear prediction with a Lipschitz loss on an unbounded domain.Source: §3.3.2 · p. 11

3.4. Theory for General Metric Spaces

  • For general metric spaces without isolated points, local and global slopes measure loss changes under local perturbations and perturbations to any point, respectively.The framework applies to broad classes of continuous, not necessarily differentiable losses.Source: §3.4 · pp. 11–12
  • Theorems 1 and 2 continue to hold for general metric spaces under the stated growth, continuity, and jump assumptions, with examples in manifold regularization and point-process intensity estimation.The paper states that these results follow by replacing Assumptions 1 and 2 with Assumption 5 and using the specified substitutions.Source: §3.4 · p. 13
  • Wasserstein order affects the assumptions and bounds: order 1 needs only local continuity and jump conditions but may give only a sandwich inequality, while other orders can require global growth conditions.The worst-case distribution perturbs points within bounded distances for orders at least 2, whereas below 2 it tends to use large-distance perturbations.Source: §3.4 · p. 13

4. Applications

The applications illustrate how Wasserstein DRO relates to variation regularization across operations research, prediction, neural networks, and non-Euclidean settings. The examples also show extensions to non-convex losses and applications such as manifold regularization and point-process intensity estimation.

4.1. Multi-item Newsvendor

  • The newsvendor example has 2^3 piecewise-linear regions, yet its remainder grows only linearly in 3.Source: §4.1 · p. 14

4.2. Portfolio Selection

  • For piecewise-linear utility portfolio selection, Theorem 4 gives a high-probability variation-regularization approximation under the example’s stated conditions.Source: §4.2 · pp. 14–15

4.3. Linear Prediction

  • Corollary 2 covers unbounded-domain Lipschitz losses, including non-convex inverse-S-shaped losses, relaxing the convexity assumption in earlier equivalence results.Source: §4.3 · p. 15

4.4. Neural Networks

  • The theory yields a high-probability variation-regularization result for leaky ReLU networks when the input domain is compact and the stated norm and distribution conditions hold.Source: §4.4 · p. 16

4.5. Non-Euclidean Spaces

  • For non-Euclidean settings, the manifold example connects Wasserstein DRO to Laplacian regularization, while another result identifies a score-function penalty for 2-Wasserstein DRO.Source: §4.5 · pp. 16–17
  • The examples also extend the framework to nested-Wasserstein distances on point-process paths and robust negative-log-likelihood estimation of point-process intensity.Source: §4.5 · pp. 16–17

5. Generalization Guarantees for Adversarial Robust Learning

The paper studies generalization of adversarial risk by applying its Wasserstein DRO framework. Its bound includes the complexity of local slopes, and the adversarial objective is equivalent to empirical total-variation regularization under the stated conditions.

5. Generalization Guarantees for Adversarial Robust Learning

  • The framework treats adversarial risk as 1-Wasserstein DRO and bounds the gap between empirical and population adversarial risk.Source: §5 · p. 18
  • Under the stated smoothness, piecewise-smoothness, and distribution conditions, empirical adversarial risk is equivalent to empirical total-variation regularization with high probability.Source: §5 · p. 18
  • The generalization bound includes the Rademacher complexity of local slopes, which the authors identify as crucial alongside the ordinary empirical-risk complexity.Source: §5 · p. 18

6. Conclusion

The conclusion presents variation regularization as a framework for understanding Wasserstein DRO’s regularization effect. Its examples span operations research and machine learning, and its theory offers new perspectives on adversarial-learning generalization.

  • The paper introduces variation regularization and a framework connecting it to Wasserstein DRO to address gaps in understanding DRO’s regularization effect.Source: §6 · p. 19
  • Examples across operations research and machine learning are presented as solidifying existing regularization techniques and inspiring new ones.Source: §6 · p. 19
  • The theory provides new aspects for understanding the generalization behavior of adversarial robust learning.Source: §6 · p. 19

Appendix A: A Variant of Theorem 1

The appendix gives an alternative to Theorem 1(II) that drops one lower-bound assumption. Its theorem uses a lower-isometry condition and establishes a high-probability approximation between Wasserstein and variation regularization.

Appendix A: A Variant of Theorem 1

  • The alternative to Theorem 1(II) does not require the lower bound 23 in Assumption 4.Source: Appendix A · p. 19
  • The variant assumes a lower-isometry property: empirical variation is bounded below by a positive fraction of true variation for functions above a stated variation threshold.Source: Appendix A · p. 19
  • Under Assumptions 4’, 5, and 6, Theorem 4 gives a high-probability bound comparing Wasserstein regularization at radius d_n=d0/sqrt(n) with variation regularization.Source: Appendix A · p. 19

Appendix B: Results for General Metric Space

Appendix B states results for Wasserstein DRO on general metric spaces, including theorem bounds under Lipschitz and other stated conditions. It treats the case with exponent 1 separately from another exponent regime.

Appendix B: Results for General Metric Space

  • For exponent 1, the appendix gives a bound on the DRO objective’s deviation from a gradient-based term, with a distance-to-set contribution.The stated bound applies for sufficiently small radius d.Source: Appendix B · p. 20
  • For another exponent regime, the appendix states a corresponding bound under Assumptions 1, 2, and 4.The result applies for sufficiently small d0 and all functions in F.Source: Appendix B · p. 20
  • Theorem 2 assumes Lipschitz continuity and additional conditions, then states a high-probability result involving metric displacement.Its accompanying inequality relates loss change to the distance between points.Source: Appendix B · p. 20

Appendix EC.1: Proofs for Section 2

Appendix EC.1 establishes duality results under stated regularity and support conditions and outlines proof steps. It then points to results for general metric spaces in Appendix EC.2.

Appendix EC.1: Proofs for Section 2

Appendix EC.2: Proofs for Section 3

EC.2.1. Auxiliary Results

The auxiliary results include a contraction property for Rademacher complexity and a concentration lemma. The subsequent proofs connect smoothness and growth conditions to (GS) and use (GS) to establish bounds for Section 3.2.1.

EC.2.1. Auxiliary Results

  • The auxiliary results also state a high-probability lemma for a bounded function class.The lemma gives probability at least 1 − 4^-C.Source: EC.2.1. Auxiliary Results · p. 27
  • A Lipschitz transformation of a function class satisfies a contraction property for Rademacher complexity.The cited lemma attributes this property to Ledoux and Talagrand.Source: EC.2.1. Auxiliary Results · p. 27

EC.2.2. Proofs for Section 3.2.1

EC.2.3. Proofs for Section 3.2.2

This appendix proves results for Sections 3.2.2, 3.3, and 4.1, addressing variation bounds, a sufficient small-ball condition for the lower-isometry assumption, and Example 5. The proofs use covering arguments, norm identities, and technical lemmas.

EC.2.3. Proofs for Section 3.2.2

  • Assumptions 1 and 2 imply Assumption 5; under Assumption 4’, the appendix derives a deterministic gap bound and completes Theorem 1(II), then combines the preceding lemmas to prove Theorem 1.The gap bound is developed across the q regimes stated in Lemma EC.9; Lemma EC.10 uses Assumption 4, and Lemma EC.11 supplies probabilistic upper bounds for Theorem 1(III).Source: EC.2.3. Proofs for Section 3.2.2 · pp. 30, 31, 33, 34, 35

EC.2.4.1. A sufficient condition on the lower isometry property

  • The small-ball condition, together with a complexity condition verified case by case, ensures that sufficiently many local slopes capture a fraction of variation and yields a guarantee of Assumption 6.The passage describes the small-ball condition as a sufficient route to the lower-isometry property.Source: EC.2.4.1. A sufficient condition on… · p. 36

EC.2.5. Proofs for Section 3.3

  • For Theorem 2, the proof passage invokes concavity for an upper bound and begins a lower-bound argument using a transport map on an event, but does not provide the completed result.The passage defines a transported distribution and an expected transport distance before ending mid-proof.Source: EC.2.5. Proofs for Section 3.3 · p. 37
  • A finite covering of the loss family reduces the uniform probability bound to a union bound over net elements.The proof selects a finite subset with size bounded by the covering number and controls the loss difference between each function and its net representative.Source: EC.2.5. Proofs for Section 3.3 · p. 37
  • The proof of Corollary 1 constructs a mapping on a high-probability subset and uses the Banach-space assumption to ensure the mapping exists.The subset has probability greater than 1 − ε, as stated in the proof.Source: EC.2.5. Proofs for Section 3.3 · p. 38
  • Under the corollary’s assumptions, the proof identifies the Lipschitz norm with the variation quantities and verifies condition (T).It uses the limiting slope characterization and assumption (L) to obtain points approaching the Lipschitz norm.Source: EC.2.5. Proofs for Section 3.3 · p. 38

EC.3.1. Proofs for Section 4.1

  • For Example 5, Lemma EC.15’s proof expresses the gradient norm through coordinatewise indicator terms and gives an expression involving coordinatewise maxima of the displayed quantities.Source: EC.3.1. Proofs for Section 4.1 · p. 38

EC.3.2. Proofs for Section 4.2

These proofs establish example-specific assumptions and bounds used in Sections 4.2–4.5. They use complexity arguments, covering-number bounds, and duality to support the paper’s results.

EC.3.2. Proofs for Section 4.2

  • For Example 6, the proof uses Rademacher-complexity and VC-dimension arguments to verify Assumption 6.The cited lemmas concern indicator classes and provide high-probability bounds under the Example 6 setting.Source: EC.3.2. Proofs for Section 4.2 · pp. 39, 41

EC.3.3. Proofs for Section 4.3

  • The Example 7 proof derives an upper bound on the covering number N(n;F,dF).The supplied bound’s remaining expression is not sufficiently legible to state more precisely.Source: EC.3.3. Proofs for Section 4.3 · p. 41

EC.3.4. Proofs for Section 4.4

EC.3.5. Proofs for Section 4.5

  • For Example 11, strong duality gives a dual problem of the same form as (D), linking the gradient-norm penalty to that formulation.The proof also applies Lemma 1 under the stated Lipschitz-gradient condition and (GS) to bound robust loss.Source: EC.3.5. Proofs for Section 4.5 · p. 43

Appendix EC.4: Proofs for Section 5

These proofs derive uniform generalization bounds and relate robust risk under one distribution to risk under another. The bounds hold uniformly over the function class, with a stated high-probability result for sufficiently small d.

Appendix EC.4: Proofs for Section 5

Loading 1712.06050v3…