# Exact capacity of the _wide_ hidden layer treelike neural networks with
generic activations

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

Recent progress in studying _treelike committee machines_ (TCM) neural
networks (NN) in [36, 40] showed that the Random Duality Theory (RDT) and its
a _partially lifted_(pl RDT) variant are powerful tools that can be used for
very precise networks capacity analysis. The initial considerations from [36,
40], related to the famous _sign_ activations, were then extended to more
general activations in [42], where particularly elegant results were obtained
for _any_ even number of the _quadratically_ and _ReLU_ activated hidden layer
neurons, $d$. While the results of [42] are in principle applicable to any
type of activations a significant amount of numerical work is often needed to
make them practically usable. Here, we consider _wide_ hidden layer networks
and uncover that certain aspects of such difficulties miraculously disappear.
In particular, we employ recently developed _fully lifted_ (fl) RDT to
characterize the _wide_ ($d\rightarrow\infty$) TCM nets capacity. We obtain
explicit, closed form, capacity characterizations for a very generic class of
the hidden layer activations. While the utilized approach significantly lowers
the amount of the needed numerical evaluations, the ultimate fl RDT usefulness
and success still require a solid portion of the residual numerical work. To
get the concrete capacity values, we take four very famous activations
examples: _ReLU_ , _quadratic_ , _erf_ , and _tanh_. After successfully
conducting all the residual numerical work for all of them, we uncover that
the whole lifting mechanism exhibits a remarkably rapid convergence with the
relative improvements no better than $\sim 0.1\%$ happening already on the
3-rd level of lifting. As a convenient bonus, we also uncover that the
capacity characterizations obtained on the first and second level of lifting
precisely match those obtained through the statistical physics replica theory
methods in [53] for the generic and in [2] for the ReLU activations.

Index Terms: Wide TCM neural networks; Capacity; Fully lifted random duality
theory; ReLU, quadratic, erf, tanh.

##  1 Introduction

Development of machine learning (ML) and neural networks (NN) concepts
experienced a rapid progress over the last 15-20 years. Larger than ever need
for efficient handling and interpretation of huge data sets stimulated the
invention of many fundamental algorithmic NN breakthroughs. Such an
algorithmic progress necessarily dictated advancement of the accompanying
analytical/theoretical justification methodologies. Along the paths of both
algorithmic and theoretical advancements, many new concepts have been
developed and many old ones have been revisited and brought to practical
usability. We are here interested in, possibly, the most important of them
all, namely the so-called, network’s _memory capacity_ (see, e.g., [26, 9, 49,
48, 47, 8, 22, 16, 45, 3]). As is well known, studying the network capacity
has two key components: _(i)_ the _theoretical_ one which attempts to provide
the engineering practitioners with the mathematically precise description of
the ultimate underlying network architecture usefulness; and _(ii)_ the
_practical/algorithmic_ one which attempts to provide the users with the
concrete (hopefully efficiently implementable) computational methodologies to
indeed utilize the network architectures to their ultimate potential. Here we
continue the trend established in the recent literature, focus on the first
one, and provide a strong theoretical progress on several important capacity
related questions. To be able to properly present the technical contributions
and to adequately contextualize them within the relevant prior work, we find
it convenient to first introduce the needed mathematical formalisms that best
describe the underlying NN models.

###  1.1 Architecture of the _wide_ hidden layer generically activated NNs

We start with a generic architecture description of the multi-input single-
output feed-forward neural networks with $L-2$ hidden layers and $d_{i}$
($i\in\\{1,2,\dots,L\\}$) nodes (neurons) in the $i$-th layer. For the
notational convenience, we add two artificial layers, indexed by $i=1$ and
$i=L$, which correspond to the network’s input and output, respectively.
Although they are artificial, we refer to them as networks layers to ensure
the consistency of the overall indexation. The network operates through the
specification of the activation functions vectors, ${\bf f}^{(i)}(\cdot)=[{\bf
f}_{1}^{(i)}(\cdot),{\bf f}_{2}^{(i)}(\cdot),\dots,{\bf
f}_{d_{i+1}}^{(i)}(\cdot)]^{T}$, where each activation function ${\bf
f}_{j}^{(i)}(\cdot):{\mathbb{R}}^{d_{i}}\rightarrow{\mathbb{R}}$ describes how
the $j$-th neuron in layer $i$ operates. One effectively has that the outputs
of the nodes in layer $i$ are taken as the inputs of the nodes in layer $i+1$
and then transformed into the new outputs (of the nodes in layer $i+1$) via
${\bf f}_{j}^{(i)}(\cdot)$ and matrix of weights,
$W^{(i)}\in{\mathbb{R}}^{d_{i}\times d_{i+1}}$. Setting ${\bf
d}=[d_{1},d_{2},\dots,d_{L}]$ (with $d_{1}=n$ and $d_{L}=1$) and denoting by
${\bf b}^{(i)}\in{\mathbb{R}}^{d_{i+1}}$ the so-called activation thresholds
vectors and by ${\bf x}^{(i)}\in{\mathbb{R}}^{d_{i}}$ and ${\bf
x}^{(i+1)}\in{\mathbb{R}}^{d_{i+1}}$ the inputs and outputs of the neurons in
layer $i$, one has the following:

Mathematical formalism of NN with architecture $A({\bf d}\text{; }{\bf
f}^{(i)})$: $\mbox{{input:}}\triangleq{\bf x}^{(1)}\quad\longrightarrow$ ${\bf
x}^{(i+1)}={\bf f}^{(i)}(W^{(i)}{\bf x}^{(i)}-{\bf b}^{(i)})$
$\longrightarrow\quad\mbox{{output:}}\triangleq{\bf x}^{(L+1)}$. (1)

Clearly, the network’s architecture, $A({\bf d};{\bf f}^{(i)})$, is fully
specified by the vectors ${\bf d}$ and ${\bf f}^{(i)}$ (we may on occasion
write $A({\bf d};{\bf f})$ instead of $A({\bf d};{\bf f}^{(i)})$ when ${\bf
f}^{(i)}$ are identical).

As is the case for the single neurons, one of the most fundamental features of
any neural net is their ability to properly store/memorize a large amount of
data. To see how the above formalism works in that regard, one can assume, for
example, the existence of $m$ data pairs $({\bf x}^{(0,k)},{\bf y}^{(0,k)})$,
$k\in\\{1,2,\dots,m\\}$, with ${\bf x}^{(0,k)}\in{\mathbb{R}}^{n}$ being the
$n$-dimensional data vectors and ${\bf y}^{(0,k)}\in{\mathbb{R}}$ being their
corresponding labels. Finding weight matrices $W^{(i)}$ such that

${\bf x}^{(1)}={\bf x}^{(0,k)}\quad\Longrightarrow\quad{\bf x}^{(L+1)}={\bf
y}^{(0,k)}\qquad\forall k,$ (2)

is then sufficient to relate given data vectors, ${\bf x}^{(0,k)}$, to their
associated labels, ${\bf y}^{(0,k)}$. The _memory capacity, $C(A({\bf d},{\bf
f}^{(i)}))$_ of the given architecture $A({\bf d},{\bf f}^{(i)})$ is then
defined as the largest sample size, $m$, such that (2) holds for any
collection of data pairs $({\bf x}^{(0,k)},{\bf y}^{(0,k)})$,
$k\in\\{1,2,\dots,m\\}$ with certain prescribed properties. Given the
relevance of the capacity in understanding the limits of NNs functioning,
determining its precise theoretical value (together with the development of
the corresponding computationally efficient algorithmic procedures that
achieve it), is of utmost importance. We below provide a collection of results
that enable full capacity characterization for many well known architectures
$A({\bf d};{\bf f}^{(i)})$.

We state below several technical and structural assumptions that facilitate
the presentation. As many of them are aligned with the ones discussed in [36,
40, 42], we avoid unnecessarily repeating them and instead opt for briefly
recalling on the most important ones. We, however, do place a particular
emphasis on those that substantially differ and are of particular relevance
for the considerations of main interest in this paper.

###  1.2 Assumptions related to architecture and data

As the assumptions that we rely on are rather common and prevalent in the
existing literature, we avoid discussing them in deep details and instead
focus on precisely stating them.

_Architecture assumptions:_ We consider _generic_ zero-threshold activation
functions in the hidden layer with the following properties: _(i)_ We take
$L=3$, ${\bf b}^{(i)}=0$, $W^{(1)}=I_{n\times n}$, and $W^{(3)}={\bf w}^{T}$,
where ${\bf w}\in{\mathbb{R}}^{d_{2}\times 1}$ (in other words, $W^{(3)}$ is a
$d_{2}$-dimensional row vector). _(ii)_ We set $d\triangleq d_{2}$ and
$\delta\triangleq\delta_{1}=\frac{d_{1}}{d_{2}}=\frac{n}{d}$. While we
ultimately consider $d\rightarrow\infty$ scenario, many of the presented
mathematical concepts hold for any even $d$. Along the same lines, whenever
$d$ is not emphasized as infinite, we assume that it is any given even natural
number. _(iii)_ _Identity_ neuronal functions, ${\bf f}^{(1)}({\bf
x}^{(1)})={\bf x}^{(1)}$, are considered in the first (artificial) layer. In
the hidden layer, we take _generic_ zero-threshold activations ${\bf
f}_{j}^{(2)}(\cdot):{\mathbb{R}}^{d_{2}}\rightarrow R$ with ${\bf
f}_{j}^{(2)}(\cdot)={\bf f}_{k}^{(2)}(\cdot)$ for any $j\neq k$. As typical
for the TCMs, at the output, the zero-threshold sign activations, ${\bf
f}^{(3)}(W^{(3)}{\bf x}^{(3)}-{\bf b}^{(3)})=\mbox{sign}\left(W^{(3)}{\bf
x}^{(3)}\right)$, are assumed. We denote this architecture by $A({\bf d};[{\bf
f}^{(1)},{\bf f}^{(2)},{\bf f}^{(3)}])=A({\bf d};[I,{\bf
f}^{(2)},\mbox{sign}])\triangleq A({\bf d};{\bf f}^{(2)})$. _(iv)_ The matrix
of the hidden layer weights, $W^{(2)}$, can be full or with a particular
sparse structure. Both options have been considered previously throughout the
literature. For example, a particular sparse structuring with the support of
$W^{(2)}$’s $j$-th row, $\mbox{supp}\left(W_{j,:}^{(2)}\right)$, satisfying
$\mbox{supp}\left(W_{j,:}^{(2)}\right)={\mathcal{S}}^{(j)}$, with
${\mathcal{S}}^{(j)}\triangleq\\{(j-1)\delta+1,(j-1)\delta+2,\dots,j\delta\\}$,
makes the above architecture correspond to the _treelike committee machines_
(TCM) which are of our main interest in this paper (alternatively, full
$W^{(2)}$ makes the architecture correspond to the _fully connected committee
machines_ (FCM)).

_Data assumptions:_ _(i)_ We assume the typical _binary_ labeling ${\bf
y}_{i}^{(0,k)}\in\\{-1,1\\}$ (in addition to being the most standard type of
labeling, it is also nicely complemented by the _sign_ neuronal choice at the
network’s output). _(ii)_ Data sets that are inseparable are not allowed.
This, for example, means that indistinguishable or contradictory pairs, such
as $({\bf x}^{(0,k)},{\bf y}^{(0,k)})$ and $({\bf x}^{(0,k)},-{\bf
y}^{(0,k)})$, can not appear. _(iii)_ We focus on statistical datasets and
particularly focus on ${\bf x}^{(0,k)}$ being comprised of iid standard
normals. This follows the trend established in the classical single perceptron
references (see, e.g., [12, 16, 29, 9, 49, 48, 47]) and is expected to allow
for a fairly universal statistical treatment. To provide universal capacity
upper bounds, it is, however, perfectly sufficient to consider any type of
data set (including even nonstatistical ones).

###  1.3 Contextualization within relevant prior work

Given that the problems of our interest are well known and have been studied
for longer than a half of century, the underlying related literature is rather
vast. As surveying all of it here is infeasible (and way better suited for
general review papers), we below focus on the results, which, in our view, are
the most relevant and closest to our own.

The first memory capacity considerations started with the spherical
perceptrons in the early sixties of the last century. A close connection to
several fundamental integral geometry problems was observed and the early
results were directly related to some of the classical
geometrical/probabilistic works (see, e.g., [26, 9, 47, 22]). The most famous
of them establishes that $C(A(1;\mbox{sign}))\rightarrow 2n$ as
$n\rightarrow\infty$, which effectively means that, in a large dimensional
statistical context, the spherical _sign_ perceptron capacity basically
_doubles the dimension_ of the data ambient space, $n$. After being initially
proven as a remarkable combinatorial geometry fact in [26, 9, 49, 48, 47, 8,
22], decades later, it was reproved in various forms in a host of different
fields ranging from machine learning and pattern recognition to probability
and information theory (see, e.g., [3, 45, 10, 28, 11, 12, 16, 29, 33]).

_Sign perceptrons hidden layer activations:_ Extending the single neuron
capacity results to the corresponding network ones is not easy. Particularly
scarce are results related to TCM NNs. On the other hand, a bit more is known
about the FCM ones, but a direct connection between the two is not very
apparent. For example, the FCM capacities trivially upper-bound the
corresponding TCM ones, but a way more appropriate appears to be viewing the
TCM capacities as roughly the FCM ones divided by $d$. An overwhelming
majority of the known capacity results are of the _scaling_ type and indicate
an unavoidable relation to the total number of the network weights,
$w=\sum_{i=1}^{L-1}d_{i}d_{i+1}$. For example, the famous VC-dimension
provides the upper-bounding scaling $O(w\log(w))$. For the NNs with 1-hidden
layer, one has $w=d_{1}d_{2}+d_{2}=(n+1)d$ for the FCM and $w=d_{1}+d_{2}=n+d$
for the TCM, which, for large $d_{i}$’s and huge $n$, gives the “ _division by
$d$_” FCM – TCM capacity relation. When it comes to the corresponding lower
bounding, [7] argued that the capacity of a shallow 3-layer net scales as
$O(nd)$. A bit stronger version was obtained recently in [46], where, for the
networks with more than three layers, the capacity was shown to scale at least
as $O(w)$.

_Scaling versus non-scaling:_ Obtaining the capacity results that are precise
and of the _non-scaling_ type is a much harder challenge. Given the simplicity
and elegance of the single spherical perceptron capacity, this initially might
seem as a bit surprising. However, after recognizing that several decades of a
strong effort did not produce much of the analytical progress, the level of
difficulty becomes clearer. In fact, after [15] provided simple multi-
perceptron extension of the combinatorial considerations of [9, 49, 48, 47, 8,
22], the progresses completely stalled until the very recent appearance of
[40, 36, 42]. Relying on the Random duality theory (RDT), [36] developed a
generic framework for the analysis of TCM networks and obtained strong
capacity upper bounds for any given (odd) number of the hidden layer neurons.
[40] went then a bit further, utilized a partially lifted (pl) RDT variant and
substantially lowered the bounds proven in [36].

_Different hidden layer activations:_ The above discussion highlighted the
analytical hardness as the first of the two key obstacles one typically faces
when trying to transition from the single to multi neuron architectures. The
second one is of the algorithmic type and relates to the _sign_ perceptrons
being noncontinuous functions. Namely, it is usually not very easy to design
computationally provably efficient network training strategies for such
objects. This amplifies the need for potentially less simple but easier to use
activation factions. Since the discreteness is usually perceived as the main
source of the sign perceptrons analytical and algorithmic hardness,
consideration of continuous activations positions itself as a promising
alternative. Many of such activations have already found their place in
various NN architectures, include the ReLU, quadratic, tanh, erf and so on. As
things are, at least, algorithmically a bit more favorable when such
activations are in place, a little bit more is known regarding their
capacities as well. For example, [51] first suggested for deep nets, and [20]
later on proved for 4-layer nets, that the capacity is at least $O(w)$ for
sigmoids. [54, 19] then showed similar results for ReLU while keeping an
additional number of nodes restriction which was later on removed in [52] for
both tanh and ReLU. After [40, 36] first introduced a generic framework for
precise _non-scaling_ capacity analysis of the _sign_ hidden layer
activations, [42] extended the framework so that it can handle various
different activations. It then particularly focused on three types of
activations, linear, quadratic, and ReLU. For the linear, [42] determined the
exact value of the capacity and showed that, for _any_ width (the number of
the hidden layer neurons), it matches the corresponding one of the single
spherical perceptron. On the other hand, for the quadratic and ReLU, it
obtained the plain and the pl RDT capacity upper bounds. All considerations
from [40, 36, 42] were done for the networks with any given (even) number of
hidden layer neurons, $d$.

