Sharp $O(1/k)$ convergence rate for the Sinkhorn algorithm via a local analysis
We prove that the Sinkhorn algorithm converges at the rate of $O(1/k)$ in $\ell_1$-norm marginal error and in joint relative entropy, which is known to be sharp in the asymptotically scalable case. The proof is based on examining the bipartite graph associated to the entropy-regularized optimal transport problem, and treating differently the edges that are assigned a positive mass in the optimal transport plan vs. those that are not. This yields a local convergence bound with the sharp rate, which is bootstrapped into a global bound using the author's previous result in arXiv:2604.26265…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.28973
curl -X POST /api/v1/records/arxiv/2606.28973/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.28973/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'