# Fixed width treelike neural networks capacity analysis – generic activations

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

We consider the capacity of _treelike committee machines_ (TCM) neural
networks. Relying on Random Duality Theory (RDT), [42] recently introduced a
generic framework for their capacity analysis. An upgrade based on the so-
called _partially lifted_ RDT (pl RDT) was then presented in [45]. Both lines
of work focused on the networks with the most typical, _sign_ , activations.
Here, on the other hand, we focus on networks with other, more general, types
of activations and show that the frameworks of [42, 45] are sufficiently
powerful to enable handling of such scenarios as well. In addition to the
standard _linear_ activations, we uncover that particularly convenient results
can be obtained for two very commonly used activations, namely, the
_quadratic_ and _rectified linear unit (ReLU)_ ones. In more concrete terms,
for each of these activations, we obtain both the RDT and pl RDT based memory
capacities upper bound characterization for _any_ given (even) number of the
hidden layer neurons, $d$. In the process, we also uncover the following two,
rather remarkable, facts: 1) contrary to the common wisdom, both sets of
results show that the bounding capacity decreases for large $d$ (the width of
the hidden layer) while converging to a constant value; and 2) the maximum
bounding capacity is achieved for the networks with precisely _two_ hidden
layer neurons! Moreover, the large $d$ converging values are observed to be in
excellent agrement with the statistical physics replica theory based
predictions.

Index Terms: TCM neural networks; Capacity; Lifted random duality theory;
Different activations.

##  1 Introduction

Demand for efficient handling and interpretation of large data sets, has grown
rather rapidly over the last 15-20 years. Machine learning (ML) clearly
distinguished itself as a particularly helpful set of concepts capable of
providing the needed technical and scientific resources to meet such a high
demand. Consequently, a fast development of various ML branches ensued. Neural
networks (NN), as one of such branches, quickly became one of the focuses of
strong research interests and among the fastest growing research fields. Many
great results and quite a few remarkable breakthroughs that relate to both
theoretical and practical NN aspects have been obtained. Moreover, many of the
well known results achieved in prior decades – that for a long time served as
academic prototypes – have been revisited and brought to practical usability.
Among the most prominent of them are certainly those that relate to one of the
key NN features, the so-called, network’s _memory capacity_ (see, e.g., [26,
9, 52, 51, 50, 8, 22, 16, 48, 3]). Here we continue the same trend and focus
on several important capacity related questions and provide a strong
theoretical progress. Before discussing in more detail some of the main
problems and our technical contributions, we find it convenient to first
introduce the basics of the NN models of our interest.

###  1.1 Feed forward neural networks – mathematical basics

To be able to properly introduce the network’s memory capacity as the main
object of our interest, we first discuss the underlying network architecture.

_Architecture:_ We are interested in multilayered 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. To ensure a
notational facilitation, two additional layers, indexed by $i=1$ and $i=L$ are
artificially added and they correspond to the network input and output,
respectively (although the input and output of the network are basically
artificial NN layers, to be in agreement with the introduced indexation, we
will refer to them as networks layers). The way the network operates is
basically determined by specifying the vectors of threshold functions, ${\bf
f}^{(i)}(\cdot)=[{\bf f}_{1}^{(i)}(\cdot),{\bf f}_{2}^{(i)}(\cdot),\dots,{\bf
f}_{d_{i+1}}^{(i)}(\cdot)]^{T}$. Each threshold function ${\bf
f}_{j}^{(i)}(\cdot):{\mathbb{R}}^{d_{i}}\rightarrow{\mathbb{R}}$ describes how
neuron $j$ in layer $i$ operates. The network effectively functions by taking
the outputs of the nodes from layer $i$ as the inputs of the nodes in layer
$i+1$ and transforming them into the new outputs (in layer $i+1$) via a linear
combination governed by the matrix of weights
$W^{(i)}\in{\mathbb{R}}^{d_{i}\times d_{i+1}}$. After 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}},i=1,2,\dots L$ the so-called
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)

The architecture of the network, $A({\bf d};{\bf f}^{(i)})$, is fully
specified by the vectors ${\bf d}$ and ${\bf f}^{(i)}$. Also, when the vectors
of functions, ${\bf f}^{(i)}$, are identical, we write $A({\bf d};{\bf f})$
instead of $A({\bf d};{\bf f}^{(i)})$.

_Memory capacity:_ As mentioned earlier, one of the most fundamental features
of any neural net (including single neurons as special cases) is their ability
to properly memorize/store a large amount of data. A simple way to see how the
above formalism achieves this is the following: assume 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 associated labels.
Determining 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 properly relate given data vectors to their
corresponding labels. If the network architecture $A({\bf d},{\bf f}^{(i)})$
is given then its _memory capacity, $C(A({\bf d},{\bf f}^{(i)}))$,_ is 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. Since the memory capacity plays one of the most
important roles in understanding the overall neural nets’ functioning mosaic,
finding both, its precise theoretical characterization and the corresponding
fast algorithmic procedure that achieves it, is of utmost importance. Of our
particular interest in this paper are the theoretical aspects and we below
provide a host of results that for many well known architectures almost fully
characterize their capacities.

To facilitate the presentation, a few structural and technical assumptions are
in place as well. Many of them, however, are aligned with the ones discussed
in [42, 45]. To avoid an unnecessary repetition, we only briefly recall on
these and refer for a more detailed exposition to [42, 45]. On the other hand,
we place the most emphasis on those that are substantially different and
particularly relevant to the results that we present in this paper.

###  1.2 Technical assumptions

To facilitate the exposition and to make the final results cleaner and easier
to use, we will rely on several architectural and data related assumptions. We
state them below before starting the analytical considerations. As they are
fairly common and rather prevalent in the literature, we avoid discussing them
in deep details.

_Network architecture assumptions:_ 1-hidden layer _treelike committee
machine_ type of neural networks with _generic_ zero-threshold activation
functions in the hidden layer are considered. This means the following: _(i)_
We assume $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}$ (i.e. $W^{(3)}$ is a
$d_{2}$-dimensional row vector that will be specified depending on the type of
the considered activation functions). _(ii)_ We also define $d\triangleq
d_{2}$ and $\delta\triangleq\delta_{1}=\frac{d_{1}}{d_{2}}=\frac{n}{d}$. While
the presented mathematical concepts will hold for any $d$, to be able to get
concrete capacity values, we eventually assume that $d$ is any (even) natural
number. _(iii)_ In the first layer, we consider _identity_ neuronal functions,
i.e. we take ${\bf f}^{(1)}({\bf x}^{(1)})={\bf x}^{(1)}$. In the hidden
layer, we take the _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$. Finally, at
the output, we take zero-threshold sign activation ${\bf f}^{(3)}(W^{(3)}{\bf
x}^{(3)}-{\bf b}^{(3)})=\mbox{sign}\left(W^{(3)}{\bf x}^{(3)}\right)$. For
notational simplicity, 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
$W^{(i)}$ can be generically full or with a particular structure. Both types
of structuring have been of interest throughout the literature. A particular
type of sparse structuring, where the support of $W^{(i)}$’s $j$-th row,
$\mbox{supp}\left(W_{j,:}^{(i)}\right)$, satisfies
$\mbox{supp}\left(W_{j,:}^{(i)}\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 what is in the literature referred
to as the _treelike committee machines_ (TCM). Precisely such architectures
will be of our interest in this paper. For the completeness, we also add that
if the matrix is full then the above architecture corresponds to what is in
the literature typically referred to as the _fully connected committee
machines_ (FCM).

_Data related assumptions:_ _(i)_ _Binary_ labeling ${\bf
y}_{i}^{(0,k)}\in\\{-1,1\\}$, as the most standard type of labeling, is
assumed as well (choosing _sign_ perceptron as neuronal function at the output
naturally complements the binary labeling choice as well). _(ii)_ Inseparable
data sets are not allowed (for example, indistinguishable/contradictory pairs
(or subgroups) like $({\bf x}^{(0,k)},{\bf y}^{(0,k)})$ and $({\bf
x}^{(0,k)},-{\bf y}^{(0,k)})$ can not appear). _(iii)_ Data sets of
statistical nature will be of our main interest. We particularly focus on
${\bf x}^{(0,k)}$ as iid standard normals. This follows into the footsteps of
the trend established in the classical single perceptron references (see,
e.g., [12, 16, 34, 9, 52, 51, 50]) and allows for, expectedly, a fairly
universal statistical treatment. It is also useful to note that for providing
universal capacity upper bounds, any type of acceptable data set (including
even nonstatistical ones) actually suffices.

###  1.3 Prior work

The problems of our interest are well known and have been studied in various
forms for almost 70 years. Naturally, the early studies related to the single
neurons while the more recent ones emphasize the importance of understanding
the multi-neuron or multi-layered architectures. Given the pace at which the
ML and NN fields are developing, the underlying relevant literature is rather
vast and growing. We below highlight the results that we view as most closely
related to our own.

Since the memory capacity of spherical perceptrons is directly connected to
several fundamental questions in integral geometry, the early capacity
considerations were related to some of the geometrical/probabilistic classic
works (see, e.g., [26, 9, 50, 22]). Possibly the most famous of them states
that the capacity of the spherical _sign_ perceptrons _doubles the dimension_
of the data ambient space, $n$, i.e., $C(A(1;\mbox{sign}))\rightarrow 2n$ as
$n\rightarrow\infty$. After being initially obtained as a remarkable closed
form combinatorial geometry fact in [26, 9, 52, 51, 50, 8, 22], it was decades
later rediscovered and reproved in various different forms in a plethora of
different fields ranging from machine learning and pattern recognition to
information theory, probability, and statistical physics (see, e.g., [3, 48,
10, 33, 11, 12, 16, 34, 40]).

_Sign perceptrons networks:_ Despite the elegance of the single perceptron
results, the corresponding multi-perceptron ones are not easy to obtain.
Particularly scarce are the TCM related ones. While a bit more is known about
the FCM ones, a direct connection between the two is not apparent. Besides the
trivial fact that the FCM capacities upper-bound the corresponding TCM ones,
one may also (somewhat ad-hoc) view the TCM capacities as roughly the FCM ones
divided by $d$. Although non necessarily rigorous (or even fully correct) such
a viewing suggests a potential usefulness of FCM results. Still, an
overwhelming majority of known results indicates that the memory capacity is
unavoidably related 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
_qualitative_ memory capacity upper bound gives the scaling $O(w\log(w))$. It
is interesting to note that for NNs with 1-hidden layer,
$w=d_{1}d_{2}+d_{2}=(n+1)d$ for FCM and $w=d_{1}+d_{2}=n+d$ for TCM. This, on
the other hand, for large $d_{i}$’s and huge $n$, gives, the above mentioned,
“ _division by $d$_” FCM – TCM capacity relation. A couple of lower bounding
results are known as well. For example, [7] argued that the capacity of a
shallow 3-layer network (similar to the one studied here) scales as $O(nd)$.
On the other hand, [49] obtained recently a stronger version, where, for the
networks with more than three layers, the capacity is shown to be roughly at
least $O(w)$.

Obtaining precise results of _non-scaling_ type in network architectures
turned out to be a much harder challenge. This seems particularly surprising
given the simplicity and elegance of the corresponding single perceptron ones.
Until the very recent appearance of [45, 42] there was hardly any
mathematically rigorous result that could provide even remotely close sign
perceptron networks capacity estimates. [42] utilized the Random duality
theory (RDT) and developed a generic framework for the analysis of TCM network
capacities. As a results of the framework, strong upper bounds were obtained
for any given (odd) number of the nodes in the hidden layer. [45] went a step
further, utilized a partially lifted RDT variant (pl RDT) and substantially
lowered the upper bounds of [42].

_Different activations networks:_ Given the importance of a single sign
perceptron, studying their merging into a large architectural structure is a
natural transition. Two things should be kept in mind when making such a
transition though. First, it is not clear a priori that the results that hold
for the single perceptron will hold in a similar fashion for the network of
perceptrons. Second, the sign perceptrons are not continuous functions and
handling them algorithmically when using or training the network might impose
computationally/numerically unsurpassable obstacles. If on top of that, one
adds the above mentioned analytical hardness, the need for potentially less
simple but easier to use activation factions is rather obvious.

As the discreteness is typically perceived as the main source of both
analytical and algorithmic sign perceptrons hardness, the natural choice for
different activations leads towards allowing various continuous ones as well.
Many of them have already found a steady place in NN architectures. Examples
include but are not limited to ReLU, quadratic, tanh, erf and so on. Such
activations make things a bit easier and, consequently, a little bit more is
known about their capacities. For example, [54] suggested for deep nets and
[20] proved for 4-layer nets that the capacity is at least $O(w)$ for
sigmoids. [57, 19] showed similar results for ReLU while additionally
restricting on the number of nodes. Such a restriction though was later on
removed in [55] for both tanh and ReLU.

_Statistical physics – Replica theory:_ Given that the _precise_ capacity
characterizations (as functions of the number of the hidden layer neurons $d$)
do not allow for any _qualitative/scaling_ descriptions (say, of the
$O(\cdot)$ type), the mathematically rigorous results are often very hard to
achieve. In such situations, statistical physics replica methods are an
excellent (and often irreplaceable) tool to produce, non-rigorous, but
expectedly _precise_ analyses. As the hardness of the precise analytical
studying of various NN features has been recognized in the mid-eighties of the
last century, the application of the replica methods in capacity
characterization has been around for close to four decades. The foundational
concepts of such an approach were laid out in the pioneering works [17, 16],
whre various forms of single perceptrons were discussed. Here, we focus more
on the ensuing ones that relate to the network architectures. In particular,
[14, 5] studied the very same, TCM architecture, as we do (as well as the
above mentioned, related, FCM one). For the sign perceptrons, they obtained
the closed form replica symmetry based capacity predictions for any number of
the neurons in the hidden layer, $d$. They established the corresponding large
$d$ scaling behavior. Both of these results were proven as mathematically
rigorous capacity upper bounds in [45, 42]. Moreover, [14, 5] showed that
their replica symmetry based large $d$ predictions violate the mathematically
rigorous ones obtained through the uniform-bounding extension of [9, 52, 51,
50] given in [15]. This contradiction was remedied in [14, 5] by studying the
first level of replica symmetry breaking (rsb) and showing that it lowers the
capacity. Related large $d$ scaling rsb considerations were also presented in
[24] for both the committee and the so-called parity machines (PM) (more on
the earlier PM replica considerations can be found in, e.g., [6, 4]). Also,
for the FCM architecture, a bit later, [47, 53] obtained the large $d$ scaling
that matches the upper-bounding one of [15]. Particularly relevant to our work
are two very recent lines of work. [2] first obtained the first level of rsb
capacity predictions for the TCM architectures with the ReLU activations and
[56] moved things even further and obtained similar rsb predictions for
several different activations, including the well known linear, ReLU, erf,
quadratic, and tanh. A key difference with respect to our results should also
be noted. Namely, both sets of results, [2] and [56], relate to the networks
with large $d$ (basically, to the networks with $d\rightarrow\infty$), whereas
our results are obtained for any given (even) $d$.

_Practical achievability:_ Another line of work attracted a lot of interest
over the last several years and should be mentioned as well. It is related to
the design and analysis of efficient algorithms that can be used to train the
networks to potentially approach the capacity. The key focus has been on
showing that the simple gradient based methods might actually perform quite
well in this context. The so-called mild over-parametrization (moderately
larger number of free parameters, $w$, compared to the size of the data set,
$m$) is deemed as sufficing to ensure excellent performance of gradient based
methods. More on the recent progress in these directions can be found in,
e.g., [13, 18, 1, 21, 23, 25, 46, 27, 58]. These results mostly relate to FCMs
but are also extendable to TCMs as well.

###  1.4 Contributions

The main object of our study is the so-called $n$-scaled memory capacity of
the TCM NNs with various (different from standard _sign_ one) activation
functions in the hidden layer. In other words, we study

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

A very strong progress in characterizing $C(A([n,d,1];\mbox{sign}))$ for any
given (odd) $d$ has been made in [42]. In particular, utilizing the powerful
Random Duality Theory (RDT) mathematical engine, [42] provides an explicit
upper bound $\hat{c}(d;\mbox{sign})$ on $c(d;\mbox{sign})$. Numerical results
obtained for smaller values of $d$ suggested a strong benefit in adding more
neurons in a network architecture context. On the other hand, we, in this
paper, make a substantial progress in several different aspects including both
methodological and practical ones.

_A summary of the main technical results of the paper:_ _(i)_ We first show
that the main framework from [42, 45] (established relying on the RDT and pl
RDt principles) for the capacity analysis of sign perceptron networks can be
utilized for different activations as well. _(ii)_ To produce concrete
capacity estimates, we then focus on several particular activations for which
neat and convenient results can be obtained. We fist start with the _linear_
activations and show that the capacity of the TCM network with one hidden
layer network is identical to the single spherical perceptron. We then switch
to the _quadratic_ activations and obtain the close form analytical RDT based
capacity upper bounds and their refined pl RDT counterparts. Finally, we
consider the _ReLU_ activations and obtain the corresponding analytical closed
form RDT and pl RDT results. _(iii)_ For all activations, we conduct the
needed numerical evaluations to obtain the concrete capacity values as well.
_(iv)_ All our results are obtained for an extremely challenging scenario
where the number of the hidden layer neurons, $d$, can be any even positive
integer. This allows us to uncover two rather fascinating phenomena: 1) Both
thr RDT and the pl RDT estimates are decreasing for large $d$ while converging
to a _constant_ (not dependent on $d$) value; and 2) The maxima of both
estimates for both quadratic and ReLU activations are achieved for $d=2$
neurons in the hidden layer. This is a bit contrary to the common wisdom and
in a strike contrast with the corresponding behavior of the sign activations
where the capacity estimates grow with $d$. In particular, one effectively has
that when it comes to the memory capabilities, uncontrollably increasing the
width of the hidden layer may not always be among the most recommended
architecture building strategies.

