Abstract
The statistical analysis of discrete data has been the subject of extensive research dating back to the work of Pearson. In this survey, we review recently developed methods for testing hypotheses about high-dimensional multinomials. Traditional tests, such as the $\chi^2$ test and the likelihood ratio test (LRT), often exhibit poor power in high-dimensional settings where the number of categories $d$ is large relative to the sample size $n$. Much of the research in this area has focused on finding tests with asymptotically Normal limits and developing the stringent conditions under which these limits hold. We argue that this perspective suffers from a significant deficiency: it can exclude many high-dimensional cases where, despite having non-Normal null distributions, carefully designed tests can achieve high power. Finally, we illustrate that taking a minimax perspective and considering refinements of this approach can lead naturally to powerful and practical tests.
1. Introduction: The High-Dimensional Challenge
In classical statistics, goodness-of-fit and two-sample testing for multinomial data are typically handled using Pearson’s $\chi^2$ test or the Likelihood Ratio Test (LRT). These methods were developed for the "fixed $d$, large $n$" regime, where the number of categories is small and the number of observations is sufficient to populate each category.
However, modern datasets—ranging from genomics and natural language processing to large-scale social surveys—frequently involve "sparse arrays" where the number of possible categories $d$ is massive, often far exceeding the sample size $n$. In these high-dimensional settings, classical assumptions collapse:
- Loss of Power: Traditional tests lose the ability to detect subtle but important deviations from the null hypothesis.
- Invalid Asymptotics: The assumption that test statistics follow a $\chi^2$ or Normal distribution breaks down when expected counts are low.
- The "Zero" Problem: Many categories contain zero observations, causing standard formulas (particularly the LRT) to behave erratically or become undefined.
2. The Minimax Perspective
This review advocates for a shift away from traditional asymptotic theory toward a minimax perspective. Rather than focusing on "local alternatives" (infinitesimal deviations from the null), researchers identify the critical radius ($\epsilon_n$). This represents the minimum distance (typically in $L_1$ or Total Variation distance) a distribution must be from the null for a test to reliably detect the difference with high probability.
One of the most significant theoretical insights in this field is that testing is fundamentally easier than estimation. To estimate a high-dimensional distribution to a certain accuracy in $L_1$ distance, one typically requires $n \approx d$ samples. However, to simply test if a distribution matches a known null, one only needs $n \approx \sqrt{d}$ samples. This "square-root" reduction in sample complexity is a cornerstone of modern high-dimensional inference.
3. Methodological Innovations
To address the limitations of classical tests, several novel statistics have been proposed:
- Truncated $\chi^2$ Test: Standard $\chi^2$ tests can be dominated by categories with very small expected probabilities, where the variance is high and the signal-to-noise ratio is low. By capping or truncating the denominator in the $\chi^2$ formula, researchers can prevent these "noisy" categories from washing out the actual signal.
- The $L_{2/3}$-Norm Test: Work by Valiant & Valiant introduced a test statistic based on the $L_{2/3}$ norm of the distribution. While mathematically non-intuitive compared to the standard $L_2$ (Euclidean) norm, this approach has been shown to achieve optimal detection rates in high dimensions.
- Local Minimaxity: The difficulty of a test is not uniform across the probability simplex. Testing against a Uniform null distribution is significantly harder than testing against a highly sparse or skewed (e.g., power-law) distribution. Modern methods account for this geometry to provide more sensitive results.
- Simulation-Based Thresholds: Because we cannot rely on Normal limits when $d \gg n$, the review highlights the importance of using permutation tests or direct simulation from the null distribution to determine rejection thresholds, ensuring precise control over Type I error (false positives).
4. Key Results and Empirical Observations
Theoretical analysis and simulations using synthetic datasets (such as power-law and uniform distributions) reveal several critical findings:
- Global Rates: The global minimax separation rate for goodness-of-fit is approximately $d^{1/4}/\sqrt{n}$. This defines the mathematical "frontier" of what is detectable.
- Two-Sample Complexity: Testing whether two unknown samples originate from the same distribution is strictly harder than goodness-of-fit testing. The minimax rate for two-sample testing in high dimensions is $d^{1/2}/n^{3/4}$.
- LRT Failure: In high-dimensional regimes, the Likelihood Ratio Test—often considered the "gold standard"—can actually perform worse than the $\chi^2$ test, particularly when the null distribution is not uniform.
5. Limitations and Future Directions
While the minimax theory for simple null hypotheses (testing against a single fixed distribution) is well-developed, several challenges remain:
- Composite Nulls: Testing whether a distribution belongs to a family (e.g., "Is this distribution monotonic?" or "Is it Poisson?") is significantly more complex and lacks a complete minimax theory.
- Practical Constants: Many theoretically optimal tests involve unspecified constants that make them difficult to implement in software without further calibration.
- Beyond Testing: Extending these high-dimensional insights to the construction of confidence intervals and point estimation remains the next major frontier in multinomial statistics.
6. Conclusion
High-dimensional multinomial testing requires a departure from the "Normal approximation" mindset. By embracing the minimax framework and focusing on the specific geometry of the probability simplex, statisticians can develop tests that remain powerful even when data is sparse and categories are numerous.
Summary updated