Wasserstein Barycenters Are NP-Hard to Compute
| Autor: | Jason M. Altschuler, Enric Boix-Adserà |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Computational Complexity Computer Science - Machine Learning Optimization and Control (math.OC) Computer Science - Data Structures and Algorithms FOS: Mathematics Mathematics::Metric Geometry Data Structures and Algorithms (cs.DS) Computational Complexity (cs.CC) Mathematics - Optimization and Control Machine Learning (cs.LG) |
| Zdroj: | SIAM Journal on Mathematics of Data Science. 4:179-203 |
| ISSN: | 2577-0187 |
| DOI: | 10.1137/21m1390062 |
| Popis: | Computing Wasserstein barycenters (a.k.a. Optimal Transport barycenters) is a fundamental problem in geometry which has recently attracted considerable attention due to many applications in data science. While there exist polynomial-time algorithms in any fixed dimension, all known running times suffer exponentially in the dimension. It is an open question whether this exponential dependence is improvable to a polynomial dependence. This paper proves that unless P=NP, the answer is no. This uncovers a "curse of dimensionality" for Wasserstein barycenter computation which does not occur for Optimal Transport computation. Moreover, our hardness results for computing Wasserstein barycenters extend to approximate computation, to seemingly simple cases of the problem, and to averaging probability distributions in other Optimal Transport metrics. to appear in SIAM Journal on Mathematics of Data Science (SIMODS) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|