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

By Stefano Ermon, Carla P. Gomes, Ashish Sabharwal, Bart Selman. 2013

132 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications, Representation & Self-Supervised Learning, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Representation & Self-Supervised Learning

In Signal Processing

Citations in the corpus

Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “Our work provides a fast deterministic alternative to recently proposed Perturb-and-MAP algorithms (Papandreou and Yuille, 2011; Hazan and Jaakkola, 2012; Ermon et al., 2013).”
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “For the unweighted case (MC), hashing-based methods (Ermon et al. 2013; Chakraborty, Meel, and Vardi 2013) (see also (Chakraborty, Meel, and Vardi 2016)) produce an approximation with probabilistic guarantees.”
Learning and Inference via Maximum Inner Product Search (2016, background): “Problems with large output spaces arise naturally in many fields including NLP and computer vision (Bengio et al., 2006; Andreas et al., 2015; Devlin et al., 2014), and pose numerous challenges to inference and learning algorithms (Ermon et al., 2013a).”
Embed and Project: Discrete Sampling with Universal Hashing (2013, methodology): “This parallels recent work [9] that extended s imilar ideas for unweighted counting to the weighted counting world, addressing the problem of disc rete integration.”
Marginal Inference in MRFs using Frank-Wolfe (2013, background): “Recently, two different algorithms have been proposed that reduce marginal inference in a Markov Random Field (MRF) to multiple instances of MAP inference [1] [2].”