We show some of the concrete capacity estimates that we obtained for all the
three mentioned activations, linear, quadratic, and ReLU, in Table 1. In
Figure 1 we also visualize the quadratic ones as well. Few key smallest values
of $d$ are shown explicitly in the table and a much wider range of $d$ is
shown in the figure (it goes without saying that the quadratic activation for
$d=1$ does not make sense). For the completeness, we, in Figure 1, also show
the $d\rightarrow\infty$ asymptotics obtained for quadratic activations
utilizing the replica methods in [56].

Table 1: Theoretical estimates of the ${\bf f}^{(2)}$-activated hidden layer TCM capacity upper bounds Activation | Upper bound on | Methodology | $d$
---|---|---|---
(function) | $c(d;{\bf f}^{(2)})\triangleq\lim_{n\rightarrow\infty}\frac{C(A([n,d,1];{\bf f}^{(2)}))}{n}$ |  | $\mathbf{1}$ | $\mathbf{2}$ | $\mathbf{4}$
_linear_ | $\bar{c}(d;{\bf f}^{(2)})$ |  RDT | $\mathbf{2}$ | $\mathbf{2}$ | $\mathbf{2}$
(${\bf f}^{(2)}({\bf x})={\bf x}$) |  $\hat{c}(d;{\bf f}^{(2)})$ | pl RDT | $\mathbf{2}$ | $\mathbf{2}$ | $\mathbf{2}$
_quadratic_ | $\bar{c}(d;{\bf f}^{(2)})$ |  RDT | $\mathbf{-}$ | $\mathbf{5.498}$ | $\mathbf{4.660}$
(${\bf f}^{(2)}({\bf x})={\bf x}^{2}$) |  $\hat{c}(d;{\bf f}^{(2)})$ | pl RDT | $\mathbf{-}$ | $\mathbf{4.065}$ | $\mathbf{3.657}$
_ReLU_ | $\bar{c}(d;{\bf f}^{(2)})$ |  RDT | $\mathbf{2}$ | $\mathbf{3.810}$ | $\mathbf{3.066}$
(${\bf f}^{(2)}({\bf x})=\max({\bf x},0)$) |  $\hat{c}(d;{\bf f}^{(2)})$ | pl RDT | $\mathbf{2}$ | $\mathbf{3.810}$ | $\mathbf{3.066}$

Figure 1: Memory capacity upper bound as a function of the number of neurons,
$d$, in the hidden layer; 1-hidden layer TCM with _quadratic_ activations;
_plain_ RDT versus _partially lifted_ RDT (Replica symmetry (RS) and Partial
1rsb $d\rightarrow\infty$ estimates are included as well)

##  2 Algebraic description of network data processing

To put everything on the right mathematical track and facilitate writing and
overall presentation, we first set $W\triangleq W^{(2)}$. After recalling that
$W^{(1)}=I$ and $W^{(3)}={\bf w}^{T}$, we then have 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)

A very neat closed-form explicit relation between the input and the output of
the network can be obtained by connecting beginning in (4) and end in (6)

${\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)

For network to operate properly, it is then both necessary and sufficient that
the following condition holds

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

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)

one can then rewrite (8) 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)

and the $k$-th data pair $\left({\bf x}^{(0,k)},{\bf y}^{(0,k)}\right)$ are
the $k$-th rows of $m\times n$ matrix $X$ and $m\times 1$ column vector ${\bf
y}$. This further leads to the following (effectively an 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.

Clearly, the above algebraic formulation is the key mathematical problem on
the path towards ensuring proper network data memorization. We therefore
analyze it below in more detail.

##  3 Random Duality Theory (RDT) based capacity analysis

As mentioned earlier, we consider statistical data sets with elements of $X$
being iid standard normals. Due to rotational symmetry, one can then, without
a loss of generality, assume that the elements of ${\bf y}$ are all equal to
1, i.e. one can assume that ${\bf y}={\bf 1}$. The above key optimization can
then be rewritten

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

where a cosmetic change, $Z=W^{T}$, is introduced to facilitate writing. As in
[45, 42], we here consider the TCM architecture, with a sparse $Z$ that
ensures that treelike network architecture. This basically means that we
consider $Z$ such that the only nonzero elements of its $j$-th column are in
rows
${\mathcal{S}}^{(j)}\triangleq\\{(j-1)\delta+1,(j-1)\delta+2,\dots,j\delta\\}$.
Utilizing this $Z$ specialization and given that the above problem is
insensitive with respect to the scaling of $Z$ or $Q$, one can 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}\|_{2}$ being the norm of the $j$-th column of $Z$. A further
trivial rewriting of the above 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}$. We
follow into the footsteps of [45, 42] and to statistically analyze the
optimizations in (3) and (3), we utilize the powerful mathematical engine
called Random Duality Theory (RDT) developed in a long series of work [30, 32,
28, 31, 39]. To make the presentation easier to follow, we will try to
parallel as closely as possible the approach presented in [42]. However, to
avoid unnecessary repetitions, we only briefly recall on some of the concepts
that are identical or very similar to the corresponding ones of [42], and
instead focus on key differences. As in [42], we start by first summarizing
the RDT main principles and then continue by discussing each of them within
the context of our interest here.

Summary of the RDT’s main principles [30, 39]
$\displaystyle\begin{array}[]{ll}\mbox{1) \emph{Finding underlying
optimization algebraic representation}}&\mbox{2) \emph{Determining the random
dual}}\\\ \mbox{3) \emph{Handling the random dual}}&\mbox{4) \emph{Double-
checking strong random duality.}}\end{array}$

As in [42], all the key results (including both simple to more complicated
ones) are formulated as lemmas and theorems.

1) _Algebraic memorization characterization:_ The following lemma summarizes
the above algebraic discussion by providing a precise resulting optimization
representation of the network memorization property and is a mirrored analogue
to Lemma 1 in [42].

######  Lemma 1.

(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,$ (16)

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),$ (17)

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 [42]. ∎

Of our interest below is mathematically the most challenging, so-called
_linear_ , regime with

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

The above lemma is of purely algebraic nature and as such it holds for any
given data set $\left({\bf x}^{(0,k)},1\right)_{k=1:m}$. To analyze (16) and
(17), the RDT further proceeds by accounting for a statistical $X$.

2) _Determining the random dual:_ We follow the standard RDT practice and
utilize the so-called concentration of measure property, which basically means
that for any fixed $\epsilon>0$, we have (see, e.g. [30, 39, 32, 42, 45])

$\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}\left(\frac{|f_{rp}(X)-{\mathbb{E}}_{X}(f_{rp}(X))|}{{\mathbb{E}}_{X}(f_{rp}(X))}>\epsilon\right)\longrightarrow
0.$ (19)

Moreover, the following so-called random dual theorem is another key
ingredient of the RDT machinery and is a mirrored alternative to Theorem 1
from [42].

