Strong Low Degree Hardness of Strict Local Optima and other Random Optimization Problems, Part 1

Music City Center 

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 local strong convexity) on physical time-scales. In the context of the Sherrington--Kirkpatrick spin glass, recent work has 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≤o(N): any such algorithm has probability o(1) to output a stable local optimum. For spherical mean-field spin glasses with no external field, we also prove that the Langevin dynamics do not find stable local optima within dimension-free time. The first half of the talk will explain these results.