Topology trivialization and large deviations for the minimum in the simplest random optimization

Abstract

Finding the global minimum of a cost function given by the sum of a quadratic and a linear form in N real variables over (N-1)- dimensional sphere is one of the simplest, yet paradigmatic problems in Optimization Theory known as the "trust region subproblem" or "constraint least square problem". When both terms in the cost function are random this amounts to studying the ground state energy of the simplest spherical spin glass in a random magnetic field. We first identify and study two distinct large-N scaling regimes in which the linear term (magnetic field) leads to a gradual topology trivialization, i.e. reduction in the total number N_{tot} of critical (stationary) points in the cost function landscape. In the first regime N_{tot} remains of the order $N$ and the cost function (energy) has generically two almost degenerate minima with the Tracy-Widom (TW) statistics. In the second regime the number of critical points is of the order of unity with a finite probability for a single minimum. In that case the mean total number of extrema (minima and maxima) of the cost function is given by the Laplace transform of the TW density, and the distribution of the global minimum energy is expected to take a universal scaling form generalizing the TW law. Though the full form of that distribution is not yet known to us, one of its far tails can be inferred from the large deviation theory for the global minimum. In the rest of the paper we show how to use the replica method to obtain the probability density of the minimum energy in the large-deviation approximation by finding both the rate function and the leading pre-exponential factor.

in this version the new formula (63) and a few relevant references are added and some misprints are corrected

References in corpus (5)

• Large Deviations of the Maximum Eigenvalue for Wishart and Gaussian Random Matrices
• The KPZ equation with flat initial condition and the directed polymer with one free end
• Critical Behaviour of the Number of Minima of a Random Landscape at the Glass Transition Point and the Tracy-Widom distribution
• Classical Particle in a Box with Random Potential: exploiting rotational symmetry of replicated Hamiltonian
• Energy Landscape of the Finite-Size Mean-field 3-Spin Spherical Model

Cited by in corpus (40)

• Top eigenvalue of a random matrix: large deviations and third order phase transition
• Perspective: Energy Landscapes for Machine Learning
• Random matrices and entanglement entropy of trapped Fermi gases
• 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
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Exponential number of equilibria and depinning threshold for a directed polymer in a random potential
• Large time zero temperature dynamics of the spherical p=2-spin glass model of finite size
• Ferromagnetic to paramagnetic transition in spherical spin glass
• Topology trivialization transition in random non-gradient autonomous ODE's on a sphere
• Hessian spectrum at the global minimum of high-dimensional random landscapes
• Triviality of the geometry of mixed $p$-spin spherical Hamiltonians with external field
• Spherical spin glass model with external field
• Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
• The Loss Surface of XOR Artificial Neural Networks
• Quenched complexity of equilibria for asymmetric Generalized Lotka-Volterra equations
• Central limit theorem near the critical temperature for the overlap in the 2-spin spherical SK model
• Many-Body-Localization Transition : sensitivity to twisted boundary conditions
• A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• Matrix optimization under random external fields
• Kac-Rice fixed point analysis for single- and multi-layered complex systems
• Energy Landscape of the Finite-Size Mean-field 2-Spin Spherical Model and Topology Trivialization
• Free energy fluctuations of the $2$-spin spherical SK model at critical temperature
• Finite size effects and loss of self-averageness in the relaxational dynamics of the spherical Sherrington-Kirkpatrick model
• Fluctuations in the random-link matching problem
• Separability gap and large deviation entanglement criterion
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• On-Site Potential Creates Complexity in Systems with Disordered Coupling
• Manifolds pinned by a high-dimensional random landscape: Hessian at the global energy minimum
• Statistics of Stationary Points of Random Finite Polynomial Potentials
• 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
• Overlap of a spherical spin glass model with microscopic external field
• The Most Dispersed Subset of Random Points in ${\mathbb{R}}^d$
• Finite-size relaxational dynamics of a spike random matrix spherical model
• Appearance of Random Matrix Theory in Deep Learning
• Generalised Gibbs Ensemble for spherically constrained harmonic models
• The Tracy-Widom distribution at large Dyson index
• Nonlinear analog of the complexity-stability transition in random dynamical systems: a replica calculation
• Optimization landscape in the simplest constrained random least-square problem