Solving overparametrized systems of nonlinear equations

Andrea Montanari (Stanford)
Wed, May 1 2024, 12:00pm

I will discuss the problem of solving a system of equations F(x)=0,for x a d-dimensional unit vectors and D a non-linear map from R^d to R^n whose components are independent, rotationally invariant Gaussian processes. We studied this problem under the proportional asymptotics in which n and d goes to diverge, with their ratio converging to alpha>0. I will present upper and lower bounds, as well as conjectures about the existence of solutions and the existence of polynomial-time algorithms to find them. Finally, I will discuss generalizations of this model, and how these insights shed light on the optimization landscape of overparametrized neural nets. [Based on joint work with Eliran Subag.]