# Capacity of the Hebbian-Hopfield network associative memory

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

In [8], Hopfield introduced a _Hebbian_ learning rule based neural network
model and suggested how it can efficiently operate as an associative memory.
Studying random binary patterns, he also uncovered that, if a small fraction
of errors is tolerated in the stored patterns retrieval, the capacity of the
network (maximal number of memorized patterns, $m$) scales linearly with each
pattern’s size, $n$. Moreover, he famously predicted
$\alpha_{c}=\lim_{n\rightarrow\infty}\frac{m}{n}\approx 0.14$. We study this
very same scenario with two most famous pattern’s basins of attraction
notions: _(i)_ The AGS one from [2] which relies on the existence of a local
energy minimum around aimed pattern; and _(ii)_ The NLT one from [16, 11, 12,
13, 33] which relies on the existence of a firm energy barrier around
patterns. Relying on the _fully lifted random duality theory_ (fl RDT) from
[30], we obtain the following explicit closed form capacity characterizations
on the first level of lifting:

$\displaystyle\alpha_{c}^{(AGS,1)}$ $\displaystyle=$
$\displaystyle\left(\max_{\delta\in\left(0,\frac{1}{2}\right)}\frac{1-2\delta}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}\right)^{2}\approx\mathbf{0.137906}$
$\displaystyle\alpha_{c}^{(NLT,1)}$ $\displaystyle=$
$\displaystyle\frac{\mbox{erf}(x)^{2}}{2x^{2}}-1+\mbox{erf}(x)^{2}\approx\mathbf{0.129490},\quad
1-\mbox{erf}(x)^{2}-\frac{2\mbox{erf}(x)e^{-x^{2}}}{\sqrt{\pi}x}+\frac{2e^{-2x^{2}}}{\pi}=0.$

To maximally utilize fl RDT, one also needs to perform substantial numerical
work on higher levels of lifting. After doing so, we obtain
$\alpha_{c}^{(AGS,2)}\approx\mathbf{0.138186}$ and
$\alpha_{c}^{(NLT,2)}\approx\mathbf{0.12979}$, effectively uncovering a
remarkably fast lifting convergence (with the relative improvement no better
than $\sim 0.1\%$ already on the _second_ level of lifting). Moreover, the
obtained AGS characterizations exactly match those obtained based on replica
symmetry methods of [2] and the corresponding symmetry breaking ones of [19].
The NLT ones are substantially higher than the previously best known ones of
[16, 11, 12, 13, 33].

Index Terms: Hopfield network; Hebbian rule; Associative memory capacity;
Random duality.

##  1 Introduction

Following an initial introduction in [17] (where they were viewed as a simpler
form of spin glasses), the present day Hopfield neural networks models became
prevalently popular when their connection to the auto-associative memories was
proposed in [8]. As is by now well known, the main idea revolves around an
iterative pattern searching dynamics that aims to converge to a local optimum
which corresponds to or is in a vicinity of a pattern to be stored/memorized.
Similarly to any other memory concept, two key questions immediately position
themselves as of critical importance: 1) What is the memory capacity (maximum
allowable number of stored patterns) and how does it behave/scale as a
function of other system parameters; and 2) How efficiently a practical
dynamics realization can approach such a capacity. We proceed along these
lines and study the first question in detail. Given that the associative
capacity of the Hopfield nets has been a very popular research subject since
the appearance of the Hopfield’s introductory paper [8], a large body of
relevant work is already available in the existing literature. Before
proceeding with the exposition of our own approach and results, we briefly
survey the already achieved key milestones.

###  1.1 Relevant prior work

Relying on the Hebbian learning principle/rule [7], Hopfiled in [8] proposed a
basic neural associative dynamics model. As the numerical evidence suggested,
the dynamics seemed to have the ability to converge to a pattern of $n$ binary
neurons (state of the network) that either exactly matched one of the
previously stored patterns or was in a close proximity of it. Viewing the
maximum number of the stably stored/retrieved patterns,$m$, as the associative
capacity of the network, Hopfield proceeded further, utilized a simple
Gaussian noise argument, and gave rough capacity estimates. Assuming random
iid binary patterns, his noise based reasoning suggested that the exact
pattern retrieval (convergence of the dynamics to one of the stored patterns),
happens (with probability going to 1 as $n\rightarrow\infty$) provided that
$m\approx\frac{n}{2\log(n)}$. While this result is already very encouraging,
an even better one was awaiting. Namely, Hopfield noted that a small fraction
of errors in retrieved patterns, allows even for a _linear_ capacity scaling.
Moreover, his noise based reasoning gave prediction for the linear
proportionality $\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}\approx
0.14$ with only $0.4\%$ of errors, which happened to be in an solid agrement
with the numerical predictions.

Hopfield’s initial considerations provided a very strong foundation and
generated a large amount of research regarding various aspects of these topics
over the last four decades. We below discuss some of the works that are the
most relevant to our own and that have made a very strong analytical progress.
To properly highlight some of the key analytical aspects of the problem, we
find it convenient to distinguish four separate streams of relevant research
and within each of them focus on the most representative results. As almost
all of the relevant results that we revisit below rely on the same random
binary patterns statistical context already mentioned above, we skip
reemphasizing it. Along the same lines, we adopt the terminology convention of
not explicitly mentioning that the known results stated below hold with
probability going to 1 as $n\rightarrow\infty$ (the very same convention is
later on adopted in the presentation of our own results as well).

_(i)_ _Exact retrieval:_ Following the initial Hopfield’s noise based
considerations, [2] analyzed the memory capacity problem utilizing the
statistical physics replica theory methods. Assuming the replica symmetry, the
very same $m\approx\frac{n}{2\log(n)}$ capacity estimate for retrieving
_exactly_ the stored patterns was obtained. A bit later on, [15] provided the
very first mathematically rigorous results in this direction, which (depending
on the type of the probabilistic statements) matched the [8, 2] sublinear
exact retrieval scaling. The very same $\frac{n}{2\log(n)}$ result obtained in
[2] through the replica symmetry analysis was shown as a rigorous lower bound
in [5]. In a somewhat related line of work, [9] extended the results of [15]
and showed that each of the stored patterns has a nonzero basin of attraction.
[15] also provided a strong numerical evidence that the patterns are unlikely
to be _exactly_ retrievable if the capacity were to scale stronger than
$\sim\frac{n}{\log(n)}$.

_(ii)_ _Approximate retrieval – AGS basin of attraction:_ As already noted in
Hopfield’s considerations, one of the key properties of the underlying
dynamics is its ability to achieve a _linear_ capacity scaling if approximate
retrieval is allowed. A combination of Hopfield rough analytical estimates and
strong algorithmic numerical evidence suggested that the linear
proportionality should be around
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}\approx 0.14$. Relying on
the existence of an energy well around each of the stored patterns (Amit-
Gutfreund-Sompolinsky (AGS) basin of attraction) and the convergence of the
Hopfield dynamics to a local energy (objective) minima of such a well, the
replica symmetry analysis of [2] provided a very precise estimate
$\alpha\approx 0.137906$. Moreover, the discussion of [2] suggested that
further replica symmetry breaking (rsb) corrections should not necessarily be
quantitatively substantial. Such a suggestion was indeed confirmed in [19],
where it was obtained, relying on 1rsb, that $\alpha\approx 0.138186$ and
relying on 2rsb, that $\alpha\approx 0.138187$. As far as the mathematically
rigorous AGS basin related results are concerned, [5] showed that $\alpha\geq
0.113$.

_(iii)_ _Approximate retrieval – NLT basin of attraction:_ A strong rigorous
progress, however, has been made considering a different type of attraction
basin. Namely, in [16, 11, 12, 13] an alternative (to which we refer as the
NLT basin) to the AGS was analyzed. Such alternative assumes that in addition
to the existence of the AGS type of energy well around each pattern, one also
insists that the well’s local energy maximum is not smaller than the one
achieved by the pattern itself. Clearly, such a basin is a bit more
restrictive and clearly its existence implies the existence of the AGS one as
well. That also means that all the capacity results for the NLT basin are
automatically lower bounds for the corresponding AGS related ones. In [16], it
was shown that $\alpha\geq 0.056$ for the NLT basin. This results was then
improved to $\alpha\geq 0.071$ in [11, 12] and to $\alpha\geq 0.08$ in [33].

_(iv)_ _Non-Hebbian learning rules:_ It is also interesting to note that the
capacity can grow even beyond the linear one if one is willing to deviate from
the standard Hebbian learning principle. If, instead of the Hebbian rule which
assumes the quadratic (polynomial of degree 2) objective, one relies on an
objective based on a general overlap power (polynomial of degree) $p$, the
capacity of the _exact_ retrieval scales as $m\sim\frac{n^{p-1}}{\log(n)}$ and
the capacity of the _approximate_ retrieval scales as $m\sim n^{p-1}$ [6, 1,
10] (clearly, for $p=2$ these estimates match the ones discussed above). If,
on the other hand, one relies on the exponential interactions, the capacity
can actually grow even exponentially [4, 18, 34, 14]. While these results
allow for a substantial increase in the analytically/algorithmically
achievable associative capacity, the connection of the underlying learning
principles to the neurological behavior is not necessarily as clear as in the
Hebbian rule based models.

###  1.2 Our contributions

After recognizing the connection between the Hopfiled associative memory
models and _bilinearly indexed_ (bli) random processes, we start by utilizing
a strong progress achieved recently in studying bli’s in [26, 29]. We make a
particular use of the _fully lifted_ random duality theory (fl RDT)
established in [30] that first allows us create a powerful generic framework
for the analysis of the Hopfield dynamics and then to also obtain associated
memory capacity characterizations. For the utilization of the fl RDT to become
practically relevant, a substantial amount of the underlying numerical work
needs to be performed as well. Performing such a work more often than not
requires a rather strong effort. Relying on a remarkable set of closed form
explicit analytical relations among the key lifting parameters turns out to be
extremely helpful in that regard. In addition to being helpful with the
numerical work, these relations also provide a direct insight into a beautiful
structuring of the parametric interconnections. The most important of all,
they eventually allow us to uncover that the capacity characterizations,
obtained already on the _second_ level of the _full_ lifting (2-sfl RDT),
exhibit a remarkably rapid convergence with relative improvements of the order
of $\sim 0.1\%$.

##  2 Mathematical setup

We assume the standard Hopfield model with $m$ binary patterns to be
memorized. The $i$-th pattern will be denoted by $\bar{{\bf
g}}^{(i)}\in{\mathbb{S}}_{H}^{n},i=1,2,\dots,m,$ where ${\mathbb{S}}_{H}^{n}$
is the $n$-dimensional Hamming sphere of radius 1, i.e.
${\mathbb{S}}_{H}^{n}\triangleq\left\\{-\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}\right\\}^{n}$.
Speaking in a high-dimensional geometry terminology, ${\mathbb{S}}_{H}^{n}$ is
the set of all corners of the unit $n$-dimensional hypercube. Also, we denote
by $\bar{{\bf g}}_{j}^{(i)},j=1,2,\dots,n,$ the $j$-th component of $\bar{{\bf
g}}^{(i)}$ and assume the typical statistical context where $\bar{{\bf
g}}_{j}^{(i)}$ are iid $\pm 1$ Bernoulli random variables. For the writing
convenience, we also find it convenient to set

$\displaystyle{\mathcal{G}}\triangleq\sum_{i=1}^{m}\bar{{\bf
g}}^{(i)}\left(\bar{{\bf g}}^{(i)}\right)^{T}.$ (1)

The following is then the associated Hopfield sequential retrieval dynamics

$\displaystyle\bar{{\bf x}}_{i}(t+1)=\mbox{sign}\left(\sum_{j=1,j\neq
i}^{n}{\mathcal{G}}_{i,j}\bar{{\bf x}}_{j}(t)\right),$ (2)

where (here and throughout the paper) ${\mathcal{G}}_{i,j}$ stands for the
$ij$-th component of ${\mathcal{G}}$ and ${\mathcal{G}}_{i,:}$ is the $i$-th
row of ${\mathcal{G}}$. If one defines the energy objective as

$\displaystyle{\cal H}({\bf x})\triangleq-{\bf x}^{T}{\mathcal{G}}{\bf x},$
(3)

the above dynamics, (2), converges to its a local minimum. Let $\bar{{\bf x}}$
be the converging point of (2), i.e. let

$\displaystyle\bar{{\bf x}}=\lim_{t\rightarrow\infty}\bar{{\bf x}}(t),$ (4)

and let the corresponding achieved value of the local energy minimum be

$\displaystyle{\cal H}(\bar{{\bf x}})=-\bar{{\bf x}}^{T}{\mathcal{G}}\bar{{\bf
x}}.$ (5)

One then also has

$\displaystyle{\cal H}(\bar{{\bf x}})\leq\min_{\|{\bf x}-\bar{{\bf
x}}\|_{2}=\frac{2}{\sqrt{n}},{\bf x}\in S_{H}^{n}}-{\bf
x}^{T}{\mathcal{G}}{\bf x}.$ (6)

The main idea behind the energy objective in (3) is that, provided that the
patterns $\bar{{\bf g}}$ are “sufficiently orthogonal”, the dynamics might
actually converge so that it either exactly or approximately matches one of
the stored patterns. In other words, it might happen that $\bar{{\bf
x}}^{T}\bar{{\bf g}}^{(i)}=1$ or $\bar{{\bf x}}^{T}\bar{{\bf
g}}^{(i)}=1-2\delta$, where $\delta$ is a small real number. In fact, as the
noise arguments of [8] and the replica symmetry ones of [2] suggested, and the
rigorous ones of [15, 5] confirmed, one indeed has $\bar{{\bf x}}^{T}\bar{{\bf
g}}^{(i)}=1$ provided that $m\leq\frac{n}{2\log(n)}$. On the other hand, a bit
looser scenario $\bar{{\bf x}}^{T}\bar{{\bf g}}^{(i)}=1-2\delta$ allows even
for (a higher) $m$ that grows aa a linear function of $n$. To be able to
precisely state this, we distinguish two different sub-scenarios depending of
the choice of the basin of attraction.

