Marginals-to-Models Reducibility
Abstract
We consider a number of classical and new computational problems regarding marginal distributions, and inference in models specifying a full joint distribution. We prove general and efficient reductions between a number of these problems, which demonstrate that algorithmic progress in inference automatically yields progress for “pure data” problems. Our main technique involves formulating the problems as linear programs, and proving that the dual separation oracle for the Ellipsoid Method is provided by the target problem. This technique may be of independent interest in probabilistic inference.
Cite
Text
Roughgarden and Kearns. "Marginals-to-Models Reducibility." Neural Information Processing Systems, 2013.Markdown
[Roughgarden and Kearns. "Marginals-to-Models Reducibility." Neural Information Processing Systems, 2013.](https://mlanthology.org/neurips/2013/roughgarden2013neurips-marginalstomodels/)BibTeX
@inproceedings{roughgarden2013neurips-marginalstomodels,
title = {{Marginals-to-Models Reducibility}},
author = {Roughgarden, Tim and Kearns, Michael},
booktitle = {Neural Information Processing Systems},
year = {2013},
pages = {1043-1051},
url = {https://mlanthology.org/neurips/2013/roughgarden2013neurips-marginalstomodels/}
}