PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Wasserstein Profile Inference and Applications to Machine Learning

Jose Blanchet, Yang Kang, Karthyek Murthy

arXiv:1610.05627v4math.ST

TL;DR

The paper asks how regularization and DRO uncertainty radii can be connected and selected without cross validation. It represents several estimators through optimal-transport-based DRO, introduces RWPI for radius inference, and reports principled calibration with coverage and convergence guarantees. The framework applies beyond the showcased regression settings, while relying on stated regularity conditions.

  • Problem

    Regularization parameters are crucial for estimator performance but are often chosen by repeatedly testing alternatives through cross validation.

  • Method

    The paper represents regularized estimators as optimal-transport-based DRO problems and introduces RWPI, an Empirical-Likelihood extension using optimal transport costs.

  • Results

    The proposed radius prescriptions provide coverage guarantees for optimal risk with an O(n−1/2) convergence rate and yield regularization choices consistent with independent statistical prescriptions.

  • Takeaways & Limitations

    RWPI provides a systematic way to select DRO uncertainty radii and corresponding regularization parameters for several machine learning estimators.

  • Takeaways & Limitations

    The analysis uses a local Lipschitz assumption A6), although the authors state that it can be relaxed.

Abstract

from arXiv · show

We show that several machine learning estimators, including square-root LASSO (Least Absolute Shrinkage and Selection) and regularized logistic regression can be represented as solutions to distributionally robust optimization (DRO) problems. The associated uncertainty regions are based on suitably defined Wasserstein distances. Hence, our representations allow us to view regularization as a result of introducing an artificial adversary that perturbs the empirical distribution to account for out-of-sample effects in loss estimation. In addition, we introduce RWPI (Robust Wasserstein Profile Inference), a novel inference methodology which extends the use of methods inspired by Empirical Likelihood to the setting of optimal transport costs (of which Wasserstein distances are a particular case). We use RWPI to show how to optimally select the size of uncertainty regions, and as a consequence, we are able to choose regularization parameters for these machine learning estimators without the use of cross validation. Numerical experiments are also given to validate our theoretical findings.

1. Introduction

The paper interprets regularization through optimal-transport-based DRO and introduces RWPI to calibrate uncertainty radii and regularization parameters. It applies this framework to several estimators and establishes inference and coverage results, including high-dimensional square-root LASSO.

  • Motivation: Regularization can be interpreted as optimally transporting mass from the empirical measure to maximize loss under a budget constraint.The budget constrains how far the empirical distribution may be perturbed.
  • DRO representation: The regularization parameter equals the DRO uncertainty-set radius, enabling a principled optimization criterion for choosing it.The paper applies this interpretation to square-root LASSO and regularized logistic regression, among others.
  • Inference and calibration: The selected radius is the smallest value making the optimal parameter plausible with 1−α confidence, which yields coverage guarantees for optimal risk.The paper connects this criterion directly to the DRO optimizer and confidence-region construction.
  • RWPI methodology: RWPI extends Empirical Likelihood by replacing likelihood-based discrepancies with optimal transport costs and supports asymptotic selection of the uncertainty radius.Its analysis centers on the Robust Wasserstein Profile function evaluated at the optimal parameter.
  • Scope: The framework recasts square-root LASSO, regularized logistic regression, and support vector machines as optimal-transport-based DRO problems.The RWP function is also presented as applicable to general estimating equations and broader data-driven DRO settings.

2. Optimal Transport Definitions and DRO Representations of Machine Learning Estimators

The paper defines optimal transport discrepancies and uses Wasserstein-type DRO formulations to reinterpret regularized machine-learning estimators. General duality results then yield exact representations for regression, logistic regression, and SVM regularization.

  • Optimal transport definitions: Optimal transport cost D_c(P, Q) minimizes expected transportation cost over joint distributions with marginals P and Q.The cost c(u, w) measures the expense of transporting unit mass from u to w.
  • Optimal transport definitions: Wasserstein distances arise from costs whose powered form is a metric, while the paper also permits lower semi-continuous costs that may be infinite.This broader cost structure is needed for the paper’s machine-learning formulations.
  • DRO representations: DRO minimizes loss over predictors while evaluating performance against all distributions within a transport-cost neighborhood of the empirical distribution.This reframes robustness and generalization through perturbations of the empirical training distribution.
  • DRO representations: For square loss, suitably chosen Wasserstein-type discrepancies recover ℓp-norm regularized linear regression, including exact norm regularization in β.The modified cost removes ambiguity in the response variable and replaces ∥β̄∥p with ∥β∥p.
  • DRO representations: The same framework exactly recovers regularized logistic regression and SVMs with log-exponential and hinge losses, respectively.The paper emphasizes that these classification equivalences use a general cost structure and, for the stated formulation, infinite transportation costs.

