标题： 自旋玻璃中稳定局部最优的强低次数难解性 显示英文标题

标题： Strong Low Degree Hardness for Stable Local Optima in Spin Glasses

摘要： 人们普遍认为，在自旋玻璃和无序系统的理论中，非平衡动力学无法在物理时间尺度上找到表现出例如局部严格凸性的稳定局部最优解。在谢林顿-基尔帕特里克自旋玻璃的背景下，Behrens-Arpino-Kivva-Zdeborová 和 Minzer-Sah-Sawhney 最近提出猜想，认为这种障碍可能是所有高效算法固有的，尽管在整个景观中存在指数级多的这些最优解。我们证明了这个搜索问题对于次数为$D\leq o(N)$的多项式算法表现出强烈的低次数难度：任何此类算法输出一个稳定局部最优解的概率为$o(1)$。据我们所知，这是第一个证明即使常数次数的多项式在没有植入结构的随机搜索问题上也具有概率$o(1)$解决问题的结果。为了证明这一点，我们开发了一种通用的集合重叠间隙属性增强方法，并作为副产品改进了之前关于自旋玻璃优化、最大独立集、随机$k$-SAT 和伊辛感知器的结果，使其达到强低次数难度。最后，对于没有外部场的球面自旋玻璃，我们证明了朗之万动力学在与维度无关的时间内无法找到稳定的局部最优解。 显示英文摘要

摘要： It is a folklore belief in the theory of spin glasses and disordered systems that out-of-equilibrium dynamics fail to find stable local optima exhibiting e.g. local strict convexity on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, Behrens-Arpino-Kivva-Zdeborov\'a and Minzer-Sah-Sawhney have recently conjectured that this obstruction may be inherent to all efficient algorithms, despite the existence of exponentially many such optima throughout the landscape. We prove this search problem exhibits strong low degree hardness for polynomial algorithms of degree $D\leq o(N)$: any such algorithm has probability $o(1)$ to output a stable local optimum. To the best of our knowledge, this is the first result to prove that even constant-degree polynomials have probability $o(1)$ to solve a random search problem without planted structure. To prove this, we develop a general-purpose enhancement of the ensemble overlap gap property, and as a byproduct improve previous results on spin glass optimization, maximum independent set, random $k$-SAT, and the Ising perceptron to strong low degree hardness. Finally for spherical spin glasses with no external field, we prove that Langevin dynamics does not find stable local optima within dimension-free time.