# Hypothesis Testing For Densities and High-Dimensional Multinomials: Sharp Local Minimax Rates

arXiv: https://arxiv.org/abs/1706.10003 · HTML: https://mlsanity.com/paper/1706.10003/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2017.

## Built on by (most cited first, 11 of 11)

- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [The Fundamental Limits of Structure-Agnostic Functional Estimation](https://mlsanity.com/paper/2305.04116/) (2023)
- [Structure-agnostic Optimality of Doubly Robust Learning for Treatment Effect Estimation](https://mlsanity.com/paper/2402.14264/) (2024)
- [Token-Efficient Change Detection in LLM APIs](https://mlsanity.com/paper/2602.11083/) (2026)
- [The Hardness of Validating Observational Studies with Experimental Data](https://mlsanity.com/paper/2503.14795/) (2025)
- [BEAUTY Powered BEAST](https://mlsanity.com/paper/2103.00674/) (2021)
- [Optimal high-dimensional and nonparametric distributed testing under communication constraints](https://mlsanity.com/paper/2202.00968/) (2022)
- [Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates](https://mlsanity.com/paper/2211.08580/) (2022)
- [GRASP: A Goodness-of-Fit Test for Classification Learning](https://mlsanity.com/paper/2209.02064/) (2022)
- [The Minimax Risk in Testing Uniformity over Large Alphabets under Missing-Ball Alternatives](https://mlsanity.com/paper/2305.18111/) (2023)
- [Two-Sample Testing for Inhomogeneous Random Graphs in Non-Integral Lr Norms](https://mlsanity.com/paper/2609.33968/) (2026)

## Abstract (arXiv)

We consider the goodness-of-fit testing problem of distinguishing whether the data are drawn from a specified distribution, versus a composite alternative separated from the null in the total variation metric. In the discrete case, we consider goodness-of-fit testing when the null distribution has a possibly growing or unbounded number of categories. In the continuous case, we consider testing a Lipschitz density, with possibly unbounded support, in the low-smoothness regime where the Lipschitz parameter is not assumed to be constant. In contrast to existing results, we show that the minimax rate and critical testing radius in these settings depend strongly, and in a precise way, on the null distribution being tested and this motivates the study of the (local) minimax rate as a function of the null distribution. For multinomials the local minimax rate was recently studied in the work of Valiant and Valiant. We re-visit and extend their results and develop two modifications to the chi-squared test whose performance we characterize. For testing Lipschitz densities, we show that the usual binning tests are inadequate in the low-smoothness regime and we design a spatially adaptive partitioning scheme that forms the basis for our locally minimax optimal tests. Furthermore, we provide the first local minimax lower bounds for this problem which yield a sharp characterization of the dependence of the critical radius on the null hypothesis being tested. In the low-smoothness regime we also provide adaptive tests, that adapt to the unknown smoothness parameter. We illustrate our results with a variety of simulations that demonstrate the practical utility of our proposed tests.