###  2.1 AGS basin of attraction

In [2], the Hopfield dynamics convergence to a local minimum that
approximately matches one of the patterns to be retrieved and the
corresponding associative capacity are formulated relying on the existence of
appropriately defined energy wells. Taking ${\bf g}^{(1)}$ as the targeted
pattern of retrieval, the capacity (in AGS sense) is defined as the largest
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}$ such that for some
(small) $\delta>0$

$\displaystyle\hat{{\bf x}}^{(AGS)}(\delta)\triangleq\mbox{arg min}_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}-{\bf
x}^{T}{\mathcal{G}}{\bf x}.$ (7)

and

$\displaystyle{\cal H}(\bar{{\bf x}})\leq\min\left({\cal H}(\bar{{\bf
g}}^{(1)}),{\cal H}(\hat{{\bf x}}^{(AGS)}(\delta))\right).$ (8)

As mentioned earlier, the replica symmetry arguments of [2] gave
$\alpha\approx 0.1379056$ whereas the corresponding 1rsb and 2rsb ones gave
$\alpha\approx 0.138186$ and $\alpha\approx 0.138187$, respectively. On the
other hand, the rigorous lower bound of [5] gave a significantly lower
capacity estimate $\alpha\geq 0.113$. Given that the numerical simulations
suggest that indeed $\alpha\approx 0.14$ this leaves a substantial rigorous
theory – replica predictions gap to bridge.

###  2.2 NLT basin of attraction

A slightly different basin of attraction was considered in [16, 11, 12, 13,
33]. One again relies on the existence of the energy wells but utilizes them
in an analytically possibly more convenient way. Taking again, without loss of
generality, ${\bf g}^{(1)}$ as the targeted pattern, the capacity (in NLT
sense) is defined as the largest
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}$ such that for some
(small) $\delta>0$

$\displaystyle\hat{{\bf x}}^{(NLT)}(\delta)\triangleq\mbox{arg min}_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}-{\bf
x}^{T}{\mathcal{G}}{\bf x}.$ (9)

and

$\displaystyle{\cal H}(\bar{{\bf x}})\leq\min\left({\cal H}(\bar{{\bf
g}}^{(1)}),{\cal H}(\hat{{\bf
x}}^{(NLT)}(\delta))\right)\qquad\mbox{and}\qquad{\cal H}(\bar{{\bf
g}}^{(1)})<{\cal H}(\hat{{\bf x}}^{(NLT)}(\delta)).$ (10)

While in writing the difference between this basin of attraction notion and
the one from (7) and (8) seems rather marginal, in analytical terms it is
actually significant. It allows one to switch the focus on the second portion
of the condition in (10) which is typically analytically easier to handle.
Consequently the known rigorous results are a bit more diverse as well. As
stated earlier, it was first shown in [16] that $\alpha\geq 0.056$. This was
then improved to $\alpha\geq 0.071$ in [11, 12] and to $\alpha\geq 0.08$ in
[33]. It is also not that difficult to see that (9) and (10) are more
restrictive than (and certainly imply) (7) and (8). This then also means that
the capacity estimates obtained based on the NLT basin of attraction are for
sure lower bounds on the corresponding ones obtained relying on the AGS basin.

No matter which of the above attractions basins one adopts, it is clear that
the optimization problems from (7) or (9) play a critical role in determining
the corresponding associative memory capacity. In what follows, we therefore
focus precisely on these optimization programs.

###  2.3 Statistical associative memory capacity

We first set

$\displaystyle\xi_{1}(\delta)\triangleq\lim_{n\rightarrow\infty}\frac{1}{n}\min_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}-{\bf
x}^{T}{\mathcal{G}}{\bf x},$ (11)

and then, after noting that for ${\bf x}\in S_{H}^{n}$, $\|{\bf x}-\bar{{\bf
g}}^{(1)}\|_{2}^{2}=4\delta$ implies ${\bf x}^{T}\bar{{\bf
g}}^{(1)}=1-2\delta$, write

$\displaystyle\xi_{1}(\delta)=-\left(1-2\delta\right)^{2}+\lim_{n\rightarrow\infty}\frac{1}{n}\min_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in
S_{H}^{n}}-\sum_{i=2}^{m}{\bf x}^{T}{\bf g}^{(i)}\left({\bf
g}^{(i)}\right)^{T}{\bf x}.$ (12)

After setting

$\displaystyle G\triangleq\begin{bmatrix}\left({\bf g}^{(2)}\right)^{T}\\\
\left({\bf g}^{(3)}\right)^{T}\\\ \vdots\\\ \left({\bf
g}^{(m)}\right)^{T}\end{bmatrix},$ (13)

one can rewrite (12) as

$\displaystyle\xi_{1}(\delta)$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}+\lim_{n\rightarrow\infty}\frac{1}{n}\min_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}-{\bf
x}^{T}G^{T}G{\bf x}$ (14) $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}+\lim_{n\rightarrow\infty}\frac{1}{n}\min_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}-\|G{\bf
x}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\lim_{n\rightarrow\infty}\frac{1}{n}\max_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}\|G{\bf
x}\|_{2}^{2}$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\xi(\delta)^{2},$

where

$\displaystyle\xi(\delta)\triangleq\lim_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\max_{\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}}\|G{\bf
x}\|_{2}.$ (15)

The problem from (15) can be rewritten in the following way

$\displaystyle\xi(\delta)\triangleq\lim_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\max_{{\bf
x}\in{\mathcal{X}}(\delta)}\max_{{\bf y}\in{\mathbb{S}}^{m}}{\bf y}^{T}G{\bf
x},$ (16)

where ${\mathbb{S}}^{m}$ is the unit $m$-dimensional Euclidean sphere, and for
$\delta\in[0,1]$

$\displaystyle{\mathcal{X}}(\delta)\triangleq\left\\{{\bf x}|\quad\|{\bf
x}-\bar{{\bf g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}\right\\}.$ (17)

Even though we assumed at the beginning that the patterns are comprised of iid
binary random variables, everything that we have written above holds
deterministically, i.e. for any $G$ and ${\bf g}^{(1)}$. To make the
exposition neater, in what follows, we view $G$ as being comprised of iid
standard normals (concentrations and the Lindeberg variant of the central
limit theorem allow for such a switch without a substantial change in the
final results; while there are many ways as to how the Lindeberg principle can
be implemented, we find as particularly elegant and quick the one from [3]).
Moreover, to further facilitate the writing and exposition, we, without loss
of generality, assume that ${\bf g}^{(1)}=\frac{{\bf 1}}{\sqrt{n}}$, i.e., we
assume that ${\bf g}^{(1)}$ is an $n$-dimensional column vector of all ones
scaled so that it has a unit Euclidean norm.

After recognizing that $\lim_{n\rightarrow\infty}\frac{1}{n}{\cal
H}\left(\bar{{\bf g}}^{(1)}\right)=\xi_{1}(0)$, we can formally define the AGS
and the NLT basins of attractions associative memory _capacity_ in a large
dimensional statistical context in the following way

$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{m}{n}$
$\displaystyle\alpha_{c}^{(AGS)}$ $\displaystyle\triangleq$
$\displaystyle\max\\{\alpha|\hskip
5.78172pt\exists\delta>\delta_{1}>0,\lim_{n\rightarrow\infty}{\mathbb{P}}_{G}\left(\xi_{1}(\delta_{1})\leq\min(\xi_{1}(0),\xi_{1}(\delta))\right)\longrightarrow
1\\}$ $\displaystyle\alpha_{c}^{(NLT)}$ $\displaystyle\triangleq$
$\displaystyle\max\\{\alpha|\hskip
5.78172pt\exists\delta>\delta_{1}>0,\lim_{n\rightarrow\infty}{\mathbb{P}}_{G}\left(\xi_{1}(\delta_{1})\leq\xi_{1}(0)<\xi_{1}(\delta)\right)\longrightarrow
1\\}.$ (18)

We adopt the convention that the subscripts next to ${\mathbb{P}}$ and
${\mathbb{E}}$, whenever appear throughout the paper, denote the randomness
with respect to which the statistical evaluation is taken. On the other hand,
the subscripts are left unspecified when it is clear from the context what the
underlying randomness is.

###  2.4 Free energy correspondence

It is rather clear from the above presentation (and particularly so from (18))
that studying $\xi_{1}(\delta)$ is of critical importance for determining the
capacity. Moreover, from (14), one can actually observe that the most relevant
object for studying is in fact $\xi(\delta)$. In that regard, the
representation from (16) turns out to be quite relevant. Namely, as recognized
on numerous occasions when studying various random feasibility problems
(including many perceptron instances) [20, 25, 24, 21, 27], studying the
representation from (16), in a way, directly corresponds to studying
statistical physics objects called _free energies_. For the completeness, we
below sketch the most important contours of such a correspondence and refer
for a more detailed discussion to [20, 25, 24, 21, 27].

Free energies are well known and almost unavoidable objects in many
statistical physics considerations. To introduce their mathematically
representation of interest here, we start with the following, so-called,
_bilinear Hamiltonian_

${\cal H}_{sq}(G)={\bf y}^{T}G{\bf x},$ (19)

and its corresponding partition function

$Z_{sq}(\beta,G)=\sum_{{\bf x}\in{\mathcal{X}}}\sum_{{\bf
y}\in{\mathcal{Y}}}e^{\beta{\cal H}_{sq}(G)}.$ (20)

For the time being ${\mathcal{X}}$ and ${\mathcal{Y}}$ are taken as general
sets. However, fairly soon, specializations,
${\mathcal{X}}={\mathcal{X}}(\delta)$ and ${\mathcal{Y}}={\mathbb{S}}^{m}$,
necessary for our considerations here will take place as well. One then
further has for the corresponding thermodynamic limit of the average free
energy

$\displaystyle f_{sq}(\beta)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\log{(Z_{sq}(\beta,G)})}{\beta\sqrt{n}}=\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\log\left(\sum_{{\bf
x}\in{\mathcal{X}}}\sum_{{\bf y}\in{\mathcal{Y}}}e^{\beta{\cal
H}_{sq}(G)}\right)}{\beta\sqrt{n}}$ (21) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\log\left(\sum_{{\bf
x}\in{\mathcal{X}}}\sum_{{\bf y}\in{\mathcal{Y}}}e^{\beta{\bf y}^{T}G{\bf
x})}\right)}{\beta\sqrt{n}}.$

The ground state energy is a special case obtained by considering the so-
called “zero-temperature” ($T\rightarrow 0$ or
$\beta=\frac{1}{T}\rightarrow\infty$) regime

$\displaystyle
f_{sq}(\infty)\triangleq\lim_{\beta\rightarrow\infty}f_{sq}(\beta)$
$\displaystyle=$
$\displaystyle\lim_{\beta,n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\log{(Z_{sq}(\beta,G)})}{\beta\sqrt{n}}=\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\max_{{\bf
x}\in{\mathcal{X}}}\max_{{\bf y}\in{\mathcal{Y}}}{\bf y}^{T}G{\bf
x}}{\sqrt{n}}.$ (22)

It is not that difficult to see that (22) is directly related to (16). At the
same time, this also implies that $f_{sq}(\infty)$ is very tightly connected
to $\xi_{1}(\delta)$, which then means that studying and understanding
$f_{sq}(\infty)$ is of critical importance in characterizing the statistical
capacity from (18). This is basically exactly what will happen in the sections
that follow below. Before proceeding further, we find it useful to emphasize
that studying $f_{sq}(\infty)$ directly is usually not very easy. We therefore
rely on studying first $f_{sq}(\beta)$ for a general $\beta$ and then on
specializing the obtained general results to the ground state,
$\beta\rightarrow\infty$, regime. To ease the exposition, we, on occasion,
neglect some analytical details which paly no significant role in the ultimate
ground state considerations.

##  3 Connection to bli random processes and sfl RDT

A key observation that is of fundamental importance for everything that
follows is that the free energy from (21),

$\displaystyle f_{sq}(\beta)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\log\left(\sum_{{\bf
x}\in{\mathcal{X}}}\sum_{{\bf y}\in{\mathcal{Y}}}e^{\beta{\bf y}^{T}G{\bf
x})}\right)}{\beta\sqrt{n}},$ (23)

can be viewed as a function of _bilinearly indexed_ (bli) random process ${\bf
y}^{T}G{\bf x}$. Such a recognition then allows us to further connect
$f_{sq}(\beta)$ and the bli related results of [26, 29, 30]. To do so, we
closely follow the machinery of [31, 27] and start with a collection of
necessary technical definitions. For $r\in{\mathbb{N}}$,
$k\in\\{1,2,\dots,r+1\\}$, sets ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$ and
${\mathcal{Y}}\subseteq{\mathbb{R}}^{m}$, function
$f_{S}(\cdot):{\mathbb{R}}^{n}\rightarrow R$, real scalars $x$, $y$, and $s$
such that $x>0$, $y>0$, and $s^{2}=1$, vectors ${\bf p}=[{\bf p}_{0},{\bf
p}_{1},\dots,{\bf p}_{r+1}]$, ${\bf q}=[{\bf q}_{0},{\bf q}_{1},\dots,{\bf
q}_{r+1}]$, and ${\bf c}=[{\bf c}_{0},{\bf c}_{1},\dots,{\bf c}_{r+1}]$ such
that

$\displaystyle 1={\bf p}_{0}\geq{\bf p}_{1}\geq{\bf p}_{2}\geq\dots\geq{\bf
p}_{r}\geq{\bf p}_{r+1}$ $\displaystyle=$ $\displaystyle 0$ $\displaystyle
1={\bf q}_{0}\geq{\bf q}_{1}\geq{\bf q}_{2}\geq\dots\geq{\bf q}_{r}\geq{\bf
q}_{r+1}$ $\displaystyle=$ $\displaystyle 0,$ (24)

