Remember the curse of dimensionality: the case of goodness-of-fit 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, the "curse of dimensionality" is often overlooked or even explicitly contradicted by claims of parametric convergence rates. This paper addresses this discrepancy by demonstrating that such optimistic rates typically rely on narrow, directional alternatives. By extending the foundational work of Ingster (1987), we establish that the minimax rate for nonparametric testing in $d$ dimensions is inherently nonparametric and exhibits a prototypical curse of dimensionality. Furthermore, we demonstrate that a properly tuned, classic chi-squared test achieves this minimax rate and can adapt to the intrinsic dimensionality of the data. Finally, we propose a multiscale version of the chi-squared test that adapts to unknown smoothness with minimal loss in power.

Introduction

The two-sample goodness-of-fit test is a cornerstone of statistical inference: given two sets of independent observations, $X$ and $Y$, we must determine if they originate from the same underlying distribution ($F = G$). As datasets grow in complexity and dimensionality—spanning fields from genomics to high-frequency finance—the demand for robust high-dimensional testing has increased.

Recent literature has suggested that certain modern tests can achieve "parametric" rates, where the error decreases at a speed independent of the number of dimensions $d$. However, this paper argues that these results are often a mirage. Such rates are achievable only when the difference between distributions is restricted to a specific direction or a simple shift. When considering general nonparametric alternatives—where the difference could be any smooth function—the statistical difficulty scales exponentially with dimension. This paper seeks to formalize these limits and identify tests that can reach them.

Establishing the Minimax Lower Bound

To understand the fundamental limits of testing, we employ minimax analysis. This framework identifies the best possible performance a test can guarantee against the most difficult alternative distribution within a specific class—in this case, densities within a Hölder smoothness class $s$ supported on a unit hypercube $[0, 1]^d$.

By extending Ingster’s (1987) univariate results to $d$ dimensions, we prove that the minimax rate for the detection boundary is proportional to:

$$m^{-\frac{2s}{4s+d}}$$

where $m$ is the sample size. Because the dimension $d$ appears in the denominator of the exponent, the sample size required to maintain a constant level of power must grow exponentially as $d$ increases. This is the mathematical manifestation of the curse of dimensionality in goodness-of-fit testing. Any claim of a dimension-independent rate necessarily ignores the complexity of general nonparametric alternatives.

The Optimality of the Chi-Squared Test

A surprising finding of this research is the efficacy of the classic chi-squared test. While often dismissed as a "toy" method in the era of complex kernel machines, a chi-squared test based on a specific partitioning of the space into bins is actually minimax optimal.

If the bin size is correctly calibrated to the expected smoothness $s$ of the densities, the chi-squared test achieves the theoretical "speed limit" established by our lower bound. This suggests that for the purposes of minimax testing, the structural simplicity of binning is as powerful as more sophisticated modern methods.

Adaptivity to Manifolds and Smoothness

Real-world high-dimensional data often possesses hidden structure, frequently residing on a lower-dimensional manifold (the "intrinsic dimension" $d_0$) rather than filling the entire ambient space $d$. We show that the chi-squared test is naturally adaptive to this geometry. If the data lies on a manifold of dimension $d_0 < d$, the test’s performance automatically improves to the rate associated with $d_0$, effectively bypassing the curse of the ambient dimension.

Furthermore, because the optimal bin size depends on the unknown smoothness $s$, we propose a multiscale chi-squared test. Following the spirit of Ingster (2000), this test evaluates multiple bin sizes simultaneously. Using a Bonferroni correction to manage multiple comparisons, we prove that this multiscale approach is adaptive to unknown smoothness. It achieves the minimax rate within a small logarithmic factor ($\sqrt{\log m}$), providing a practical solution when the characteristics of the underlying distributions are unknown.

Conclusion and Future Directions

This work reaffirms that the curse of dimensionality is an inescapable reality in nonparametric testing. While directional tests may offer faster rates, they are blind to complex, non-linear differences between distributions. The chi-squared test, despite its age, remains a powerful and optimal tool when properly adapted to the multiscale nature of the problem.

Two primary avenues for future research remain. First, there is a small theoretical gap of $\sqrt{\log m}$ between the adaptive multiscale test and the absolute lower bound; closing this may require more refined probabilistic inequalities. Second, while statistically efficient, implementing hyper-rectangular binning in very high dimensions is computationally demanding. Future work should investigate the use of dyadic trees or space-filling curves to maintain statistical optimality while improving computational scalability.

Summary updated

Abstract

Despite a substantial literature on nonparametric two-sample goodness-of-fit testing in arbitrary dimensions, there is no mention there of any curse of dimensionality. In fact, in some publications, a parametric rate is derived. As we discuss below, this is because a directional alternative is considered. Indeed, even in dimension one, Ingster, Y. I. [(1987). Minimax testing of nonparametric hypotheses on a distribution density in the l_p metrics. Theory of Probability & Its Applications, 31(2), 333–337] has shown that the minimax rate is not parametric. In this paper, we extend his results to arbitrary dimension and confirm that the minimax rate is not only nonparametric, exhibits but also a prototypical curse of dimensionality. We further extend Ingster's work to show that the chi-squared test achieves the minimax rate. Moreover, we show that the test adapts to the intrinsic dimensionality of the data. Finally, in the spirit of Ingster, Y. I. [(2000). Adaptive chi-square tests. Journal of Mathematical Sciences, 99(2), 1110–1119], we consider a multiscale version of the chi-square test, showing that one can adapt to unknown smoothness without much loss in power.
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 testing in arbitrary dimension}},
  journal = {Journal of Nonparametric Statistics},
  year = {2018},
  doi = {10.1080/10485252.2018.1435875},
}
Figure