Talk Title: Semi-discrete Optimal Transport: Hardness, Regularization and Numerical Solution

Speaker: Soroosh Shafieezadeh Abadeh

Meeting Link: https://gatech.zoom.us/j/99381428980

Abstract: 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 computing the Wasserstein distance between a discrete probability measure supported on two points and the Lebesgue measure on the standard hypercube is already #P-hard. This insight prompts us to seek approximate solutions for semi-discrete optimal transport problems. We thus perturb the underlying transportation cost with an additive disturbance governed by an ambiguous probability distribution, and we introduce a distributionally robust dual optimal transport problem whose objective function is smoothed with the most adverse disturbance distributions from within a given ambiguity set. We further show that smoothing the dual objective function is equivalent to regularizing the primal objective function, and we identify several ambiguity sets that give rise to several known and new regularization schemes. As a byproduct, we discover an intimate relation between semi-discrete optimal transport problems and discrete choice models traditionally studied in psychology and economics. To solve the regularized optimal transport problems efficiently, we use a stochastic gradient descent algorithm with imprecise stochastic gradient oracles. A new convergence analysis reveals that this algorithm improves the best-known convergence guarantee for semi-discrete optimal transport problems with entropic regularizers.

Bio: Soroosh Shafieezadeh Abadeh is currently a postdoctoral researcher at Tepper School of Business at Carnegie Mellon University, working with Professor Fatma Kılınç-Karzan. Before joining CMU, he held a postdoctoral position at the Automatic Control Laboratory at ETH Zurich, working with Professor John Lygeros and Professor Florian Dörfler. He received his doctoral degree in Management of Technology from École Polytechnique Fédérale de Lausanne in 2020, where he worked with Professor Daniel Kuhn and Professor Peyman Mohajerin Esfahani. His doctoral dissertation entitled Wasserstein Distributionally Robust Learning was awarded an EPFL Thesis Distinction in 2020. He received a Bachelor and a master’s degree in electrical engineering (major in automatic control) from the University of Tehran in 2011 and 2014, respectively. His current research interests are focused on optimization under uncertainty, the design of large-scale algorithms for solving stochastic and distributionally robust optimization problems, and the development of statistical tools for data-driven decision-making problems. His research is inspired by applications in machine learning, control, economics and finance.

Note: Boxed lunch with be served at the seminar. So, please stop by 15 minutes before the seminar to pick up lunch.