Solving systems of Random Equations via First and Second-Order Optimization Algorithms

We revisit the problem of solving $n$ random equations in $d$ real variables, when the equations are independent realizations of a Gaussian process in $d$ dimensions. A special case is the one of random polynomial equations, which has been studied since Littlewood-Offord and Kac in the 1940s (who studied of existence of solutions of random polynomials) and Shub and Smale in the 1990s. The last authors first investigated the computational aspect of this problem. Smale's `17th problem' asks whether a system of random polynomial equations can be (approximately) solved in average case polynomial time.
We formulate this as a nonconvex optimization problem, and apply local algorithms based on gradient or Hessian information. We leverage recent advances in spin glass theory to characterize the optimal algorithm in this class, and show that the latter undergoes a phase transition at a critical value $\alpha_{\text{alg}}$ of the ratio $\alpha=n/d$. We establish that near-solutions can be found with-high probability for $\alpha<\alpha_{\text{alg}}$, while a companion paper proves that a broad class of efficient algorithms fail for $\alpha>\alpha_{\text{alg}}$ (we outline the proof of this hardness result). We further prove that there are cases such that for $(1+\delta)\alpha_{\text{alg}}<n/d<(1-\delta)\alpha_{\text{lb}}$ (with $\delta>0$ arbitrarily small) solutions exists with high probability but are not found efficiently by a broad class of algorithms.
We compare our predictions with numerical simulations using the optimal algorithm we propose as well as stochastic gradient descent, and show that they are accurate for a related albeit non-Gaussian cost function. We finally observe empirically a sensitivity cross-over in the behavior of optimization algorithms, below $\alpha_{\text{alg}}$. This marks a qualitative departure with respect to standard optimization theories.