2025-11-14T20:13:11.521057

Minimax Optimal Kernel Two-Sample Tests with Random Features

Mukherjee, Sriperumbudur
Reproducing Kernel Hilbert Space (RKHS) embedding of probability distributions has proved to be an effective approach, via MMD (maximum mean discrepancy), for nonparametric hypothesis testing problems involving distributions defined over general (non-Euclidean) domains. While a substantial amount of work has been done on this topic, only recently have minimax optimal two-sample tests been constructed that incorporate, unlike MMD, both the mean element and a regularized version of the covariance operator. However, as with most kernel algorithms, the optimal test scales cubically in the sample size, limiting its applicability. In this paper, we propose a spectral-regularized two-sample test based on random Fourier feature (RFF) approximation and investigate the trade-offs between statistical optimality and computational efficiency. We show the proposed test to be minimax optimal if the approximation order of RFF (which depends on the smoothness of the likelihood ratio and the decay rate of the eigenvalues of the integral operator) is sufficiently large. We develop a practically implementable permutation-based version of the proposed test with a data-adaptive strategy for selecting the regularization parameter. Finally, through numerical experiments on simulated and benchmark datasets, we demonstrate that the proposed RFF-based test is computationally efficient and performs almost similarly (with a small drop in power) to the exact test.
academic

Minimax Optimal Kernel Two-Sample Tests with Random Features

基本信息

  • 论文ID: 2502.20755
  • 标题: Minimax Optimal Kernel Two-Sample Tests with Random Features
  • 作者: Soumya Mukherjee, Bharath K. Sriperumbudur (Pennsylvania State University)
  • 分类: math.ST cs.LG stat.ML stat.TH
  • 发表时间: October 17, 2025 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2502.20755

摘要

本文针对基于再生核希尔伯特空间(RKHS)嵌入的双样本检验问题，提出了一种基于随机傅里叶特征(RFF)近似的谱正则化双样本检验方法。该方法在保持统计最优性的同时显著降低了计算复杂度，从立方级别降低到接近线性，并提供了完全数据驱动的实际可实现版本。

研究背景与动机

核心问题

双样本检验是统计学中的基本问题，旨在通过分析两个随机样本来判断其来源的概率分布是否相等。传统的参数和非参数检验方法在处理高维数据或非欧几里得域上的分布时面临显著局限性。

现有方法局限性

  1. MMD检验的次优性：虽然最大均值差异(MMD)检验广泛应用，但它缺乏minimax最优性，仅考虑均值嵌入而忽略协方差算子信息
  2. 谱正则化方法的计算瓶颈：最近提出的谱正则化MMD检验虽然达到了minimax最优性，但计算复杂度为O(n³)，限制了其在大规模数据上的应用
  3. 参数选择困难：正则化参数的选择依赖于未知的分布特性，缺乏数据驱动的自适应策略

研究动机

本文旨在通过随机傅里叶特征近似技术，在保持统计最优性的前提下显著提升谱正则化双样本检验的计算效率，并开发实际可用的自适应版本。

核心贡献

  1. 计算高效且统计最优的检验：提出基于RFF的谱正则化双样本检验，将计算复杂度从O(n³)降低到O(nl²+nld)，同时在充分条件下保持minimax最优性
  2. 理论保证：建立了RFF近似阶数与统计最优性之间的理论联系，证明了在特征数量l满足特定条件时检验的minimax最优性
  3. 实用的自适应版本：开发了基于置换检验的完全数据驱动版本，包含正则化参数和核函数的自适应选择策略
  4. 全面的实验验证：通过合成数据和基准数据集验证了方法的有效性，展示了计算效率与统计性能的良好权衡

方法详解

任务定义

给定来自分布P和Q的独立样本X₁:N和Y₁:M，检验假设H₀: P = Q vs H₁: P ≠ Q。

核心方法架构

1. 谱正则化框架

对于核函数K，定义谱正则化差异：

ηλ(P,Q) = 4⟨Tgλ(T)u, u⟩_{L²(R)}

其中T是积分算子，u = dP/dR - 1是似然比偏差，gλ是正则化函数。

2. 随机傅里叶特征近似

对于形式为K(x,y) = ∫φ(x,θ)φ(y,θ)dΞ(θ)的核函数，构造近似核：

Kₗ(x,y) = (1/l)∑ᵢ₌₁ˡ φ(x,θᵢ)φ(y,θᵢ)

3. 近似检验统计量

基于近似核Kₗ构造检验统计量：

η̂λ,l = (1/[n(n-1)m(m-1)]) ∑ᵢ≠ⱼ ∑ᵢ'≠ⱼ' t(Xᵢ,Xⱼ,Yᵢ',Yⱼ')

其中t函数涉及正则化协方差算子的平方根。

技术创新点

1. 理论创新

  • minimax最优性条件：建立了RFF特征数量l与统计最优性的精确关系
  • 多项式和指数衰减情况：分别分析了积分算子特征值的不同衰减模式
  • 非渐近分析：提供了有限样本下的性能保证

2. 算法创新

  • 自适应正则化：通过联合检验实现对正则化参数的数据驱动选择
  • 核函数自适应：扩展到多核函数的自适应选择
  • 置换检验实现：提供完全数据驱动的临界值计算

3. 计算创新

  • 高效算法：详细的计算复杂度分析和优化实现
  • 并行化：置换检验的天然并行化特性

实验设置

