T-6

Goal: Complete the characterisation of the energy landscape of the spherical $p$-spin.
Techniques: saddle point, random matrix theory.

Problems

Problem 6: the Hessian at the stationary points, and random matrix theory

This is a continuation of problem 5. To get the complexity of the spherical $p$-spin, it remains to compute the expectation value of the determinant of the Hessian matrix: this is the goal of this problem. We will do this exploiting results from random matrix theory discussion in the Tutorial and Exercise 4 .

1. Gaussian Random matrices. Show that the matrix $M$, defined in Problem 5, is a GOE matrix, i.e. a matrix taken from the Gaussian Orthogonal Ensemble, meaning that it is a symmetric matrix with distribution $P_N(M)=Z_N^{-1}\text{exp}(-\frac{N}{4{\sigma }^2}\text{Tr}{M}^2)$ where $Z_N$ is a normalization. What is the value of ${\sigma }^2$?

2. Eigenvalue density and concentration. Let ${\lambda }_{\alpha }$ be the eigenvalues of the matrix $M$. Show that the following identity holds: $$\mathbb{𝔼}[|\text{det}(M-pϵ\mathbb{𝕀})|]=\mathbb{𝔼}\left[\text{exp}((N-1)\int d\lambda {\rho }_{N-1}(\lambda )\log |\lambda -pϵ|)\right],{\rho }_{N-1}(\lambda )=\frac{1}{N-1}\sum _{\alpha =1}^{N-1}\delta (\lambda -{\lambda }_{\alpha })$$ where ${\rho }_{N-1}(\lambda )$ is the empirical eigenvalue distribution. It can be shown that if $M$ is a GOE matrix, the distribution of the empirical distribution has a large deviation form with speed $N^2$, meaning that $P_N[\rho ]=e^{-N^{2}g[\rho ]}$ where now $g[\cdot ]$ is a functional. Using a saddle point argument, show that this implies $$\mathbb{𝔼}\left[\text{exp}((N-1)\int d\lambda {\rho }_{N-1}(\lambda )\log |\lambda -pϵ|)\right]=\text{exp}[N\int d\lambda {\rho }_{\mathrm{\infty }}(\lambda +pϵ)\log |\lambda |+o(N)]$$ where ${\rho }_{\mathrm{\infty }}(\lambda )$ is the typical value of the eigenvalue density, which satisfies $g[{\rho }_{\mathrm{\infty }}]=0$.

