Abstract
Information projections are the key building block of variational inference algorithms and are used to approximate a target probabilistic model by projecting it onto a family of tractable distributions. This paper introduces Mean Field with Random Projections (MFRP), a method that bridges the gap between the theoretical guarantees of randomized hashing and the practical efficiency of variational inference. By combining random parity constraints with standard information projections, MFRP provides provably tight lower bounds on the partition function of complex probabilistic models, often outperforming standard variational methods by hundreds of orders of magnitude.
Introduction
In probabilistic machine learning, calculating the partition function ($Z$)—the normalization constant of a distribution—is a fundamental yet computationally intractable task. For models with many interacting variables, such as Ising models or Restricted Boltzmann Machines (RBMs), computing $Z$ is "#P-hard." Existing approaches generally fall into two categories: sampling-based methods, which can be accurate but slow in high-dimensional spaces, and Variational Inference (VI), which is fast but lacks guarantees on approximation quality. When models are highly complex, standard VI methods like Mean Field can produce wildly inaccurate estimates.
Methodology: Mean Field with Random Projections (MFRP)
The authors propose a hybrid approach that simplifies the target distribution using random projections before applying information projections (I-projections).
Random Parity Constraints
The core innovation is the use of random parity constraints (e.g., $Ax = b \pmod 2$) to sub-sample the configuration space. These constraints act as a strongly universal hash function, effectively reducing the degrees of freedom in the model. Intuitively, by restricting the model to a smaller, random subset of states, the remaining distribution becomes easier for a simple family (like Mean Field) to approximate accurately.
The MFRP Algorithm
The algorithm employs a coordinate-wise ascent method to solve the optimization problem under these hard parity constraints. To handle the non-convex nature of the problem, the authors use multiple random initializations and aggregate results across different random projections using a median-based estimator. This ensures the robustness of the final partition function estimate while maintaining linear scaling with the number of variables.
Experimental Results
The MFRP method was evaluated on synthetic Ising models and real-world RBMs trained on the MNIST dataset.
Performance on Ising Models
On large binary grids with mixed interactions (both positive and negative), MFRP demonstrated exceptional performance. As shown in the figure below, the log-ratio of the MFRP estimator to standard Mean Field increases dramatically with grid size, indicating that MFRP provides lower bounds that are hundreds of orders of magnitude tighter than standard methods.
Real-World Application: RBMs and MNIST
For RBMs trained on MNIST, MFRP significantly improved log-likelihood estimates. Qualitatively, the marginals (the "average" digit the model sees) produced by MFRP were much clearer and more representative of the data, whereas standard Mean Field produced blurry or incorrect results. This demonstrates that the theoretical tightness translates into practical improvements for real-world generative models.
Conclusion
MFRP represents a significant step forward in variational inference, providing provable tightness guarantees that were previously unavailable for Mean Field methods. By integrating information geometry with randomized hashing, the authors achieve a balance between theoretical rigor and practical efficiency. Future work may extend this framework to continuous spaces or more sophisticated variational methods like the Bethe approximation.
Summary updated