Hypothesis Testing For Densities and High-Dimensional Multinomials:
  Sharp Local Minimax Rates
  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.