3. The Robust Wasserstein Profile Function

The Robust Wasserstein Profile function extends profile-likelihood-style inference to estimating equations with optimal-transport costs. Its asymptotic behavior yields confidence regions and depends on the transport-cost exponent.

  • Definition: The RWP function is defined for estimating equations E[h(W, θ)] = 0 using i.i.d. samples and a Wasserstein-type transport cost.The framework uses the empirical distribution and cost functions based on ℓq distances, while allowing adaptation to more general costs.
  • Inference: The RWP function supports inference by identifying parameters satisfying the population estimating equation and diverging away from such parameters after scaling.For θ satisfying E[h(W, θ)] = 0, Rn(θ; ρ) tends to zero; otherwise, n^ρ/2Rn(θ; ρ) tends to infinity.
  • Assumptions: The theory assumes fixed dimension, and the local Lipschitz condition A6) is imposed for analytical simplicity but can be relaxed.The paper describes A6) as mild for its applications rather than essential to the broader framework.
  • Extensions: The asymptotic analysis applies to general estimating equations, while the linear-regression profile is recovered as a particular choice of W and h.The general theory includes both upper-bound results and matching lower bounds under mild additional conditions.
  • Asymptotic theory: Under suitable conditions, n^ρ/2Rn(θ∗; ρ) converges in distribution to a random variable that determines asymptotic confidence-region thresholds.The analysis establishes stochastic upper and lower bounds, with matching limits under additional regularity conditions.

4. Using RWPI for optimal regularization

RWPI uses the asymptotic RWP distribution to select the DRO uncertainty radius and thereby the regularization parameter. The resulting prescriptions provide coverage and achieve an O(n^-1/2) optimal-risk rate, including a high-dimensional square-root LASSO result.

  • Selecting δ: δ equals the regularization parameter λ in both square-root LASSO and regularized logistic regression.The DRO representations make the uncertainty radius and regularization coefficient identical in the two examples.
  • Selecting δ: RWPI selects δ so that the true model parameter belongs to the confidence region with the desired asymptotic coverage.The events Rn(β∗) ≤ δ and β∗ ∈ Λn(δ) coincide, linking the RWP threshold directly to parameter coverage.
  • Coverage and rates: O(n^-1/2) is the optimal-risk convergence rate achieved by the RWPI-based radius prescription, contrasting with the O(n^-1/d) concentration-based rate.The rate reflects RWPI’s focus on coverage for the d-dimensional optimal parameter rather than the full distribution.
  • Square-root LASSO: The square-root LASSO regularization prescription does not depend on the error variance, avoiding the need to estimate that variance.The paper identifies this as an advantage over traditional LASSO.
  • Square-root LASSO: The prescription can use an upper bound independent of β∗, while a consistent plug-in estimator may reduce bias but has not yet been shown to improve generalization guarantees.The paper proposes plug-in estimation as a possible refinement and leaves its guarantees for future research.
  • High-dimensional square-root LASSO: The high-dimensional square-root LASSO prescription is valid uniformly when log d ≤ Cn^1/2−ε under the stated regularity conditions.For nonnormal errors, the paper gives a separate uniform condition d ≤ 0.5αn^(a−2−ε)/2 with an additional moment assumption.

5. Numerical Examples

The numerical examples compare RWPI-based square-root LASSO regularization selection with cross-validation and OLS across synthetic and diabetes regression settings. They also assess whether the DRO worst-case loss provides a tight upper bound for optimal risk.

  • Experimental comparisons: RWPI-based square-root LASSO selection is compared with cross-validation and OLS using training and test mean square errors.The comparisons cover synthetic sparse linear regression and diabetes data.
  • Synthetic regression: The synthetic setting varies predictor dimension and training-sample size to evaluate RWPI-based square-root LASSO.Example 4 uses a sparse linear model with correlated normal predictors and Gaussian noise with σ = 10.
  • Evaluation metrics: 100 repetitions yield average training and test MSEs plus average ℓ1 and ℓ2 coefficient errors for the regression procedures.The experiments also report empirical coverage probabilities for the DRO worst-case expected loss.
  • Coverage assessment: The DRO worst-case expected loss is evaluated against the optimal error E[(Y−E[Y|X])^2] = σ^2 = 100.Coverage closer to 1−α = 0.95 indicates a tighter upper bound for the optimal loss.
  • High-dimensional regression: Table 2 covers d = 600 predictors, including a case where n < d and OLS is not applicable.The table compares RWPI-based and cross-validation-based square-root LASSO mean square errors with OLS where available.