_Statistical physics – Replica methods:_ Notorious difficulty that moving from
the _scaling_ (say, of the $O(\cdot)$ type) to the _precise_ capacity
descriptions imposes was already recognized in the early eighties of the last
century. As at that time there were no available powerful mathematical
techniques that could handle such a move, statistical physics replica methods
positioned themselves as an excellent (and basically only known) alternative.
Despite their analytical non-rigorousness, they produce expectedly _precise_
final results. The foundational replica concepts within the analysis of the NN
capacities were laid out in the pioneering works [17, 16], where various
single perceptron forms were discussed. Utilizing those concepts, a few years
later, [14, 5] studied the same TCM architecture that we study here (as well
as the related FCM one). Considering the sign activations, and the so-called
replica symmetry formalism, they obtained the capacity predictions for any
number of the neurons in the hidden layer, $d$. They also established the
corresponding large $d$ scaling behavior. Each of these results was proven as
mathematically rigorous capacity upper bound, the first one in [36] and the
second one in [40]. [14, 5], however, went a step further and showed that
their replica symmetry large $d$ predictions violate the mathematically
rigorous ones of [15]. To remedy such a contradiction, [14, 5] then proceeded
by studying the first level of replica symmetry breaking (rsb) and showing
that it lowers the capacity. For both the committee and the so-called parity
machines (PM), relevant large $d$ scaling rsb considerations were presented in
[24] as well (for earlier PM related replica considerations see also, e.g.,
[6, 4]). On the other hand, for the FCM architecture, [44, 50] obtained a bit
later the large $d$ scaling that matches the upper-bounding one of [15]. Of
particular relevance, however, to our work are two very recent lines of work
[2, 53] where the _wide_ hidden layer TCM architectures were considered. In
[2] the 1rsb capacity predictions for the ReLU activations were obtained. A
bit later, [53] moved things further and obtained analogous 1rsb predictions
for several other activations, including the linear, ReLU, quadratic, erf, and
tanh among others.

_Practical achievability:_ We also mention another line of work that attracted
a strong interest over the last several years. It relates to the design and
analysis of the efficient network training algorithms that could potentially
approach the capacity. After it was empirically observed that the simple
gradient based methods perform reasonably well in this context while requiring
only the so-called mild over-parametrization (moderately larger number of free
parameters, $w$, compared to the data set size, $m$), a lot of effort was put
in providing theoretical justifications of such a phenomenon. More on a solid
progress made in these directions in recent years can be found in, e.g., [13,
18, 1, 21, 23, 25, 43, 27, 55]. While these results are mostly oriented
towards the FCMs, they are also extendable to the TCMs as well.

####  1.3.1 Contributions

The _precise_ analytical characterization of the so-called $n$-_scaled_ memory
capacity of the TCM NNs with generic neuronal activations, ${\bf f}^{(2)}$, in
the _wide_ hidden layer is the main object of our study. In other words, we
are interested in determining

$\alpha_{c}(\infty;{\bf
f}^{(2)})\triangleq\lim_{d\rightarrow\infty}\alpha_{c}(d;{\bf
f}^{(2)})\triangleq\lim_{d\rightarrow\infty}\lim_{n\rightarrow\infty}\frac{C(A([n,d,1];{\bf
f}^{(2)}))}{n},$ (3)

where we often for brevity instead of $\alpha_{c}(\infty;{\bf f}^{(2)})$ write
just $\alpha_{c}(\infty)$. The generic framework for the analysis of sign
activations, established in[36, 40] (relying on the RDT and pl RDt
principles), was extended to various different activations in [42]. While the
framework works for any given even number of hidden layer neurons, it also
heavily relies on the underlying numerical evaluations. We, here consider
_wide_ hidden layers ($d\rightarrow\infty$), and uncover that a significant
portions of numerical difficulties miraculously disappears.

_A summary of the key results:_ _(i)_ Relying on [39], we establish _fully
lifted_ (fl) RDT, based framework for the capacity analysis of _wide_ hidden
layer TCM NNs with generic activations. _(ii)_ For several particular
activations, ReLU, quadratic, erf, and tanh, we then obtain explicit
$d\rightarrow\infty$ closed form capacity characterizations. _(iii)_ While we
uncover that, compared to [42], a significant amount of required numerical
work disappears, to have the obtained capacity characterizations become
practically operational, a substantial amount of the residual numerical work
is still needed. For all the considered activations, we successfully conduct
the needed numerical evaluations and obtain the concrete capacity values as
well. _(iv)_ We observe a rather rapid convergence of the lifting mechanism
with the relative improvement no better than $\sim 0.1\%$ achieved already on
the third level of full lifting. Moreover, we uncover that the first and
second level of lifting characterizations match the ones obtained through the
replica symmetry and 1rsb analyses in [53] for a spectrum of different
activations and in [2] for the ReLU activation. Some of the concrete estimates
are also shown in Table 1. The results from Table 1 are additionally
complemented with their visual representations in Figure 1. Both, the strong
effect/benefit of the fl lifted RDT as well as its a rapid convergence are
rather obvious.

Table 1: _Wide_ treelike net capacity – lifting mechanism progress for different activations; $d\rightarrow\infty$; $n\rightarrow\infty$ Memory capacity | Activation
---|---
($r$ – lifting level) | ReLU | Quad | erf | tanh
$\alpha_{c}^{(1,f)}(\infty)$ ($1$-sfl RDT) | $\quad\mathbf{2.9339}\quad$ | $\quad\mathbf{4}\quad$ | $\quad\mathbf{2.4514}\quad$ | $\quad\mathbf{2.3556}\quad$
$\alpha_{c}^{(2,f)}(\infty)$ ($2$-sfl RDT) | $\mathbf{2.6643}$ | $\mathbf{3.3750}$ | $\mathbf{2.3750}$ | $\mathbf{2.3063}$
$\alpha_{c}^{(3,f)}(\infty)$ ($3$-sfl RDT) | $\mathbf{2.6534}$ | $\mathbf{3.3669}$ | $\mathbf{2.3744}$ | $\mathbf{2.3058}$

Figure 1: Memory capacity – treelike nets with $d\rightarrow\infty$ hidden
layer neurons; different activations

##  2 Mathematical formalism of network functioning

To ensure the easiness of writing and overall presentation, we set
$W\triangleq W^{(2)}$, recall on $W^{(1)}=I$ and $W^{(3)}={\bf w}^{T}$, and
write for any $k\in\\{1,2,\dots,m\\}$

${\bf x}^{(1)}={\bf x}^{(0,k)}\quad\Longrightarrow\quad{\bf x}^{(2)}={\bf
f}^{(1)}(W^{(1)}{\bf x}^{(1)})={\bf f}^{(1)}({\bf x}^{(1)})={\bf x}^{(1)}={\bf
x}^{(0,k)},$ (4)

and

${\bf x}^{(2)}={\bf x}^{(0,k)}\quad\Longrightarrow\quad{\bf x}^{(3)}={\bf
f}^{(2)}(W^{(2)}{\bf x}^{(2)})={\bf f}^{(2)}(W{\bf x}^{(0,k)}),$ (5)

and

${\bf x}^{(3)}={\bf f}^{(2)}(W{\bf x}^{(0,k)})\quad\Longrightarrow\quad{\bf
x}^{(4)}={\bf f}^{(3)}(W^{(3)}{\bf x}^{(3)})={\bf f}^{(3)}({\bf w}^{T}{\bf
x}^{(3)})=\mbox{sign}({\bf w}^{T}{\bf f}^{(2)}(W{\bf x}^{(0,k)})).$ (6)

After connecting beginning in (4) and end in (6), one obtains the following
explicit relation between the network’s input and output

${\bf x}^{(1)}={\bf x}^{(0,k)}\quad\Longrightarrow\quad{\bf
x}^{(4)}=\mbox{sign}({\bf w}^{T}{\bf f}^{(2)}(W{\bf x}^{(0,k)})).$ (7)

The necessary and sufficient condition for network to operate properly, is
then the following

${\bf y}^{(0,k)}=\mbox{sign}({\bf w}^{T}{\bf f}^{(2)}(W{\bf x}^{(0,k)})).$ (8)

Moreover, after setting

${\bf y}\triangleq\begin{bmatrix}{\bf y}^{(0,1)}&{\bf y}^{(0,2)}&\dots&{\bf
y}^{(0,m)}\end{bmatrix}^{T}\qquad\mbox{and}\qquad
X\triangleq\begin{bmatrix}{\bf x}^{(0,1)}&{\bf x}^{(0,2)}&\dots&{\bf
x}^{(0,m)}\end{bmatrix}^{T},$ (9)

it is not that difficult to see that (8) can be rewritten in generic matrix
form as

$\left(\exists W\in{\mathbb{R}}^{d\times n}|\|{\bf y}^{T}-\mbox{sign}({\bf
w}^{T}{\bf
f}^{(2)}(WX^{T}))\|_{2}=0\right)\quad\Longleftrightarrow\quad\left(\left(X,{\bf
y}\right)\mbox{is memorized}\right),$ (10)

where the $k$-th data pair, $\left({\bf x}^{(0,k)},{\bf y}^{(0,k)}\right)$,
are the $k$-th row of $m\times n$ matrix $X$ and the $k$-th element of
$m\times 1$ column vector ${\bf y}$. One then has the following (alternative
to (10)):

Algebraic memorization characterization of the ${\bf f}^{(2)}$-activated
hidden layer TCMs: $\displaystyle 0=\xi\triangleq\min_{W,Q}$
$\displaystyle\|{\bf y}-\mbox{sign}({\bf f}^{(2)}(Q){\bf w})\|_{2}$ subject to
$\displaystyle XW^{T}=Q$ (11) $\Longleftrightarrow$ Data set $\left(X,{\bf
y}\right)$ is properly memorized.

As it will soon be clear, the above is the key mathematical problem on the
path towards characterizing the network memorization capabilities. We find it
useful for what follows to slightly reformulate the above optimization. To
that end we first observe that it can be rewritten as

$\displaystyle\xi=\min_{Z,Q}$ $\displaystyle\|{\bf y}-\mbox{sign}({\bf
f}^{(2)}(Q){\bf w})\|_{2}$ subject to $\displaystyle XZ=Q,$ (12)

where cosmetic change, $Z=W^{T}$, is only for facilitating overall writing. We
continue the trend of [40, 36, 42] and consider the TCM architecture, with a
sparse $Z$ that ensures the _treelike_ architecture. In other words, we
consider $Z$ with the only nonzero elements in the $j$-th column are in the
rows from the following set
${\mathcal{S}}^{(j)}\triangleq\\{(j-1)\delta+1,(j-1)\delta+2,\dots,j\delta\\}$.
Keeping in mind this $Z$ specialization and the insensitiveness of (2) with
respect to the $Z$ or $Q$ scalings, one can further write

$\displaystyle\xi=\min_{Z,Q}$ $\displaystyle\|{\bf 1}-\mbox{sign}({\bf
f}^{(2)}(Q){\bf w})\|_{2}$ subject to $\displaystyle XZ=Q$ (13)
$\displaystyle\|Z_{:,j}\|_{2}=1$
$\displaystyle\mbox{supp}(Z_{:,j})={\mathcal{S}}^{(j)},1\leq j\leq d,$

with $Z_{:,j}$ being the $j$-th column of $Z$ and $\|Z_{:,j}\|_{2}$ its
Euclidean norm. A bit of additional cosmetic rewriting of (2) gives

$\displaystyle\xi=\min_{{\bf z}^{(j)},Q}$ $\displaystyle\|{\bf
1}-\mbox{sign}({\bf f}^{(2)}(Q){\bf w})\|_{2}$ subject to $\displaystyle
X^{(j)}{\bf z}^{(j)}=Q_{:,j},1\leq j\leq d,$ (14) $\displaystyle\|{\bf
z}^{(j)}\|_{2}=1$ $\displaystyle{\bf
z}^{(j)}\in{\mathbb{R}}^{\delta},Q\in{\mathbb{R}}^{m\times d},$

where $X^{(j)}=X_{:,{\mathcal{S}}^{(j)}}\in{\mathbb{R}}^{m\times\delta}$. As
emphasized earlier, we consider statistical data sets with elements of $X$
being iid standard normals, which, due to rotational symmetry and without loss
of generality, allows to take all the elements of ${\bf y}$ equal to 1. For
short, in what follows, we therefore take ${\bf y}={\bf 1}$ (where ${\bf 1}$
is the all ones column vector of appropriate dimensions). Keeping this in
mind, the following lemma, taken from [42], provides a precise resulting
optimization representation of the network memorization property. It is in
fact structurally a mirrored analogue to Lemma 1 from [36].

######  Lemma 1.

([42] Algebraic optimization representation) Assume a 1-hidden layer TCM with
architecture $A([n,d,1];{\bf f}^{(2)})$. Any given data set $\left({\bf
x}^{(0,k)},1\right)_{k=1:m}$ can not be properly memorized by the network if

$f_{rp}(X)>0,$ (15)

where

$f_{rp}(X)\triangleq\frac{1}{\sqrt{n}}\min_{\|{\bf
z}^{(j)}\|_{2}=1,Q}\max_{\Lambda\in{\mathbb{R}}^{m\times d}}\|{\bf
1}-\mbox{\emph{sign}}({\bf f}^{(2)}(Q){\bf
w})\|_{2}+\sum_{j=1}^{d}(\Lambda_{:,j})^{T}X^{(j)}{\bf z}^{(j)}-{\rm
tr}\,(\Lambda^{T}Q),$ (16)

and $X\triangleq\begin{bmatrix}{\bf x}^{(0,1)}&{\bf x}^{(0,2)}&\dots&{\bf
x}^{(0,m)}\end{bmatrix}^{T}$.

###### Proof.

Immediate consequence of Lemma 1 in [36]. ∎

Throughout the rest of the paper we consider mathematically the most
challenging, so-called _linear_ , regime with

$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}.$ (17)

###  2.1 Connecting network functioning and (partially reciprocal) _free
energy_

_Free energies_ are well known and almost unavoidable objects in many
statistical physics considerations. Here, we view them as purely mathematical
objects. We below give a bit of a preview related to the importance of these
objects in studying neural networks capacities. To introduce their
mathematical representation relevant to the problems of our interest here, we
start by defining the following, so-called, _bilinearly summed Hamiltonian_

${\cal H}_{sq}(G^{(j_{w})})=\sum_{j_{w}=1}^{d}\left({\bf
y}^{(j_{w})}\right)^{T}G^{(j_{w})}{\bf x}^{(j_{w})},$ (18)

and its, so to say, _partially reciprocal_ partition function

$Z_{sq}(\beta,G^{(j_{w})})=\sum_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})}}\left(\sum_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})}}e^{\beta{\cal
H}_{sq}(G^{(j_{w})})}\right)^{-1}.$ (19)

It is important to note right here at the beginning that for $d=1$ one gets
the usual _bilinear_ Hamiltonian. Indexing and summing over $j_{w}$ will
effectively correspond to the extension of the width of the hidden layer – the
key component of the considered network architecture. For starters, we take
${\mathcal{X}}^{(j_{w})}$ and ${\mathcal{Y}}^{(j_{w})}$ in (19) as general
sets. Later on, throughout the presentation, we make the necessary
specializations. One also notes that the inner summation factors in in a
reciprocal fashion making the overall partition function appear as seemingly
different from the typically seen counterparts in the statistical physics
literature. The thermodynamic limit of the average of such “ _partially
reciprocal_ ” free energy is then

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

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

$\displaystyle
f_{sq}(\infty)\triangleq\lim_{\beta\rightarrow\infty}f_{sq}(\beta)$
$\displaystyle=$
$\displaystyle\lim_{\beta,n\rightarrow\infty}\frac{{\mathbb{E}}_{G^{(j_{w})}}\log{(Z_{sq}(\beta,G^{(j_{w})})})}{\beta\sqrt{n}}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G^{(j_{w})}}\max_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})}}-\max_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})}}\sum_{j_{w}=1}^{d}\left({\bf
y}^{(j_{w})}\right)^{T}G^{(j_{w})}{\bf x}^{(j_{w})}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle-\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G^{(j_{w})}}\min_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})}}\max_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})}}\sum_{j_{w}=1}^{d}\left({\bf
y}^{(j_{w})}\right)^{T}G^{(j_{w})}{\bf x}^{(j_{w})}}{\sqrt{n}}.$

