Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910494695096320 |
|---|---|
| author | Li, Gen Chen, Yanxi Huang, Yu Chi, Yuejie Poor, H. Vincent Chen, Yuxin |
| author_facet | Li, Gen Chen, Yanxi Huang, Yu Chi, Yuejie Poor, H. Vincent Chen, Yuxin |
| contents | Efficient computation of the optimal transport distance between two distributions serves as an algorithm subroutine that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $\varepsilon$ additive accuracy with runtime $\widetilde{O}( n^2/\varepsilon)$, where $n$ denotes the dimension of the probability distributions of interest. Our algorithm achieves the state-of-the-art computational guarantees among all first-order methods, while exhibiting favorable numerical performance compared to classical algorithms like Sinkhorn and Greenkhorn. Underlying our algorithm designs are two key elements: (a) converting the original problem into a bilinear minimax problem over probability distributions; (b) exploiting the extragradient idea -- in conjunction with entropy regularization and adaptive learning rates -- to accelerate convergence. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_13006 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods Li, Gen Chen, Yanxi Huang, Yu Chi, Yuejie Poor, H. Vincent Chen, Yuxin Machine Learning Data Structures and Algorithms Information Theory Optimization and Control Efficient computation of the optimal transport distance between two distributions serves as an algorithm subroutine that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $\varepsilon$ additive accuracy with runtime $\widetilde{O}( n^2/\varepsilon)$, where $n$ denotes the dimension of the probability distributions of interest. Our algorithm achieves the state-of-the-art computational guarantees among all first-order methods, while exhibiting favorable numerical performance compared to classical algorithms like Sinkhorn and Greenkhorn. Underlying our algorithm designs are two key elements: (a) converting the original problem into a bilinear minimax problem over probability distributions; (b) exploiting the extragradient idea -- in conjunction with entropy regularization and adaptive learning rates -- to accelerate convergence. |
| title | Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods |
| topic | Machine Learning Data Structures and Algorithms Information Theory Optimization and Control |
| url | https://arxiv.org/abs/2301.13006 |