PaperlayerView exact revision on arXiv

Source-linked AI summary

Regularization via Mass Transportation

Soroosh Shafieezadeh-Abadeh, Daniel Kuhn, Peyman Mohajerin Esfahani

arXiv:1710.10016v3math.OCcs.LGstat.ML

TL;DR

Supervised learning must control out-of-sample error when only finitely many training samples are available. This paper uses Wasserstein distributional robustness to create tractable regularized models with generalization bounds and probabilistic interpretations of existing regularization.

  • Problem

    Finite training samples make the data-generating distribution inaccessible, so minimizing empirical loss can yield hypotheses with high out-of-sample error.

    Source: §1 · p. 1, §2.2 · p. 6

  • Method

    The paper minimizes worst-case expected loss over Wasserstein balls around the empirical distribution, deriving tractable convex, kernelizable, and neural-network learning formulations.

    Source: §1 · p. 3

  • Results

    The proposed models provide generalization bounds under minimal assumptions, while classical regularization emerges as a special case and many formulations remain tractable.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Wasserstein distributional robustness supplies a unified framework for regularization, tractable learning models, and out-of-sample guarantees without relying on hypothesis-complexity notions.

    Source: §1 · p. 3

    Efficient nonlinear kernel formulations require regularity assumptions that are often violated by popular kernels.

    Source: §3.3 · p. 17

Abstract

from arXiv · show

The goal of regression and classification methods in supervised learning is to minimize the empirical risk, that is, the expectation of some loss function quantifying the prediction error under the empirical distribution. When facing scarce training data, overfitting is typically mitigated by adding regularization terms to the objective that penalize hypothesis complexity. In this paper we introduce new regularization techniques using ideas from distributionally robust optimization, and we give new probabilistic interpretations to existing techniques. Specifically, we propose to minimize the worst-case expected loss, where the worst case is taken over the ball of all (continuous or discrete) distributions that have a bounded transportation distance from the (discrete) empirical distribution. By choosing the radius of this ball judiciously, we can guarantee that the worst-case expected loss provides an upper confidence bound on the loss on test data, thus offering new generalization bounds. We prove that the resulting regularized learning problems are tractable and can be tractably kernelized for many popular loss functions. We validate our theoretical out-of-sample guarantees through simulated and empirical experiments.

1 Introduction

The introduction motivates Wasserstein distributionally robust learning as a remedy for overfitting and develops its tractable, probabilistic, and statistical contributions. It also previews connections to regularization and robust optimization, along with confidence analysis and worst-case distribution computation.

1 Introduction

  • Wasserstein ambiguity sets hedge against distributions near the empirical distribution, addressing fragile empirical-risk estimators that overfit scarce training data.The framework considers continuous or discrete distributions within bounded transportation cost of the discrete empirical distribution.Source: §1 · pp. 1–2
  • The framework provides generalization bounds under minimal assumptions, including an improved dimension-independent square-root bound when the hypothesis space is bounded.A naïve Wasserstein confidence bound suffers from the curse of dimensionality and converges slowly in high dimensions.Source: §1 · pp. 3–4
  • The proposed models admit tractable convex reformulations for many losses and linear hypotheses, with kernelizable lifted variants and approximations for neural networks.Neural-network models can be addressed using regularized empirical loss minimization and stochastic proximal gradient descent.Source: §1 · p. 3
  • Classical regularized learning arises as a special case when transporting probability mass along the output space becomes infinitely costly, linking regularization to input transportation costs and Wasserstein radius.The regularization function and weight are determined by the input-space transportation cost and ambiguity-set radius, respectively.Source: §1 · p. 3
  • The paper characterizes equivalence with classical robust learning under dispersion or separability conditions and develops tractable confidence intervals and worst-case distributions for fixed hypotheses.The confidence intervals target absolute prediction error for regressors and misclassification risk for classifiers, while worst-case distributions support stress tests and contamination experiments.Source: §1 · p. 4

1.1 Notation

  • The notation subsection defines extended-arithmetic conventions, vector inner products, dual norms, conjugates, indicator and support functions, cones, Lipschitz moduli, product distributions, and index sets.It also points to a table of commonly used symbols.Source: §1.1 · p. 4

2 Problem Statement

The section formulates supervised learning from finite independent samples and motivates replacing heuristic complexity penalties with a Wasserstein-distributionally robust objective. This objective minimizes worst-case loss over distributions near the empirical distribution, aiming to provide tractable optimization and out-of-sample guarantees.

