Abstract
Recently, Ermon et al. (2013) pioneered a way to practically compute approximations to large-scale counting or discrete integration problems by using random hashes. These hashes reduce the problem of summation to a sequence of optimization tasks. This paper introduces MB-WISH, an algorithm that provides a constant-factor approximation for discrete integration on $q$-ary "hypergrids." By optimizing over multiple bins of a random hash function simultaneously, the authors improve the approximation factor from a poor $q^2$ to a steady value near 4, regardless of the alphabet size $q$.
The Challenge of Discrete Integration
Many fundamental problems in machine learning and statistical physics require discrete integration: the summation of a non-negative function across every possible configuration of a system. Examples include calculating the partition function of a Potts model or the permanent of a matrix.
These domains are typically exponentially large. A system with $n$ variables, each taking $q$ possible values, results in $q^n$ configurations. For even modest values of $n$ and $q$, brute-force summation is computationally impossible, placing these problems in the #P-complete complexity class. While previous methods like the WISH algorithm worked well for binary domains ($q=2$), their error grew quadratically with $q$, making them impractical for large-alphabet problems like protein folding or image alignment.
Methodology: Multi-Bin WISH (MB-WISH)
The core innovation of this work is the Multi-Bin WISH (MB-WISH) algorithm. The method relies on the statistical relationship between the maximum value of a function in a random subset (a "bin") and the total sum of the function across the entire domain.
Hashing to Optimization
MB-WISH uses pairwise independent hash functions to partition the domain into bins. Instead of performing a direct sum, it utilizes an optimization oracle (such as an Integer Linear Programming solver) to find the maximum weight within these bins.
The Multi-Bin Innovation
Unlike the standard WISH approach, which examines one bin at a time, MB-WISH looks at multiple bins simultaneously. In a $q$-ary setting, this is implemented efficiently using inequality constraints within an ILP solver. By grouping bins, the algorithm "boosts" the probability of finding high-weight elements, stabilizing the approximation. The authors further refine this into an "Unconstrained MB-WISH" using generator-matrix approaches from coding theory, which simplifies the oracle's task by removing complex parity constraints.
Key Results and Empirical Performance
The authors prove that by selecting the number of bins ($r$) correctly, they can achieve an approximation factor of roughly $4(1 + \epsilon)^2$. This is a significant theoretical leap over the previous $q^2$ bound. For a 5-state Potts model, where the old method yielded a 25-approximation, MB-WISH provides a 6.25-approximation.
Empirical evaluations on synthetic Potts models and real-world constraint satisfaction problems (CSPs) demonstrate that MB-WISH is highly accurate. As shown in the comparison above, MB-WISH estimates for the log-partition function track very closely with exact methods like Belief Propagation (BP) and often outperform Markov Chain Monte Carlo (MCMC) methods in terms of stability and accuracy as the system size $n$ increases.
Conclusion and Future Directions
MB-WISH successfully breaks the $q$-dependency that previously limited hashing-based integration. By treating bins as cosets of a linear code, the authors provide a robust framework for high-dimensional summation.
However, challenges remain. The runtime is still dependent on the efficiency of NP-hard optimization solvers. Additionally, the current mathematical framework requires the alphabet size $q$ to be a prime power. Future work may focus on extending these techniques to arbitrary integers and designing "oracle-friendly" hash functions that are easier for solvers to process while maintaining necessary statistical properties.
Summary updated