📊 statistics

Conjugate Generalized Bayesian Inference for Discrete Doubly Intractable Problems

This paper introduces a computationally efficient generalized Bayesian inference method for discrete doubly intractable problems that enables conjugate, closed-form, or Gibbs-based MCMC solutions within exponential family models, offering significant speed improvements over existing state-of-the-art techniques while maintaining theoretical guarantees.

Original authors: William Laplante, Matias Altamirano, Jeremias Knoblauch, Andrew Duncan, François-Xavier Briol

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: William Laplante, Matias Altamirano, Jeremias Knoblauch, Andrew Duncan, François-Xavier Briol

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but the crime scene is a massive, foggy city where the rules of probability are hidden behind a locked door. In the world of statistics, this is what happens when we try to understand complex data, like the spread of a disease or the patterns in a social network. Usually, to solve the mystery, we need to calculate a "normalization constant"—a giant, invisible number that makes all the probabilities add up to exactly 100%. Think of it like trying to weigh a cloud: you know it's there, but you can't put it on a scale because it's too big and too messy to measure directly. Without this number, the standard math tools we use to update our beliefs (a process called Bayesian inference) get stuck. They have to take a slow, winding path through the fog, guessing their way forward, which can take days or even weeks of computer time.

This paper tackles that exact problem, specifically for data that comes in whole numbers, like counts of people, animals, or pixels. The authors are working on a method to bypass the locked door entirely. Instead of trying to weigh the whole cloud, they propose a clever trick: look at the differences between the clouds. By comparing how likely one specific outcome is versus a slightly different one, they can figure out the rules of the game without ever needing to know the total weight of the cloud. This allows them to update their beliefs instantly, turning a multi-day calculation into a matter of seconds.

The Paper's Big Idea: A Shortcut Through the Fog

The paper introduces a new mathematical tool called "Log-Ratio Matching" (LRM), which acts like a super-fast GPS for these tricky, foggy problems. The authors, led by William Laplante and his team, show that for a huge class of models involving discrete counts (like the number of times a bird sings or the number of pixels in an image), this new method is not just fast—it's a game-changer.

Here is the core discovery: The team created a new way to measure how well a model fits the data that doesn't require that impossible-to-calculate "total weight" number. Because of this, they can derive a "conjugate" posterior. In plain English, this means the math works out so neatly that the computer doesn't have to guess and check thousands of times. Instead, it can write down the answer in a single, clean formula. It's the difference between trying to find a needle in a haystack by pulling out one piece of hay at a time (the old way) versus having a magnet that instantly pulls the needle right to the surface (the new way).

What They Found and How Fast It Is

The authors tested their method on some very difficult puzzles, including models used to analyze cancer gene data, satellite images of ice sheets, and crime statistics. In every case, their new method, which they call LRM-Bayes, produced results that were nearly identical to the standard, slow methods. But the speed difference was staggering.

In their experiments, the new method was between 10 and 6,000 times faster than the best existing techniques. For example, in one test with a complex model of breast cancer data, a method that usually takes about 31.6 minutes to run was completed in just 2.2 seconds using their approach. In another test involving a time-series model for crime data, a process that took 20 minutes was done in roughly 1 minute. Even in the most extreme cases, they saw speedups of over 1,200 times.

What They Don't Claim

It is important to note what this paper does not say. The authors do not claim that their method works for every type of data problem; it is specifically designed for "exponential family" models of discrete data (like counts). They also do not claim that their method is perfect in every single scenario. In one experiment with a satellite image of Antarctic ice, they found that the model they were using didn't perfectly match the real-world data (a situation called "misspecification"). In that case, their fast method gave a result that was slightly different from the slow method, but they argue this is because the model itself was the issue, not the speed of the calculation. They explicitly state that their method is a computational shortcut, not a magic wand that fixes bad models.

The Bottom Line

The paper suggests that by changing how we measure the "fit" of a model—focusing on ratios rather than totals—we can unlock the ability to solve complex statistical problems in seconds that previously took hours. The authors proved mathematically that this shortcut is reliable and that as you get more data, the answer gets closer and closer to the truth. While they acknowledge that there is still work to be done on how to choose the best settings for the method, the results show that for many real-world problems involving counts and networks, we no longer have to wait days for an answer. We can get the answer almost instantly, opening the door to analyzing much larger and more complex datasets than ever before.

