技術的概要：ワルシュタイン距離推定における計算統計的実行時間の最適化

問題定義

二乗ワルシュタイン距離 $W_2^2(P, Q)$ は、$\mathbb{R}^d$ における確率分布 $P$ と $Q$ の間の不一致を測定するための標準的な指標である。実用的なデータ分析および機械学習タスク（パラメータ推定、仮説検定など）において、これらの分布は未知であり、サイズ $n$ の経験的サンプル $\hat{P}_n$ および $\hat{Q}_n$ から推定されなければならない。

既存のアプローチは根本的なボトルネックに直面している：$W_2^2(\hat{P}_n, \hat{Q}_n)$ を正確に、または加法的誤差 $\epsilon$ で計算するには、通常、$n$ および $\epsilon$ に対して性能が劣悪にスケールする実行時間（例：$O(n^2/\epsilon^2)$ またはそれ以上）が必要となる。一方、経験的測度の収束率に依存する純粋な統計的アプローチは、結果として生じる大規模データセット上で最適輸送問題を解く計算コストをしばしば無視している。

本論文は、**計算統計的実行時間（CSR）**に対処するものである。目標は、サンプル収集のコスト（サンプルあたり $O(1)$ と仮定）と計算コストの両方を考慮した実行時間 $O(f(\epsilon))$ において、期待値として $\epsilon$ 加法的誤差の範囲内で $W_2^2(P, Q)$ を推定するランダム化アルゴリズムを設計することである。著者らは、目標精度は経験的測度を真実として扱うのではなく、サンプルサイズによって引き起こされる統計的誤差と整合するべきであると主張する。

手法：サンプリング・スケッチ・ソルブパラダイム

著者らは、特に領域 $(0, 1)^d$ 上のホルダー滑らかな密度を持つ分布に対して高速な CSR を達成するための三段階パラダイムを提案する：

1. サンプリング（Sample）: $P$ および $Q$ から $n$ 個のランダムサンプルを収集し、経験的測度 $\hat{P}_n$ および $\hat{Q}_n$ を形成する。
2. スケッチ（Sketch）: これらのサンプルを、セル幅 $h = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$ の規則的な直交格子 $G_h$ 上に写像する。格子セル内のすべての質量はセルの中心に集約される。これにより、圧縮された離散測度 $G_h\#\hat{P}_n$ および $G_h\#\hat{Q}_n$ が生成される。
3. ソルブ（Solve）: 規則的な格子構造を利用する専用アルゴリズムを用いて、スケッチされた測度間の正確な二乗ワルシュタイン距離を計算する。

主要な技術的要素

1. 格子ベースの離散化誤差 bound（第 2 節）

本論文は、質量を格子中心に集約することによって導入される近似誤差に関する新しい上界を確立する。

