Conditioning the complexity of random landscapes on marginal optima.

Abstract

Marginal optima are minima or maxima of a function with many nearly flat directions. In settings with many competing optima, marginal ones tend to attract algorithms and physical dynamics. Often, the important family of marginal attractors is a vanishing minority compared with nonmarginal optima and other unstable stationary points. We introduce a generic technique for conditioning the statistics of stationary points in random landscapes on their marginality and apply it in three isotropic settings with qualitatively different structures: in the spherical spin-glasses, where the energy is Gaussian and its Hessian is a Gaussian orthogonal ensemble (GOE); in multispherical spin glasses, which are Gaussian but non-GOE; and in sums of squared spherical random functions, which are non-Gaussian. In these problems, we are able to fully characterize the distribution of marginal optima in the landscape, including when they are in the minority.