Variable Selection for Kernel Two-Sample Tests

Jie Wang, Santanu S. Dey, Yao XiearXiv 2023 · DOI · arXiv

TL;DR

This paper introduces a novel framework for identifying the most informative features to distinguish between two probability distributions. By maximizing a variance-regularized kernel Maximum Mean Discrepancy (MMD) statistic through Mixed-Integer Programming, the authors provide a method that breaks the "curse of dimensionality," where the required sample size depends on the number of selected features rather than the total data dimension.

What Problem Does This Paper Address?

Two-sample testing is a fundamental statistical task: given two sets of data, do they come from the same distribution? In modern data science, we often face high-dimensional datasets where only a small subset of variables actually drives the difference between groups (e.g., a few specific genes indicating a disease).

Standard variable selection tools like Lasso are designed for regression or classification, not for testing distributional differences. Existing kernel-based tests often struggle in high dimensions because the "noise" from irrelevant variables washes out the signal. The authors tackle the "subset selection problem"—finding the best $d$ variables out of $D$ total variables—which is computationally "hard" (NP-hard) and lacks established statistical guarantees for two-sample testing.

Methods

The authors propose a framework based on Maximum Mean Discrepancy (MMD), a popular kernel-based metric for comparing distributions. Their core contribution is a variance-regularized objective function: instead of just maximizing the MMD, they maximize the MMD minus a weighted term for its variance. This balance is crucial for maximizing the actual "power" of the statistical test.

The paper explores three kernel types:

  1. Linear Kernel: Leads to a "Sparse Trust Region Subproblem" (STRS). The authors provide an exact Mixed-Integer Semidefinite Programming (MISDP) reformulation and a fast first-order approximation using the Alternating Direction Method of Multipliers (ADMM).
  2. Quadratic Kernel: Captures correlations between variables but results in a harder, non-concave optimization problem.
  3. Gaussian Kernel: The most flexible but computationally the most difficult.

For the non-linear kernels, they develop a heuristic algorithm that combines Simulated Annealing with iterative quadratic approximations (solving an STRS at each step).

Datasets

The framework was evaluated on both synthetic and real-world data:

  • Synthetic Datasets: Four controlled scenarios including Gaussian mean shifts, covariance shifts (where means are identical but correlations differ), and comparisons between Gaussian and Laplacian distributions.
  • MNIST: The classic handwritten digits dataset. The authors used this to visualize which pixels the model selects to distinguish between different digits (e.g., '3' vs '8').
  • Healthcare (Sepsis) Dataset: A real-world dataset with 39 features from over 23,000 patients, used to identify key clinical variables that distinguish healthy patients from those with Sepsis.

Key Insights and Ideas

  • Beating the Curse of Dimensionality: The most significant theoretical insight is that the sample size requirement for these tests depends on the number of selected variables ($d$), not the total variables ($D$). This means the test remains powerful even if you have thousands of irrelevant features, provided you can solve the selection problem.
  • The Variance Matters: Simply picking variables that maximize the MMD isn't enough. By regularizing with the variance, the authors ensure the resulting test statistic is stable, which directly translates to a lower Type-II error (fewer missed detections).
  • Kernel Trade-offs: There is a clear hierarchy of complexity. Linear kernels are easy to solve but can't see differences if the means are the same. Quadratic kernels can detect changes in correlation. Gaussian kernels are the "gold standard" for flexibility but require much more sophisticated optimization heuristics.

Key Results

  • Statistical Power: On the Sepsis dataset, the Quadratic MMD approach achieved a testing power of 0.915, significantly outperforming Sparse Logistic Regression (0.771) and Projected Wasserstein methods (0.749).
  • Support Recovery: In synthetic tests, the proposed method consistently achieved lower False Discovery Proportions (FDP) than baselines, meaning it was much better at picking the "true" informative variables and ignoring the noise.
  • Computational Efficiency: The ADMM-based approximation for the linear kernel was shown to be orders of magnitude faster than exact SDP solvers while maintaining nearly identical solution quality.

Limitations and Future Work

  • Hyperparameter Sensitivity: The performance depends on the choice of the regularization parameter $\lambda$ and kernel bandwidth. While the authors use a "median heuristic" and cross-validation, a more automated or theoretically grounded selection method remains an open question.
  • Gaussian Optimization: Because the Gaussian kernel objective is highly complex (an "$\infty$-degree monomial"), the second-order approximations used in the heuristic may not always be reliable.
  • Scalability: While the ADMM approach helps, solving Mixed-Integer Programs for extremely large $D$ (e.g., hundreds of thousands of features) still presents a significant computational hurdle. Future work could explore even more efficient screening rules to prune the variable space before optimization.

Summary updated

Abstract

We consider the variable selection problem for two-sample tests, aiming to select the most informative variables to determine whether two collections of samples follow the same distribution. To address this, we propose a novel framework based on the kernel maximum mean discrepancy (MMD). Our approach seeks a subset of variables with a pre-specified size that maximizes the variance-regularized kernel MMD statistic. We focus on three commonly used types of kernels: linear, quadratic, and Gaussian. From a computational perspective, we derive mixed-integer programming formulations and propose exact and approximation algorithms with performance guarantees to solve these formulations. From a statistical viewpoint, we derive the rate of testing power of our framework under appropriate conditions. These results show that the sample size requirements for the three kernels depend crucially on the number of selected variables, rather than the data dimension. Experimental results on synthetic and real datasets demonstrate the superior performance of our method, compared to other variable selection frameworks, particularly in high-dimensional settings.
BibTeX
@misc{wang2023variable,
  author = {Jie Wang and Santanu S. Dey and Yao Xie},
  title = {{Variable Selection for Kernel Two-Sample Tests}},
  year = {2023},
  eprint = {2302.07415},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2302.07415},
}
Figure