提出简单算法学习低温下的SK自旋玻璃模型参数
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
- 用乘法权重更新法学习随机边权的无向图模型
- 可在β≤√log n条件下多项式时间完成参数学习
- 适合对统计物理与机器学习交叉感兴趣的读者
我们研究在边权随机设定下学习无向图模型（马尔可夫随机场）参数的基本问题。针对伊辛模型，证明克利万斯和梅卡提出的乘法权重更新算法可在任意逆温度β≤√log n时实现多项式时间学习。该结果直接给出了超越高温度区域β<1的施林格-基尔帕特里克（SK）模型参数学习算法。此前工作在β=1处失效，且需依赖统计物理或函数不等式的复杂工具。而本研究分析更简洁，仅使用次高斯浓度性质。结果还可推广至更高阶马尔可夫随机场（如纯p自旋模型），甚至在高温度情形下此前亦无已知结果。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。