Learning Ising models from one or multiple samples

DOI10.1145/3406325.3451074MaRDI QIDQ6065181zbMATH OpenOpenAlexFDO

Authors Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala

Publication date 14 November 2023

Published in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.09370

zbMATH Keywords

concentration inequalitiesdependent dataIsing modellow temperaturemaximum likelihood estimationsingle-sample estimation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: There have been two separate lines of work on estimating Ising models: (1) estimating them from multiple independent samples under minimal assumptions about the model's interaction matrix; and (2) estimating them from one sample in restrictive settings. We propose a unified framework that smoothly interpolates between these two settings, enabling significantly richer estimation guarantees from one, a few, or many samples. Our main theorem provides guarantees for one-sample estimation, quantifying the estimation error in terms of the metric entropy of a family of interaction matrices. As corollaries of our main theorem, we derive bounds when the model's interaction matrix is a (sparse) linear combination of known matrices, or it belongs to a finite set, or to a high-dimensional manifold. In fact, our main result handles multiple independent samples by viewing them as one sample from a larger model, and can be used to derive estimation bounds that are qualitatively similar to those obtained in the afore-described multiple-sample literature. Our technical approach benefits from sparsifying a model's interaction network, conditioning on subsets of variables that make the dependencies in the resulting conditional distribution sufficiently weak. We use this sparsification technique to prove strong concentration and anti-concentration results for the Ising model, which we believe have applications beyond the scope of this paper.

Cited in

(7)

• Modified log-Sobolev inequalities, Beckner inequalities and moment estimates
• Concentration inequalities for some negatively dependent binary random variables
• One-shot learning for k-SAT
• On sampling from Ising models with spectral constraints
• High dimensional logistic regression under network dependence
• Phase transitions of the maximum likelihood estimators in the p-spin Curie-Weiss model
• One-shot learning for \(k\)-SAT

This page was built for publication: Learning Ising models from one or multiple samples

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065181)