T-5

Goal: So far we have discussed the equilibrium properties of disordered systems, that are encoded in their partition function and free energy. In this set of problems, we characterize the energy landscape of the spherical $p$-spin, by determining the number of its stationary points.

Key concepts: gradient descent, out-of-equilibrium dynamics, metastable states, Hessian matrices, random matrix theory, Langevin dynamics,?

Dynamics, optimization, trapping local minima

• Energy landscapes. Consider the spherical $p$-spin model discussed in the Problems 2 and 3; The function $E({\vec {\sigma }})$ is an energy landscape: it is a random function defined on configuration space, which is the space all configurations ${\vec {\sigma }}$ belong to. 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 \infty$. Besides the ground state(s), the energy landscape can have other local minima; the fully-connected models of glasses are characterized by the fact that there are plenty of these local minima, see SKETCH.


• Gradient descent and stationary points. Suppose that we are interested in finding the configurations of minimal energy of some model with energy landscape $E({\vec {\sigma }})$, starting from an arbitrary initial configuration ${\vec {\sigma }}_{0}$: we can think about a dynamics in which we progressively update the configuration of the system 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{\vec {\sigma }}(t)}{dt}}=-\nabla _{\perp }E({\vec {\sigma }})$

  where the configuration changes in time moving in the direction of the gradient of the energy landscape restricted to the sphere, $\nabla _{\perp }E({\vec {\sigma }})$. The dynamics stops when it reaches a stationary point , i.e. a configuration where $\nabla _{\perp }E({\vec {\sigma }})=0$. If the landscape has a simple, convex structure, this will be the ground state one is seeking for; 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. SKETCH



• The landscape’s complexity. To understand the structure of the energy landscape and to guess where gradient descent dynamics (or its variation) are expected to converge, it is useful to characterize the distribution of the stationary points, i.e. the number ${\mathcal {N}}(\epsilon )$ of such configuration having a given energy density $\epsilon$. In fully-connected models of glasses, this quantity has an exponential scaling, ${\mathcal {N}}(\epsilon )\sim {\text{exp}}\left(N\Sigma (\epsilon )\right)$, where $\Sigma (\epsilon )$ is the complexity of the landscape. ^[1]

Problem 5.1: the Kac-Rice method and the complexity

In this Problem, we set up the computation of the annealed complexity of the spherical $p$-spin model, which is defined by

$\Sigma _{\text{a}}(\epsilon )=\lim _{N\to \infty }{\frac {1}{N}}\log {\overline {{\mathcal {N}}(\epsilon )}},\quad \quad {\mathcal {N}}(\epsilon )=\left\{{\text{number stat. points of energy density }}\epsilon \right\}$