数据集

  1. 合成数据：
    • 高斯均值偏移：P = N(0,I), Q = N(μ,I)
    • 高斯尺度偏移：P = N(0,I), Q = N(0,σ²I)
    • 柯西中位数偏移：不同中位数的柯西分布
  2. 真实数据：
    • MNIST数据集：7×7像素手写数字图像，维度d=49
    • 不同数字子集的分布差异检测

评价指标

  • 统计功效(Power)：在备择假设下正确拒绝原假设的概率
  • 计算时间：算法运行时间的比较
  • 第一类错误：控制在α=0.05水平

对比方法

  • 精确自适应检验：基于完整核矩阵的谱正则化检验
  • 不同RFF特征数量：l ∈ {1,3,5,7,9,15,20}的性能比较

实现细节

  • 正则化函数：Showalter regularizer gλ(x) = (1-e^(-x/λ))/x
  • 核函数：高斯核和拉普拉斯核，带宽自适应选择
  • 置换次数：RFF版本B=550-800，精确版本B'=250-450

实验结果

主要结果

1. 统计性能

  • 高斯均值偏移：RFF特征数l≥7时，功效接近精确方法
  • 高斯尺度偏移：l≥5时达到良好性能
  • 柯西分布：需要更多特征(l≥10-15)以处理重尾分布
  • MNIST数据：l≥15时在复杂真实数据上表现良好

2. 计算效率

显著的计算时间节省：

  • 高斯实验：RFF方法仅需33-44%的计算时间
  • 尺度偏移：30-40%的时间消耗
  • 柯西实验：仅需5-6%的计算时间
  • MNIST：5-15%的时间消耗

3. 理论验证

实验结果验证了理论预测：

  • 特征数量需求与数据维度和分布复杂度相关
  • 计算-统计权衡符合理论分析

消融实验

通过不同RFF特征数量的比较，验证了：

  1. 特征数量阈值的存在性
  2. 过少特征导致功效损失
  3. 适当特征数量实现最佳权衡

实验发现

  1. 维度效应：高维数据需要更多RFF特征
  2. 分布类型影响：重尾分布需要更多特征保证性能
  3. 实际阈值：理论要求的特征数量在实践中可以适当减少

相关工作

核方法双样本检验

  • MMD检验：Gretton et al. (2006, 2012)的开创性工作
  • minimax最优性：Li & Yuan (2024), Schrab et al. (2023)的最近进展
  • 谱正则化：Hagrass et al. (2024)的理论突破

随机特征近似

  • RFF理论：Rahimi & Recht (2007)的基础框架
  • MMD加速：Zhao & Meng (2015), Choi & Kim (2024)的应用
  • 计算-统计权衡：Sriperumbudur & Sterge (2022)的理论分析

本文优势

相比现有工作的主要优势：

  1. 更一般的核函数：不限于平移不变核
  2. 更广的适用性：支持非欧几里得域
  3. 更强的理论保证：非渐近minimax最优性
  4. 更实用的算法：完全数据驱动的实现

结论与讨论

主要结论

  1. 理论贡献：首次建立了RFF近似下谱正则化双样本检验的minimax最优性理论
  2. 算法贡献：提供了计算高效且统计最优的实用算法
  3. 实证验证：在多种数据类型上验证了方法的有效性

局限性

  1. 特征数量选择：虽然提供了理论指导，但实际选择仍需经验调整
  2. 核函数依赖：性能仍依赖于核函数的选择
  3. 重尾分布：对于极端重尾分布可能需要大量特征

未来方向

  1. 其他近似方法：探索Nyström等替代近似技术
  2. 廉价置换检验：结合cheap permutation testing进一步降低计算成本
  3. 自动调参：开发更智能的超参数选择策略

深度评价

优点

  1. 理论严谨性：提供了完整的非渐近理论分析，包括充分条件和minimax最优性证明
  2. 实用性强：算法完全数据驱动，无需先验知识
  3. 实验充分：涵盖合成和真实数据，多种分布类型
  4. 写作清晰：技术细节详尽，证明完整

不足

  1. 复杂度分析：虽然降低了渐近复杂度，但常数因子可能较大
  2. 参数敏感性：对正则化参数和特征数量的选择仍较敏感
  3. 重尾处理：对重尾分布的处理效果有待改进

影响力

  1. 理论价值：为核方法的计算-统计权衡提供了新的理论框架
  2. 实用价值：在大规模数据的双样本检验中具有重要应用前景
  3. 方法论贡献：RFF近似在统计检验中的应用为相关研究提供了新思路

适用场景

  1. 大规模数据：样本量较大时计算优势明显
  2. 高维数据：在高维设置下相比传统方法有显著优势
  3. 实时应用：计算效率的提升使得实时检验成为可能
  4. 非参数设置：适用于分布形式未知的一般情况

参考文献

  1. Gretton, A., et al. (2012). A kernel two-sample test. JMLR.
  2. Hagrass, O., et al. (2024). Spectral regularized kernel two-sample tests. Annals of Statistics.
  3. Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. NIPS.
  4. Choi, I., & Kim, I. (2024). Computational-statistical trade-off in kernel two-sample testing with random Fourier features.
  5. Sriperumbudur, B. K., & Sterge, N. (2022). Approximate kernel PCA: Computational versus statistical trade-off. Annals of Statistics.

总评：这是一篇高质量的理论统计学论文，成功地将随机特征近似技术应用于谱正则化双样本检验，在保持统计最优性的同时显著提升了计算效率。论文的理论分析深入细致，实验验证充分，对统计学习理论和实际应用都有重要价值。