Wasserstein 거리 추정을 위한 계산-통계적 실행 시간 최적화

제곱 Wasserstein 거리 (Squared Wasserstein distance)는 확률 분포 간의 불일치를 측정하기 위해 자주 사용되는 도구입니다. 이 거리는 일반적으로 두 개의 기저 무작위 샘플로부터 얻은 크기 $n$의 경험적 측도 (empirical measures) 사이에서 계산됩니다. 불행히도, 저차원 유클리드 공간 문제 $\left( d \in {2,3} \right)$에서도 근사적 또는 정확한 정밀도 보장을 갖는 Wasserstein 거리 계산 알고리즘은 $n$과 원하는 정밀도의 함수로서 실행 시간 (runtime)이 나쁘게 확장됩니다. 이에 대응하여, 우리는 샘플로부터 잠재적으로 매끄러운 측도 (smooth measures) 사이의 Wasserstein 거리를 샘플링에 대한 기대값 측면에서 $\epsilon$-가산 오차 ($\epsilon$-additive error) 이내로 추정하는 것을 목표로 하는 계산-통계적 실행 시간 (computational-statistical runtime)을 고려합니다. 우리는 샘플을 수집하는 데 $O(1)$의 계산 비용을 허용합니다. 이를 위해, 우리는 샘플의 정규 직교 그리드 스케치 (regular cartesian grid sketch)를 도입하는 샘플-스케치-해결 (Sample-Sketch-Solve) 패러다임을 개발합니다. 우리는 (특히 $\alpha$-Hölder 매끄러운 분포 하에서) 이것이 점근적 오차 (asymptotic error)를 증가시키지 않으면서 데이터를 압축할 수 있으며, 더 빠른 정확한 알고리즘을 가능하게 하는 구조를 정규화함을 보여줍니다. 궁극적으로, 우리는 $(0,1)^{d}$ 상의 $0 < \alpha < 1$ Hölder 매끄러운 분포 $P,Q$에 대해 $\epsilon$ 오차 이내로 $W_2^2(P,Q)$를 $\epsilon^{-\max(2,\frac{d+1+o(1)}{1+\alpha})}$ 시간 내에 근사합니다. 이는 $d=2$이고 $\alpha > 1/2$일 때 최적의 $\Theta(\epsilon^{-2})$를 나타내며, $d=3$일 때 $\alpha \to 1$로 갈수록 거의 최적(nearly optimal)입니다.