View source for T-5

<strong>Goal: </strong> 
In this set of problems, we characterize the energy landscape of the spherical <math>p</math>-spin by studying its metastable states (local minima).
<br>
<strong>Techniques: </strong> Kac-Rice formula, conditional probabilities.
<br>


== Dynamics, optimization, trapping local minima ==
[[File:Landscapes-GDD.png|thumb|right|x200px|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.

<ul>
 

<li> '''Rugged landscapes.''' Consider the spherical <math>p</math>-spin model: <math>E(\vec{\sigma})</math> is an <ins> energy landscape </ins>. It is a random function on configuration space (the surface <math> \mathcal{S}_N </math> 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 <math> Z </math> in the limit <math> \beta \to \infty </math>. 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 <ins> rugged</ins>, see the sketch. 
</li>
<br>


<li> '''Optimization by gradient descent.''' Suppose that we are interested in finding the configurations of minimal energy, starting from an arbitrary configuration <math>\vec{\sigma}_0</math>: 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 <ins>gradient descent</ins>,
<math display="block">
\frac{d \vec{\sigma}(t)}{dt}=- \nabla_{\perp} E(\vec{\sigma}) 
</math> 
where <math>\nabla_{\perp} E(\vec{\sigma})</math> is the gradient of the landscape restricted to the sphere. The dynamics stops when it reaches a  <ins> stationary point </ins>, a configuration where <math>  \nabla_\perp E(\vec{\sigma})=0</math>. 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).
</li>
<br>

<li> '''Stationary points and complexity.''' To guess where gradient descent dynamics (or <ins> Langevin dynamics </ins>) are expected to converge, it is useful to understand the distribution of the stationary points, i.e. the number <math> \mathcal{N}(\epsilon)</math> of such configuration having a given energy density <math> \epsilon </math>. In fully-connected models, this quantity has an exponential scaling, <math> \mathcal{N}(\epsilon) \sim \text{exp}\left(N \Sigma(\epsilon) \right)</math>, where  <math>  \Sigma(\epsilon)</math> is the landscape’s <ins>complexity</ins>. <sup>[[#Notes|[*] ]]</sup>. Stationary points can be stable (local minima), or unstable (saddles or local maxima): their stability is encoded in the spectrum of the <ins> Hessian matrix </ins> <math>{\nabla}_\perp^2 E(\vec{\sigma})</math>: when all the eigenvalues of the Hessian are positive, the point is a local minimum (and a saddle otherwise).
</li>
</ul>
<br>

<div style="font-size:89%">
: <small>[*]</small> - This quantity looks similar to the entropy <math> S(\epsilon) </math> we computed for the REM in Problem 1. However, while the entropy counts all configurations at a given energy density, the complexity <math> \Sigma(\epsilon) </math> accounts only for the stationary points.
</div>
<br>

== Problems ==
In this and in the following problem, we discuss the computation of the annealed complexity of the spherical <math>p</math>-spin model, which is defined by 
<math display="block">
\Sigma_{\text{a}}(\epsilon)= \lim_{N \to \infty}\; \frac{1}{N}\,\log \, \mathbb{E}[\mathcal{N}(\epsilon)] , \quad \quad \mathcal{N}(\epsilon)= \left\{ \text{number stat. points of energy density }  \epsilon\right\}
</math>
We performed the annealed calculation since it can be shown that the quenched one leads to the same result for this model.

=== Problem 5: the Kac-Rice formula and the complexity ===


<ol>
<li> <em> The Kac-Rice formula.</em> Consider first a random function of one variable <math> f(x)</math> defined on an interval <math> [a,b]</math>, and let <math> \mathcal{N}</math> be the number of points <math> x </math> such that <math> f(x)=0</math>. Justify why
<math display="block">
\mathbb{E}[\mathcal{N}]= \int_a^b dx \,p_0(x) , \quad \quad p_0(x)=\mathbb{E}[\delta(f(x)) \; \text{abs}(f'(x))]
</math>
where <math>  p_0(x) </math> is the probability density that <math> x </math> 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 <math> \mathcal{N}(\epsilon)</math> of the <math>p</math>-spin energy landscape, which satisfy <math> \nabla_\perp E(\vec{\sigma})=0</math>. Justify why the generalization of the formula above gives 
<math display="block">
\mathbb{E}[\mathcal{N}(\epsilon)]= \int_{\mathcal{S}_N} d \vec{\sigma} \,p_{\epsilon}(\vec{\sigma})  , \quad \quad \quad p_{\epsilon}(\vec{\sigma})=\mathbb{E}\left[{|\text{det} {\nabla}_\perp^2 E (\vec{\sigma})|\,\, \delta(\nabla_\perp E(\vec{\sigma})=0) \, \,\delta(E(\vec{\sigma})- N \epsilon)}\right]
</math>
where <math> p_{\epsilon}(\vec{\sigma})</math> is the probability density that <math> \vec \sigma</math> is a stationary point of energy density <math> \epsilon </math>, and <math> {\nabla}_\perp^2 E (\vec{\sigma}) </math> is the Hessian matrix of the function  <math> E (\vec{\sigma}) </math> restricted to the sphere.
</li>
</ol>
<br>

<ol start="2">
<li><em> Statistical rotational invariance.</em> If you solved <code>Exercise 9</code>, you have shown that the correlations of the energy landscape of the <math>p</math>-spin model are <math>\mathbb{E}[E(\vec{\sigma}) E(\vec{\tau})]= N q(\vec{\sigma}, \vec{\tau})^p</math>, where <math>q</math> is the overlap: in which sense the correlation function is rotationally invariant? Justify why rotational invariance implies that 
<math display="block">
\mathbb{E}[\mathcal{N}(\epsilon)]= (2 \pi e)^{\frac{N}{2}} \, p_{\epsilon}(\vec{1})
</math>
where <math> \vec{1}=(1,1,1, \cdots, 1) </math> is one fixed vector belonging to the surface of the sphere. Where does the prefactor arise from?
</li>
</ol>
<br>

<ol start="3">
<li><em> Gaussianity and correlations.</em> Show that: 
<math display="block">
\mathbb{E}[\mathcal{N}(\epsilon)]= (2 \pi e)^{\frac{N}{2}} \, \frac{1}{(2 \pi \, p)^{\frac{N-1}{2}}}\; \sqrt{\frac{N}{2 \pi}} e^{-\frac{N \epsilon^2}{2}}\;\overline{|\text{det} \left( M- p  \epsilon \mathbb{I} \right)|}
</math>
by using the following facts:
<ul>
<li> The variables <math> E (\vec{1})</math> and the entries of <math>\nabla_\perp E (\vec{1}), {\nabla}^2_\perp E (\vec{1})</math> are Gaussian. </li>
<li> The <math> N-1 </math> components of <math> \nabla_\perp E (\vec{1})</math> are uncorrelated to <math> E (\vec{1}), {\nabla}^2_\perp E (\vec{1})</math>; they have zero mean and covariances
<math>
\mathbb{E}[(\nabla_\perp E)_\alpha  \, (\nabla_\perp E)_\beta]=  p \, \delta_{\alpha \beta}+O\left(\frac{1}{N} \right).
</math> </li>
<li> The <math>(N-1)\times (N-1) </math> matrix <math> {\nabla}_\perp^2 E (\vec{\sigma}) </math> conditioned to the fact that <math> E(\vec 1)=N \epsilon </math> can be written as 
<math display="block">
[{\nabla}_\perp^2 E(\vec{1})]_{\alpha \beta}=  M_{\alpha \beta}- p  \epsilon\, \delta_{\alpha \beta},
</math>
where the matrix <math> M </math> has random entries with zero average and correlations
<math>
\overline{{M}_{\alpha \beta} \, {M}_{\gamma \delta}}= \frac{p (p-1)}{ N} \left( \delta_{\alpha \gamma} \delta_{\beta \delta}+ \delta_{\alpha \delta} \delta_{\beta \gamma}\right).
</math>
</ul>
</li>

</ol>
<br>

== Check out: key concepts ==

Gradient descent, rugged landscapes, metastable states, landscape’s complexity.






<!----------OLD---------
First, a few notions of geometry: we define with <math> \hat \Pi(\vec{\sigma}) </math> the projector on  the tangent plane to the sphere at <math> \vec{\sigma}</math>: this is the plane orthogonal to the vector <math> \vec{\sigma}</math>. The gradient <math> \nabla_\perp E(\vec{\sigma}) </math> is a <math> (N-1)</math>-dimensional vector that is obtained projecting the gradient <math> [\nabla E(\vec{\sigma})]_i=\partial E/\partial \sigma_i </math> on the tangent plane, <math> \nabla_\perp E(\vec{\sigma})=\hat \Pi \nabla E(\vec{\sigma})</math>. The Hessian <math> \nabla^2_\perp E(\vec{\sigma}) </math> is a <math> (N-1) \times (N-1)</math>-dimensional matrix that is obtained from the Hessian <math> [\nabla^2 E(\vec{\sigma})]_{ij}=\partial^2 E/\partial \sigma_i \partial \sigma_j </math> as <math> \nabla^2_\perp 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}</math> where <math> \mathbb{I}</math> is the identity matrix. <br>-->