######  Theorem 1.

(Memorization characterization via random dual) Let $d$ be any even positive
integer. Consider TCM with $d$ neurons in the hidden layer, and architecture
$A([n,d,1];{\bf f}^{(2)})$, and let the elements of $X\in{\mathbb{R}}^{m\times
n}$, $G\in{\mathbb{R}}^{m\times d}$, and $H\in{\mathbb{R}}^{\delta\times d}$
be iid standard normals. Set

$\displaystyle\phi(Q)$ $\displaystyle\triangleq$ $\displaystyle\|{\bf
1}-\mbox{\emph{sign}}({\bf f}^{(2)}(Q){\bf w})\|_{2}$ $\displaystyle
f_{rd}(G,H)$ $\displaystyle\triangleq$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0,\|{\bf
z}^{(j)}\|_{2}=1}\max_{\Lambda\in R^{m\times d},\|\Lambda\|_{F}=1}\left({\rm
tr}\,(\Lambda^{T}G)+\sum_{j=1}^{d}\|\Lambda_{:,j}\|_{2}(H_{:,j})^{T}{\bf
z}^{(j)}-{\rm tr}\,(\Lambda^{T}Q)\right)$ $\displaystyle\phi_{0}$
$\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}f_{rd}(G,H).\vspace{-.0in}$
(20)

One then has

$\displaystyle(\phi_{0}>0)$ $\displaystyle\Longrightarrow$
$\displaystyle\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(f_{rd}>0)\longrightarrow
1\right)\quad\Longrightarrow\quad\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(f_{rp}>0)\longrightarrow
1\right)$ (21) $\displaystyle\Longrightarrow$
$\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.

Immediate consequence of Theorem 1 in [42]. ∎

3) _Handling the random dual:_ Proceeding as in [42], one first solves the
inner maximization over $\Lambda$ and then the minimization over ${\bf
z}^{(j)}$ to obtain for $f_{rd}(G,H)$ from (20)

$\displaystyle f_{rd}(G,H)$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\sqrt{\|G-Q\|_{F}^{2}-2\sum_{j=1}^{d}\|G_{:,j}-Q_{:,j}\|_{2}\|H_{:,j}\|_{2}+\|H\|_{F}^{2}}.$
(22)

This then further gives

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}f_{rd}(G,H)=\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1,$
(23)

where, as discussed in [42], the above equality obtained relying on the
concentrations can be replaced by an inequality if one alternatively relies on
the Cauchy-Schwartz inequalities (both options are perfectly sufficient for
the subsequent analysis).

The remaining focus is on the residual optimization over $Q$. To that end we
set

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

and further write

$\displaystyle\min_{\phi(Q)=0}\|G-Q\|_{F}$ $\displaystyle=$
$\displaystyle\sqrt{\min_{\phi(Q)=0}\sum_{i=1}^{m}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}}=\sqrt{\sum_{i=1}^{m}\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}}$
(25) $\displaystyle=$ $\displaystyle\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})},$

with

$z_{i}(G_{i,1:d})\triangleq\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}.$
(26)

To further facilitate writing and remove unnecessary notations, we will set

$\displaystyle{\bf g}$ $\displaystyle\triangleq$ $\displaystyle G_{i,1:d}^{T}$
$\displaystyle{\bf q}$ $\displaystyle\triangleq$ $\displaystyle
Q_{i,1:d}^{T},$ (27)

and

$z_{i}({\bf g};{\bf f}^{(2)})\triangleq
z_{i}(G_{i,1:d})=\min_{\phi_{i}(Q_{i,1:d})=1}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf
f}^{(2)}(Q_{i,1:d}){\bf w}\geq 0}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf
f}^{(2)}({\bf q}^{T}){\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}.$ (28)

The above mechanism is generic and in principle applies to any type of
activation ${\bf f}^{(2)}$. To obtain concrete capacity estimates, we below
proceed by considering several particular activation examples that have
attracted a significant attention in NN literature.

###  3.1 Different ${\bf f}^{(2)}$ activations

We focus on three well known ${\bf f}^{(2)}$ activations: i) _linear_ , ii)
_quadratic_ , and iii) _ReLU_. For each of them we obtain relatively elegant
final capacity bounding estimates.

####  3.1.1 Linear hidden layer activations – ${\bf f}^{(2)}({\bf x})={\bf x}$

Since the linear function is odd (i.e., since $f^{(2)}(-{\bf x})=-{\bf
x}=-{\bf f}^{(2)}({\bf x})$), we can, without a loss of generality, assume
that, say, ${\bf w}={\bf 1}$, where ${\bf 1}$ is the column vector of
appropriate dimension with all of its components equal to one. However, as the
analysis below shows, linearity is a very particular form of activation where
such an assumption is actually not needed. In fact, any ${\bf w}$ suffices.
This should be kept in mind for later on when we study other two types of
activations where ${\bf w}$ will have to take particular forms to ensure that
network functioning actually makes sense at all. From (24) and (26), we then
recognize the key optimization problem of interest

$z_{i}(G_{i,1:d})=\min_{\mbox{sign}({\bf f}^{(2)}(Q_{i,1:d}){\bf
w})=1}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf f}^{(2)}(Q_{i,1:d}){\bf
w}\geq 0}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}.$ (29)

For the linear activation, one can then rewrite (29) as

$z_{i}({\bf g};\mbox{lin})=z_{i}(G_{i,1:d})=\min_{{\bf f}^{(2)}(Q_{i,1:d}){\bf
w}\geq 0}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf f}^{(2)}({\bf
q}^{T}){\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}=\min_{{\bf q}^{T}{\bf w}\geq
0}\|{\bf g}-{\bf q}\|_{2}^{2}.$ (30)

Proceeding by writing Lagrangian, we then further have

$z_{i}({\bf g};\mbox{lin})=\min_{{\bf q}^{T}{\bf w}\geq 0}\|{\bf g}-{\bf
q}\|_{2}^{2}=\min_{{\bf q}}\max_{\lambda\geq 0}\|{\bf g}-{\bf
q}\|_{2}^{2}-\lambda({\bf q}^{T}{\bf w}).$ (31)

Relying on the strong duality, one then also finds

$z_{i}({\bf g};\mbox{lin})=\min_{{\bf q}}\max_{\lambda\geq 0}\|{\bf g}-{\bf
q}\|_{2}^{2}-\lambda({\bf q}^{T}{\bf w})=\max_{\lambda\geq 0}\min_{{\bf
q}}\|{\bf g}-{\bf q}\|_{2}^{2}-\lambda({\bf q}^{T}{\bf w}).$ (32)

To solve the inner optimization over ${\bf q}$, we then consider the following
derivative

$\frac{d\left(\|{\bf g}-{\bf q}\|_{2}^{2}-\lambda({\bf q}^{T}{\bf
w})\right)}{d{\bf q}}=2({\bf q}-{\bf g})+\lambda{\bf w}.$ (33)

After equalling the above derivative to zero one then finds

${\bf q}={\bf g}-\frac{\lambda{\bf w}}{2}.$ (34)

Plugging back this value in the objective in (32), one obtains

$z_{i}({\bf g};\mbox{lin})=\max_{\lambda\geq 0}\min_{{\bf q}}\|{\bf g}-{\bf
q}\|_{2}^{2}-\lambda({\bf q}^{T}{\bf w})=\max_{\lambda\geq
0}-\frac{\lambda^{2}\|{\bf w}\|_{2}^{2}}{4}-\lambda{\bf g}^{T}{\bf w}.$ (35)

Optimizing further over $\lambda$, one finds

$\lambda_{opt}=\max\left(-\frac{2{\bf g}^{T}{\bf w}}{\|{\bf
w}\|_{2}^{2}},0\right).$ (36)

After plugging $\lambda_{opt}$ back in (35), one obtains

$z_{i}({\bf g};\mbox{lin})=\frac{\left(\max\left(-{\bf g}^{T}{\bf
w},0\right)\right)^{2}}{\|{\bf w}\|_{2}^{2}}=\left(\max\left(-{\bf
g}^{T}\frac{{\bf w}}{\|{\bf
w}\|_{2}},0\right)\right)^{2}=\left(\max\left(g_{i},0\right)\right)^{2},$ (37)

where $g_{i}$ is a standard normal random variable. Connecting (23), (25),
(30), and (37), we finally have

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1$
(38) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})}-1$
$\displaystyle=$ $\displaystyle\sqrt{\alpha{\mathbb{E}}z_{i}({\bf
g};\mbox{lin})}-1$ $\displaystyle=$
$\displaystyle\sqrt{\alpha{\mathbb{E}}\left(\max\left(g_{i},0\right)\right)^{2}}-1$
$\displaystyle=$ $\displaystyle\sqrt{\frac{\alpha}{2}}-1.$

We summarize the above results in the following lemma.

######  Lemma 2.

(Memory capacity; linear activation) Assume the setup of Theorem 1. For linear
${\bf f}^{(2)}({\bf x})={\bf x}$, let $c(d;\mbox{lin})\triangleq c(d;{\bf
f}^{(2)}({\bf x})={\bf x})$ be the $n$-scaled memory capacity from (3). One
then has the following for such

($n$-scaled) memory capacity: $\displaystyle c(d;\mbox{lin})=\mathbf{2}.$

If and only if the sample complexity $m$ is such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}\geq c(d;\mbox{lin})$
then

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];\mbox{sign})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1.$ (39)

###### Proof.

Follows immediately from the above discussion. ∎

The above lemma effectively states that only when the sample complexity $m$ is
such that $m>2n$ (with $n$ being the data vectors’ ambient dimension) the
network fails to memorize the data. Consequently, one has for the memory
capacity of the $d$ hidden layer _linearly_ activated neurons TCMs,
$C(A([n,d,1];\mbox{lin}))=2n$. This shows that the capacity does not change as
the width of the hidden layer increases. Moreover, it shows that the capacity
remains equal to the capacity of the single spherical perceptron neuron (see,
e.g., [26, 9, 52, 51, 50, 8, 22, 3, 48, 10, 33, 11, 12, 16, 34, 40]).

4) _Double checking the strong random duality:_ Strictly speaking the above
analysis establishes the upper bound on the capacity. However, given the
presence of the underlying convexity and the strong deterministic duality, the
machinery of [39, 29, 37] ensures that the strong random duality is in place
as well which then implies that the established upper bounds are in fact
tight.

####  3.1.2 Quadratic hidden layer activations – ${\bf f}^{(2)}({\bf x})={\bf
x}^{2}$

Since the quadratic function ${\bf f}^{(2)}({\bf x})={\bf x}^{2}\geq 0$ one
needs to carefully make a choice for vector ${\bf w}$ which ensures that the
network functioning is of any use. Clearly, some of the components of ${\bf
w}$ must be negative. Given the symmetry of the quadratic function, a natural
choice that is typically considered in the literature in such situations is
${\bf w}$ with $\frac{d}{2}$ 1s and $\frac{d}{2}$ -1s. For the concreteness,
we set

${\bf w}=\begin{bmatrix}-{\bf 1}_{\frac{d}{2}\times 1}\\\ {\bf
1}_{\frac{d}{2}\times 1}\end{bmatrix},$ (40)

and to facilitate exposition avoid dimensional subscripts and simply write

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

assuming that the size of the column vectors ${\bf 1}$ is $\frac{d}{2}\times
1$. As earlier, relying on (24), (26), (3), and (29), we then recognize the
following key optimization problem of interest

