An elementary introduction to entropic regularization and proximal methods for numerical optimal transport.

Summary These notes contains the material that I presented to the CEA-EDF-INRIA summer school about numerical optimal transport. These notes are, on purpose, written at an elementary level, with almost no prerequisite knowledge and the writing style is relatively informal. All the methods presented hereafter rely on convex optimization, so we start with a fairly basic introduction to convex analysis and optimization. Then, we present the entropic regularization of the Kantorovich formulation and present the now well known Sinkhorn algorithm, whose convergence is proven in continuous setting with a simple proof. We prove the linear convergence rate of this algorithm with respect to the Hilbert metric. The second numerical method we present use the dynamical formulation of optimal transport proposed by Benamou and Brenier which is solvable via non-smooth convex optimization methods. We end this short course with an overview of other dynamical formulations of optimal transport like problems.