Besag-Clifford e-values for unnormalized testing

1. Problem Statement

The paper addresses a fundamental challenge in statistical hypothesis testing: testing hypotheses involving unnormalized probability distributions.

• Context: Many modern machine learning models (e.g., Markov Random Fields, Restricted Boltzmann Machines, Product of Experts) and Bayesian models define distributions only up to a normalizing constant (e.g., $p(x) \propto g(x)$). The normalizing constant $K = \int g(x)dx$ is often intractable.
• The Limitation: Standard likelihood ratio tests (LRT) rely on the ratio $q(x)/p(x)$. If $p(x)$ is unnormalized, this ratio cannot be computed exactly, rendering standard LRTs infeasible.
• The E-value Gap: While e-values (non-negative test statistics with expectation $\le 1$ under the null) are powerful tools for sequential and post-hoc testing, constructing valid e-values for unnormalized distributions is difficult. A naive unnormalized likelihood ratio (ULR) $T(x) = q(x)/g(x)$ is generally not an e-value because its expectation under the null is $1/K \neq 1$.
• Sampling Constraints: While Markov Chain Monte Carlo (MCMC) can sample from unnormalized distributions, standard MCMC samples are autocorrelated and not independent. Furthermore, obtaining exact independent samples from the null is often impossible, making standard permutation tests or simple Monte Carlo p-values difficult to apply directly for e-value construction.

2. Methodology

The authors propose Besag-Clifford e-values, a method that leverages the parallel sampling method of Besag and Clifford (1989) to normalize unnormalized test statistics into valid e-values.

Core Mechanism: The Parallel Method

To generate samples exchangeable with the observed data $X$ under the null hypothesis $P$, the method uses a "backward-forward" sampling scheme:

1. Backward Step: Given observed data $X$, evolve the Markov chain backwards for $J$ steps using the reverse transition kernel $V^J$ to generate an intermediate state $Y^{(0)}$.
2. Forward Step: From $Y^{(0)}$, evolve the chain forwards independently for $J$ steps $M$ times using the forward transition kernel $U^J$ to generate samples $Y^{(1)}, \dots, Y^{(M)}$.
3. Exchangeability: If $X \sim P$, the set $(X, Y^{(1)}, \dots, Y^{(M)})$ is exchangeable. This property holds even if the samples are autocorrelated, provided the chain is stationary and reversible (or the reverse kernel is correctly specified).

The Besag-Clifford E-value

Using these exchangeable samples, the authors define the e-value $\hat{E}_M(X)$ for a test statistic $T(x)$ (often an unnormalized likelihood ratio):
$$\hat{E}_M(X) = \frac{(M + 1)T(X)}{T(X) + \sum_{m=1}^M T(Y^{(m)})}$$

• Validity: By Proposition 1, $\hat{E}_M(X)$ is a valid e-value (i.e., $\mathbb{E}_P[\hat{E}_M(X)] \le 1$) for any finite $M$, regardless of the mixing time of the chain, as long as exchangeability holds.
• Normalization: The denominator acts as a Monte Carlo estimator of the expected value of $T(X)$ under the null, effectively normalizing the unnormalized statistic.

Asymptotic Behavior and Log-Optimality

The paper analyzes the behavior as $M \to \infty$:

• Convergence: If $T(x) \propto q(x)/p(x)$ (the true likelihood ratio), $\hat{E}_M(X)$ converges in probability to a scaled version of the true likelihood ratio:
  $$\hat{E}_M(X) \xrightarrow{P} \frac{E(X)}{\Delta_J(Y^{(0)})}$$
  where $\Delta_J(Y^{(0)})$ is a multiplicative bias term depending on the backward transition kernel and the mixing properties.
• Log-Optimality: The bias term $\Delta_J$ is related to the mixing time of the Markov chain. If the number of backward steps $J$ is chosen to be at least the KL-mixing time of the chain, $\Delta_J \approx 1$, and the Besag-Clifford e-value becomes log-optimal (approaching the performance of the true likelihood ratio).

Extensions

• Multiple Chains: To mitigate poor mixing or sensitivity to the initial backward step, the authors propose averaging $\hat{E}_M$ over $S$ independent parallel chains. This increases e-power (the expected log-growth under the alternative) while maintaining validity.
• Composite Hypotheses: The method extends to composite nulls (finite sets) by taking the minimum of e-values across the null components, and to confidence regions by inverting the test.
• Sequential Testing: The authors define Besag-Clifford e-processes for sequential data, allowing for anytime-valid testing where the stopping time can be data-dependent.

3. Key Contributions

1. Novel E-value Construction: Introduces a method to convert unnormalized test statistics (specifically unnormalized likelihood ratios) into valid e-values using the Besag-Cliffard parallel sampling scheme, bypassing the need for known normalizing constants.
2. Theoretical Guarantees:
   • Proves validity for any finite number of samples $M$.
   • Establishes that as $M \to \infty$, the e-value converges to the true likelihood ratio up to a multiplicative factor determined by the chain's mixing time.
   • Shows that with sufficient mixing steps ($J$), the method achieves approximate log-optimality.
3. Power Boosting: Demonstrates that averaging over multiple parallel MCMC chains increases e-power without sacrificing type-1 error control, addressing the issue of slow mixing in complex models.
4. Generalization: Extends the framework to composite hypotheses, confidence regions, and sequential testing (e-processes), making it applicable to a wide range of modern statistical problems.

4. Results

The paper validates the theory through simulations and a real-world application:

• AR(1) Process Simulations:
  • Verified that $\hat{E}_M(X)$ converges to the true likelihood ratio as $M$ increases.
  • Demonstrated that the bias term $\Delta_J$ diminishes as the number of backward steps $J$ increases (improving mixing).
  • Showed that increasing the number of parallel chains $S$ improves the power of the test.
• Sequential Testing (Product of Experts):
  • Applied to a sequential Product of Experts (PoE) model.
  • Results showed that using multiple chains ($S > 1$) accelerates the growth of the e-process under the alternative hypothesis compared to a single chain.
• Composite Alternative (Gaussian Parameters):
  • Compared the Besag-Clifford e-process against a standard Universal Inference (LR) e-process.
  • The Besag-Clifford process was more stable in early stages and achieved a smaller stopping time (faster detection) for weak signals, though the LR process eventually caught up as parameters were better estimated.
• Real-World Application (Shapley Supercluster):
  • Applied to galaxy velocity data to test the number of "experts" (modes) in a Product of Experts model.
  • The method decisively favored a simpler model ($W=5$) over a complex one ($W=25$), with the e-process showing exponential decay, indicating strong evidence against the complex model.

5. Significance

• Bridging MCMC and Hypothesis Testing: This work provides a rigorous theoretical bridge between MCMC sampling (typically used for estimation) and hypothesis testing, specifically for the difficult case of unnormalized distributions.
• Robustness to Intractability: It allows researchers to perform valid, powerful hypothesis tests on complex models (like RBMs and MRFs) where the normalizing constant is unknown, a common bottleneck in modern machine learning.
• Sequential and Post-hoc Validity: By utilizing e-values rather than p-values, the method guarantees type-1 error control even under optional stopping and data-dependent analysis, which is crucial for modern adaptive experiments.
• Practical Utility: The approach is computationally feasible (using standard MCMC algorithms like HMC or Gibbs sampling) and offers a clear strategy (increasing $J$ and $S$) to trade computational cost for statistical power and optimality.

In summary, the paper establishes Besag-Clifford e-values as a robust, theoretically grounded framework for testing unnormalized distributions, offering a path to log-optimal testing that scales with computational resources.