High-Dimensional Stochastic Integration via Error-Correcting Codes

Dimitris Achlioptas UCSC, Pei Jiang
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:752-761, 2015.

Abstract

We consider the task of summing a non-negative function f over a discrete set $\Omega$, e.g., to compute the partition function of a graphical model. Ermon et al. have shown that, in a probabilistic approximate sense, summation can be reduced to maximizing f over random subsets of $\Omega$ defined by parity (XOR) constraints. Unfortunately, XORs with many variables are computationally problematic, while XORs with few variables have no guarantees. We introduce two ideas to address this problem, both motivated by the theory of error-correcting codes. The first is to maximize f over explicitly generated random affine subspaces of $\Omega$, which is equivalent to unconstrained maximization of f over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining error-correcting codes. Even though the equations in such systems only contain O(1) variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve 100x or greater speedup over the original approach and, perhaps more importantly, levels of accuracy that were completely unattainable.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-ucsc15a, title = {High-Dimensional Stochastic Integration via Error-Correcting Codes}, author = {UCSC, Dimitris Achlioptas and Jiang, Pei}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {752--761}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/ucsc15a/ucsc15a.pdf}, url = {https://proceedings.mlr.press/r13/ucsc15a.html}, abstract = {We consider the task of summing a non-negative function f over a discrete set $\Omega$, e.g., to compute the partition function of a graphical model. Ermon et al. have shown that, in a probabilistic approximate sense, summation can be reduced to maximizing f over random subsets of $\Omega$ defined by parity (XOR) constraints. Unfortunately, XORs with many variables are computationally problematic, while XORs with few variables have no guarantees. We introduce two ideas to address this problem, both motivated by the theory of error-correcting codes. The first is to maximize f over explicitly generated random affine subspaces of $\Omega$, which is equivalent to unconstrained maximization of f over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining error-correcting codes. Even though the equations in such systems only contain O(1) variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve 100x or greater speedup over the original approach and, perhaps more importantly, levels of accuracy that were completely unattainable.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T High-Dimensional Stochastic Integration via Error-Correcting Codes %A Dimitris Achlioptas UCSC %A Pei Jiang %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-ucsc15a %I PMLR %P 752--761 %U https://proceedings.mlr.press/r13/ucsc15a.html %V R13 %X We consider the task of summing a non-negative function f over a discrete set $\Omega$, e.g., to compute the partition function of a graphical model. Ermon et al. have shown that, in a probabilistic approximate sense, summation can be reduced to maximizing f over random subsets of $\Omega$ defined by parity (XOR) constraints. Unfortunately, XORs with many variables are computationally problematic, while XORs with few variables have no guarantees. We introduce two ideas to address this problem, both motivated by the theory of error-correcting codes. The first is to maximize f over explicitly generated random affine subspaces of $\Omega$, which is equivalent to unconstrained maximization of f over an exponentially smaller domain. The second idea, closer in spirit to the original approach, is to use systems of linear equations defining error-correcting codes. Even though the equations in such systems only contain O(1) variables each, their sets of solutions (codewords) have excellent statistical properties. By combining these ideas we achieve 100x or greater speedup over the original approach and, perhaps more importantly, levels of accuracy that were completely unattainable. %Z Reissued by PMLR on 04 October 2026.
APA
UCSC, D.A. & Jiang, P.. (2015). High-Dimensional Stochastic Integration via Error-Correcting Codes. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:752-761 Available from https://proceedings.mlr.press/r13/ucsc15a.html. Reissued by PMLR on 04 October 2026.

Related Material