${\bf c}_{0}=1$, ${\bf c}_{r+1}=0$, and
${\mathcal{U}}_{k}\triangleq[u^{(4,k)},{\bf u}^{(2,k)},{\bf h}^{(k)}]$ such
that the elements of $u^{(4,k)}\in{\mathbb{R}}$, ${\bf
u}^{(2,k)}\in{\mathbb{R}}^{m}$, and ${\bf h}^{(k)}\in{\mathbb{R}}^{n}$ are iid
standard normals, we first set

$\displaystyle\psi_{S,\infty}(f_{S},{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
c},x,y,s)={\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{n{\bf
c}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left(Z_{S,\infty}\right)^{{\bf
c}_{2}}\right)\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)\right)^{\frac{{\bf c}_{4}}{{\bf
c}_{3}}}\dots\right)^{\frac{{\bf c}_{r}}{{\bf c}_{r-1}}}\right),$

where

$\displaystyle Z_{S,\infty}$ $\displaystyle\triangleq$ $\displaystyle
e^{D_{0,S,\infty}}$ $\displaystyle D_{0,S,\infty}$ $\displaystyle\triangleq$
$\displaystyle\max_{{\bf x}\in{\mathcal{X}},\|{\bf x}\|_{2}=x}s\max_{{\bf
y}\in{\mathcal{Y}},\|{\bf
y}\|_{2}=y}\left(\sqrt{n}f_{S}+\sqrt{n}y\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}+\sqrt{n}x{\bf y}^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right)\right)$ $\displaystyle b_{k}$ $\displaystyle\triangleq$
$\displaystyle b_{k}({\bf p},{\bf q})=\sqrt{{\bf p}_{k-1}-{\bf p}_{k}}$
$\displaystyle c_{k}$ $\displaystyle\triangleq$ $\displaystyle c_{k}({\bf
p},{\bf q})=\sqrt{{\bf q}_{k-1}-{\bf q}_{k}}.$ (26)

With all the above definitions set, we can proceed by recalling on the
following theorem – clearly, one of most fundamental components of sfl RDT.

######  Theorem 1.

[30] Consider large $n$ linear regime with
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}$, remaining constant as
$n$ grows. Let ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$ and
${\mathcal{Y}}\subseteq{\mathbb{R}}^{m}$ be two given sets and let the
elements of $G\in{\mathbb{R}}^{m\times n}$ be i.i.d. standard normals. Assume
the complete sfl RDT frame from [26] and consider a given function $f({\bf
y}):R^{m}\rightarrow R$. Set

$\displaystyle\psi_{rp}$ $\displaystyle\triangleq-\max_{{\bf
x}\in{\mathcal{X}}}s\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf y})+{\bf
y}^{T}G{\bf
x}\right)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{random
primal}})}$ $\displaystyle\psi_{rd}({\bf p},{\bf q},{\bf c},x,y,s)$
$\displaystyle\triangleq\frac{x^{2}y^{2}}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(f({\bf y}),{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
c},x,y,s)\hskip
2.168pt\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{fl
random dual}})}.$

Let $\hat{{\bf p}_{0}}\rightarrow 1$, $\hat{{\bf q}_{0}}\rightarrow 1$, and
$\hat{{\bf c}_{0}}\rightarrow 1$, $\hat{{\bf p}}_{r+1}=\hat{{\bf
q}}_{r+1}=\hat{{\bf c}}_{r+1}=0$, and let the non-fixed parts of $\hat{{\bf
p}}\triangleq\hat{{\bf p}}(x,y)$, $\hat{{\bf q}}\triangleq\hat{{\bf q}}(x,y)$,
and $\hat{{\bf c}}\triangleq\hat{{\bf c}}(x,y)$ be the solutions of the
following system

$\displaystyle\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y,s)}{d{\bf
p}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y,s)}{d{\bf
q}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},x,y,s)}{d{\bf c}}=0.$ (28)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\min_{x>0}\max_{y>0}\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}}(x,y),\hat{{\bf q}}(x,y),\hat{{\bf
c}}(x,y),x,y,s)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
sfl random duality}})},$

where $\psi_{S,\infty}(\cdot)$ is as in (3)-(3).

###### Proof.

Follows from the corresponding one proven in [30] in exactly he same way as
Theorem 1 in [28]. ∎

The above theorem holds generically for any given sets ${\mathcal{X}}$ and
${\mathcal{Y}}$. The following corollary makes it fully operational for
studying the statistical associative memory capacity which is of our interest
here.

######  Corollary 1.

Assume the setup of Theorem 1 with $\delta\in[0,1]$ and
${\mathcal{X}}={\mathcal{X}}(\delta)$ and ${\mathcal{Y}}={\mathbb{S}}^{m}$
where ${\mathcal{X}}(\delta)$ is as in (17) and ${\mathbb{S}}^{m}$ is the unit
$m$-dimensional Euclidean sphere. Set

$\displaystyle\psi_{rp}$ $\displaystyle\triangleq-\max_{{\bf
x}\in{\mathcal{X}}}s\max_{{\bf y}\in{\mathcal{Y}}}\left({\bf y}^{T}G{\bf
x}\right)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{random
primal}})}$ $\displaystyle\psi_{rd}({\bf p},{\bf q},{\bf c},1,1,s)$
$\displaystyle\triangleq\frac{1}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(0,{\cal X},{\cal Y},{\bf p},{\bf q},{\bf
c},1,1,s)\quad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{fl
random dual}})}.$

Let the non-fixed parts of $\hat{{\bf p}}$, $\hat{{\bf q}}$, and $\hat{{\bf
c}}$ be the solutions of the following system

$\displaystyle\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},1,1,s)}{d{\bf
p}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},1,1,s)}{d{\bf
q}}=0,\quad\frac{d\psi_{rd}({\bf p},{\bf q},{\bf c},1,1,s)}{d{\bf c}}=0.$ (31)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}$
$\displaystyle=$ $\displaystyle\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},1,1,s)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
sfl random duality}})},$

where $\psi_{S,\infty}(\cdot)$ is as in (3)-(3).

###### Proof.

Follows trivially as an immediate consequence of Theorem 1, after choosing
$f({\bf y})=0$ and recognizing that the specialized sets
${\mathcal{X}}={\mathcal{X}}(\delta)$ and ${\mathcal{Y}}={\mathbb{S}}^{m}$ are
such that each of their elements has unit Euclidean norm. ∎

As noted in [30, 31], trivial random primal concentrations enable various
probabilistic variants of (1) and (1) as well. We skip stating such
trivialities though.

##  4 Practical realization

As usual, to ensure that Theorem 1 and Corollary 1 are practically relevant,
each of the underlying quantities needs to be evaluated. While trying to do
so, two obstacles might appear as potentially unsurpassable: (i) A priori, it
is not clear what the correct value for $r$ should be; and (ii) Neither of the
sets ${\mathcal{X}}$ and ${\mathcal{Y}}$ has a component-wise structural
characterization which guarantees that the decoupling over both ${\bf x}$ and
${\bf y}$ is straightforward (if doable at all). It turns out, however, that
each of these potential obstacles can be successfully surpassed.

Taking the sets specializations, ${\mathcal{X}}={\mathcal{X}}(\delta)$ and
${\mathcal{Y}}={\mathbb{S}}^{m}$, and relying on results of Corollary 1, we
start by noting that the key object of practical relevance is the following
_random dual_

$\displaystyle\psi_{rd}({\bf p},{\bf q},{\bf c},1,1,s)$
$\displaystyle\triangleq\frac{1}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(0,{\mathcal{X}},{\mathcal{Y}},{\bf p},{\bf q},{\bf
c},1,1,s)$
$\displaystyle\triangleq\frac{1}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf
p}_{k-1}{\bf q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\psi_{S,\infty}(0,{\mathcal{X}}(\delta),{\mathbb{S}}^{m},{\bf p},{\bf
q},{\bf c},1,1,s)$
$\displaystyle=\frac{1}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf p}_{k-1}{\bf
q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-\frac{1}{n}\varphi(D^{(per)}(s),{\bf
c})-\frac{1}{n}\varphi(D^{(sph)}(s),{\bf c}),$

where, based on (3)-(3),

$\displaystyle\varphi(D,{\bf c})$ $\displaystyle\triangleq$
$\displaystyle{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{{\bf
c}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left(e^{D}\right)^{{\bf
c}_{2}}\right)\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)\right)^{\frac{{\bf c}_{4}}{{\bf
c}_{3}}}\dots\right)^{\frac{{\bf c}_{r}}{{\bf c}_{r-1}}}\right),$

and

$\displaystyle D^{(per)}(s)$ $\displaystyle=$ $\displaystyle\max_{{\bf
x}\in{\mathcal{X}}(\delta)}\left(s\sqrt{n}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}\right)$ $\displaystyle D^{(sph)}(s)$
$\displaystyle\triangleq$ $\displaystyle s\max_{{\bf
y}\in{\mathbb{S}}^{m}}\left(\sqrt{n}{\bf y}^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right)\right).$ (35)

_(i) Handling $D^{(per)}(1)$:_ One first easily finds

$\displaystyle D^{(per)}(1)$ $\displaystyle=$ $\displaystyle\max_{{\bf
x}\in{\mathcal{X}}(\delta)}\left(\sqrt{n}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}\right)=\sqrt{n}\max_{{\bf
x}\in{\mathcal{X}}(\delta)}\left(\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}{\bf x}\right).$ (36)

Relying on (17), one then also observes that ${\mathcal{X}}$ can be
parameterized in the following way as well

$\displaystyle{\mathcal{X}}(\delta)$ $\displaystyle\triangleq$
$\displaystyle\left\\{{\bf x}|\quad\|{\bf x}-\bar{{\bf
g}}^{(1)}\|_{2}^{2}=4\delta,{\bf x}\in S_{H}^{n}\right\\}$ (37)
$\displaystyle=$ $\displaystyle\left\\{{\bf x}|\quad{\bf x}=\frac{{\bf
1}}{\sqrt{n}}-{\bf z},{\bf
z}\in\left\\{0,\frac{2}{\sqrt{n}}\right\\}^{n},\sum_{i=1}^{n}{\bf
z}_{i}=2\delta\sqrt{n}\right\\},$

where we recall that, as mentioned earlier, due to distributional symmetry,
one can, without loss of generality, assume $\bar{{\bf g}}^{(1)}=\frac{{\bf
1}}{\sqrt{n}}$. A combination of (36) and (37) gives

$\displaystyle D^{(per)}(1)$ $\displaystyle=$
$\displaystyle-\sqrt{n}\min_{{\bf z}}\left(-\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}\left(\frac{{\bf 1}}{\sqrt{n}}-{\bf z}\right)\right)$
subject to $\displaystyle{\bf
z}\in\left\\{0,\frac{2}{\sqrt{n}}\right\\}^{n},\sum_{i=1}^{n}{\bf
z}_{i}=2\delta\sqrt{n}.$ (38)

Writing the Lagrangian and utilizing the strong Lagrangian duality, we then
obtain

$\displaystyle D^{(per)}(1)$ $\displaystyle=$
$\displaystyle-\sqrt{n}\min_{{\bf
z}\in\left\\{0,\frac{2}{\sqrt{n}}\right\\}^{n}}\max_{\nu}\left(-\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}\left(\frac{{\bf 1}}{\sqrt{n}}-{\bf
z}\right)-\nu\sum_{i=1}^{n}{\bf z}_{i}+2\nu\delta\sqrt{n}\right)$ (39)
$\displaystyle=$ $\displaystyle-\sqrt{n}\max_{\nu}\min_{{\bf
z}\in\left\\{0,\frac{2}{\sqrt{n}}\right\\}^{n}}\left(-\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}\right)^{T}\left(\frac{{\bf 1}}{\sqrt{n}}-{\bf
z}\right)-\nu\sum_{i=1}^{n}{\bf z}_{i}+2\nu\delta\sqrt{n}\right).$

After the optimization over ${\bf z}$, we then also have

$\displaystyle D^{(per)}(1)$ $\displaystyle=$
$\displaystyle-\max_{\nu}\left(2\nu\delta
n+2\min\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}-\nu,0\right)-\left(\sum_{k=2}^{r+1}c_{k}{\bf h}^{(k)}\right)^{T}{\bf
1}\right)$ (40) $\displaystyle=$ $\displaystyle\min_{\nu}\left(-2\nu\delta
n-2\min\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k)}-\nu,0\right)+\left(\sum_{k=2}^{r+1}c_{k}{\bf h}^{(k)}\right)^{T}{\bf
1}\right)$ $\displaystyle=$ $\displaystyle\min_{\nu}\left(-2\nu\delta
n+\sum_{i=1}^{n}D^{(per)}_{i}(c_{k})\right),$

where

$\displaystyle D^{(per)}_{i}(c_{k})=-2\min\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}_{i}^{(k)}-\nu,0\right)+\sum_{k=2}^{r+1}c_{k}{\bf h}_{i}^{(k)}.$ (41)

_(ii) Handling $D^{(sph)}(1)$:_ We start by observing

$\displaystyle D^{(sph)}(1)$ $\displaystyle\triangleq$
$\displaystyle\sqrt{n}\max_{{\bf y}\in{\mathbb{S}}^{m}}\left({\bf
y}^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right)\right)=\sqrt{n}\left\|\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right\|_{2}.$ (42)

The _square root trick_ introduced on numerous occasions in [23, 22, 25, 24],
turns out as particularly useful in handling (42). To that end, we write

$\displaystyle D^{(sph)}(1)$
$\displaystyle=\sqrt{n}\left\|\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right\|_{2}=\sqrt{n}\min_{\gamma}\left(\frac{\left\|\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k)}\right\|_{2}^{2}}{4\gamma}+\gamma\right)$
$\displaystyle=\sqrt{n}\min_{\gamma}\left(\frac{\sum_{i=1}^{m}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k)}\right)^{2}}{4\gamma}+\gamma\right).$ (43)

