Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration
Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distance...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Published: |
Neural Information Processing Systems Foundation
2018
|
| Online Access: | http://hdl.handle.net/1721.1/116389 https://orcid.org/0000-0002-4933-1455 https://orcid.org/0000-0002-0135-7162 |
| _version_ | 1826206786112192512 |
|---|---|
| author | Altschuler, Jason Max Weed, Jonathan Rigollet, Philippe |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Altschuler, Jason Max Weed, Jonathan Rigollet, Philippe |
| author_sort | Altschuler, Jason Max |
| collection | MIT |
| description | Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iterations, which also directly suggests a new greedy coordinate descent algorithm GREENKHORN with the same theoretical guarantees. Numerical simulations illustrate that GREENKHORN significantly outperforms the classical SINKHORN algorithm in practice. |
| first_indexed | 2024-09-23T13:38:19Z |
| format | Article |
| id | mit-1721.1/116389 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T13:38:19Z |
| publishDate | 2018 |
| publisher | Neural Information Processing Systems Foundation |
| record_format | dspace |
| spelling | mit-1721.1/1163892022-09-28T15:13:44Z Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration Altschuler, Jason Max Weed, Jonathan Rigollet, Philippe Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Altschuler, Jason Max Weed, Jonathan Rigollet, Philippe Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iterations, which also directly suggests a new greedy coordinate descent algorithm GREENKHORN with the same theoretical guarantees. Numerical simulations illustrate that GREENKHORN significantly outperforms the classical SINKHORN algorithm in practice. National Science Foundation (U.S.). Graduate Research Fellowship Program (1122374) National Science Foundation (U.S.). Faculty Early Career Development Program (DMS-1541099) National Science Foundation (U.S.). Faculty Early Career Development Program (DMS-1541100) National Science Foundation (U.S.). Faculty Early Career Development Program (DMS-1712596) United States. Defense Advanced Research Projects Agency (W911NF-16-1-0551) United States. Office of Naval Research (N00014-17-1-2147) MIT NEC Corporation (grant) 2018-06-19T12:13:02Z 2018-06-19T12:13:02Z 2018-02 2018-05-30T13:10:45Z Article http://purl.org/eprint/type/ConferencePaper 1049-5258 http://hdl.handle.net/1721.1/116389 Altschuler, Jason, Jonathan Weed and Philippe Rigollet. "Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration." Advances in Neural Information Processing Systems 30 (NIPS 2017): 1961-1971. https://orcid.org/0000-0002-4933-1455 https://orcid.org/0000-0002-0135-7162 http://dx.doi.org/ Advances in Neural Information Processing Systems Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Neural Information Processing Systems Foundation Neural Information Processing Systems (NIPS) |
| spellingShingle | Altschuler, Jason Max Weed, Jonathan Rigollet, Philippe Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title | Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title_full | Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title_fullStr | Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title_full_unstemmed | Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title_short | Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration |
| title_sort | near linear time approximation algorithms for optimal transport via sinkhorn iteration |
| url | http://hdl.handle.net/1721.1/116389 https://orcid.org/0000-0002-4933-1455 https://orcid.org/0000-0002-0135-7162 |
| work_keys_str_mv | AT altschulerjasonmax nearlineartimeapproximationalgorithmsforoptimaltransportviasinkhorniteration AT weedjonathan nearlineartimeapproximationalgorithmsforoptimaltransportviasinkhorniteration AT rigolletphilippe nearlineartimeapproximationalgorithmsforoptimaltransportviasinkhorniteration |