2.1 Classical Statistical Learning

  • Supervised learning infers an unknown target function from finitely many independent input-output samples drawn from an unknown distribution, using hypotheses restricted to a structured space H.Regression uses continuous outputs, classification uses categorical outputs, and candidate spaces include linear functions, reproducing kernel Hilbert spaces, and fixed-depth neural networks.Source: §2.1 · p. 5

Examples of Regression Models

  • In regression, empirical-loss minimization with linear hypotheses encompasses Huber, support vector, and quantile regression through corresponding univariate loss functions.Huber loss is less sensitive to outliers, ε-insensitive loss penalizes deviations beyond ε, and pinball loss targets a conditional quantile; support vector regression is marked and quantile regression.Source: Examples of Regression Models · p. 5

Examples of Classification Models

  • In classification, linear empirical-loss minimization includes hinge-loss SVM, smooth-hinge SVM, and logistic regression, while low training error can still produce high out-of-sample error through overfitting.Common L2 and L1 penalties have Gaussian and Laplacian prior interpretations, but such distributional assumptions are viewed as arbitrary, making many practical regularization methods heuristic.Source: Examples of Classification Models · p. 6

2.2 A New Perspective on Regularization

  • The proposed model minimizes expected loss over every distribution within a Wasserstein ball around the empirical distribution, targeting an upper confidence bound on out-of-sample error.The Wasserstein distance measures minimum transportation cost, and the ball contains distributions whose distance from the empirical distribution is at most ρ.Source: §2.2 · p. 7
  • The framework addresses overfitting by replacing difficult-to-justify regularization penalties with a distributionally robust program that is tractable, kernelizable, generalizable, and asymptotically consistent under stated conditions.For convex losses, the objective is convex; the optimal value yields confidence bounds without estimating VC dimension, and shrinking balls with growing samples recover the ex post optimal hypothesis.Source: §2.2 · pp. 7–8

3 Tractable Reformulations

This section develops tractable reformulations of distributionally robust regression and classification for linear and nonlinear hypotheses, including RKHS and neural-network models. It derives convex or efficiently kernelized optimization formulations under suitable loss, calmness, and Lipschitz conditions, while connecting them to classical regularization and robust optimization.

3.1 Distributionally Robust Linear Regression

  • Distributionally robust linear regression is finitely convex-representable when the loss is piecewise affine, or when Ξ = Rn+1 and the loss is Lipschitz continuous.The formulation assumes convex closed X and Y and a norm-induced transportation metric.Source: §3.1 · p. 8
  • With infinite output-transportation cost, robust regression reduces to classical regularization with a dual-norm penalty, while finite cost allows uncertainty in outputs.The regularization weight is loss-dependent: c = ρδ for Huber loss, c = ρ for ϵ-insensitive loss, and c = max{τ, 1 −τ}ρ for pinball loss.Source: §3.1 · p. 9
  • Theorem 3.6 constructs worst-case or asymptotically optimal distributions for linear regression, while the robust worst-case-loss interpretation requires minimal dispersion for equality.Without that assumption, the distributionally robust worst-case expected loss still provides an upper bound on robust worst-case loss.Source: §3.1 · pp. 10–11

3.2 Distributionally Robust Linear Classification

  • Distributionally robust linear classification likewise admits finite convex reformulations for piecewise-affine losses, or for Lipschitz losses when X = Rn.The transportation metric includes κ > 0 as the cost of switching a label.Source: §3.2 · p. 11
  • For κ = ∞, robust classification recovers classical regularization with a dual-norm penalty and assumes output labels are exact; finite κ permits label uncertainty.The framework covers hinge, smooth hinge, and logloss examples, while its equivalence to robust worst-case loss requires κ = ∞ and the stated non-separability condition.Source: §3.2 · pp. 12, 14
  • Theorem 3.17 provides convex-optimization constructions of worst-case or asymptotically optimal distributions for linear classification.The non-separability condition generalizes the classical requirement; it fails for logloss because its steepest slope occurs at infinity.Source: §3.2 · pp. 13–14

