2023/06/23 by Andrea Montanari, Eliran Subag, Montanari, Andrea +1 · 1 voice
Mathematics · #math.PR
paper · pdf · doi:10.48550/arxiv.2306.13326
91 pages; 44 pdf figures
arxiv created 2026/07/29 · arxiv updated 2026/07/30
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 αalg of the ratio α=n/d. We establish that near-solutions can be found with-high probability for α<αalg, while a companion paper proves that a broad class of efficient algorithms fail for α>αalg (we outline the proof of this hardness result). We further prove that there are cases such that for (1+δ)αalg<n/d<(1-δ)αlb (with δ>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 αalg. This marks a qualitative departure with respect to standard optimization theories.