We then introduce scaling $\gamma=\gamma_{sq}\sqrt{n}$ and rewrite (4) as

$\displaystyle D^{(sph)}(1)$ $\displaystyle=$
$\displaystyle\sqrt{n}\min_{\gamma_{sq}}\left(\frac{\sum_{i=1}^{m}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k)}\right)^{2}}{4\gamma_{sq}\sqrt{n}}+\gamma_{sq}\sqrt{n}\right)$
$\displaystyle=$
$\displaystyle\min_{\gamma_{sq}}\left(\frac{\sum_{i=1}^{m}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k)}\right)^{2}}{4\gamma_{sq}}+\gamma_{sq}n\right)$ $\displaystyle=$
$\displaystyle\min_{\gamma_{sq}}\left(\sum_{i=1}^{m}D_{i}^{(sph)}(b_{k})+\gamma_{sq}n\right),$

with

$\displaystyle D_{i}^{(sph)}(b_{k})=\frac{\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k)}\right)^{2}}{4\gamma_{sq}}.$ (45)

Recalling on (16), we then have

$\displaystyle\xi(\delta)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\max_{{\bf
x}\in{\mathcal{X}}(\delta)}\max_{{\bf y}\in{\mathbb{S}}^{m}}{\bf y}^{T}G{\bf
x}}{\sqrt{n}}=\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G}\psi_{rp}}{\sqrt{n}}=\lim_{n\rightarrow\infty}\psi_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf c}},1,1,1).$ (46)

Keeping in mind (4)-(45), we can then formulate the following theorem that
ultimately enables fitting the associative memorization within the sfl RDT
machinery.

######  Theorem 2.

Assume the setup of Theorem 1 and consider large $n$ linear regime with
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}$. Set

$\displaystyle\varphi(D,{\bf c})$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{G,{\mathcal{U}}_{r+1}}\frac{1}{{\bf
c}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}}\left(\left(e^{D}\right)^{{\bf
c}_{2}}\right)\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)\right)^{\frac{{\bf c}_{4}}{{\bf
c}_{3}}}\dots\right)^{\frac{{\bf c}_{r}}{{\bf c}_{r-1}}}\right),$

and

$\displaystyle\bar{\psi}_{rd}({\bf p},{\bf q},{\bf c},\gamma_{sq},\nu,\delta)$
$\displaystyle\triangleq$
$\displaystyle-\frac{1}{2}\sum_{k=2}^{r+1}\Bigg{(}\Bigg{.}{\bf p}_{k-1}{\bf
q}_{k-1}-{\bf p}_{k}{\bf q}_{k}\Bigg{.}\Bigg{)}{\bf
c}_{k}-2\nu\delta+\varphi(D_{1}^{(per)}(1),{\bf
c})+\gamma_{sq}+\alpha\varphi(D_{1}^{(sph)}(1),{\bf c}),$

where $D_{1}^{(per)}(1)$ and $D_{1}^{(sph)}(1)$ are as in (41) and (45),
respectively. Let the “fixed” parts of $\hat{{\bf p}}$, $\hat{{\bf q}}$, and
$\hat{{\bf c}}$ satisfy $\hat{{\bf p}}_{1}\rightarrow 1$, $\hat{{\bf
q}}_{1}\rightarrow 1$, $\hat{{\bf c}}_{1}\rightarrow 1$, $\hat{{\bf
p}}_{r+1}=\hat{{\bf q}}_{r+1}=\hat{{\bf c}}_{r+1}=0$, and let the “non-fixed”
parts of $\hat{{\bf p}}_{k}$, $\hat{{\bf q}}_{k}$, and $\hat{{\bf c}}_{k}$
($k\in\\{2,3,\dots,r\\}$) and $\hat{\gamma}_{sq}$ and $\hat{\nu}$ be the
solutions of the following system of equations

$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf p}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf q}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf c}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\nu}=0,$ (49)

and, consequently, let

$\displaystyle c_{k}(\hat{{\bf p}},\hat{{\bf q}})$ $\displaystyle=$
$\displaystyle\sqrt{\hat{{\bf q}}_{k-1}-\hat{{\bf q}}_{k}}$ $\displaystyle
b_{k}(\hat{{\bf p}},\hat{{\bf q}})$ $\displaystyle=$
$\displaystyle\sqrt{\hat{{\bf p}}_{k-1}-\hat{{\bf p}}_{k}}.$ (50)

Then

$\xi(\delta)=\bar{\psi}_{rd}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta).$ (51)

###### Proof.

Follows from the above discussion, Theorem 1, Corollary 1, and the sfl RDT
machinery presented in [29, 26, 30, 31]. ∎

###  4.1 Numerical evaluations – AGS basin

As we have stated earlier, to have the results of Theorem 2 become practically
operational one needs to conduct all the underlying numerical evaluations.
Since all technical ingredients needed for the evaluations are already present
in the theorem itself, we start the evaluations with $r=1$ and proceed by
incrementally increasing $r$. This allows us to have a systematic view on how
the entire lifting machinery is progressing. Also, as mentioned earlier,
several analytical closed form results can be obtained as well. They turn out
to be critically important for simplification of the entire evaluation process
and we state them below as well.

####  4.1.1 $r=1$ – first level of lifting

For the first level, we have $r=1$ and $\hat{{\bf p}}_{1}\rightarrow 1$ and
$\hat{{\bf q}}_{1}\rightarrow 1$ which, together with $\hat{{\bf
p}}_{r+1}=\hat{{\bf p}}_{2}=\hat{{\bf q}}_{r+1}=\hat{{\bf q}}_{2}=0$, and
$\hat{{\bf c}}_{2}\rightarrow 0$, gives

$\displaystyle\bar{\psi}_{rd}^{(1)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\gamma_{sq},\nu,\delta)$ $\displaystyle=-\frac{1}{2}\hat{{\bf
c}}_{2}-2\nu\delta+\frac{1}{\hat{{\bf
c}}_{2}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{\hat{{\bf
c}}_{2}\left(-2\min\left(\sqrt{1-0}{\bf
h}_{1}^{(2)}-\nu,0\right)+\sqrt{1-0}{\bf h}_{1}^{(2)}\right)}\right)$
$\displaystyle\quad+\gamma_{sq}+\alpha\frac{1}{\hat{{\bf
c}}_{2}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{\hat{{\bf
c}}_{2}\frac{\left(\sqrt{1-0}{\bf
u}_{1}^{(2,2)}\right)^{2}}{4\gamma_{sq}}}\right)$
$\displaystyle\rightarrow-2\nu\delta+\frac{1}{\hat{{\bf
c}}_{2}}\log\left(1+{\mathbb{E}}_{{\mathcal{U}}_{2}}\hat{{\bf
c}}_{2}\left(-2\min\left(\sqrt{1-0}{\bf
h}_{1}^{(2)}-\nu,0\right)+\sqrt{1-0}{\bf h}_{1}^{(2)}\right)\right)$
$\displaystyle\quad+\gamma_{sq}+\alpha\frac{1}{\hat{{\bf
c}}_{2}}\log\left(1+{\mathbb{E}}_{{\mathcal{U}}_{2}}\hat{{\bf
c}}_{2}\frac{\left(\sqrt{1-0}{\bf
u}_{1}^{(2,2)}\right)^{2}}{4\gamma_{sq}}\right)$
$\displaystyle\rightarrow-2\nu\delta+\frac{1}{\hat{{\bf
c}}_{2}}\log\left(1+\hat{{\bf
c}}_{2}{\mathbb{E}}_{{\mathcal{U}}_{2}}\left(-2\min\left({\bf
h}_{1}^{(2)}-\nu,0\right)+{\bf h}_{1}^{(2)}\right)\right)$
$\displaystyle\quad+\gamma_{sq}+\alpha\frac{1}{\hat{{\bf
c}}_{2}}\log\left(1+\frac{\hat{{\bf c}}_{2}}{4\gamma_{sq}}\right)$
$\displaystyle\rightarrow-2\nu\delta+{\mathbb{E}}_{{\mathcal{U}}_{2}}\left(-2\min\left({\bf
h}_{1}^{(2)}-\nu,0\right)+{\bf h}_{1}^{(2)}\right)$
$\displaystyle\quad+\gamma_{sq}+\frac{\alpha}{4\gamma_{sq}}.$ (52)

From $\frac{\bar{\psi}_{rd}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}=0$, one easily finds
$\hat{\gamma}_{sq}=\frac{\sqrt{\alpha}}{2}$, which then gives

$\displaystyle\bar{\psi}_{rd}^{(1)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\nu,\delta)$ $\displaystyle\rightarrow$
$\displaystyle-2\nu\delta+{\mathbb{E}}_{{\mathcal{U}}_{2}}\left(-2\min\left({\bf
h}_{1}^{(2)}-\nu,0\right)+{\bf h}_{1}^{(2)}\right)+\sqrt{\alpha}$ (53)
$\displaystyle\rightarrow$ $\displaystyle f_{1}(\nu)+\sqrt{\alpha},$

where

$\displaystyle
f_{1}(\nu)\triangleq{\mathbb{E}}_{{\mathcal{U}}_{2}}\left(2\max\left(-{\bf
h}_{1}^{(2)}+\nu,0\right)+{\bf
h}_{1}^{(2)}\right)-2\nu\delta={\mathbb{E}}_{{\mathcal{U}}_{2}}\left(2\max\left(-{\bf
h}_{1}^{(2)}+\nu,0\right)\right)-2\nu\delta.$ (54)

After computing the above expectation, one obtains

$\displaystyle f_{1}(\nu)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\mathcal{U}}_{2}}\left(2\max\left(-{\bf
h}_{1}^{(2)}+\nu,0\right)\right)-2\nu\delta$ (55) $\displaystyle=$
$\displaystyle
2\left(\frac{1}{\sqrt{2\pi}}e^{-\nu^{2}/2}+\frac{\nu}{2}\mbox{erfc}\left(-\frac{\nu}{\sqrt{2}}\right)\right)-2\nu\delta.$

One then further has

$\displaystyle\frac{df_{1}(\nu)}{d\nu}$ $\displaystyle=$ $\displaystyle
2\left(\frac{1}{2}\mbox{erfc}\left(-\frac{\nu}{\sqrt{2}}\right)\right)-2\delta=\mbox{erfc}\left(-\frac{\nu}{\sqrt{2}}\right)-2\delta=1-2\delta-\mbox{erf}\left(-\frac{\nu}{\sqrt{2}}\right).$
(56)

From $\frac{\bar{\psi}_{rd}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\gamma_{sq},\nu,\delta)}{d\nu}=\frac{df_{1}(\nu)}{d\nu}=0$, one also finds
$\hat{\nu}=-\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)$, which then gives

$\displaystyle f_{1}(\hat{\nu})$ $\displaystyle=$ $\displaystyle
2\left(\frac{1}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\frac{\hat{\nu}}{2}\mbox{erfc}\left(-\frac{\hat{\nu}}{\sqrt{2}}\right)\right)-2\hat{\nu}\delta=\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\hat{\nu}\mbox{erfc}\left(-\frac{\hat{\nu}}{\sqrt{2}}\right)-2\hat{\nu}\delta$
(57) $\displaystyle=$
$\displaystyle\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\hat{\nu}-\hat{\nu}\mbox{erf}\left(-\frac{\hat{\nu}}{\sqrt{2}}\right)-2\hat{\nu}\delta=\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\hat{\nu}-\hat{\nu}\mbox{erf}\left(\mbox{erfinv}\left(1-2\delta\right)\right)-2\hat{\nu}\delta$
$\displaystyle=$
$\displaystyle\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\hat{\nu}-\hat{\nu}\left(1-2\delta\right)-2\hat{\nu}\delta=\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}.$

A combination of (14), (51), (53), and (57) gives

$\displaystyle\xi_{1}(\delta)$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\xi(\delta)^{2}=-\left(1-2\delta\right)^{2}-\left(\bar{\psi}_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)\right)^{2}$ (58) $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\left(f_{1}(\hat{\nu})+\sqrt{\alpha}\right)^{2}=-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}+\sqrt{\alpha}\right)^{2}$
$\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)^{2}$

Focusing on AGS basin related part of (18), one observes that the stationary
points of $\xi_{1}(\delta)$ are of critical importance for capacity
evaluation. To that end, we continue further by writing

$\displaystyle\frac{d\hat{\nu}}{d\delta}=\sqrt{2\pi}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}},$
(59)

and

$\displaystyle\frac{df_{1}(\hat{\nu})}{d\delta}=-\hat{\nu}\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}\frac{d\hat{\nu}}{d\delta}=-\hat{\nu}\frac{2}{\sqrt{2\pi}}e^{-\frac{\hat{\nu}^{2}}{2}}\sqrt{2\pi}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}=-2\hat{\nu}=-2\sqrt{2}\mbox{erfinv}\left(1-2\delta\right).$
(60)

Combining (58) and (60), we find

$\displaystyle\frac{d\xi_{1}(\delta)}{d\delta}$ $\displaystyle=$
$\displaystyle
4\left(1-2\delta\right)-2\left(f_{1}(\hat{\nu})+\sqrt{\alpha}\right)\frac{df_{1}(\hat{\nu})}{d\delta}$
(61) $\displaystyle=$ $\displaystyle
4\left(1-2\delta\right)-4\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right).$

From the capacity point of view, the most critical scenario happens when the
stationary points of $\xi_{1}(\delta)$ merge to become an infliction point. To
analytically determine the infliction point, the second derivative is needed
as well. To that end, we first have

$\displaystyle\frac{d^{2}f_{1}(\hat{\nu})}{d\delta^{2}}=-2\frac{d\hat{\nu}}{d\delta}=-2\sqrt{2\pi}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}},$
(62)

and then

