Please Note: This seminar will be given online.
|
Probability seminar series Will Perkins Link to join seminar: Hosted on Webex |
Frozen 1-RSB structure of the symmetric Ising perceptron
The Ising perceptron model is a toy model of a neural network storing random patterns. The model can be phrased as a random constraint satisfaction problem: given a set of m n-dimensional Gaussian vectors X_i, solutions are binary vectors of length n whose inner product with each X_i lies in some interval. For the symmetric perceptron (where this interval is symmetric around 0), we prove a conjecture of Krauth and Mezard on the structure of the solutions space when m is linear in n. For all densities below the satisfiability threshold, typical solutions are completely isolated: they are at linear distance from the nearest other solution. We will discuss possible implications this "frozen 1-RSB" scenario has for algorithms. Based on joint work with Changji Xu (Harvard).