Replica Symmetry Breaking Condition Exposed by Random Matrix Calculation of Landscape Complexity

By Yan V. Fyodorov, Ian Williams. 2007

118 citations recorded by the source corpus.

Abstract We start with a rather detailed, general discussion of recent results of the replica approach to statistical mechanics of a single classical particle placed in a random N(≫1)-dimensional Gaussian landscape and confined by a spherically symmetric potential suitably growing at infinity. Then we employ random matrix methods to calculate the density of stationary points, as well as minima, of the associated energy surface. This is used to show that for a generic smooth, concave confining potentials the condition of the zero-temperature replica symmetry breaking coincides with one signaling that both mean total number of stationary points in the energy landscape, and the mean number of minima are exponential in N. For such systems the (annealed) complexity of minima vanishes cubically when approaching the critical confinement, whereas the cumulative annealed complexity vanishes quadratically. Different behaviour reported in our earlier short communication (Fyodorov et al. in JETP Lett. 85:261, 2007) was due to non-analyticity of the hard-wall confinement potential. Finally, for the simplest case of parabolic confinement we investigate how the complexity depends on the index of stationary points. In particular, we show that in the vicinity of critical confinement the saddle-points with a positive annealed complexity must be close to minima, as they must have a vanishing fraction of negative eigenvalues in the Hessian.

Subfields: Condensed Matter Physics, Materials Chemistry, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Condensed Matter Physics

In Materials Chemistry

In Statistical and Nonlinear Physics

Citations in the corpus

Entropy-SGD: biasing gradient descent into wide valleys (2016, neutral): “They also relate to earlier studies such as Baldi & Hornik (1989); Fyodorov & Williams (2007); Bray & Dean (2007) which show that critical points with high training error are exponentially likely to be saddle points with many negative directions and all local minima are likely to have error that is…”
An empirical analysis of the optimization of deep network loss surfaces (2016, background): “Some have characterized the critical points of deep linear neural networks [2, 28] and high-dimensional, random Gaussian error functions [4, 9, 11, 24].”
Local minima in training of neural networks (2016, background): “In particular Fyodorov & Williams (2007); Bray & Dean (2007) showed, using the Replica Theory (Parisi, 2007), that random Gaussian error functions have a particular friendly structure.”
On the saddle point problem for non-convex optimization (2014, background): “…at a critical point with error very close to the global minimum is not a fully unconstrained random Gaussian matrix; the fact that the error is so small, shifts its eigenvalue distribution to the right, so that more eigenvalues are positive Bray and Dean (2007); Fyodorov and Williams (2007).”
An Empirical Analysis of Deep Network Loss Surfaces (2016, methodology): “One approach is to analogize the states of neurons as the magnetics dipoles used in spherical spinglass Ising models from statistical physics (Parisi, 2016; Fyodorov & Williams, 2007; Bray & Dean, 2007).”
Local minima in training of deep networks (2017, background): “The claim is that the error structure of neural networks might follow the same structure as that of random Gaussian fields who have been recently understood and studied in Fyodorov & Williams (2007); Bray & Dean (2007).”
Identifying and attacking the saddle point problem in high-dimensional non-convex optimization (2014, background): “Fyodorov and Williams (2007) exponentially rare in the dimensionality of the problem, but saddle points with many negative and approximate plateau directions are exponentially likely.”
Random Matrices and Complexity of Spin Glasses (2010, methodology): “A variant of our approach has also been used in a prior work by Fyodorov [Fyo04] and Fyodorov and Williams [FW07].”
On the energy landscape of deep networks (2015, methodology): “A more precise statement is proved for spin glasses in (Fyodorov and Williams, 2007).”
The Loss Surfaces of Multilayer Networks (2014, background): “Earlier theoretical analyses [Baldi and Hornik, 1989, Wigner, 1958, Fyodorov and Williams, 2007, Bray and Dean, 2007] suggest the existence of a certain structure of critical points of random Gaussian error functions on high dimensional continuous spaces.”