$\displaystyle\frac{d^{2}\xi_{1}(\delta)}{d\delta^{2}}$ $\displaystyle=$
$\displaystyle-8-2\left(\frac{df_{1}(\hat{\nu})}{d\delta}\right)^{2}-2\left(f_{1}(\hat{\nu})+\sqrt{\alpha}\right)\frac{d^{2}f_{1}(\hat{\nu})}{d\delta^{2}}$
(63) $\displaystyle=$
$\displaystyle-8-8\hat{\nu}^{2}+4\sqrt{2\pi}\left(f_{1}(\hat{\nu})+\sqrt{\alpha}\right)e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}$
$\displaystyle=$
$\displaystyle-8-8\hat{\nu}^{2}+4\sqrt{2\pi}f_{1}(\hat{\nu})e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}+4\sqrt{2\pi}\sqrt{\alpha}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}$
$\displaystyle=$
$\displaystyle-8-8\hat{\nu}^{2}+4\sqrt{2\pi}\frac{2}{\sqrt{2\pi}}e^{-(\mbox{erfinv}\left(1-2\delta\right))^{2}}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}+4\sqrt{2\pi}\sqrt{\alpha}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}$
$\displaystyle=$
$\displaystyle-8\hat{\nu}^{2}+4\sqrt{2\pi}\sqrt{\alpha}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}$
$\displaystyle=$
$\displaystyle-16\mbox{erfinv}(1-2\delta)^{2}+4\sqrt{2\pi}\sqrt{\alpha}e^{(\mbox{erfinv}\left(1-2\delta\right))^{2}}.$

To determine the infliction point one needs

$\displaystyle\frac{d\xi_{1}(\delta)}{d\delta}=\frac{d^{2}\xi_{1}(\delta)}{d\delta^{2}}=0.$
(64)

From (63) and (64) we then have

$\displaystyle\sqrt{\alpha}=\frac{4}{\sqrt{2\pi}}\mbox{erfinv}(1-2\delta)^{2}e^{-(\mbox{erfinv}\left(1-2\delta\right))^{2}}.$
(65)

Plugging $\sqrt{\alpha}$ from (65) back into (61) and keeping in mind (64), we
obtain the following critical equation

$\displaystyle
4\left(1-2\delta\right)-4\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\frac{4}{\sqrt{2\pi}}\mbox{erfinv}(1-2\delta)^{2}e^{-(\mbox{erfinv}\left(1-2\delta\right))^{2}}\right)=0.$
(66)

After denoting by $\hat{\delta}$ the solution of (66), we then from (65)
finally have

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{first
level:}}})\qquad\qquad\alpha_{c}^{(AGS,1)}=\left(\frac{4}{\sqrt{2\pi}}\mbox{erfinv}(1-2\hat{\delta})^{2}e^{-(\mbox{erfinv}\left(1-2\hat{\delta}\right))^{2}}\right)^{2}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.137905566}}.$
(67)

We show in Figure 1 $\xi_{tot}(\delta)$ defined as

$\xi_{tot}(\delta)=\xi_{1}(\delta)-\xi_{1}(0)=-(1-2\delta)^{2}-\xi(\delta)^{2}+1+\alpha.$
(68)

It is not that difficult to see that $\xi_{tot}(\delta)$ is the shifted
version of $\xi_{1}(\delta)$ which accounts for the difference with respect to
the energy of the aimed memorized pattern.

Figure 1: $\xi_{tot}$ as a function of $\delta$;
$\alpha_{c}^{(AGS,1)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.137905566}}$
– maximum $\alpha$ such that the infliction point still exists on the first
level of lifting

The above analysis proceeded rather smoothly since the underlying analytical
calculations can be explicitly performed. In general, however, that might not
be the case. In such situations, it is useful to observe that the associative
memory capacity in the AGS basin sense, based on (18), can alternatively be
obtained as

$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{m}{n}$
$\displaystyle\alpha_{c}^{(AGS)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\exists\delta\in\left(0,\frac{1}{2}\right),\frac{d\xi_{1}(\delta)}{d\delta}=0\right\\}.$
(69)

Combining (61) and (69), one alternative finds

$\displaystyle\alpha_{c}^{(AGS,1)}$ $\displaystyle=$
$\displaystyle\left(\max_{\delta\in\left(0,\frac{1}{2}\right)}\frac{1-2\delta}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}\right)^{2}.$
(70)

It is not that difficult to check that $\hat{\delta}$ that satisfies (66) is
the solution to the above optimization. The above alternative view is
visualized in Figure 2. As figure indicates, $\alpha>\alpha_{c}^{(AGS,1)}$
would not be able to touch the right hand side of (70), i.e., the blue curve
in the figure.

Figure 2: Alternative view of
$\alpha_{c}^{(AGS,1)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.137905566}}$
– maximum $\alpha$ such that the infliction point still exists on the first
level of lifting

####  4.1.2 $r=2$ – second level of lifting

The setup presented above can be utilized for the second level as well. We
now, however, have $r=2$ and, similarly to what we had on the first level,
$\hat{{\bf p}}_{1}\rightarrow 1$ and $\hat{{\bf q}}_{1}\rightarrow 1$. On the
other hand, $\hat{{\bf c}}_{2}\neq 0$, ${\bf p}_{2}\neq 0$, and ${\bf
q}_{2}\neq 0$ which, together with $\hat{{\bf p}}_{r+1}=\hat{{\bf
p}}_{3}=\hat{{\bf q}}_{r+1}=\hat{{\bf q}}_{3}=0$ allows to write, analogously
to (4.1.1),

$\displaystyle\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)$ $\displaystyle=$ $\displaystyle-\frac{1}{2}(1-{\bf
p}_{2}{\bf q}_{2}){\bf c}_{2}-2\nu\delta$ $\displaystyle+\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{{\bf
c}_{2}\left(-2\min\left(\sqrt{1-{\bf q}_{2}}{\bf h}_{1}^{(2)}+\sqrt{{\bf
q}_{2}}{\bf h}_{1}^{(3)}-\nu,0\right)+\sqrt{1-{\bf q}_{2}}{\bf
h}_{1}^{(2)}+\sqrt{{\bf q}_{2}}{\bf h}_{1}^{(3)}\right)}\right)$
$\displaystyle+\gamma_{sq}+\alpha\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{{\bf
c}_{2}\frac{\left(\sqrt{1-{\bf p}_{2}}{\bf u}_{1}^{(2,2)}+\sqrt{{\bf
p}_{2}}{\bf u}_{1}^{(2,3)}\right)^{2}}{4\gamma_{sq}}}\right)$ $\displaystyle=$
$\displaystyle-\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf c}_{2}-2\nu\delta$
$\displaystyle+\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{{\bf
c}_{2}\left(-2\min\left(\sqrt{1-{\bf q}_{2}}{\bf h}_{1}^{(2)}+\sqrt{{\bf
q}_{2}}{\bf h}_{1}^{(3)}-\nu,0\right)+\sqrt{1-{\bf q}_{2}}{\bf
h}_{1}^{(2)}+\sqrt{{\bf q}_{2}}{\bf h}_{1}^{(3)}\right)}\right)$
$\displaystyle+\gamma_{sq}+\alpha\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2})}{2\gamma_{sq}}\right)+\frac{{\bf p}_{2}}{2(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))}\Bigg{.}\Bigg{)}.$

After solving the remaining integrals, we also have

$\displaystyle\hat{b}$ $\displaystyle=$ $\displaystyle\frac{\sqrt{{\bf
q}_{2}}{\bf h}_{1}^{(3)}-\nu}{\sqrt{1-{\bf q}_{2}}}$ $\displaystyle\hat{a}$
$\displaystyle=$ $\displaystyle{\bf c}_{2}\sqrt{1-{\bf q}_{2}}$ $\displaystyle
f_{(zu)}^{(2,f)}$ $\displaystyle=$ $\displaystyle e^{{\bf c}_{2}\sqrt{q}{\bf
h}_{1}^{(3)}}\left(\frac{1}{2}e^{\frac{\hat{a}^{2}}{2}}\left(\mbox{erf}\left(\frac{\hat{a}+\hat{b}}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{(zd)}^{(2,f)}$ $\displaystyle=$ $\displaystyle e^{-{\bf
c}_{2}\sqrt{q}{\bf h}_{1}^{(3)}+2{\bf
c}_{2}\nu}\left(\frac{1}{2}e^{\frac{\hat{a}^{2}}{2}}\left(\mbox{erf}\left(\frac{\hat{a}-\hat{b}}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{(zt)}^{(2,f)}$ $\displaystyle=$ $\displaystyle
f_{(zd)}^{(2,f)}+f_{(zu)}^{(2,f)}.$ (72)

and

$\displaystyle{\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}}e^{{\bf
c}_{2}\left(-2\min\left(\sqrt{1-{\bf q}_{2}}{\bf h}_{1}^{(2)}+\sqrt{{\bf
q}_{2}}{\bf h}_{1}^{(3)}-\nu,0\right)+\sqrt{1-{\bf q}_{2}}{\bf
h}_{1}^{(2)}+\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}\right)}\right)={\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left(f_{(zt)}^{(2,f)}\right).$
(73)

The _five_ derivatives with respect to ${\bf p}_{2}$, ${\bf q}_{2}$, ${\bf
c}_{2}$, $\gamma_{sq}$,, and $\nu$ need to be computed as well. This is done
next.

(i) ${\bf p}_{2}$ – derivative: We start with the following

$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf p}_{2}}$ $\displaystyle=$
$\displaystyle\frac{1}{2}{\bf q}_{2}{\bf
c}_{2}+\alpha\Bigg{(}\Bigg{.}-\frac{1}{2((2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2})))}+\frac{1}{2((2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2})))}$ (74)
$\displaystyle-\frac{{\bf p}_{2}}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2}))^{2}}{\bf c}_{2}\Bigg{.}\Bigg{)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}{\bf q}_{2}{\bf c}_{2}-\alpha\frac{{\bf
p}_{2}}{2(2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf p}_{2}))^{2}}{\bf c}_{2}$
$\displaystyle=$ $\displaystyle{\bf c}_{2}\left(\frac{1}{2}{\bf
q}_{2}-\alpha\frac{{\bf p}_{2}}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2}))^{2}}\right).$

(ii) ${\bf q}_{2}$ – derivative: As above, we start with

$\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf q}_{2}}=\frac{1}{2}{\bf p}_{2}{\bf
c}_{2}+\frac{1}{{\bf
c}_{2}}\frac{d\left({\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left(f_{(zt)}^{(2,f)}\right)\right)}{d{\bf
q}_{2}}=\frac{1}{2}{\bf p}_{2}{\bf c}_{2}+\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\frac{1}{f_{(zt)}^{(2,f)}}\frac{d\left(f_{(zt)}^{(2,f)}\right)}{d{\bf
q}_{2}}\right).$ (75)

From (4.1.2), we further have

$\displaystyle\frac{df_{(zt)}^{(2,f)}}{d{\bf q}_{2}}$ $\displaystyle=$
$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d{\bf
q}_{2}}+\frac{df_{(zu)}^{(2,f)}}{d{\bf q}_{2}}.$ (76)

We first find

$\displaystyle\frac{d\hat{b}}{d{\bf q}_{2}}$ $\displaystyle=$
$\displaystyle\frac{{\bf h}_{1}^{(3)}}{2\sqrt{{\bf q}_{2}}\sqrt{1-{\bf
q}_{2}}}-\frac{\nu}{2\sqrt{1-{\bf q}_{2}}^{3}}$
$\displaystyle\frac{d\hat{a}}{d{\bf q}_{2}}$ $\displaystyle=$
$\displaystyle-\frac{{\bf c}_{2}}{2\sqrt{1-{\bf q}_{2}}}.$ (77)

Then we obtain

$\displaystyle\frac{df_{(zu)}^{(2,f)}}{d{\bf q}_{2}}=f_{({\bf
q},u)}^{(1)}+f_{({\bf q},u)}^{(2)},$ (78)

where

$\displaystyle f_{({\bf q},u)}^{(1)}$ $\displaystyle=$
$\displaystyle\left(\frac{{\bf c}_{2}}{2\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}}+\hat{a}\frac{d\hat{a}}{d{\bf
q}_{2}}\right)\left(\frac{1}{2}e^{{\bf c}_{2}\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}+\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{({\bf q},u)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{{\bf c}_{2}\sqrt{q}{\bf
h}_{1}^{(3)}+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}+\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d{\bf
q}_{2}}+\frac{d\hat{b}}{d{\bf q}_{2}}\right)\frac{1}{\sqrt{2}}\right).$ (79)

One then analogously finds

$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d{\bf q}_{2}}=f_{({\bf
q},d)}^{(1)}+f_{({\bf q},d)}^{(2)},$ (80)

where

$\displaystyle f_{({\bf q},d)}^{(1)}$ $\displaystyle=$
$\displaystyle\left(-\frac{{\bf c}_{2}}{2\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}}+\hat{a}\frac{d\hat{a}}{d{\bf
q}_{2}}\right)\left(\frac{1}{2}e^{-{\bf c}_{2}\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}-\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{({\bf q},d)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{-{\bf c}_{2}\sqrt{q}{\bf h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}-\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d{\bf
q}_{2}}-\frac{d\hat{b}}{d{\bf q}_{2}}\right)\frac{1}{\sqrt{2}}\right).$ (81)

A combination of (4.1.2), (75)-(4.1.2) is then sufficient to determine ${\bf
q}_{2}$–derivative.

(iii) ${\bf c}_{2}$ – derivative: We again start by writing

$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf c}_{2}}$ $\displaystyle=$
$\displaystyle-\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2})-\frac{1}{{\bf
c}_{2}^{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\log\left(f_{(zt)}^{(2,f)}\right)+\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\frac{1}{f_{(zt)}^{(2,f)}}\frac{d\left(f_{(zt)}^{(2,f)}\right)}{d{\bf
c}_{2}}\right)$ (82) $\displaystyle+\alpha\Bigg{(}\Bigg{.}\frac{1}{2{\bf
c}_{2}^{2}}\log\left(\frac{2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2})}{2\gamma_{sq}}\right)+\frac{1-{\bf p}_{2}}{2{\bf
c}_{2}(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))}$ $\displaystyle+\frac{{\bf
p}_{2}(1-{\bf p}_{2})}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2}))^{2}}\Bigg{.}\Bigg{)}.$

