| Title | : | Learning the Sherrington-Kirkpatrick model even at low temperature |
| Speaker | : | Gautam Chandrasekaran (UT Austin) |
| Details | : | Tue, Aug 5, 2025 4:00 PM, @ SSB 334 |
| Abstract | : | 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 beta at most sqrt{log n}. This immediately yields an algorithm for learning the Sherrington-Kirkpatrick (SK) model beyond the high-temperature regime of beta < 1. Prior work breaks down at beta = 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. This is joint work with Adam Klivans. |