Title: Introduction to Optimal Transport
Abstract: We will cover transportation theory before getting into the transportation method for concentration inequalities. It can be used to prove the isoperimetric inequality in a more general space and has many applications in data science and machine learning. In this first part, we focus on the basic optimal transport theory.
Gaspard Monge (1781) introduced optimal transport as an optimization problem of the total cost over all transport maps. However, Monge’s formulation turns out to be very difficult. In the 1940s, Kantorovich relaxed its formulation. Instead of considering a transport map, consider a coupling of the given probability measures and minimize the total cost over all these couplings. This is much more tractable because it is a convex optimization problem, unlike Monge’s problem. The convexity allows us to define dual formulation, Kantorovich duality, which can be solved by linear programming. Bernier (1987) proved Monge’s problem (M) and Kantorovich’s problem (K) are equivalent under suitable conditions on measure and cost function. I will cover these (M) and (K) formulations and Bernier’s theorem for quadratic cost.