Note on computational complexity of the Gromov-Wasserstein distance
This addresses a computational bottleneck for researchers in optimal transport and machine learning, but it is incremental as it clarifies known difficulties without proposing a new solution.
The paper tackled the computational complexity of the Gromov-Wasserstein distance by analyzing its optimization problem, showing it is non-convex and quadratic for any input data, and provided explicit examples to illustrate this non-convexity.
This note addresses computational difficulty of the Gromov-Wasserstein distance frequently mentioned in the literature. We provide details on the structure of the Gromov-Wasserstein distance optimization problem that show its non-convex quadratic nature for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.