Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics

Motivation

• Known: MMD 기반 two-sample test는 kernel 선택과 permutation testing을 통해 널리 사용되어 왔으며, 표본 크기가 동일할 때는 MMD estimator가 U-statistic으로 표현되어 잘 확립된 U-statistics의 asymptotic theory(Hoeffding, 1948; Lee, 2019)를 그대로 적용할 수 있었다.
• Gap: 그러나 실제 응용에서는 두 분포로부터의 표본 크기가 다른 경우가 흔한데, 이 경우 MMD estimator는 더 이상 U-statistic이 아니어서 기존 이론이 적용되지 않으며, 기존 방법(Liu et al., 2020)은 동일 크기로 subsampling하여 데이터를 낭비하는 문제가 있었고, cross-MMD(Shekhar et al., 2023) 이론은 표본 크기 제약이 없지만 kernel 선택 방법을 제공하지 않는다.
• Why: 불균등 표본 크기를 다루는 이론적 틀이 없으면 실무자들은 귀중한 데이터를 버려야 하며 이는 검정력을 불필요하게 저하시키므로, 데이터를 모두 보존하면서도 이론적으로 엄밀한 검정 절차를 구축하는 것이 실용적으로나 통계학적으로나 중요하다.
• Approach: Hoeffding의 generalized U-statistics 이론을 확장하여 unequal sample size regime(비례 관계에 제약되지 않는 경우 포함)에서도 성립하는 일반적 결과를 도출하고, 이를 usual MMD estimator(식 (1))에 적용하여 asymptotic distribution과 variance를 특성화한다.

Achievement

Figure 1. Comparison of RE and RR when training on 1000 sam-

1. Generalized U-statistics 이론 확장: 기존에 제한적으로만 다뤄지던(특히 proportional regime에 국한된) generalized U-statistics의 asymptotic distribution 이론을 비례하지 않는 불균등 표본 크기 상황까지 확장하였다.
2. MMD estimator의 asymptotic 특성화: 귀무가설과 대립가설 하에서 unequal sample sizes를 갖는 usual \\(\\widehat{\\mathrm{MMD}}^2\\) estimator의 asymptotic distribution을 새롭게 규명하였다.
3. Kernel 선택을 위한 새로운 power 최적화 기준: 불균등 표본 크기 환경에서 MMD test의 검정력을 최대화하는 kernel을 선택하기 위한 criterion을 제시하여, 데이터를 subsampling 없이 모두 활용 가능하게 하였다.
4. Variance의 더 깔끔한 특성화 및 오개념 정정: MMD estimator의 variance에 대해 기존 문헌보다 명확한 특성화를 제공하고, MMD가 0이 아니어도 degenerate estimator가 될 수 있는 경우를 구성적으로 제시함과 동시에, 일반적인 상황에서는 그런 일이 일어나지 않음을 증명하여 대립가설 하 MMD에 대한 문헌상의 흔한 오해를 정정하였다.
5. 기존 이론과의 통합: 표본 크기가 동일할 경우 제안된 일반화된 검정 절차가 기존 U-statistic 기반 접근법으로 정확히 환원됨을 보여, 이를 기존 프레임워크의 자연스러운 확장으로 자리매김시켰다.

How

Figure 2. Histograms of n \

• Hilbert-Schmidt operator와 kernel mean embedding, covariance operator(\\(C_P\\), \\(\\mu_P\\))의 기존 이론(Setting A)을 기반으로 시작.
• U-statistic의 order-two variance decomposition(Proposition 2.5, Hoeffding decomposition 형태)을 generalized U-statistics(불균등 표본, 서로 다른 kernel 함수 h를 갖는 경우)로 확장.
• 확장된 이론을 usual unbiased \\(\\widehat{\\mathrm{MMD}}^2\\) estimator(식 (1))에 적용하여 asymptotic normal distribution(대립가설 하)과 degenerate U-statistic의 극한 분포(귀무가설 하, MMD=0인 경우)를 도출.
• Variance 표현을 정리하고, 이를 permutation testing 및 kernel 선택을 위한 power criterion 설계에 활용.
• MMD estimator와 대안적 estimator \\(\\widehat{\\mathrm{MMD}}^2_U\\) 간 차이를 McDiarmid's inequality로 고확률 bound(Theorem 2.3)하여 두 추정량의 asymptotic 동등성을 정당화.
• degenerate이면서 MMD≠0인 반례를 명시적으로 구성하고, 이러한 현상이 일반적인 상황(예: 흔히 사용되는 kernel 조건 하)에서는 발생하지 않음을 증명.
• 시뮬레이션(히스토그램, Figure 2, 3)을 통해 이론적으로 유도된 asymptotic distribution과 실제 통계량의 분포를 비교하고, Figure 1을 통해 제안 방법(RE)과 기존 subsampling 접근(RR)의 성능을 비교.

Originality

• 기존에 이론적으로 덜 발전되어 있던 generalized U-statistics의 asymptotic theory를 proportional regime을 넘어서는 일반적 불균등 표본 크기 상황까지 확장한 점이 핵심적인 이론적 기여이다.
• MMD estimator가 generalized U-statistic이라는 관찰(Kim et al., 2022)은 기존에 존재했으나, 이를 실제로 활용해 asymptotic distribution과 power-optimal kernel selection criterion을 도출한 것은 이 논문이 처음이다.
• MMD≠0이면서 degenerate estimator가 되는 반례를 구성한 것은 해당 분야의 통념(zero MMD가 degeneracy와 동치라는 오해)을 정정하는 독창적 이론적 발견이다.

Limitation & Further Study

• 발췌된 본문에서는 이론 전개(Theorem, Proposition)의 상당 부분이 Preliminaries 단계에 머물러 있어, 제안된 power 최적화 criterion의 구체적 형태와 실제 알고리즘적 절차, 그리고 이를 뒷받침하는 실험적 검증(Figure 1-3)의 세부 내용이 충분히 드러나지 않는다.
• degenerate하지만 MMD≠0인 경우가 "common situations"에서는 발생하지 않는다고 주장하지만, 이 "common situations"의 정확한 조건 범위가 실제 응용에서 얼마나 넓은지에 대한 논의가 제한적일 수 있다.
• 후속 연구로는 deep kernel 학습이나 고차원 데이터에서의 실제 성능 검증, 그리고 cross-MMD 등 대안적 estimator와의 정량적 비교가 필요할 것으로 보인다.

Evaluation

총평: 불균등 표본 크기라는 실용적이지만 오랫동안 미해결된 문제를 generalized U-statistics 이론 확장을 통해 엄밀하게 해결하고, 흥미로운 부수적 이론적 발견(비영 MMD에서의 degeneracy)까지 제공하는 탄탄한 이론 논문이다.