Technical Summary: Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance

Problem Statement

The paper addresses the challenge of extending the Kolmogorov-Smirnov (KS) distance, a fundamental non-parametric metric for comparing univariate distributions, to multi-dimensional settings ($d > 1$). While the univariate KS distance is well-understood, stable, and efficiently computable, existing high-dimensional generalizations suffer from significant limitations:

1. Instability: Popular heuristics like "quad-KS" (which restricts the search space to quadrants defined by data points) are shown to be unstable; the distance can change drastically with the addition or removal of a single data point, preventing rigorous sample complexity bounds.
2. Computational Intractability: Exact computation of the multi-dimensional KS distance over all possible ranges is computationally expensive (naively $O(n^d)$), and many existing permutation-based tests require exponential time relative to sample size.
3. Unit Sensitivity: Many alternative metrics (e.g., Wasserstein, Maximum Mean Discrepancy) rely on Euclidean ground distances, making them sensitive to the choice of units or scaling of dimensions, which is problematic when dimensions have different physical units (e.g., height vs. weight).

The authors propose a formulation of the multi-dimensional KS distance ($dKS$) that is an Integral Probability Metric (IPM), invariant to unit choices, and capable of being computed efficiently with provable approximation guarantees.

Methodology

1. Definition of Multi-Dimensional KS ($dKS$)

The authors define the distance between two distributions $\mu$ and $\nu$ in $\mathbb{R}^d$ as the maximum difference in their cumulative distribution functions over orthogonal dominating rectangular ranges.
$$dKS(\mu, \nu) = \sup_{z \in \mathbb{R}^d} \left| \int_{x \preceq z} d\mu(x) - \int_{x \preceq z} d\nu(x) \right|$$
where $x \preceq z$ denotes that every coordinate of $x$ is less than or equal to the corresponding coordinate of $z$. Unlike some previous extensions (e.g., Peacock's) that consider all $2^d$ orthants, this formulation focuses on a single quadrant (dominating rectangles), which the authors argue is sufficient for a robust metric.

2. Theoretical Properties

• Metric Properties: The paper proves that $dKS$ is a full metric (satisfying symmetry, triangle inequality, and strong identity) on the space of probability measures, unlike heuristic variants which may only be pseudometrics or lack stability.
• Sample Complexity: Leveraging VC-dimension theory for range spaces, the authors establish that $n = O(\frac{1}{\epsilon^2}(d + \log(1/\delta)))$ samples are sufficient to estimate the distance within error $\epsilon$ with probability $1-\delta$. This bound is linear in the dimension $d$.

3. Computational Algorithms

The paper introduces algorithms to compute an $\epsilon$-approximation of $dKS$ with Computational-Statistical Runtime (CSR) that is near-linear in the required sample size for dimensions $d \le 4$.

• For $d=2$: The authors propose a sketching approach (Algorithm 2, dKS-Sketch). By sorting points and constructing a stratified grid of size $O((d/\epsilon)^d)$, the algorithm reduces the problem to dynamic programming on the grid.
  • Runtime: $O(n \log n + (d/\epsilon)^d)$. For $d=2$ and $\epsilon \approx 1/\sqrt{n}$, this yields $O(n \log n)$.
• For $d=3, 4$: The authors reduce the problem to finding a point of maximum depth in a set of weighted rectangles (a variation of Klee's Measure Problem).
  • They first compress the sample to a smaller $\epsilon$-approximation set using low-discrepancy colorings (Lemma 2).
  • They then apply Chan's algorithm for the maximum weight point in $O(s^{d/2} \text{polylog}(s))$ time, where $s$ is the compressed sample size.
  • Runtime: Near-linear in the sample complexity $n_\epsilon$. Specifically, $O(n \log^3 n)$ for $d=3$ and $O(n \log^{21} n)$ for $d=4$.
• Hardness: The paper argues that achieving near-linear runtime for $d > 4$ is unlikely, as it would imply a breakthrough in solving the Max-Weight $k$-Clique problem, a widely held hard problem in fine-grained complexity.

4. Hypothesis Testing

Using the derived sample complexity bounds and the metric properties, the authors construct a level-$\delta$ two-sample hypothesis test.

• The test rejects the null hypothesis ($\mu = \nu$) if the computed $dKS$ exceeds a threshold derived from the sample size and confidence level.
• Crucially, unlike Monte Carlo-based tests, this test provides a precise, finite-sample guarantee on the Type I error rate without relying on asymptotic approximations.

Key Results

1. Stability: The proposed $dKS$ formulation is stable with respect to sampling, unlike "quad-KS" or other quadrant-restricted heuristics. The authors construct pathological examples where adding a single point to a quad-KS calculation doubles the distance, whereas $dKS$ remains stable.
2. Efficiency:
   • $d=2$: Achieves $O(n \log n)$ runtime, matching the efficiency of the univariate case.
   • $d=3, 4$: Achieves near-linear runtime in the sample complexity, a significant improvement over the exponential or high-polynomial costs of previous exact methods.
3. Precision: The derived hypothesis test is the first to offer a precise, non-asymptotic, and non-simulation-based test for multi-dimensional distributions in moderate dimensions ($d \le 4$).
4. Empirical Validation: Experiments on $d=2$ data show that the dKS-Sketch algorithm is orders of magnitude faster (e.g., 0.2s vs. 4.2 hours for $n \approx 10^6$) than the baseline exact algorithm while maintaining comparable accuracy. In power evaluations, the sketch-based test achieves full statistical power in seconds, whereas permutation-based baselines require hours or days.

Significance and Claims

The paper claims to provide the "right way" to generalize the KS distance to multiple dimensions by balancing mathematical rigor (stability, metric properties, sample complexity) with computational feasibility.

• Theoretical Contribution: It establishes that a one-quadrant formulation is sufficient for a robust metric and proves that this metric admits efficient approximation algorithms in low dimensions.
• Practical Impact: It enables the application of non-parametric two-sample testing to moderate-dimensional data (e.g., 2D to 4D) with different units, where Euclidean-based metrics fail and previous KS extensions were either unstable or computationally prohibitive.
• Limitations: The authors explicitly note that for dimensions $d > 4$, the problem is likely intractable to solve with near-linear runtime unless major conjectures in complexity theory are resolved. They also acknowledge that the algorithms for $d=3, 4$ rely on complex reductions to Klee's measure problem and may be difficult to implement practically compared to the $d=2$ case.

The work positions the proposed $dKS$ as a preferred alternative to existing high-dimensional extensions, offering a stable, precise, and computationally efficient tool for statistical analysis in moderate dimensions.