A Bipartite Ranking Approach to the Two-Sample Problem

Stéphan Clémençon, Myrto Limnios, Nicolas Vayatis

In the world of statistics and machine learning, the two-sample problem is a fundamental question: Given two sets of data, do they come from the same underlying distribution? While this is straightforward in one dimension, it becomes a nightmare in high-dimensional spaces—a phenomenon known as the "curse of dimensionality."

A new paper by Clémençon, Limnios, and Vayatis proposes a clever workaround. Instead of trying to measure distances between complex high-dimensional shapes, they use machine learning to "flatten" the data into a single dimension where classical, powerful tests can do the heavy lifting.

TL;DR

The authors propose a two-step framework for high-dimensional two-sample testing. By using bipartite ranking algorithms to learn an optimal projection of multivariate data onto the real line, they enable the use of powerful univariate rank tests in complex spaces, effectively bypassing the curse of dimensionality.

What Problem Does This Paper Address?

The goal is to test the null hypothesis $H_0: G = H$ (the distributions are the same) against the alternative $H_1: G \neq H$.

In one dimension, we have "rank tests" (like the Mann-Whitney-Wilcoxon test). These are great because they are pivotal—their behavior under the null hypothesis is known and doesn't depend on the specific distribution of the data. However, ranking requires a natural order (1 is less than 2), which doesn't exist in $\mathbb{R}^d$ for $d \geq 2$.

Existing high-dimensional solutions, such as Maximum Mean Discrepancy (MMD) or Energy distances, often struggle to detect small differences between distributions as the number of dimensions grows, or they require computationally expensive permutations to determine significance levels.

Methods

The authors introduce a framework that combines statistical learning with classical hypothesis testing in two main steps:

  1. Bipartite Ranking (The Learning Phase): The two samples are treated as "positive" and "negative" classes. A bipartite ranking algorithm (like a Ranking Forest or RankSVM) is trained on a portion of the data to learn a scoring function $s(x)$. Ideally, this function mimics the likelihood ratio between the two distributions, assigning higher scores to points more likely to come from distribution $G$.
  2. Univariate Rank Test (The Testing Phase): The remaining data is "projected" onto the real line using the learned scoring function. Because the data is now one-dimensional, the authors can apply a standard linear rank test.

To ensure the test remains statistically valid, they use a 2-split trick: one subset of data is used to learn the ranking, and a completely separate subset is used to perform the actual test. This prevents "overfitting" the test to the specific samples used for training.

Datasets

The authors evaluated their approach using several synthetic multivariate benchmarks designed to simulate different types of distributional shifts:

  • Location Gaussian Models: Distributions differ by a small shift in the mean ($\epsilon$).
  • Scale Gaussian Models: Distributions have the same mean but different covariance structures (e.g., different correlation levels).
  • Non-Gaussian Models: Heavy-tailed distributions (Cauchy) and Lognormal models to test robustness beyond "nice" bell curves.
  • High-Dimensional Scaling: Experiments were conducted with dimensions ranging from $d=3$ up to $d=100$.

Key Insights and Ideas

  • Approximating the Likelihood Ratio: The "Aha!" moment is realizing that the optimal scoring function for ranking is a monotone transform of the likelihood ratio. By learning this ratio, the algorithm automatically finds the "direction" in high-dimensional space where the two distributions differ most.
  • Dimensionality Independence: Once the data is projected via the scoring function, the final test is univariate. This means the statistical power of the test is less affected by the "noise" of high dimensions compared to methods that look at the whole space at once.
  • ROC Curve Connection: The paper elegantly links rank statistics to the Area Under the ROC Curve (AUC). Testing if two distributions are the same is equivalent to testing if the "optimal" ROC curve for ranking them is just a diagonal line.

Key Results

  • Superior Power: In almost all scenarios, the ranking-based approach—specifically using Ranking Forests (rForest)—outperformed state-of-the-art (SoA) competitors like MMD and Energy tests. It was significantly better at detecting "small" departures ($\epsilon$) from the null hypothesis.
  • Robustness to Dimension: While the power of MMD and Energy tests often degraded as the dimension $d$ increased, the ranking-based methods (particularly those using neural networks or forests) maintained high rejection rates even at $d=100$.
  • Zero Bias: Because the second step uses a pivotal rank test, the method maintains excellent control over Type-I errors (false positives), matching the theoretical significance level $\alpha$ accurately.

Limitations and Future Work

  • Data Splitting Efficiency: The "2-split trick" is necessary for theory but "wastes" data. The authors note that determining the optimal ratio for splitting (currently 80% for learning, 20% for testing) is a difficult open problem.
  • Choice of Ranking Algorithm: The performance depends heavily on the chosen machine learning model. While Ranking Forests performed best here, different data structures might favor different architectures.
  • Ensemble Testing: A single scoring function might miss certain types of differences. The authors suggest that future work could involve combining multiple ranking-based tests (using different score-generating functions) to create an even more robust "ensemble" test.

Summary updated

Abstract

The two-sample problem, which consists in testing whether independent samples on $\mathbb{R}^d$ are drawn from the same (unknown) distribution, finds applications in many areas. Its study in high-dimension is the subject of much attention, especially because the information acquisition processes at work in the Big Data era often involve various sources, poorly controlled, leading to datasets possibly exhibiting a strong sampling bias. While classic methods relying on the computation of a discrepancy measure between the empirical distributions face the curse of dimensionality, we develop an alternative approach based on statistical learning and extending rank tests, capable of detecting small departures from the null assumption in the univariate case when appropriately designed. Overcoming the lack of natural order on $\mathbb{R}^d$ when $d\geq 2$, it is implemented in two steps. Assigning to each of the samples a label (positive vs. negative) and dividing them into two parts, a preorder on $\mathbb{R}^d$ defined by a real-valued scoring function is learned by means of a bipartite ranking algorithm applied to the first part and a rank test is applied next to the scores of the remaining observations to detect possible differences in distribution. Because it learns how to project the data onto the real line nearly like (any monotone transform of) the likelihood ratio between the original multivariate distributions would do, the approach is not much affected by the dimensionality, ignoring ranking model bias issues, and preserves the advantages of univariate rank tests. Nonasymptotic error bounds are proved based on recent concentration results for two-sample linear rank-processes and an experimental study shows that the approach promoted surpasses alternative methods standing as natural competitors.
BibTeX
@inproceedings{clemencon2025bipartite,
  author = {Stéphan Clémençon and Myrto Limnios and Nicolas Vayatis},
  title = {{A Bipartite Ranking Approach to the Two-Sample Problem}},
  booktitle = {Electronic},
  year = {2025},
  doi = {10.1214/25-ejs2392},
}
Figure