TITLE: Distributionally Robust Stochastic Optimization with Wasserstein Distance

Abstract

Optimization under uncertainty is often formulated as a stochastic optimization problem. In many settings, a "true" probability distribution may not be known, or the notion of a true distribution may not even be applicable. In this talk, we consider an approach, called distributionally robust stochastic optimization (DRSO), in which one hedges against all probability distributions that are within a chosen Wasserstein distance from a nominal distribution, for example an empirical distribution. Comparing to the popular phi-divergences, Wasserstein distance yields more reasonable worst-case distributions. We derive a dual reformulation of the corresponding DRSO problem and construct the worst-case distribution explicitly via the first-order optimality condition of the dual problem.

Our contributions are five-fold. (i) We identify necessary and sufficient conditions for the existence of a worst-case distribution, which are naturally related to the growth rate of the objective function. (ii) We show that the worst-case distributions resulting from an appropriate Wasserstein distance have a concise structure and a clear interpretation. (iii) Using this structure, we show that data-driven DRSO problems can be approximated to any accuracy by robust optimization problems, and thereby many DRSO problems become tractable by using tools from robust optimization. (iv) To the best of our knowledge, our proof of strong duality is the first constructive proof for DRSO problems, and we show that this technique is also useful in other contexts. (v) Our strong duality result holds in a very general setting, and can be applied to infinite dimensional process control problems and worst-case value-at-risk analysis.


This is a joint work with Anton Kleywegt.

Bio

Rui Gao is a 4th  year PhD student in our department, working with Prof. Anton Kleywegt. His current research is focused on data-driven decision-making under uncertainty, arising in the context of revenue management, systems design and machine learning.