Betting Across Kernels: Anytime-Valid Two-Sample Testing over Kernel Families

Motivation

• Known: MMD 기반 kernel two-sample test에서 fixed-n 세팅에서는 MMDAgg, MMD-Fuse 등 kernel bandwidth를 aggregation하는 방법이 이미 존재하며, sequential/anytime-valid 세팅에서는 Shekhar-Ramdas의 within-RKHS adaptive witness betting test가 하나의 고정된 kernel에 대해 최적의 witness 방향을 online으로 학습하는 방법으로 알려져 있다.
• Gap: 기존 anytime-valid kernel two-sample test들은 모두 단일 RKHS를 사전에 고정해야 하며, MMDAgg의 sequential 대응물 즉 연속적인 kernel family 전체에 대해 adaptive한 anytime-valid test는 문헌에 존재하지 않았다.
• Why: 실제 응용(예: LLM 감사, A/B 테스트, 분포 변화 모니터링)에서는 어떤 kernel이 두 분포를 가장 잘 분리할지 사전에 알 수 없는데, 잘못된 kernel 선택은 검정력 손실과 늦은 탐지로 이어지므로, kernel 선택 문제 자체를 데이터가 스스로 해결하게 하면서도 anytime-valid 보장을 유지하는 방법은 실용적, 이론적으로 중요하다.
• Approach: 각 kernel별로 Shekhar-Ramdas online betting e-process를 구성한 뒤 kernel family에 대한 prior π 하에서 method-of-mixtures로 평균 wealth를 취하는 outer aggregation을 결합하여, no-regret-kernel 현상을 갖는 anytime-valid 검정을 제안한다.

Achievement

1. no-regret-kernel 현상 실증: regime-uncertain stream에서 online mixture 검정이 사후에 최적 kernel을 아는 oracle보다 0.65배의 정지 시간으로 더 빠르게 결정을 내림을 보였다.
2. Tight stopping-time rate 증명: (log K + log(1/α) + C)/MMD^2_{k*} 형태의 정지 시간 상한(Theorem 3.2, 3.4, 3.6)과, 이 log K 비용이 정보이론적으로 불가피함을 보이는 matching lower bound(Theorem 4.2)를 제시했다.
3. Meta-theorem과 confidence sequence: 임의의 per-kernel non-negative supermartingale family에 대해 mixture 구성을 적용할 수 있는 meta-theorem을 제시하고, best-in-family divergence MMD^2_{k*}=sup_λ MMD^2_{k_λ}에 대한 최초의 time-uniform confidence sequence를 유도했으며, 이를 independence testing, goodness-of-fit(KSD), change-point detection으로 확장했다.
4. 실험적 검증: LLM auditing(18개 샘플로 cross-provider drift 탐지), A/B testing, direct scaling study를 통해 예측된 (log K + log(1/α))/MMD^2_{k*} 정지 시간 법칙과 연속 모니터링 하 정확한 Type-I 오류 통제(naive peeking z-test는 34% 오탐)를 확인했다.

How

• 각 kernel k_λ에 대해 Shekhar-Ramdas의 adaptive witness betting을 통해 wealth process W_t^(λ)를 구성(식 3)
• kernel family에 대한 확률측도(prior) π를 두고 W_t = ∫ W_t^(λ) dπ(λ) 형태의 method-of-mixtures aggregation으로 outer wealth process 정의(식 5)
• Tonelli 정리와 개별 kernel의 supermartingale 성질을 이용해 Wt가 non-negative supermartingale임을 증명하고 Ville's inequality로 anytime-valid함을 도출(Theorem 3.2)
• local kernel regularity 가정(Assumption 3.3, MMD continuity, uniform SR regret) 하에서 연속 prior에 대해 ϵ-net을 이용한 posterior concentration으로 정지 시간 상한을 도출
• 임의의 kernel family에 대한 e-process aggregation을 일반화하는 meta-theorem을 세우고 independence, goodness-of-fit, change-point testing에 적용
• bandpass(Gabor) kernel 구성을 이용해 log K 비용이 불가피함을 보이는 information-theoretic lower bound 증명
• LLM auditing, A/B testing, scaling study 등 사전 등록된(pre-registered) 예측을 실험으로 검증

Originality

• 기존 sequential kernel test들이 단일 RKHS 선택을 전제로 했던 것과 달리, kernel family 전체에 대한 online mixture를 통해 kernel 선택 자체를 데이터 기반으로 해결하는 최초의 anytime-valid 구성을 제시
• "no-regret-kernel phenomenon"이라는 새로운 현상을 정의하고, 이것이 post-hoc oracle보다 우월하다는 반직관적 결과를 이론과 실험 양쪽에서 입증
• log K 추가 비용에 대한 matching lower bound를 제시하여 상한이 tight함을 information-theoretic하게 증명한 점
• 단일 kernel 최적화가 아닌 best-in-family divergence MMD^2_{k*}에 대한 최초의 time-uniform confidence sequence 제시
• 임의의 supermartingale family에 적용 가능한 meta-theorem을 통해 독립성 검정, 적합도 검정, 변화점 검정으로 일반화한 통합적 프레임워크 제안

Limitation & Further Study

• 이론적 정지 시간 상한과 lower bound는 특정 정규성 가정(local kernel regularity, 균일 SR regret 등)에 의존하므로 실제 응용에서 이 가정들이 항상 성립하는지는 추가 검증이 필요함
• 실험이 LLM auditing 18개 샘플, A/B 테스트 등 상대적으로 제한된 시나리오에 국한되어 있어, 더 다양한 실제 배포 환경에서의 강건성 검증이 요구됨
• prior π의 선택이 성능에 미치는 영향(특히 연속 kernel family에서 ϵ-net 크기 Nϵ에 따른 burn-in 비용)에 대한 실무적 가이드라인이 더 필요함
• 향후 연구로 학습된 kernel family(learned kernel families)나 비정상(non-stationary) 스트림에서의 확장, 그리고 더 일반적인 witness-learning 알고리즘과의 결합이 가능할 것으로 보임

Evaluation

총평: anytime-valid kernel two-sample testing 분야에서 kernel 선택 문제를 우아하게 해결하면서도 이론적으로 tight한 rate와 lower bound를 함께 제시한 완성도 높은 연구로, no-regret-kernel 현상이라는 흥미로운 발견을 신뢰할 만한 이론과 사전 등록된 실험으로 뒷받침한 점이 인상적이다.