Taming the Curse of Dimensionality: Discrete Integration by Hashing and Optimization

Abstract

Integration is affected by the curse of dimensionality and quickly becomes intractable as the dimensionality of the problem grows. We propose a randomized algorithm that, with high probability, gives a constant-factor approximation of a general discrete integral defined over an exponentially large set. This algorithm relies on solving only a small number of instances of a discrete combinatorial optimization problem subject to randomly generated parity constraints used as a hash function. As an application, we demonstrate that with a small number of MAP queries we can efficiently approximate the partition function of discrete graphical models, which can in turn be used, for instance, for marginal computation or model selection.

References in corpus (4)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Tightening LP Relaxations for MAP using Message Passing
• Improving the Accuracy and Efficiency of MAP Inference for Markov Logic
• On the Partition Function and Random Maximum A-Posteriori Perturbations

Cited by in corpus (7)

• Flexible constrained sampling with guarantees for pattern mining
• Belief Propagation Neural Networks
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
• Solution Enumeration by Optimality in Answer Set Programming
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma
• Model Counting meets F0 Estimation
• Phase Transition Behavior of Cardinality and XOR Constraints