技術要約：効率的かつ安定的な多次元コルモゴロフ・スミルノフ距離

問題提起

本論文は、単変量分布の比較における基本的な非パラメトリック指標であるコルモゴロフ・スミルノフ（KS）距離を、多次元設定（$d > 1$）へと拡張する際の課題に対処している。単変量のKS距離はよく理解されており、安定かつ効率的に計算可能であるが、既存の高次元への拡張には重大な制限がある：

1. 不安定性： 「quad-KS」（データ点によって定義される象限に探索空間を制限するもの）のような一般的なヒューリスティックは、不安定であることが示されている。すなわち、データ点の追加や削除によって距離が劇的に変化するため、厳密なサンプル複雑性の境界を定めることができない。
2. 計算の困難性： すべての可能な範囲にわたる多次元KS距離の正確な計算は、計算コストが非常に高い（素朴には $O(n^d)$）。また、既存の置換ベースのテストの多くは、サンプルサイズに対して指数関数的な時間を必要とする。
3. 単位への敏感さ： 他の代替指標（例：ワッサースタイン距離、最大平均偏差）の多くは、ユークリッド地上距離に依存しているため、次元の単位やスケールの選択に敏感である。これは、次元ごとに物理単位が異なる場合（例：身長 vs 体重）に問題となる。

著者らは、**積分確率測度（IPM）**であり、単位の選択に不変で、証明可能な近似保証とともに効率的に計算可能な多次元KS距離（$dKS$）の定式化を提案している。

手法

1. 多次元KS（$dKS$）の定義

著者らは、$\mathbb{R}^d$ における2つの分布 $\mu$ と $\nu$ の間の距離を、直交する支配的長方形範囲における累積分布関数の最大差として定義する。
$$dKS(\mu, \nu) = \sup_{z \in \mathbb{R}^d} \left| \int_{x \preceq z} d\mu(x) - \int_{x \preceq z} d\nu(x) \right|$$
ここで、$x \preceq z$ は、$x$ のすべての座標が $z$ の対応する座標以下であることを示す。すべての $2^d$ 個の直交領域を考慮する以前の拡張（例：Peacockの手法）とは異なり、この定式化は単一の象限（支配的長方形）に焦点を当てている。著者らは、これが堅牢な指標として十分であると主張している。

2. 理論的特性

• 距離の性質： 本論文では、$dKS$ が確率測量の空間上で完全な距離（対称性、三角不等式、および強い同一性を満たす）であることを証明している。これは、擬距離（疑似距離）であったり、あるいは安定性に欠けたりするヒューリスティックなバリアントとは対照的である。
• サンプル複雑性： 範囲空間のVC次元理論を活用し、$n = O(\frac{1}{\epsilon^2}(d + \log(1/\delta)))$ 個のサンプルがあれば、確率 $1-\delta$ で誤差 $\epsilon$ 以内で距離を推定できることを確立している。この境界は次元 $d$ に対して線形である。

3. 計算アルゴリズム

論文では、次元 $d \le 4$ において、必要なサンプルサイズに対して近線形な**計算・統計的実行時間（CSR）**で、$dKS$の$\epsilon$-近似を計算するアルゴリズムを紹介している。

• $d=2$ の場合： 著者らはスケッチ手法（アルゴリズム2、dKS-Sketch）を提案している。点をソートし、$O((d/\epsilon)^d)$ サイズの層化グリッドを構築することで、アルゴリズムは問題をグリッド上での動的計画法へと還元する。
  • 実行時間： $O(n \log n + (d/\epsilon)^d)$。$d=2$ かつ $\epsilon \approx 1/\sqrt{n}$ の場合、これは $O(n \log n)$ となる。
• $d=3, 4$ の場合： 著者らは、問題を「重み付き長方形の最大深度の点を見つける問題」（クレーの測度問題の変種）へと還元する。
  • まず、低不一致彩色（Low-discrepancy colorings、補題2）を用いて、サンプルをより小さな $\epsilon$-近似集合へと圧縮する。
  • 次に、重み付き点の最大値を求めるためのChanのアルゴリズムを、$O(s^{d/2} \text{polylog}(s))$ 時間で適用する（ここで $s$ は圧縮されたサンプルサイズである）。
  • 実行時間： サンプル複雑性 $n_\epsilon$ に対して近線形である。具体的には、$d=3$ で $O(n \log^3 n)$、$d=4$ で $O(n \log^{21} n)$ となる。
• 困難性： 論文では、$d > 4$ において近線形な実行時間を達成することは、Max-Weight $k$-Clique 問題の解決における画期的な進展を意味するため、困難であると論じている。これは、細粒度計算量理論において広く困難とされる問題である。

4. 仮説検定

導出されたサンプル複雑性の境界と距離の特性を用いて、著者らはレベル-$\delta$ 二標本仮説検定を構築している。

• 計算された $dKS$が、サンプルサイズと信頼レベルから導出された閾値を超える場合に、帰無仮説（$\mu = \nu$）を棄却する。
• 極めて重要な点として、このテストはモンテカルロベースのテストとは異なり、漸近近似に頼ることなく、精密な有限サンプル保証を伴う第I種の誤り率を提供する。

主な結果

1. 安定性： 提案された $dKS$ 定式化は、samplingに対して安定している。「quad-KS」やその他の象限制限型のヒューリスティックとは異なる。著者らは、単一の点を追加することでquad-KSの計算結果が距離を倍増させる一方で、$dKS$ は安定性を保つという、病理的な例を構築している。
2. 効率性：
   • $d=2$： 単変量のケースと同等の効率である $O(n \log n)$ の実行時間を達成している。
   • $d=3, 4$： サンプル複雑性に対して近線形な実行時間を達成しており、これは従来の正確な手法の指数関数的または高多項式的なコストと比較して大幅な改善である。
3. 精度： 導出された仮説検定は、中程度の次元（$d \le 4$）における多次元分布に対する、精密で非漸近的、かつシミュレーションに基づかない最初のテストを提供している。
4. 実証的検証： $d=2$ のデータを用いた実験では、dKS-Sketch アルゴリズムは、同等の精度を維持しながら、ベースラインとなる正確なアルゴリズムよりも数桁高速であること（例：$n \approx 10^6$ において 4.2 時間 vs 0.2 秒）を示した。検出力の評価において、スケッチベースのテストは、置換ベースのベースラインが数時間から数日を要するのに対し、数秒で完全な統計的検出力を達成した。

意義と主張

本論文は、数学的な厳密さ（安定性、距離の性質、サンプル複雑性）と計算の実現可能性のバランスを取りながら、多次元へのコルモゴロフ・スミルノフ距離の「正しい拡張方法」を提供していると主張している。

• 理論的貢献： 一つの象限による定式化が、堅牢な距離として十分であることを確立し、この距離が低次元において効率的な近似アルゴリズムを許容することを証明した。
• 実用的影響： ユークリッド距離に基づく指標が失敗するような、異なる単位を持つ中程度の次元（例：2Dから4D）のデータに対して、非パラメトリックな二標本検定の適用を可能にする。
• 限界： 著者らは、$d > 4$ の場合、計算理論の主要な予想が解決されない限り、近線形な実行時間で解くことは困難である可能性が高いことを明記している。また、$d=3, 4$ のアルゴリズムはクレーの測度問題への複雑な還元に依存しており、$d=2$ の場合と比較して実用的な実装が困難である可能性があることも認めている。

本研究は、提案された $dKS$ を、中程度の次元における統計分析のための、より好ましい代替手段として位置づけている。