6. Conclusions

The conclusions recast several regularized machine learning estimators as optimal-transport DRO problems and introduce RWPI for selecting uncertainty-set radii. The resulting framework supports regularization selection and coverage guarantees, while a limiting profile relationship suggests further inference and optimization uses.

  • Main conclusions: Square-root LASSO, regularized logistic regression, and support vector machines are represented as optimal-transport-based DRO formulations.This connects regularized estimators to a common DRO formulation.
  • Main conclusions: RWPI is used at the optimal parameter to choose the DRO radius δ and derive corresponding regularization-parameter prescriptions.The prescriptions apply to ℓp-norm-regularized linear and logistic regression.
  • Main conclusions: The proposed radius prescriptions produce prescriptions similar to those obtained from independent considerations in the statistics literature.This comparison is reported for the settings studied in the paper.
  • Future inference uses: A limiting relationship for the profile function near θ* can support confidence intervals, DRO solution error bounds, and plug-in radius selection.The stated relationship is n^ρ/2 R_n(θ* + Δ/√n) ⇒ L(Δ), for continuous L(·).
  • Supporting material: The article’s proofs are provided in supplementary material.The supplementary material is located after the References section.

Supplementary material to the paper Robust Wasserstein Profile Inference and Applications to Machine Learning

The supplementary material contains proofs of the paper’s main results and supporting technical background on moment problems and strong duality.

  • Organization: Section A provides proofs of all main results, while Section B introduces moment problems and a useful strong-duality result.The supplementary material also includes additional technical results beyond the portions described here.

Appendix A. Proofs of main results

Appendix A organizes proofs for the paper’s distributionally robust representations, coverage properties, stochastic bounds, and selected applications.

  • Proof organization: Subsection A.1 derives the distributionally robust representations presented in Section 2.4.
  • Proof organization: Subsection A.2 proves the coverage properties.
  • Proof organization: Subsection A.3 proves stochastic upper and lower bounds and the resulting weak limits presented in Section 3.3.
  • Proof organization: Subsection A.4 contains proofs of Theorems 5 and 6 as applications of the stochastic bounds.

A.1. Proofs of the distributionally robust representations in Section 2.4.

The proofs derive distributionally robust representations for norm-regularized regression, square-root LASSO, logistic regression, and SVM objectives using Wasserstein-cost duality. Infinite transportation costs enforce label preservation and enable an exact regularized logistic-regression representation.

  • Norm-regularized regression: The appendix proves that norm-regularized regressions arise as special cases of distributionally robust regression.These results are identified as Proposition 2 and Theorems 1 and 2.
  • Linear regression: Hölder’s inequality bounds the perturbation term by the product of dual norms, producing the norm-dependent regularization structure.For the linear-regression loss, the proof uses |β̄^TΔ| ≤ ||β̄||_p||Δ||_q.
  • Linear regression: The dual formulation becomes finite only when the dual variable exceeds the coefficient norm, after which the empirical quadratic term is identified with mean square error.The proof explicitly notes that φγ is infinite when γ ≤ ||β||_2 and identifies the empirical term as MSE_n(β).
  • Logistic regression: Infinite transportation costs for label changes restrict the adversary to perturbations preserving each observed label.This restriction reduces the supremum to points with y′ = Y_i.
  • Logistic regression: The resulting worst-case expected log-exponential loss is equivalent to regularized logistic regression.The proof obtains this equivalence after applying the Wasserstein DRO dual formulation pointwise.
  • Support Vector Machines: For SVM hinge loss, the proof applies minimax reasoning and Hölder’s inequality before restricting the outer minimization to λ ≥ ||β||_q.The resulting expression completes the distributionally robust representation argument for the hinge-loss case.

A.2. Proofs of results on coverage properties.

The coverage proofs bound out-of-sample loss relative to empirical loss through Wasserstein neighborhoods and regularized estimators. The resulting bounds combine a radius-dependent term with a sampling term and establish the stated asymptotic guarantee.

  • Coverage comparison: The proof uses a distribution within Wasserstein distance δ of the empirical distribution to compare expected losses under the target and empirical measures.Symmetry of the transport cost gives D_c(P̂,P_n) ≤ δ, which feeds the comparison bound.
  • Coverage comparison: The comparison is bounded by C1δ + C2(n)^1/ρ=2.This is the stated upper-bound form after substituting the regularized regression estimators for the relevant cases.
  • Regression applications: The same argument applies the regularized regression estimators from Theorems 1 and 2 for linear and logistic regression.The proof repeats the theorem arguments with the baseline distribution set to P̂ rather than P_n.
  • Asymptotic guarantee: The target expected loss is related to the empirical optimum through a high-probability bound involving (α^-1n^-1 Var_P*[l(X,Y;β*)])^1/4.The bound holds with probability exceeding 1 − α, and the theorem concludes via triangle inequality and a union bound.

