The Gromov-Wasserstein (GW) distance quantifies dissimilarity between metric measure spaces and provides a meaningful figure of merit for applications involving heterogeneous data. While computational aspects of the GW distance have been widely studied, a strong duality theory and fundamental statistical questions concerning empirical convergence rates remained obscure. This work closes these gaps for the $(2,2)$-GW distance (namely, with quadratic cost) over Euclidean spaces of different dimensions $d_x$ and $d_y$. We consider both the standard GW and the entropic GW (EGW) distances, derive their dual forms, and use them to analyze expected empirical convergence rates. The resulting rates are $n^{-2/\max\{d_x,d_y,4\}}$ (up to a log factor when $\max\{d_x,d_y\}=4$) and $n^{-1/2}$ for the two-sample GW and EGW problems, respectively, which matches the corresponding rates for standard and entropic optimal transport distances. We also study stability of EGW in the entropic regularization parameter and establish approximation and continuity results for the cost and optimal couplings. Lastly, the duality is leveraged to shed new light on the open problem of the one-dimensional GW distance between uniform distributions on $n$ points, illuminating why the identity and anti-identity permutations may not be optimal. Our results serve as a first step towards a comprehensive statistical theory as well as computational advancements for GW distances, based on the discovered dual formulation.


翻译:Gromov-Wasserstein (GW) 距离量化度量测度空间的不相似性,适用于涉及异构数据的应用,并为此提供有意义的性能指标。虽然 GW 距离的计算方面已经广泛研究,但其强对偶理论和关于经验收敛速度的基本统计问题仍然模糊不清。本文针对不同维度 d_x 和 d_y 的欧几里得空间中的 $(2,2)$-GW 距离(即具有二次成本), 分别考虑标准 GW 和熵正则化 GW (EGW) 距离,导出它们的对偶形式,并使用它们分析预期的经验收敛速度。对于两个样本的 GW 和 EGW 问题,所得到的收敛速度为 $n^{-2/\max\{d_x,d_y,4\}}$ (当 $\max \{d_x,d_y\}=4$ 时带有对数因子) 和 $n^{-1/2}$,这与标准和熵正则化最优运输距离的相应速率相匹配。我们还研究了 EGW 距离在熵正则化参数中的稳定性,并为成本和最优匹配提供了逼近性和连续性结果。最后,对偶性被用来揭示一维均匀分布之间 GW 距离的开放问题,阐明了为什么恒等和反恒等排列可能不是最优的。我们的结果是迈向全面的统计理论和基于发现的对偶公式的计算进步的第一步。

1
下载
关闭预览

相关内容

在数学,统计学和计算机科学中,尤其是在机器学习和逆问题中,正则化是添加信息以解决不适定问题或防止过度拟合的过程。 正则化适用于不适定的优化问题中的目标函数。
【硬核书】稀疏多项式优化:理论与实践,220页pdf
专知会员服务
66+阅读 · 2022年9月30日
【2022新书】谱图理论,Spectral Graph Theory,100页pdf
专知会员服务
74+阅读 · 2022年4月15日
【硬核书】树与网络上的概率,716页pdf
专知会员服务
71+阅读 · 2021年12月8日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
61+阅读 · 2020年3月4日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【论文笔记】ICLR 2018 Wasserstein自编码器
专知
28+阅读 · 2018年6月29日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2023年5月17日
VIP会员
相关资讯
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
灾难性遗忘问题新视角:迁移-干扰平衡
CreateAMind
17+阅读 · 2019年7月6日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
【论文笔记】ICLR 2018 Wasserstein自编码器
专知
28+阅读 · 2018年6月29日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
1+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员