One can then also trivially rewrite (LABEL:eq:limlogpartfunsqrta0) as

$\displaystyle-f_{sq}(\infty)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{G^{(j_{w})}}\min_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})}}\max_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})}}\sum_{j_{w}=1}^{d}\left({\bf
y}^{(j_{w})}\right)^{T}G^{(j_{w})}{\bf x}^{(j_{w})}}{\sqrt{n}}.$ (22)

Connecting $j$ to $j_{w}$, $X^{(j)}$ to $G^{(j_{w})}$, $\Lambda_{:,j}$ to
${\bf y}^{(j_{w})}$, and ${\bf z}^{(j)}$ to ${\bf x}^{(j_{w})}$ hints that the
network functioning may indeed be related to the above introduced partially
reciprocal free energy. However, quite a few of additional preliminaries need
to be addressed before one can definitely make such a connection. One
particular thing from (22) should be kept in mind for later on though. Namely,
while the connection between $f_{rp}(X)$ and $f_{sq}(\infty)$ seems apparent,
direct studying of $f_{sq}(\infty)$ might not be very easy. Somewhat
paradoxically, we may instead find it as more beneficial to first study
$f_{sq}(\beta)$ for a general $\beta$ and then to eventually specialize the
obtained results to the above mentioned ground state,
$\beta\rightarrow\infty$, regime. As the analysis will be rather heavy, we may
also, in the interest of easing the exposition, on occasion neglect some terms
which are of no importance in the ground state considerations.

The above hints at the potential role that the free energies can play in
studying the networks capacities. Still, to be able to fully exploit such a
potential connection, one would need to develop a mechanism to study the free
energies themselves. Such a mechanism is precisely what we discuss next.

##  3 Network memorization through the prism of sfl RDT

To ensure a smooth and proper connection between the network functioning and
the sfl RDT, we find it convenient to first revisit some of the sfl RDT
basics.

###  3.1 Basics of sfl RDT

To make writing easier and initial considerations a bit smoother, we, for time
being, take $d=1$, which allows to ignore all $j_{w}$ indexing. One of the key
observations that enables pretty much everything that follows is then the
recognition that a slightly changed variant of the (partially reciprocal) free
energy from (20),

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

is a function of _bilinearly indexed_ (bli) random process ${\bf y}^{T}G{\bf
x}$. Precisely this very recognition is exactly that allows us to establish a
direct connection between $f_{sq}(\beta)$ and the bli related results from
[34, 38, 39]. To that end, we closely follow [41, 35] and start with several
technical definitions. We consider $r\in{\mathbb{N}}$,
$k\in\\{1,2,\dots,r+1\\}$, real scalars $s$, $x$, and $y$ that satisfy
$s^{2}=1$, $x>0$, and $y>0$, sets ${\mathcal{X}}\subseteq{\mathbb{R}}^{n}$ and
${\mathcal{Y}}\subseteq{\mathbb{R}}^{m}$, function
$f_{S}(\cdot):{\mathbb{R}}^{n+m}\rightarrow R$, 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)

and ${\bf c}_{0}=1$, ${\bf c}_{r+1}=0$. For
${\mathcal{U}}_{k}\triangleq[u^{(4,k)},{\bf u}^{(2,k)},{\bf h}^{(k)}]$ such
that the components of $u^{(4,k)}\in{\mathbb{R}}$, ${\bf
u}^{(2,k)}\in{\mathbb{R}}^{m}$, and ${\bf h}^{(k)}\in{\mathbb{R}}^{n}$ are
i.i.d. standard normals, we 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)

Equipped with all the above, we are in position to recall on the following
theorem – clearly, one of the sfl RDT’s fundamental components.

######  Theorem 1.

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

$\displaystyle\psi_{rp}$ $\displaystyle\triangleq-\max_{{\bf
x}\in{\mathcal{X}}}s\max_{{\bf y}\in{\mathcal{Y}}}\left(f({\bf x},{\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}$
$\displaystyle\quad-\psi_{S,\infty}(f({\bf x},{\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.1)-(3.1).

###### Proof.

The $s=-1$ scenario follows immediately from the corresponding one proven in
[39] after a trivial change $f({\bf x})\rightarrow f({\bf x},{\bf y})$. On the
other hand, the $s=1$ scenario, follows after trivial line-by-line repetitions
of the arguments from Section 3 of [39] with $s=-1$ replaced by $s=1$ and
$f({\bf x})$ replaced by $f({\bf x},{\bf y})$. ∎

The above theorem has a very generic character and holds for any given sets
${\mathcal{X}}$ and ${\mathcal{Y}}$. Of our interest here is its a $d$-fold
summing extension and specialization to particular sets analogues
${\mathcal{X}}^{(j_{w})}$ and ${\mathcal{Y}}^{(j_{w})}$,
$j_{w}\in\\{1,2,\dots,d\\}$. The following corollary contains such a fully
operational extension.

######  Corollary 1.

Assume the setup of Theorem 1. For $d>0$ and $j_{w}\in\\{1,2,\dots,d\\}$, let
the elements of $G^{(j_{w})}\in{\mathbb{R}}^{m\times n}$ be i.i.d. standard
normals. Let ${\mathcal{X}}^{(j_{w})}\subseteq{\mathbb{R}}^{n}$,
${\mathcal{Y}}^{(j_{w})}\subseteq{\mathbb{R}}^{m}$ be $2d$ given sets and let
${\mathcal{Q}}\in{\mathbb{R}}^{l}$ be another given set. Also, let $f({\bf
x}^{(j_{w})},{\bf
y}^{(j_{w})},Q):{\mathbb{R}}^{d(n+m)+l}\rightarrow{\mathbb{R}}$ and
${\mathcal{U}}_{k}^{(j_{w})}\triangleq[u^{(4,k,j_{w})},{\bf
u}^{(2,k,j_{w})},{\bf h}^{(k,j_{w})}]$ with the components of
$u^{(4,k,j_{w})}\in{\mathbb{R}}$, ${\bf u}^{(2,k,j_{w})}\in{\mathbb{R}}^{m}$,
and ${\bf h}^{(k,j_{w})}\in{\mathbb{R}}^{n}$ being i.i.d. standard normals.
Set

$\psi_{S,\infty}^{(d)}(f_{S},{\cal X}^{(j_{w})},{\cal Y}^{(j_{w})},{\bf
p},{\bf q},{\bf
c},x^{(j_{w})},y^{(j_{w})},s)={\mathbb{E}}_{G^{(j_{w})},{\mathcal{U}}_{r+1}^{(j_{w})}}\frac{1}{n{\bf
c}_{r}}\\\
\times\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}^{(j_{w})}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\left(\left(Z_{S,\infty}^{(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),$ (30)

where

$\displaystyle Z_{S,\infty}^{(d)}$ $\displaystyle\triangleq$ $\displaystyle
e^{D_{0,S,\infty}^{(d)}}$ $\displaystyle D_{0,S,\infty}^{(d)}$
$\displaystyle\triangleq$ $\displaystyle\max_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})},\|{\bf
x}^{(j_{w})}\|_{2}=x^{(j_{w})},Q\in{\mathcal{Q}}}s\max_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})},\|{\bf
y}^{(j_{w})}\|_{2}=y^{(j_{w})}}\left(\sqrt{n}f_{S}+{\mathcal{D}}_{1}+{\mathcal{D}}_{2}\right)$
$\displaystyle{\mathcal{D}}_{1}$ $\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}y^{(j_{w})}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right)^{T}{\bf x}^{(j_{w})}$ $\displaystyle{\mathcal{D}}_{2}$
$\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}x^{(j_{w})}\left({\bf
y}^{(j_{w})}\right)^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\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}}.$ (31)

Set

$\psi_{rp}^{(d)}\triangleq-\max_{{\bf
x}^{(j_{w})}\in{\mathcal{X}}^{(j_{w})},Q\in{\mathcal{Q}}}s\max_{{\bf
y}^{(j_{w})}\in{\mathcal{Y}}^{(j_{w})}}\left(f({\bf x}^{(j_{w})},{\bf
y}^{(j_{w})},Q)+\sum_{j_{w}=1}^{d}\left({\bf
y}^{(j_{w})}\right)^{T}G^{(j_{w})}{\bf
x}^{(j_{w})}\right),\quad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{random
primal}})}$ (32)

and

$\psi_{rd}^{(d)}({\bf p},{\bf q},{\bf
c},x^{(j_{w})},y^{(j_{w})},s)\triangleq\frac{\sum_{j_{w}=1}^{d}\left(x^{(j_{w})}\right)^{2}\left(y^{(j_{w})}\right)^{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}^{(d)}(f({\bf x}^{(j_{w})},{\bf y}^{(j_{w})},Q),{\cal
X}^{(j_{w})},{\cal Y}^{(j_{w})},{\bf p},{\bf q},{\bf
c},x^{(j_{w})},y^{(j_{w})},s)\qquad\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{fl
random dual}})}.\\\ $ (33)

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^{(j_{w})},y^{(j_{w})})$, $\hat{{\bf
q}}\triangleq\hat{{\bf q}}(x^{(j_{w})},y^{(j_{w})})$, and $\hat{{\bf
c}}\triangleq\hat{{\bf c}}(x^{(j_{w})},y^{(j_{w})})$ be the solutions of the
following system

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

Then,

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

###### Proof.

Follows as a $d$-fold application of Theorem 1 in the same manner Theorem 1 of
[36] follows in the plain RDT case. ∎

###  3.2 Fitting memorization into the sfl RDT machinery

The following corollary enables fitting the analysis of the network
memorization problem into the sfl RDT framework.

######  Corollary 2.

Assume the setup of Theorem 1, Corollary 1, and Lemma 1. Set

$\psi_{S,\infty}^{(d)}(f_{S},\left({\mathbb{S}}^{n}\right)^{\times
d},{\mathbb{S}}^{dm},{\bf p},{\bf q},{\bf
c},1,\lambda^{(j_{w})},s)={\mathbb{E}}_{X^{(j_{w})},{\mathcal{U}}_{r+1}^{(j_{w})}}\frac{1}{n{\bf
c}_{r}}\\\
\times\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}^{(j_{w})}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\left(\left(Z_{S,\infty}^{(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),$ (36)

where

$\displaystyle Z_{S,\infty}^{(d)}$ $\displaystyle\triangleq$ $\displaystyle
e^{D_{0,S,\infty}^{(d)}}$ $\displaystyle D_{0,S,\infty}^{(d)}$
$\displaystyle\triangleq$ $\displaystyle\max_{\|{\bf
z}^{(j_{w})}\|_{2}=1,\phi(Q)=1}s\max_{\|\Lambda_{:,j_{w}}\|_{2}=\lambda^{(j_{w})},\|\lambda^{(j_{w})}\|_{2}=1}\left(\sqrt{n}f_{S}+{\mathcal{D}}_{1}+{\mathcal{D}}_{2}\right)$
$\displaystyle{\mathcal{D}}_{1}$ $\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}\lambda^{(j_{w})}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right)^{T}{\bf z}^{(j_{w})}$ $\displaystyle{\mathcal{D}}_{2}$
$\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}\left(\Lambda_{:,j_{w}}\right)^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right)$ $\displaystyle\phi(Q)$ $\displaystyle\triangleq$
$\displaystyle\|{\bf 1}-\mbox{\emph{sign}}({\bf f}^{(2)}(Q){\bf w})\|_{2}$
$\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}}.$ (37)

Set

$\displaystyle\psi_{rp}^{(d)}$ $\displaystyle\triangleq$
$\displaystyle-\max_{\|{\bf
z}^{(j_{w})}\|_{2}=1,\phi(Q)=1}s\max_{\|\Lambda_{:,j_{w}}\|_{2}=\lambda^{(j_{w})},\|\lambda^{(j_{w})}\|_{2}=1}\left(f(\Lambda,Q)+\sum_{j_{w}=1}^{d}\left(\Lambda_{:,j_{w}}\right)^{T}X^{(j_{w})}{\bf
z}^{(j_{w})}\right),$ (38) (random primal)

and

$\displaystyle\psi_{rd}^{(d)}({\bf p},{\bf q},{\bf c},1,\lambda^{(j_{w})},s)$
$\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}$
$\displaystyle-\psi_{S,\infty}^{(d)}(f(\Lambda,Q),\left({\mathbb{S}}^{n}\right)^{\times
d},{\mathbb{S}}^{dm},{\bf p},{\bf q},{\bf
c},1,\lambda^{(j_{w})},s)\qquad\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}}(1,\lambda^{(j_{w})})$, $\hat{{\bf
q}}\triangleq\hat{{\bf q}}(1,\lambda^{(j_{w})})$, and $\hat{{\bf
c}}\triangleq\hat{{\bf c}}(1,\lambda^{(j_{w})})$ be the solutions of the
following system

$\displaystyle\frac{d\psi_{rd}^{(d)}({\bf p},{\bf q},{\bf
c},1,\lambda^{(j_{w})},s)}{d{\bf p}}=0,\quad\frac{d\psi_{rd}^{(d)}({\bf
p},{\bf q},{\bf c},1,\lambda^{(j_{w})},s)}{d{\bf
q}}=0,\quad\frac{d\psi_{rd}^{(d)}({\bf p},{\bf q},{\bf
c},1,\lambda^{(j_{w})},s)}{d{\bf c}}=0.$ (40)

Then,

$\displaystyle\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{X^{(j_{w})}}\psi_{rp}^{(d)}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\max_{\lambda^{(j_{w})}>0}\lim_{n\rightarrow\infty}\psi_{rd}^{(d)}(\hat{{\bf
p}}(1,\lambda^{(j_{w})}),\hat{{\bf q}}(1,\lambda^{(j_{w})}),\hat{{\bf
c}}(1,\lambda^{(j_{w})}),1,\lambda^{(j_{w})},s)$ $\displaystyle\hskip
144.54pt\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
sfl random duality}})}.$

Moreover, for $s=-1$ and $f(\Lambda,Q)=-{\rm tr}\,(\Lambda^{T}Q)$ one has

$\displaystyle\psi_{rp}^{(d)}$ $\displaystyle\triangleq$
$\displaystyle\min_{\|{\bf
z}^{(j_{w})}\|_{2}=1,\phi(Q)=1}\max_{\|\Lambda_{:,j_{w}}\|_{2}=\lambda^{(j_{w})},\|\lambda^{(j_{w})}\|_{2}=1}\left(-{\rm
tr}\,(\Lambda^{T}Q)+\sum_{j_{w}=1}^{d}\left(\Lambda_{:,j_{w}}\right)^{T}X^{(j_{w})}{\bf
z}^{(j_{w})}\right),$ (42) (random primal)

and

$\displaystyle\phi_{0}=\lim_{n\rightarrow\infty}\frac{{\mathbb{E}}_{X^{(j_{w})}}\psi_{rp}^{(d)}}{\sqrt{n}}$
$\displaystyle=$
$\displaystyle\max_{\lambda^{(j_{w})}>0}\lim_{n\rightarrow\infty}\psi_{rd}^{(d)}(\hat{{\bf
p}}(1,\lambda^{(j_{w})}),\hat{{\bf q}}(1,\lambda^{(j_{w})}),\hat{{\bf
c}}(1,\lambda^{(j_{w})}),1,\lambda^{(j_{w})},-1)$ $\displaystyle\hskip
144.54pt\mbox{({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{strong
sfl random duality}})}.$

One then has

$\displaystyle(\phi_{0}>0)$ $\displaystyle\Longleftrightarrow$
$\displaystyle\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(f_{rp}(X)>0)\longrightarrow
1\right)\Longleftrightarrow\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(\psi_{rp}^{(d)}>0)\longrightarrow
1\right)$ (44) $\displaystyle\Longleftrightarrow$
$\displaystyle\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];{\bf
f}^{(2)})\quad\mbox{fails to memorize data set}\quad(X,{\bf
1}))\longrightarrow 1\right).$

###### Proof.

Follows immediately from Corollary 1 and Lemma 1 after first recognizing the
following connections:

$\displaystyle j\leftrightarrow j_{w},\quad X^{(j)}\leftrightarrow
G^{(j_{w})},\quad\Lambda_{:,j}\leftrightarrow{\bf y}^{(j_{w})},\quad{\bf
z}^{(j)}\leftrightarrow{\bf
x}^{(j_{w})},\quad{\mathcal{X}}\leftrightarrow{\mathbb{S}}^{n},$ (45)

and then observing that

