Random Matrices and Complexity of Spin Glasses

By Antonio Auffinger, Gérard Ben Arous, Jirí Cerný. 2010

318 citations recorded by the source corpus.

We give an asymptotic evaluation of the complexity of spherical p‐spin spin glass models via random matrix theory. This study enables us to obtain detailed information about the bottom of the energy landscape, including the absolute minimum (the ground state), and the other local minima, and describe an interesting layered structure of the low critical values for the Hamiltonians of these models. We also show that our approach allows us to compute the related TAPcomplexity and extend the results known in the physics literature. As an independent tool, we prove a large deviation principle for the kth‐largest eigenvalue of the Gaussian orthogonal ensemble, extending the results of Ben Arous, Dembo, and Guionnet. © 2012 Wiley Periodicals, Inc.

Subfields: Discrete Mathematics and Combinatorics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/ca63de58e25f14753085674b883ade3d8ecb7d29

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Statistics and Probability

Citations in the corpus

Neural Networks with Finite Intrinsic Dimension have no Spurious Valleys (2018, background): “In [7], the optimization landscape of multi-layers ReLU networks has been related to spherical spin glasses [1].”
Trainability and Accuracy of Artificial Neural Networks: An Interacting Particle System Approach (2018, background): “The function (5.1) is known to have a number of critical points that grows exponentially with the dimensionality d [2,3,29].”
Empirical Analysis of the Hessian of Over-Parametrized Neural Networks (2017, background): “A theoretical review on this can be found in [Auffinger et al., 2013], while Sagun et al. [2014] and Ballard et al. [2017] provide an experimental simulation as well as a numerical study for neural networks. They notably find that high error local minima traps do not appear when the model is over-pa”
The complexity of spherical p-spin models - a second moment approach (2015, methodology): “For reasons that will be explained later, adapting the argument of [ABAČ13] to this case is impossible.”
Open Problem: The landscape of the loss surfaces of multilayer networks (2015, background): “Note that the term in bold is a Hamiltonian of the spherical spin-glass model Auffinger et al. (2010).”
Gradient Descent Only Converges to Minimizers (2016, background): “The Lojasiewicz inequality is very general as discussed in Bolte et al. (2010); Attouch et al.”
Gradient Descent Converges to Minimizers (2016, background): “We remark that the strict saddle assumption is necessary in the worst case, due to hardness results regarding testing the local optimality of functions whose Hessians are highly degenerate at criticalpoints (e.g, quartic polynomials) [19].”
The Effect of Gradient Noise on the Energy Landscape of Deep Networks (2015, methodology): “As Auffinger et al. (2013) show, we can explicitly compute the limiting value of crt(u) and crtk(u).”
ℓ1-regularized Neural Networks are Improperly Learnable in Polynomial Time (2015, methodology): “After several simplifying assumptions, a neural network can be shown to be a Gaussian ﬁeld whose critical points can be analyzed using the Kac-Rice formula and properties of the Gaussian Orthogonal Ensemble [3, 10, 8].”
On the energy landscape of deep networks (2015, methodology): “This is a zero-mean random variable with bounded second moment, indeed( ν2C 2n )2 n−1 ∑ i=1 E {( 1−W 2i )2} = 2 ( ν2C 2n )2 (n−1); (A-13) for some constant C > 0.”
Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks (2018, methodology): “We use the p-spin energy function [27, 28] as the target function due to its complexity as the dimension grows large.”
Identity Matters in Deep Learning (2016, methodology): “In analogy with residual networks, we will instead parameterize the objective function as min A1,...,A` E‖y − (I +A`) · · · (I +A1)x‖2 .”
The Landscape of the Spiked Tensor Model (2017, methodology): “This fact, together with the explicitly known joint distribution of the eigenvalues of W n, is used in [5] to express the expected determinant in terms of the distribution of one eigenvalue and a normalization that is computed using Selberg’s integral.”
EXPECTED TOPOLOGY OF RANDOM REAL ALGEBRAIC SUBMANIFOLDS (2013, background): “In particular, the asymptotic equidistribution of critical points of random sections over a fixed projective manifold has been studied in [8], [9] and [22], or also [11], [1], [5], while we studied critical points of the restriction of a fixed Morse function on random real hypersurfaces, see [15], [”