@inproceedings{
rioux2023semidiscrete,
title={Semi-discrete Gromov-Wasserstein distances: Existence of Gromov-Monge Maps and Statistical Theory},
author={Gabriel Rioux and Ziv Goldfeld and Kengo Kato},
booktitle={NeurIPS 2023 Workshop Optimal Transport and Machine Learning},
year={2023},
url={https://openreview.net/forum?id=mCNl1EMAfH}
}
The Gromov-Wasserstein (GW) distance serves as a discrepancy measure between metric measure spaces. Despite recent theoretical developments, its  structural properties, such as existence of optimal maps, remain largely unaccounted for. In this work, we analyze the semi-discrete regime  for the GW problem wherein one measure is finitely supported. Notably, we derive a primitive condition which guarantees the existence of optimal maps. This condition also enables us to derive the asymptotic distribution of the empirical semi-discrete GW distance under proper centering and scaling. As a complement to this asymptotic result, we also derive expected empirical convergence rates. As is the case with the standard Wasserstein distance, the rate we derive in the semi-discrete GW case, $n^{-\frac{1}{2}}$, is dimension-independent which is in stark contrast to the curse of dimensionality  rate obtained in general.
Semi-discrete Gromov-Wasserstein distances: Existence of Gromov-Monge Maps and Statistical Theory
Gabriel Rioux Ziv Goldfeld Kengo Kato