From (4.1.2), we further have

$\displaystyle\frac{df_{(zt)}^{(2,f)}}{d{\bf c}_{2}}$ $\displaystyle=$
$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d{\bf
c}_{2}}+\frac{df_{(zu)}^{(2,f)}}{d{\bf c}_{2}}.$ (83)

Following what we presented above, we first find

$\displaystyle\frac{d\hat{b}}{d{\bf c}_{2}}$ $\displaystyle=$ $\displaystyle
0$ $\displaystyle\frac{d\hat{a}}{d{\bf c}_{2}}$ $\displaystyle=$
$\displaystyle\sqrt{1-{\bf q}_{2}}.$ (84)

Then we obtain

$\displaystyle\frac{df_{(zu)}^{(2,f)}}{d{\bf c}_{2}}=f_{({\bf
c},u)}^{(1)}+f_{({\bf c},u)}^{(2)},$ (85)

where

$\displaystyle f_{({\bf c},u)}^{(1)}$ $\displaystyle=$
$\displaystyle\left(\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+\hat{a}\frac{d\hat{a}}{d{\bf
c}_{2}}\right)\left(\frac{1}{2}e^{{\bf c}_{2}\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}+\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{({\bf c},u)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{{\bf c}_{2}\sqrt{q}{\bf
h}_{1}^{(3)}+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}+\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d{\bf
c}_{2}}+\frac{d\hat{b}}{d{\bf c}_{2}}\right)\frac{1}{\sqrt{2}}\right).$ (86)

One then analogously finds

$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d{\bf q}_{2}}=f_{({\bf
c},d)}^{(1)}+f_{({\bf c},d)}^{(2)},$ (87)

where

$\displaystyle f_{({\bf c},d)}^{(1)}$ $\displaystyle=$
$\displaystyle\left(-\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+2\nu+\hat{a}\frac{d\hat{a}}{d{\bf
c}_{2}}\right)\left(\frac{1}{2}e^{-{\bf c}_{2}\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}-\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{({\bf c},d)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{-{\bf c}_{2}\sqrt{q}{\bf h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}-\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d{\bf
c}_{2}}-\frac{d\hat{b}}{d{\bf c}_{2}}\right)\frac{1}{\sqrt{2}}\right).$ (88)

A combination of (4.1.2), (82)-(4.1.2) is then sufficient to determine ${\bf
c}_{2}$–derivative.

(iv) $\gamma_{sq}$ – derivative: We easily find

$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}$ $\displaystyle=$ $\displaystyle
1+\alpha\left(-\frac{1}{{\bf c}_{2}(2\gamma_{sq}-{\bf c}_{2}(1-{\bf
p}_{2}))}+\frac{1}{2{\bf c}_{2}\gamma_{sq}}-\frac{{\bf
p}_{2}}{(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))^{2}}\right)$
$\displaystyle=$ $\displaystyle 1+\alpha\left(-\frac{1-{\bf
p}_{2}}{2\gamma_{sq}(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))}-\frac{{\bf
p}_{2}}{(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))^{2}}\right).$

(v) $\nu$ – derivative: Following the path traced above, we start by writing

$\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\nu}=-2\delta+\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}}\left(\frac{1}{f_{(zt)}^{(2,f)}}\frac{d\left(f_{(zt)}^{(2,f)}\right)}{d\nu}\right).$
(90)

Recalling once again on (4.1.2), we have

$\displaystyle\frac{df_{(zt)}^{(2,f)}}{d\nu}$ $\displaystyle=$
$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d\nu}+\frac{df_{(zu)}^{(2,f)}}{d\nu}.$
(91)

After finding

$\displaystyle\frac{d\hat{b}}{d{\bf c}_{2}}$ $\displaystyle=$
$\displaystyle-\frac{1}{\sqrt{1-{\bf q}_{2}}}$
$\displaystyle\frac{d\hat{a}}{d{\bf c}_{2}}$ $\displaystyle=$ $\displaystyle
0,$ (92)

we then also observe that

$\displaystyle\frac{df_{(zu)}^{(2,f)}}{d\nu}=f_{(\nu,u)}^{(1)}+f_{(\nu,u)}^{(2)},$
(93)

where

$\displaystyle f_{(\nu,u)}^{(1)}$ $\displaystyle=$
$\displaystyle\left(\hat{a}\frac{d\hat{a}}{d{\bf
c}_{2}}\right)\left(\frac{1}{2}e^{{\bf c}_{2}\sqrt{{\bf q}_{2}}{\bf
h}_{1}^{(3)}+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}+\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{(\nu,u)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{{\bf c}_{2}\sqrt{q}{\bf
h}_{1}^{(3)}+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}+\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d\nu}+\frac{d\hat{b}}{d\nu}\right)\frac{1}{\sqrt{2}}\right).$
(94)

In a similar manner, one then also finds

$\displaystyle\frac{df_{(zd)}^{(2,f)}}{d\nu}=f_{(\nu,d)}^{(1)}+f_{(\nu,d)}^{(2)},$
(95)

where

$\displaystyle f_{(\nu,d)}^{(1)}$ $\displaystyle=$ $\displaystyle\left(2{\bf
c}_{2}+\hat{a}\frac{d\hat{a}}{d{\bf c}_{2}}\right)\left(\frac{1}{2}e^{-{\bf
c}_{2}\sqrt{{\bf q}_{2}}{\bf h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\hat{a}^{2}/2}\left(\mbox{erf}\left(\frac{(\hat{a}-\hat{b})}{\sqrt{2}}\right)+1\right)\right)$
$\displaystyle f_{(\nu,d)}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}e^{-{\bf c}_{2}\sqrt{q}{\bf h}_{1}^{(3)}+2{\bf
c}_{2}\nu+\frac{\hat{a}^{2}}{2}}\left(\frac{2}{\sqrt{\pi}}e^{-\frac{(\hat{a}-\hat{b})^{2}}{2}}\left(\frac{d\hat{a}}{d\nu}-\frac{d\hat{b}}{d\nu}\right)\frac{1}{\sqrt{2}}\right).$
(96)

Combining (4.1.2), (90)-(4.1.2) is sufficient to determine $\nu$–derivative.
After solving the following system

$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf q}_{2}}$ $\displaystyle=$ $\displaystyle 0$
$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf p}_{2}}$ $\displaystyle=$ $\displaystyle 0$
$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf c}_{2}}$ $\displaystyle=$ $\displaystyle 0$
$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}$ $\displaystyle=$ $\displaystyle 0$
$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\nu}$ $\displaystyle=$ $\displaystyle 0,$ (97)

and denoting by $\hat{{\bf p}}_{2},\hat{{\bf q}}_{2},\hat{{\bf
c}}_{2},\hat{\gamma}_{sq},\hat{\nu}$ the obtained solution, one obtains
$\bar{\psi}_{rd}^{(2)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)$ and consequently $\xi(\delta)$ and
$\xi_{1}(\delta)$. To determine the point of infliction one also needs
$\delta$-derivative.

(vi) $\delta$ – derivative: We first quickly note

$\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\delta}=-2\nu.$ (98)

Moreover, recalling on (14) and (51), we also have

$\frac{d\xi_{1}(\delta)}{d\delta}=4(1-2\delta)-2\xi(\delta)\frac{d\xi(\delta)}{d\delta}=4(1-2\delta)-2\bar{\psi}_{rd}^{(2)}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)\frac{d\bar{\psi}_{rd}^{(2)}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)}{d\delta}.$ (99)

One also recognizes that

$\displaystyle\frac{d\bar{\psi}_{rd}^{(2)}(\hat{{\bf p}},\hat{{\bf
q}},\hat{{\bf c}},\hat{\gamma}_{sq},\hat{\nu},\delta)}{d\delta}$
$\displaystyle=$
$\displaystyle\Bigg{(}\Bigg{.}\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf
q},{\bf c},\gamma_{sq},\nu,\delta)}{d{\bf p}_{2}}\frac{d{\bf
p}_{2}}{d\delta}+\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf q}_{2}}\frac{d{\bf q}_{2}}{d\delta}$ (100)
$\displaystyle+\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf c}_{2}}\frac{d{\bf
c}_{2}}{d\delta}+\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}\frac{d\gamma_{sq}}{d\delta}$
$\displaystyle+\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\nu}\frac{d\nu}{d\delta}+\frac{d\bar{\psi}_{rd}^{(2)}({\bf
p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\delta}\Bigg{.}\left.\Bigg{)}\right|_{({\bf
p},{\bf q},{\bf c},\gamma_{sq},\nu)=(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu})}$ $\displaystyle=$
$\displaystyle\left.\frac{d\bar{\psi}_{rd}^{(2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\delta}\right|_{({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu)=(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu})}$ $\displaystyle=$
$\displaystyle-2\hat{\nu}.$

Recalling on (18) and (69), one has that the associative memory capacity in
the AGS basin sense is given as

$\displaystyle\alpha_{c}^{(AGS)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\exists\delta\in\left(0,\frac{1}{2}\right),\frac{d\xi_{1}(\delta)}{d\delta}=0\right\\}.$
(101)

Combining (99) and (101), we then have

$\displaystyle\alpha_{c}^{(AGS,2)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\exists\delta\in\left(0,\frac{1}{2}\right),4(1-2\delta)+4\hat{\nu}\bar{\psi}_{rd}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)=0\right\\}.$ (102)

Taking the concrete numerical values gives

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{second
level:}}})\qquad\qquad\qquad\qquad\qquad
a_{c}^{(AGS,2)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.138186}}.$
(103)

_Closed form relations:_ Following [28, 32], we uncover the existence of
closed form explicit parameters relations that turn out to be of crucial help
for numerical handling of the above system. Namely, from (74), we first find

$\displaystyle{\bf q}_{2}=\alpha\frac{{\bf p}_{2}}{(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))^{2}}.$ (104)

From (4.1.2), we further have

$\displaystyle 1=\alpha\frac{1-{\bf p}_{2}}{2\gamma_{sq}(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))}+\alpha\frac{{\bf p}_{2}}{(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))^{2}}.$ (105)

A combination of (104) and (105) gives

$\displaystyle 1=\alpha\frac{1-{\bf p}_{2}}{2\gamma_{sq}(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))}+\alpha\frac{{\bf p}_{2}}{(2\gamma_{sq}-{\bf
c}_{2}(1-{\bf p}_{2}))^{2}}=\alpha\frac{1-{\bf
p}_{2}}{2\gamma_{sq}(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))}+{\bf q}_{2}.$
(106)

Combining (104) and (106) further, we obtain

$\displaystyle\gamma_{sq}=\alpha\frac{1-{\bf p}_{2}}{2(1-{\bf
q}_{2})(2\gamma_{sq}-{\bf c}_{2}(1-{\bf p}_{2}))}=\frac{1}{2}\frac{1-{\bf
p}_{2}}{1-{\bf q}_{2}}\sqrt{\frac{{\bf q}_{2}}{{\bf p}_{2}}\alpha}.$ (107)

Also, from (104) we can write

$\displaystyle{\bf c}_{2}(1-{\bf p}_{2})=2\gamma_{sq}-\sqrt{\frac{{\bf
p}_{2}}{{\bf q}_{2}}\alpha}.$ (108)

A combination of (107) and (108) then gives

$\displaystyle{\bf c}_{2}(1-{\bf p}_{2})=2\gamma_{sq}-\sqrt{\frac{{\bf
p}_{2}}{{\bf q}_{2}}\alpha}=\frac{1-{\bf p}_{2}}{1-{\bf
q}_{2}}\sqrt{\frac{{\bf q}_{2}}{{\bf p}_{2}}\alpha}-\sqrt{\frac{{\bf
p}_{2}}{{\bf q}_{2}}\alpha},$ (109)

and

$\displaystyle{\bf c}_{2}=\frac{1}{1-{\bf q}_{2}}\sqrt{\frac{{\bf q}_{2}}{{\bf
p}_{2}}\alpha}-\frac{1}{1-{\bf p}_{2}}\sqrt{\frac{{\bf p}_{2}}{{\bf
q}_{2}}\alpha}.$ (110)

_Concrete numerical values:_ In Table 1, $a_{c}^{(AGS,2)}$ is complemented
with the concrete values of all the relevant quantities related to the second
_full_ (2-sfl RDT) level of lifting. We also show in parallel the same
quantities for the first _full_ (1-sfl RDT) which enables a systematic view of
the lifting progress.