$\displaystyle\|\Lambda\|_{F}=1\quad\Longleftrightarrow\quad\|\lambda^{(j_{w})}\|_{2}=\sum_{j_{w}=1}^{d}\left(\lambda^{(j_{w})}\right)^{2}=1\quad\Longleftrightarrow\quad{\mathcal{Y}}\times{\mathcal{Y}}\dots\times{\mathcal{Y}}={\mathbb{S}}^{dn},$
(46)

and that for $s=-1$, $\psi_{rp}^{(d)}$ from (42), and $f_{rp}(X)$ from (16)

$\displaystyle\sqrt{n}f_{rp}(X)=\psi_{rp}^{(d)}.$ (47)

∎

From the above corollary one then easily recognizes the relevance and
importance of $\psi_{rd}^{(d)}({\bf p},{\bf q},{\bf
c},1,\lambda^{(j_{w})},-1)$ from (2) and consequently of
$\psi_{S,\infty}^{(d)}(f(\Lambda,Q),\left({\mathbb{S}}^{n}\right)^{\times
d},{\mathbb{S}}^{dm},{\bf p},{\bf q},{\bf c},1,\lambda^{(j_{w})},-1)$ from
(36), and $D_{0,S,\infty}^{(d)}$ from (2). Rewriting $D_{0,S,\infty}^{(d)}$
for $s=-1$ and $f_{S}=f(\Lambda,Q)=-{\rm tr}\,(\Lambda^{T}Q)$ one obtains

$\displaystyle D_{0,S,\infty}^{(d)}$ $\displaystyle\triangleq$
$\displaystyle-\min_{\|{\bf
z}^{(j_{w})}\|_{2}=1,\phi(Q)=1}\max_{\|\Lambda_{:,j_{w}}\|_{2}=\lambda^{(j_{w})},\|\lambda^{(j_{w})}\|_{2}=1}\left(-\sqrt{n}{\rm
tr}\,(\Lambda^{T}Q)+{\mathcal{D}}_{1}+{\mathcal{D}}_{2}\right),$ (48)

with

$\displaystyle{\mathcal{D}}_{1}$ $\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}\lambda^{(j_{w})}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right)^{T}{\bf z}^{(j_{w})}$ $\displaystyle{\mathcal{D}}_{2}$
$\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sum_{j_{w}=1}^{d}\left(\Lambda_{:,j_{w}}\right)^{T}\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right).$ (49)

After optimizing over $\Lambda$ and ${\bf z}$, we find

$\displaystyle D_{0,S,\infty}^{(d)}$ $\displaystyle\triangleq$
$\displaystyle-\sqrt{n}\min_{\phi(Q)=1}\sqrt{a^{(f)}_{1}-2a^{(f)}_{2}+a^{(f)}_{3}},$
(50)

where

$\displaystyle a^{(f)}_{1}$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right)-Q_{:,j_{w}}\right\|_{2}^{2}$ $\displaystyle
a^{(f)}_{2}$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right)-Q_{:,j_{w}}\right\|_{2}\left\|\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right\|_{2}$ $\displaystyle a^{(f)}_{3}$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{d}\left\|\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right\|_{2}^{2}.$ (51)

Since by Cauchy-Schwartz

$\displaystyle a^{(f)}_{2}\leq a^{(f)}_{1}a^{(f)}_{3},$ (52)

one can then rewrite (50) as

$\displaystyle D_{0,S,\infty}^{(d)}$ $\displaystyle\leq$
$\displaystyle-\sqrt{n}\min_{\phi(Q)=1}\sqrt{a^{(f)}_{1}}-\sqrt{a^{(f)}_{3}}=D^{(net)}(d)+D^{(per)}(d),$
(53)

where

$\displaystyle D^{(net)}(d)$ $\displaystyle\triangleq$
$\displaystyle-\sqrt{n}\min_{\phi(Q)=1}\sqrt{\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right)-Q_{:,j_{w}}\right\|_{2}^{2}}$ $\displaystyle
D^{(per)}(d)$ $\displaystyle\triangleq$
$\displaystyle\sqrt{n}\sqrt{\sum_{j_{w}=1}^{d}\left\|\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right\|_{2}^{2}}.$ (54)

Utilizing the _square root trick_ introduced on numerous occasions in [31, 30,
33, 32], we further find

$\displaystyle D^{(per)}(d)$ $\displaystyle=$
$\displaystyle\sqrt{n}\sqrt{\sum_{j_{w}=1}^{d}\left\|\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right\|_{2}^{2}}=\sqrt{n}\min_{\gamma^{(p)}}\left(\frac{\sum_{j_{w}=1}^{d}\left\|\sum_{k=2}^{r+1}c_{k}{\bf
h}^{(k,j_{w})}\right\|_{2}^{2}}{4\gamma^{(p)}}+\gamma^{(p)}\right)$ (55)
$\displaystyle=$
$\displaystyle\sqrt{n}\min_{\gamma^{(p)}}\left(\frac{\sum_{i=1}^{\frac{n}{d}}\sum_{j_{w}=1}^{d}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}_{i}^{(k,j_{w})}\right)^{2}}{4\gamma^{(p)}}+\gamma^{(p)}\right).$

After introducing scaling $\gamma^{(p)}=\gamma^{(p)}_{sq}\sqrt{n}$, one can
rewrite (55) as

$\displaystyle D^{(per)}(s)$ $\displaystyle=$
$\displaystyle\sqrt{n}\min_{\gamma_{sq}^{(p)}}\left(\frac{\sum_{i=1}^{\frac{n}{d}}\sum_{j_{w}=1}^{d}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}_{i}^{(k,j_{w})}\right)^{2}}{4\gamma_{sq}^{(p)}\sqrt{n}}+\gamma_{sq}^{(p)}\sqrt{n}\right)$
$\displaystyle=$
$\displaystyle\min_{\gamma_{sq}^{(p)}}\left(\frac{\sum_{i=1}^{\frac{n}{d}}\sum_{j_{w}=1}^{d}\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}_{i}^{(k,j_{w})}\right)^{2}}{4\gamma_{sq}^{(p)}}+\gamma_{sq}^{(p)}n\right)$
$\displaystyle=$
$\displaystyle\min_{\gamma_{sq}^{(p)}}\left(\sum_{i=1}^{\frac{n}{d}}\sum_{j_{w}=1}^{d}D^{(per)}_{i,j_{w}}(c_{k})+\gamma_{sq}^{(p)}n\right),$
. (56)

where

$\displaystyle
D^{(per)}_{i,j_{w}}(c_{k})=\frac{\left(\sum_{k=2}^{r+1}c_{k}{\bf
h}_{i}^{(k,j_{w})}\right)^{2}}{4\gamma_{sq}^{(p)}}.$ (57)

After setting

$\phi_{i}(Q_{i,1:d})\triangleq\mbox{sign}({\bf f}^{(2)}(Q_{i,1:d}){\bf w}),$
(58)

another utilization of the _square root trick_ gives

$\displaystyle D^{(net)}(d)$ $\displaystyle\triangleq$
$\displaystyle-\sqrt{n}\min_{\phi(Q)=1}\sqrt{\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}^{(2,k,j_{w})}\right)-Q_{:,j_{w}}\right\|_{2}^{2}}$ (59) $\displaystyle=$
$\displaystyle-\sqrt{n}\sqrt{\min_{\phi(Q)=1}\sum_{j_{w}=1}^{d}\sum_{i=1}^{m}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right\|_{2}^{2}}$ $\displaystyle=$
$\displaystyle-\sqrt{n}\sqrt{\min_{\phi(Q)=1}\sum_{i=1}^{m}\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right\|_{2}^{2}}$ $\displaystyle=$
$\displaystyle-\sqrt{n}\sqrt{\sum_{i=1}^{m}\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j_{w}=1}^{d}\left\|\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right\|_{2}^{2}}$ $\displaystyle=$
$\displaystyle-\sqrt{n}\min_{\gamma}\left(\frac{\sum_{i=1}^{m}\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}}{4\gamma}+\gamma\right).$

After introducing scaling $\gamma=\gamma_{sq}\sqrt{n}$, (59) can further be
rewritten as

$\displaystyle D^{(net)}(d)$ $\displaystyle=$
$\displaystyle-\sqrt{n}\min_{\gamma_{sq}}\left(\frac{\sum_{i=1}^{m}\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}}{4\gamma_{sq}\sqrt{n}}+\gamma_{sq}\sqrt{n}\right)$
$\displaystyle=$
$\displaystyle-\min_{\gamma_{sq}}\left(\frac{\sum_{i=1}^{m}\min_{\phi_{i}(Q_{:,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}}{4\gamma_{sq}}+\gamma_{sq}n\right)$
$\displaystyle=$
$\displaystyle-\min_{\gamma_{sq}}\left(\sum_{i=1}^{m}D_{i}^{(net)}(b_{k})+\gamma_{sq}n\right),$

with

$\displaystyle
D_{i}^{(net)}(b_{k})=\frac{\min_{\phi_{i}(Q_{:,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}}{4\gamma_{sq}}.$ (61)

We summarize the above discussion into the following theorem.

######  Theorem 2.

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

$\displaystyle\varphi(D,{\bf c})$ $\displaystyle\triangleq$
$\displaystyle{\mathbb{E}}_{{\mathcal{U}}_{r+1}^{(j_{w})}}\frac{1}{{\bf
c}_{r}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{r}^{(j_{w})}}\left(\dots\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left(\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\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}^{(d)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\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}$
$\displaystyle-\gamma_{sq}^{(p)}-\varphi(D_{1,1}^{(per)}(c_{k}({\bf p},{\bf
q})),{\bf c})+\gamma_{sq}-\alpha\varphi(-D_{1}^{(net)}(b_{k}({\bf p},{\bf
q})),{\bf c}),$

where $D_{1,1}^{(per)}(c_{k}({\bf p},{\bf q}))$ and $D_{1}^{(net)}(b_{k}({\bf
p},{\bf q}))$ are as in (57) and (61), 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\\}$) be the solutions
of the following system of equations

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

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}}.$ (65)

Then

$\displaystyle\bar{\psi}_{rd}^{(d)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})>0$
$\displaystyle\Longleftrightarrow\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(f_{rp}(X)>0)\longrightarrow
1\right)$
$\displaystyle\Longleftrightarrow\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];{\bf
f}^{(2)})\quad\mbox{fails to memorize data set}\quad(X,{\bf
1}))\longrightarrow 1\right).$

###### Proof.

Follows from the previous discussion, Lemma 1, Theorem 1, Corollaries 1 and 2,
the sfl RDT machinery presented in [38, 34, 39, 41], and after recognizing
that for $\phi_{0}$ and $\psi_{rd}^{(d)}(\hat{{\bf
p}}(1,\lambda^{(j_{w})}),\hat{{\bf q}}(1,\lambda^{(j_{w})}),\hat{{\bf
c}}(1,\lambda^{(j_{w})}),1,\lambda^{(j_{w})},-1)$ from (2) and
$\bar{\psi}_{rd}^{(d)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})$ from (LABEL:eq:thm2ta17) one,
based on (48)-(61), has

$\displaystyle\phi_{0}=\max_{\lambda^{(j_{w})}>0}\lim_{n\rightarrow\infty}\psi_{rd}^{(d)}(\hat{{\bf
p}}(1,\lambda^{(j_{w})}),\hat{{\bf q}}(1,\lambda^{(j_{w})}),\hat{{\bf
c}}(1,\lambda^{(j_{w})}),1,\lambda^{(j_{w})},-1)=\bar{\psi}_{rd}^{(d)}(\hat{{\bf
p}},\hat{{\bf q}},\hat{{\bf c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)}).$
(67)

The inequality in (53) is sufficient for the implication in
(LABEL:eq:thm2ta17). The equivalence follows since, due to symmetry and
concentrations, the inequality in (53) can actually be replaced by equality. ∎

##  4 Practical utilization and numerical evaluations

For the results of Theorem 2 to become practically useful, all the underlying
quantities need to be successfully evaluated. That, in general, is not an easy
task. A couple of obstacles might be particulary unsurpassable: _(i)_ It is
not clear a priori what is the correct value for $r$; and _(ii)_ The residual
decoupling over ${\bf y}$ is, in general, potentially highly non-convex. By a
complete miracle, it however turns out, that each of them can be successfully
surpassed. A majority of technical ingredients needed for the evaluations is
already present in the theorem itself. However, several additional aspects
will need to be addressed as well. These are, however, fairly specific and not
particularly convenient to be presented in a generic form. We therefore
discuss them as the presentation progresses within the context where their
relevance becomes important. As is usually the case with the fl RDT
considerations, the evaluations start with $r=1$ and proceed by increasing $r$
incrementally. This enhances the clarity and enables a systematic following of
the overall lifting mechanism’s progression. As a bonus, this, at the same
time, also allows to establish adequate connections with some of the known
results. Since we consider several different hidden layer activations, ${\bf
f}^{(2)}$, to ensure the easiness of the exposition and following, we try to
parallel the presentation of each of them with the remaining ones. Also, since
we will take as concrete examples some of the well known activations, it will
be possible to obtain corresponding concrete capacity numerical values.
Finally, several explicit analytical results can be obtained that
substantially simplify the evaluation process. These will be stated as the
presentation progresses below as well.

To facilitate writing and exposition, we set

$\displaystyle{\bf g}^{(k)}$ $\displaystyle\triangleq$
$\displaystyle\begin{bmatrix}{\bf u}_{i}^{(2,k,1)}&{\bf
u}_{i}^{(2,k,2)}&\dots&{\bf u}_{i}^{(2,k,d)}\end{bmatrix}^{T}$
$\displaystyle\bar{{\bf g}}^{(r+1)}$ $\displaystyle\triangleq$
$\displaystyle\left\\{{\bf g}^{(2)},{\bf g}^{(3)},\dots,{\bf
g}^{(r+1)}\right\\}$ $\displaystyle{\bf q}^{(net)}$ $\displaystyle\triangleq$
$\displaystyle\left(Q_{i,1:d}\right)^{T},$ (68)

and

$\displaystyle z_{i}^{(r)}(\bar{{\bf g}}^{(r+1)};{\bf f}^{(2)})$
$\displaystyle\triangleq$
$\displaystyle\min_{\phi_{i}(Q_{:,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}$ (69) $\displaystyle=$
$\displaystyle\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)-{\bf q}^{(net)}_{j_{w}}\right)^{2}.$

One then has

$\displaystyle D_{i}^{(net)}(b_{k})$ $\displaystyle=$
$\displaystyle\frac{\min_{\phi_{i}(Q_{:,1:d})=1}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
u}_{i}^{(2,k,j_{w})}\right)-Q_{i,j_{w}}\right)^{2}}{4\gamma_{sq}}$ (70)
$\displaystyle=$ $\displaystyle\frac{\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)-{\bf q}^{(net)}_{j_{w}}\right)^{2}}{4\gamma_{sq}}$
$\displaystyle=$ $\displaystyle\frac{z_{i}^{(r)}(\bar{{\bf g}}^{(r+1)};{\bf
f}^{(2)})}{4\gamma_{sq}}.$

###  4.1 ReLU activations

We start by considering the well known ReLU activation. In other words, we
assume that the neuronal activation functions in the hidden layer are

$\mbox{{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\emph{ReLU}}
activation:}}\hskip 72.26999pt{\bf f}^{(2)}({\bf x})=\max({\bf x},0).$ (71)

As stated earlier, we begin by considering the first level of lifting.

####  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}^{(d,1)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}{\bf
c}_{2}-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{{\bf
c}_{2}\frac{\left(\sqrt{1-0}{\bf
h}_{1}^{(2,1)}\right)^{2}}{4\gamma_{sq}^{(p)}}}\right)$
$\displaystyle+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left(\left(\sqrt{1-0}{\bf g}_{j_{w}}^{(2)}\right)-{\bf
q}^{(net)}_{j_{w}}\right)^{2}}{4\gamma_{sq}}}\right)$
$\displaystyle\rightarrow-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{2}}\log\left(1+{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}{\bf
c}_{2}\frac{\left(\sqrt{1-0}{\bf
h}_{1}^{(2,1)}\right)^{2}}{4\gamma_{sq}^{(p)}}\right)+\gamma_{sq}$
$\displaystyle\qquad-\alpha\frac{1}{{\bf
c}_{2}}\log\left(1-{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}{\bf
c}_{2}\frac{\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq 0}\sum_{j_{w}=1}^{d}\left({\bf
g}_{j_{w}}^{(2)}-{\bf q}^{(net)}_{j_{w}}\right)^{2}}{4\gamma_{sq}}\right)$
$\displaystyle\rightarrow-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{2}}\log\left(1+{\bf c}_{2}\frac{1}{4\gamma_{sq}^{(p)}}\right)$
$\displaystyle\qquad+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left(1-\frac{{\bf
c}_{2}}{4\gamma_{sq}}{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}\right)$
$\displaystyle\rightarrow-\gamma_{sq}^{(p)}-\frac{1}{4\gamma_{sq}^{(p)}}+\gamma_{sq}+\frac{\alpha}{4\gamma_{sq}}{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}.$ (72)

