Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

A curious case of symmetric binary perceptron model. Algorithms and algorithmic barriers.

Probability

Speaker: David Gamarnik, MIT
Location: MSB 2112
Start time: Tue, Oct 11 2022, 1:10PM

Symmetric binary perceptron model is a random constraint satisfaction problem which intrigued probabilists, statistical physicists, computer scientists and machine learners. The model is extremely easy to describe: given a collection of random vectors in a binary cube, find a vector which is nearly orthogonal to all of them within some allowable range. The model exhibits a puzzling structural phase transition and algorithmic properties. In particular, the existence of polynomial time algorithms for finding such a vector coincides with the presence of an extreme form of clustered, golf-course type solution space. This goes against a conventional wisdom for random constraint satisfaction problems, stating that the presence of such clustering should make the algorithmic task hard.

In order to understand this conundrum we conduct a different landscape analysis. We establish that the model exhibits a form of the overlap gap property (OGP), which we will explain in the talk. We show that the onset of this property asymptotically matches the threshold for the existence of the best known algorithms, and that its presence is a provable barrier to a large class of algorithms, including algorithms which succeed below the OGP threshold.

Joint work with Eren Kizildag, Will Perkins and Changji Xu.