Technical Summary: Conjugate Generalized Bayesian Inference for Discrete Doubly Intractable Problems

1. Problem Statement

The paper addresses doubly intractable problems in Bayesian inference, a scenario common in discrete statistical models where both the likelihood and the posterior distribution are available only in unnormalized form. Specifically, the normalization constant (partition function) $Z(\theta)$ of the likelihood $p_\theta(x) = \tilde{p}_\theta(x)/Z(\theta)$ cannot be computed or efficiently approximated due to summations over large or infinite state spaces.

In standard Bayesian inference, the posterior is proportional to the likelihood times the prior. However, when $Z(\theta)$ is intractable, the posterior normalization constant becomes a function of the data and parameters that is also intractable. Existing solutions typically rely on:

MCMC with auxiliary variables (e.g., Exchange algorithm), which are computationally expensive and require tuning.
Approximations (e.g., pseudo-likelihood, variational Bayes), which may introduce bias or misspecification.
Generalized Bayesian Inference (GBI) using divergences like the Discrete Fisher Divergence (DFD) (Matsubara et al., 2023). While DFD-Bayes avoids computing $Z(\theta)$ , it fails to yield conjugate posteriors. Consequently, it still requires MCMC sampling, suffering from issues like slow mixing in high dimensions, multi-modality, and the need for convergence checks.

The core challenge is to develop a method for discrete intractable models that eliminates the need for MCMC by achieving conjugacy (closed-form or Gibbs-based updates) while maintaining the computational efficiency of GBI.

2. Methodology

2.1 Log-Ratio Matching (LRM) Divergence

The authors propose a novel statistical divergence called Log-Ratio Matching (LRM) to construct a generalized posterior.

