A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width

We revisit the well-studied problem of efficiently learning the underlying structure and parameters of an Ising model from data. Current algorithmic approaches achieve essentially optimal sample complexity when samples are generated i.i.d. from the stationary measure and the underlying model satisfies "width" constraints that bound the total ℓ 1 interaction involving each node. However, these assumptions are not satisfied in some important settings of interest, like temporally correlated data or more complicated models (like spin glasses) that do not satisfy width bounds.

We analyze a simple existing approach based on node-wise logistic regression, and show it provably succeeds at efficiently recovering the underlying Ising model in several new settings:

1. Given dynamically generated data from a wide variety of local Markov chains, including Glauber, block, and round-robin dynamics, logistic regression recovers the parameters with sample complexity that is optimal up to log log n factors. This generalizes work of Bresler, Gamarnik, and Shah [IEEE Trans. Inf. Theory '18], which provides a specialized algorithm for only structure recovery in bounded degree graphs from continuous-time Glauber dynamics.

2. For the Sherrington-Kirkpatrick model of spin glasses, given poly(n) independent samples, logistic regression recovers the parameters in most of the known high-temperature regime, including the entire high-temperature regime with zero field. This improves on recent work of Anari, Jain, Koehler, Pham, and Vuong [ArXiv'23] which gives distribution learning at very high temperature via a reduction of Koehler, Heckett, and Risteski [ICLR'23]. Our analysis provides a much simpler reduction from parameter learning to weaker structural properties of the Gibbs measure.