Optimization landscape in the simplest constrained random least-square problem

TY - JOUR

T1 - Optimization landscape in the simplest constrained random least-square problem

AU - Fyodorov, Yan V.

AU - Tublin, Rashel

N1 - Funding Information: The research of the first author was supported by the EPSRC Grant EP/V002473/1 Random Hessians and Jacobians: theory and applications. Publisher Copyright: © 2022 The Author(s). Published by IOP Publishing Ltd.

PY - 2022/6/17

Y1 - 2022/6/17

N2 - 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 a system of M linear equations in N unknowns: ( a k , x ) = b k , k = 1, ..., M on the N-sphere x 2 = N. We treat both the N-component vectors 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 overcomplete case M > N in the framework of the Kac-Rice approach combined with the random matrix theory for Wishart ensemble. Then we perform its asymptotic analysis as N → ∞ at a fixed α = 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 λ min associated with the problem, and in this way to find its most probable value. This can be further used to predict the asymptotic mean minimal value Emin of the loss function as N → ∞. Finally, we develop an alternative approach based on the replica trick to conjecture the form of the large deviation function for the density of Emin at N ≫ 1 and any fixed ratio α = M/N > 0. As a by-product, we find the compatibility threshold α c < 1 which is the value of α beyond which a large random linear system on the N-sphere becomes typically incompatible.

AB - 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 a system of M linear equations in N unknowns: ( a k , x ) = b k , k = 1, ..., M on the N-sphere x 2 = N. We treat both the N-component vectors 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 overcomplete case M > N in the framework of the Kac-Rice approach combined with the random matrix theory for Wishart ensemble. Then we perform its asymptotic analysis as N → ∞ at a fixed α = 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 λ min associated with the problem, and in this way to find its most probable value. This can be further used to predict the asymptotic mean minimal value Emin of the loss function as N → ∞. Finally, we develop an alternative approach based on the replica trick to conjecture the form of the large deviation function for the density of Emin at N ≫ 1 and any fixed ratio α = M/N > 0. As a by-product, we find the compatibility threshold α c < 1 which is the value of α beyond which a large random linear system on the N-sphere becomes typically incompatible.

KW - random landscapes

KW - random matrices

KW - random optimization

UR - http://www.scopus.com/inward/record.url?scp=85131411266&partnerID=8YFLogxK

U2 - 10.1088/1751-8121/ac6d8e

DO - 10.1088/1751-8121/ac6d8e

M3 - Article

AN - SCOPUS:85131411266

SN - 1751-8113

VL - 55

JO - Journal of Physics A

JF - Journal of Physics A

IS - 24

M1 - 244008

ER -