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

요약

본 논문은 확률 분포 간의 불일치를 측정하는 Squared Wasserstein 거리 계산의 비효율적인 실행 시간을 개선하기 위한 새로운 알고리즘을 제안합니다. 'Sample-Sketch-Solve' 패러다임을 통해 데이터를 압축하고 구조를 정규화함으로써, 특히 저차원 유클리드 공간에서 기존보다 훨씬 빠른 속도로 $\epsilon$-가산 오차 이내의 근사치를 계산할 수 있음을 증명했습니다.

핵심 포인트

• 기존 Wasserstein 거리 계산 알고리즘의 높은 시간 복잡도 문제를 해결하기 위한 계산-통계적 접근법 제시
• 정규 직교 그리드 스케치를 활용한 'Sample-Sketch-Solve' 패러다임 개발
• $\alpha$-Hölder 매끄러운 분포 하에서 점근적 오차 증가 없이 데이터 압축 가능
• $d=2, \alpha > 1/2$ 조건에서 최적의 $\Theta(\epsilon^{-2})$ 실행 시간 달성