Topology trivialization and large deviations for the minimum in the simplest random optimization
From MaRDI portal
Publication:2016530
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 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.
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
Cites work
- scientific article; zbMATH DE number 2174437 (Why is no real title available?)
- scientific article; zbMATH DE number 2247572 (Why is no real title available?)
- LU decomposition of matrices with augmented dense constraints
- A constrained eigenvalue problem
- Aging of spherical spin glasses
- Bethe ansatz solution for one-dimensional directed polymers in random media
- Classical particle in a box with random potential: exploiting rotational symmetry of replicated Hamiltonian
- Complexity of random energy landscapes, glass transition, and absolute value of the spectral determinant of random matrices
- Complexity of random smooth functions on the high-dimensional sphere
- Edge effects in some perturbations of the Gaussian unitary ensemble
- Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices
- Full dynamical solution for a spherical spin-glass model
- Large Deviations of Extreme Eigenvalues of Random Matrices
- Large deviations of the extreme eigenvalues of random deformations of matrices
- Large deviations of the maximal eigenvalue of random matrices
- Minimization of a Large-Scale Quadratic FunctionSubject to a Spherical Constraint
- Minimizing a quadratic over a sphere
- On orthogonal and symplectic matrix ensembles
- 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
- Random Fields and Spin Glasses
- Random matrices and complexity of spin glasses
- Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity
- Spectral density asymptotics for Gaussian and Laguerre \(\beta \)-ensembles in the exponentially small region
- Statistical mechanics of a single particle in a multiscale random potential: Parisi landscapes in finite-dimensional Euclidean spaces
- The largest eigenvalue of rank one deformation of large Wigner matrices
- The largest eigenvalue of small rank perturbations of Hermitian random matrices
- The quadratic eigenvalue problem
- The spectrum edge of random matrix ensembles.
- Trust Region Methods
Cited in
(32)- Exponential number of equilibria and depinning threshold for a directed polymer in a random potential
- 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
- Overlaps of a spherical spin glass model with microscopic external field
- Statistics of stationary points of random finite polynomial potentials
- Spherical spin glass model with external field
- Central limit theorems for the real eigenvalues of large Gaussian random matrices
- Diversity-induced trivialization and resilience of neural dynamics
- Nonlinear analog of the complexity-stability transition in random dynamical systems: a replica calculation
- Hessian spectrum at the global minimum of high-dimensional random landscapes
- Many-body-localization transition: sensitivity to twisted boundary conditions
- Landscape complexity beyond invariance and the elastic manifold
- Free energy fluctuations of the two-spin spherical SK model at critical temperature
- Topology trivialization transition in random non-gradient autonomous ODEs on a sphere
- Quenched complexity of equilibria for asymmetric generalized Lotka–Volterra equations
- Expected number and height distribution of critical points of smooth isotropic Gaussian random fields
- Central limit theorem near the critical temperature for the overlap in the 2-spin spherical SK model
- Manifolds pinned by a high-dimensional random landscape: Hessian at the global energy minimum
- Ferromagnetic to paramagnetic transition in spherical spin glass
- A spin Glass model for reconstructing nonlinearly encrypted signals corrupted by noise
- Finite size effects and loss of self-averageness in the relaxational dynamics of the spherical Sherrington–Kirkpatrick model
- Optimization landscape in the simplest constrained random least-square problem
- scientific article; zbMATH DE number 566075 (Why is no real title available?)
- The Petrov type D isolated null surfaces
- Triviality of the geometry of mixed \(p\)-spin spherical Hamiltonians with external field
- Kac-Rice fixed point analysis for single- and multi-layered complex systems
- Counting equilibria in a random non-gradient dynamics with heterogeneous relaxation rates
- Matrix optimization under random external fields
- Large time zero temperature dynamics of the spherical p = 2-spin glass model of finite size
- 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
- Replica-symmetry breaking transitions in the large deviations of the ground-state of a spherical spin-glass
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)
