2024/11/17 by Gautam Chandrasekaran, Chandrasekaran, Gautam, Adam R. Klivans +1 · 4 citations
Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reservoir Engineering and Simulation Methods #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2411.11174
openalex publication_date 2024/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 β≤ √(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.