3.3 Nonlinear Hypotheses: Reproducing Kernel Hilbert Spaces

  • The nonlinear extension begins by modeling hypotheses in an RKHS, where a feature map represents point evaluations through inner products and induces a symmetric positive-definite kernel.The associated kernel matrix is positive definite for every finite training set.Source: §3.3 · p. 14
  • The RKHS lifting is not generally equivalent to the original problem because distributions in the lifted Wasserstein ball need not be pushforwards of distributions in the original ball.Efficient reduction of lifted robust classification can fail when lifted samples are linearly separable, as under the Gaussian kernel, whereas lifted distributionally robust problems remain efficiently solvable under standard regularity conditions.Source: §3.3 · pp. 15, 17
  • Under kernel calmness, the lifted RKHS learning problem upper-bounds the original nonlinear problem after transforming the Wasserstein radius by the growth function g.The calmness condition holds for most commonly used kernels, although polynomial kernels require bounded inputs when their degree exceeds one.Source: §3.3 · pp. 15–16
  • Kernelized distributionally robust regression and classification reduce optimization over possibly infinite-dimensional RKHS hypotheses to problems with similar computational effort as linear models.The resulting predictors have finite kernel expansions in the training samples for convex Lipschitz losses.Source: §3.3 · p. 16

3.4 Nonlinear Hypotheses: Neural Networks2

  • For neural networks, the distributionally robust learning model is bounded above by empirical loss plus a regularizer based on the product of activation Lipschitz moduli and weight-matrix operator norms.The classification constant is c = max{1, 2 suph∈H,x∈X |h(x)|}, and bounded final activations such as softmax permit c = 2.Source: §3.4 · pp. 17–18
  • When κ = ∞, the neural-network bound admits a convex regularization term, but the empirical prediction loss remains non-convex and is addressed with local stochastic optimization.The proposed stochastic proximal gradient method relies on efficiently computable proximal operators for selected matrix norms, though it offers no strong performance guarantees.Source: §3.4 · p. 18

4 Generalization Bounds

The paper derives finite-sample Wasserstein generalization bounds under light-tailed data without hypothesis-complexity measures, including settings with infinite VC-dimension. Restricting the hypothesis space improves the radius decay from dimension-dependent to essentially square-root behavior.

Generalization bounds

  • Wasserstein measure concentration under exponentially decaying tails yields finite-sample confidence bounds without controlling VC-dimension, covering numbers, or Rademacher averages.The approach can therefore extend to hypothesis spaces with infinite VC-dimension and relaxes compactness assumptions used in related asymptotic work [76].Source: §4 · p. 19

Basic generalization bound

  • The basic bound holds whenever the Wasserstein radius exceeds ρ_N(η), because the empirical distribution contains the unknown distribution with confidence at least 1−η.The radius ρ_N(η) decreases with sample size, and the bound also guarantees performance for an optimal distributionally robust hypothesis.Source: §4 · p. 20

Limitations

  • The basic radius suffers a fundamental curse of dimensionality, requiring a factor of 2^n more samples to halve it in the large-sample regime.The light-tail assumption is restrictive but holds for bounded-support, Gaussian, and exponential input-output distributions; the resulting bound may also be conservative.Source: §4 · pp. 20–21

Extension to nonlinear hypotheses

  • The guarantee extends directly to calm-kernel RKHS hypotheses, remains valid for infinite-VC-dimension spaces, and is computationally evaluable for finitely generated kernel hypotheses.The required radius is scaled by the kernel growth function, with constants differing between regression and classification.Source: §4 · pp. 20–21

Improved generalization bound

  • Under the theorem’s Lipschitz-loss, light-tail, and hypothesis-space assumptions, halving the Wasserstein radius ρ′N(η) requires increasing sample size N by a factor of 4, irrespective of input dimension n.Source: §4 · p. 21

5 Error and Risk Estimation

This section derives worst- and best-case out-of-sample error and risk estimates over transportation balls, yielding tractable confidence intervals for fixed hypotheses and extensions to RKHS hypotheses.

Extensions

  • The estimation results extend directly from linear hypotheses to conic-representable support sets and nonlinear hypotheses ranging over an RKHS.The RKHS extension lifts inputs into feature space and uses finitely parameterized hypotheses to preserve tractability.Source: §5 · pp. 22–23

Regression

  • For linear regression, worst- and best-case mean absolute prediction errors are characterized over the transportation ball around the empirical distribution.The target is E(w)=E_P[|y−⟨w,x⟩|] under the unknown data-generating distribution.Source: §5 · p. 22

Classification

  • For linear classification, worst- and best-case misclassification risks are characterized over the transportation ball using a label-flip cost κ.The risk is R(w)=P[y≠sign(⟨w,x⟩)].Source: §5 · p. 22

Computational tractability

  • Because the hypothesis is fixed, the error and risk estimation problems are tractable linear programs that can be solved efficiently.This tractability applies to the optimization formulations for both error and risk estimation.Source: §5 · p. 22