One then easily finds $\gamma_{sq}^{(p)}=\frac{1}{2}$ and
$\hat{\gamma}_{sq}=\frac{\sqrt{\alpha}}{2}\sqrt{{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}}$ and

$\displaystyle\bar{\psi}_{rd}^{(d,1)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})$
$\displaystyle=-1+\sqrt{\alpha}\sqrt{{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}}.$ (73)

To obtain the critical $\alpha_{c}^{(1)}$, we rely on condition
$\bar{\psi}_{rd}^{(d,1)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})=0$, which gives

$\displaystyle a_{c}^{(1)}(d)$ $\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\left(z_{i}^{(1)}\left({\bf
g}^{(2)};{\bf f}^{(2)}\left({\bf q}^{(net)}\right)\right)\right)}$ (74)
$\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}}$ $\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}_{{\bf g}^{(2)}}\min_{\left(\max\left({\bf
q}^{(net)},0\right)\right)^{T}{\bf w}\geq 0}\sum_{j_{w}=1}^{d}\left({\bf
g}_{j_{w}}^{(2)}-{\bf q}^{(net)}_{j_{w}}\right)^{2}}$ $\displaystyle=$
$\displaystyle\frac{1}{{\mathbb{E}}_{{\bf
g}^{(2)}}\left(z_{i}^{(1)}\left(\bar{{\bf g}}^{(2)};\max\left({\bf
q}^{(net)},0\right)\right)\right)}.$

As discussed in [42], solving the optimization in (74) is not an easy task in
general. For a couple of small (even) values of $d$ it was done analytically.
For larger values of $d$ the analytical solutions required additional
numerical simulations to complete the needed evaluations. Here, however, we
uncover that when $d$ is large, i.e. when $d\rightarrow\infty$, the numerical
evaluations miraculously sufficiently simplify so that they can ultimately be
done. For the simplicity of writing, we assume large even $d$ and, due to the
nonnegativity of ReLU,

${\bf w}=\begin{bmatrix}-{\bf 1}\\\ {\bf 1}\end{bmatrix},$ (75)

where ${\bf 1}$ is the $\frac{d}{2}$-dimensional vector of all ones.

To handle ${\mathbb{E}}_{{\bf g}^{(2)}}\left(z_{i}^{(1)}\left(\bar{{\bf
g}}^{(2)};{\bf f}^{(2)}\left({\bf q}^{(net)}\right)\right)\right)$, we start
by writing

$\displaystyle z_{i}^{(1)}\left(\bar{{\bf g}}^{(2)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)=\min_{q^{(net)}}$
$\displaystyle\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}$ subject to $\displaystyle{\bf
f}^{(2)}\left({\bf q}^{(net)}\right)^{T}{\bf w}\geq 0.$ (76)

After further writing the Lagrangian and utilizing the Lagrangian duality one
obtains

$z_{i}^{(1)}\left(\bar{{\bf g}}^{(2)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)=\min_{{\bf q}^{(net)}}\max_{\nu\geq
0}{\mathcal{L}}(\nu)\geq\max_{\nu\geq 0}\min_{{\bf
q}^{(net)}}{\mathcal{L}}(\nu),$ (77)

where

$\displaystyle{\mathcal{L}}(\nu)$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}-2\nu{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)^{T}{\bf w}=\left\|{\bf g}^{(2)}-{\bf
q}^{(net)}\right\|_{2}^{2}-2\nu{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)^{T}{\bf w}.$ (78)

Taking the derivative with respect to ${\bf q}^{(net)}$, we further find

$\displaystyle\frac{d{\mathcal{L}}(\nu)}{d{\bf q}^{(net)}}=-2\left({\bf
g}^{(2)}-{\bf q}^{(net)}\right)-2\nu\frac{d{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)}{d{\bf q}^{(net)}}\circ{\bf w},$ (79)

where $\circ$ stands for the component-wise multiplication. Equalling the
above derivative to zero gives

$\displaystyle{\bf q}^{(net)}={\bf g}^{(2)}+\nu\frac{d{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)}{d{\bf q}^{(net)}}\circ{\bf w}.$ (80)

Plugging this back into (78), one then finds

$\displaystyle{\mathcal{L}}(\nu)$ $\displaystyle=$
$\displaystyle\nu^{2}\left\|\frac{d{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)}{d{\bf q}^{(net)}}\circ{\bf w}\right\|_{2}^{2}-2\nu{\bf
f}^{(2)}\left({\bf q}^{(net)}\right)^{T}{\bf w}$ (81) $\displaystyle=$
$\displaystyle\nu^{2}\left\|\frac{d{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)}{d{\bf q}^{(net)}}\right\|_{2}^{2}-2\nu{\bf
f}^{(2)}\left({\bf q}^{(net)}\right)^{T}{\bf w},$

with ${\bf q}^{(net)}$ as given in (80). For the time being we assume
$\lim_{d\rightarrow\infty}\nu\rightarrow 0$, and for the ${\bf q}^{(net)}$
from (80), we write

$\displaystyle{\bf f}^{(2)}\left({\bf q}^{(net)}\right)={\bf
f}^{(2)}\left({\bf g}^{(2)}\right)+\left(\nu\frac{d{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)}{d{\bf q}^{(net)}}\circ{\bf w}\right)\circ\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf g}^{(2)}}+o(\nu).$ (82)

Combining (81) and (82), one further finds

$\displaystyle{\mathcal{L}}(\nu)$ $\displaystyle=$
$\displaystyle-\nu^{2}\left\|\frac{d{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)}{d{\bf g}^{(2)}}\circ{\bf w}\right\|_{2}^{2}-2\nu{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf w}+o(\nu).$ (83)

Taking the derivative of ${\mathcal{L}}(\nu)$ with respect to $\nu$ gives

$\displaystyle\frac{d{\mathcal{L}}(\nu)}{d\nu}$ $\displaystyle\rightarrow$
$\displaystyle-2\nu\left\|\frac{d{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}-2{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)^{T}{\bf w}.$ (84)

Equalling the above derivative to zero and keeping in mind that $\nu\geq 0$,
one then finds

$\displaystyle\nu^{(opt)}=\frac{\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)^{T}{\bf w},0\right)}{\left\|\frac{d{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}}.$ (85)

Plugging this value of $\nu$ back into (83), one obtains

$\displaystyle{\mathcal{L}}(\nu^{(opt)})$ $\displaystyle=$
$\displaystyle\frac{\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)^{T}{\bf w},0\right)\right)^{2}}{\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}}.$ (86)

A combination of (4.1.1), (77), (78), and (86) together with concentrations
gives

$\displaystyle{\mathbb{E}}_{{\bf g}^{(2)}}z_{i}^{(1)}\left(\bar{{\bf
g}}^{(2)};{\bf f}^{(2)}\left({\bf q}^{(net)}\right)\right)$
$\displaystyle\geq$ $\displaystyle{\mathbb{E}}_{{\bf
g}^{(2)}}{\mathcal{L}}(\nu^{(opt)})$ (87) $\displaystyle\rightarrow$
$\displaystyle\frac{{\mathbb{E}}_{{\bf g}^{(2)}}\left(\max\left(-{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf
w},0\right)\right)^{2}}{{\mathbb{E}}_{{\bf g}^{(2)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}}.$

_(i) Handling ${\mathbb{E}}_{{\bf g}^{(2)}}\left(\max\left(-{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf w},0\right)\right)^{2}$:_ We first
write

$\displaystyle-{\bf f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf w}$
$\displaystyle=$ $\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}{\bf
f}^{(2)}\left({\bf g}_{j_{w}}^{(2)}\right)-\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf
f}^{(2)}\left({\bf g}_{j_{w}}^{(2)}\right).$ (88)

Utilizing concentrations and the central limit theorem, one further has

$\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(2)}\right)$ $\displaystyle\rightarrow$ $\displaystyle
g_{c,1}^{(2)},$ (89)

where $g_{c,1}^{(2)}$ is a Gaussian variable with mean $\mu_{2,1}$ and
variance $\sigma_{2,1}^{2}$, i.e., $g_{c,1}^{(2)}$ is a Gaussian variable
given by

$g_{c,1}^{(2)}\sim{\mathcal{N}}(\mu_{2,1},\sigma_{2,1}^{2})\quad\mbox{with}\quad\mu_{2,1}=\frac{d}{2}{\mathbb{E}}{\bf
f}^{(2)}\left({\bf
g}_{1}^{(2)}\right),\quad\mbox{and}\quad\sigma_{2,1}^{2}=\frac{d}{2}\left({\mathbb{E}}\left({\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)^{2}-\left({\mathbb{E}}{\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)^{2}\right).$ (90)

Analogously, one also has

$\displaystyle\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(2)}\right)$ $\displaystyle\rightarrow$ $\displaystyle
g_{c,2}^{(2)},$ (91)

where $g_{c,2}^{(2)}$ is a Gaussian variable with mean $\mu_{2,2}$ and
variance $\sigma_{2,2}^{2}$, i.e., $g_{c,2}^{(2)}$ is a Gaussian variable
given by

$g_{c,2}^{(2)}\sim{\mathcal{N}}(\mu_{2,2},\sigma_{2,2}^{2})\quad\mbox{with}\quad\mu_{2,2}=\frac{d}{2}{\mathbb{E}}{\bf
f}^{(2)}\left({\bf
g}_{1}^{(2)}\right),\quad\mbox{and}\quad\sigma_{2,2}^{2}=\frac{d}{2}\left({\mathbb{E}}\left({\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)^{2}-\left({\mathbb{E}}{\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)^{2}\right).$ (92)

As $g_{c,1}^{(2)}$ and $g_{c,2}^{(2)}$ are independent one also has

$\displaystyle-{\bf f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf
w}=\sum_{j_{w}=1}^{\frac{d}{2}}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(2)}\right)-\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(2)}\right)\longrightarrow\left(g_{c,1}^{(2)}-g_{c,2}^{(2)}\right)\longrightarrow
g_{c}^{(2)},$ (93)

where $g_{c}^{(2)}$ is a Gaussian variable with mean
$\mu_{2}=\mu_{2,1}-\mu_{2,2}=0$ and variance
$\sigma_{2}^{2}=\sigma_{2,1}^{2}+\sigma_{2,2}^{2}$, i.e., $g_{c}^{(2)}$ is a
Gaussian variable given by

$\displaystyle
g_{c}^{(2)}\sim{\mathcal{N}}(\mu_{2},\sigma_{2}^{2})\quad\mbox{with}\quad\mu_{2}=0,\quad\mbox{and}\quad\sigma_{2}^{2}=d\left({\mathbb{E}}\left({\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)^{2}-\left({\mathbb{E}}\left({\bf
f}^{(2)}\left({\bf g}_{1}^{(2)}\right)\right)\right)^{2}\right).$ (94)

We then also have

$\displaystyle{\mathbb{E}}_{{\bf g}^{(2)}}\left(\max\left(-{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf
w},0\right)\right)^{2}={\mathbb{E}}_{g_{c}^{(2)}}\left(\max\left(g_{c}^{(2)},0\right)\right)^{2}=\frac{1}{2}\sigma_{2}^{2}.$
(95)

Recalling on (71), we first have

${\mathbb{E}}\left({\bf f}^{(2)}\left({\bf
g}_{1}^{(2)}\right)\right)={\mathbb{E}}\max({\bf
g}_{1}^{(2)},0)=\frac{1}{2}\sqrt{\frac{2}{\pi}},$ (96)

and then

${\mathbb{E}}\left({\bf f}^{(2)}\left({\bf
g}_{1}^{(2)}\right)\right)^{2}={\mathbb{E}}\left(\max({\bf
g}_{1}^{(2)},0)\right)^{2}=\frac{1}{2}.$ (97)

Combining (94), (96), and (97), one obtains

$\displaystyle\sigma_{2}^{2}=d\left({\mathbb{E}}\left({\bf f}^{(2)}\left({\bf
g}_{1}^{(2)}\right)\right)^{2}-\left({\mathbb{E}}\left({\bf f}^{(2)}\left({\bf
g}_{1}^{(2)}\right)\right)\right)^{2}\right)=d\left(\frac{1}{2}-\left(\frac{1}{2}\sqrt{\frac{2}{\pi}}\right)^{2}\right)=d\left(\frac{\pi-1}{2\pi}\right).$
(98)

From (95) and (98), we find

$\displaystyle{\mathbb{E}}_{{\bf g}^{(2)}}\left(\max\left(-{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf
w},0\right)\right)^{2}=\frac{1}{2}\sigma_{2}^{2}=d\left(\frac{\pi-1}{4\pi}\right).$
(99)

_(ii) Handling ${\mathbb{E}}_{{\bf g}^{(2)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}$:_
Recalling again on (71), we find

$\displaystyle\frac{d{\bf f}^{(2)}\left({\bf g}_{j_{w}}^{(2)}\right)}{d{\bf
g}_{j_{w}}^{(2)}}=\begin{cases}1,&\mbox{if }{\bf g}_{j_{w}}^{(2)}\geq 0\\\
0,&\mbox{otherwise}.\end{cases}$ (100)

One then also has

$\displaystyle{\mathbb{E}}_{{\bf g}^{(2)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf
g}^{(2)}}\right\|_{2}^{2}={\mathbb{E}}_{{\bf
g}^{(2)}}\sum_{j_{w}=1}^{d}\left(\frac{d{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(2)}\right)}{d{\bf
g}_{j_{w}}^{(2)}}\right)^{2}=\sum_{j_{w}=1}^{d}{\mathbb{E}}_{{\bf
g}_{j_{w}}^{(2)}}h_{s}({\bf g}_{j_{w}}^{(2)})=\frac{d}{2},$ (101)

where $h_{s}(\cdot)$ is the unit step function. Moreover, a combination of
(85), (95), and (101) gives

$\displaystyle\nu^{(opt)}=\frac{\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)^{T}{\bf w},0\right)}{\left\|\frac{d{\bf f}^{(2)}\left({\bf
g}^{(2)}\right)}{d{\bf
g}^{(2)}}\right\|_{2}^{2}}\rightarrow\frac{\max\left(g_{c}^{(2)},0\right)}{\frac{d}{2}},$
(102)

which means that for any constant $\epsilon>0$

$\displaystyle\lim_{d\rightarrow\infty}{\mathbb{P}}\left(\nu^{(opt)}>\epsilon\right)=1.$
(103)

This then confirms the small $\nu$ assumptions utilized earlier and ensures
that the above machinery is indeed correct. Also, while the above establishes
the inequality in (87), it is trivial to check that taking ${\bf q}^{(net)}$
as in (80) with $\nu^{(opt)}$ from (85), one has that the objective in (4.1.1)
is actually equal to the right hand side of (87). Moreover, from (82), one
finds

$\displaystyle{\bf f}^{(2)}\left({\bf q}^{(net)}\right){\bf w}={\bf
f}^{(2)}\left({\bf g}^{(2)}\right){\bf w}+\nu\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf g}^{(2)}}\right\|_{2}^{2}+o(\nu),$
(104)

which for $\nu^{(opt)}$ from (85) ensures that, with probability going to 1 as
$d\rightarrow\infty$, ${\bf f}^{(2)}\left({\bf q}^{(net)}\right){\bf w}\geq
0$. This also implies that ${\bf q}^{(net)}$ from (80) with $\nu^{(opt)}$ from
(85) is, in the large $d$ limit, with probability 1 feasible in (4.1.1),
which, on the other hand, ensures that the lower bound given by the right hand
side of (87) is actually attainable. All of this practically means that one
has the equality in (87). Due to the concentrations, the equality holds not
only for the expectations but also with probability going to 1 as
$d\rightarrow\infty$.

Utilizing all of the above observations, and combining (87), (99), and (101),
we then obtain

