Soft and subspace robust multivariate rank tests based on entropy regularized optimal transport

Shoaib Bin Masud, Boyang Lyu, Shuchin AeronarXiv 2021 · OpenReview

Abstract

This paper extends the recently proposed multivariate rank energy distance—a framework based on optimal transport for statistical testing of distributional similarity—to a differentiable "soft" rank energy distance. By applying entropy regularization, the authors derive a test statistic that is amenable to gradient-based optimization. This differentiability enables the development of the Projected soft-Rank Energy (PsRE) distance, which identifies optimal low-dimensional subspaces via optimization over the Stiefel manifold. Experimental results demonstrate that PsRE effectively balances detection power and false alarm rates by focusing on relevant feature subspaces. Furthermore, the proposed tests show significant utility in unsupervised change point detection for multivariate time series data.

Introduction

In statistical analysis, the two-sample test is a foundational tool used to determine if two sets of data are drawn from the same underlying distribution. While this is a well-understood problem in one-dimensional space (e.g., the Kolmogorov-Smirnov test), it becomes significantly more complex in multivariate settings. The primary obstacle is the lack of a "natural ordering" in high-dimensional space; unlike the real line, there is no inherent way to rank data points relative to one another.

Recent advancements have utilized Optimal Transport (OT) to define multivariate ranks by mapping data points to a uniform grid, such as a Halton sequence. However, these "hard" ranks are discrete and non-differentiable, limiting their integration into modern machine learning pipelines and preventing the use of gradient-based methods to identify specific subspaces where distributions might differ. Moreover, as dimensionality increases, standard tests often suffer from a loss of statistical power, failing to detect differences that may only exist within a small subset of features.

Methodology

Soft Rank Energy (sRE)

The authors address the limitations of discrete ranks by introducing Soft Rank Energy (sRE). Instead of relying on exact, discrete optimal transport—which functions as a rigid matching problem—they employ entropic regularization via the Sinkhorn algorithm. This approach yields a "soft" transport plan that is a smooth, differentiable function of the input data. Consequently, the rank-based test statistic can be incorporated into optimization frameworks, allowing for more flexible statistical modeling.

Projected soft-Rank Energy (PsRE)

Building on the differentiability of sRE, the authors propose a "subspace robust" test: the Projected soft-Rank Energy (PsRE). By optimizing over the Stiefel manifold (the space of all orthogonal projection matrices), the method identifies a low-dimensional subspace that maximizes the distance between two distributions. This effectively "zooms in" on the dimensions where the samples differ most, mitigating the curse of dimensionality and enhancing the test's sensitivity to localized distributional shifts.

Experimental Evaluation

Synthetic Benchmarks

The methods were evaluated against a suite of 12 synthetic distributional settings (v1-v12), including heavy-tailed Cauchy distributions, Gamma distributions, auto-regressive models, and multivariate Gaussians contaminated with noise. The experiments confirmed that:

  • Consistency: With a small regularizer (e.g., $\epsilon = 0.001$), sRE behaves almost identically to traditional "hard" rank energy tests but with reduced computational complexity.
  • Subspace Power: In a 100-dimensional test where differences were confined to a small number of dimensions, standard sRE failed to distinguish the null hypothesis. However, PsRE (projecting to a 3D subspace) successfully identified the differences, demonstrating significantly higher statistical power.

Real-World Application: Change Point Detection

The authors applied their framework to the HASC-PAC2016 dataset, which contains over 700 three-axis accelerometer sequences of human activities (e.g., walking, jogging, climbing stairs). The sRE statistic was used for unsupervised change point detection, successfully identifying the exact moments when subjects transitioned between different physical activities. This highlights the method's practical utility for real-time time-series analysis.

Key Insights

  1. Differentiability as an Enabler: Turning a static statistical test into a differentiable objective function allows for the discovery of optimal subspaces, transforming how we approach high-dimensional hypothesis testing.
  2. Distribution-Freeness: A critical property of rank tests is being "distribution-free" (where the test's behavior under the null hypothesis is independent of the underlying distribution). The authors demonstrate that sRE maintains this property for small values of the entropic regularizer.
  3. Robustness to Dimensionality: PsRE solves the problem of "washed out" signals in high dimensions by focusing only on the features that contribute to distributional differences.

Limitations and Future Work

While promising, the method has certain trade-offs. The test is highly sensitive to shifts in signal, which is beneficial for change point detection but can lead to frequent false alarms in the presence of outliers or anomalies. Additionally, while the Sinkhorn algorithm is efficient, performing Riemannian optimization over the Stiefel manifold introduces additional computational overhead. Future research is expected to focus on a deeper theoretical analysis of the properties of these soft multivariate ranks and improving robustness against noisy data environments.

Summary updated

Abstract

In this paper, we extend the recently proposed multivariate rank energy distance, based on the theory of optimal transport, for statistical testing of distributional similarity, to soft rank energy distance. Being differentiable, this in turn allows us to extend the rank energy to a subspace robust rank energy distance, dubbed Projected soft-Rank Energy distance, which can be computed via optimization over the Stiefel manifold. We show via experiments that using projected soft rank energy one can trade-off the detection power vs the false alarm via projections onto an appropriately selected low dimensional subspace. We also show the utility of the proposed tests on unsupervised change point detection in multivariate time series data. All codes are publicly available at the link provided in the experiment section.
BibTeX
@misc{masud2021soft,
  author = {Shoaib Bin Masud and Boyang Lyu and Shuchin Aeron},
  title = {{Soft and subspace robust multivariate rank tests based on entropy regularized optimal transport}},
  year = {2021},
  eprint = {2103.08811},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.08811},
}
Figure