Symmetric Binary Perceptron Model: Algorithms and Barriers

Wednesday, February 16, 2022 - 4:00pm to 4:30pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Eren Can Kizildag

Affiliation

LIDS

Building and Room Number

LIDS Lounge

Abstract

It has been shown very recently that the symmetric binary perceptron (SBP) exhibits an extreme form of clustering at all positive densities: almost all of its solutions are singletons separated by large distances. This suggests that finding a solution is likely to be computationally intractable. At the same time, SBP admits polynomial-time algorithms succeeding at low enough densities. This conundrum challenges the view that clustering implies algorithmic hardness. In this paper, we conduct a different landscape analysis to understand the true algorithmic tractability of this problem. Guided by statistical physics insights, we show that SBP exhibits the multi Overlap Gap Property (m-OGP), an intricate geometric property known to be a rigorous barrier for large classes of algorithms. Our analysis shows the m-OGP threshold (a) is well below the satisfiability threshold; and (b) is nearly tight: up to polylogarithmic factors, it matches the best algorithmic threshold. We then leverage the m-OGP to establish that any sufficiently stable algorithm (appropriately defined) fails to find a satisfying solution.  Our hardness result for the stable algorithms is based on Ramsey Theory from extremal combinatorics, and is of independent interest. The most technically involved part of this work is establishing the stability of the known algorithms, which unlike in several prior models, do not appear to fall into the class of low-degree polynomials. Joint work with David Gamarnik, Will Perkins, and Changji Xu. 

Biography

Eren is a final-year Ph.D. student in the Department of Electrical Engineering and Computer Science (EECS) at Massachusetts Institute of Technology (MIT), where he is advised by Prof. David Gamarnik. His current research focuses on problems in theoretical machine learning, high-dimensional statistics, and discrete applied probability; where he is interested in devising computationally efficient algorithms for solving such problems as well as in understanding their fundamental computational limits by leveraging insights from the statistical physics and spin glass theory. Before that, he received his B.S. degree in electrical and electronics engineering from Boğaziçi University in 2014, and his M.S. degree in EECS from MIT in 2017.