• 仮定: $P$ および $Q$ は $\alpha$-ホルダー滑らかな密度を持ち（$0 < \alpha < 1$）、ゼロおよび無限大から離れて有界である。
• 結果: 著者らは、$|W_2^2(G_h\#P, G_h\#Q) - W_2^2(P, Q)| \leq K h^{1+\alpha}$ を証明する。
• メカニズム: $O(h)$ を与える標準的な三角不等式の議論とは異なり、この結果はブレニエ写像（最適輸送写像）の正則性に基づく新しいカップリング議論を利用する。コリンズおよびトン [2025] によるブレニエ写像の全球的ホルダー連続性に関する最近の結果を活用することで、著者らは一次誤差項が（中点則と同様に）相殺されることを示し、より tight な $O(h^{1+\alpha})$ の bound を得る。
• 非滑らかな場合: 滑らかさの仮定がない分布の場合、bound は標準的な三角不等式の議論と一致する $O(h)$ に戻る。

2. 規則的格子における効率的な正確計算（第 3 節）

データが規則的格子にスケッチされると、問題構造により、はるかに高速な正確計算が可能となる。

• 構造: スケッチされた測度は、軸あたり $L$ 分割の格子上でサポートされ、各原子の重みは $1/n$ の倍数である。基底コスト（二乗ユークリッド距離）は次元ごとに分離可能である。
• 還元: 著者らは、分離可能なコストを持つ $d$ 次元ヒストグラム間の最適輸送問題を、$(d+1)$-部グラフ上の最小費用流問題に変換するオーリッキオら [2018] による還元を利用する。
• アルゴリズム: 整数の需要、容量、コストを確保するために問題をスケーリングし、ヴァン・デン・ブランドら [2023] の決定論的正確最小費用流アルゴリズムを適用する。
• 複雑性: スケッチ上の正確計算は $\tilde{O}(L^{d+1+o(1)})$ 時間で実行される。

3. 統合：CSR アルゴリズム（第 4 節）

最終的なアルゴリズムは、統計的サンプリング、格子スケッチ、および高速ソルバーを組み合わせる。

• サンプルサイズ: 統計的誤差と離散化誤差のバランスを取るためにサンプル数 $n$ が選択され、通常 $n = \tilde{O}(\epsilon^{-\max(2, d/2)})$ である。
• 格子分解能: 格子サイズは $L = \Theta(\epsilon^{-\frac{1}{1+\alpha}})$ に設定される。
• 総実行時間: 結合された実行時間はソルバーステップによって支配され、以下の計算統計的実行時間を生み出す：
  $$\tilde{O}\left(\epsilon^{-\max\left(2, \frac{d+1+o(1)}{1+\alpha}\right)}\right)$$

主要な結果と貢献

1. 滑らかな分布に対する実行時間の改善

本論文は、$\alpha$-ホルダー滑らかな分布に対して、特定の領域において CSR が統計的下界 $\Omega(\epsilon^{-2})$ とほぼ一致し、ほぼ最適であることを示す：

• 次元 $d=2$: $\alpha > 1/2$ の場合、アルゴリズムは $\tilde{O}(\epsilon^{-2})$ を達成する。これは最適な統計的レートと一致し、計算コストが十分なサンプルを収集するコストを超えないことを意味する。
• 次元 $d=3$: $\alpha \to 1$（リプシッツ滑らかさ）に近づくと、実行時間は $\tilde{O}(\epsilon^{-2})$ に近づく。一般的な $0 < \alpha < 1$ の場合、実行時間は $\tilde{O}(\epsilon^{-\frac{4}{1+\alpha}})$ である。
• 一般次元 $d$: 実行時間は $\tilde{O}(\epsilon^{-\max(2, \frac{d+1}{1+\alpha})})$ である。

2. 先行研究との比較

著者らは、表 2 で既存の方法との結果を比較する：

• 経験的プラグイン + ラーンら [2019]: $d=2$ で $\tilde{O}(\epsilon^{-4})$、$d=3$ で $\tilde{O}(\epsilon^{-5})$ を達成。
• エントロピー OT / Sinkhorn（チザトら [2020]）: $d=2$ および $d=3$ で $\tilde{O}(\epsilon^{-6})$ を達成。
• 本研究: $d=2$ で（$\alpha > 1/2$ の場合）$\tilde{O}(\epsilon^{-2})$ を達成し、$d=3$ で（$\alpha \to 1$ として）$\tilde{O}(\epsilon^{-2})$ を達成。

3. 非滑らかな場合

滑らかさの仮定がない場合（$\alpha \to 0$）、この方法は $\tilde{O}(\epsilon^{-\max(2, d+1)})$ の CSR を生む。$d=2$ の場合、これは $\tilde{O}(\epsilon^{-3})$ であり、$d=3$ の場合、$\tilde{O}(\epsilon^{-4})$ である。

意義と主張

本論文の主要な貢献は、統計的推定誤差と輸送問題の計算複雑性を成功裡に分離するサンプリング・スケッチ・ソルブパラダイムであると主張されている。

• 誤差なしの圧縮: 著者らは、基礎となる分布が滑らかであれば、サンプルを規則的な格子に写像することで漸近的誤差を増加させることなくデータを圧縮できることを示す。
• 速度のための正則化: 格子構造は問題を正則化し、一般的な離散点集合に対しては扱いが困難な高速な正確流アルゴリズムの使用を可能にする。
• 最適性: 本論文は、低次元（$d=2, 3$）の十分に滑らかな分布に対して、計算的に $\epsilon^{-2}$ の最適な統計的レートを達成することが可能であると論じる。これは、ワルシュタイン距離の計算が、所望の精度に対して本質的に超線形または超二次の実行時間を必要とするという考え方に挑戦するものである。

著者らは明示的に、結果が $P$ および $Q$ が有界な領域（具体的には $(0, 1)^d$）でサポートされ、ホルダー滑らかな密度を持つという仮定に依存していると述べている。これらの結果が修正なしに非滑らかな分布や無界な領域に拡張されることを主張するものではない。意義は、統計的推定理論と計算的最適輸送の間のギャップを埋め、現実的な滑らかさの仮定の下では「計算ボトルネック」を実質的に除去できることを実証することにある。