BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:External FLAIR Seminar: Prof. David Gamarnik
DTSTART:20220421T131500
DTEND:20220421T141500
DTSTAMP:20260508T213237Z
UID:888134814153dd1def067930b1b74371b2b75e63f17a4e82c97e0cdc
CATEGORIES:Conferences - Seminars
DESCRIPTION:David Gamarnik\nTitle: A curious case of symmetric binary perc
 eptron model. Algorithms and algorithmic barriers.\n\nSpeaker: David Gama
 rnik (MIT)\n\nAbstract: Symmetric binary perceptron model exhibits an int
 eresting solution landscape property: the existence of polynomial time a
 lgorithms coincides with the presence of an extreme form of the clusterin
 g property. The latter means that at every strictly positive constraints 
 to variables ratio\, most of the satisfying solutions are singletons sepa
 rated by large distances. \n \nIn order to understand this conundrum  
 and gain an insight into the algorithmic tractability of this problem\, w
 e conduct a different landscape analysis. We establish that the model ex
 hibits a multi overlap gap property (m-OGP)\, and we show that  the ons
 et of this property asymptotically matches the performance of the best al
 gorithms.  Next we establish that m-OGP is a barrier to stable algorith
 ms\, appropriately defined\, and conjecture that the onset of m-OGP  ma
 rks in fact the onset of the true algorithmic hardness. The proof of this
  barrier is uses Ramsey theory from extremal combinatorics. We furthermo
 re show that one of the algorithm for the perceptron model\, known as Kim
 -Roche algorithm is indeed stable. \n \nJoint work with Eren Kizildag\,
  Will Perkins and Changji Xu.\n\n\n\nMainling list: The external FLAIR se
 minars about the theory of machine learning are also announced by email. T
 o receive them\, please subscribe to the mailing list here: https://forms
 .gle/3z6WwwKmN1XZzAxp8
LOCATION:GA 3 21 https://plan.epfl.ch/?room==GA%203%2021
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR