Daniel Kuhn

Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Viet Anh Nguyen
    • Categories Convex Optimization, Robust Optimization Tags , ,

    We introduce a distributionally robust maximum likelihood estimation model with a Wasserstein ambiguity set to infer the inverse covariance matrix of a p-dimensional Gaussian random vector from n independent samples. The proposed model minimizes the worst case (maximum) of Stein’s loss across all normal reference distributions within a prescribed Wasserstein distance from the normal distribution … Read more

    Distributionally robust optimization with polynomial densities: theory, models and algorithms

  • Etienne de Klerk
  • Daniel Kuhn
  • Krzysztof Postek
    • Categories Robust Optimization, Semi-definite Programming Tags , , ,

    In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distribution that give nature too much … Read more

    Regularization via Mass Transportation

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Soroosh Shafieezadeh-Abadeh
    • Categories Robust Optimization, Stochastic Programming Tags , ,

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

    Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Approximation Algorithms, Data-Mining, Linear, Cone and Semidefinite Programming Tags , , ,

    Plain vanilla K-means clustering is prone to produce unbalanced clusters and suffers from outlier sensitivity. To mitigate both shortcomings, we formulate a joint outlier-detection and clustering problem, which assigns a prescribed number of datapoints to an auxiliary outlier cluster and performs cardinality-constrained K-means clustering on the residual dataset. We cast this problem as a mixed-integer … Read more

    Distributionally Robust Mechanism Design

  • Garud Iyengar
  • Çağıl Koçyiğit
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags , , , ,

    We study a mechanism design problem where an indivisible good is auctioned to multiple bidders, for each of whom it has a private value that is unknown to the seller and the other bidders. The agents perceive the ensemble of all bidder values as a random vector governed by an ambiguous probability distribution, which belongs … Read more

    From Data to Decisions: Distributionally Robust Optimization is Optimal

  • Daniel Kuhn
  • Bart Paul Gerard Van Parys
  • Peyman Mohajerin Esfahani
    • Categories Robust Optimization, Second-Order Cone Programming, Stochastic Programming Tags , , , , ,

    We study stochastic programs where the decision-maker cannot observe the distribution of the exogenous uncertainties but has access to a finite set of independent samples from this distribution. In this setting, the goal is to find a procedure that transforms the data to an estimate of the expected cost function under the unknown data-generating distribution, … Read more

    From Infinite to Finite Programs: Explicit Error Bounds with Applications to Approximate Dynamic Programming

  • Daniel Kuhn
  • Tobias Sutter
  • John Lygeros
  • Peyman Mohajerin Esfahani
    • Categories Dynamic Programming, Infinite Dimensional Optimization, Stochastic Programming Tags , , , ,

    We consider linear programming (LP) problems in infinite dimensional spaces that are in general computationally intractable. Under suitable assumptions, we develop an approximation bridge from the infinite-dimensional LP to tractable finite convex programs in which the performance of the approximation is quantified explicitly. To this end, we adopt the recent developments in two areas of … Read more

    Scenario Reduction Revisited: Fundamental Limits and Guarantees

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Kilian Schindler
  • Wolfram Wiesemann
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , , , ,

    The goal of scenario reduction is to approximate a given discrete distribution with another discrete distribution that has fewer atoms. We distinguish continuous scenario reduction, where the new atoms may be chosen freely, and discrete scenario reduction, where the new atoms must be chosen from among the existing ones. Using the Wasserstein distance as measure … Read more

    Decision Rule Bounds for Two-Stage Stochastic Bilevel Programs

  • Daniel Kuhn
  • Ihsan Yanıkoğlu
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We study stochastic bilevel programs where the leader chooses a binary here-and-now decision and the follower responds with a continuous wait-and-see-decision. Using modern decision rule approximations, we construct lower bounds on an optimistic version and upper bounds on a pessimistic version of the leader’s problem. Both bounding problems are equivalent to explicit mixed-integer linear programs … Read more

    Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

  • Grani A. Hanasusanto
  • Daniel Kuhn
    • Categories Robust Optimization Tags , , ,

    Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, … Read more