$z_{i}({\bf g};\mbox{quad})=z_{i}(G_{i,1:d})=\min_{{\bf
f}^{(2)}(Q_{i,1:d}){\bf w}\geq 0}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf
f}^{(2)}({\bf q}^{T}){\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}=\min_{({\bf
q}^{2})^{T}{\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}.$ (42)

After effectively splitting the problem into two parts, an interesting
formulation can be obtained

$\displaystyle z_{i}({\bf g};\mbox{quad})=\min_{{\bf q}}$
$\displaystyle\sum_{i=1}^{\frac{d}{2}}({\bf g}_{i}-{\bf
q}_{i})^{2}+\sum_{i=\frac{d}{2}+1}^{d}({\bf g}_{i}-{\bf q}_{i})^{2}$ subject
to $\displaystyle\sum_{i=1}^{\frac{d}{2}}{\bf
q}_{i}^{2}\leq\sum_{i=\frac{d}{2}+1}^{d}{\bf q}_{i}^{2}.$ (43)

For a moment, we find it convenient to set $\sum_{i=\frac{d}{2}+1}^{d}{\bf
q}_{i}^{2}=b$, define ${\bf g}^{(r)}\triangleq{\bf g}_{\frac{d}{2}+1:d}$, and
look at the following optimization problem

$\displaystyle z_{i}^{(r)}({\bf g}^{(r)},b)=\min_{{\bf q}}$
$\displaystyle\sum_{i=\frac{d}{2}+1}^{d}({\bf g}_{i}-{\bf q}_{i})^{2}$ subject
to $\displaystyle\sum_{i=\frac{d}{2}+1}^{d}{\bf q}_{i}^{2}=b.$ (44)

One can then trivially rewrite (3.1.2) as

$\displaystyle z_{i}^{(r)}({\bf g}^{(r)},b)=\min_{{\bf q}}$
$\displaystyle\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}-2\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}{\bf q}_{i}+b$ subject to
$\displaystyle\sum_{i=\frac{d}{2}+1}^{d}{\bf q}_{i}^{2}=b.$ (45)

Solving (3.1.2) then gives

$\displaystyle z_{i}^{(r)}({\bf g}^{(r)},b)$ $\displaystyle=$
$\displaystyle\left(\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}-2\sqrt{b}\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}^{2}}+b\right)$
(46) $\displaystyle=$ $\displaystyle\left(\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}-2\sqrt{b}\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}^{2}}+b\right)$
$\displaystyle=$ $\displaystyle\left(\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}}-\sqrt{b}\right)^{2}.$

One can then rewrite (3.1.2) as

$\displaystyle z_{i}({\bf g};\mbox{quad})=\min_{{\bf q},b}$
$\displaystyle\sum_{i=1}^{\frac{d}{2}}({\bf g}_{i}-{\bf
q}_{i})^{2}+z_{i}^{(r)}({\bf g}^{(r)},b)$ subject to
$\displaystyle\sum_{i=1}^{\frac{d}{2}}{\bf q}_{i}^{2}\leq b.$ (47)

A few additional algebraic transformations give

$\displaystyle z_{i}({\bf g};\mbox{quad})=\min_{{\bf q},b}$
$\displaystyle\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}-2\sum_{i=1}^{\frac{d}{2}}{\bf g}_{i}{\bf
q}_{i}+\sum_{i=1}^{\frac{d}{2}}{\bf q}_{i}^{2}+z_{i}^{(r)}({\bf g}^{(r)},b)$
subject to $\displaystyle\sum_{i=1}^{\frac{d}{2}}{\bf q}_{i}^{2}\leq b.$ (48)

We again for a moment set $\sum_{i=}^{\frac{d}{2}}{\bf q}_{i}^{2}=b_{1}\leq
b$, define ${\bf g}^{(l)}\triangleq{\bf g}_{1:\frac{d}{2}}$, and find

$\displaystyle z_{i}({\bf g};\mbox{quad})=\min_{b_{1}\leq b}$ $\displaystyle
z_{i}^{(l)}({\bf g}^{(l)},b_{1})+z_{i}^{(r)}({\bf g}^{(r)},b),$ (49)

where, analogously to (46), we also have

$\displaystyle z_{i}^{(l)}({\bf g}^{(l)},b)$ $\displaystyle=$
$\displaystyle\left(\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}-\sqrt{b_{1}}\right)^{2}.$ (50)

Clearly,

$\displaystyle\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}\leq\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}}\qquad\implies\qquad z_{i}({\bf g})=0.$ (51)

On the other hand, if $\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}>\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}^{2}}$ then $b_{1}=b$
and the optimization from (49) becomes

$\displaystyle z_{i}({\bf
g};\mbox{quad})=\min_{b}\left(\left(\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}-\sqrt{b}\right)^{2}+\left(\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}}-\sqrt{b}\right)^{2}\right).$ (52)

Optimizing over $b$ one then finds

$\displaystyle\sqrt{b}=\frac{\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}+\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}^{2}}}{2},$ (53)

and

$\displaystyle\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}>\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}}\qquad\implies\qquad z_{i}({\bf
g};\mbox{quad})=\frac{\left(\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}-\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf g}_{i}^{2}}\right)^{2}}{2}.$
(54)

Writing (51) and (54) in a more compact form gives

$\displaystyle z_{i}({\bf
g};\mbox{quad})=\frac{\left(\max\left(\sqrt{\sum_{i=1}^{\frac{d}{2}}{\bf
g}_{i}^{2}}-\sqrt{\sum_{i=\frac{d}{2}+1}^{d}{\bf
g}_{i}^{2}},0\right)\right)^{2}}{2}.$ (55)

Moreover, one also has

$\displaystyle z_{i}({\bf
g};\mbox{quad})=\frac{\left(\max\left(a_{i}^{(1)}-a_{i}^{(2)},0\right)\right)^{2}}{2},$
(56)

where $a_{i}^{(1)}$ and $a_{i}^{(2)}$ are independent chi random variables
with $\frac{d}{2}$ degrees of freedom. Connecting (23), (25), (42), and (56),
we finally have

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1$
(57) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})}-1$
$\displaystyle=$ $\displaystyle\sqrt{\alpha{\mathbb{E}}z_{i}({\bf
g};\mbox{quad})}-1$ $\displaystyle=$
$\displaystyle\sqrt{\alpha{\mathbb{E}}\frac{\left(\max\left(a_{i}^{(1)}-a_{i}^{(2)},0\right)\right)^{2}}{2}}-1.$

Given the pdf of the chi random variable with $\frac{d}{2}$ degrees of freedom

$\displaystyle
f_{\chi}(a)=\frac{2^{1-\frac{d}{4}}}{\gamma(\frac{d}{4})}a^{\frac{d}{2}-1}e^{-\frac{a^{2}}{2}},$
(58)

one can also find

$\displaystyle{\mathbb{E}}\left(\max\left(a_{i}^{(1)}-a_{i}^{(2)},0\right)\right)^{2}=\int_{0}^{\infty}\int_{0}^{a_{i}^{(1)}}\left(a_{i}^{(1)}-a_{i}^{(2)}\right)^{2}f_{\chi}(a_{i}^{(2)})f_{\chi}(a_{i}^{(1)})da_{i}^{(2)}da_{i}^{(1)}.$
(59)

We summarize the above results in the following lemma.

######  Lemma 3.

(Memory capacity upper bound; quadratic activation) Assume the setup of
Theorem 1. For quadratic ${\bf f}^{(2)}({\bf x})={\bf x}^{2}$, let
$c(d;\mbox{quad})\triangleq c(d;{\bf f}^{(2)}({\bf x})={\bf x}^{2})$ be the
$n$-scaled memory capacity from (3). Let $a_{i}^{(1)}$ and $a_{i}^{(2)}$ be
independent, chi distributed, random variables with $\frac{d}{2}$ degrees of
freedom and let $f_{\chi}(a)$ be as in (58). One then has the following

($n$-scaled) memory capacity upper bound:
$\displaystyle\hat{c}(d;\mbox{quad})=\frac{2}{{\mathbb{E}}\left(\max\left(a_{i}^{(1)}-a_{i}^{(2)},0\right)\right)^{2}}=\frac{2}{\int_{0}^{\infty}\int_{0}^{a_{i}^{(1)}}\left(a_{i}^{(1)}-a_{i}^{(2)}\right)^{2}f_{\chi}(a_{i}^{(2)})f_{\chi}(a_{i}^{(1)})da_{i}^{(2)}da_{i}^{(1)}}.$

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\hat{c}(d;\mbox{quad})$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];\mbox{quad})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1,$ (60)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(d,\mbox{quad})<\hat{c}(d,\mbox{quad}))\longrightarrow
1.$ (61)

###### Proof.

Follows immediately from the above discussion. ∎

Taking, say, $d=2$ for the concreteness, one finds
$\hat{c}(d;\mbox{quad})=5.4978$, which basically means that when the sample
complexity $m$ is such that $m>5.4978n$ (with $n$ being the data vectors’
ambient dimension) the network fails to memorize the data. Consequently, one
has for the memory capacity of the $2$ hidden layer _quadratically_ activated
neurons TCMs, $C(A([n,2,1];\mbox{quad}))\leq 5.4978n$. The results for a wider
range of $d$ are shown in Figure 2. We also add the
$\hat{c}(\infty;\mbox{quad})=4$, replica symmetry based prediction obtained in
[56]. As the figure indicates, one has that the RDT upper bound from the above
theorem approaches the $d\rightarrow\infty$ replica symmetry based prediction
already for fairly narrow nets with the number of neurons of the order of a
couple of tens. We should also add that due to the fact that the underlying
problems are now highly non-convex, the strong random duality considerations
from [39, 29, 37] are inapplicable. As we will see a bit later on, the results
obtained above (and shown in Figure 2), are in fact _strict_ (non-tight)
capacity upper bounds.

Figure 2: Memory capacity upper bound as a function of the number of neurons,
$d$, in the hidden layer; 1-hidden layer TCM with _quadratic_ activations;
_plain_ RDT estimate (Replica symmetry (RS) $d\rightarrow\infty$ estimate is
included as well)

####  3.1.3 ReLU hidden layer activations – ${\bf f}^{(2)}({\bf x})=\max({\bf
x},0)$

As was the case above when we considered the quadratic activation, for ReLU
(rectified linear unit) one has ${\bf f}^{(2)}({\bf x})=\max({\bf x},0)\geq
0$. This means that one again needs to carefully make a choice for vector
${\bf w}$ which ensures that the network functioning makes sense. Moreover,
one again easily observes that some of the components of ${\bf w}$ must be
negative. We follow the trend set above and in the ReLU relevant literature
and consider ${\bf w}$ with $\frac{d}{2}$ 1s and $\frac{d}{2}$ -1s, i.e., we
again take

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

while assuming that the size of the column vectors ${\bf 1}$ is
$\frac{d}{2}\times 1$. After again relying on (24), (26), (29), and (3), one
recognizes the following key optimization problem of interest

$z_{i}({\bf g};\mbox{relu})=z_{i}(G_{i,1:d})=\min_{{\bf
f}^{(2)}(Q_{i,1:d}){\bf w}\geq 0}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}=\min_{{\bf
f}^{(2)}({\bf q}^{T}){\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}=\min_{\max({\bf
q},0)^{T}{\bf w}\geq 0}\|{\bf g}-{\bf q}\|_{2}^{2}.$ (63)

Splitting the problem into two parts, gives the following formulation

$\displaystyle z_{i}({\bf g};\mbox{relu})=\min_{{\bf q}}$
$\displaystyle\sum_{i=1}^{\frac{d}{2}}({\bf g}_{i}-{\bf
q}_{i})^{2}+\sum_{i=\frac{d}{2}+1}^{d}({\bf g}_{i}-{\bf q}_{i})^{2}$ subject
to $\displaystyle\sum_{i=1}^{\frac{d}{2}}\max({\bf
q}_{i},0)\leq\sum_{i=\frac{d}{2}+1}^{d}\max({\bf q}_{i},0).$ (64)

#####  3.1.3.1 $d=2$

We study separately the simplest case $d=2$. There are two reasons for doing
so: 1) One can obtain a neat and explicit closed form final result; and 2)
Somewhat counter-intuitively, it will turn out that the bounding capacities
are decreasing functions of $d$.

When $d=2$, (3.1.3) becomes

$\displaystyle z_{i}({\bf g};\mbox{relu}_{2})=\min_{{\bf q}}$
$\displaystyle({\bf g}_{1}-{\bf q}_{1})^{2}+({\bf g}_{2}-{\bf q}_{2})^{2}$
subject to $\displaystyle\max({\bf q}_{1},0)\leq\max({\bf q}_{2},0).$ (65)

For ${\bf g}_{1}\leq 0$ one easily has $z_{i}({\bf g})=0$. Also, one trivially
has that for ${\bf g}_{2}\geq{\bf g}_{1}$, $z_{i}({\bf g})=0$. We then focus
on scenario where ${\bf g}_{1}\geq 0$ and ${\bf g}_{2}\leq{\bf g}_{1}$ happen
simultaneously. One first finds that for ${\bf g}_{2}\leq(1-\sqrt{2}){\bf
g}_{1}$, $z_{i}({\bf g})={\bf g}_{1}^{2}$. On the other hand for
$(1-\sqrt{2}){\bf g}_{1}\geq{\bf g}_{2}\leq{\bf g}_{1}$, $z_{i}({\bf
g})=\min\left({\bf g}_{1}^{2},2\left(\frac{{\bf g}_{1}-{\bf
g}_{2}}{2}\right)^{2}\right)=\frac{\left({\bf g}_{1}-{\bf
g}_{2}\right)^{2}}{2}$. In a more compact form one then has