$\displaystyle\lim_{d\rightarrow\infty}{\mathbb{E}}_{{\bf
g}^{(2)}}z_{i}^{(1)}\left(\bar{{\bf g}}^{(2)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle=$
$\displaystyle\lim_{d\rightarrow\infty}\frac{{\mathbb{E}}_{{\bf
g}^{(2)}}\left(\max\left(-{\bf f}^{(2)}\left({\bf g}^{(2)}\right)^{T}{\bf
w},0\right)\right)^{2}}{{\mathbb{E}}_{{\bf g}^{(2)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(2)}\right)}{d{\bf
g}^{(2)}}\right\|_{2}^{2}}=\frac{\pi-1}{2\pi}.$ (105)

A further combination of (74) and (105) then gives

$\displaystyle(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{first
level:}}})\qquad a_{c}^{(1)}(\infty)$ $\displaystyle=$
$\displaystyle\lim_{d\rightarrow\infty}a_{c}^{(1)}(d)=\frac{1}{\lim_{d\rightarrow\infty}{\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}\left(z_{i}^{(1)}\left(\bar{{\bf
g}}^{(2)};{\bf f}^{(2)}\left({\bf q}^{(net)}\right)\right)\right)}$ (106)
$\displaystyle=$
$\displaystyle\frac{1}{\lim_{d\rightarrow\infty}{\mathbb{E}}_{{\bf
g}^{(2)}}\left(z_{i}^{(1)}\left(\bar{{\bf g}}^{(2)};\max\left({\bf
q}^{(net)},0\right)\right)\right)}=\frac{2\pi}{\pi-1}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{2.9339}}.$

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

The analysis of the second level of lifting will be split into two separate
parts: (i) _partial_ second level of lifting; and (ii) _full_ second level of
lifting.

#####  4.1.2.1 Partial second level of lifting

For $r=2$ and the partial lifting, we have (similarly to the first level)
$\hat{{\bf p}}_{1}\rightarrow 1$ and $\hat{{\bf q}}_{1}\rightarrow 1$,
$\hat{{\bf p}}_{2}=\hat{{\bf q}}_{2}=0$, and $\hat{{\bf p}}_{r+1}=\hat{{\bf
p}}_{3}=\hat{{\bf q}}_{r+1}=\hat{{\bf q}}_{3}=0$. However, now, in general,
$\hat{{\bf c}}_{2}\neq 0$. Following discussion of the previous sections, we
again start by writing

$\displaystyle\bar{\psi}_{rd}^{(d,2)}(\hat{{\bf p}},\hat{{\bf q}},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}{\bf
c}_{2}-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{{\bf
c}_{2}\frac{\left(\sqrt{1-0}{\bf
h}_{1}^{(2,1)}\right)^{2}}{4\gamma_{sq}^{(p)}}}\right)$
$\displaystyle\quad+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{\bar{{\bf g}}^{(3)}}e^{-{\bf
c}_{2}\frac{z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};{\bf
f}^{(2)}\right)}{4\gamma_{sq}}}\right)$ $\displaystyle=\frac{1}{2}{\bf
c}_{2}-\gamma_{sq}^{(p)}+\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf
c}_{2}}{2\gamma_{sq}^{(p)}}\right)$
$\displaystyle\quad+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{\bar{{\bf g}}^{(3)}}e^{-{\bf
c}_{2}\frac{z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right).$ (107)

From (87), (104), considerations right after (104), (105), (93), (94), and
(98), we first have

$\displaystyle z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle\rightarrow$
$\displaystyle\frac{\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(3)}\right)^{T}{\bf w},0\right)\right)^{2}}{\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(3)}\right)}{d{\bf g}^{(3)}}\right\|_{2}^{2}},$ (108)

and then

$\displaystyle z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};\max\left({\bf
q}^{(net)},0\right)\right)$ $\displaystyle\rightarrow$
$\displaystyle\frac{\left(\max\left(g_{c}^{(3)},0\right)\right)^{2}}{\frac{d}{2}}\rightarrow\left(\max\left(\bar{g}_{c}^{(3)},0\right)\right)^{2},$
(109)

with

$\displaystyle\bar{g}_{c}^{(3)}\sim{\mathcal{N}}\left(0,\bar{\sigma}_{3}^{2}\right),\quad\mbox{and}\quad\bar{\sigma}_{3}^{2}=\frac{\pi-1}{\pi}.$
(110)

A combination of (4.1.2.1) and (110) further gives

$\displaystyle\bar{\psi}_{rd}^{(d,2)}(\hat{{\bf p}},\hat{{\bf q}},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}{\bf
c}_{2}-\gamma_{sq}^{(p)}+\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf
c}_{2}}{2\gamma_{sq}^{(p)}}\right)+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left({\mathbb{E}}_{\bar{g}_{c}^{(2)}}e^{-{\bf
c}_{2}\frac{\left(\max\left(\bar{g}_{c}^{(3)},0\right)\right)^{2}}{4\gamma_{sq}}}\right)$
$\displaystyle=\frac{1}{2}{\bf c}_{2}-\gamma_{sq}^{(p)}+\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf
c}_{2}}{2\gamma_{sq}^{(p)}}\right)+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}\log\left(\frac{1}{2}+\frac{1}{2\sqrt{\frac{\bar{\sigma}_{3}^{2}{\bf
c}_{2}}{2\gamma_{sq}}+1}}\right).$ (111)

After computing the derivatives of $\bar{\psi}_{rd}^{(d,2)}(\hat{{\bf
p}},\hat{{\bf q}},{\bf c},\gamma_{sq},\gamma_{sq}^{(p)})$ with respect to
$\gamma_{sq}^{(p)}$, $\gamma_{sq}$, and ${\bf c}_{2}$ and equalling them to
zero, one proceeds by solving the obtained system of equations. Denoting the
solution of the system by $\hat{\gamma}_{sq}^{(p)}$, $\hat{\gamma}_{sq}$, and
$\hat{{\bf c}}_{2}$, we first have the following convenient closed form
relation

$\hat{\gamma}_{sq}^{(p)}=\frac{\hat{{\bf c}}_{2}+\sqrt{\hat{{\bf
c}}_{2}^{2}+4}}{4},$ (112)

and then ultimately from $\bar{\psi}_{rd}^{(d,2)}(\hat{{\bf p}},\hat{{\bf
q}},\hat{{\bf c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})=0$ obtain for

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\emph{partial}
second level:}}})\qquad\qquad
a_{c}^{(2,p)}(\infty)=\lim_{d\rightarrow\infty}a_{c}^{(2,p)}(d)\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{2.8503}}.$
(113)

#####  4.1.2.2 Full second level of lifting

One can also utilize the above setup for the full lifting on the second level.
This time though, one has to be additionally careful. Namely, in addition to
$\hat{{\bf c}}_{2}\neq 0$, one, in general, also has ${\bf p}_{2}\neq 0$ and
${\bf q}_{2}\neq 0$. Analogously to (4.1.2.1), we now write

$\displaystyle\bar{\psi}_{rd}^{(d,2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{{\bf
c}_{2}\frac{\left(\sqrt{1-{\bf q}_{2}}{\bf h}_{1}^{(2,1)}+\sqrt{{\bf
q}_{2}}{\bf h}_{1}^{(3,1)}\right)^{2}}{4\gamma_{sq}^{(p)}}}\right)$ (114)
$\displaystyle+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}-\gamma_{sq}^{(p)}-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}}\right)$ $\displaystyle+\frac{{\bf
q}_{2}}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf q}_{2}))}\Bigg{.}\Bigg{)}$
$\displaystyle+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right).$

We now briefly digress and set

$\displaystyle{\bf g}^{(x,r)}\triangleq\sum_{k=2}^{r+1}b_{k}{\bf g}^{(k)},$
(115)

and recalling on (69) write

$\displaystyle z_{i}^{(r)}(\bar{{\bf g}}^{(r+1)};{\bf f}^{(2)})$
$\displaystyle=$ $\displaystyle\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left(\left(\sum_{k=2}^{r+1}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)-{\bf q}^{(net)}_{j_{w}}\right)^{2}$ (116)
$\displaystyle=$ $\displaystyle\min_{{\bf f}^{(2)}\left(\left({\bf
q}^{(net)}\right)^{T}\right){\bf w}\geq 0}\sum_{j_{w}=1}^{d}\left({\bf
g}_{j_{w}}^{(x,r)}-{\bf q}^{(net)}_{j_{w}}\right)^{2}.$

Specializing (116) to $r=2$, we further have

$\displaystyle z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle=$ $\displaystyle\min_{{\bf
f}^{(2)}\left(\left({\bf q}^{(net)}\right)^{T}\right){\bf w}\geq
0}\sum_{j_{w}=1}^{d}\left({\bf g}_{j_{w}}^{(x,2)}-{\bf
q}^{(net)}_{j_{w}}\right)^{2}.$ (117)

Repeating all the arguments between (4.1.1) and (87) and relying on the
discussion between (103) and (105), one obtains that as $d\rightarrow\infty$

$\displaystyle z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle\rightarrow$
$\displaystyle\frac{\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(x,2)}\right)^{T}{\bf w},0\right)\right)^{2}}{{\mathbb{E}}_{\bar{{\bf
g}}^{(3)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf
g}^{(x,2)}}\right\|_{2}^{2}}.$ (118)

_(i) Handling $\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(x,2)}\right)^{T}{\bf w},0\right)\right)^{2}$:_ We first recall
$b_{2}=\sqrt{1-{\bf p}_{2}}$ and $b_{3}=\sqrt{{\bf p}_{2}}$ and write

$\displaystyle-{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)^{T}{\bf w}$
$\displaystyle=$ $\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}{\bf
f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)-\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf
f}^{(2)}\left({\bf g}_{j_{w}}^{(x,2)}\right).$ (119)

Conditioning on ${\bf g}^{(3)}$, utilizing concentrations, and relying on the
central limit theorem, one further has

$\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)=\sum_{j_{w}=1}^{\frac{d}{2}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{j_{w}}^{(k)}\right)\rightarrow
g_{c,1}^{(3,1)},$ (120)

where $g_{c,1}^{(3,1)}$ is a Gaussian variable with mean $\mu_{3,1;1}$ and
variance $\sigma_{3,1;1}^{2}$, i.e., $g_{c,1}^{(3,1)}$ is a Gaussian variable
given by

$g_{c,1}^{(3,1)}\sim{\mathcal{N}}(\mu_{3,1;1},\sigma_{3,1;1}^{2}),$ (121)

with

$\mu_{3,1;1}=\sum_{j_{w}=1}^{\frac{d}{2}}{\mathbb{E}}_{{\bf g}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{r+1}b_{k}{\bf g}_{j_{w}}^{(k)}\right),$ (122)

and

$\displaystyle\sigma_{3,1;1}^{2}$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}\left({\mathbb{E}}_{{\bf
g}^{(3)}}{\mathbb{E}}_{{\bf g}^{(2)}}\left({\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}^{(3)}}\left({\mathbb{E}}_{{\bf g}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\right)^{2}\right)$ (123) $\displaystyle=$
$\displaystyle\frac{d}{2}\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}\left({\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right).$

Moreover, utilizing again the concentrations, and relying on the central limit
theorem, one further has for $\mu_{3,1;1}$ itself

$\displaystyle\mu_{3,1;1}=\sum_{j_{w}=1}^{\frac{d}{2}}{\mathbb{E}}_{{\bf
g}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\rightarrow g_{c,1}^{(3,2)},$ (124)

where $g_{c,1}^{(3,2)}$ is a Gaussian variable with mean $\mu_{3,2;1}$ and
variance $\sigma_{3,2;1}^{2}$, i.e., $g_{c,1}^{(3,2)}$ is a Gaussian variable
given by

$g_{c,1}^{(3,2)}\sim{\mathcal{N}}(\mu_{3,2;1},\sigma_{3,2;1}^{2}),$ (125)

with

$\mu_{3,2;1}=\sum_{j_{w}=1}^{\frac{d}{2}}{\mathbb{E}}_{{\bf
g}^{(3)}}{\mathbb{E}}_{{\bf g}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)=\frac{d}{2}{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right),$ (126)

and

$\displaystyle\sigma_{3,2;1}^{2}$ $\displaystyle=$
$\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}\left({\mathbb{E}}_{{\bf
g}^{(3)}}\left({\mathbb{E}}_{{\bf g}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}^{(3)}}{\mathbb{E}}_{{\bf g}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\right)^{2}\right)$ (127) $\displaystyle=$
$\displaystyle\frac{d}{2}\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right).$

A combination of (120)-(127) gives

$\displaystyle\sum_{j_{w}=1}^{\frac{d}{2}}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)=\sum_{j_{w}=1}^{\frac{d}{2}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{j_{w}}^{(k)}\right)\rightarrow\sigma_{3,1;1}g_{f,1}^{(3,1)}+\sigma_{3,2;1}g_{f,1}^{(3,2)}+\mu_{3,2;1},$
(128)

where $g_{f,1}^{(3,1)}$ and $g_{f,1}^{(3,2)}$ are independent standard
normals. Due to symmetry, one analogously also has

$\displaystyle\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)$ $\displaystyle\rightarrow$
$\displaystyle\sigma_{3,1;1}g_{f,2}^{(3,1)}+\sigma_{3,2;1}g_{f,2}^{(3,2)}+\mu_{3,2;1},$
(129)

where $g_{f,2}^{(3,1)}$ and $g_{f,2}^{(3,2)}$ are independent standard normals
(which are also independent of $g_{f,1}^{(3,1)}$ and $g_{f,1}^{(3,2)}$). It is
then easy to observe that

$\displaystyle-{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)^{T}{\bf
w}=\sum_{j_{w}=1}^{\frac{d}{2}}{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)-\sum_{j_{w}=\frac{d}{2}+1}^{d}{\bf
f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)\longrightarrow\sqrt{2}\sigma_{3,1;1}g_{f}^{(3,1)}+\sqrt{2}\sigma_{3,2;1}g_{f}^{(3,2)},$
(130)

where $g_{f}^{(3,1)}$ and $g_{f}^{(3,2)}$ are independent standard normals,
where $g_{f}^{(3,1)}$ relates to the first part obtained by conditioning on
${\bf g}^{(3)}$ and the second part relates to the residual randomness over
${\bf g}^{(3)}$.

_(ii) Handling ${\mathbb{E}}_{\bar{{\bf g}}^{(3)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf g}^{(x,2)}}\right\|_{2}^{2}$:_ Due
to concentrations one has analogously to (101)

$\displaystyle{\mathbb{E}}_{\bar{{\bf g}}^{(3)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf
g}^{(x,2)}}\right\|_{2}^{2}={\mathbb{E}}_{\bar{{\bf
g}}^{(3)}}\sum_{j_{w}=1}^{d}\left(\frac{d{\bf f}^{(2)}\left({\bf
g}_{j_{w}}^{(x,2)}\right)}{d{\bf
g}_{j_{w}}^{(x,2)}}\right)^{2}=\sum_{j_{w}=1}^{d}{\mathbb{E}}_{{\bf
g}_{j_{w}}^{(x,2)}}h_{s}({\bf g}_{j_{w}}^{(x,2)})=\frac{d}{2},$ (131)

where $h_{s}(\cdot)$ is the unit step function.

One can now combine (118), (123), (127), (130), and (131) to write

$\displaystyle z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle\rightarrow$
$\displaystyle\frac{\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(x,2)}\right)^{T}{\bf w},0\right)\right)^{2}}{{\mathbb{E}}_{\bar{{\bf
g}}^{(3)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf
g}^{(x,2)}}\right\|_{2}^{2}}$ (132) $\displaystyle\rightarrow$
$\displaystyle\left(\max\left(\bar{b}_{2}g_{f}^{(3,1)}+\bar{b}_{3}g_{f}^{(3,2)},0\right)\right)^{2},$

where

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{d}{{\mathbb{E}}_{\bar{{\bf
g}}^{(3)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf
g}^{(x,2)}}\right\|_{2}^{2}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}\left({\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right)}$
$\displaystyle\bar{b}_{3}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{d}{{\mathbb{E}}_{\bar{{\bf
g}}^{(3)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,2)}\right)}{d{\bf
g}^{(x,2)}}\right\|_{2}^{2}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right)},$

which, after the utilization of (131), becomes

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{2\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\left({\bf f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right)}$
$\displaystyle\bar{b}_{3}$ $\displaystyle=$
$\displaystyle\sqrt{2\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}\right)}.$
(134)

As mentioned earlier, $g_{f}^{(3,1)}$ relates to the randomness of ${\bf
g}^{(2)}$ (i.e., ${\mathcal{U}}_{2}$) and $g_{f}^{(3,2)}$ relates to the
randomness of ${\bf g}^{(3)}$ (i.e., ${\mathcal{U}}_{3}$).

