On Combining Graph-based Variance Reduction schemes


Vibhav Gogate, Rina Dechter ;
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:257-264, 2010.


In this paper, we consider two variance reduction schemes that exploit the structure of the primal graph of the graphical model: Rao-Blackwellised w-cutset sampling and AND/OR sampling. We show that the two schemes are orthogonal and can be combined to further reduce the variance. Our combination yields a new family of estimators which trade time and space with variance. We demonstrate experimentally that the new estimators are superior, often yielding an order of magnitude improvement over previous schemes on several benchmarks.

Related Material