Confidence intervals

  • With radius ρ_N(η/2), the estimated error and risk contain the true values with confidence 1−η, even when the hypothesis depends on training data.The error interval is analytically computable, while the risk interval is obtained efficiently from tractable linear programs.Source: §5 · p. 22

6 Numerical Results

Numerical experiments show that distributionally robust support vector machines (DRSVMs) improve out-of-sample classification, including with learned parameters and multi-label image recognition. Additional experiments empirically support the generalization bounds and illustrate how worst-case distributions perturb inputs and labels.

6.1 Regularization with Pre-selected Parameters

  • With pre-selected parameters, DRSVM achieves its best out-of-sample CCR at κ = 0.25 uniformly across Wasserstein radii and exhibits a wider optimal plateau than RSVM.Unregularized SVM is dominated by RSVMs and DRSVMs across a wide range of regularization parameters.Source: §6.1 · p. 23, Figure 1 · p. 24

6.2 Regularization with Learned Parameters

  • Learned-parameter DRSVM consistently outperforms RSVM across polynomial, Laplacian, and Gaussian kernels when parameters are selected by cross validation.The polynomial-kernel DRSVM includes the non-kernelized model as the degree-one special case.Source: §6.2 · pp. 23–24, Table 1 · p. 24
  • DRSVM outperforms RSVM in AUC for all tested norms across all datasets, while RSVM outperforms unregularized hinge-loss minimization by a similar amount.AUC is used because the datasets are mostly imbalanced; results are reported in Table 2.Source: §6.2 · p. 24, Table 2 · p. 25

6.3 Multi-Label Classification

  • Fine-tuned spectral-norm regularization consistently outperforms almost all other multi-label methods, while DRSVM also wins over RSVM in mean average precision.The experiment uses PASCAL VOC 2007 with ALEXNET features and evaluates AP and mAP across 20 object categories.Source: §6.3 · pp. 25–26, Table 3 · p. 26

6.4 Generalization Bounds

  • All three Wasserstein-radius selection approaches decay approximately as 1/N, empirically confirming Theorem 4.6 even without Assumption 4.5's restrictions on W.The approaches are cross validation, test-error optimization, and selecting the smallest radius whose bound covers test loss in at least 95% of trials.Source: §6.4 · p. 27

6.5 Worst-Case Distributions

  • Worst-case distributions perturb training inputs more severely as ρ increases, while label flipping is disallowed for κ = ∞ and costless for κ = 0.Each training sample contributes one nonzero-probability scenario, producing a worst-case training dataset for each parameter pair.Source: §6.5 · pp. 27–28, Figure 3 · p. 28

A Appendix: Proofs · A.1 Proofs of Section 3

This appendix proves the paper’s tractability results by reducing Wasserstein worst-case expectations to robust and dual optimization problems. It also establishes the stated kernelization, uniqueness, representer-theorem, and neural-network regularization results through transportation-metric, Lipschitz, and convex-optimization arguments.