_(iii) Specializing to ${\bf f}^{(2)}\left({\bf
q}^{(net)}\right)=\max\left({\bf q}^{(net)},0\right)$:_ We first observe

$\displaystyle\bar{p}_{1}=2{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\left({\bf f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}=2{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\left(\max\left(\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)\right)^{2}=2\frac{1}{2}=1,$ (135)

and

$\displaystyle\bar{p}_{3}=2\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}=2\left({\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)\right)^{2}=2\left(\frac{1}{2}\sqrt{\frac{2}{\pi}}\right)^{2}=\frac{1}{\pi}.$

Then one also has

$\displaystyle{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sum_{k=2}^{3}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)={\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sqrt{1-{\bf p}_{2}}{\bf g}_{1}^{(2)}+\sqrt{{\bf
p}_{2}}{\bf g}_{1}^{(3)}\right),0\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\sqrt{\frac{2}{\pi}}\sqrt{1-{\bf
p}_{2}}e^{-\frac{\left(\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\right).^{2}}{2\sqrt{1-{\bf p}_{2}}^{2}}}+\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\mbox{erf}\left(\frac{\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}}{\sqrt{2}\sqrt{1-{\bf p}_{2}}}\right)+\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\right),$

and

$\displaystyle\bar{p}_{2}$ $\displaystyle=$ $\displaystyle 2{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{3}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}$
$\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}\left(\sqrt{\frac{2}{\pi}}\sqrt{1-{\bf
p}_{2}}e^{-\frac{\left(\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\right).^{2}}{2\sqrt{1-{\bf p}_{2}}^{2}}}+\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\mbox{erf}\left(\frac{\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}}{\sqrt{2}\sqrt{1-{\bf p}_{2}}}\right)+\sqrt{{\bf p}_{2}}{\bf
g}_{1}^{(3)}\right)^{2}\frac{e^{-\frac{\left({\bf
g}^{(3)}\right)^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}^{(3)}.$

Combining (4.1.2.2), (135), (4.1.2.2), and (4.1.2.2), we then find

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{\bar{p}_{1}-\bar{p}_{2}}$ $\displaystyle\bar{b}_{3}$
$\displaystyle=$ $\displaystyle\sqrt{\bar{p}_{2}-\bar{p}_{3}},$ (139)

where, for the ReLU activations, $\bar{p}_{1}$, $\bar{p}_{2}$, and
$\bar{p}_{3}$ are as in (135), (4.1.2.2), and (4.1.2.2), respectively.

We can now return to the initial considerations, utilize (132),(135),
(4.1.2.2), (4.1.2.2), and (4.1.2.2), and rewrite (114) as

$\displaystyle\bar{\psi}_{rd}^{(d,2)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}-\gamma_{sq}^{(p)}-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}}\right)$ (140) $\displaystyle+\frac{{\bf
q}_{2}}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf q}_{2}))}\Bigg{.}\Bigg{)}$
$\displaystyle+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(2)}\left(\bar{{\bf g}}^{(3)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}-\gamma_{sq}^{(p)}-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}}\right)$ $\displaystyle+\frac{{\bf
q}_{2}}{2(2\gamma_{sq}-{\bf c}_{2}(1-{\bf q}_{2}))}\Bigg{.}\Bigg{)}$
$\displaystyle+\gamma_{sq}-\alpha\frac{1}{{\bf
c}_{2}}{\mathbb{E}}_{g_{f}^{(3,2)}}\log\left({\mathbb{E}}_{g_{f}^{(3,1)}}e^{-{\bf
c}_{2}\frac{\left(\max\left(\bar{b}_{2}g_{f}^{(3,1)}+\bar{b}_{3}g_{f}^{(3,2)},0\right)\right)^{2}}{4\gamma_{sq}}}\right).$

One now observes a remarkable property of the above machinery. Namely, the
expression in (140) is structurally identical to the corresponding one given
in equation (50) in [37]. The only difference is that now one has the adjusted
values $\bar{b}_{2}=\sqrt{1-\bar{p}_{2}}$ and
$\bar{b}_{3}=\sqrt{\bar{p}_{2}-\bar{p}_{3}}$. One can then solve the remaining
integrals as in [37] and obtain

$\displaystyle\hat{h}$ $\displaystyle=$
$\displaystyle-\frac{\sqrt{\bar{p}_{2}-\bar{p}_{3}}g_{f}^{(3,2)}}{\sqrt{\bar{p}_{1}-\bar{p}_{2}}}$
$\displaystyle\hat{B}$ $\displaystyle=$ $\displaystyle\frac{{\bf
c}_{2}}{4\gamma_{sq}}$ $\displaystyle\hat{C}$ $\displaystyle=$
$\displaystyle\sqrt{\bar{p}_{2}-\bar{p}_{3}}g_{f}^{(3,2)}$ $\displaystyle
f_{(zd)}^{(2,f)}$ $\displaystyle=$
$\displaystyle\frac{e^{-\frac{\hat{B}\hat{C}^{2}}{2\bar{p}_{1}1-\bar{p}_{2})\hat{B}+1}}}{2\sqrt{2(\bar{p}_{1}-\bar{p}_{2})\hat{B}+1}}\mbox{erfc}\left(\frac{\hat{h}}{\sqrt{4(\bar{p}_{1}-\bar{p}_{2})\hat{B}+2}}\right)$
$\displaystyle f_{(zu)}^{(2,f)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\mbox{erfc}\left(-\frac{\hat{h}}{\sqrt{2}}\right),$
$\displaystyle f_{(zt)}^{(2,f)}$ $\displaystyle=$ $\displaystyle
f_{(zd)}^{(2,f)}+f_{(zu)}^{(2,f)}.$ (141)

and

$\displaystyle{\mathbb{E}}_{g_{f}^{(3,2)}}\log\left({\mathbb{E}}_{g_{f}^{(3,1)}}e^{-{\bf
c}_{2}\frac{\left(\max\left(\bar{b}_{2}g_{f}^{(3,1)}+\bar{b}_{3}g_{f}^{(3,2)},0\right)\right)^{2}}{4\gamma_{sq}}}\right)={\mathbb{E}}_{g_{f}^{(3,2)}}\log\left(f_{(zt)}^{(2,f)}\right).$
(142)

As in [37], one now needs to compute _five_ derivatives with respect to ${\bf
q}_{2}$, ${\bf p}_{2}$, ${\bf c}_{2}$, $\gamma_{sq}$, and $\gamma_{sq}^{(p)}$.
These are structurally identical (with a very minimal adjustment for
$\bar{p}_{3}\neq 0$) to the corresponding ones computed in [37]. The only tiny
structural difference is that for the ${\bf p}_{2}$ derivative, one needs to
additionally trivially account for $\frac{d\bar{p}_{2}}{d{\bf p}_{2}}$. After
computing the derivatives one then solves the following system of equations

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

and denotes the obtained solution by $\hat{{\bf q}}_{2},\hat{{\bf
p}}_{2},\hat{{\bf c}}_{2},\hat{\gamma}_{sq}^{(p)},\hat{\gamma}_{sq}$. Due to
structural identicalness between the derivatives considered here and those
considered in [37], one actually even has that the following closed form
relations, established in [37], actually hold here as well

$\displaystyle\hat{\gamma}_{sq}^{(p)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\frac{1-\hat{{\bf q}}_{2}}{1-\hat{{\bf
p}}_{2}}\sqrt{\frac{\hat{{\bf p}}_{2}}{\hat{{\bf q}}_{2}}}$
$\displaystyle\hat{{\bf c}}_{2}$ $\displaystyle=$
$\displaystyle\frac{1}{1-\hat{{\bf p}}_{2}}\sqrt{\frac{\hat{{\bf
p}}_{2}}{\hat{{\bf q}}_{2}}}-\frac{1}{1-\hat{{\bf
q}}_{2}}\sqrt{\frac{\hat{{\bf q}}_{2}}{\hat{{\bf p}}_{2}}}.$ (144)

Taking concrete numerical values for all the parameters, we then from
$\bar{\psi}_{rd}^{(d,2)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})=0$ find for

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\emph{full}
second level:}}})\qquad\qquad
a_{c}^{(2,f)}(\infty)=\lim_{d\rightarrow\infty}a_{c}^{(2,f)}(d)\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{2.6643}}.$
(145)

_Concrete numerical values:_ In Table 2, the above $a_{c}^{(2,f)}(\infty)$ is
complemented with the concrete values of all the relevant quantities related
to the second _full_ (2-sfl RDT) level of lifting. Moreover, to enable a
systematic view of the lifting progress, the corresponding quantities for the
first _full_ (1-sfl RDT) and the second _partial_ (2-spf RDT) level are shown
as well.

Table 2: $r$-sfl RDT parameters; _ReLU_ activations – _wide_ treelike net capacity; $\hat{{\bf c}}_{1}\rightarrow 1$; $d\rightarrow\infty$; $n\rightarrow\infty$ $r$-sfl RDT | $\hat{\gamma}_{sq}$ | $\hat{\gamma}_{sq}^{(p)}$ | $\hat{{\bf p}}_{2}$ | $\hat{{\bf p}}_{1}$ | $\hat{{\bf q}}_{2}$ | $\hat{{\bf q}}_{1}$ | $\hat{{\bf c}}_{2}$ | $\alpha_{c}^{(r)}(-1.5)$
---|---|---|---|---|---|---|---|---
$1$-sfl RDT | $0.5$ | $0.5$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $\rightarrow 0$ | $\mathbf{2.9339}$
$2$-spl RDT | $0.3339$ | $0.7487$ | $0$ | $\rightarrow 1$ | $0$ | $\rightarrow 1$ | $0.8295$ | $\mathbf{2.8503}$
$2$-sfl RDT | $0.1396$ | $1.7903$ | $0.7571$ | $\rightarrow 1$ | $0.3822$ | $\rightarrow 1$ | $4.6457$ | $\mathbf{2.6643}$

We also observe that the capacity results shown in Table 2 exactly match the
corresponding ones obtained using the statistical physics replica methods
relying on the replica symmetry, partial 1rsb, and full 1rsb in [53].
Moreover, the very same replica symmetry and 1rsb predictions were obtained in
[2] as well and are also exactly matched.

####  4.1.3 $r=3$ – third level of lifting

The main ideas behind the partial lifting were already presented in earlier
sections. We here skip repeating such considerations and immediately look at
the _full_ third level of lifting. For $r=3$, one has that $\hat{{\bf
p}}_{1}\rightarrow 1$ and $\hat{{\bf q}}_{1}\rightarrow 1$ as well as
$\hat{{\bf p}}_{r+1}=\hat{{\bf p}}_{4}=\hat{{\bf q}}_{r+1}=\hat{{\bf
q}}_{4}=0$. Analogously to (4.1.1), (4.1.2.1), and (114), we then write

$\displaystyle\bar{\psi}_{rd}^{(d,3)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}(1-{\bf
p}_{2}{\bf q}_{2}){\bf c}_{2}+\frac{1}{2}({\bf p}_{2}{\bf q}_{2}-{\bf
p}_{3}{\bf q}_{3}){\bf c}_{3}$
$\displaystyle\quad-\gamma_{sq}^{(p)}-\frac{1}{{\bf
c}_{3}}{\mathbb{E}}_{{\mathcal{U}}_{4}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{{\bf
c}_{2}\frac{\left(\sqrt{1-{\bf q}_{2}}{\bf h}_{1}^{(2,1)}+\sqrt{{\bf
q}_{2}-{\bf q}_{3}}{\bf h}_{1}^{(3,1)}+\sqrt{{\bf q}_{3}}{\bf
h}_{1}^{(4,1)}\right)^{2}}{4\gamma_{sq}^{(p)}}}\right)^{\frac{{\bf
c}_{3}}{{\bf c}_{2}}}\right)$
$\displaystyle\quad+\gamma_{sq}-\frac{\alpha}{{\bf
c}_{3}}{\mathbb{E}}_{{\mathcal{U}}_{4}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(3)}\left(\bar{{\bf g}}^{(4)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)$ $\displaystyle=\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}+\frac{1}{2}({\bf p}_{2}{\bf q}_{2}-{\bf p}_{3}{\bf q}_{3}){\bf
c}_{3}-\gamma_{sq}^{(p)}$ $\displaystyle\quad-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}^{(p)}}\right)-\frac{1}{2{\bf
c}_{3}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf
c}_{3}({\bf q}_{2}-{\bf q}_{3})}{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}\right)$ $\displaystyle\quad+\frac{{\bf
q}_{3}}{2(2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf c}_{3}({\bf
q}_{2}-{\bf q}_{3}))}\Bigg{.}\Bigg{)}$
$\displaystyle\quad+\gamma_{sq}-\frac{\alpha}{{\bf
c}_{3}}{\mathbb{E}}_{{\mathcal{U}}_{4}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(3)}\left(\bar{{\bf g}}^{(4)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right),$ (146)

where the first sequence of integrals is handled through the utilization of
the closed form solutions obtained in [41, 37]. To be able to proceed with
further analysis of (4.1.3), we now again digress for a moment and look at the
parts of the above expression that turn out to be particularly relevant.

_(i) Handling $z_{i}^{(3)}\left(\bar{{\bf g}}^{(4)};\max\left({\bf
q}^{(net)}\right)\right)$:_ Repeating the reasoning between (115) and (132),
one can write the following, third level, analogue to (132)

$\displaystyle z_{i}^{(3)}\left(\bar{{\bf g}}^{(4)};{\bf f}^{(2)}\left({\bf
q}^{(net)}\right)\right)$ $\displaystyle\rightarrow$
$\displaystyle\frac{\left(\max\left(-{\bf f}^{(2)}\left({\bf
g}^{(x,3)}\right)^{T}{\bf w},0\right)\right)^{2}}{{\mathbb{E}}_{\bar{{\bf
g}}^{(4)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,3)}\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}}$ (147) $\displaystyle\rightarrow$
$\displaystyle\left(\max\left(\bar{b}_{2}g_{f}^{(4,1)}+\bar{b}_{3}g_{f}^{(4,2)},0+\bar{b}_{4}g_{f}^{(4,3)},0\right)\right)^{2},$

