Events
FDS
Algorithmic thresholds in random optimization problems
 |
Speaker: Brice Huang (MIT) Massachusetts Institute of Technology Wednesday, February 26, 2025 11:30AM - 1:00PM Lunch at 11:30am in 1307
Talke at 12:00-1:00pm in 1327a Location: Yale Institute for Foundations of Data Science, Kline Tower 13th Floor, Room 1327, New Haven, CT 06511 and via Webcast: https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=ec06b7aa-b314-4949-994a-b25900f3462a |
Abstract: Optimizing high-dimensional functions generated from random data is a central problem in modern statistics and machine learning. As these objectives are highly non-convex, the maximum value reachable by efficient algorithms is usually smaller than the maximum value that exists, and characterizing the fundamental computational limits of these problems is a difficult challenge.
In this talk, I will describe the “branching overlap gap property,” a new technique I have developed that obtains sharp algorithmic thresholds in several random optimization problems. We focus on two prototypical families of random functions, namely the Hamiltonians of mean-field spin glasses and random perceptrons. These models are widely studied in probability, statistical physics, and computer science, and are related to problems in high-dimensional statistical inference and neural networks. We exactly characterize the maximum value achievable by a broad class of stable algorithms, which includes gradient descent, Langevin dynamics, and general first-order methods on dimension-free time scales. We also identify this value with a phase transition in the solution landscape, yielding a unified geometric description of the algorithmic threshold that holds across several problems.
Speaker bio: Brice Huang is a final-year Ph.D. student in Electrical Engineering and Computer Science at MIT, advised by Nike Sun and Guy Bresler. His research focuses on the theoretical foundations of optimization and sampling problems over random, high-dimensional landscapes, and studies both the fundamental statistical and computational limits of these problems. In addition, he has worked on statistical inference, quantum learning theory, and combinatorics. His work has been recognized with a FOCS Best Student Paper Award, the Ernst A. Guillemin award for Best SM thesis, and a Google Ph.D. Fellowship.
Add To: Google Calendar | Outlook | iCal File
Submit an Event
Interested in creating your own event, or have an event to share? Please fill the form if you’d like to send us an event you’d like to have added to the calendar.