$\displaystyle z_{i}({\bf g};\mbox{relu}_{2})=\begin{cases}0,&\mbox{if }{\bf
g}_{1}\leq 0\quad\mbox{or}\quad{\bf g}_{2}\geq{\bf g}_{1}\geq 0\\\ {\bf
g}_{1}^{2},&\mbox{if }{\bf g}_{1}\geq 0\quad\mbox{and}\quad{\bf
g}_{2}\leq(1-\sqrt{2}){\bf g}_{1}\\\ \frac{\left({\bf g}_{1}-{\bf
g}_{2}\right)^{2}}{2},&\mbox{if }{\bf g}_{1}\geq
0\quad\mbox{and}\quad(1-\sqrt{2}){\bf g}_{1}\leq{\bf g}_{2}\leq{\bf
g}_{1}.\end{cases}.$ (66)

Connecting (23), (25), (63), (3.1.3), and (66), we obtain

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1$
(67) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})}-1$
$\displaystyle=$ $\displaystyle\sqrt{\alpha{\mathbb{E}}z_{i}({\bf
g};\mbox{relu}_{2})}-1.$

Moreover, we also have

$\displaystyle{\mathbb{E}}z_{i}({\bf g};\mbox{relu}_{2})$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\int_{-\infty}^{\infty}z_{i}({\bf
g};\mbox{relu}_{2})\frac{e^{-\frac{{\bf
g}_{2}^{2}}{2}}}{\sqrt{2\pi}}\frac{e^{-\frac{{\bf
g}_{1}^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}_{2}d{\bf g}_{1}$ (68) $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\left(\int_{-\infty}^{(1-\sqrt{2}){\bf
g}_{1}}{\bf g}_{1}^{2}\frac{e^{-\frac{{\bf
g}_{2}^{2}}{2}}}{\sqrt{2\pi}}+\int_{(1-\sqrt{2}){\bf g}_{1}}^{{\bf
g}_{1}}\frac{\left({\bf g}_{1}-{\bf g}_{2}\right)^{2}}{2}\frac{e^{-\frac{{\bf
g}_{2}^{2}}{2}}}{\sqrt{2\pi}}\right)\frac{e^{-\frac{{\bf
g}_{1}^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}_{2}d{\bf g}_{1}$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\left(I_{1}({\bf g}_{1})+I_{2}({\bf
g}_{1})\right)\frac{e^{-\frac{{\bf g}_{1}^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}_{1},$

where

$\displaystyle I_{1}({\bf g}_{1})$ $\displaystyle\triangleq$
$\displaystyle{\bf g}_{1}^{2}\frac{\mbox{erfc}\left(\frac{(\sqrt{2}-1){\bf
g}_{1}}{\sqrt{2}}\right)}{2}$ $\displaystyle I_{2}({\bf g}_{1})$
$\displaystyle\triangleq$ $\displaystyle\frac{1}{4}\left(({\bf
g}_{1}^{2}+1)\left(\mbox{erf}\left(\frac{{\bf
g}_{1}}{\sqrt{2}}\right)-\mbox{erf}\left(\frac{(1-\sqrt{2}){\bf
g}_{1}}{\sqrt{2}}\right)\right)+\sqrt{\frac{2}{\pi}}\left({\bf
g}_{1}e^{-\frac{{\bf g}_{1}^{2}}{2}}-(1+\sqrt{2}){\bf
g}_{1}e^{-\frac{\left((1-\sqrt{2}){\bf g}_{1}\right)^{2}}{2}}\right)\right).$

We summarize the above results in the following lemma.

######  Lemma 4.

(Memory capacity upper bound; ReLU activation; $d=2$) Assume the setup of
Theorem 1. For rectified linear unit (ReLU) ${\bf f}^{(2)}({\bf x})=\max({\bf
x},0)$, let $c(d;\mbox{relu})\triangleq c(d;{\bf f}^{(2)}({\bf x})=\max({\bf
x},0)))$ be the $n$-scaled memory capacity from (3). Let $I_{1}({\bf g}_{1})$
and $I_{2}({\bf g}_{1})$ be as in (LABEL:eq:relud1a14). One then has the
following

($n$-scaled) memory capacity upper bound:
$\displaystyle\hat{c}(2;\mbox{relu})=\frac{1}{\int_{0}^{\infty}\left(I_{1}({\bf
g}_{1})+I_{2}({\bf g}_{1})\right)\frac{e^{-\frac{{\bf
g}_{1}^{2}}{2}}}{\sqrt{2\pi}}d{\bf g}_{1}}\approx\mathbf{3.81}.$

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\hat{c}(2;\mbox{relu})$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,2,1];\mbox{relu})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1,$ (70)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(2,\mbox{relu})<\hat{c}(2,\mbox{relu}))\longrightarrow
1.$ (71)

###### Proof.

Follows immediately from the above discussion. ∎

The above lemma basically states that when the sample complexity $m$ is such
that $m>3.81n$ (with $n$ being the data vectors’ ambient dimension) the
network fails to memorize the data. Consequently, one has for the memory
capacity of the $2$ hidden layer _ReLU_ activated neurons TCMs,
$C(A([n,2,1];\mbox{relu}))\leq 3.81n$. As was the case when we discussed the
quadratic activation, due to highly non-convex underlying problems, the strong
random duality considerations from [39, 29, 37] are inapplicable.

#####  3.1.3.2 General $d$

For studying general $d$, we find it convenient to introduce vector ${\bf
g}^{(1)}$, ${\bf g}^{(2)}$, ${\bf g}^{(2,ac)}$, and ${\bf g}^{(2,a)}$

$\displaystyle{\bf g}^{(1)}$ $\displaystyle\triangleq$
$\displaystyle\left\\{{\bf g}_{i}|{\bf g}_{i}>0,1\leq
i\leq\frac{d}{2}\right\\}$ $\displaystyle{\bf g}^{(2)}$
$\displaystyle\triangleq$ $\displaystyle\mbox{sort}\left({\bf
g}_{\frac{d}{2}+1:d}\right)$ $\displaystyle{\bf g}^{(2,a)}$
$\displaystyle\triangleq$ $\displaystyle\min({\bf g}^{(2)},0),$ (72)

where sorting is in the descending order. Basically, ${\bf g}^{(1)}$ is
comprised of the positive components of ${\bf g}_{1:\frac{d}{2}}$ and ${\bf
g}^{(2)}$ is ${\bf g}_{\frac{d}{2}+1:d}$ sorted in the descending order. Also,
for the notational simplicity, let the lengths of ${\bf g}^{(1)}$ and ${\bf
g}^{(2)}$ be $d_{1}$ and $d_{2}$, respectively and let $d_{3}$ be the number
of the nonnegative elements of ${\bf g}^{(2)}$ (clearly, $d_{2}=\frac{d}{2}$).
It is then not difficult to see that (3.1.3) can be rewritten as

$\displaystyle z_{i}({\bf g};\mbox{relu})=\min_{{\bf q}^{(1)},{\bf q}^{(2)}}$
$\displaystyle\sum_{i=1}^{d_{1}}({\bf g}^{(1)}_{i}-{\bf
q}^{(1)}_{i})^{2}+\sum_{i=1}^{d_{2}}({\bf g}^{(2,a)}_{i}-{\bf
q}^{(2)}_{i})^{2}$ subject to $\displaystyle\sum_{i=1}^{d_{1}}\max({\bf
q}^{(1)}_{i},0)\leq\sum_{i=1}^{d_{2}}\max({\bf q}^{(2)}_{i},0).$ (73)

Moreover, given the positivity of ${\bf g}^{(1)}$, it is relatively easy to
see that

$\displaystyle z_{i}({\bf g};\mbox{relu})=\min_{{\bf q}^{(1)}\geq 0,{\bf
q}^{(2)}}$ $\displaystyle\sum_{i=1}^{d_{1}}({\bf g}^{(1)}_{i}-{\bf
q}^{(1)}_{i})^{2}+\sum_{i=1}^{d_{2}}({\bf g}^{(2,a)}_{i}-{\bf
q}^{(2)}_{i})^{2}$ subject to $\displaystyle\sum_{i=1}^{d_{1}}{\bf
q}^{(1)}_{i}\leq\sum_{i=1}^{d_{2}}\max({\bf q}^{(2)}_{i},0).$ (74)

Following the methodology utilized for studying the quadratic activations, we
find it convenient to study the following optimization problem for a $b\geq 0$
and for any $k\in\\{d_{3},d_{3}+1,\dots,d_{2}\\}$

$\displaystyle z_{i}^{(2)}({\bf g}^{(2)},b,k;\mbox{relu})=\min_{{\bf
q}^{(2)}\geq 0}$ $\displaystyle\sum_{i=1}^{k}({\bf g}^{(2,a)}_{i}-{\bf
q}^{(2)}_{i})^{2}$ subject to $\displaystyle\sum_{i=1}^{k}{\bf
q}^{(2)}_{i}=b.$ (75)

One can then trivially rewrite (3.1.3.2) as

$\displaystyle z_{i}^{(2)}({\bf g}^{(2)},b,k;\mbox{relu})=\min_{{\bf
q}^{(2)}\geq 0}$ $\displaystyle\sum_{i=1}^{k}\left({\bf
g}^{(2,a)}_{i}\right)^{2}-2\sum_{i=1}^{k}{\bf g}^{(2,a)}_{i}{\bf
q}^{(2)}_{i}+\sum_{i=1}^{k}\left({\bf q}^{(2)}_{i}\right)^{2}$ subject to
$\displaystyle\sum_{i=1}^{k}{\bf q}^{(2)}_{i}=b.$ (76)

After writing the Lagrangian and relying on the strong duality, we also have

$\displaystyle z_{i}^{(2)}({\bf g}^{(2)},b,k;\mbox{relu})$ $\displaystyle=$
$\displaystyle\min_{{\bf q}^{(2)}\geq 0}\max_{\nu}\sum_{i=1}^{k}\left({\bf
g}^{(2,a)}_{i}\right)^{2}-2\sum_{i=1}^{k}{\bf g}^{(2,a)}_{i}{\bf
q}^{(2)}_{i}+\sum_{i=1}^{k}\left({\bf
q}^{(2)}_{i}\right)^{2}+2\nu\left(\sum_{i=1}^{k}{\bf q}^{(2)}_{i}-b\right)$
(77) $\displaystyle=$ $\displaystyle\max_{\nu}\min_{{\bf q}^{(2)}\geq
0}\sum_{i=1}^{k}\left({\bf g}^{(2,a)}_{i}\right)^{2}-2\sum_{i=1}^{k}{\bf
g}^{(2,a)}_{i}{\bf q}^{(2)}_{i}+\sum_{i=1}^{k}\left({\bf
q}^{(2)}_{i}\right)^{2}+2\nu\left(\sum_{i=1}^{k}{\bf q}^{(2)}_{i}-b\right).$

Solving over ${\bf q}^{(2)}$ gives

$\displaystyle{\bf q}^{(2,opt)}=\max({\bf g}^{(2,a)}-\nu,0),$ (78)

and

$\displaystyle z_{i}^{(2)}({\bf g}^{(2)},b,k;\mbox{relu})$ $\displaystyle=$
$\displaystyle\max_{\nu}\left(\sum_{i=1}^{k}\left({\bf
g}^{(2,a)}_{i}\right)^{2}-\sum_{i=1}^{k}\left({\bf
q}^{(2,opt)}_{i}\right)^{2}-2\nu b\right).$ (79)

After setting

$\displaystyle\bar{z}_{i}^{(2)}({\bf
g}^{(2)},b,k;\mbox{relu})=\begin{cases}\max_{\nu}\left(\sum_{i=1}^{k}\left({\bf
g}^{(2,a)}_{i}\right)^{2}-\sum_{i=1}^{k}\left({\bf
q}^{(2,opt)}_{i}\right)^{2}-2\nu b\right),&\mbox{if }\min({\bf
q}^{(2,opt)})>0\\\ \infty,&\mbox{otherwise},\end{cases}$ (80)

it is not that difficult to see that (3.1.3.2) can be rewritten as

$\displaystyle z_{i}({\bf g};\mbox{relu})=\min_{b\geq 0,{\bf q}^{(1)}\geq 0}$
$\displaystyle\sum_{i=1}^{d_{1}}({\bf g}^{(1)}_{i}-{\bf
q}^{(1)}_{i})^{2}+\min_{k\in\\{d_{3},d_{3}+1,\dots,d_{2}\\}}z_{i}^{(2)}({\bf
g}^{(2)},b,k;\mbox{relu})$ subject to $\displaystyle\sum_{i=1}^{d_{1}}{\bf
q}^{(1)}_{i}\leq b.$ (81)

We can then write the Lagrangian and rely on the strong duality as above to
obtain

$\displaystyle z_{i}({\bf g};\mbox{relu})$ $\displaystyle=$
$\displaystyle\min_{b\geq 0,{\bf q}^{(1)}\geq 0}\max_{\nu_{1}\geq
0}\sum_{i=1}^{d_{1}}({\bf g}^{(1)}_{i}-{\bf
q}^{(1)}_{i})^{2}+\min_{k\in\\{d_{3}+1,d_{3}+2,\dots,d_{2}\\}}\bar{z}_{i}^{(2)}({\bf
g}^{(2)},b,k;\mbox{relu})+2\nu_{1}(\sum_{i=1}^{d_{1}}{\bf q}^{(1)}_{i}-b)$
$\displaystyle=$ $\displaystyle\min_{b\geq 0}\max_{\nu_{1}\geq 0}\min_{{\bf
q}^{(1)}\geq 0}\sum_{i=1}^{d_{1}}({\bf g}^{(1)}_{i}-{\bf
q}^{(1)}_{i})^{2}+\min_{k\in\\{d_{3}+1,d_{3}+2,\dots,d_{2}\\}}\bar{z}_{i}^{(2)}({\bf
g}^{(2)},b,k;\mbox{relu})+2\nu_{1}(\sum_{i=1}^{d_{1}}{\bf q}^{(1)}_{i}-b).$

Solving over ${\bf q}^{(1)}$ gives

$\displaystyle{\bf q}^{(1,opt)}=\max({\bf g}^{(1)}-\nu_{1},0),$ (83)

and

$\displaystyle z_{i}({\bf g};\mbox{relu})$ $\displaystyle=$
$\displaystyle\min_{b\geq 0}\max_{\nu_{1}\geq 0}\sum_{i=1}^{d_{1}}\left({\bf
g}^{(1)}_{i}\right)^{2}-\sum_{i=1}^{d_{1}}\left({\bf
q}^{(1,opt)}_{i}\right)^{2}-2\nu_{1}b+\min_{k\in\\{d_{3},d_{3}+1,\dots,d_{2}\\}}\bar{z}_{i}^{(2)}({\bf
g}^{(2)},b,k;\mbox{relu}).$

Connecting (23), (25), (63), (3.1.3), and (3.1.3.2), we obtain

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1$
(85) $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})}-1$
$\displaystyle=$ $\displaystyle\sqrt{\alpha{\mathbb{E}}z_{i}({\bf
g};\mbox{relu})}-1.$

