2022

Bahar Taskesen is selected as the winner of the 2022 INFORMS Optimization Society Student Prize

Winner

Bahar Taskesen (Risk Analytics and Optimization at Ecole Polytechnique Federale de Lausanne, Switzerland) for the paper titled "Semi-Discrete Optimal Transport: Hardness, Regularization, and Numerical Solution" jointly authored with Soroosh Shafieezadeh-Abadeh and Daniel Kuhn.

Citation

This research studies semi-discrete optimal transport problems, which evaluate the Wasserstein distance between a discrete and a generic (possibly non-discrete) probability measure. Optimal transport theory has a long history in mathematics dating back to the seminal work of Monge (1781) and Kantorovich (1942) and has recently been widely used in machine learning and computer vision. This paper first proves 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. Therefore, they approximate the semi-discrete optimal transport problems via distributionally robust dual optimal transport problems. This approximation can be interpreted as regularized semi- discrete optimal transport problems and can be solved via an efficient stochastic gradient descent algorithm with imprecise stochastic gradient oracles. This paper is of high quality, and the topic is important and timely. We expect this work to have a long-standing impact on many domains in distributionally robust optimization, machine learning, computer vision, and computational geometry.

Honorable Mentions:

Sebastian Perez-Salazar (School of Industrial and Systems Engineering, Georgia Institute of Technology, USA) for the paper "Adaptive Bin Packing with Overflow", jointly authored with Mohit Singh and Alejandro Toriello.

Haoming Shen (Department of Industrial and Operations Engineering, University of Michigan, USA) for the paper "Convex Chance-Constrained Programs with Wasserstein Ambiguity", jointly authored with Ruiwei Jiang.

Prize committee

Weijun Xie (chair), Andres Gomez, Aida Khajavirad, Carla Michini