Likelihood-free hypothesis testing

Patrik Róbert Gerber, Yury Polyanskiy

TL;DR

This paper introduces a theoretical framework for "likelihood-free hypothesis testing," where we test hypotheses about data distributions without direct access to their likelihood functions. The authors establish a fundamental trade-off between the number of simulated samples and the number of real data samples needed for accurate testing, revealing that this trade-off depends crucially on the complexity of the underlying distributions.

What Problem Does This Paper Address?

In many scientific fields, like particle physics or climate science, we often have access to complex, high-fidelity simulators that can generate data according to a model, but we cannot directly compute the probability of observing a given data point (the likelihood function). This is known as the "likelihood-free" setting. A key task in these fields is hypothesis testing: deciding which of two competing models (or hypotheses) best explains the observed experimental data. Traditional statistical methods, like the Neyman-Pearson test, rely heavily on likelihood functions, making them unusable in the likelihood-free setting. This paper addresses the challenge of performing hypothesis testing when only simulated data from candidate models is available, and the true data-generating process is unknown. Specifically, it investigates the sample complexity – how many simulated and real data samples are needed – for such likelihood-free hypothesis tests.

Methods

The core of the paper's contribution lies in characterizing the minimax sample complexity of likelihood-free hypothesis testing (LFHT). The authors introduce a framework that unifies LFHT with other fundamental statistical problems like goodness-of-fit testing, two-sample testing, and density estimation. They leverage techniques from non-parametric statistics and information theory, particularly focusing on the L²-distance test statistic, which compares empirical L²-norms of probability distributions. A key aspect of their methodology is the discovery of a fundamental trade-off between the number of simulated samples ($n$) and the number of real data samples ($m$) required for successful testing. This trade-off is shown to be dependent on the separation ($\epsilon$) between the hypotheses and the class of distributions being considered. They also employ "flattening" techniques, which transform distributions to mitigate the effects of massive empirical count differences in certain bins, allowing for more robust testing.

Datasets

Not discussed in the paper. The paper deals with theoretical properties of distributions and sample complexity, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Fundamental Trade-off: The paper reveals a non-trivial trade-off between the number of simulated samples ($n$) and real data samples ($m$) for likelihood-free hypothesis testing. This trade-off is not simply about having "enough" data, but about the balance between simulated and real data.
  • Interpolation between Statistical Problems: LFHT naturally interpolates between classical statistical problems. The sample complexity region for LFHT can be seen as encompassing regions for binary hypothesis testing, two-sample testing, and goodness-of-fit testing, providing a unified perspective.
  • Distribution Class Matters: The specific class of distributions significantly impacts the sample complexity. Some classes exhibit simpler trade-offs, while others, like discrete distributions on large alphabets, show more complex behavior, including phase transitions.
  • L²-Distance Test Optimality: The paper shows that a simple L²-distance based test statistic, which compares empirical L²-norms, is surprisingly optimal for LFHT in many "regular" settings, even when the simulated samples are insufficient to accurately estimate the underlying distributions.
  • Robustness: The framework extends to robust hypothesis testing, where tests are designed to be less sensitive to model misspecification.

Key Results

The paper establishes precise characterizations of the sample complexity for LFHT across several classes of distributions (smooth densities, Gaussian sequence models, and discrete distributions). For "regular" classes (like smooth densities and bounded discrete distributions), the sample complexity is characterized by the condition $m \ge 1/\epsilon^2$, $n \ge n_{GoF}$, and $mn \ge n_{GoF}^2$, where $n_{GoF}$ is the sample complexity for goodness-of-fit testing. For general discrete distributions, a more complex phase transition is observed when the alphabet size ($k$) is large relative to the separation ($\epsilon$). The paper also shows that the L²-distance test achieves these minimax optimal rates.

Limitations and Future Work

The authors acknowledge that their analysis for the Hellinger distance case is limited and suggest further research in this direction. They also pose several open problems, including:

  • Studying the dependence on the number of hypotheses ($M > 2$) in multi-hypothesis testing.
  • Defining and studying local minimax rates for LFHT.
  • Investigating LFHT under Hellinger separation for various distribution classes.
  • Characterizing "regular" models where LFHT, goodness-of-fit testing, and two-sample testing have equivalent hardness.
  • Studying the competitive optimality of algorithms, particularly Scheffé's test.

Summary updated

Abstract

Consider the problem of binary hypothesis testing. Given $Z$ coming from either $\mathbb P^{\otimes m}$ or $\mathbb Q^{\otimes m}$, to decide between the two with small probability of error it is sufficient and in most cases necessary to have $m \asymp 1/\epsilon^2$, where $\epsilon$ measures the separation between $\mathbb P$ and $\mathbb Q$ in total variation ($\mathsf{TV}$). Achieving this, however, requires complete knowledge of the distributions and can be done, for example, using the Neyman-Pearson test. In this paper we consider a variation of the problem, which we call likelihood-free (or simulation-based) hypothesis testing, where access to $\mathbb P$ and $\mathbb Q$ is given through $n$ iid observations from each. In the case when $\mathbb P,\mathbb Q$ are assumed to belong to a non-parametric family $\mathcal P$, we demonstrate the existence of a fundamental trade-off between $n$ and $m$ given by $nm \asymp n^2_\mathsf{GoF}(\epsilon,\cal P)$, where $n_\mathsf{GoF}$ is the minimax sample complexity of testing between the hypotheses $H_0: \mathbb P= \mathbb Q$ vs $H_1: \mathsf{TV}(\mathbb P,\mathbb Q) \ge \epsilon$. We show this for three families of distributions: $\beta$-smooth densities supported on $[0,1]^d$, the Gaussian sequence model over a Sobolev ellipsoid, and the collection of distributions on alphabet $[k]=\{1,2,\dots,k\}$ with pmfs bounded by $c/k$ for fixed $c$. For the larger family of all distributions on $[k]$ we obtain a more complicated trade-off that exhibits a phase-transition. The test that we propose, based on the $L^2$-distance statistic of Ingster, simultaneously achieves all points on the trade-off curve for the regular classes. This demonstrates the possibility of testing without fully estimating the distributions, provided $m\gg1/\epsilon^2$.
BibTeX
@article{gerber2022likelihood,
  author = {Patrik Róbert Gerber and Yury Polyanskiy},
  title = {{Likelihood-free hypothesis testing}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2024.3412107},
}
Figure