Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
This provides a solution for learning complex statistical models in machine learning and physics, particularly for high-dimensional settings, though it is incremental as it builds on existing algorithms with improved analysis.
The paper tackles the problem of learning parameters of undirected graphical models, specifically Ising and Sherrington-Kirkpatrick models, by showing that a multiplicative-weight update algorithm can learn these parameters in polynomial time for inverse temperatures up to √log n, extending beyond the high-temperature regime of β < 1 where prior methods fail.
We consider the fundamental problem of learning the parameters of an undirected graphical model or Markov Random Field (MRF) in the setting where the edge weights are chosen at random. For Ising models, we show that a multiplicative-weight update algorithm due to Klivans and Meka learns the parameters in polynomial time for any inverse temperature $β\leq \sqrt{\log n}$. This immediately yields an algorithm for learning the Sherrington-Kirkpatrick (SK) model beyond the high-temperature regime of $β< 1$. Prior work breaks down at $β= 1$ and requires heavy machinery from statistical physics or functional inequalities. In contrast, our analysis is relatively simple and uses only subgaussian concentration. Our results extend to MRFs of higher order (such as pure $p$-spin models), where even results in the high-temperature regime were not known.