with

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{\frac{d}{{\mathbb{E}}_{\bar{{\bf
g}}^{(4)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,3)}\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\left({\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)}$ $\displaystyle\bar{b}_{3}$
$\displaystyle=$ $\displaystyle\sqrt{\frac{d}{{\mathbb{E}}_{\bar{{\bf
g}}^{(4)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,3)}\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)}$ $\displaystyle\bar{b}_{4}$
$\displaystyle=$ $\displaystyle\sqrt{\frac{d}{{\mathbb{E}}_{\bar{{\bf
g}}^{(4)}}\left\|\frac{d{\bf f}^{(2)}\left({\bf g}^{(x,3)}\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)},$

which after the utilization of

$\displaystyle{\mathbb{E}}_{\bar{{\bf g}}^{(4)}}\left\|\frac{d{\bf
f}^{(2)}\left({\bf g}^{(x,3)}\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}={\mathbb{E}}_{\bar{{\bf
g}}^{(4)}}\left\|\frac{d\max\left({\bf g}^{(x,3)},0\right)}{d{\bf
g}^{(x,3)}}\right\|_{2}^{2}=\frac{d}{2},$ (149)

becomes

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{2\left({\mathbb{E}}_{{\bf g}_{1}^{(4)}}{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}\left({\bf
f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)}$ $\displaystyle\bar{b}_{3}$
$\displaystyle=$ $\displaystyle\sqrt{2\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)}$ $\displaystyle\bar{b}_{4}$
$\displaystyle=$ $\displaystyle\sqrt{2\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}-\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}\right)},$ (150)

where $b_{2}=\sqrt{1-{\bf p}_{2}}$, $b_{3}=\sqrt{{\bf p}_{2}-{\bf p}_{3}}$,
and $b_{4}=\sqrt{{\bf p}_{3}}$, and, similarly to what we had earlier,
$g_{f}^{(4,1)}$ relates to the randomness of ${\bf g}^{(2)}$ (i.e.,
${\mathcal{U}}_{2}$), $g_{f}^{(4,2)}$ to the randomness of ${\bf g}^{(3)}$
(i.e., ${\mathcal{U}}_{3}$), and $g_{f}^{(4,3)}$ to the randomness of ${\bf
g}^{(4)}$ (i.e., ${\mathcal{U}}_{4}$).

_(ii) Further specializing to ${\bf f}^{(2)}\left({\bf
q}^{(net)}\right)=\max\left({\bf q}^{(net)},0\right)$:_ We start by observing

$\displaystyle\bar{p}_{1}=2{\mathbb{E}}_{{\bf g}_{1}^{(4)}}{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}\left({\bf
f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}=2{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\left(\max\left(\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)\right)^{2}=2\frac{1}{2}=1,$

and

$\displaystyle\bar{p}_{4}$ $\displaystyle=$ $\displaystyle
2\left({\mathbb{E}}_{{\bf g}_{1}^{(4)}}{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf g}_{1}^{(k)}\right)\right)^{2}$
$\displaystyle=$ $\displaystyle 2\left({\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)\right)^{2}=2\left(\frac{1}{2}\sqrt{\frac{2}{\pi}}\right)^{2}=\frac{1}{\pi}.$

Then one also has

$\displaystyle{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf g}_{1}^{(k)}\right)$
$\displaystyle=$ $\displaystyle{\mathbb{E}}_{{\bf
g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sqrt{1-{\bf p}_{2}}{\bf g}_{1}^{(2)}+\sqrt{{\bf
p}_{2}-{\bf p}_{3}}{\bf g}_{1}^{(3)}+\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\right),0\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\sqrt{\frac{2}{\pi}}\sqrt{1-{\bf
p}_{3}}e^{-\frac{\left(\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\right)^{2}}{2\sqrt{1-{\bf p}_{3}}^{2}}}+\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\mbox{erf}\left(\frac{\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}}{\sqrt{2}\sqrt{1-{\bf p}_{3}}}\right)+\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\right),$

and

$\displaystyle\bar{p}_{3}$ $\displaystyle=$ $\displaystyle 2{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}\left({\mathbb{E}}_{{\bf g}_{1}^{(3)}}{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}$ (154) $\displaystyle=$
$\displaystyle\frac{1}{2}\int_{-\infty}^{\infty}\left(\sqrt{\frac{2}{\pi}}\sqrt{1-{\bf
p}_{3}}e^{-\frac{\left(\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\right)^{2}}{2\sqrt{1-{\bf p}_{3}}^{2}}}+\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\mbox{erf}\left(\frac{\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}}{\sqrt{2}\sqrt{1-{\bf p}_{3}}}\right)+\sqrt{{\bf p}_{3}}{\bf
g}_{1}^{(4)}\right)^{2}\frac{e^{-\frac{\left({\bf
g}^{(4)}\right)^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}^{(4)}$
$\displaystyle\triangleq$ $\displaystyle\bar{p}_{x}({\bf p}_{3}).$

Moreover, we also find

$\displaystyle{\mathbb{E}}_{{\bf g}_{1}^{(2)}}{\bf
f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf g}_{1}^{(k)}\right)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf
g}_{1}^{(2)}}\max\left(\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right),0\right)$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf g}_{1}^{(2)}}\max\left(\left(\sqrt{1-{\bf
p}_{2}}{\bf g}_{1}^{(2)}+\sqrt{{\bf p}_{2}-{\bf p}_{3}}{\bf
g}_{1}^{(3)}+\sqrt{{\bf p}_{3}}{\bf g}_{1}^{(4)}\right),0\right),$

and

$\displaystyle\bar{p}_{2}$ $\displaystyle=$ $\displaystyle 2{\mathbb{E}}_{{\bf
g}_{1}^{(4)}}{\mathbb{E}}_{{\bf g}_{1}^{(3)}}\left({\mathbb{E}}_{{\bf
g}_{1}^{(2)}}{\bf f}^{(2)}\left(\sum_{k=2}^{4}b_{k}{\bf
g}_{1}^{(k)}\right)\right)^{2}=\bar{p}_{x}({\bf p}_{2}).$

A combination of (4.1.3), (4.1.3), (4.1.3), (154), and (4.1.3) then also gives

$\displaystyle\bar{b}_{2}$ $\displaystyle=$
$\displaystyle\sqrt{\bar{p}_{1}-\bar{p}_{2}}$ $\displaystyle\bar{b}_{3}$
$\displaystyle=$ $\displaystyle\sqrt{\bar{p}_{2}-\bar{p}_{3}}$
$\displaystyle\bar{b}_{4}$ $\displaystyle=$
$\displaystyle\sqrt{\bar{p}_{3}-\bar{p}_{4}},$ (157)

where, for the ReLU activations, $\bar{p}_{1}$, $\bar{p}_{2}$, $\bar{p}_{3}$,
and $\bar{p}_{4}$ are as in (4.1.3), (4.1.3), (154), and (4.1.3),
respectively.

One can now return to the analysis of (4.1.3) and rewrite it as

$\displaystyle\bar{\psi}_{rd}^{(d,3)}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}(1-{\bf
p}_{2}{\bf q}_{2}){\bf c}_{2}+\frac{1}{2}({\bf p}_{2}{\bf q}_{2}-{\bf
p}_{3}{\bf q}_{3}){\bf c}_{3}-\gamma_{sq}^{(p)}$
$\displaystyle\quad-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}^{(p)}}\right)-\frac{1}{2{\bf
c}_{3}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf
c}_{3}({\bf q}_{2}-{\bf q}_{3})}{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}\right)$ $\displaystyle\quad+\frac{{\bf
q}_{3}}{2(2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf c}_{3}({\bf
q}_{2}-{\bf q}_{3}))}\Bigg{.}\Bigg{)}$
$\displaystyle\quad+\gamma_{sq}-\frac{\alpha}{{\bf
c}_{3}}{\mathbb{E}}_{{\mathcal{U}}_{4}^{(j_{w})}}\log\left({\mathbb{E}}_{{\mathcal{U}}_{3}^{(j_{w})}}\left({\mathbb{E}}_{{\mathcal{U}}_{2}^{(j_{w})}}e^{-{\bf
c}_{2}\frac{z_{i}^{(3)}\left(\bar{{\bf g}}^{(4)};\max\left({\bf
q}^{(net)},0\right)\right)}{4\gamma_{sq}}}\right)^{\frac{{\bf c}_{3}}{{\bf
c}_{2}}}\right)$ $\displaystyle=\frac{1}{2}(1-{\bf p}_{2}{\bf q}_{2}){\bf
c}_{2}+\frac{1}{2}({\bf p}_{2}{\bf q}_{2}-{\bf p}_{3}{\bf q}_{3}){\bf
c}_{3}-\gamma_{sq}^{(p)}$ $\displaystyle\quad-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}^{(p)}}\right)-\frac{1}{2{\bf
c}_{3}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf
c}_{3}({\bf q}_{2}-{\bf q}_{3})}{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}\right)$ $\displaystyle\quad+\frac{{\bf
q}_{3}}{2(2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf c}_{3}({\bf
q}_{2}-{\bf q}_{3}))}\Bigg{.}\Bigg{)}$
$\displaystyle\quad+\gamma_{sq}-\frac{\alpha}{{\bf
c}_{3}}{\mathbb{E}}_{g_{f}^{(4,3)}}\log\left({\mathbb{E}}_{g_{f}^{(4,2)}}\left({\mathbb{E}}_{g_{f}^{(4,1)}}e^{-{\bf
c}_{2}\frac{\left(\max\left(\bar{b}_{2}g_{f}^{(4,1)}+\bar{b}_{3}g_{f}^{(4,2)},0+\bar{b}_{4}g_{f}^{(4,3)},0\right)\right)^{2}}{4\gamma_{sq}}}\right)^{\frac{{\bf
c}_{3}}{{\bf c}_{2}}}\right).$ (158)

The very same remarkable property that was observed when considering the
second level of lifting right after (140), remains in place and one again
observes the structural identicalness between the expression in (4.1.3) and
the corresponding one given in equation (91) in [37]. As earlier, the adjusted
values $\bar{b}_{2}=\sqrt{\bar{p}_{1}-\bar{p}_{2}}$,
$\bar{b}_{3}=\sqrt{\bar{p}_{2}-\bar{p}_{3}}$, and
$\bar{b}_{4}=\sqrt{\bar{p}_{3}-\bar{p}_{4}}$ are the only difference. This
then enables us to solve the remaining integrals as in [37] and write

$\displaystyle\tilde{h}$ $\displaystyle=$
$\displaystyle-\frac{\sqrt{\bar{p}_{2}-\bar{p}_{3}}g_{f}^{(4,2)}+\sqrt{\bar{p}_{3}-\bar{p}_{4}}g_{f}^{(4,3)}}{\sqrt{\bar{p}_{1}-\bar{p}_{2}}}$
$\displaystyle\tilde{B}$ $\displaystyle=$ $\displaystyle\frac{{\bf
c}_{2}}{4\gamma_{sq}}$ $\displaystyle\tilde{C}$ $\displaystyle=$
$\displaystyle\sqrt{\bar{p}_{2}-\bar{p}_{3}}g_{f}^{(4,2)}+\sqrt{\bar{p}_{3}-\bar{p}_{4}}g_{f}^{(4,3)}$
$\displaystyle f_{(zd)}^{(3,f)}$ $\displaystyle=$
$\displaystyle\frac{e^{-\frac{\tilde{B}\tilde{C}^{2}}{2(\bar{p}_{1}-\bar{p}_{2})\tilde{B}+1}}}{2\sqrt{2(\bar{p}_{1}-\bar{p}_{2})\tilde{B}+1}}\mbox{erfc}\left(\frac{\tilde{h}}{\sqrt{4(\bar{p}_{1}-\bar{p}_{2})\tilde{B}+2}}\right)$
$\displaystyle f_{(zu)}^{(3,f)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\mbox{erfc}\left(-\frac{\tilde{h}}{\sqrt{2}}\right),$
$\displaystyle f_{(zt)}^{(3,f)}$ $\displaystyle=$ $\displaystyle
f_{(zd)}^{(3,f)}+f_{(zu)}^{(3,f)}.$ (159)

and

$\displaystyle{\mathbb{E}}_{g_{f}^{(4,3)}}\log\left({\mathbb{E}}_{g_{f}^{(4,2)}}\left({\mathbb{E}}_{g_{f}^{(4,1)}}e^{-{\bf
c}_{2}\frac{\left(\max\left(\bar{b}_{2}g_{f}^{(4,1)}+\bar{b}_{3}g_{f}^{(4,2)},0+\bar{b}_{4}g_{f}^{(4,3)},0\right)\right)^{2}}{4\gamma_{sq}}}\right)^{\frac{{\bf
c}_{3}}{{\bf
c}_{2}}}\right)={\mathbb{E}}_{g_{f}^{(4,3)}}\log\left({\mathbb{E}}_{g_{f}^{(4,2)}}\left(f_{(zt)}^{(3,f)}\right)^{\frac{{\bf
c}_{3}}{{\bf c}_{2}}}\right).$

Combining (4.1.3) and (4.1.3), we obtain

$\displaystyle\bar{\psi}_{rd}({\bf p},{\bf q},{\bf
c},\gamma_{sq},\gamma_{sq}^{(p)})$ $\displaystyle=\frac{1}{2}(1-{\bf
p}_{2}{\bf q}_{2}){\bf c}_{2}+\frac{1}{2}({\bf p}_{2}{\bf q}_{2}-{\bf
p}_{3}{\bf q}_{3}){\bf
c}_{3}-\gamma_{sq}^{(p)}-\Bigg{(}\Bigg{.}-\frac{1}{2{\bf
c}_{2}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}{2\gamma_{sq}^{(p)}}\right)$ $\displaystyle\quad-\frac{1}{2{\bf
c}_{3}}\log\left(\frac{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf
c}_{3}({\bf q}_{2}-{\bf q}_{3})}{2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf
q}_{2})}\right)$ $\displaystyle\quad+\frac{{\bf
q}_{3}}{2(2\gamma_{sq}^{(p)}-{\bf c}_{2}(1-{\bf q}_{2})-{\bf c}_{3}({\bf
q}_{2}-{\bf q}_{3}))}\Bigg{.}\Bigg{)}+\gamma_{sq}-\frac{\alpha}{{\bf
c}_{3}}{\mathbb{E}}_{g_{f}^{(4,3)}}\log\left({\mathbb{E}}_{g_{f}^{(4,2)}}\left(f_{(zt)}^{(3,f)}\right)^{\frac{{\bf
c}_{3}}{{\bf c}_{2}}}\right).$ (161)

Following what we presented in the earlier sections when we discussed the
second level of lifting and relying on [37], one proceeds by computing the
_eight_ derivatives with respect to ${\bf q}_{2}$, ${\bf q}_{3}$, ${\bf
p}_{2}$, ${\bf p}_{3}$, ${\bf c}_{2}$, ${\bf c}_{3}$, $\gamma_{sq}$, and
$\gamma_{sq}^{(p)}$. Keeping in mind very minimal adjustments for
$\bar{p}_{4}\neq 0$, the resulting derivatives are structurally identical to
the corresponding ones from [37]. The only small structural difference is that
for the ${\bf p}_{2}$ and ${\bf p}_{3}$ derivatives, a trivial additional
accounting for $\frac{d\bar{p}_{2}}{d{\bf p}_{2}}$, and
$\frac{d\bar{p}_{3}}{d{\bf p}_{3}}$ is needed as well. After computing all the
derivatives, one then solves the following system of equations

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

and denotes the obtained solution by $\hat{{\bf q}}_{2},\hat{{\bf
q}}_{3},\hat{{\bf p}}_{2},\hat{{\bf p}}_{3},\hat{{\bf c}}_{2},\hat{{\bf
c}}_{3},\hat{\gamma}_{sq}^{(p)},\hat{\gamma}_{sq}$. Moreover, the structural
identicalness also ensures that the following closed form relations,
established in [37], actually hold here as well

$\displaystyle\hat{\gamma}_{sq}^{(p)}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\frac{1-\hat{{\bf q}}_{2}}{1-\hat{{\bf
p}}_{2}}\frac{\hat{{\bf p}}_{2}-\hat{{\bf p}}_{3}}{\hat{{\bf q}}_{2}-\hat{{\bf
q}}_{3}}\sqrt{\frac{\hat{{\bf q}}_{3}}{\hat{{\bf p}}_{3}}}$
$\displaystyle\hat{{\bf c}}_{3}$ $\displaystyle=$
$\displaystyle\frac{1}{\hat{{\bf p}}_{2}-\hat{{\bf
p}}_{3}}\sqrt{\frac{\hat{{\bf p}}_{3}}{\hat{{\bf q}}_{3}}}-\frac{1}{\hat{{\bf
q}}_{2}-\hat{{\bf q}}_{3}}\sqrt{\frac{\hat{{\bf q}}_{3}}{\hat{{\bf p}}_{3}}}$
$\displaystyle\hat{{\bf c}}_{2}$ $\displaystyle=$
$\displaystyle\frac{1}{1-\hat{{\bf p}}_{2}}\frac{\hat{{\bf p}}_{2}-\hat{{\bf
p}}_{3}}{\hat{{\bf q}}_{2}-\hat{{\bf q}}_{3}}\sqrt{\frac{\hat{{\bf
q}}_{3}}{\hat{{\bf p}}_{3}}}-\frac{1}{1-\hat{{\bf q}}_{2}}\frac{\hat{{\bf
q}}_{2}-\hat{{\bf q}}_{3}}{\hat{{\bf p}}_{2}-\hat{{\bf
p}}_{3}}\sqrt{\frac{\hat{{\bf p}}_{3}}{\hat{{\bf q}}_{3}}}.$ (163)

After, taking concrete numerical values for all the considered parameters,
${\bf q}_{2}$, ${\bf q}_{3}$, ${\bf p}_{2}$, ${\bf p}_{3}$, ${\bf c}_{2}$,
${\bf c}_{3}$, $\gamma_{sq}$, and $\gamma_{sq}^{(p)}$, we then, from
$\bar{\psi}_{rd}^{(d,3)}(\hat{{\bf p}},\hat{{\bf q}},\hat{{\bf
c}},\hat{\gamma}_{sq},\hat{\gamma}_{sq}^{(p)})=0$, obtain for

$(\mbox{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\emph{full}
third level:}}})\qquad\qquad
a_{c}^{(3,f)}(\infty)=\lim_{d\rightarrow\infty}a_{c}^{(3,f)}(d)\approx{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\mathbf{2.6534}}.$
(164)

_Concrete numerical values:_ In Table 3, the concrete values of all the
relevant quantities related to the third _full_ (3-sfl RDT) level of lifting,
complement the above $a_{c}^{(3,f)}(\infty)$. A systematic view of the lifting
progress is also enabled, by showing in parallel the corresponding quantities
for the first _full_ (1-sfl RDT) and the second _partial_ (2-spl RDT) and
_full_ (2-sfl RDT) levels as well.