Matching Sets: For a data point $x$ , a matching set $M(x)$ is defined as a finite set of neighboring states $\{M_j(x)\}_{j \in J}$ . This set is constructed based on the data structure (e.g., flipping bits in a lattice or incrementing counts).
Definition: The LRM divergence between a data-generating process $q_0$ and a model $p_\theta$ is defined as the expected squared difference between the log-ratios of the model and the data:
$D_{LRM}(q_0 \| p_\theta) = \mathbb{E}_{x \sim q_0} \left[ \frac{1}{|M(x)|} \sum_{x' \in M(x)} \left( \log \frac{p_\theta(x')}{p_\theta(x)} - \log \frac{q_0(x')}{q_0(x)} \right)^2 \right]$
Key Property: Unlike standard divergences, $D_{LRM}$ does not depend on the intractable normalization constant $Z(\theta)$ because the ratio $p_\theta(x')/p_\theta(x)$ cancels out $Z(\theta)$ .
Theoretical Validity: Under the assumption that the matching set induces a connected graph over the state space, $D_{LRM}(q_0 \| p_\theta) = 0$ if and only if $q_0 = p_\theta$ .

2.2 The LRM-Bayes Posterior

Using the LRM divergence, the authors define a loss function $L_{LRM}(\theta)$ and a corresponding estimator $\hat{L}_{LRM}^n(\theta)$ based on data $\{x_i\}_{i=1}^n$ and an estimated probability mass function $\hat{q}$ (typically via Laplace smoothing). The LRM-Bayes posterior is defined as:
$\hat{\pi}_M^\beta(\theta; \{x_i\}) \propto \exp\left( -\beta n \hat{L}_{LRM}^n(\theta) \right) \pi(\theta)$
where $\beta > 0$ is a scaling parameter.

2.3 Conjugacy for Exponential Families

The primary theoretical breakthrough is that for discrete exponential family models of the form $p_\theta(x) \propto \exp(\eta(\theta)^\top T(x) + B(x))$ , the LRM loss is quadratic in the natural parameters $\eta(\theta)$ .

Loss Structure: $\hat{L}_{LRM}^n(\theta) = \eta(\theta)^\top \Lambda_n \eta(\theta) - 2\eta(\theta)^\top \nu_n + C$ .
Conjugate Update: If the prior $\pi(\eta)$ is exponentially quadratic (e.g., a multivariate Gaussian), the posterior is also a multivariate Gaussian (or a truncated Gaussian if the parameter space is constrained).
Computational Implication: This allows for closed-form inference (computing mean and covariance matrices) without MCMC.
Partial Conjugacy: For models where the loss is quadratic in only a subset of parameters (e.g., autoregressive time series or models with horseshoe priors), the method enables exact Gibbs updates for those blocks, significantly accelerating MCMC mixing compared to standard approaches.

3. Key Contributions

Novel Divergence: Introduction of the Log-Ratio Matching (LRM) divergence, which bypasses the normalization constant and induces a quadratic loss for exponential families.
Conjugate Generalized Posterior: Demonstration that LRM-Bayes yields conjugate posteriors for discrete intractable exponential families, a property previously unattainable with discrete divergences like DFD.
Computational Efficiency: The method replaces expensive MCMC sampling with closed-form matrix operations or fast Gibbs updates, reducing computational time by orders of magnitude.
Theoretical Guarantees: Proof of posterior consistency and a Bernstein-von Mises theorem, showing that the LRM-Bayes posterior is asymptotically Gaussian and concentrates around the minimizer of the true loss under mild regularity conditions.
Flexibility: The framework supports partial conjugacy for complex priors (e.g., horseshoe, spike-and-slab) and time-series models, enabling exact updates for specific parameter blocks.

4. Experimental Results

The method was evaluated on several challenging discrete intractable models:

Univariate Conway-Maxwell-Poisson (CMP):
- LRM-Bayes produced posterior credible regions nearly identical to standard MCMC and DFD-Bayes.
- Speed: LRM was >100x faster than DFD-Bayes and >20x faster than standard MCMC for moderate sample sizes.
Multivariate CMP Graphical Model (Breast Cancer Data, $d=10, p=65$ ):
- Standard Bayesian inference was computationally infeasible.
- LRM-Bayes provided reliable posterior predictive distributions.
- Speed: LRM was >35x faster than DFD-Bayes (approx. 2 seconds vs. 31 minutes).
- Sparsity: The method successfully incorporated horseshoe and spike-and-slab priors, inducing sparsity while maintaining exact Gibbs updates.
Autoregressive Count Time Series (Crime Data):
- Demonstrated partial conjugacy where the autoregressive parameter $\phi$ was updated via Metropolis-Hastings, while other parameters were updated via exact Gibbs steps.
- Speed: LRM-Bayes mixed in ~1 minute, whereas standard Approximate MCMC required ~20 minutes (20x speedup).
Markov Random Fields (Ising and Potts Models):
- Ising Model: LRM recovered parameters as accurately as DFD and pseudo-likelihood methods but was ~10x faster.
- Potts Model (Antarctic Ice Data): LRM was >35x faster than auxiliary variable MCMC and significantly faster than DFD/PL. The posterior was comparable to other methods, though the authors note the model itself was misspecified for the heterogeneous data.

5. Significance and Claims

The paper claims that LRM-Bayes provides a computationally efficient alternative to existing methods for discrete doubly intractable problems. Its significance lies in:

Bridging the Gap: It replicates the computational benefits of continuous-domain KSD-Bayes (Matsubara et al., 2022) for discrete domains, a feat previously unachieved.
Scalability: By achieving conjugacy, it removes the dependency on the number of MCMC iterations ( $T$ ), reducing complexity from $O(ndpT)$ to $O(ndp^2 + p^3)$ .
Practical Utility: It enables the application of complex, flexible models (e.g., high-dimensional graphical models, time series with heavy-tailed priors) that were previously too computationally expensive for Bayesian analysis.
Theoretical Soundness: The method is not just a heuristic; it is supported by rigorous asymptotic theory ensuring consistency and normality.

The authors remain modest regarding the scope, noting that the method relies on the estimation of a reference PMF ( $\hat{q}$ ) and that the choice of the matching set $M$ influences the posterior concentration, though estimating the scaling parameter $\beta$ helps mitigate this sensitivity. The work is positioned as a step toward broader applications in simulation-based inference and latent variable models.