Minimax-Optimal Kernel Two-sample Testing in Sub-quadratic Time

Motivation

• Known: MMD 기반 kernel two-sample test는 smooth alternative에 대해 minimax-optimal한 검정력을 가진다는 것이 알려져 있으나, 표준 unbiased MMD 추정량은 pooled sample size N에 대해 Θ(N^2) 쌍의 kernel 평가가 필요해 계산 비용이 크다.
• Gap: 기존의 subsampling 기반 subquadratic MMD test들은 검정력을 희생하거나, quadratic-time test와 동등한 minimax optimality를 달성하려면 추가적인 분포 가정(tail/kernel regime 등)을 필요로 하며, random Fourier features나 kernel thinning 등 일부 예외도 제한된 조건에서만 subquadratic minimax optimality를 보인다는 근본적 한계가 있었다.
• Why: 최소한의 분포 가정 하에서 quadratic-time MMD test와 동일한 minimax rate-optimal power를 유지하면서 실제로 subquadratic time에 통계량을 계산할 수 있는지는 kernel two-sample testing 분야의 근본적인 미해결 문제였으며, 이를 해결하면 대규모 데이터에 대해 강력한 통계적 보장을 유지한 채 실용적인 계산 효율을 얻을 수 있다.
• Approach: MMD 통계량을 kernel lower-triangular sum으로 재표현한 뒤, orthantwise separable kernel(예: product Laplace kernel)에 대해서는 Fenwick tree(및 그 다차원 변형)를 이용한 fast prefix-sum query로 정확히 계산하고, exactly separable하지 않은 characteristic kernel(Gaussian, inverse multiquadric 등)에는 exponentially convergent trapezoidal rule에 기반한 almost separable 근사를 도입하여 통계적으로 무해한 근사 오차로 subquadratic 계산을 가능하게 한다.

Achievement

Figure 1. MMD permutation two sample testing experiments. The left (right) half uses the Laplace (Gaussian) kernel. The

1. Fast exact algorithm: orthantwise separable kernel(예: product Laplace kernel)에 대해 동일한 quadratic MMD statistic을 O((2 log N)^d N) 시간에 계산하는 정확한 알고리즘을 개발함.
2. Approximation framework: Gaussian, inverse multiquadric kernel은 exponentially accurate separable approximation을 가지며, half-integer Matérn과 Laplace kernel은 exact finite separable sum으로 표현됨을 증명함.
3. Minimax-optimal permutation test: 근사된 MMD permutation test가 non-asymptotic level α를 만족하고, Sobolev ball 상의 L2-separated alternative 및 MMD-separated alternative 모두에 대해 고정 차원에서 near-linear time으로 minimax-rate optimality를 달성함을 증명함.
4. 성장하는 차원(regime) 분석: d = o(log N/log log N)에서 동일 구현이 subquadratic time을 유지함을 보이고, 신호가 저차원 latent subspace에 있을 때 PCA와 결합 가능함을 보임.

How

Figure 2. MMD permutation two sample testing experiments with dimension reduction via PCA.

• MMD 추정량을 KXX, KYY, KXY 세 개의 kernel lower-triangular sum으로 분해
• Definition 3.1의 orthantwise separable kernel에 대해 Fenwick tree(및 다차원 변형, Mishra 2013; Wang et al. 2021)를 이용해 prefix-sum query로 lower-triangular sum을 O((2 log N)^d N) 시간·메모리에 계산
• exactly separable하지 않은 kernel(Gaussian, inverse multiquadric)에 대해 실수축 위 analytic integrand에 대한 exponentially convergent trapezoidal rule(Trefethen & Weideman, 2014)을 적용해 almost separable approximation을 구성하고 polylogarithmic overhead만 추가되도록 설계
• 근사 오차가 검정 통계량의 uniform separation rate에 영향을 주지 않을 정도로 충분히 작게 통제됨을 이론적으로 증명(비대칭 level-α permutation test 보장 포함)
• minimax 하한과 상한을 d가 n과 함께 커지는 growing-dimension regime으로 확장하여, d=Ω(log N)일 때 rate가 0으로 가지 않고, d=o(log N/log log N)일 때 하한·상한이 polylogarithmic factor까지 일치함을 규명
• 신호가 저차원 subspace에 있을 때 PCA와 결합하는 dimensionality reduction 방법 제시
• 합성 데이터 실험(Figure 1, Figure 2)을 통해 검정력과 계산 효율을 검증

Originality

• MMD 계산을 kernel lower-triangular sum으로 보는 관점(Bodenham & Kawahara, 2023의 1차원 아이디어)을 다차원 Fenwick tree 구조로 확장하여 정확한 subquadratic 알고리즘을 구축
• fast kernel density estimation과 수치해석의 exponentially convergent trapezoidal rule을 결합해 characteristic kernel의 almost separable approximation을 도입한 것이 독창적
• 기존 연구들이 검정력과 계산 효율 사이에서 트레이드오프를 감수하거나 제한적 가정을 요구했던 것과 달리, 최소 분포 가정 하에서 quadratic-time MMD test와 동등한 minimax rate optimality를 subquadratic time에 달성함을 보인 것이 핵심 기여
• 고정 차원뿐 아니라 growing-dimension regime(d = o(log N/log log N))까지 minimax 하한·상한을 확장하고 이 영역에서 알고리즘이 여전히 subquadratic함을 보인 점도 새로움

Limitation & Further Study

• 제안된 알고리즘의 시간복잡도 O((2 log N)^d N)는 차원 d가 커질수록 지수적으로 증가하므로, d = Ω(log N) 영역에서는 실질적 이득이 사라지며 이는 minimax rate 자체가 0으로 수렴하지 않는다는 이론적 한계와 맞물려 있음
• Gaussian, inverse multiquadric 등 일부 kernel에 대해서만 exponentially accurate separable approximation이 증명되어 있어, 더 일반적인 characteristic kernel 클래스로의 확장 가능성은 추가 연구가 필요함
• 실험이 합성 데이터 위주로 제시되어 있어(Figure 1, 2), 실제 고차원 실데이터에서의 성능 및 PCA 결합 시 신호 손실에 대한 실증적 검증이 제한적임
• 저차원 latent subspace 가정이 성립하지 않는 고차원 실제 응용에서의 실용성 검증이 후속 연구로 필요함

Evaluation

총평: Fenwick tree와 수치해석적 근사를 결합해 kernel two-sample test의 계산 효율과 minimax-optimal 검정력을 동시에 달성한 이론적으로 탄탄하고 참신한 연구이나, 고차원 영역에서의 실질적 한계와 실데이터 검증의 부족이 아쉬운 점이다.