We summarize the above results in the following lemma.

######  Lemma 5.

(Memory capacity upper bound; ReLU activation; general $d$) Assume the setup
of Theorem 1. For rectified linear unit (ReLU) ${\bf f}^{(2)}({\bf
x})=\max({\bf x},0)$, let $c(d;\mbox{relu})\triangleq c(d;{\bf f}^{(2)}({\bf
x})=\max({\bf x},0)))$ be the $n$-scaled memory capacity from (3). Let ${\bf
g}$ be an $d$-dimensional vector comprised of iid standard normals and let
${\bf g}^{(1)}$, ${\bf g}^{(2)}$, and ${\bf g}^{(2,a)}$ be as in (3.1.3.2).
Also, let $d_{3}$ be the number of the nonnegative elements of ${\bf g}^{(2)}$
and let $d_{2}=\frac{d}{2}$. Additionally, let ${\bf q}^{(2,opt)}$, ${\bf
q}^{(1,opt)}$, $\bar{z}_{i}^{(2)}({\bf g}^{(2)},b,k;\mbox{relu})$, and
$z_{i}({\bf g};\mbox{relu})$ be as in (78), (83), (80), and (3.1.3.2),
respectively. One then has the following

($n$-scaled) memory capacity upper bound:
$\displaystyle\hat{c}(d;\mbox{relu})=\frac{1}{{\mathbb{E}}z_{i}({\bf
g};\mbox{relu})}.$

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\hat{c}(d;\mbox{relu})$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];\mbox{relu})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1,$ (86)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(d,\mbox{relu})<\hat{c}(d,\mbox{relu}))\longrightarrow
1.$ (87)

###### Proof.

Follows immediately from the above discussion. ∎

Utilization of the above lemma relies on a solid amount of numerical work.
Taking for the concreteness, say, $d=4$, we obtain
$\hat{c}(4;\mbox{relu})\approx 3.11$. This basically means that when the
sample complexity $m$ is such that $m>3.11n$ (with $n$ being the data vectors’
ambient dimension) the network fails to memorize the data. Consequently, one
has for the memory capacity of the $4$ hidden layer _ReLU_ activated neurons
TCMs, $C(A([n,4,1];\mbox{relu}))\leq 3.11n$. One can continue for other even
$d$, with the numerical calculations being more and more involved as $d$
increases. A bit easier (albeit not as precise and a bit jittery) alternative
is to simulate higher values of $d$. The obtained results are shown for a
wider range of $d$ in Figure 3. The replica symmetry based prediction,
$\hat{c}(\infty;\mbox{relu})\approx 2.93$, obtained in [56] is shown for the
completeness as well. Finally, we should add that (as was the case when we
discussed the quadratic activation and the _ReLU_ one with $d=2$), due to
highly non-convex underlying problems, the strong random duality
considerations from [39, 29, 37] are inapplicable.

Figure 3: Memory capacity upper bound as a function of the number of neurons,
$d$, in the hidden layer; 1-hidden layer TCM with _ReLU_ activations; _plain_
RDT estimate (Replica symmetry (RS) $d\rightarrow\infty$ estimate is included
as well)

##  4 _Partially lifted_ Random Duality Theory (pl RDT)

As the results from the previous sections showed, the RDT is rather useful
tool when it comes to characterizing the memory capacity. In particular, the
_plain_ RDT determines the memory capacity for the _linear_ activation and
upper-bounds it for the _quadratic_ and _ReLU_ activations. Moreover, the
scenarios where the application of the _plain_ RDT is of the upper-bounding
nature can be handled through the recently developed _fully lifted_ (fl) RDT
[41, 43, 44]. However, one needs to keep in mind, that the fl RDT relies on
heavy numerical evaluations which would come on top of the already seen
substantial numerical work from the previous sections. Opting for an
analytically less accurate but computationally more convenient route seems as
practically more beneficial. Recalling that a similar situation was observed
when the _sign_ activations were considered [42, 45], we find it reasonable to
follow the path taken overthere and consider a _partially lifted_ (pl) RDT
variant which relies on the following principles.

Summary of the _partially lifted_ (pl) RDT’s main principles [30, 39, 35, 40,
38] $\displaystyle\begin{array}[]{ll}\mbox{1) \emph{Finding underlying
optimization algebraic representation}}&\mbox{2) \emph{Determining the
{partially lifted} random dual}}\\\ \mbox{3) \emph{Handling the {partialy
lifted} random dual}}&\mbox{4) \emph{Double-checking strong random
duality.}}\end{array}$

We below assume a solid level of familiarity with the discussions presented in
[42, 45]. To ensure the smoothness of the presentation, we parallel the
presentation from [45] as closely as possible and discuss separately each of
the above four principles within the context of our interest here.

1) _Algebraic memorization characterization:_ This part of the pl RDT
corresponds to the first part of the plain RDT and is already obtained in
Lemma 1. As mentioned earlier, Lemma 1 holds for any given data set
$\left({\bf x}^{(0,k)},1\right)_{k=1:m}$. On the other hand, to analyze (16)
and (17), the pl RDT proceeds similarly to the plain RDT and imposes a
statistics on $X$.

2) _Determining the partially lifted random dual:_ Keeping in mind the measure
concentration from (19) (see, e.g. [30, 39, 32, 42, 45]), the following so-
called _partially lifted_ random dual theorem is another key ingredient of the
RDT machinery.

######  Theorem 2.

(Memorization characterization via _partially lifted_ random dual) Let $d$ be
any even integer. Consider a TCM with $d$ neurons in the hidden layer and
architecture $A([n,d,1];{\bf f}^{(2)})$, and let the elements of
$X\in{\mathbb{R}}^{m\times n}$, $G\in{\mathbb{R}}^{m\times d}$, and
$H\in{\mathbb{R}}^{\delta\times d}$ be iid standard normals. Assuming
$c_{3}>0$ and ${\bf w}\in{\mathbb{R}}^{d\times 1}$, set

$\displaystyle\phi(Q)$ $\displaystyle\triangleq$ $\displaystyle\|{\bf
1}-\emph{\mbox{sign}}({\bf f}^{(2)}(Q){\bf w})\|_{2}$ $\displaystyle
f_{rd}^{(1)}(G)$ $\displaystyle\triangleq$
$\displaystyle\max_{\phi(Q)=0}-c_{3}\|G-Q\|_{F}$ $\displaystyle
f_{rd}^{(2)}(H)$ $\displaystyle\triangleq$ $\displaystyle\|H\|_{F}$
$\displaystyle\bar{\phi}_{0}(\alpha;c_{3})$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}\frac{1}{\sqrt{n}}\left(\frac{c_{3}}{2}-\frac{1}{c_{3}}\log\left({\mathbb{E}}_{G}e^{\frac{c_{3}}{2}f_{rd}^{(1)}(G)}\right)-\frac{1}{c_{3}}\log\left({\mathbb{E}}_{H}e^{\frac{c_{3}}{2}f_{rd}^{(2)}(H)}\right)\right).\vspace{-.04in}$
(89)

One then has

$\displaystyle(\bar{\phi}_{0}(\alpha;c_{3})>0)$ $\displaystyle\Longrightarrow$
$\displaystyle\left(\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(f_{rp}>0)\longrightarrow
1\right)$ (90) $\displaystyle\Longrightarrow$
$\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.

Immediate consequence of Theorem 2 from [45]. ∎

3) _Handling the lifted random dual:_ After proceeding with a detailed careful
analysis of the optimization over $Q$, one arrives at the following theorem.

######  Theorem 3.

(Memory capacity partially lifted (pl) RDT based upper bound; general $d$)
Assume the setup of Theorem 2. Let the network $n$-scaled capacity, $c(d;{\bf
f}^{(2)})$, be as defined in (3) and let ${\bf g}$ be a $d$-dimensional vector
of iid standard normals. First one has

$\displaystyle z_{i}({\bf g};{\bf f}^{(2)})$ $\displaystyle=$
$\displaystyle\min_{{\bf f}^{(2)}({\bf q}^{T}){\bf w}\geq 0}\|{\bf g}-{\bf
q}\|_{2}^{2}$ $\displaystyle I_{Q}$ $\displaystyle=$
$\displaystyle{\mathbb{E}}_{{\bf g}}e^{-\frac{c_{3}}{4\gamma}z_{i}\left({\bf
g};{\bf f}^{(2)}\right)}$ $\displaystyle I_{sph}$ $\displaystyle=$
$\displaystyle\gamma_{sph}-\frac{1}{2c_{3}}\log\left(1-\frac{c_{3}}{2\gamma_{sph}}\right),\quad\gamma_{sph}=\frac{c_{3}+\sqrt{c_{3}^{2}+4}}{4}$
$\displaystyle\bar{\phi}_{0}(\alpha)$ $\displaystyle=$
$\displaystyle\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\alpha}{c_{3}}\log(I_{Q})-I_{sph}\right).$
(91)

Further, consider the following

($n$-scaled general $d$) memory capacity upper bound, $\bar{c}(d;{\bf
f}^{(2)})$, that satisfies: $\displaystyle\bar{\phi}_{0}(\bar{c}(d;{\bf
f}^{(2)}))=0\quad\Longleftrightarrow\quad\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\bar{c}(d;{\bf
f}^{(2)})}{c_{3}}\log(I_{Q})-I_{sph}\right)=0.$ (92)

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\bar{c}(d;{\bf
f}^{(2)})$

