Complexity of random smooth functions on the high-dimensional sphere

Abstract

We analyze the landscape of general smooth Gaussian functions on the sphere in dimension $N$, when $N$ is large. We give an explicit formula for the asymptotic complexity of the mean number of critical points of finite and diverging index at any level of energy and for the mean Euler characteristic of level sets. We then find two possible scenarios for the bottom landscape, one that has a layered structure of critical values and a strong correlation between indexes and critical values and another where even at levels below the limiting ground state energy the mean number of local minima is exponentially large. We end the paper by discussing how these results can be interpreted in the language of spin glasses models.

Published in at http://dx.doi.org/10.1214/13-AOP862 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Validity of the expected Euler characteristic heuristic

Cited by in corpus (54)

• Perspective: Energy Landscapes for Machine Learning
• Algorithmic thresholds for tensor PCA
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Turning intractable counting into sampling: computing the configurational entropy of three-dimensional jammed packings
• Trainability and Accuracy of Neural Networks: An Interacting Particle System Approach
• Rethinking mean-field glassy dynamics and its relation with the energy landscape: the awkward case of the spherical mixed p-spin model
• The geometry of the Gibbs measure of pure spherical spin glasses
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed p-spin models
• Computational Complexity of Vacua and Near-Vacua in Field and String Theory
• Free energy and complexity of spherical bipartite models
• On the number of connected components of random algebraic hypersurfaces
• Spectral gap estimates in mean field spin glasses
• Low Temperature Asymptotics in Spherical Mean Field Spin Glasses
• Exponential number of equilibria and depinning threshold for a directed polymer in a random potential
• Replica Symmetry Breaking in Bipartite Spin Glasses and Neural Networks
• Topology trivialization transition in random non-gradient autonomous ODE's on a sphere
• Geometry of energy landscapes and the optimizability of deep neural networks
• Hessian spectrum at the global minimum of high-dimensional random landscapes
• Approximate Ultrametricity for Random Measures and Applications to Spin Glasses
• Triviality of the geometry of mixed $p$-spin spherical Hamiltonians with external field
• On the energy landscape of the mixed even $p$-spin model
• On the Spectral Gap of Spherical Spin Glass Dynamics
• How to count in hierarchical landscapes: a 'full' solution to mean-field complexity
• The Loss Surface of XOR Artificial Neural Networks
• Nonlinearity-generated Resilience in Large Complex Systems
• Bounding flows for spherical spin glass dynamics
• Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
• Effects of intraspecific cooperative interactions in large ecosystems
• Concentration of the complexity of spherical pure $p$-spin models at arbitrary energies
• Activated dynamics: an intermediate model between REM and p-spin
• Optimizing Mean Field Spin Glasses with External Field
• A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• Manifolds in high dimensional random landscape: complexity of stationary points and depinning
• Introduction to the dynamics of disordered systems: equilibrium and gradient descent
• Existence of two-step replica symmetry breaking for the spherical mixed p-spin glass at zero temperature
• Zero-temperature dynamics in the dilute Curie-Weiss model
• Complex complex landscapes
• Dynamics for spherical spin glasses: disorder dependent initial conditions
• Localization in the Discrete Non-Linear Schrödinger Equation and geometric properties of the microcanonical surface
• Complexity of Gaussian random fields with isotropic increments: critical points with given indices
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Probing chaos in the spherical p-spin glass model
• Manifolds pinned by a high-dimensional random landscape: Hessian at the global energy minimum
• Counting equilibria of large complex systems by instability index
• Glass--like transition described by toppling of stability hierarchy
• On-Site Potential Creates Complexity in Systems with Disordered Coupling
• Statistics of Stationary Points of Random Finite Polynomial Potentials
• Black holes and the loss landscape in machine learning
• Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass
• Superposition of Random Plane Waves in High Spatial Dimensions: Random Matrix Approach to Landscape Complexity
• Information scrambling and butterfly velocity in quantum spin glass chains
• Thouless-Anderson-Palmer equations for the Ghatak-Sherrington mean field spin glass model
• Optimization landscape in the simplest constrained random least-square problem
• Inflation in a Gaussian Random Landscape