Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective

The OT problem was originally proposed by Gaspard Monge in the 1780s to address the problem of finding a method to transport resources between a collection of sources and sinks, and was rediscovered in the early 1900s by Hitchcock, Kantorovich, and Koopmans with applications in designing transportation systems, coinciding with the birth of linear programming. Recent advances in computing resources has renewed interest in the OT problem, both in the design of approximate methods for this problem suited for large-scale settings (Peyr e and Cuturi, 2019), and in the development of a theoretical understanding of its properties (Villani, 2003; Santambrogio, 2015). The "optimality" in the OT problem is defined in terms of a cost function c: X Y R . The optimal value of the problem results in a notion of discrepancy between µ and ν that complements information-theoretic discrepancy measures like the total variation distance or the Kullback-Leibler (KL) divergence. Formally, let Π( µ,ν) be the set of all joint distributions whose marginals are µ and ν .