Learning to Sample from Censored Markov Random Fields

Ankur Moitra, Elchanan Mossel, Colin P Sandon
Proceedings of Thirty Fourth Conference on Learning Theory, PMLR 134:3419-3451, 2021.

Abstract

We study the problem of learning Censored Markov Random Fields (abbreviated CMRFs), which are Markov Random Fields where some of the nodes are censored (i.e. not observed). We assume the CMRF is high temperature but, crucially, make no assumption about its structure. This makes structure learning impossible. Nevertheless we introduce a new definition, which we call learning to sample, that circumvents this obstacle. We give an algorithm that can learn to sample from a distribution within $\epsilon n$ earthmover distance of the target distribution for any $\epsilon > 0$. We obtain stronger results when we additionally assume high girth, as well as computational lower bounds showing that these are essentially optimal.

Cite this Paper

BibTeX
@InProceedings{pmlr-v134-moitra21a, title = {Learning to Sample from Censored Markov Random Fields}, author = {Moitra, Ankur and Mossel, Elchanan and Sandon, Colin P}, booktitle = {Proceedings of Thirty Fourth Conference on Learning Theory}, pages = {3419--3451}, year = {2021}, editor = {Belkin, Mikhail and Kpotufe, Samory}, volume = {134}, series = {Proceedings of Machine Learning Research}, month = {15--19 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v134/moitra21a/moitra21a.pdf}, url = {https://proceedings.mlr.press/v134/moitra21a.html}, abstract = {We study the problem of learning Censored Markov Random Fields (abbreviated CMRFs), which are Markov Random Fields where some of the nodes are censored (i.e. not observed). We assume the CMRF is high temperature but, crucially, make no assumption about its structure. This makes structure learning impossible. Nevertheless we introduce a new definition, which we call learning to sample, that circumvents this obstacle. We give an algorithm that can learn to sample from a distribution within $\epsilon n$ earthmover distance of the target distribution for any $\epsilon > 0$. We obtain stronger results when we additionally assume high girth, as well as computational lower bounds showing that these are essentially optimal.} }
Endnote
%0 Conference Paper %T Learning to Sample from Censored Markov Random Fields %A Ankur Moitra %A Elchanan Mossel %A Colin P Sandon %B Proceedings of Thirty Fourth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2021 %E Mikhail Belkin %E Samory Kpotufe %F pmlr-v134-moitra21a %I PMLR %P 3419--3451 %U https://proceedings.mlr.press/v134/moitra21a.html %V 134 %X We study the problem of learning Censored Markov Random Fields (abbreviated CMRFs), which are Markov Random Fields where some of the nodes are censored (i.e. not observed). We assume the CMRF is high temperature but, crucially, make no assumption about its structure. This makes structure learning impossible. Nevertheless we introduce a new definition, which we call learning to sample, that circumvents this obstacle. We give an algorithm that can learn to sample from a distribution within $\epsilon n$ earthmover distance of the target distribution for any $\epsilon > 0$. We obtain stronger results when we additionally assume high girth, as well as computational lower bounds showing that these are essentially optimal.
APA
Moitra, A., Mossel, E. & Sandon, C.P.. (2021). Learning to Sample from Censored Markov Random Fields. Proceedings of Thirty Fourth Conference on Learning Theory, in Proceedings of Machine Learning Research 134:3419-3451 Available from https://proceedings.mlr.press/v134/moitra21a.html.

Related Material