High-dimensional two-sample testing: From optimal transport to optimal derangements
Abstract
In recent years, optimal transport has emerged as a useful framework for constructing distribution-free multivariate two-sample tests by transporting observations to a reference distribution under a suitable transportation cost. However, existing optimal transport-based tests can perform poorly in high dimension, low sample size (HDLSS) settings, and their performance depends critically on the choice of the reference distribution and transportation cost. We investigate this phenomenon and show that suitable choices can substantially improve their performance. Motivated by this analysis, we introduce a class of two-sample tests based on optimal derangements that do not require an external reference distribution. The minimum distance pairing test of Rosenbaum arises as a special case when the optimization is restricted to a subclass of derangements, thereby revealing a connection between this method and optimal transport. We propose the optimal derangement (ODER) test and its distribution-free variant, the ODER-SHC test, obtained by restricting the minimization to derangements consisting of a single Hamiltonian cycle. We establish their consistency under both HDLSS and classical large-sample asymptotic regimes. We also develop corresponding procedures based on the L1 distance and establish their high-dimensional consistency under conditions involving coordinate-wise energy distances. These L1 distance based tests can also discriminate between two high-dimensional distributions with identical first two moments but different marginal distributions. Analyses of benchmark datasets and extensive simulation studies demonstrate the performance of the proposed methods across a variety of alternatives and data settings.
Related
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- High-Dimensional Two-Sample Covariance Testing with Null-Preserving Transformations
- Rigidity of one-dimensional point processes via optimal transport
- Data-Matrix-Based Overall Goodness-of-Fit Testing for Confirmatory Factor Analysis: In-Sample Prediction Error for Observed Variables
- OLS Testing with Predictors Scaled to Have Unit Sample Variance, and Similar Results for a Robust Regression Estimator
BibTeX
@misc{ghosh2026highdimensional,
title = {{High-dimensional two-sample testing: From optimal transport to optimal derangements}},
author = {Abhradipta Ghosh and Vaibhav Sherkar and Bilol Banerjee and Anil K. Ghosh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38519},
eprint = {2610.38519},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38519},
}
RIS
TY - UNPB
TI - High-dimensional two-sample testing: From optimal transport to optimal derangements
AU - Abhradipta Ghosh
AU - Vaibhav Sherkar
AU - Bilol Banerjee
AU - Anil K. Ghosh
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38519
UR - https://arxiv.org/abs/2610.38519
AB - In recent years, optimal transport has emerged as a useful framework for constructing distribution-free multivariate two-sample tests by transporting observations to a reference distribution under a suitable transportation cost. However, existing optimal transport-based tests can perform poorly in high dimension, low sample size (HDLSS) settings, and their performance depends critically on the choice of the reference distribution and transportation cost. We investigate this phenomenon and show that suitable choices can substantially improve their performance. Motivated by this analysis, we introduce a class of two-sample tests based on optimal derangements that do not require an external reference distribution. The minimum distance pairing test of Rosenbaum arises as a special case when the optimization is restricted to a subclass of derangements, thereby revealing a connection between this method and optimal transport. We propose the optimal derangement (ODER) test and its distribution-free variant, the ODER-SHC test, obtained by restricting the minimization to derangements consisting of a single Hamiltonian cycle. We establish their consistency under both HDLSS and classical large-sample asymptotic regimes. We also develop corresponding procedures based on the L1 distance and establish their high-dimensional consistency under conditions involving coordinate-wise energy distances. These L1 distance based tests can also discriminate between two high-dimensional distributions with identical first two moments but different marginal distributions. Analyses of benchmark datasets and extensive simulation studies demonstrate the performance of the proposed methods across a variety of alternatives and data settings.
ER -