Shuangping Li (Yale)- On hardness for finding isolated perceptron solutions via stable algorithms
Abstract: We consider the Ising perceptron problem, which asks to find a sign vector in the intersection of independently chosen random halfspaces with intercept kappa. We show that stable algorithms, corresponding to polynomials of degree $N^{1-o(1)}$, cannot have a high probability to find isolated solutions. To do so, we show that near any isolated solution, the number of solutions after rerandomizing the disorder cannot concentrate on the value $1$. This is based on forthcoming joint work with Shuyang Gong, Brice Huang, and Mark Sellke.
Speakers
Shuangping Li
Shuangping Li is an assistant Professor of Statistics and Data Science at Yale University. She received her Ph.D. in Applied and Computational Mathematics from Princeton University, where she was co-advised by Professors Allan Sly and Emmanuel Abbe. Prior to joining Yale, she was a Stein Fellow in the Department of Statistics at Stanford University. Her research lies at the intersection of probability theory, high-dimensional statistics, theory of algorithms, and theoretical machine learning.
