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

DOI10.1007/S10955-013-0838-1zbMATH Open1291.82127arXiv1304.0024OpenAlexW3102513472MaRDI QIDQ2016530FDOQ2016530

Y. V. Fyodorov, Pierre Le Doussal

Publication date: 20 June 2014

Published in: Journal of Statistical Physics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1304.0024

Recommendations

• Optimization landscape in the simplest constrained random least-square problem
• The Shape of a Local Minimum and the Probability of its Detection in Random Search
• Complexity of random smooth functions on the high-dimensional sphere
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• The Petrov type D isolated null surfaces

zbMATH Keywords

large deviationsrandom matricesspin glassesreplica methodrandom optimizationtracy-widom distributionrandom landscapes

Mathematics Subject Classification ID

Large deviations (60F10) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Linear-quadratic optimal control problems (49N10) Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses) (82D30)

Cites Work

• On orthogonal and symplectic matrix ensembles
• Trust Region Methods
• Aging of spherical spin glasses
• Classical particle in a box with random potential: exploiting rotational symmetry of replicated Hamiltonian
• The spectrum edge of random matrix ensembles.
• Spectral density asymptotics for Gaussian and Laguerre β-ensembles in the exponentially small region
• Large deviations of the maximal eigenvalue of random matrices
• Title not available (Why is that?)
• The quadratic eigenvalue problem
• Complexity of random energy landscapes, glass transition, and absolute value of the spectral determinant of random matrices
• Large deviations of the extreme eigenvalues of random deformations of matrices
• The largest eigenvalue of rank one deformation of large Wigner matrices
• Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
• The largest eigenvalue of small rank perturbations of Hermitian random matrices
• Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
• Random Matrices and Complexity of Spin Glasses
• A constrained eigenvalue problem
• Minimizing a quadratic over a sphere
• Edge effects in some perturbations of the Gaussian unitary ensemble
• Random Fields and Spin Glasses
• Large Deviations of Extreme Eigenvalues of Random Matrices
• Complexity of random smooth functions on the high-dimensional sphere
• Bethe ansatz solution for one-dimensional directed polymers in random media
• LU decomposition of matrices with augmented dense constraints
• Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity
• Full dynamical solution for a spherical spin-glass model
• Statistical mechanics of a single particle in a multiscale random potential: Parisi landscapes in finite-dimensional Euclidean spaces
• On the Stationary Values of a Second-Degree Polynomial on the Unit Sphere
• On the dynamics of a spherical spin-glass in a magnetic field
• Title not available (Why is that?)

Cited In (32)

• Large time zero temperature dynamics of the spherical p  =  2-spin glass model of finite size
• Central limit theorems for the real eigenvalues of large Gaussian random matrices
• Landscape complexity beyond invariance and the elastic manifold
• Expected number and height distribution of critical points of smooth isotropic Gaussian random fields
• Optimization landscape in the simplest constrained random least-square problem
• Fluctuations of the free energy of the spherical Sherrington-Kirkpatrick model with ferromagnetic interaction
• Top eigenvalue of a random matrix: large deviations and third order phase transition
• Statistics of stationary points of random finite polynomial potentials
• Topology trivialization transition in random non-gradient autonomous ODEs on a sphere
• Manifolds pinned by a high-dimensional random landscape: Hessian at the global energy minimum
• Ferromagnetic to paramagnetic transition in spherical spin glass
• Title not available (Why is that?)
• Sharp complexity asymptotics and topological trivialization for the (p, k) spiked tensor model
• Superposition of random plane waves in high spatial dimensions: Random matrix approach to landscape complexity
• Spherical spin glass model with external field
• The Petrov type D isolated null surfaces
• Nonlinear analog of the complexity-stability transition in random dynamical systems: a replica calculation
• Many-body-localization transition: sensitivity to twisted boundary conditions
• Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass
• Kac–Rice fixed point analysis for single- and multi-layered complex systems
• Matrix optimization under random external fields
• Quenched complexity of equilibria for asymmetric generalized Lotka–Volterra equations
• Exponential number of equilibria and depinning threshold for a directed polymer in a random potential
• Finite size effects and loss of self-averageness in the relaxational dynamics of the spherical Sherrington–Kirkpatrick model
• Triviality of the geometry of mixed \(p\)-spin spherical Hamiltonians with external field
• Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
• Overlaps of a spherical spin glass model with microscopic external field
• Hessian spectrum at the global minimum of high-dimensional random landscapes
• Free energy fluctuations of the two-spin spherical SK model at critical temperature
• Central limit theorem near the critical temperature for the overlap in the 2-spin spherical SK model
• Diversity-induced trivialization and resilience of neural dynamics
• A spin Glass model for reconstructing nonlinearly encrypted signals corrupted by noise

This page was built for publication: Topology trivialization and large deviations for the minimum in the simplest random optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2016530)