Giacomo Greco<EMAIL_ADDRESS>University of Technology and Maxence
Noble<EMAIL_ADDRESS>Conforti
<EMAIL_ADDRESS>Oliviero–Durmus
<EMAIL_ADDRESS>Polytechnique

# Non-asymptotic convergence bounds for Sinkhorn iterates and their gradients:
a coupling approach.

###### Abstract

Computational optimal transport (OT) has recently emerged as a powerful
framework with applications in various fields. In this paper we focus on a
relaxation of the original OT problem, the entropic OT problem, which allows
to implement efficient and practical algorithmic solutions, even in high
dimensional settings. This formulation, also known as the Schrödinger Bridge
problem, notably connects with Stochastic Optimal Control (SOC) and can be
solved with the popular Sinkhorn algorithm. In the case of discrete-state
spaces, this algorithm is known to have exponential convergence; however,
achieving a similar rate of convergence in a more general setting is still an
active area of research. In this work, we analyze the convergence of the
Sinkhorn algorithm for probability measures defined on the $d$-dimensional
torus $\mathbb{T}_{L}^{d}$, that admit densities with respect to the Haar
measure of $\mathbb{T}_{L}^{d}$. In particular, we prove pointwise exponential
convergence of Sinkhorn iterates and their gradient. Our proof relies on the
connection between these iterates and the evolution along the Hamilton-Jacobi-
Bellman equations of value functions obtained from SOC -problems. Our approach
is novel in that it is purely probabilistic and relies on coupling by
reflection techniques for controlled diffusions on the torus.

###### keywords:

optimal transport, Sinkhorn algorithm, stochastic optimal control, Schrödinger
bridge

##  1 Introduction

Computational optimal transport (OT) has known great progress over these past
few years (peyre2019computational), and has thus become a popular tool in a
wide range of fields such as machine learning (adler2017learning;
arjovsky2017wasserstein), computer vision (dominitz2009texture;
solomon2015convolutional), or signal processing (kolouri2017optimal). Let
$\mu$ and $\nu$ be two probability measures defined on a measurable state
space $(\mathsf{X},\mathcal{X})$. The primal OT problem (villani2008optimal)
between $\mu$ and $\nu$, corresponding to a measurable cost function
$\mathsf{c}\,:\mathsf{X}^{2}\to[0,+\infty)$, can be formulated as solving the
optimization problem

$\inf_{\pi\in\Pi(\mu,\nu)}\int\mathsf{c}(x,y)\mathrm{d}\pi(x,y)\,,$ (1)

where $\Pi(\mu,\nu)$ is defined as the set of couplings between $\mu$ and
$\nu$, i.e., $\pi\in\Pi(\mu,\nu)$ if
$\pi(\mathsf{A}\times\mathsf{X})=\mu(\mathsf{A})$ and
$\pi(\mathsf{X}\times\mathsf{A})=\nu(\mathsf{A})$ for any
$\mathsf{A}\in\mathcal{X}$. This problem admits the following dual formulation

$\sup_{(\varphi^{\star},\psi^{\star})\in\mathcal{R}(\mathsf{c})}\int\\{\varphi^{\star}(x)+\psi^{\star}(y)\\}\mathrm{d}(\mu\otimes\nu)(x,y)\,,$
(2)

where

$\mathcal{R}(\mathsf{c})=\\{(\varphi^{\star},\psi^{\star})\in\mathcal{C}(\mathsf{X})^{2}:\text{
for any
}(x,y)\in\mathsf{X}^{2},\varphi^{\star}(x)+\psi^{\star}(y)\leq\mathsf{c}(x,y)\\}$

is the set of “Kantorovitch potentials” (kellerer1984duality). In many
applications of OT, $\mathsf{X}\subset\mathbb{R}^{d}$ and one chooses the
Euclidean quadratic cost $\mathsf{c}(x,y)=\|x-y\|^{2}/2$. Under this setting,
Monge-Kantorovich’s theorem states that (1) admits a unique minimizer
$\pi^{\star}$. In addition, in the case where $\mu$ admits a density with
respect to the Lebesgue measure, Brenier’s theorem (brenier1991polar)
established that this minimizer is also solution to the Monge problem, i.e.,
there exists a convex function
$\Psi:\mathbb{R}^{d}\to\mathbb{R}\cup\\{\infty\\}$ such that $\pi^{\star}$ is
the pushforward of $\mu$ by the application $x\mapsto(x,\mathrm{T}(x))$ with
$\mathrm{T}(x)=\nabla\Psi(x)$ if $\Psi(x)<\infty$ and $\mathrm{T}(x)=0$
otherwise (referred to as the “Monge” map). Moreover, $\Psi$ is related to a
Kantorovitch potential $\varphi^{\star}$ solving (2) as $\Psi(x)=$