Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics

Arkopal Dutt, Andrey Lokhov, Marc D Vuffray, Sidhant Misra
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:2914-2925, 2021.

Abstract

The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-dutt21a, title = {Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics}, author = {Dutt, Arkopal and Lokhov, Andrey and Vuffray, Marc D and Misra, Sidhant}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {2914--2925}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/dutt21a/dutt21a.pdf}, url = {https://proceedings.mlr.press/v139/dutt21a.html}, abstract = {The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly.} }
Endnote
%0 Conference Paper %T Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics %A Arkopal Dutt %A Andrey Lokhov %A Marc D Vuffray %A Sidhant Misra %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-dutt21a %I PMLR %P 2914--2925 %U https://proceedings.mlr.press/v139/dutt21a.html %V 139 %X The usual setting for learning the structure and parameters of a graphical model assumes the availability of independent samples produced from the corresponding multivariate probability distribution. However, for many models the mixing time of the respective Markov chain can be very large and i.i.d. samples may not be obtained. We study the problem of reconstructing binary graphical models from correlated samples produced by a dynamical process, which is natural in many applications. We analyze the sample complexity of two estimators that are based on the interaction screening objective and the conditional likelihood loss. We observe that for samples coming from a dynamical process far from equilibrium, the sample complexity reduces exponentially compared to a dynamical process that mixes quickly.
APA
Dutt, A., Lokhov, A., Vuffray, M.D. & Misra, S.. (2021). Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:2914-2925 Available from https://proceedings.mlr.press/v139/dutt21a.html.

Related Material