LIDS & Stats Tea Talk || Eren Can Kizildag (LIDS)

Speaker: Eren Can Kizildag

MIT Affiliation: LIDS

Title: Symmetric Binary Perceptron Model: Algorithms and Barriers

Date: Wednesday, February 16, 2022

Time: 4:00 PM to 4:30 PM

Location: LIDS Lounge

Host: Sathwik Chadaga

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. 

Bio: 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 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.

**************

ABOUT: Tea talks are 20-minute-long informal chalk-talks for the purpose of sharing ideas and making others aware about some of the topics that may be of interest to the LIDS and Stats audience. If you are interested in presenting in the upcoming tea talks, please email lids_stats_tea@mit.edu.

Information on future talks: https://lids.mit.edu/news-and-events/lids-stats-tea.

Details

• Date: Wednesday, February 16
• Time: 4:00 pm - 5:00 pm
• Location: LIDS lounge

Additional Location Details:

Note: In accordance with MIT’s COVID policies, we are required to collect contact information from those who attend this event. If you are an MIT Covid Pass holder, please bring your smart phone and be prepared to present your MIT ID Barcode, which can be found in the MIT Atlas app.