On the topology of solutions to random continuous constraint satisfaction problems

Abstract

We consider the set of solutions to $M$ random polynomial equations whose $N$ variables are restricted to the $(N-1)$-sphere. Each equation has independent Gaussian coefficients and a target value $V_0$. When solutions exist, they form a manifold. We compute the average Euler characteristic of this manifold in the limit of large $N$, and find different behavior depending on the target value $V_0$, the ratio $\alpha =M/N$, and the variances of the coefficients. We divide this behavior into five phases with different implications for the topology of the solution manifold. When $M=1$ there is a correspondence between this problem and level sets of the energy in the spherical spin glasses. We conjecture that the transition energy dividing two of the topological phases corresponds to the energy asymptotically reached by gradient descent from a random initial condition, possibly resolving an open problem in out-of-equilibrium dynamics. However, the quality of the available data leaves the question open for now.

References in corpus (33)

• Spin-Glass Theory for Pedestrians
• Qualitatively characterizing neural network optimization problems
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• The simplest model of jamming
• Universality of the SAT-UNSAT (jamming) threshold in non-convex continuous constraint satisfaction problems
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• The spherical 2+p spin glass model: an analytically solvable model with a glass-to-glass transition
• The spherical $2+p$ spin glass model: an exactly solvable model for glass to spin-glass transition
• Properties of the geometry of solutions and capacity of multi-layer neural networks with Rectified Linear Units activations
• Rethinking mean-field glassy dynamics and its relation with the energy landscape: the awkward case of the spherical mixed p-spin model
• Critical jammed phase of the linear perceptron
• Constraint satisfaction mechanisms for marginal stability and criticality in large ecosystems
• Supersymmetric quenched complexity in the Sherrington-Kirkpatrick model
• Marginal States in Mean Field Glasses
• Gradient descent dynamics in the mixed $p$-spin spherical model: finite size simulation and comparison with mean-field integration
• On weak ergodicity breaking in mean-field spin glasses
• The role of the Becchi-Rouet-Stora-Tyutin supersymmetry in the calculation of the complexity for the Sherrington-Kirkpatrick model
• How to count in hierarchical landscapes: a 'full' solution to mean-field complexity
• Coexistence of supersymmetric and supersymmetry-breaking states in spherical spin-glasses
• Algorithmic Thresholds in Mean Field Spin Glasses
• A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• A continuous constraint satisfaction problem for the rigidity transition in confluent tissues
• Arrangement of nearby minima and saddles in the mixed spherical energy landscapes
• Revisiting "Qualitatively Characterizing Neural Network Optimization Problems"
• Dynamical mean field theory for models of confluent tissues and beyond
• The Spherical p+s Spin Glass At Zero Temperature
• Random Linear Systems with Quadratic Constraints: from Random Matrix Theory to replicas and back
• Solving systems of Random Equations via First and Second-Order Optimization Algorithms
• Statistical physics of complex systems: glasses, spin glasses, continuous constraint satisfaction problems, high-dimensional inference and neural networks
• Stochastic Gradient Descent outperforms Gradient Descent in recovering a high-dimensional signal in a glassy energy landscape
• On Smale's 17th problem over the reals
• On the Trajectories of SGD Without Replacement
• Algorithm-independent bounds on complex optimization through the statistics of marginal optima