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 (12)

• Flexible constrained sampling with guarantees for pattern mining
• Optimization With Parity Constraints: From Binary Codes to Discrete Integration
• Belief Propagation Neural Networks
• Closing the Gap Between Short and Long XORs for Model Counting
• Sparse Hashing for Scalable Approximate Model Counting: Theory and Practice
• Solution Enumeration by Optimality in Answer Set Programming
• Taming Discrete Integration via the Boon of Dimensionality
• Model Counting meets F0 Estimation
• Towards Efficient Discrete Integration via Adaptive Quantile Queries
• Learning Markov Random Fields for Combinatorial Structures via Sampling through Lovász Local Lemma
• High Dimensional Discrete Integration over the Hypergrid
• Phase Transition Behavior of Cardinality and XOR Constraints