Table 1: $r$-sfl RDT parameters; Hopfield associative memory capacity; $\hat{{\bf c}}_{1}\rightarrow 1$; $n,\beta\rightarrow\infty$ $r$-sfl RDT | $\hat{\gamma}_{sq}$ | $\hat{\nu}$ | $\hat{\delta}$ | $\hat{{\bf p}}_{2}$ | $\hat{{\bf p}}_{1}`$ | $\hat{{\bf q}}_{2}$ | $\hat{{\bf q}}_{1}$ | $\hat{{\bf c}}_{2}$ | $\alpha_{c}^{(AGS,r)}$
---|---|---|---|---|---|---|---|---|---
$1$-sfl RDT | $0.1867$ | $-2.1372$ | $0.0163$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{0.137906}$
$2$-sfl RDT | $0.2153$ | $-2.1252$ | $0.0167$ | $0.99645$ | $\rightarrow 1$ | $0.99694$ | $\rightarrow 1$ | $16.6192$ | $\mathbf{0.138186}$

As was done on the first level, we visualize the above results by showing in
Figure 1 $\xi_{tot}(\delta)$ which is defined as

$\xi_{tot}(\delta)=\xi_{1}(\delta)-\xi_{1}(0)=-(1-2\delta)^{2}-\xi(\delta)^{2}+1+\alpha.$
(111)

We recall that $\xi_{tot}(\delta)$ is the shifted version of $\xi_{1}(\delta)$
which accounts for the difference with respect to the energy of the aimed
memorized pattern.

Figure 3: $\xi_{tot}$ as a function of $\delta$;
$\alpha_{c}^{(AGS,2)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.138186}}$
– maximum $\alpha$ such that the infliction point still exists on the second
level of lifting

As the figure shows, the convergence is remarkably fast. Even with a rather
tiny scaling of $y$ axis (with the values $\sim 10^{-3}$), the
$\xi_{tot}(\delta)\triangleq\xi_{1}(\delta)-\xi_{1}(0)$ curves for the first
and second level are almost indistinguishable. Consequently, we have that
already on the second level of lifting the associative capacity relative
improvement is $\sim 0.1\%$, which renders evaluations for higher levels
practically irrelevant. We also observe that the obtained results exactly
match the ones obtained utilizing the statistical physics methods based on
replica symmetry [2] and replica symmetry breaking [19].

####  4.1.3 Modulo-${\bf m}$ sfl RDT

Everything that we presented above can be repeated if one relies on the so-
called modulo-$m$ sfl RDT frame of [26]. Instead of Theorem 2, one then has
the following theorem.

######  Theorem 3.

Assume the setup of Theorem 2 and instead of the complete, assume the
modulo-${\bf m}$ sfl RDT setup of [26]. Let the “fixed” parts of $\hat{{\bf
p}}$, $\hat{{\bf q}}$, and $\hat{{\bf c}}$ satisfy $\hat{{\bf
p}}_{1}\rightarrow 1$, $\hat{{\bf q}}_{1}\rightarrow 1$, $\hat{{\bf
c}}_{1}\rightarrow 1$, $\hat{{\bf p}}_{r+1}=\hat{{\bf q}}_{r+1}=\hat{{\bf
c}}_{r+1}=0$, and let the “non-fixed” parts of $\hat{{\bf p}}_{k}$, and
$\hat{{\bf q}}_{k}$ ($k\in\\{2,3,\dots,r\\}$), $\hat{\gamma}_{sq}$, and
$\hat{\nu}$ be the solutions of the following system of equations

$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf p}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d{\bf q}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\gamma_{sq}}=0$
$\displaystyle\frac{d\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\nu,\delta)}{d\nu}=0.$ (112)

Consequently, let

$\displaystyle c_{k}(\hat{{\bf p}},\hat{{\bf q}})$ $\displaystyle=$
$\displaystyle\sqrt{\hat{{\bf q}}_{k-1}-\hat{{\bf q}}_{k}}$ $\displaystyle
b_{k}(\hat{{\bf p}},\hat{{\bf q}})$ $\displaystyle=$
$\displaystyle\sqrt{\hat{{\bf p}}_{k-1}-\hat{{\bf p}}_{k}}.$ (113)

Then

$\displaystyle\xi(\delta)\geq\min_{{\bf c}}\bar{\psi}_{rd}(\hat{{\bf
p}},\hat{{\bf q}},{\bf c},\hat{\gamma}_{sq},\hat{\nu},\delta).$ (114)

###### Proof.

Follows from the above discussions, Theorems 1 and 2, Corollary 1, and the sfl
RDT machinery presented in [29, 26, 30]. ∎

We conducted the numerical evaluations using the modulo-${\bf m}$ results of
the above theorem and found no scenario where the inequality in (114) is not
tight, which indicates that the _stationarity_ over ${\bf c}$ is of the
_minimization_ type. Moreover, we repeated the same type of evaluations for
the NLT considerations discussed below and observed the very same behavior.

###  4.2 Numerical evaluations – NLT basin

Below we show that the capacity results analogous to the AGS basin ones
presented above, can be obtained for the NLT basin as well. Moreover, many of
the calculations remains the same. What changes is the way how one uses them.
As was the case above when analyzing the AGS basin, we again start the
evaluations with $r=1$ and proceed by incrementally increasing $r$.

####  4.2.1 $r=1$ – first level of lifting

Everything between (4.1.1) and (61) remains in place again, which means that
we have $\hat{\nu}=\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)$,

$\displaystyle\xi_{1}(\delta)$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)^{2},$
(115)

and

$\displaystyle\frac{d\xi_{1}(\delta)}{d\delta}$ $\displaystyle=$
$\displaystyle
4\left(1-2\delta\right)-4\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right).$
(116)

Recalling on (18), we observe that the associative memory capacity in the NLT
basin sense, can alternatively be obtained as

$\displaystyle\alpha_{c}^{(NLT)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\exists\hat{\delta}\in\left(0,\frac{1}{2}\right),\left.\frac{d\xi_{1}(\delta)}{d\delta}\right|_{\delta=\hat{\delta}}=0\quad\mbox{and}\quad\xi_{1}(\hat{\delta})=\xi_{1}(0)\right\\}.$
(117)

Utilizing (116) and $\frac{d\xi_{1}(\delta)}{d\delta}=0$, implies the
following choice

$\displaystyle\alpha$ $\displaystyle=$
$\displaystyle\left(\frac{1-2\delta}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}\right)^{2}.$
(118)

Recalling on (115) and $\xi(0)=-1-\alpha$, we then have that
$\xi_{1}(\hat{\delta})=\xi_{1}(0)$ implies

$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)^{2}=\xi_{1}(\delta)=\xi_{1}(0)=-1-\alpha.$
(119)

After plugging $\alpha$ from (118) into (119), we obtain

$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{1-2\delta}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}\right)^{2}=-1-\left(\frac{1-2\delta}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}\right)^{2}.$
(120)

A bit of additional algebraic transformations gives

$\displaystyle
2\delta(1-\delta)-\frac{1-2\delta}{\sqrt{\pi}\mbox{erfinv}\left(1-2\delta\right)}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\frac{1}{\pi}e^{-2\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}=0.$
(121)

After denoting by $\hat{\delta}$ the solution of (121), we then from (118)
finally have

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{first
level:}}})\qquad\qquad\alpha_{c}^{(NLT,1)}=\left(\frac{1-2\hat{\delta}}{\sqrt{2}\mbox{erfinv}\left(1-2\hat{\delta}\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\hat{\delta}\right)\right)^{2}}\right)^{2}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.1294899}}.$
(122)

Similarly to what we sowed in Figure 1, in Figure 4, we, for
$\alpha=\alpha_{c}^{(NLT,1)}$, show $\xi_{tot}(\delta)$ – a shifted version of
$\xi_{1}(\delta)$ defined as

$\xi_{tot}(\delta)=\xi_{1}(\delta)-\xi_{1}(0)=-(1-2\delta)^{2}-\xi(\delta)^{2}+1+\alpha.$
(123)

As figure indicates, in addition to $\xi_{tot}(0)=0$, one also has
$\xi_{tot}(\delta)=0$ for $\delta=\hat{\delta}\approx 0.033935$.

Figure 4: $\xi_{tot}$ as a function of $\delta$;
$\alpha_{c}^{(NLT,1)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.1294899}}$
– maximum $\alpha$ such that $\exists\delta\in\left(0,\frac{1}{2}\right)$ for
which $\xi_{tot}(\delta)=\xi_{tot}(0)$ on the first level of lifting

For the completeness, we also mention that with a little bit of additional
algebraic transformations the above capacity characterization can be rewritten
in the following, possibly more compact/elegant, way:

$\displaystyle\alpha_{c}^{(NLT,1)}$ $\displaystyle=$
$\displaystyle\frac{\mbox{erf}(x)^{2}}{2x^{2}}-1+\mbox{erf}(x)^{2}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.1294899}},\quad
1-\mbox{erf}(x)^{2}-\frac{2\mbox{erf}(x)e^{-x^{2}}}{\sqrt{\pi}x}+\frac{2e^{-2x^{2}}}{\pi}=0.$
(124)

It is not that difficult to see the correspondence
$x=\mbox{erfinv}\left(1-2\hat{\delta}\right)$.

####  4.2.2 $r=2$ – second level of lifting

One again can utilize the results obtained for the AGS basin. In particular,
everything between (4.1.2) and (100) remain in place. Instead of utilizing
(101), we now recall on (18) and utilize (125). As the difference between
(101) and (125) is in an additionally imposed constraint
$\xi_{1}(\hat{\delta})=\xi_{1}(0)$, one can still utilize (102) but with a
slight modification to account for such a constraint. This basically means
that instead of (101), we now have

$\displaystyle\alpha_{c}^{(NLT)}$ $\displaystyle\triangleq$
$\displaystyle\max\left\\{\alpha|\hskip
5.78172pt\exists\hat{\delta}\in\left(0,\frac{1}{2}\right),\left.\frac{d\xi_{1}(\delta)}{d\delta}\right|_{\delta=\hat{\delta}}=0\quad\mbox{and}\quad\xi_{1}(\hat{\delta})=\xi_{1}(0)=-1-\alpha\right\\},$
(125)

and instead of (102)

$\alpha_{c}^{(NLT,2)}=\max\left\\{\alpha|\hskip
2.8903pt\exists\delta\in\left(0,\frac{1}{2}\right),4(1-2\delta)+4\hat{\nu}\bar{\psi}_{rd}^{(2)}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)=0\quad\mbox{and}\quad\xi_{1}(\hat{\delta})=\xi_{1}(0)=-1-\alpha\right\\},$
(126)

where we also recall from (14) and (51) that on the second level
$\xi_{1}(\delta)$ is given as

$\displaystyle\xi_{1}(\delta)$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\xi(\delta)^{2}=-\left(1-2\delta\right)^{2}-\left(\bar{\psi}_{rd}^{(2)}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\nu},\delta)\right)^{2},$ (127)

Taking the concrete numerical values gives

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{second
level:}}})\qquad\qquad\qquad\qquad\qquad
a_{c}^{(NLT,2)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.12979}}.$
(128)

_Concrete numerical values:_ Analogously to Table 1, we in Table 2 complement
$a_{c}^{(NLT,2)}$ with the concrete values of all the relevant quantities
related to the second _full_ (2-sfl RDT) level of lifting. As was the case for
the AGS basin in Table 1, we here also show both first and second level
parameters’ values in parallel ensuring that a systematic view of the lifting
progressing mechanism is enabled.

Table 2: $r$-sfl RDT parameters; Hopfield associative memory capacity – NLT basin; $\hat{{\bf c}}_{1}\rightarrow 1$; $n,\beta\rightarrow\infty$ $r$-sfl RDT | $\hat{\gamma}_{sq}$ | $\hat{\nu}$ | $\hat{\delta}$ | $\hat{{\bf p}}_{2}$ | $\hat{{\bf p}}_{1}`$ | $\hat{{\bf q}}_{2}$ | $\hat{{\bf q}}_{1}$ | $\hat{{\bf c}}_{2}$ | $\alpha_{c}^{(NLT,r)}$
---|---|---|---|---|---|---|---|---|---
$1$-sfl RDT | $0.1799$ | $-1.8259$ | $0.0339$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{0.12949}$
$2$-sfl RDT | $0.2309$ | $-1.8111$ | $0.0347$ | $0.98806$ | $\rightarrow 1$ | $0.99067$ | $\rightarrow 1$ | $8.54157$ | $\mathbf{0.12979}$

As earlier, we visualize the above results in Figure 5 by showing
$\xi_{tot}(\delta)$.

Figure 5: $\xi_{tot}$ as a function of $\delta$;
$\alpha_{c}^{(NLT,2)}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.12979}}$
– maximum $\alpha$ such that $\exists\delta\in\left(0,\frac{1}{2}\right)$ for
which $\xi_{tot}(\delta)=\xi_{tot}(0)$ on the second level of lifting

As is rather clear from the figure, the convergence is remarkably fast.
Similarly to what we had for the AGS basin, the
$\xi_{tot}(\delta)\triangleq\xi_{1}(\delta)-\xi_{1}(0)$ curves for the first
and second level are almost indistinguishable and already on the second level
of lifting the associative capacity relative improvement is $\sim 0.1\%$. This
again, for all practical purposes, renders evaluations for higher levels as
basically of not much significance.

###  4.3 AGS vs NLT basins

To illustrate the key conceptual difference between AGS and NLT basins, we
show their $\xi_{tot}(\delta)$ in parallel in Figure 6.

Figure 6: $\xi_{tot}$ as a function of $\delta$; AGS vs NLT basin

As can be seen from the figure, the lifting convergence is remarkably fast in
both cases. Also, the curves clearly display the key point: the AGS basin
revolves around the concept of having any form of a well (no matter how
shallow it is) whereas the NLT insists on having a more robust rather deep
well with the local maximum matching (borderline exceeding) the zero value
that corresponds to the value of the aimed stored pattern.

###  4.4 Global local minima

Both AGS and NLT ultimately rely on having basins of attraction around the
aimed pattern which are characterized by the existence of a local minimum. As
$\alpha$ decreases, these local minima become global. The above machinery can
be reutilized to determine critical $\alpha=\alpha_{c}^{(GLM)}$ where this
happens. Namely, this will happen where no vector ${\bf x}$ which is not in
the vicinity of one of the patterns (i.e., which has zero overlap with them)
can achieve a minimum lower than the local one from the AGS well. This
basically means that one can use all of the above AGS results with the
exception that now $\delta=0.5$.

In particular, we have for the first level of lifting

$\alpha_{c}^{(GLM,1)}=\left\\{\alpha|\min_{\delta\in\left(0,\frac{1}{2}\right)}\xi_{1}(\delta)-\xi_{1}(0.5)=0\right\\},$
(129)

where $\xi_{1}(\delta)$ is as in (58), i.e.,

$\displaystyle\xi_{1}(\delta)$ $\displaystyle=$
$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)^{2}.$
(130)

We first note that

$\displaystyle\xi_{1}(0.5)$ $\displaystyle=$
$\displaystyle-\left(\frac{2}{\sqrt{2\pi}}+\sqrt{\alpha}\right)^{2},$ (131)

