Algorithmic Learning for Ising Models at "High-Temperature"

Ising models are fundamental high-dimensional spin systems with applications across probability theory, statistics, computer science, and economics. There has been a long line of research, dating back to Chow and Liu in the 1960s, on efficiently (i.e. polynomial samples and time) learning the parameters of the model given i.i.d. samples, with major algorithmic breakthroughs in the last decade. But what general conditions on the distribution suffice for efficient learning? We show that significantly weaker “high-temperature’’ conditions suffice for learning than previously known. As an application, these conditions, in combination with recently established covariance bounds, implies efficient learnability of the Sherrington-Kirkpatrick model in the (conjectured) replica-symmetric regime. Rather curiously, though, these structural conditions (and the corresponding temperatures where they provably hold) are quite distinct from those of the related problems of efficient optimization and sampling.

Based on joint works with Ahmed El Alaoui and Elchanan Mossel.