Optimization landscape in the simplest constrained random least-square problem

Abstract

We analyze statistical features of the ``optimization landscape'' in a random version of one of the simplest constrained optimization problems of the least-square type: finding the best approximation for the solution of an overcomplete system of $M>N$ linear equations $({\mathbf{a}}_k,\mathbf{x})=b_k,k=1,\dots ,M$ on the $N-$sphere ${\mathbf{x}}^2=N$. We treat both the $N-$component vectors ${\mathbf{a}}_k$ and parameters $b_k$ as independent mean zero real Gaussian random variables. First, we derive the exact expressions for the mean number of stationary points of the least-square loss function in the framework of the Kac-Rice approach combined with the Random Matrix Theory for Wishart Ensemble, and then perform its asymptotic analysis as $N\to \infty$ at a fixed $\alpha =M/N>1$ in various regimes. In particular, this analysis allows to extract the Large Deviation Function for the density of the smallest Lagrange multiplier ${\lambda }_{min}$ associated with the problem, and in this way to find its most probable value. This can be further used to predict the asymptotic minimal value ${\mathcal{E}}_{min}$ of the loss function as $N\to \infty$. Finally, we develop an alternative approach based on the replica trick to conjecture the form of the Large Deviation function for the density of ${\mathcal{E}}_{min}$ at $N\gg 1$. As a by-product, we find the value of the {\it compatibility threshold} ${\alpha }_c$ which is the minimal value of the asymptotic ratio $M/N$ such that the random linear system on the $N-$sphere is typically compatible.

arXiv comment38 pages, 4 figures

References in corpus (21)

• Spin-Glass Theory for Pedestrians
• Large Deviations of Extreme Eigenvalues of Random Matrices
• The statistics of critical points of Gaussian fields on large-dimensional spaces
• Complexity of random smooth functions on the high-dimensional sphere
• Negative moments of characteristic polynomials of random matrices: Ingham-Siegel integral as an alternative to Hubbard-Stratonovich transformation
• Critical Behaviour of the Number of Minima of a Random Landscape at the Glass Transition Point and the Tracy-Widom distribution
• Complex energy landscapes in spiked-tensor and simple glassy models: ruggedness, arrangements of local minima and phase transitions
• Topology trivialization and large deviations for the minimum in the simplest random optimization
• Large Deviations of the Smallest Eigenvalue of the Wishart-Laguerre Ensemble
• Multifractality and Freezing Phenomena in Random Energy Landscapes: an Introduction
• Complexity of Random Energy Landscapes, Glass Transition and Absolute Value of Spectral Determinant of Random Matrices
• Moments of Wishart-Laguerre and Jacobi ensembles of random matrices: application to the quantum transport problem in chaotic cavities
• Topology trivialization transition in random non-gradient autonomous ODE's on a sphere
• Triviality of the geometry of mixed $p$-spin spherical Hamiltonians with external field
• The averaged characteristic polynomial for the Gaussian and chiral Gaussian ensembles with a source
• The Loss Surfaces of Neural Networks with General Activation Functions
• Spherical spin glass model with external field
• Large deviation eigenvalue density for the soft edge Laguerre and Jacobi $\beta$-ensembles
• Matrix optimization under random external fields
• A spin glass model for reconstructing nonlinearly encrypted signals corrupted by noise
• Counting stationary points of the loss function in the simplest constrained least-square optimization