{
  "id": "2304.04451",
  "version": "v1",
  "published": "2023-04-10T08:35:44.000Z",
  "updated": "2023-04-10T08:35:44.000Z",
  "title": "Quantitative contraction rates for Sinkhorn algorithm: beyond bounded costs and compact marginals",
  "authors": [
    "Giovanni Conforti",
    "Alain Durmus",
    "Giacomo Greco"
  ],
  "comment": "51 pages",
  "categories": [
    "math.PR",
    "math.OC"
  ],
  "abstract": "We show non-asymptotic geometric convergence of Sinkhorn iterates to the Schr\\\"odinger potentials, solutions of the quadratic Entropic Optimal Transport problem on $\\mathbb{R}^d$. Our results hold under mild assumptions on the marginal inputs: in particular, we only assume that they admit an asymptotically positive log-concavity profile, covering as special cases log-concave distributions and bounded smooth perturbations of quadratic potentials. More precisely, we provide exponential $\\mathrm{L}^1$ and pointwise convergence of the iterates (resp. their gradient and Hessian) to Schr\\\"odinger potentials (resp. their gradient and Hessian) for large enough values of the regularization parameter. As a corollary, we establish exponential convergence of Sinkhorn plans and bridges w.r.t. a symmetric relative entropy. Up to the authors' knowledge, these are the first results which establish geometric convergence of Sinkhorn algorithm in a general setting without assuming bounded cost functions or compactly supported marginals. Our results are proven following a probabilistic approach that rests on integrated semiconvexity estimates for Sinkhorn iterates that are of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-04-10T08:35:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "49Q22",
      "90C25",
      "49N05",
      "93E20",
      "47D07"
    ],
    "keywords": [
      "quantitative contraction rates",
      "sinkhorn algorithm",
      "bounded cost",
      "compact marginals",
      "quadratic entropic optimal transport problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 51,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}