BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Brice Huang (MIT Mathematics)
DTSTART:20220421T213000Z
DTEND:20220421T230000Z
DTSTAMP:20260423T035417Z
UID:SPAMS/16
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/SPAMS/16/">T
 ight Algorithmic Thresholds from the Branching Overlap Gap Property</a>\nb
 y Brice Huang (MIT Mathematics) as part of MIT Simple Person's Applied Mat
 hematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\
 n\nAbstract\nWe will describe recent progress on algorithmic hardness resu
 lts for ``spin glass-like" random optimization problems. The landscapes of
  these problems are highly nonconvex and often include many bad local maxi
 ma\, impeding optimization by efficient algorithms. As a result\, these pr
 oblems exhibit gaps between the largest objectives that exist and that can
  be found by efficient algorithms\; characterizing the algorithmic limit r
 equires developing sharp hardness results. For mean field spin glasses\, w
 e describe a new hardness result that tightly characterizes the algorithmi
 c limit for any algorithm with $O(1)$-Lipschitz dependence on the disorder
  coefficients. This class includes the best algorithm known for this probl
 em and natural formulations of gradient descent and approximate message pa
 ssing. \\\\\n \nWe will go over the Overlap Gap Property (OGP) framework o
 f Gamarnik and Sudan\, which shows hardness in random optimization problem
 s against any algorithm that is suitably stable in its inputs. We introduc
 e the \\emph{Branching OGP}\, a generalization of the OGP to arbitrary ult
 rametric constellations of solutions\, which is the key tool in the proof 
 of the aforementioned hardness result. By considering the Continuous Rando
 m Energy Model (CREM)\, we will see by analogy why the Branching OGP yield
 s tight algorithmic thresholds in mean field spin glasses and potentially 
 in greater generality. \\\\\n \nBased on joint works with Guy Bresler and 
 Mark Sellke.\n
LOCATION:https://researchseminars.org/talk/SPAMS/16/
END:VEVENT
END:VCALENDAR