On the Convergence Rate of Sinkhorn's Algorithm
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916674255454208 |
|---|---|
| author | Ghosal, Promit Nutz, Marcel |
| author_facet | Ghosal, Promit Nutz, Marcel |
| contents | We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate $π_{t}$ is shown to satisfy $H(π_{t}|π_{*})+H(π_{*}|π_{t})=O(t^{-1})$ where $H$ denotes relative entropy and $π_{*}$ the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with subgaussian marginals. We also obtain the rate $O(t^{-1})$ for the dual suboptimality and $O(t^{-2})$ for the marginal entropies. More precisely, we derive non-asymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for $π_{*}$ as a function of the marginals, quantified in relative entropy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_06000 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Convergence Rate of Sinkhorn's Algorithm Ghosal, Promit Nutz, Marcel Optimization and Control Analysis of PDEs Probability 90C25, 49N05 We study Sinkhorn's algorithm for solving the entropically regularized optimal transport problem. Its iterate $π_{t}$ is shown to satisfy $H(π_{t}|π_{*})+H(π_{*}|π_{t})=O(t^{-1})$ where $H$ denotes relative entropy and $π_{*}$ the optimal coupling. This holds for a large class of cost functions and marginals, including quadratic cost with subgaussian marginals. We also obtain the rate $O(t^{-1})$ for the dual suboptimality and $O(t^{-2})$ for the marginal entropies. More precisely, we derive non-asymptotic bounds, and in contrast to previous results on linear convergence that are limited to bounded costs, our estimates do not deteriorate exponentially with the regularization parameter. We also obtain a stability result for $π_{*}$ as a function of the marginals, quantified in relative entropy. |
| title | On the Convergence Rate of Sinkhorn's Algorithm |
| topic | Optimization and Control Analysis of PDEs Probability 90C25, 49N05 |
| url | https://arxiv.org/abs/2212.06000 |