$\displaystyle\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,$ (93)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(d;{\bf
f}^{(2)})<\bar{c}(d;{\bf f}^{(2)}))\longrightarrow 1.$ (94)

###### Proof.

The proof is split into two parts: _(i)_ Handling
$\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{H}\mbox{exp}\left(c_{3}f_{rd}^{(2)}(H)\right)\right)$;
and _(ii)_ Handling of
$\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(c_{3}f_{rd}^{(1)}(G)\right)\right)$.

_(i)_ Handling
$\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{H}\mbox{exp}\left(c_{3}f_{rd}^{(2)}(H)\right)\right)$:
One first observes

$I_{sph}\triangleq\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{H}\mbox{exp}\left(c_{3}f_{rd}^{(2)}(H)\right)\right)=\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{H}\mbox{exp}\left(c_{3}\|H^{T}\|_{F}\right)\right).$
(95)

After appropriate scaling, $c_{3}\rightarrow c_{3}\sqrt{n}$, it was determined
in [36, 45] that

$I_{sph}=\gamma_{sph}-\frac{1}{2c_{3}}\log\left(1-\frac{c_{3}}{2\gamma_{sph}}\right),\quad\gamma_{sph}=\frac{c_{3}+\sqrt{c_{3}^{2}+4}}{4}.$
(96)

_(ii)_ Handling
$\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(c_{3}f_{rd}^{(1)}(G)\right)\right)$:
Following closely [45], we first observe

$\log(I_{Q}^{\prime})\triangleq\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(c_{3}f_{rd}^{(2)}(G)\right)\right)=\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(-c_{3}\min_{\phi(Q)=0}\|G-Q\|_{F}\right)\right).$
(97)

Utilizing the squaring trick introduced on many occasions in [40, 36], we
further find

$\log(I_{Q}^{\prime})=\max_{\gamma}\frac{1}{c_{3}\sqrt{n}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(c_{3}\left(-\frac{1}{4\gamma}\min_{\phi(Q)=0}\|G-Q\|_{F}^{2}-\gamma\right)\right)\right).$
(98)

Keeping in mind the appropriate scaling, $c_{3}\rightarrow c_{3}\sqrt{n}$ and
$\gamma\rightarrow\gamma\sqrt{n}$, and recalling
$\alpha=\lim_{n\rightarrow\infty}\frac{m}{n}$, one also has

$-\log(I_{Q}^{\prime})=\min_{\gamma}\left(\gamma-\frac{\alpha}{c_{3}}\log\left({\mathbb{E}}_{G}\mbox{exp}\left(c_{3}\left(-\frac{1}{4\gamma}\min_{\phi_{i}(Q_{i,:})=1}\|G_{i,:}-Q_{i,:}\|_{F}^{2}\right)\right)\right)\right),$
(99)

where

$\phi_{i}(Q_{i,:})\triangleq\mbox{sign}(\mbox{sign}(Q_{i,:}){\bf 1}).$ (100)

It is then not difficult to see that (99) is equivalent to the following

$\displaystyle-\log(I_{Q}^{\prime})$ $\displaystyle=$
$\displaystyle\min_{\gamma}\left(\gamma-\frac{\alpha}{c_{3}}\log\left({\mathbb{E}}_{{\bf
g}}\mbox{exp}\left(\left(-\frac{c_{3}}{4\gamma}\min_{{\bf f}^{(2)}({\bf
q}^{T}){\bf w}\leq 0}\|{\bf g}-{\bf q}\|_{2}^{2}\right)\right)\right)\right)$
(101) $\displaystyle=$
$\displaystyle\min_{\gamma}\left(\gamma-\frac{\alpha}{c_{3}}\log\left({\mathbb{E}}_{{\bf
g}}\mbox{exp}\left(-\frac{c_{3}}{4\gamma}z_{i}\left({\bf g};{\bf
f}^{(2)}\right)\right)\right)\right)$ $\displaystyle=$
$\displaystyle\min_{\gamma}\left(\gamma-\frac{\alpha}{c_{3}}\log\left(I_{Q}\right)\right).$

A simple combination of (89), (95)-(97), and (101) then completes the proof. ∎

4) _Double checking the strong random duality:_ As discussed earlier and in
[42, 45], the standard strong random duality double checking is not in place
due to inapplicability of the typical, convexity based, considerations from
[39, 29, 37].

###  4.1 Specialization to particular ${\bf f}^{(2)}$ activations

Theorem 3 is generic and works for various ${\bf f}^{(2)}$ activations. To see
how the whole machinery practically works, we here consider particular ${\bf
f}^{(2)}$ activations. However, since the plain RDT completely solved the
linear activation, we here focus only on the remaining two, the _quadratic_
and the _ReLU_. In fact, we first focus most of our interest to the quadratic
one as in that case the concrete capacity results can be obtained without an
extensive numerical work. We then afterwards briefly comment on the ReLU case
as well.

####  4.1.1 Pl RDT capacity estimates for quadratic activations – ${\bf
f}^{(2)}({\bf x})={\bf x}^{2}$

The following theorem summarizes the pl RDT results for the _quadratic_
activations.

######  Theorem 4.

(Memory capacity partially lifted (pl) RDT based upper bound; quadratic
activation) Assume the setup of Lemma 3 and Theorem 3 with $a_{i}^{(1)}$ and
$a_{i}^{(2)}$ being independent chi distributed random variables with
$\frac{d}{2}$ degrees of freedom. First one has

$\displaystyle I_{Q}$ $\displaystyle=$
$\displaystyle\int_{0}^{\infty}\int_{0}^{\infty}e^{-\frac{c_{3}}{4\gamma}\frac{\left(\max(a_{i}^{(1)}-a_{i}^{(2)},0)\right)^{2}}{2}}f_{\chi}(a_{i}^{(2)})f_{\chi}(a_{i}^{(1)})da_{i}^{(2)}da_{i}^{(1)}$
$\displaystyle I_{sph}$ $\displaystyle=$
$\displaystyle\gamma_{sph}-\frac{1}{2c_{3}}\log\left(1-\frac{c_{3}}{2\gamma_{sph}}\right),\quad\gamma_{sph}=\frac{c_{3}+\sqrt{c_{3}^{2}+4}}{4}$
$\displaystyle\bar{\phi}_{0}(\alpha)$ $\displaystyle=$
$\displaystyle\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\alpha}{c_{3}}\log(I_{Q})-I_{sph}\right).$
(102)

Further, consider the following

($n$-scaled general $d$) memory capacity upper bound,
$\bar{c}(d;\mbox{quad})$, that satisfies:
$\displaystyle\bar{\phi}_{0}(\bar{c}(d;\mbox{quad}))=0\quad\Longleftrightarrow\quad\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\bar{c}(d;\mbox{quad})}{c_{3}}\log(I_{Q})-I_{sph}\right)=0.$
(103)

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\bar{c}(d;\mbox{quad})$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];\mbox{quad})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1,$ (104)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(d;\mbox{quad})<\bar{c}(d;\mbox{quad}))\longrightarrow
1.$ (105)

###### Proof.

Follows immediately from Theorem 3 after recognizing that $z_{i}({\bf
g};\mbox{quad})=\frac{\left(\max\left(a_{i}^{(1)}-a_{i}^{(2)},0\right)\right)^{2}}{2}$.
∎

The results obtained based on the above theorem for a wider range of $d$ are
shown in Figure 4. For the completeness and a quick comparison, we include the
results obtained earlier based on the plain RDT. The benefit of the partially
lifted RDT is fairly strong throughout the entire range of the considered
$d$’s. We also add the partial 1rsb $d\rightarrow\infty$ estimate obtained
based on the statistical physics replica methods in [56]. As can be seen from
the figure, the convergence with $d$ is rather fast and already for fairly
small $d$ values (of the order of a couple of tens) the limiting,
$d\rightarrow\infty$, bound is narrowly approached. As was the case for the
plain RDT, we here observe that the bounding capacity estimates are decreasing
as $d$ increases with the largest value obtained again for $d=2$. Given its
clear importance, we, for the concreteness, take precisely $d=2$ and find
$\bar{c}(d;\mbox{quad})=4.065$, which then implies that the memory capacity of
the $2$ hidden layer _quadratically_ activated neurons TCMs,
$C(A([n,2,1];\mbox{quad}))\leq 4.065n$. Moreover, one observes a substantial
drop from the plain RDT bound of $5.4978$ established in earlier sections.

Figure 4: Memory capacity upper bound as a function of the number of neurons,
$d$, in the hidden layer; 1-hidden layer TCM with _quadratic_ activations;
_plain_ RDT versus _partially lifted_ RDT (Replica symmetry (RS) and Partial
1rsb $d\rightarrow\infty$ estimates are included as well)

####  4.1.2 Pl RDT capacity estimates for ReLU activations – ${\bf
f}^{(2)}({\bf x})=\max({\bf x},0)$

The following theorem summarizes the pl RDT results for the _ReLU_
activations.

######  Theorem 5.

(Memory capacity partially lifted (pl) RDT based upper bound; ReLU activation)
Assume the setup of Lemma 3 and Theorem 3 with $z_{i}({\bf g};\mbox{relu})$ as
in (3.1.3.2). First one has

$\displaystyle I_{Q}$ $\displaystyle=$
$\displaystyle\int_{-\infty}^{\infty}e^{-\frac{c_{3}}{4\gamma}z_{i}({\bf
g};\mbox{relu})}d{\bf g}$ $\displaystyle I_{sph}$ $\displaystyle=$
$\displaystyle\gamma_{sph}-\frac{1}{2c_{3}}\log\left(1-\frac{c_{3}}{2\gamma_{sph}}\right),\quad\gamma_{sph}=\frac{c_{3}+\sqrt{c_{3}^{2}+4}}{4}$
$\displaystyle\bar{\phi}_{0}(\alpha)$ $\displaystyle=$
$\displaystyle\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\alpha}{c_{3}}\log(I_{Q})-I_{sph}\right).$
(106)

Further, consider the following

($n$-scaled general $d$) memory capacity upper bound,
$\bar{c}(d;\mbox{relu})$, that satisfies:
$\displaystyle\bar{\phi}_{0}(\bar{c}(d;\mbox{relu}))=0\quad\Longleftrightarrow\quad\max_{c_{3}>0}\min_{\gamma}\left(\frac{c_{3}}{2}+\gamma-\frac{\bar{c}(d;\mbox{relu})}{c_{3}}\log(I_{Q})-I_{sph}\right)=0.$
(107)

Then for any sample complexity $m$ such that
$\alpha\triangleq\lim_{n\rightarrow\infty}\frac{m}{n}>\bar{c}(d;\mbox{relu})$

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(A([n,d,1];\mbox{relu})\quad\mbox{fails
to memorize data set}\quad(X,{\bf 1}))\longrightarrow 1,$ (108)

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(d,\mbox{relu})<\bar{c}(d,\mbox{relu}))\longrightarrow
1.$ (109)

###### Proof.

Follows immediately from Theorem 3 after recognizing that $z_{i}({\bf
g};\mbox{relu})$ from (3.1.3.2) is precisely $z_{i}({\bf g};{\bf
f}^{(2)}=\max({\bf x},0))$. ∎

The numerical evaluations are now substantially more involved even for small
values of $d$. Moreover, the simulations are rather extensive for larger
values and the indication from the plain RDT suggest that $d=2$ is
particularly relevant. As indicated in Table 1, we applied the above machinery
for $d=2$ and obtained the bound $\approx 3.81$, which means that in this
particular case the partial RDT makes no improvement over the plain RDT. The
table is completed by taking the plain RDT value for $d=4$ as well, since the
underlying partial RDT numerical work is already rather heavy.

##  5 Conclusion

In this paper we studied the treelike committee machines (TCM) neural networks
and their memory capabilities. Differently form the common practice, we here
instead of typical _sign_ perceptron hidden layer neuronal activations
consider a generic set of activations. Utilizing a powerful mathematical
concept called Random Duality Theory (RDT), [42] established a generic
statistical framework for the 1-hidden layer TCMs analysis that can study on a
very precise level the scaled capacities for any given number of the neurons
in the hidden layer, $d$. Among other things, such a machinery effectively
enabled avoiding the qualitative/descriptive scaling types of estimates
typically prevalent in the capacity analysis literature. Moreover, studying
the _sign_ perceptron activations, it also made a very strong progress towards
obtaining, in a mathematically rigorous way, their _exact_ $n$-scaled
capacities. For small values of $d$, it also made a very first rigorous
progress in over 30 years over the previously best known bounds of [15]. Since
the results of [42] are, in general, of the upper-bounding type, [45]
proceeded further by considering the so-called partially lifted (pl) RDT
variant and significantly lowered the estimates from [42]. Such a lowering
further resulted in ensuring a universal (over the entire range of $d$)
improvement over the previously best known results of [15].

