Hypergrid Integration.pdf

High dimensional discrete integration over the hypergrid is a problem of approximating large scale counting or discrete integration problems. Ermon et al. (2013) pioneered a method to compute approximations using random hashes, reducing the counting problem into separate discrete optimization problems solvable by an NP-oracle. For a domain of integration {0, 1}n, a 16-approximation is achievable. However, for a domain {0, 1, ..., q-1}n, q > 2 (hypergrid), the straightforward extension allows a q2-approximation, which is undesirable for large q.

An improved technique achieves an approximation factor of 4 + O(1/q2) by optimizing over multiple bins of the hash functions using inequality constraints or unconstrained optimization. The NP-oracle can be simulated using an ILP solver. Simulation results support the theoretical guarantees of the algorithms. The method is applicable to various counting tasks, such as computing the partition function of the ferromagnetic Potts model.

Key aspects of the problem include:

Discrete integration over a hypergrid
Random hashes to reduce counting problems
NP-oracle solvable discrete optimization problems
Approximation factor of 4 + O(1/q2) achievable
* Applicable to various counting tasks, including ferromagnetic Potts model.

The method improves upon the straightforward extension of Ermon et al.'s method, which provides a q2-approximation, and is particularly useful for large values of q. The technique can be implemented using inequality constraints or unconstrained optimization, and the NP-oracle can be simulated using an ILP solver.