In probabilistic graphical models, the partition function $Z$ is the "holy grail" of inference. It is the normalization constant that turns unnormalized scores into probabilities. Unfortunately, for most interesting models, computing $Z$ exactly is #P-hard, as it requires summing over an exponential number of possible states.
To bypass this, researchers traditionally rely on variational methods like Mean Field theory, which provide a lower bound on $\log Z$. However, these bounds are often loose and provide no guarantee of how far they are from the truth. A growing body of research focuses on tightening these bounds—moving from simple point estimates to rigorous, "guaranteed" intervals that sandwich the true value of $Z$.
Beyond Linear Approximations
Standard variational inference relies on the Jensen’s inequality lower bound, which is essentially a first-order (linear) approximation of the log-exponential function. While computationally efficient, this linear "floor" fails to capture the curvature of the true distribution, especially in systems with strong dependencies.
Martijn A. R. Leisink and Bert Kappen demonstrated that we can do much better by using higher-order polynomial expansions. In A Tighter Bound for Graphical Models, they introduced a recursive integration technique to derive third-order polynomial bounds. By matching the target function more closely at a specific point, these cubic approximations can reduce error by an order of magnitude compared to standard mean field methods, as further detailed in Means, Correlations and Bounds. The intuition is simple: a curved floor fits a curved room better than a flat one.
Turning Counting into Optimization
A different perspective on bounding $Z$ comes from the "Perturb-and-MAP" framework. Instead of trying to sum all states, can we estimate the sum by finding the single best state (MAP inference) under random noise?
Subhransu Maji, Tamir Hazan, and Tommi Jaakkola showed in On Sampling from the Gibbs Distribution with Random Maximum A-Posteriori Perturbations that MAP-based perturbations provide tighter lower bounds than traditional belief propagation, particularly in "high-signal" environments where variables are strongly coupled.
This idea was pushed further by Stefano Ermon and colleagues in Optimization With Parity Constraints: From Binary Codes to Discrete Integration. They showed that by adding random parity constraints—effectively slicing the search space into smaller, random subsets—and solving MAP queries on those slices, one can obtain "anytime" upper and lower bounds. This bridges the gap between discrete optimization and statistical integration.
The Power of Clamping
If a problem is too complex to bound accurately, why not break it into smaller pieces? This is the intuition behind "clamping" (or conditioning). By fixing the value of a specific variable, we split the partition function into two sub-problems: $Z = Z(x_i=0) + Z(x_i=1)$.
In Improving Optimization-Based Approximate Inference by Clamping Variables, Junyao Zhao and Andreas Krause proved that summing the bounds of these sub-problems is theoretically guaranteed to be at least as tight as the bound on the original problem. This creates a monotonic path to accuracy: the more variables you clamp, the tighter your bound becomes. Matej Balog and Adrian Weller extended this logic to stochastic estimators in Lost Relatives of the Gumbel Trick, showing that sequential clamping reduces the variance of partition function estimates.
Capturing Multi-modality
Standard bounds often fail because they assume the distribution has a single "hump" (mode). If the true distribution is multi-modal, a single factorized distribution will miss most of the mass.
To address this, Chris Bishop and Michael I. Jordan proposed using mixtures of factorized distributions in Mixture Representations for Inference and Learning in Boltzmann Machines. By increasing the number of components in the mixture, the error in the partition function bound decreases systematically.
Similarly, Emma Rollon and Rina Dechter looked at the internal "content" of probability tables in New Mini-Bucket Partitioning Heuristics for Bounding the Probability of Evidence. They found that by partitioning variables based on the actual numerical values in the tables—rather than just the graph structure—they could find functional alignments that significantly tighten upper bounds.
Guaranteed Conservatism
Finally, for certain classes of models, we can prove that specific approximations are always conservative. Nicholas Ruozzi showed in The Bethe Partition Function of Log-supermodular Graphical Models that for log-supermodular models, the Bethe partition function (a common approximation used in belief propagation) is a guaranteed lower bound. This provides a theoretical safety net, ensuring that the approximation never overestimates the true evidence.