Designing Algorithms for Entropic Optimal Transport from an Optimisation Perspective

In this work, we study and develop a collection of methods for the entropy-regularised optimal transport (eOT) problem through the lens of optimisation. These methods are proposed as optimisation methods for the semi-dual of the eOT problem (Cuturi and Peyre, 2018) and gives rise to two broad classes of methods for solving this problem: either based on solving a non-convex constrained problem over a structured subset of couplings, or by working directly with the semi-dual. This is inspired by recent optimisation interpretations of the Sinkhorn algorithm -- the de-facto method for solving the eOT problem. By adopting this new viewpoint, we obtain non-asymptotic rates of convergence for the methods studied in this work (old and new) and particularly under minimal assumptions on the problem structure.