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