SK 模型采样难题突破:多项式时间算法覆盖 β<1 全区间
canondetortugas · x · 2026-09-29
Holden Lee、Juspreet Singh Sandhu、Jonathan Shi 发布 arXiv 论文(2609.30590),给出在任意逆温 β<1 下、以总变差距离 on(1) 误差从 Sherrington-Kirkpatrick(SK)模型 Gibbs 测度采样的多项式时间算法,解决了自 2022 年 El Alaoui、Montanari、Sellke 提出去噪扩散算法以来悬而未决的问题。
技术要点:
- 结合算法随机局部化(ASL)与基于 Jarzynski 等式的路径空间拒绝采样
- 将作者此前 β<1/2 结果中的 SDE 误差分析的全局正则性要求,替换为「可能轨迹附近」的局部正则性
- 局部强凸性借助 Celentano 对 TAP 自由能局部强凸的证明建立
- 使用腔插值与自由概率工具,以 TAP 自由能作为随机局部化后 Gibbs 测度真实自由能的高效可计算代理
作者自嘲这项工作拖了三年才完成,是延续其「Potential Hessian Ascent」系列第四篇。
「研究」频道最新
- Anthropic 实测：基础设施配置可让编程评测相差 6 个百分点 — giansegato · 2026-09-29
- GoFish 演示层级式动画图表：分组柱状图逐月生长 — arvindsatya1 · 2026-09-29
- 作者回应评测质疑：跑过多次，但别过度迷信行业基准分 — giansegato · 2026-09-29
- 重磅预告：无需反向传播，零阶优化直接预训练 Transformer — teortaxesTex · 2026-09-29
- DR-GEM 论文：降维方法偏心高频样本，漏掉稀有细胞类型 — anshulkundaje · 2026-09-29
- AI 智能体给出 Collatz 猜想新进展:正比例整数回于 1 并完成 Lean 形式化 — AlexKontorovich · 2026-09-29