1. The Kac-Rice formula. Consider first a random function of one variable $f(x)$ defined on an interval $[a,b]$, and let ${\mathcal {N}}$ be the number of points $x$ such that $f(x)=0$. Justify why

   ${\overline {\mathcal {N}}}=\int _{a}^{b}dx\,p_{0}(x),\quad \quad p_{0}(x)={\overline {\delta (f(x))|f'(x)|}}$

   where $p_{0}(x)$ is the probability density that $x$ is a zero of the function. In particular, why is the derivative of the function appearing in this formula? Consider now the number of stationary points ${\mathcal {N}}(\epsilon )$ of the $p$-spin energy landscape, which satisfy $\nabla _{\perp }E({\vec {\sigma }})=0$. Justify why the generalization of the formula above gives

   ${\overline {{\mathcal {N}}(\epsilon )}}=\int _{S_{N}}d{\vec {\sigma }}\,p_{\epsilon }({\vec {\sigma }}),\quad \quad p_{\epsilon }({\vec {\sigma }})={\overline {|{\text{det}}\nabla _{\perp }^{2}E({\vec {\sigma }})|\,\,\delta (\nabla _{\perp }E({\vec {\sigma }})=0)\,\,\delta (E({\vec {\sigma }})-N\epsilon )}}$

   where $p_{\epsilon }({\vec {\sigma }})$ is the probability density that ${\vec {\sigma }}$ is a stationary point of energy density $\epsilon$, and $\nabla _{\perp }^{2}E({\vec {\sigma }})$ is the Hessian matrix of the function $E({\vec {\sigma }})$ restricted to the sphere.^[2]

2. Statistical rotational invariance. Recall the expression of the correlations of the energy landscape of the $p$-spin computed in Problem 2.1: in which sense the correlation function is rotationally invariant? Justify why rotational invariance implies that

   ${\overline {{\mathcal {N}}(\epsilon )}}=(2\pi e)^{\frac {N}{2}}\,p_{\epsilon }({\vec {1}})$

   where ${\vec {1}}=(1,1,1,\cdots ,1)$ is one fixed vector belonging to the surface of the sphere. Where does the prefactor arise from?

3. Gaussianity and correlations. Determine the distribution of the quantity $E({\vec {1}})$. Show that the components of the vector $\nabla E({\vec {1}})$ are Gaussian random variables with zero mean and covariances

   ${\overline {(\nabla E)_{i}\,(\nabla E)_{j}}}={\frac {p}{2}}\,\delta _{ij}+O\left({\frac {1}{N}}\right)$

   The quantity $\nabla _{\perp }E({\vec {1}})$ can be shown to be uncorrelated to $E({\vec {1}}),\nabla _{\perp }^{2}E({\vec {1}})$. The entries of the $(N-1)\times (N-1)$ matrix $\nabla _{\perp }^{2}E({\vec {\sigma }})$ are also Gaussian variables. Computing their correlation, one finds that the matrix conditioned to the fact that $E({\vec {1}})=N\epsilon$ can be written as

   $[\nabla _{\perp }^{2}E({\vec {1}})]_{\alpha \beta }=\left[{\hat {\Pi }}\nabla ^{2}E({\vec {1}}){\hat {\Pi }}-N^{-1}p\,E({\vec {\sigma }})\mathbb {I} \right]_{\alpha \beta }=G_{\alpha \beta }-p\epsilon \,\delta _{\alpha \beta },$

   where the matrix $G$ has random entries with zero average and correlations

   ${\overline {{G}_{\alpha \beta }\,{G}_{\gamma \delta }}}={\frac {p(p-1)}{2N}}\left(\delta _{\alpha \gamma }\delta _{\beta \delta }+\delta _{\alpha \delta }\delta _{\beta \gamma }\right)$

   Combining everything, show that this implies

   ${\overline {{\mathcal {N}}(\epsilon )}}=(2\pi e)^{\frac {N}{2}}\,{\frac {1}{(\pi \,p)^{\frac {N-1}{2}}}}\;{\sqrt {\frac {N}{\pi }}}e^{-N\epsilon ^{2}}\;{\overline {|{\text{det}}\left(G-p\epsilon \mathbb {I} \right)|}}$

Problem 5.2: the Hessian and random matrix theory

To get the complexity, 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.

1. Gaussian Random matrices. Show that the matrix $G$ is a GOE matrix, i.e. a matrix taken from the Gaussian Orthogonal Ensemble, meaning that it is a symmetric matrix with distribution $P(G)=Z_{N}^{-1}e^{-{\frac {N}{4\sigma ^{2}}}{\text{Tr}}G^{2}}.$ What is the value of $\sigma ^{2}$? How can these matrices be generated numerically?

2. Eigenvalue density and concentration. Let $\lambda _{\alpha }$ be the eigenvalues of the matrix $G$. Show that the following identity holds:

   ${\overline {|{\text{det}}\left({\hat {\Pi }}\nabla ^{2}E({\vec {1}}){\hat {\Pi }}-p\epsilon \mathbb {I} \right)|}}={\overline {{\text{exp}}\left[(N-1)\left(\int d\lambda \,\rho _{N}(\lambda )\,\log |\lambda -p\epsilon |\right)\right]}},\quad \quad \rho _{N}(\lambda )={\frac {1}{N-1}}\sum _{\alpha =1}^{N-1}\delta (\lambda -\lambda _{\alpha })$

   where $\rho _{N}(\lambda )$ is the empirical eigenvalue density. It can be shown that if $G$ is a GOE matrix, the distribution of the empirical density has a large deviation form (recall TD1) with speed $N^{2}$, meaning that $P[\rho ]=e^{-N^{2}\,g[\rho ]}$ where now $g[\cdot ]$ is a functional (a function of a function). Using a saddle point argument, show that this implies

   ${\overline {{\text{exp}}\left[(N-1)\left(\int d\lambda \,\rho _{N}(\lambda )\,\log |\lambda -p\epsilon |\right)\right]}}={\text{exp}}\left[N\left(\int d\lambda \,\rho _{\text{ty}}(\lambda )\,\log |\lambda -p\epsilon |\right)+o(N)\right]$

   where $\rho _{\text{ty}}(\lambda )$ is the typical value of the eigenvalue density, which satisfies $g[\rho _{\text{ty}}]=0$.

3. The semicircle, the threshold and the ground state. The eigenvalue density of GOE matrices is self-averaging, and it equals to

   $\lim _{N\to \infty }\rho _{N}(\lambda )=\lim _{N\to \infty }{\overline {\rho _{N}}}(\lambda )=\rho _{\text{ty}}(\lambda )={\frac {1}{2\pi \sigma ^{2}}}{\sqrt {4\sigma ^{2}-\lambda ^{2}}}$

   • Check this numerically: generate matrices for various values of $N$, plot their empirical eigenvalue density and compare with the asymptotic curve. Is the convergence faster in the bulk, or in the extreme of the support of the density?
   • Combining all the results of the previous problems, show that the annealed complexity is $\Sigma _{\text{a}}(\epsilon )={\frac {1}{2}}\log[4e(p-1)]-\epsilon ^{2}+I_{p}(\epsilon ),\quad \quad I_{p}(\epsilon )={\frac {2}{\pi }}\int dx{\sqrt {1-\left(x+{\frac {\epsilon }{\epsilon _{\text{th}}}}\right)^{2}}}\,\log |x|,\quad \quad \epsilon _{\text{th}}={\sqrt {\frac {2(p-1)}{p}}}.$
   • Show that $\epsilon _{\text{th}}$ is a critical value where a transition occurs for the complexity. What happens to the eigenvalue density in $I_{p}(\epsilon )$ when this value of energy is attained? Recalling that this is the eigenvalue density is that of the Hessian matrix of the landscape, explain why the stationary points at energy $\epsilon _{\text{th}}$ are marginally stable .
   • The integral $I_{p}(\epsilon )$ can be computed explicitly, and one finds: $I_{p}(\epsilon )={\begin{cases}&{\frac {\epsilon ^{2}}{\epsilon _{\text{th}}^{2}}}-{\frac {1}{2}}+{\frac {\epsilon }{\epsilon _{\text{th}}}}{\sqrt {{\frac {\epsilon ^{2}}{\epsilon _{\text{th}}^{2}}}-1}}+\log \left(-{\frac {\epsilon }{\epsilon _{\text{th}}}}+{\sqrt {{\frac {\epsilon ^{2}}{\epsilon _{\text{th}}^{2}}}-1}}\right)-\log 2\quad {\text{if}}\quad \epsilon \leq \epsilon _{\text{th}}\\&{\frac {\epsilon ^{2}}{\epsilon _{\text{th}}^{2}}}-{\frac {1}{2}}-\log 2\quad {\text{if}}\quad \epsilon >\epsilon _{\text{th}}\end{cases}}$

     Plot the annealed complexity, and determine numerically where it vanishes: why is the corresponding energy density equal to the ground state energy density?

Notes

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

[2] - We define with ${\hat {\Pi }}({\vec {\sigma }})$ the projector on the tangent plane to the sphere at ${\vec {\sigma }}$: this is the plane orthogonal to the vector ${\vec {\sigma }}$. The gradient $\nabla _{\perp }E({\vec {\sigma }})$ is a $(N-1)$-dimensional vector that is obtained projecting the gradient $[\nabla E({\vec {\sigma }})]_{i}=\partial E/\partial \sigma _{i}$ on the tangent plane, $\nabla _{\perp }E({\vec {\sigma }})={\hat {\Pi }}\nabla E({\vec {\sigma }})$. The Hessian $\nabla _{\perp }^{2}E({\vec {\sigma }})$ is a $(N-1)\times (N-1)$-dimensional matrix that is obtained from the Hessian $[\nabla ^{2}E({\vec {\sigma }})]_{ij}=\partial ^{2}E/\partial \sigma _{i}\partial \sigma _{j}$ as $\nabla _{\perp }^{2}E({\vec {\sigma }})={\hat {\Pi }}({\vec {\sigma }})\,\nabla ^{2}E({\vec {\sigma }})\,{\hat {\Pi }}({\vec {\sigma }})-N^{-1}\nabla E({\vec {\sigma }})\cdot {\vec {\sigma }}\mathbb {I}$ where $\mathbb {I}$ is the identity matrix.