A.3. Proofs of asymptotic stochastic upper and lower bounds of RWP function in Section 3.3.

These proofs establish asymptotic stochastic upper and lower bounds for the RWP function by localizing the dual optimization, controlling perturbation regions, and exploiting continuity and moment assumptions. Separate arguments handle ρ > 1, ρ = 1, and the associated regression cases.

  • Dual localization: Proposition 3 supplies the dual formulation used to analyze n^ρ/2R_n(θ*), with Assumptions A2 and A4 placing zero in the relevant convex hull interior.The proof then localizes the dual variable to a bounded norm region with high probability.
  • Uniform convergence: Continuity, bounded localization, and the Strong Law of Large Numbers yield uniform convergence on compact dual-variable sets in probability.The argument uses convergence of finite-dimensional distributions and a deterministic limit.
  • Case ρ = 1: For ρ = 1, the proof separates small and large perturbations, replaces the local integrand by ζ^TD_h(W_i)Δ, and solves the inner maximization.The large-perturbation region is controlled first, while the local region supports the linear approximation.
  • Lower bound: Moment and continuity conditions control the localization errors and yield the desired asymptotic stochastic lower bound.The proof sends ε′′ and δ to zero and b to infinity after establishing the intermediate bounds.

A.4. Proofs of RWP function limit theorems for linear and logistic regression examples.

The limit-theorem proofs derive dual RWP representations for linear and logistic regression and verify the assumptions needed for convergence in distribution. Linear regression obtains a Gaussian-based limit, while logistic regression receives a stochastic upper bound.

  • Dual formulations: The RWP dual formulation is obtained from Proposition 3 using estimating equations for linear and logistic regression with cost c(·) = N_q(·).The linear estimating equation is h(x,y;β) = (y − β^Tx)x, while the logistic case uses the equation defined earlier in the paper.
  • Linear regression: For linear regression, finite variance and covariance assumptions verify the conditions needed to apply the ρ = 2 convergence result.Under H0, the residual is independent of X, has zero mean, and has finite variance σ^2.
  • Linear regression: The linear-regression RWP function converges to the stated Gaussian-based limit involving H ~ N(0, Cov[h(X,Y;β*)]).When Cov[h(X,Y;β*)] = σ^2Σ, the proof standardizes with Z = H/σ.
  • Logistic regression: For logistic regression, continuity, moment, density, and derivative conditions verify the assumptions for the ρ = 1 limit analysis.The proof uses the logistic optimality condition E[h(X,Y;β*)] = 0 and verifies the required assumptions through properties of X and Y.
  • Logistic regression: The logistic-regression analysis bounds the limiting RWP quantity by a Gaussian norm involving a covariance matrix based on E[XX^T].The proof shows stochastic domination by L4 := ||Ẑ||_q for Ẑ ~ N(0,E[XX^T]).

Appendix B. Strong duality for the linear semi-infinite program resulting from the RWP function

The appendix casts the RWP function as a problem of moments and uses a Slater condition to obtain a dual representation. This establishes the dual form used for asymptotic analysis of RWP.

  • Strong duality then provides the dual representation of R_n used in the paper’s asymptotic analysis.
  • The problem of moments seeks a worst-case bound over nonnegative measures satisfying prescribed moment constraints.
  • Adding the normalization moment f_0 = 1_Ω reformulates the problem with an augmented moment vector.
  • An interior-point Slater condition yields an equivalent dual representation for the moment problem.
  • The RWP function is recast as a special case of this moment-problem duality using the empirical sample constraints and transport cost structure.

Appendix C. Exchange of sup and inf in the DRO formulation (8)

The appendix justifies exchanging the supremum and infimum in the DRO formulation by approximating the uncertainty set and proving convergence of the resulting optimization problems.

  • The exchange applies when the robust objective is real-valued, level-bounded, convex, and lower semicontinuous in the decision variable.
  • Compact-support approximation problems produce an increasing sequence of robust objective functions through Sion’s minimax theorem.
  • The approximation objectives converge pointwise to the unrestricted robust objective.
  • The approximating objectives epiconverge to the limiting objective as the support bound grows.
  • Convexity and level-boundedness ensure convergence of optimal values, forcing the inequalities in the minimax relation to become equalities.
  • For linear regression, finite second moments and the DRO representation verify the required conditions; analogous reasoning applies to logistic regression.
Loading 1610.05627v4…