Abstract
Numerous problems in applied mathematics and statistics require integrating a function f over a high-dimensional domain. For example, estimating the partition function of a graphical model for a fixed set of parameters requires integrating (summing) its unnormalized probability function f over all possible configurations (value assignments). The most common methods for performing such integration stochastically involve Markov Chains (MCMC).
We present an alternative to MCMC based on ideas from the theory of modern error-correcting codes. Specifically, we will see that stochastically integrating a non-negative function f over its entire domain can often be achieved at the cost of merely maximizing f over a few random subsets of its domain. The key lies in specifying subsets with appropriate statistical properties in a manner than does not dramatically affect the capacity for maximization. Using real-life CNF formulas as benchmarks, our approach of encoding the subsets as cosets of LDPC error-correcting codes allows us to achieve dramatic speedup and levels of accuracy that were previously completely unattainable.
Based on joint work with Pei Jiang.