Solving overparametrized systems of nonlinear equations

Andrea Montanari
Stanford University

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.]


Back to EnCORE Workshop on Computational vs Statistical Gaps in Learning and Optimization