diff options
Diffstat (limited to 'frsb_kac-rice_letter.tex')
| -rw-r--r-- | frsb_kac-rice_letter.tex | 37 |
1 files changed, 18 insertions, 19 deletions
diff --git a/frsb_kac-rice_letter.tex b/frsb_kac-rice_letter.tex index 1d8785c..c3628f9 100644 --- a/frsb_kac-rice_letter.tex +++ b/frsb_kac-rice_letter.tex @@ -145,7 +145,22 @@ landscape. This behavior of the complexity can be used to explain a rich variety of phenomena in the equilibrium and dynamics of the pure models: the threshold energy $E_\mathrm{th}$ corresponds to the average energy at the dynamic transition temperature, and the asymptotic energy reached by slow aging -dynamics, and to the algorithmic limit $E_\mathrm{alg}$. +dynamics. + +In the pure models, $E_\mathrm{th}$ also corresponds to the \emph{algorithmic +threshold} $E_\mathrm{alg}$, defined by the lowest energy reached by local +algorithms like approximate message passing \cite{ElAlaoui_2020_Algorithmic, +ElAlaoui_2021_Optimization}. In the spherical models, this has been proven to +be +\begin{equation} + E_{\mathrm{alg}}=-\int_0^1dq\,\sqrt{f''(q)} +\end{equation} +For full RSB systems, $E_\mathrm{alg}=E_0$ and the algorithm can reach the +ground state energy. For the pure $p$-spin models, +$E_\mathrm{alg}=E_\mathrm{th}$, where $E_\mathrm{th}$ is the energy at which +marginal minima are the most common stationary points. Something about the +topology of the energy function might be relevant to where this algorithmic +threshold lies. Things become much less clear in even the simplest mixed models. For instance, one mixed model known to have a replica symmetric complexity was shown to @@ -247,24 +262,8 @@ This should correspond to 1RSB in the complexity. We take established to have a 2RSB ground state \cite{Crisanti_2011_Statistical}. With this covariance, the model sees a replica symmetric to 1RSB transition at $\beta_1=1.70615\ldots$ and a 1RSB to 2RSB transition at -$\beta_2=6.02198\ldots$. At these transitions, the average energies in equilibrium are -$\langle E\rangle_1=-0.906391\ldots$ and $\langle E\rangle_2=-1.19553\ldots$, -respectively, and the ground state energy is $E_0=-1.287\,605\,530\ldots$. -Besides these typical equilibrium energies, an energy of special interest for -looking at the landscape topology is the \emph{algorithmic threshold} -$E_\mathrm{alg}$, defined by the lowest energy reached by local algorithms like -approximate message passing \cite{ElAlaoui_2020_Algorithmic, -ElAlaoui_2021_Optimization}. In the spherical models, this has been proven to -be -\begin{equation} - E_{\mathrm{alg}}=-\int_0^1dq\,\sqrt{f''(q)} -\end{equation} -For full RSB systems, $E_\mathrm{alg}=E_0$ and the algorithm can reach the -ground state energy. For the pure $p$-spin models, -$E_\mathrm{alg}=E_\mathrm{th}$, where $E_\mathrm{th}$ is the energy at which -marginal minima are the most common stationary points. Something about the -topology of the energy function might be relevant to where this algorithmic threshold -lies. For the $3+16$ model at hand, $E_\mathrm{alg}=-1.275\,140\,128\ldots$. +$\beta_2=6.02198\ldots$. The typical equilibrium energies at these phase +transitions are listed in Table~\ref{tab:energies}. \begin{table} \begin{tabular}{l|cc} |