We here adopt the same strategy and utilize both the plain RDT and the partial
RDT to characterize the 1-hidden layer TCM capacities with neuronal
activations substantially different from the classical _sign_ one. We first
establish a universal framework for studying generic activations and then
consider three particular activations types that have attracted a strong
interest in recent NN literature: (i) _linear_ ; (ii) _quadratic_ ; and (iii)
_ReLU_. For the linear activation we show that the plain RDT _exactly_
characterizes the capacity. Moreover, we show that, no matter how wide the
hidden layer is, the capacity remains equal to the capacity of the single
spherical _sign_ perceptron. For the quadratic and ReLU activations we obtain
that the plain RDT predictions are decreasing functions of $d$ that converge
to a constant value. The maximum bounding value is in both cases obtained for
the smallest possible $d=2$. Moreover, for the pl RDT and quadratic
activation, we obtain a strong improvement over the plain RDT through the
entire range of the considered $d$’s. At the same time, the bounding capacity
maintains the decreasing in $d$ property with the maximal value again being
achieved for (the minimal possible) $d=2$. For the ReLU, we obtained that the
pl RDT offers no improvement over the plain RDT for $d=2$ which means that the
same, decreasing in $d$, trend applies to these activations as well. Moreover,
we uncover that another of the trends observed in [42] manifests itself here
as well. Namely, the bounds obtained in [42] precisely matched the
corresponding statistical physics replica symmetry based predictions obtain in
[14, 5]. Here, we also observe that the _linear_ activation predictions
precisely match the ones obtained through the replica considerations in [56,
2]. Moreover, the $d\rightarrow\infty$ converging values of our both plain RDT
and pl RDT closely approach the corresponding ones obtained in [56].

Various extensions are possible as well. It is rather clear that the first
next one is to conduct the analysis with the _fully lifted_ (fl) RDT (see,
e.g., [44]). Also, we here consider only three well known activation
functions. Many others are of interest as well, e.g., sigmoid, erf, tanh and
so on. More complex multi-layered network architectures including both TCM and
FCM or PM based ones are of interest as well. All of these extensions, we will
discuss in separate papers.

## References

  * [1] S. Arora, S. S. Du, W. Hu, Z. Li, and R. Wang.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  2019\.  available online at http://arxiv.org/abs/1901.08584.
  * [2] C. Baldassi, E. M. Malatesta, and R. Zecchina.  Properties of the geometry of solutions and capacity of multilayer neural networks with rectified linear unit activations.  Phys. Rev. Lett., 123:170602, October 2019.
  * [3] P. Baldi and S. Venkatesh.  Number od stable points for spin-glasses and neural networks of higher orders.  Phys. Rev. Letters, 58(9):913–916, Mar. 1987.
  * [4] E. Barkai, D. Hansel, and I. Kanter.  Statistical mechanics of a multilayered neural network.  Phys. Rev. Lett., 65(18):2312–2315, Oct 1990.
  * [5] E. Barkai, D. Hansel, and H. Sompolinsky.  Broken symmetries in multilayered perceptrons.  Phys. Rev. A, 45(6):4146, March 1992.
  * [6] E. Barkai and I. Kanter.  Storage capacity of a multilayer neural network with binary weights.  Europhys. Lett., 14(2):107, 1991.
  * [7] E. B. Baum.  On the capabilities of multilayer perceptrons.  Journal of complexity, 4(3):193–215, 1988.
  * [8] S. H. Cameron.  Tech-report 60-600.  Proceedings of the bionics symposium, pages 197–212, 1960.  Wright air development division, Dayton, Ohio.
  * [9] T. Cover.  Geomretrical and statistical properties of systems of linear inequalities with applications in pattern recognition.  IEEE Transactions on Electronic Computers, (EC-14):326–334, 1965\.
  * [10] D. Donoho and J. Tanner.  Neighborliness of randomly-projected simplices in high dimensions.  Proc. National Academy of Sciences, 102(27):9452–9457, 2005.
  * [11] D. Donoho and J. Tanner.  Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing.  Phylosophical transactions of the royal society A: mathematical, physical and engineering sciences, 367, November 2009.
  * [12] D. Donoho and J. Tanner.  Counting the face of randomly projected hypercubes and orthants, with application.  Discrete and Computational Geometry, 43:522–541, 2010.
  * [13] S. S. Du, X. Zhai, B. Poczos, and A. Singh.  Gradient descent provably optimizes overparameterized neural networks.  2018\.  available online at http://arxiv.org/abs/1810.02054.
  * [14] A. Engel, H. M. Kohler, F. Tschepke, H. Vollmayr, and A. Zippelius.  Storage capacity and learning algorithms for two-layer neural networks.  Phys. Rev. A, 45(10):7590, May 1992.
  * [15] R. M. Durbin G. J. Mitchison.  Bounds on the learning capacity of some multi-layer networks.  Biological Cybernetics, 60:345–365, 1989.
  * [16] E. Gardner.  The space of interactions in neural networks models.  J. Phys. A: Math. Gen., 21:257–270, 1988.
  * [17] E. Gardner and B. Derrida.  Optimal storage properties of neural networks models.  J. Phys. A: Math. Gen., 21:271–284, 1988.
  * [18] R. Ge, R. Wang, and H. Zhao.  Mildly overparametrized neural nets can memorize training data efficiently.  2019\.  available online at http://arxiv.org/abs/1909.11837.
  * [19] M. Hardt and T. Ma.  Identity matters in deep learning.  2016\.  available online at http://arxiv.org/abs/1611.04231.
  * [20] G. B. Huang.  Learning capability and storage capacity of two-hidden-layer feedforward networks.  IEEE Transactions on Neural Networks, 14(2):274–281, 2003.
  * [21] Z. Ji and M. Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  2019\.  available online at http://arxiv.org/abs/1909.12292.
  * [22] R. D. Joseph.  The number of orthants in $n$-space instersected by an $s$-dimensional subspace.  Tech. memo 8, project PARA, 1960.  Cornel aeronautical lab., Buffalo, N.Y.
  * [23] Y. Li and Y. Liang.  Learning overparameterized neural networks via stochastic gradient descent on structured data.  In Advances in Neural Information Processing Systems, pages 8157–8166, 2018.
  * [24] R. Monasson and R. Zecchina.  Weight space structure and internal representations: A direct approach to learning and generalization in multilayer neural networks.  Phys. Rev. Lett., 75:2432, September 1995.
  * [25] S. Oymak and M. Soltanolkotabi.  Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.  2019\.  available online at http://arxiv.org/abs/1902.04674.
  * [26] L. Schlafli.  Gesammelte Mathematische AbhandLungen I.  Basel, Switzerland: Verlag Birkhauser, 1950.
  * [27] Z. Song and X. Yang.  Quadratic suffices for over-parametrization via matrix Chernoff bound.  2019\.  available online at http://arxiv.org/abs/1906.03593.
  * [28] M. Stojnic.  Block-length dependent thresholds in block-sparse compressed sensing.  available online at http://arxiv.org/abs/0907.3679.
  * [29] M. Stojnic.  Upper-bounding $\ell_{1}$-optimization weak thresholds.  available online at http://arxiv.org/abs/1303.7289.
  * [30] M. Stojnic.  Various thresholds for $\ell_{1}$-optimization in compressed sensing.  available online at http://arxiv.org/abs/0907.3666.
  * [31] M. Stojnic.  Block-length dependent thresholds for $\ell_{2}/\ell_{1}$-optimization in block-sparse compressed sensing.  ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3918–3921, 14-19 March 2010.  Dallas, TX.
  * [32] M. Stojnic.  $\ell_{1}$ optimization and its various thresholds in compressed sensing.  ICASSP, IEEE International Conference on Acoustics, Signal and Speech Processing, pages 3910–3913, 14-19 March 2010.  Dallas, TX.
  * [33] M. Stojnic.  Recovery thresholds for $\ell_{1}$ optimization in binary compressed sensing.  ISIT, IEEE International Symposium on Information Theory, pages 1593 – 1597, 13-18 June 2010.  Austin, TX.
  * [34] M. Stojnic.  Another look at the Gardner problem.  2013\.  available online at http://arxiv.org/abs/1306.3979.
  * [35] M. Stojnic.  Lifting $\ell_{1}$-optimization strong and sectional thresholds.  2013\.  available online at http://arxiv.org/abs/1306.3770.
  * [36] M. Stojnic.  Lifting/lowering Hopfield models ground state energies.  2013\.  available online at http://arxiv.org/abs/1306.3975.
  * [37] M. Stojnic.  Meshes that trap random subspaces.  2013\.  available online at http://arxiv.org/abs/1304.0003.
  * [38] M. Stojnic.  Negative spherical perceptron.  2013\.  available online at http://arxiv.org/abs/1306.3980.
  * [39] M. Stojnic.  Regularly random duality.  2013\.  available online at http://arxiv.org/abs/1303.7295.
  * [40] M. Stojnic.  Spherical perceptron as a storage memory with limited errors.  2013\.  available online at http://arxiv.org/abs/1306.3809.
  * [41] M. Stojnic.  Bilinearly indexed random processes – _stationarization_ of fully lifted interpolation.  2023\.  available online at http://arxiv.org/abs/2311.18097.
  * [42] M. Stojnic.  Capacity of the treelike sign perceptrons neural networks with one hidden layer – rdt based upper bounds.  2023\.  available online at http://arxiv.org/abs/2312.08244.
  * [43] M. Stojnic.  Fully lifted interpolating comparisons of bilinearly indexed random processes.  2023\.  available online at http://arxiv.org/abs/2311.18092.
  * [44] M. Stojnic.  Fully lifted random duality theory.  2023\.  available online at http://arxiv.org/abs/2312.00070.
  * [45] M. Stojnic.  _Lifted_ rdt based capacity analysis of the 1-hidden layer treelike _sign_ perceptrons neural networks.  2023\.  available online at http://arxiv.org/abs/2312.08257.
  * [46] R. Sun.  Optimization for deep learning: theory and algorithms.  2019\.  available online at http://arxiv.org/abs/1912.08957.
  * [47] R Urbanczik.  Storage capacity of the fully-connected committee machine.  J. Phys. A: Math. Gen., 30, 1997.
  * [48] S. Venkatesh.  Epsilon capacity of neural networks.  Proc. Conf. on Neural Networks for Computing, Snowbird, UT, 1986\.
  * [49] R. Vershynin.  Memory capacity of neural networks with threshold and ReLU activations.  2019\.  available online at http://arxiv.org/abs/2001.06938.
  * [50] J. G. Wendel.  A problem in geometric probability.  Mathematica Scandinavica, 1:109–111, 1962.
  * [51] R. O. Winder.  Single stage threshold logic.  Switching circuit theory and logical design, pages 321–332, Sep. 1961.  AIEE Special publications S-134.
  * [52] R. O. Winder.  Threshold logic.  Ph. D. dissertation, Princetoin University, 1962.
  * [53] Y. Xiong and J. H. Oh C. Kwon.  The storage capacity of a fully-connected committee machine.  NIPS, 1997.
  * [54] M. Yamasaki.  The lower bound of the capacity for a neural network with multiple hidden layers.  In International Conference on Artificial Neural Networks, pages 546–549, 1993.
  * [55] C. Yun, S. Sra, and A. Jadbabaie.  Small relu networks are powerful memorizers: a tight analysis of memorization capacity.  In Advances in Neural Information Processing Systems, pages 15532–15543, 2019.
  * [56] J. A. Zavatone-Veth and C. Pehlevan.  Activation function dependence of the storage capacity of treelike neural networks.  Phys. Rev. E, 103:L020301, February 2021.
  * [57] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  ICLR, 2017.
  * [58] D. Zou, Y. Cao, D. Zhou, and Q. Gu.  Stochastic gradient descent optimizes overparameterized deep relu networks.  2018\.  available online at http://arxiv.org/abs/1811.08888.