A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918153386196992 |
|---|---|
| author | Chiarini, Alberto Conforti, Giovanni Greco, Giacomo Tamanini, Luca |
| author_facet | Chiarini, Alberto Conforti, Giovanni Greco, Giacomo Tamanini, Luca |
| contents | We study stability of optimizers and convergence of Sinkhorn's algorithm for the entropic optimal transport problem. In the special case of the quadratic cost, our stability bounds imply that if one of the two entropic potentials is semiconcave, then the relative entropy between optimal plans is controlled by the squared Wasserstein distance between their marginals. When employed in the analysis of Sinkhorn's algorithm, this result gives a natural sufficient condition for its exponential convergence, which does not require the ground cost to be bounded. By controlling from above the Hessians of Sinkhorn potentials in examples of interest, we obtain new exponential convergence results. For instance, for the first time we obtain exponential convergence for log-concave marginals and quadratic costs for all values of the regularization parameter, based on semiconcavity propagation results. Moreover, the convergence rate has a linear dependence on the regularization: this behavior is sharp and had only been previously obtained for compact distributions arXiv:2407.01202. These optimal rates are also established in situations where one of the two marginals does not have subgaussian tails. Other interesting new applications include subspace elastic costs, weakly log-concave marginals, marginals with light tails (where, under reinforced assumptions, we manage to improve the rates obtained in arXiv:2311.04041), the case of Lipschitz costs with bounded Hessian, and compact Riemannian manifolds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_09235 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm Chiarini, Alberto Conforti, Giovanni Greco, Giacomo Tamanini, Luca Probability Optimization and Control Machine Learning 49Q22, 68Q87, 68W40, 60E15, 90C25 We study stability of optimizers and convergence of Sinkhorn's algorithm for the entropic optimal transport problem. In the special case of the quadratic cost, our stability bounds imply that if one of the two entropic potentials is semiconcave, then the relative entropy between optimal plans is controlled by the squared Wasserstein distance between their marginals. When employed in the analysis of Sinkhorn's algorithm, this result gives a natural sufficient condition for its exponential convergence, which does not require the ground cost to be bounded. By controlling from above the Hessians of Sinkhorn potentials in examples of interest, we obtain new exponential convergence results. For instance, for the first time we obtain exponential convergence for log-concave marginals and quadratic costs for all values of the regularization parameter, based on semiconcavity propagation results. Moreover, the convergence rate has a linear dependence on the regularization: this behavior is sharp and had only been previously obtained for compact distributions arXiv:2407.01202. These optimal rates are also established in situations where one of the two marginals does not have subgaussian tails. Other interesting new applications include subspace elastic costs, weakly log-concave marginals, marginals with light tails (where, under reinforced assumptions, we manage to improve the rates obtained in arXiv:2311.04041), the case of Lipschitz costs with bounded Hessian, and compact Riemannian manifolds. |
| title | A semiconcavity approach to stability of entropic plans and exponential convergence of Sinkhorn's algorithm |
| topic | Probability Optimization and Control Machine Learning 49Q22, 68Q87, 68W40, 60E15, 90C25 |
| url | https://arxiv.org/abs/2412.09235 |