3. The semicircle and the complexity. The eigenvalue density of GOE matrices is self-averaging, and it equals to $$\underset{N\to \mathrm{\infty }}{\lim }{\rho }_N(\lambda )=\underset{N\to \mathrm{\infty }}{\lim }\mathbb{𝔼}[{\rho }_N(\lambda )]={\rho }_{\mathrm{\infty }}(\lambda )=\frac{1}{2\pi {\sigma }^2}\sqrt{4{\sigma }^2-{\lambda }^2}$$
   Combining all the results, show that the annealed complexity is $${\mathrm{\Sigma }}_{\text{a}}(ϵ)=\frac{1}{2}\log [4e(p-1)]-\frac{{ϵ}^2}{2}+I_p(ϵ),I_p(ϵ)=\frac{2}{\pi }\int dx\sqrt{1-{(x-\frac{ϵ}{{ϵ}_{\text{th}}})}^2}\log |x|,{ϵ}_{\text{th}}=-2\sqrt{\frac{p-1}{p}}.$$ The integral $I_p(ϵ)$ can be computed explicitly, and one finds: $$I_p(ϵ)=\{\begin{array}{ll}& \frac{{ϵ}^2}{{ϵ}_{\text{th}}^2}-\frac{1}{2}-\frac{ϵ}{{ϵ}_{\text{th}}}\sqrt{\frac{{ϵ}^2}{{ϵ}_{\text{th}}^2}-1}+\log (\frac{ϵ}{{ϵ}_{\text{th}}}+\sqrt{\frac{{ϵ}^2}{{ϵ}_{\text{th}}^2}-1})-\log 2\text{if}ϵ\le {ϵ}_{\text{th}}\\ & \frac{{ϵ}^2}{{ϵ}_{\text{th}}^2}-\frac{1}{2}-\log 2\text{if}ϵ>{ϵ}_{\text{th}}\end{array}$$ Plot the annealed complexity, and determine numerically where it vanishes: why is this a lower bound or the ground state energy density?

4. The threshold and the stability. Sketch ${\rho }_{\mathrm{\infty }}(\lambda +pϵ)$ for different values of $ϵ$; recalling that the Hessian encodes for the stability of the stationary points, show that there is a transition in the stability of the stationary points at the critical value of the energy density ${ϵ}_{\text{th}}=-2\sqrt{(p-1)/p}.$ When are the critical points stable local minima? When are they saddles? Why the stationary points at $ϵ={ϵ}_{\text{th}}$ are called marginally stable ?

Dynamics, optimization, trapping local minima

Non-rugged vs rugged energy landscapes.

So far we have discussed the equilibrium properties of disordered systems, that are encoded in their partition function/free energy. When a system (following Langevin, Monte Carlo dynamics) equilibrates at sufficiently large times, its long-time properties are captured by these equilibrium calculations. In glassy systems the equilibration timescales are extremely large: for very large timescales the system does not visit equilibrium configurations, but rather metastable states.

• Rugged landscapes. Consider the spherical $p$-spin model: $E(\overrightarrow{\sigma })$ is an energy landscape . It is a random function on configuration space (the surface ${{𝒮}}_N$ of the sphere). This landscape has its global minimum(a) at the ground state configuration(s): the energy density of the ground state(s) can be obtained studying the partition function $Z$ in the limit $\beta \to \mathrm{\infty }$. Besides the ground state(s), the energy landscape can have other local minima; fully-connected models of glasses are characterized by the fact that there are plenty of these local minima: the energy landscape is rugged, see the sketch.


• Optimization by gradient descent. Suppose that we are interested in finding the configurations of minimal energy, starting from an arbitrary configuration ${\overrightarrow{\sigma }}_0$: we can implement a dynamics in which we progressively update the configuration moving towards lower and lower values of the energy, hoping to eventually converge to the ground state(s). The simplest dynamics of this sort is gradient descent, $$\frac{d\overrightarrow{\sigma }(t)}{dt}=-{\mathrm{\nabla }}_{\perp }E(\overrightarrow{\sigma })$$ where ${\mathrm{\nabla }}_{\perp }E(\overrightarrow{\sigma })$ is the gradient of the landscape restricted to the sphere. The dynamics stops when it reaches a stationary point , a configuration where ${\mathrm{\nabla }}_{\perp }E(\overrightarrow{\sigma })=0$. If the landscape has a convex structure, this will be the ground state; if the energy landscape is very non-convex like in glasses, the end point of this algorithm will be a local minimum at energies much higher than the ground state (see sketch).


• Stationary points and complexity. To guess where gradient descent dynamics (or Langevin dynamics ) are expected to converge, it is useful to understand the distribution of the stationary points, i.e. the number ${𝒩}(ϵ)$ of such configuration having a given energy density $ϵ$. In fully-connected models, this quantity has an exponential scaling, ${𝒩}(ϵ)\sim \text{exp}(N\mathrm{\Sigma }(ϵ))$, where $\mathrm{\Sigma }(ϵ)$ is the landscape’s complexity. ^[*] . Stationary points can be stable (local minima), or unstable (saddles or local maxima): their stability is encoded in the spectrum of the Hessian matrix ${\mathrm{\nabla }}_{\perp }^{2}E(\overrightarrow{\sigma })$: when all the eigenvalues of the Hessian are positive, the point is a local minimum (and a saddle otherwise).

[*] - This quantity looks similar to the entropy $S(ϵ)$ we computed for the REM in Problem 1. However, while the entropy counts all configurations at a given energy density, the complexity $\mathrm{\Sigma }(ϵ)$ accounts only for the stationary points.

Check out: key concepts

Metastable states, Hessian matrices, random matrix theory, landscape’s complexity.