From 2573972d0cde8d969db6a66294e76336cc29a09f Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Mon, 22 Jan 2024 17:18:35 +0100 Subject: Some writing an a figure. --- figs/large_deviation.pdf | Bin 0 -> 11693 bytes marginal.tex | 215 +++++++++++++++++++++++++++++++---------------- 2 files changed, 143 insertions(+), 72 deletions(-) create mode 100644 figs/large_deviation.pdf diff --git a/figs/large_deviation.pdf b/figs/large_deviation.pdf new file mode 100644 index 0000000..9149a5a Binary files /dev/null and b/figs/large_deviation.pdf differ diff --git a/marginal.tex b/marginal.tex index 8c7cf0e..0a21499 100644 --- a/marginal.tex +++ b/marginal.tex @@ -19,6 +19,7 @@ maxnames = 100 ]{biblatex} \usepackage{anyfontsize,authblk} +\usepackage{bbold} \usepackage{tikz} @@ -27,15 +28,17 @@ \begin{document} \title{ - None yet + Conditioning the complexity of random landscapes on marginal minima } \author{Jaron Kent-Dobias} \affil{Istituto Nazionale di Fisica Nucleare, Sezione di Roma I} -%\maketitle -%\begin{abstract} -%\end{abstract} +\maketitle +\begin{abstract} +\end{abstract} + +\tableofcontents \section{Introduction} @@ -88,42 +91,79 @@ stationary points be zero, we restrict to marginal minima, either those with a pseudogap in their bulk spectrum or those with outlying eigenvectors. We provide a heuristic to distinguish these two cases. We demonstrate the method on the spherical models, where it is unnecessary but instructive, and on -extensions of the spherical models with non-GOE Hessians where the technique is +extensions of the spherical models with non-\textsc{goe} Hessians where the technique is more useful. -\section{How to condition on the smallest eigenvalue} +\section{Conditioning on the smallest eigenvalue} + + An arbitrary function $g$ of the minimum eigenvalue of a matrix $A$ can be expressed as \begin{equation} g(\lambda_\textrm{min}(A)) =\lim_{\beta\to\infty}\int\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)e^{-\beta\mathbf x^TA\mathbf x}}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')e^{-\beta\mathbf x'^TA\mathbf x'}}g\left(\frac{\mathbf x^TA\mathbf x}N\right) \end{equation} +Assuming \begin{equation} - \lim_{\beta\to\infty}\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)e^{-\beta\mathbf x^TA\mathbf x}}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')e^{-\beta\mathbf x'^TA\mathbf x'}} - =d\mathbf x\,\frac12\left[\delta(\mathbf x_\mathrm{min}(A)-\mathbf x)+\delta(\mathbf x_\mathrm{min}(A)+\mathbf x)\right] + \begin{aligned} + \lim_{\beta\to\infty}\int\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)e^{-\beta\mathbf x^TA\mathbf x}}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')e^{-\beta\mathbf x'^TA\mathbf x'}}&g\left(\frac{\mathbf x^TA\mathbf x}N\right) + =\int\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)\mathbb 1_{\operatorname{ker}(A-\lambda_\mathrm{min}(A)I)}(\mathbf x)}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')\mathbb 1_{\operatorname{ker}(A-\lambda_\mathrm{min}(A)I)}(\mathbf x')}g\left(\frac{\mathbf x^TA\mathbf x}N\right) \\ + &=g(\lambda_\mathrm{min}(A)) + \frac{\int d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)\mathbb 1_{\operatorname{ker}(A-\lambda_\mathrm{min}(A)I)}(\mathbf x)}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')\mathbb 1_{\operatorname{ker}(A-\lambda_\mathrm{min}(A)I)}(\mathbf x')} + =g(\lambda_\mathrm{min}(A)) + \end{aligned} \end{equation} -The first equality makes use of the normalized eigenvector $x_\mathrm{min}(A)$ -associated with the minimum eigenvalue. By definition, -$x_\mathrm{min}(A)^TAx_\mathrm{min}(A)=x_\mathrm{min}(A)^Tx_\mathrm{min}(A)\lambda_\mathrm{min}(A)=N\lambda_\mathrm{min}(A)$ -assuming the normalization is $\|x_\mathrm{min}(A)\|^2=N$. The second equality -extends a technique first introduced in \cite{Ikeda_2023_Bose-Einstein-like} -and used in \cite{Kent-Dobias_2024_Arrangement}. A Boltzmann distribution is introduced over a spherical -model whose Hamiltonian is quadratic with interaction matrix given by $A$. In -the limit of zero temperature, the measure will concentrate on the ground -states of the model, which correspond with the eigenvectors $\pm x_\mathrm{min}$ -associated with the minimal eigenvalue $\lambda_\mathrm{min}$. - -Consider a matrix $A=B+\omega I$ for $B$ a GOE matrix with entries whose variance is $\sigma^2/N$. As an example, we compute -\begin{equation} - e^{NG_\sigma(\omega)}=\overline{\lim_{\beta\to\infty}\int\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)e^{-\beta\mathbf x^T(B+\omega I)\mathbf x}}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')e^{-\beta\mathbf x'^T(B+\omega I)\mathbf x'}}\,\delta\big(\mathbf x^T(B+\omega I)\mathbf x\big)} +The first relation extends a technique first introduced in +\cite{Ikeda_2023_Bose-Einstein-like} and used in +\cite{Kent-Dobias_2024_Arrangement}. A Boltzmann distribution is introduced +over a spherical model whose Hamiltonian is quadratic with interaction matrix +given by $A$. In the limit of zero temperature, the measure will concentrate on +the ground states of the model, which correspond with the eigenspace of $A$ +associated with its minimum eigenvalue $\lambda_\mathrm{min}$. The second +relation uses the fact that, once restricted to the sphere $\mathbf x^T\mathbf +x=N$ and the minimum eigenspace, $\mathbf x^TA\mathbf +x=N\lambda_\mathrm{min}(A)$. + +The relationship is formal, but we can make use of the fact that the integral +expression with a Gibbs distribution can be manipulated with replica +techniques, averaged over, and in general treated with a physicist's toolkit. +In particular, we have specific interest in using +$g(\lambda_\mathrm{min}(A))=\delta(\lambda_\mathrm{min}(A))$, a Dirac +delta-function, which can be inserted into averages over ensembles of matrices +$A$ (or indeed more complicated averages) in order to condition that the +minimum eigenvalue is zero. + +\subsection{Simple example: shifted GOE} + +We demonstrate the efficacy of the technique by rederiving a well-known result: +the large-deviation function for pulling an eigenvalue from the bulk of the +\textsc{goe} spectrum. +Consider an ensemble of $N\times N$ matrices $A=B+\omega I$ for $B$ drawn from the \textsc{goe} ensemble with entries +whose variance is $\sigma^2/N$. We know that the bulk spectrum of $A$ is a +Wigner semicircle with radius $2\sigma$ shifted by a constant $\omega$. +Therefore, for $\omega=2\sigma$, the minimum eigenvalue will typically be zero, +while for $\omega>2\sigma$ the minimum eigenvalue would need to be a large +deviation from the typical spectrum and its likelihood will be exponentially +suppressed with $N$. For $\omega<2\sigma$, the bulk of the typical spectrum contains +zero and therefore a larger $N^2$ deviation, moving an extensive number of +eigenvalues, would be necessary. This final case cannot be quantified by this +method, but instead the nonexistence of a large deviation linear in $N$ appears +as the emergence of an imaginary part in the function. + +As an example, we compute +\begin{equation} \label{eq:large.dev} + e^{NG_\sigma(\omega)}=P_{\lambda_\mathrm{min}(B+\omega I)=0}=\overline{\lim_{\beta\to\infty}\int\frac{d\mathbf x\,\delta(N-\mathbf x^T\mathbf x)e^{-\beta\mathbf x^T(B+\omega I)\mathbf x}}{\int d\mathbf x'\,\delta(N-\mathbf x'^T\mathbf x')e^{-\beta\mathbf x'^T(B+\omega I)\mathbf x'}}\,\delta\big(\mathbf x^T(B+\omega I)\mathbf x\big)} \end{equation} -where the overline is the average over $B$. Using replicas to treat the -denominator and transforming the $\delta$-function to its Fourier +where the overline is the average over $B$, and we have defined the large +deviation function $G_\sigma(\omega)$. Using replicas to treat the denominator ($x^{-1}=\lim_{n\to0}x^{n-1}$) +and transforming the $\delta$-function to its Fourier representation, we have \begin{equation} e^{NG_\sigma(\omega)}=\overline{\lim_{\beta\to\infty}\lim_{n\to0}\int d\lambda\prod_{a=1}^n\left[d\mathbf x_a\,\delta(N-\mathbf x_a^T\mathbf x_a)\right] \exp\left\{-\beta\sum_{a=1}^n\mathbf x_a^T(B+\omega I)\mathbf x_a+\lambda\mathbf x_1^T(B+\omega I)\mathbf x_1\right\}} \end{equation} +having introduced the parameter $\lambda$ in the Fourier representation of the $\delta$-function. +The whole expression, so transformed, is a simple exponential integral linear in the matrix $B$. Taking the average over $B$, we have \begin{equation} e^{NG_\sigma(\omega)} @@ -163,89 +203,112 @@ and \end{equation} Inserting these expressions and taking the limit of $n$ to zero, we find \begin{equation} - \mathcal S(q_0,\tilde q_0,\lambda)=\lambda\omega+\sigma^2\left[ + e^{NG_\sigma(\omega)}=\lim_{\beta\to\infty}\int d\lambda\,dq_0\,d\tilde q_0\,e^{N\mathcal S_\beta(q_0,\tilde q_0,\lambda)} +\end{equation} +with the effective action +\begin{equation} + \mathcal S_\beta(q_0,\tilde q_0,\lambda)=\lambda\omega+\sigma^2\left[ 2\beta^2(q_0^2-\tilde q_0^2)-2\beta\lambda(1-\tilde q_0^2)+\lambda^2 \right]-\log(1-q_0)+\frac12\log(1-2q_0+\tilde q_0^2) \end{equation} -The integral is then given by its value at the stationary point of this -expression with respect to its three arguments. -The extremal conditions are -\begin{align} - 0&=\frac{\partial\mathcal S}{\partial q_0} - =\frac1{1-q_0}-\frac1{1-2q_0+\tilde q_0^2}+4\beta^2\sigma^2q_0 \\ - 0&=\frac{\partial\mathcal S}{\partial \tilde q_0} - =\frac{\tilde q_0}{1-2q_0+\tilde q_0^2}-4\sigma^2(\beta^2-\beta\lambda)\tilde q_0 \\ - 0&=\frac{\partial\mathcal S}{\partial\lambda} - =\omega+2\sigma^2\big(\lambda-\beta(1-\tilde q_0^2)\big) -\end{align} +We need to evaluate the integral above using the saddle point method, but in the limit of $\beta\to\infty$. We expect the overlaps to concentrate on one as $\beta$ goes to infinity. We therefore take \begin{align} q_0=1-y\beta^{-1}-z\beta^{-2}+O(\beta^{-3}) && \tilde q_0=1-\tilde y\beta^{-1}-\tilde z\beta^{-2}+O(\beta^{-3}) \end{align} -The first equations expanded in $\beta$ give -\begin{align} - &0=4\sigma^2\beta^2+\bigg(\frac1{y}-\frac12\frac1{y-\tilde y}-4y\sigma^2\bigg)\beta+O(\beta^0) \\ - &0=-4\sigma^2\beta^2+\bigg(\frac12\frac1{y-\tilde y}+4\sigma^2(\lambda+\tilde y)\bigg)\beta+O(\beta^0) -\end{align} -One cannot satisfy this equation order-by-order in $\beta$. However, a solution -suggests itself: the expansion is singular when $\tilde y=y$. Making this -identification, we find instead -\begin{align} - &0=\left(4\sigma^2-\frac1{y^2+2(z-\tilde z)}\right)\beta^2+\left(\frac1y+\frac{2y\tilde z}{(y^2+2(z-\tilde z))^2}-4\sigma^2y\right)\beta+O(\beta^0) \\ - &0=\left(-4\sigma^2+\frac1{y^2+2(z-\tilde z)}\right)\beta^2+\left(-\frac y{y^2+2(z-\tilde z)}-\frac{2y\tilde z}{(y^2+2(z-\tilde z))^2}+4\sigma^2(y+\lambda)\right)\beta+O(\beta^0) -\end{align} -Finally, expanding the equation for $\lambda$ to lowest order, we have +However, taking the limit with $y\neq\tilde y$ results in an expression for the +action that diverges with $\beta$. To cure this, we must take $\tilde y=y$. The result is \begin{equation} - 0=\omega+2\sigma^2(\lambda-2y)+O(\beta^{-1}) + \mathcal S_\infty(y,z,\tilde z,\lambda) + =\lambda\omega+\sigma^2\big[ + \lambda^2-4(y+z-\tilde z) + \big]+\frac12\log\left(1+2\frac{z-\tilde z}{y^2}\right) \end{equation} -Simultaneously solving these five equations stemming from the coefficients of $\beta$ for $y$, $z$, $\tilde z$, and $\lambda$, we have +Extremizing this action over the new parameters $y$, $\Delta z=z-\tilde z$, and $\lambda$, we have \begin{align} \lambda=-\frac1\sigma\sqrt{\frac{\omega^2}{(2\sigma)^2}-1} && y=\frac1{2\sigma}\left(\frac{\omega}{2\sigma}-\sqrt{\frac{\omega^2}{(2\sigma)^2}-1}\right) - \\ - z=\frac1{2\sigma^2}\left(1-\frac{\omega^2}{(2\sigma)^2}\right) && - \tilde z=\frac1{4\sigma^2}\left(1-\frac{\omega}{2\sigma}\left(\frac\omega{2\sigma}+\sqrt{\frac{\omega^2}{(2\sigma)^2}-1}\right)\right) + \Delta z=\frac1{4\sigma^2}\left(1-\frac{\omega}{2\sigma}\left(\frac\omega{2\sigma}-\sqrt{\frac{\omega^2}{(2\sigma)^2}-1}\right)\right) \end{align} -Inserting this solution into $\mathcal S$ and taking the limit of $\beta$ to zero, we find +Inserting this solution into $\mathcal S_\infty$ we find \begin{equation} - G_\sigma(\omega)=-\frac{\omega}{2\sigma}\sqrt{\frac{\omega^2}{(2\sigma)^2}-1} + G_\sigma(\omega) + =\mathop{\textrm{extremum}}_{y,\Delta z,\lambda}\mathcal S_\infty(y,\Delta z,\lambda) + =-\frac{\omega}{2\sigma}\sqrt{\frac{\omega^2}{(2\sigma)^2}-1} +\log\left[ \frac{\omega}{2\sigma}+\sqrt{\frac{\omega^2}{(2\sigma)^2}-1} \right] \end{equation} -This function is plotted in Fig. For $\omega<2\sigma$ $G_\sigma(\omega)$ has an +This function is plotted in Fig.~\ref{fig:large.dev}. For $\omega<2\sigma$ $G_\sigma(\omega)$ has an imaginary part, which makes any additional integral over $\omega$ highly oscillatory. This indicates that the existence of a marginal minimum for this parameter value corresponds with a large deviation that grows faster than $N$, -rather like $N^2$, since in this regime the bulk of the average spectrum is +rather like $N^2$, since in this regime the bulk of the typical spectrum is over zero and therefore extensively many eigenvalues have to have large deviations in order for the smallest eigenvalue to be zero. For $\omega\geq2\sigma$ this function gives the large deviation function for the probability of seeing a zero eigenvalue given the shift $\omega$. $\omega=2\sigma$ is the maximum of the function with a real value, and -corresponds to the intersection of the average spectrum with zero. - - +corresponds to the intersection of the average spectrum with zero, i.e., a pseudogap. + +\begin{figure} + \centering + \includegraphics{figs/large_deviation.pdf} + \caption{ + The large deviation function $G_\sigma(\omega)$ defined in + \eqref{eq:large.dev} as a function of the shift $\omega$ to the + \textsc{goe} diagonal. As expected, $G_\sigma(2\sigma)=0$, while for + $\omega>2\sigma$ it is negative and for $\omega<2\sigma$ it gains an + imaginary part. + } \label{fig:large.dev} +\end{figure} + +Marginal spectra with a pseudogap and those with simple isolated eigenvalues +are qualitatively different, and more attention may be focused on the former. +Here, we see what appears to be a general heuristic for identifying the saddle +parameters for which the spectrum is psedogapped: the equivalent of this +large-deviation functions will lie on the singular boundary between a purely +real and complex value. + +\subsection{Application to complexity in random landscapes} + +The situation in the study of random landscapes is often as follows: an +ensemble of smooth functions $H:\mathbb R^N\to\mathbb R$ define random +landscapes, often with their configuration space subject to one or more +constraints of the form $g(\mathbf s)=0$ for $\mathbf s\in\mathbb R^N$. The +geometry of such landscapes is studied by their complexity, or the average +logarithm of the number of stationary points with certain properties, e.g., of +marginal minima at a given energy. + +Such problems can be studied using the method of Lagrange multipliers, with one introduced for every constraint. If the configuration space is defined by $r$ constraints, then the problem is to extremize \begin{equation} H(\mathbf s)+\sum_{i=1}^r\omega_ig_i(\mathbf s) \end{equation} +with respect to $\mathbf s$ and $\pmb\omega=\{\omega_1,\ldots,\omega_r\}$. The corresponding gradient and Hessian for the problem are \begin{align} \nabla H(\mathbf s,\pmb\omega)=\partial H(\mathbf s)+\sum_{i=1}^r\omega_i\partial g_i(\mathbf s) && \operatorname{Hess}H(\mathbf s,\pmb\omega)=\partial\partial H(\mathbf s)+\sum_{i=1}^r\omega_i\partial\partial g_i(\mathbf s) \end{align} - +The number of stationary points in a landscape for a particular realization $H$ is found by integrating over the Kac--Rice measure \begin{equation} d\mu_H(\mathbf s,\pmb\omega)=d\mathbf s\,d\pmb\omega\,\delta\big(\nabla H(\mathbf s,\pmb\omega)\big)\,\delta\big(\mathbf g(\mathbf s)\big)\,\big|\det\operatorname{Hess}H(\mathbf s,\pmb\omega)\big| \end{equation} +with a $\delta$-function of the gradient and the constraints ensuring that we +count valid stationary points, and the Hessian entering in the determinant of +the Jacobian of the argument to the $\delta$-function. It is usually more +interesting to condition the count on interesting properties of the stationary +points, like the energy, \begin{equation} d\mu_H(\mathbf s,\pmb\omega\mid E)=d\mu_H(\mathbf s,\pmb\omega)\,\delta\big(NE-H(\mathbf s)\big) \end{equation} - +In this paper we in particular want to exploit our method to condition +complexity on the marginality of stationary points. We therefore define the +number of marginal points in a particular instantiation $H$ as \begin{equation} \begin{aligned} &\mathcal N_\text{marginal}(E) @@ -261,18 +324,26 @@ where the $\delta$-functions \delta(\mathbf x^T\partial\mathbf g(\mathbf s)) =\prod_{s=1}^r\delta(\mathbf x^T\partial g_i(\mathbf s)) \end{equation} -ensure that the integrals are constrained to the tangent space of the configuration manifold at the point $\mathbf s$. - +ensure that the integrals are constrained to the tangent space of the configuration manifold at the point $\mathbf s$. This likewise allows us to define the complexity of marginal points at energy $E$ as +\begin{equation} + \Sigma_\text{marginal}(E) + =\frac1N\overline{\log\mathcal N_\text{marginal}(E)} +\end{equation} +In practice, this can be computed by introducing replicas to treat the +logarithm ($\log x=\lim_{n\to0}\frac\partial{\partial n}x^n$) and replicating +again to treat each of the normalizations in the numerator. This leads to the expression \begin{equation} \begin{aligned} - &\Sigma_\text{marginal}(E) - =\frac1N\overline{\log\mathcal N_\text{marginal}(E)} \\ - &=\lim_{\beta\to\infty}\lim_{n\to0}\frac\partial{\partial n}\int\prod_{a=1}^n\left[d\mu_H(\mathbf s_a,\pmb\omega_a\mid E)\lim_{m_a\to0} - \left(\prod_{b=1}^{m_a} d\mathbf x_a^b\,\delta(N-(\mathbf x_a^b)^T\mathbf x_a^b)\delta((\mathbf x_a^b)^T\partial\mathbf g(\mathbf s_a))e^{\beta(\mathbf x_a^b)^T\operatorname{Hess}H(\mathbf s_a,\pmb\omega_a)\mathbf x_a^b}\right)\,\delta\big((\mathbf x_a^1)^T\operatorname{Hess}H(\mathbf s_a,\pmb\omega_a)\mathbf x_a^1\big)\right] + \Sigma_\text{marginal}(E) + &=\lim_{\beta\to\infty}\lim_{n\to0}\frac1N\frac\partial{\partial n}\int\prod_{a=1}^n\Bigg[d\mu_H(\mathbf s_a,\pmb\omega_a\mid E)\,\delta\big((\mathbf x_a^1)^T\operatorname{Hess}H(\mathbf s_a,\pmb\omega_a)\mathbf x_a^1\big)\\ + &\qquad\times\lim_{m_a\to0} + \left(\prod_{b=1}^{m_a} d\mathbf x_a^b\,\delta(N-(\mathbf x_a^b)^T\mathbf x_a^b)\delta((\mathbf x_a^b)^T\partial\mathbf g(\mathbf s_a))e^{\beta(\mathbf x_a^b)^T\operatorname{Hess}H(\mathbf s_a,\pmb\omega_a)\mathbf x_a^b}\right)\Bigg] \end{aligned} \end{equation} -\section{Application to the spherical models} +\section{Examples in random landscapes} + +\subsection{Application to the spherical models} \begin{align} C_{ab}=\frac1N\mathbf s_a\cdot\mathbf s_b @@ -321,7 +392,7 @@ We will discuss at the end of this paper when these order parameters can be expe \end{equation} where the maximum over $\omega$ needs to lie at a real value. -\section{Twin spherical model} +\subsection{Twin spherical model} $\Omega=S^{N-1}\times S^{N-1}$ \begin{equation} @@ -369,7 +440,7 @@ $\Omega=S^{N-1}\times S^{N-1}$ +\log\det(Q^{11}Q^{22}-Q^{12}Q^{12}) \end{equation} -\section{Multi-species spherical model} +\subsection{Multi-species spherical model} We consider models whose configuration space consists of the product of $r$ spheres, each with its own dimension $N_s$, or -- cgit v1.2.3-70-g09d2