Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances
Statistical, Robustness, and Computational Guarantees for Sliced Wasserstein Distances
复制标题
DOI：
10.48550/arxiv.2210.09160
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Sloan Nietert;R. Sadhu;Ziv Goldfeld;Kengo Kato
中科院分区：
文献类型：
--
作者：
Sloan Nietert;R. Sadhu;Ziv Goldfeld;Kengo Kato
切片Wasserstein距离保留了经典Wasserstein距离的特性，同时在高维的计算和估计中更具可扩展性。本工作的目标是从三个关键方面量化这种可扩展性：(i)经验收敛率；（ii）对数据污染的稳健性；（三）高效的计算方法。对于经验收敛，我们推导出具有显式依赖于维度的常数的快速速率，服从于总体分布的对数凹性。对于鲁棒性，我们描述了最小最大最优，无维鲁棒估计风险，并证明了鲁棒切片1-Wasserstein估计与鲁棒均值估计之间的等价性。这使得提升统计和算法保证可用于后者的切片1-Wasserstein设置。在计算方面，我们分析了平均切片距离的蒙特卡罗估计，证明了更大的维度可以导致数值积分误差的更快收敛。对于最大切片距离，我们重点研究了在实践中经常使用的基于子梯度的局部优化算法，尽管没有正式的保证，并为其建立了一个$O(\epsilon^{-4})$的计算复杂度界。我们的理论得到了数值实验的验证，这为可扩展性问题提供了一个全面的定量描述。
Sliced Wasserstein distances preserve properties of classic Wasserstein distances while being more scalable for computation and estimation in high dimensions. The goal of this work is to quantify this scalability from three key aspects: (i) empirical convergence rates; (ii) robustness to data contamination; and (iii) efficient computational methods. For empirical convergence, we derive fast rates with explicit dependence of constants on dimension, subject to log-concavity of the population distributions. For robustness, we characterize minimax optimal, dimension-free robust estimation risks, and show an equivalence between robust sliced 1-Wasserstein estimation and robust mean estimation. This enables lifting statistical and algorithmic guarantees available for the latter to the sliced 1-Wasserstein setting. Moving on to computational aspects, we analyze the Monte Carlo estimator for the average-sliced distance, demonstrating that larger dimension can result in faster convergence of the numerical integration error. For the max-sliced distance, we focus on a subgradient-based local optimization algorithm that is frequently used in practice, albeit without formal guarantees, and establish an $O(\epsilon^{-4})$ computational complexity bound for it. Our theory is validated by numerical experiments, which altogether provide a comprehensive quantitative account of the scalability question.