A.1 Proofs of Section 3

  • The proof of Theorem 3.1 begins with a robust reformulation: Wasserstein worst-case expectations become optimization over conditional distributions anchored at the empirical samples.The representation uses the uniform empirical marginal, while Lipschitz majorants ensure integrability and strong duality yields the semi-infinite dual.Source: §A.1 · pp. 28–29
  • Lemmas A.2 and A.3 characterize the maximization using dual norms and support functions; for convex Lipschitz L, the result is finite exactly when lip(L)∥β∥*≤γ and equals L(⟨β,bζ⟩).Source: §A.1 · p. 29
  • Theorem 3.6 follows by interchanging minimization and maximization under Slater’s condition, then applying Lemma A.4 to simplify the dual using the assumption that training samples lie in Ξ.The resulting formulation is obtained by eliminating auxiliary variables, and a constructed family of discrete distributions Qγ converges in expected loss to the worst-case value as γ→0+.Source: §A.1 · pp. 31–32
  • Under Assumption 3.7, the proof of Theorem 3.9 shows that the worst-case loss reaches the Lipschitz-based penalty, and extends the argument from convex piecewise-linear losses to generic convex Lipschitz losses by uniform approximation.The piecewise-linear argument uses the steepest linear piece of L and the identity lip(L)=max_j≤J |a_j|.Source: §A.1 · pp. 33–34
  • For classification with Ξ = X × {−1, +1}, Theorem 3.11 uses the transportation distance, while Lemma A.3 yields the subordinate maximization reformulation and supports the smooth-hinge corollary.The smooth hinge loss function has Lipschitz modulus 1.Source: §A.1 · pp. 34–35
  • Theorem 3.17 derives a dual linear program for the classification worst-case expectation and constructs feasible Qγ distributions whose expected losses converge to the optimal worst-case value.The construction is restricted to γ∈[0,min{ρ,1}], with γ>ρ making the dual infeasible and γ≤1 ensuring non-negative atom probabilities.Source: §A.1 · pp. 35–37
  • Theorem 3.20 is proved by reducing convex piecewise-linear losses to tractable optimization problems and extending the argument to generic convex Lipschitz losses through uniform approximation.The proof uses κ = ∞, simplex structure, and the steepest linear piece under Assumption 3.18 to obtain the required bounds.Source: §A.1 · pp. 37–38
  • Theorem 3.24 derives kernelized worst-case bounds for regression and classification using the feature-map inequality, Jensen’s inequality, and the condition g′(z) ≥ 1.The regression proof relaxes feature-space support constraints, while the classification proof adapts the estimate to its distinct transportation metric.Source: §A.1 · pp. 38–40
  • Theorem 3.25 guarantees uniqueness of the optimal solution when the regularization function is strictly increasing in ∥h∥H, whereas non-decreasing regularization may permit multiple optima.The proof invokes [59, Theorem 4.2] and does not require additive separability of empirical loss and regularization.Source: §A.1 · p. 40
  • Theorems 3.26 and 3.27 apply the representer theorem to restrict optimal hypotheses to finite kernel expansions, yielding finite-dimensional formulations for the corresponding regularized problems.The objectives are non-decreasing in ∥h∥H, enabling restriction to h(x) = ∑_{j=1}^N β_j k(x, x̂_j).Source: §A.1 · p. 40
  • Theorems 3.30 and Corollary 3.32 show that worst-case expectations for regression and classification problems can be upper bounded using Lipschitz continuity and the composition inequality lip(f ◦g) ≤lip(f) lip(g).Source: §A.1 · p. 41

A.2 Proofs of Section 4

The appendix proves the concentration lemma underlying Theorem 4.6 and uses it to establish the theorem for classification, with regression following by minor modifications.

Concentration lemma

  • Lemma A.5 establishes sub-Gaussian concentration for empirical averages of linear-growth functions under Assumption 4.1, uniformly over N and δ ∈ [0, 1].The constants c3 ≥ 1 and c4 > 0 depend only on the light-tail constants a and A of P.Source: §A.2 · pp. 42–43
  • The lemma follows by pushing P and its empirical distribution through f, applying the one-dimensional concentration result, and relating Wasserstein deviation to the scalar variables’ marginals.It applies to any linear-growth function with asymptotic growth rate at most 1.Source: §A.2 · pp. 42–43

Theorem 4.6

  • Theorem 4.6 is proved explicitly for classification with Ξ = R^n × {−1, 1} and norm-based transportation cost; the regression proof requires only minor modifications.The proof uses Ω(w) = ∥w∥* as a regularization function and discretizes the hypothesis space with a finite ∆-net.Source: §A.2 · p. 43
  • The proof controls uniform deviations by combining Lipschitz continuity of the loss, finite-net cardinality bounds, norm equivalence, and Lemma A.5 for loss and input-norm functions.The resulting probability bound is at most η, which establishes the theorem’s claim.Source: §A.2 · pp. 43–45

A.3 Proofs of Section 5

The appendix proves Theorems 5.1 and 5.2 by reducing their formulations through loss identities, concave indicator representations, norm duality, and strong linear programming duality.

Proof of Theorem 5.1

  • Theorem 5.1(i) follows by identifying absolute loss with ϵ-insensitive loss at ϵ = 0 and applying Corollary 3.3.The proof fixes w and sets Ξ = Rn+1.Source: §A.3 · p. 45
  • Theorem 5.1(ii) reformulates the subordinate minimization using auxiliary variables, Proposition 5.5.4 in, and strong linear programming duality.Substitution and replacing vi with −vi produce constraints involving the dual norm of (w, −1).Source: §A.3 · p. 45

Proof of Theorem 5.2

  • Theorem 5.2 is proved by representing indicator functions as pointwise maxima of extended real-valued concave functions, then applying norm duality and strong linear programming duality.Substituting the resulting expressions into (53b) yields (42a), while (42b) follows similarly with details omitted.Source: §A.3 · pp. 46–47

Related papers

Loading 1710.10016v3…