Remember the Curse of Dimensionality: The Case of Goodness-of-Fit\n Testing in Arbitrary Dimension

Ery Arias-Castro, Bruno Pelletier, Venkatesh Saligrama

Abstract

Despite a substantial literature on nonparametric two-sample goodness-of-fit testing in arbitrary dimensions spanning decades, the "curse of dimensionality" has often been overlooked in favor of optimistic parametric rates. This paper provides a rigorous minimax analysis, establishing that the fundamental difficulty of this task scales exponentially with dimension. We demonstrate that the classic chi-squared test, when properly configured, achieves the minimax optimal rate and can be extended to adapt to low-dimensional manifolds and unknown smoothness.

Introduction

In the era of high-dimensional data, there is a recurring hope in machine learning that complex distributions can be compared as easily as simple ones. Recent literature on kernel-based methods has occasionally suggested that two-sample testing can achieve "parametric" rates—where the error depends only on the sample size $n$, independent of the dimension $d$. However, this paper serves as a critical reality check. By returning to the foundations of nonparametric statistics, we show that the "Curse of Dimensionality" remains an inescapable barrier when testing against general, nonparametric alternatives.

The Two-Sample Problem in High Dimensions

In statistics, the "two-sample goodness-of-fit" problem asks a fundamental question: Given two sets of data points, did they originate from the same underlying probability distribution?

While this is well-understood in one dimension using classical tools like the Kolmogorov-Smirnov test, high-dimensional spaces (such as those containing complex medical images or financial time series) introduce significant complexity. The authors argue that the optimistic $1/\sqrt{n}$ rates often cited in recent kernel method literature are misleading because they typically apply only to "directional" alternatives—specific, simple ways two distributions can differ. If the difference between two distributions is complex and truly nonparametric, the problem becomes significantly harder.

Theoretical Framework: Minimax Analysis

To establish the fundamental mathematical limits of this problem, the authors employ minimax analysis. This framework determines the best possible performance a test can achieve against the "toughest" possible alternative distribution.

Measuring the discrepancy in the $L^2$ metric (the square root of the integral of the squared difference between densities), the authors derive the minimax rate: $$ \rho_n \asymp n^{-\frac{2s}{4s+d}} $$ where $n$ is the sample size, $s$ represents the Hölder smoothness of the densities, and $d$ is the dimension. This formula reveals the prototypical curse of dimensionality: as $d$ increases in the denominator of the exponent, the detectable difference rate plummets, requiring exponentially more data to maintain sensitivity.

The Return of the Chi-Squared Test

One of the paper's most striking findings is that the classic chi-squared test is actually minimax optimal for this task. The method involves partitioning the high-dimensional space into "bins" (hyperrectangles) and comparing the counts of points from each sample within those bins.

This "oldie but goodie" result suggests that complex kernels are not always necessary; rather, the success of the test depends on selecting the correct bin size. Furthermore, the paper provides a geometric intuition for the curse: in high dimensions, even a large sample is likely to leave the "center" of the space empty, making it impossible to detect differences without making massive assumptions.

Intrinsic Dimension and Manifold Adaptation

The "curse" is not always dictated by the ambient dimension of the space. In many real-world scenarios, data points in a high-dimensional space ($d$) actually lie on a much lower-dimensional surface or manifold ($d_0$).

The authors prove that the chi-squared test can be made to work when distributions have support of low intrinsic dimension. In such cases, the rate automatically improves to: $$ n^{-\frac{2s}{4s+d_0}} $$ This confirms that the difficulty of the test is driven by the actual structure of the data, not just the number of variables recorded.

Multiscale Adaptation

Recognizing that researchers rarely know the smoothness $s$ or the intrinsic dimension $d_0$ in advance, the authors propose a multiscale version of the chi-squared test. Inspired by the work of Ingster (2000), this test:

  1. Examines multiple bin sizes simultaneously.
  2. Uses a Bonferroni correction to maintain statistical validity across scales.
  3. Adapts to unknown smoothness and dimensionality without a significant loss in power, achieving the optimal rate up to a small logarithmic factor.

Limitations and Future Work

While providing a definitive theoretical boundary, the authors note several areas for further refinement:

  • Metric Specificity: The results are specific to the $L^2$ metric; other metrics like Maximum Mean Discrepancy or Wasserstein distance may behave differently.
  • Computational Complexity: Binning a 1000-dimensional space is computationally impossible as the number of bins grows exponentially. Practical application requires combining these insights with dimensionality reduction or clever partitioning like KD-trees.
  • The Adaptive Gap: There remains a small gap (a factor of $\sqrt{\log m}$) between the adaptive upper bound and the lower bound, suggesting room for even tighter theoretical proofs.

Conclusion

This research reaffirms the necessity of considering dimensionality in nonparametric testing. By establishing minimax rates and proving the optimality of the chi-squared test, the authors provide a rigorous "reality check" for high-dimensional statistics, ensuring that the search for efficient tests remains grounded in mathematical reality.

Summary updated

Abstract

Despite a substantial literature on nonparametric two-sample goodness-of-fit\ntesting in arbitrary dimensions spanning decades, there is no mention there of\nany curse of dimensionality. Only more recently Ramdas et al. (2015) have\ndiscussed this issue in the context of kernel methods by showing that their\nperformance degrades with the dimension even when the underlying distributions\nare isotropic Gaussians. We take a minimax perspective and follow in the\nfootsteps of Ingster (1987) to derive the minimax rate in arbitrary dimension\nwhen the discrepancy is measured in the L2 metric. That rate is revealed to be\nnonparametric and exhibit a prototypical curse of dimensionality. We further\nextend Ingster's work to show that the chi-squared test achieves the minimax\nrate. Moreover, we show that the test can be made to work when the\ndistributions have support of low intrinsic dimension. Finally, inspired by\nIngster (2000), we consider a multiscale version of the chi-square test which\ncan adapt to unknown smoothness and/or unknown intrinsic dimensionality without\nmuch loss in power.\n
BibTeX
@article{ariascastro2018remember,
  author = {Ery Arias-Castro and Bruno Pelletier and Venkatesh Saligrama},
  title = {{Remember the Curse of Dimensionality: The Case of Goodness-of-Fit\textbackslash\{\}n Testing in Arbitrary Dimension}},
  journal = {Journal of Nonparametric Statistics},
  year = {2018},
  doi = {10.1080/10485252.2018.1435875},
}
Figure