wasserstein distance

A Riemannian Block Coordinate Descent Method for Computing the Projection Robust Wasserstein Distance

  • Minhui Huang
  • Shiqian Ma
  • Lifeng Lai
    • Categories Nonlinear Optimization Tags , , ,

    The Wasserstein distance has become increasingly important in machine learning and deep learning. Despite its popularity, the Wasserstein distance is hard to approximate because of the curse of dimensionality. A recently proposed approach to alleviate the curse of dimensionality is to project the sampled data from the high dimensional probability distribution onto a lower-dimensional subspace, … Read more

    Semi-Discrete Optimal Transport: Hardness, Regularization and Numerical Solution

  • Bahar Tașkesen
  • Soroosh Shafieezadeh-Abadeh
  • Daniel Kuhn
    • Categories Convex and Nonsmooth Optimization, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure, are believed to be computationally hard. Even though such problems are ubiquitous in statistics, machine learning and computer vision, however, this perception has not yet received a theoretical justification. To fill this gap, we prove that … Read more

    Residuals-based distributionally robust optimization with covariate information

  • Rohit Kannan
  • Güzin Bayraksan
  • James R. Luedtke
    • Categories Robust Optimization, Stochastic Programming Tags , , , , , , ,

    We consider data-driven approaches that integrate a machine learning prediction model within distributionally robust optimization (DRO) given limited joint observations of uncertain parameters and covariates. Our framework is flexible in the sense that it can accommodate a variety of regression setups and DRO ambiguity sets. We investigate asymptotic and finite sample properties of solutions obtained … Read more

    Distributionally Robust Two-Stage Stochastic Programming

  • Daniel Duque
  • Sanjay Mehrotra
  • David P. Morton
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and … Read more

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

  • Rui Gao
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags , , , ,

    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. … Read more

    Computationally Efficient Approximations for Distributionally Robust Optimization

  • Jianqiang Cheng
  • Ruiwei Jiang
  • Meysam Cheramin
  • Kai Pan
    • Categories Stochastic Programming Tags , , ,

    Distributionally robust optimization (DRO) is a modeling framework in decision making under uncertainty where the probability distribution of a random parameter is unknown while its partial information (e.g., statistical properties) is available. In this framework, the unknown probability distribution is assumed to lie in an ambiguity set consisting of all distributions that are compatible with … Read more

    Regret in the Newsvendor Model with Demand and Yield Randomness

  • Zhi Chen
  • Weijun Xie
    • Categories Robust Optimization Tags , , , , ,

    We study the fundamental stochastic newsvendor model that considers both demand and yield randomness. It is usually difficult in practice to describe precisely the joint demand and yield distribution, although partial statistical information and empirical data about this ambiguous distribution are often accessible. We combat the issue of distributional ambiguity by taking a data-driven distributionally … Read more

    On Linear Optimization over Wasserstein Balls

  • Daniel Kuhn
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    Wasserstein balls, which contain all probability measures within a pre-specified Wasserstein distance to a reference measure, have recently enjoyed wide popularity in the distributionally robust optimization and machine learning communities to formulate and solve data-driven optimization problems with rigorous statistical guarantees. In this technical note we prove that the Wasserstein ball is weakly compact under … Read more

    Bridging Bayesian and Minimax Mean Square Error Estimation via Wasserstein Distributionally Robust Optimization

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Viet Anh Nguyen
  • Soroosh Shafieezadeh-Abadeh
    • Categories Infinite Dimensional Optimization, Statistics, Stochastic Programming Tags , ,

    We introduce a distributionally robust minimium mean square error estimation model with a Wasserstein ambiguity set to recover an unknown signal from a noisy observation. The proposed model can be viewed as a zero-sum game between a statistician choosing an estimator—that is, a measurable function of the observation—and a fictitious adversary choosing a prior—that is, … Read more

    Optimistic Distributionally Robust Optimization for Nonparametric Likelihood Approximation

  • Daniel Kuhn
  • Viet Anh Nguyen
  • Soroosh Shafieezadeh-Abadeh
  • Wolfram Wiesemann
  • Man-Chung Yue
    • Categories Stochastic Programming Tags , , , ,

    The likelihood function is a fundamental component in Bayesian statistics. However, evaluating the likelihood of an observation is computationally intractable in many applications. In this paper, we propose a non-parametric approximation of the likelihood that identifies a probability measure which lies in the neighborhood of the nominal measure and that maximizes the probability of observing … Read more