Potential Hessian Ascent IV: Sampling the Sherrington-Kirkpatrick model at $\beta < 1$

技术摘要：潜在的 Hessian 上升 IV：在 $\beta < 1$ 时对 Sherrington–Kirkpatrick 模型进行采样

问题陈述
本文研究了对 Sherrington–Kirkpatrick (SK) 自旋玻璃模型 Gibbs 测度进行采样的计算问题。该模型定义在规模为 $n$ 的系统上，其随机对称矩阵 $A \sim \text{GOE}(n)$ 以及逆温度 $\beta$。目标是设计一个多项式时间算法，生成来自 Gibbs 分布 $\mu_{\beta A}$ 的样本，且其全变差距离 (TVD) 误差在 $n \to \infty$ 时趋于消失（即 $o_n(1)$）。

作者的前期工作 [DLSS26a] 在 $\beta < 1/2$ 时实现了这一目标。然而，对于 $\beta > 1/2$（具体而言是在 $0.798 < \beta < 1$ 的范围内），已知 TAP (Thouless-Anderson-Palmer) 自由能并非全局强凸的。这种全局凸性的缺失破坏了先前算法随机定位 (ASL) 分析所依赖的全局 Lipschitz 和光滑性假设（这些假设依赖于 TAP Hessian 逆矩阵，即 resolvent）。$\beta < 1$ 被认为是计算复杂度的阈值，因为系统在 $\beta > 1$ 时表现出全复制对称破缺 (fRSB)。

方法论
作者通过将全局正则性要求替换为围绕随机过程可能轨迹的局部正则性，扩展了他们之前的 ASL 框架。其核心方法论包括：

1. 带有拒绝采样的算法随机定位 (ASL)： 算法遵循 $dy_t = m_t dt + dB_t$ 的 ASL 过程，但利用 TAP 自由能来近似磁化强度 $m_t$。至关重要的是，算法包含一个拒绝步骤：如果轨迹离开了 TAP Hessian 局部强凸的“安全集” $S_{\beta, A}(c)$，则丢弃该轨迹并重新开始。
2. 带有生存机制的 Jarzynski 等式 (JE)： 为了修正由拒绝采样（在退出安全集时停止过程）引入的偏差，作者推导了一个修正后的 Jarzynski 等式。这使得可以通过对生存路径进行重加权来近似目标分布。
3. 通过 Celentano 结果建立局部强凸性： 安全性的存在是通过 Celentano [Cel24] 的一个结果建立的，该结果证明了对于 $\beta < 1$，TAP 自由能在近似消息传递 (AMP) 迭代附近的微小球体内是局部强凸的。作者结合了 SK 模型在随机定位下的稳定性（源自 [AMS22]），以证明 ASL 轨迹以高概率保持在这些局部凸区域内。
4. Resolvent 分析与正则化： 为了处理安全集之外的非凸性以及 TAP Hessian 可能出现的奇异性，作者引入了 resolvent（TAP Hessian 的逆）的 $C^2$ 正则化。他们利用自由概率技术和受 [BBv23] 启发的块矩阵表示法，来控制平方 resolvent 的对角线项，并建立一致的集中界限。
5. Lipschitz 扩展： 由于安全集不是凸的，标准的沿直线路径的导数界限不再适用。作者在安全集内构造了短路径，并利用 resolvent 恒等式，在不依赖全局凸性的情况下，推导出漂移项、扩散系数以及 JE 加权被积函数的 Lipschitz 界限。

主要贡献

• 将范围扩展至 $\beta < 1$： 主要贡献是为任何固定的 $\beta < 1$ 提供了一个多项式时间采样算法，突破了之前 $\beta < 1/2$ 的障碍。
• 局部正则性框架： 本文提出了一个“设计要求 (desiderata)”，将先前工作的全局正则性要求放宽为针对安全集的局部正则性。该框架被证明足以支持 ASL-JE 分析。
• 混合凸性证明： 作者通过结合 Celentano 的 AMP 迭代局部凸性结果与随机定位过程的稳定性，证明了整个随机定位路径上 TAP Hessian 都是一致局部强凸的。
• 精细化的 Resolvent 分析： 文中引入了一种正则化的 resolvent 扩展，并使用基于块矩阵表示的简化自由插值论证来控制 resolvent 的对角线，从而绕过了以往与张量积和协方差结构相关的技术瓶颈。
• 拒绝采样分析： 对使用“基于生存”的 Jarzynski 等式的拒绝采样步骤进行了严格分析，确保了因丢弃轨迹而产生的误差保持在 $o_n(1)$。

结果
本文确立了 定理 1.1：对于任何固定的 $0 < \beta < 1$ 和 $\delta > 0$，存在一个 $n_0(\beta, \delta)$，使得对于所有 $n \geq n_0$，在关于无序度 $A$ 的概率至少为 $1-\delta$ 的情况下，所提算法（算法 2）输出的分布在 TVD 意义下与 Gibbs 测度 $\mu_{\beta A}$ 接近 $o_n(1)$，且运行时间为多项式时间。

分析依赖于验证更新后的设计要求：

• (d1) 协方差估计误差是有界的。
• (d2a) TAP Hessian 在 SL 路径上是一致局部强凸的。
• (d2b) TAP Hessian 满足局部正则性（Löwner sandwich）界限。
• (d3)-(d5) 漂移项、扩散项和 JE 加权项在安全集上满足必要的 Lipschitz 和误差界限。

意义
本文声称是朝着解决“Glauber 动力学在 de Almeida-Thouless (dAT) 线以下（$\beta < 1$）表现出快速混合”这一猜想迈出的重要一步。通过展示算法随机定位如何通过局部正则性和拒绝采样绕过全局凸性障碍，这项工作为在全局泛函不等式难以建立的自旋玻璃模型中提供了一种新的采样途径。作者指出，他们的方法结合了 ASL 与局部分布的快速混合结果（通过 [KSTZ26]），以实现最终的采样保证。

同时，该工作也强调了 $\beta < 1$ 是其方法的临界点，因为已知在 $\beta > 1$ 时，没有任何稳定的算法（包括 ASL）能以较小的 $W_2$ 距离进行采样，且最坏情况下的 Glauber 动力学在该区域的混合速度呈指数级缓慢。本文并不声称解决了 $\beta \geq 1$ 时的采样问题，也不直接证明 Glauber 动力学的快速混合，而是为高温度机制下的 Gibbs 测度提供了一个高效的采样器，直至其预期的计算阈值。