A Curious Case Of Symmetric Binary Perceptron Model: Algorithms And Barriers

on YouTube ↗54m

" summary

Random symmetric binary perceptron uses an M×N random (Gaussian or Rademacher) matrix and seeks σ∈{±1}^N with Aσ/√N entrywise in [−κ,κ]. Existence has a sharp threshold α_c ≈ log 2 / |log P(|Z|≤κ)| (Xu/Perkins, Abbe/Li/Cai), yet constructive algorithms (Bansal–Spencer) succeed up to α = Θ(κ^2). A multi‑ensemble overlap‑gap property is proven via an interpolation A(t)=cos t·A+sin t·Â, produces extreme singleton clustering for most solutions, and rules out broad classes of stable algorithms above that Θ(κ^2) regime.

AI-written summary · about

" chapters (8)

1. 0:00Introduction
2. 3:53Historical context
3. 5:30Defining the model
4. 11:52Clustering and thresholds
5. 19:50Random k-set comparison
6. 23:34Solvability and gaps
7. 30:15Overlap gap property
8. 47:55Q&A and conclusion

" related talks

• 01h 07mTheory of Computation IIChristos Papadimitriou · The Brain and Computation Boot Camp
• 48mLearning by Local Entropy MaximizationRiccardo Zecchina · Random Instances and Phase Transitions (Simons Institute, 2016)
• 01h 17mGeneralization IPeter Bartlett, Sasha Rakhlin · Deep Learning Boot Camp 2019
• 01h 08mTutorial: Methods from Statistical Physics IIIAhmed El Alaoui · Deep Learning Theory Workshop and Summer School 2022
• 01h 04mStatistical Physics and Computation in High DimensionFlorent Krzakala, Lenka Zdeborova · Probability, Geometry, and Computation in High Dimensions Boot Camp (Simons Institute, Fall 2020)
• 29mComputational Barriers to Estimation from Low-Degree PolynomialsTselil Schramm · Rigorous Evidence for Information-Computation Trade-offs
• 35mPhase Retrieval In High Dimensions: Statistical And Computational Phase TransitionsAntoine Maillard · Rigorous Evidence for Information-Computation Trade-offs
• 49mAn Algorithmic Theory of Brain NetworksNancy Lynch · Computational Theories of the Brain 2018