[Sds-seminars] [Sds-announce] S&DS Seminar, Shuangping Li, 2/10/25, KT 13th Floor, Rm. 1327, 12pm-1pm, "Phase Transitions and Algorithmic Aspects of the Binary Perceptron"

[elizavette.torres at yale.edu]

 <https://statistics.yale.edu/>     <https://statistics.yale.edu/>
Department of Statistics and Data Science  

 

Shuangping Li, Stanford University

Date: Monday, February 10, 2025

Time: 12:00PM to 1:00PM

Location: Kline Tower, 13th Floor, Rm. 1327 See map
<http://maps.google.com/?q=219+Prospect+Street%2C+New+Haven%2C+CT%2C+06511%2
C+us>  

219 Prospect Street

New Haven, CT 06511

 

and via Webcast:
https://yale.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0d95c606-a684-4
393-ae0c-b2640126583b

 

 

Title: Phase Transitions and Algorithmic Aspects of the Binary Perceptron

 

Information and Abstract:  The binary perceptron model, a simple
single-layer neural network, has a rich history in theoretical physics and
machine learning. This model considers the problem of finding a sign vector
that satisfies a set of random halfspace constraints. The two central
questions are: for what constraint densities do solutions exist with high
probability, and can we efficiently find a solution when one exists?
 
In this talk, I will discuss my work addressing both questions, guided by
long-standing conjectures from physics. These conjectures predict a sharp
satisfiability threshold for the existence of solutions, and a strong
freezing property (where almost all solutions are isolated, suggesting that
finding solutions using polynomial-time algorithms is typically hard). For
the symmetric binary perceptron, we rigorously establish both predictions.
Furthermore, the strong freezing property is particularly intriguing,
because empirical evidence shows that polynomial time algorithms often
succeed in finding a solution, challenging the typically hard prediction.
This suggests that such algorithms find atypical solutions. We establish
formally this phenomenon, showing that at low constraint density, there
exists a rare but well-connected cluster of solutions, and that an efficient
multiscale majority algorithm can find solutions in such a cluster with high
probability. Additionally, we modify the canonical discrepancy minimization
algorithms to solve the binary perceptron problem. We analyze the
performance of our algorithm, yielding new algorithmic results.

 

Speaker bio: Shuangping Li is a Stein Fellow in statistics at Stanford
University. She earned her PhD in applied and computational mathematics from
Princeton University under the guidance of Professors Allan Sly and Emmanuel
Abbe. Her research lies at the intersection of probability theory, theory of
algorithms and complexity, high dimensional statistics, and theoretical
machine learning.

 

Lunch at 11:30am in room 1307
Talk at 12:00-1:00pm in room 1327A

 <https://www.facebook.com/YaleUniversity> 
For more details and upcoming events visit our website at
<https://statistics.yale.edu/calendar> https://statistics.yale.edu/calendar.


 

Department of Statistics and Data Science

Yale University
Kline Tower

219 Prospect Street
New Haven, CT 06511

 <https://statistics.yale.edu/> https://statistics.yale.edu/

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20250203/bc049136/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 2925 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20250203/bc049136/attachment.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image002.jpg
Type: image/jpeg
Size: 43099 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20250203/bc049136/attachment-0001.jpg>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image003.jpg
Type: image/jpeg
Size: 4741 bytes
Desc: not available
URL: <http://mailman.yale.edu/pipermail/sds-seminars/attachments/20250203/bc049136/attachment-0002.jpg>
-------------- next part --------------
-- 
Sds-announce mailing list
Sds-announce at mailman.yale.edu
https://mailman.yale.edu/mailman/listinfo/sds-announce