and then, recalling on (61), also

$\displaystyle\frac{d\xi_{1}(\delta)}{d\delta}$ $\displaystyle=$
$\displaystyle
4\left(1-2\delta\right)-4\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right).$
(132)

Denoting by $\hat{\delta}$ the solution of the optimization in (129), one
observes, after combining (129)-(132), that pair
$\left(\alpha_{c}^{(GLM,1)},\hat{\delta}\right)$ satisfies the following
system

$\displaystyle-\left(1-2\delta\right)^{2}-\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)^{2}=\xi_{1}(\delta)=\xi_{1}(0.5)=-\left(\frac{2}{\sqrt{2\pi}}+\sqrt{\alpha}\right)^{2}$
$\displaystyle\frac{d\xi_{1}(\delta)}{d\delta}=4\left(1-2\delta\right)-4\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)\left(\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}+\sqrt{\alpha}\right)=0.$
(133)

From (133), we then further find the following system

$\displaystyle\sqrt{\alpha}$ $\displaystyle=$
$\displaystyle(1-2\delta)\sqrt{1+\frac{1}{2(\mbox{erfinv}(1-2\delta))^{2}}}-\frac{2}{\sqrt{2\pi}}$
$\displaystyle\sqrt{\alpha}$ $\displaystyle=$
$\displaystyle\frac{\left(1-2\delta\right)}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}.$
(134)

From (134) one then establishes that

$\displaystyle\hat{\delta}=\left\\{\delta|(1-2\delta)\left(\sqrt{1+\frac{1}{2(\mbox{erfinv}(1-2\delta))^{2}}}-\frac{1}{\sqrt{2}\mbox{erfinv}\left(1-2\delta\right)}\right)=\frac{2}{\sqrt{2\pi}}\left(1-e^{-\left(\mbox{erfinv}\left(1-2\delta\right)\right)^{2}}\right)\right\\}.$
(135)

Utilizing (135) we find $\hat{\delta}\approx 5.6574\times 10^{-6}$ and

$\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{first
level:}})}\qquad\qquad\qquad\alpha_{c}^{(GLM,1)}=\frac{\left(1-2\hat{\delta}\right)}{\sqrt{2}\mbox{erfinv}\left(1-2\hat{\delta}\right)}-\frac{2}{\sqrt{2\pi}}e^{-\left(\mbox{erfinv}\left(1-2\hat{\delta}\right)\right)^{2}}\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{0.05185}},$
(136)

Moreover, using the above $\hat{\delta}$ and $\alpha_{c}^{(GLM,1)}$, one also
finds
$\xi_{1}(\hat{\delta})-\xi_{1}(0)=\xi_{1}(\hat{\delta})+1+\alpha_{c}^{(GLM,1)}=\xi_{1}(0.5)-\xi_{1}(0)=\xi_{1}(0.5)+1+\alpha_{c}^{(GLM,1)}\approx-1.072\times
10^{-6}$.

After conducting the corresponding numerical work for the second level of
lifting, one obtains the results shown in Tables 3 and 4. Table 3 relates to
$\min_{\delta\in\left(0,\frac{1}{2}\right)}\xi_{1}(\delta)$ and Table 4
relates to $\xi_{1}(0.5)$. We also observe that $\alpha_{c}^{(GLM,1)}$ exactly
matches the value obtained through the replica symmetry methods in [2].

Table 3: $r$-sfl RDT parameters; Hopfield associative memory capacity – Global local minima; minimum achieving $\delta\in\left(0,\frac{1}{2}\right)$; $\hat{{\bf c}}_{1}\rightarrow 1$; $n,\beta\rightarrow\infty$ $r$-sfl RDT | $\hat{\gamma}_{sq}$ | $\hat{\nu}$ | $\hat{\delta}$ | $\hat{{\bf p}}_{2}$ | $\hat{{\bf p}}_{1}`$ | $\hat{{\bf q}}_{2}$ | $\hat{{\bf q}}_{1}$ | $\hat{{\bf c}}_{2}$ | $\alpha_{c}^{(GLM,r)}$
---|---|---|---|---|---|---|---|---|---
$1$-sfl RDT | $0.1139$ | $-4.3904$ | $5.6574e-06$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{0.051854}$
$2$-sfl RDT | $0.1185$ | $-4.2184$ | $1.23e-5$ | $\rightarrow 1$ | $\rightarrow 1$ | $\rightarrow 1$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{0.056141}$
Table 4: $r$-sfl RDT parameters; Hopfield associative memory capacity – Global local minima; $\delta=0.5$; $\hat{{\bf c}}_{1}\rightarrow 1$; $n,\beta\rightarrow\infty$ $r$-sfl RDT | $\hat{\gamma}_{sq}$ | $\hat{\nu}$ | $\hat{\delta}$ | $\hat{{\bf p}}_{2}$ | $\hat{{\bf p}}_{1}`$ | $\hat{{\bf q}}_{2}$ | $\hat{{\bf q}}_{1}$ | $\hat{{\bf c}}_{2}$ | $\alpha_{c}^{(GLM,r)}$
---|---|---|---|---|---|---|---|---|---
$1$-sfl RDT | $0.1139$ | $0$ | $0.5$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{0.051854}$
$2$-sfl RDT | $0.2200$ | $0$ | $0.5$ | $0.5625$ | $\rightarrow 1$ | $0.7314$ | $\rightarrow 1$ | $0.5308$ | $\mathbf{0.056141}$

##  5 Conclusion

We studied the classical _Hopfield_ neural network model with the _Hebbian_
learning rule. The primary focus was on network’s associative memory. We
considered the Hopfield’s original scenario where the retrieval dynamics is
allowed to make a small fraction of errors in recovering the aimed patterns.
Studying binary random patterns, Hopfield suggested in his introductory paper,
that the associative capacity (maximal number of reliably stored patterns,
$m$) of fraction of errors allowing dynamics should grow linearly with the
pattern’s size, $n$. Moreover, utilizing a random noise argument and relying
on numerical algorithmic evidence, he also famously predicted that
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}\approx 0.14$. We here consider
several variants of this Hopfield setup and obtain results that are in an
excellent agreement with his predictions

After first making the connection between studying Hopfield’s nets capacities
and bilinearly indexed (bli) random processes, we utilized recent progress in
bli’s from [26, 29] and the _fully lifted_ random duality theory (fl RDT) from
[30] to create a powerful generic framework for the analysis of the networks
dynamics. The concept of the associative capacity critically depends on the
existence of a basin of attraction around each of the patterns to be
memorized. For a proper assessment of the capacity an accurate description of
the basin is unavoidably needed. We considered two notions of the basin most
prevalently used in the literature: _(i)_ The AGS one from [2] which relies on
the existence of a local energy minimum around aimed pattern; and _(ii)_ The
NLT one from [16, 11, 12, 13, 33] which relies on the existence of a firm
energy barrier around patterns. A tradeoff between the two exists as well.
Namely, the NLT one is more strict and robust and implies the first one. On
the other hand the capacities that it allows for are smaller than the ones
allowed by the AGS.

To be able to successively utilize the fl RDT and obtain concrete capacity
characterizations for both AGS and NLT basins, one needs to perform a
substantial amount of numerical work. We performed all the needed evaluations,
uncovered remarkable closed form explicit analytical relations among key
lifting parameters, and ultimately obtained concrete numerical values for the
capacities of both basin. Moreover, on the first level of lifting, we obtained
explicit closed form capacity characterizations. After completing the second
level numerical evaluations, we uncovered a surprising convergence property.
Namely, while the convergence rate of fl RDT is generically excellent, we here
discovered that it is remarkably rapid even for the typical fl RDT standards.
In particular, we found for both AGS and NLT that the relative improvements no
better than $\sim 0.1\%$ are happening already on the _second_ (first
nontrivial) level of the full lifting. We also found that the obtained AGS
based capacity characterizations exactly match those obtained through the
statistical physics replica symmetry methods of [2] and the corresponding
symmetry breaking ones of [19]. On the other hand the NLT ones are
substantially higher than the previously best known ones of [16, 11, 12, 13,
33].

The developed methodology is very generic and further extensions and
generalizations are possible. They include studying various other Network
properties as well as different architectures and dynamics. The associated
technical details are problem specific and we discuss them in separate papers.

## References

  * [1] E. Agliari, L. Albanese, F. Alemanno, A. Alessandrelli, A. Barra, F. Giannotti, D. Lotito, and D. Pedreschi.  Dense hebbian neural networks: A replica symmetric picture of supervised learning.  Physica A: Statistical Mechanics and its Applications, 626:129076, 2023.
  * [2] D. J. Amit, H. Gutfreund, and H. Sompolinsky.  Storing infinite number of patterns in a spin glass model of neural networks.  Phys. Rev. Letters, 55:1530, 1985.
  * [3] S. Chatterjee.  A generalization of the Lindenberg principle.  The Annals of Probability, 34(6):2061–2076.
  * [4] M. Demircigil, J. Heusel, M. Lowe, S. Upgang, and F. Vermet.  On a model of associative memory with huge storage capacity.  Journal of Statistical Physics, 168(2):288–299, July 2017.
  * [5] J. Feng, M. Shcherbina, and B. Tirozzi.  On the critical capacity of the Hopfield model.  Communications in Mathematical Physics, 2000.
  * [6] E. Gardner.  Multiconnected neural network models.  Journal of Physics A: Mathematical and General, 20(1):3453–3464, August 1987.
  * [7] D. O. Hebb.  Organization of behavior.  New York: Wiley, 1949.
  * [8] J. J. Hopfield.  Neural networks and physical systems with emergent collective computational abilities.  Proc. Nat. Acad. Science, 79:2554, 1982.
  * [9] J. Komlos and R. Paturi.  Convergence results in an autoassociative memory model.  Neural Networks, 1:239–250, 1988.
  * [10] D. Krotov and J. J. Hopfield.  Dense associative memory for pattern recognition.  Advances in Neural Information Processing Systems, 1:1180–1188, 2016.
  * [11] D. Loukianova.  Capacite de memoire dans le modele de Hopfield.  C. R. Acad. Sci. Paris t. 318, Serie I, pages 157–160, 1994.
  * [12] D. Loukianova.  Etude rigoureuse du modele de Hopfield de memoire associative.  These de doctorat de l’Universite Paris 7, 1994.
  * [13] D. Loukianova.  Lower bounds on the restitution error in the Hopfield model.  Probab. Theory Related Fields, 107:161–176, 1997.
  * [14] Carlo Lucibello and Marc Mézard.  Exponential capacity of dense associative memories.  Phys. Rev. Lett., 132:077301, Feb 2024.
  * [15] R. J. MacEliece, E. C. Posner, E. Rodemich, and S.S. Venkatesh.  The capacity of the Hopfield associative memory.  IEEE Trans. Inform. Theory, 33:461–482, 1987.
  * [16] Ch. M. Newman.  Memory capacity and neural network models: Rigorous lower bounds.  Neural Networks, 1:223–238, 1988.
  * [17] L. Pastur and A. Figotin.  Exactly soluble model of a spin-glass.  Soviet J. of Low Temperature Phys., 3(378-383), 1977.
  * [18] H. Ramsauer, B. Schafl, J. Lehner, P. Seidl, M. Widrich, L. Gruber, M. Holzleitner, T. Adler, D. Kreil, M. K. Kopp, G. Klambauer, J. Brandstetter, and S. Hochreiter.  Hopfield networks is all you need.  In International Conference on Learning Representations, 2021.
  * [19] H. Steffan and R. Kuhn.  Replica symmetry breaking in attractor neural network models.  Z. Phys. B, 95:249–260, 1994.
  * [20] M. Stojnic.  Another look at the Gardner problem.  2013\.  available online at http://arxiv.org/abs/1306.3979.
  * [21] M. Stojnic.  Discrete perceptrons.  2013\.  available online at http://arxiv.org/abs/1303.4375.
  * [22] M. Stojnic.  Lifting $\ell_{1}$-optimization strong and sectional thresholds.  2013\.  available online at http://arxiv.org/abs/1306.3770.
  * [23] M. Stojnic.  Lifting/lowering Hopfield models ground state energies.  2013\.  available online at http://arxiv.org/abs/1306.3975.
  * [24] M. Stojnic.  Negative spherical perceptron.  2013\.  available online at http://arxiv.org/abs/1306.3980.
  * [25] M. Stojnic.  Spherical perceptron as a storage memory with limited errors.  2013\.  available online at http://arxiv.org/abs/1306.3809.
  * [26] M. Stojnic.  Bilinearly indexed random processes – _stationarization_ of fully lifted interpolation.  2023\.  available online at http://arxiv.org/abs/2311.18097.
  * [27] M. Stojnic.  Binary perceptrons capacity via fully lifted random duality theory.  2023\.  available online at http://arxiv.org/abs/2312.00073.
  * [28] M. Stojnic.  Fl RDT based ultimate lowering of the negative spherical perceptron capacity.  2023\.  available online at http://arxiv.org/abs/2312.16531.
  * [29] M. Stojnic.  Fully lifted interpolating comparisons of bilinearly indexed random processes.  2023\.  available online at http://arxiv.org/abs/2311.18092.
  * [30] M. Stojnic.  Fully lifted random duality theory.  2023\.  available online at http://arxiv.org/abs/2312.00070.
  * [31] M. Stojnic.  Studying Hopfield models via fully lifted random duality theory.  2023\.  available online at http://arxiv.org/abs/2312.00071.
  * [32] M. Stojnic.  Exact capacity of the _wide_ hidden layer treelike neural networks with generic activations.  2024\.  available online at http://arxiv.org/abs/2402.05719.
  * [33] M. Talagrand.  Rigorous results for the Hopfield models with many patterns.  Prob. Theor. Rel. Fields, 110:109–176, 1998.
  * [34] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin.  Attention is all you need.  In Advances in neural information processing systems, 1:5998–6008, 2017.