Tight Algorithmic Thresholds from the Branching Overlap Gap Property

Abstract: We will describe recent progress on algorithmic hardness results for ``spin glass-like" random optimization problems. The landscapes of these problems are highly nonconvex and often include many bad local maxima, impeding optimization by efficient algorithms. As a result, these problems exhibit gaps between the largest objectives that exist and that can be found by efficient algorithms; characterizing the algorithmic limit requires developing sharp hardness results. For mean field spin glasses, we describe a new hardness result that tightly characterizes the algorithmic limit for any algorithm with $O(1)$-Lipschitz dependence on the disorder coefficients. This class includes the best algorithm known for this problem and natural formulations of gradient descent and approximate message passing. \\ We will go over the Overlap Gap Property (OGP) framework of Gamarnik and Sudan, which shows hardness in random optimization problems against any algorithm that is suitably stable in its inputs. We introduce the \emph{Branching OGP}, a generalization of the OGP to arbitrary ultrametric constellations of solutions, which is the key tool in the proof of the aforementioned hardness result. By considering the Continuous Random Energy Model (CREM), we will see by analogy why the Branching OGP yields tight algorithmic thresholds in mean field spin glasses and potentially in greater generality. \\ Based on joint works with Guy Bresler and Mark Sellke.

Computer scienceMathematicsPhysics

Audience: researchers in the topic

MIT Simple Person's Applied Mathematics Seminar