# Capacity of the treelike sign perceptrons neural networks with one hidden
layer – RDT based upper bounds

Mihailo Stojnic 111e-mail<EMAIL_ADDRESS>
Abstract

We study the capacity of _sign_ perceptrons neural networks (SPNN) and
particularly focus on 1-hidden layer _treelike committee machine_ (TCM)
architectures. Similarly to what happens in the case of a single perceptron
neuron, it turns out that, in a statistical sense, the capacity of a
corresponding multilayered network architecture consisting of multiple _sign_
perceptrons also undergoes the so-called phase transition (PT) phenomenon.
This means: (i) for certain range of system parameters (size of data, number
of neurons), the network can be properly trained to accurately memorize _all_
elements of the input dataset; and (ii) outside the region such a training
does not exist. Clearly, determining the corresponding phase transition curve
that separates these regions is an extraordinary task and among the most
fundamental questions related to the performance of any network. Utilizing
powerful mathematical engine called Random Duality Theory (RDT), we establish
a generic framework for determining the upper bounds on the 1-hidden layer TCM
SPNN capacity. Moreover, we do so for _any_ given (odd) number of neurons. We
further show that the obtained results _exactly_ match the replica symmetry
predictions of [14, 5], thereby proving that the statistical physics based
results are not only nice estimates but also mathematically rigorous bounds as
well. Moreover, for $d\leq 5$, we obtain the capacity values that improve on
the best known rigorous ones of [15], thereby establishing a first,
mathematically rigorous, progress in well over 30 years.

Index Terms: Multi-layer neural networks; Capacity; Random duality theory.

##  1 Introduction

As is well known, neural networks (NN) are among the most powerful algorithmic
and engineering tools often used to handle many, otherwise intractable,
problems. Growing demand for understanding large datasets has skyrocketed the
NN relevance within the last decade. Clearly, the practical algorithmic
aspects including designs and various NN applications lead the way. A
corresponding trend of high demand for the adequate theoretical justifications
has been created as well. We in this paper follow such a trend and provide a
strong theoretical support for _precisely_ determining the so-called network’s
_memory capacity_ – one of the key fundamental features of any NN.

###  1.1 Model, mathematical setup, and relevant prior work

We start by considering a general setup with (potentially) fully connected
multilayered multi-input single-output feed-forward neural net with the number
of inputs $n$ and the number of hidden layers $L-2$. Deviating slightly from
the common practice and for the notational convenience, we view the inputs as
the nodes of the first layer and the output as the node of the last layer.
This also implies that $n$ is the number of the neurons in the first and $1$
is the number of the nodes in the last layer (the first and/or the last layer
can then be viewed through the prism of the existing literature terminology as
artificial layers). Also we denote by $d_{i}$ the number of the nodes in layer
$i$, $1\leq i\leq L$ and, clearly, set $d_{1}\triangleq n$ and $d_{L}=1$. The
nodes from layers $i$ and $i+1$ are linearly connected by weights
$W^{(i)}\in{\mathbb{R}}^{d_{i}\times d_{i+1}}$ (to ensure the full generality,
we initially assume that matrices $W^{(i)}$ are full; below, we specialize to
particular cases). The network effectively operates based on the following
simple mathematical formalism:

${\bf x}^{(i+1)}={\bf f}^{(i)}(W^{(i)}{\bf x}^{(i)}-{\bf b}^{(i)}),$ (1)

where ${\bf x}^{(i)}\in{\mathbb{R}}^{d_{i}}$ and ${\bf
x}^{(i+1)}\in{\mathbb{R}}^{d_{i+1}}$ are respectively the input and output
vectors of the neurons in layer $i$, ${\bf b}^{(i)}\in{\mathbb{R}}^{d_{i+1}}$
are the vectors of the so-called neuron threshold values, and ${\bf
f}^{(i)}(\cdot)=[{\bf f}_{1}^{(i)}(\cdot),{\bf f}_{2}^{(i)}(\cdot),\dots,{\bf
f}_{d_{i+1}}^{(i)}(\cdot)]^{T}$ are $d_{i+1}\times 1$ column vectors of
functions ${\bf
f}_{j}^{(i)}(\cdot):{\mathbb{R}}^{d_{i}}\rightarrow{\mathbb{R}}$ that describe
how $d_{i+1}$ neurons in layer $(i+1)$ operate. We also follow the standard
conventions and define network’s input and output as:

$\mbox{{network input:}}\triangleq{\bf x}^{(1)}\qquad\mbox{{network
output:}}\triangleq{\bf x}^{(L+1)}.$ (2)

We refer to the above architecture as $A({\bf d};{\bf f}^{(i)})$ where ${\bf
d}=[d_{1},d_{2},\dots,d_{L}]$ (or for short $A({\bf d};{\bf f})$ when all the
neurons after the first layer have identical functions ${\bf f}$).

As we have already mentioned, the above is the general fully connected network
architecture. Of our particular interest is the _treelike_ one as well. In
such an architecture, one has matrices $W^{(i)}$ as sparse objects with a
particular type of sparsity. Namely, assuming that
$\delta_{i}=\frac{d_{i}}{d_{i+1}}$ is a positive integer, the nonzero elements
of the $j$-th (for $j\in\\{1,2,\dots,d_{i}\\}$) row of $W^{(i)}$ are
restricted to columns
$\\{(j-1)\delta_{i}+1,(j-1)\delta_{i}+2,\dots,j\delta_{i}\\}$.

Memory capacity: Any neuron has, as one of its most fundamental properties,
ability to properly characterize certain features of a given data set. For
example, assume that one is given a collection of images showing various
sporting events ranging from basketball, football, and soccer to tennis, golf,
and chess. One can then wonder if an NN architecture can properly memorize
which image shows which of the sports. The answer is yes (in fact, not only
can a properly trained NN do so, but a single neuron can as well). To see how
this question fits into the above mathematical NN frame, let us assume that we
are given $m$ data pairs $({\bf x}^{(0,k)},{\bf y}^{(0,k)})$,
$k\in\\{1,2,\dots,m\\}$. For each ${\bf x}^{(0,k)}\in{\mathbb{R}}^{n}$ that
represents an $n$-dimensional image, ${\bf y}^{(0,k)}\in{\mathbb{R}}$
represents its a corresponding label that explains which sport the image
shows. One then observes that determining weights $W^{(i)}$ in (1) such that

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

is sufficient to properly memorize the given data pairs. While the above NN
concept has the ability to memorize, it doesn’t necessarily mean that it can
do so for any data set. As intuitively expected, it typically turns out that
the properties of the underlying data set, and in particular its size, play a
key role in distinguishing between when the memorization can and cannot be
done. In fact, the so-called _memory capacity_ , $C(A)$, of a given neural
architecture is exactly the largest $m$ such that (3) 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. Clearly, determining an, as precise as
possible, value of the memory capacity, is of the fundamental importance when
it comes to ensuring a proper network utilization. We below present a
collection of results that directly relate to the memory capacity.

Before proceeding with the discussion of the main results, we find it useful
to clearly state all the underlying assumptions that make the analysis easier
to present.

Structural (network architecture) assumptions: _(i)_ We consider zero-
thresholds (${\bf b}^{(i)}=0$) _committee machine_ networks with one hidden
layer. That means that, in the above generic setup, we have $L=3$,
$W^{(1)}=I_{n\times n}$ and $W^{(3)}={\bf 1}_{d_{2}\times 1}^{T}$ (i.e.
$W^{(3)}$ is a $d_{2}$-dimensional row vector of all ones). _(ii)_ For the
very first layer we assume, as is done traditionally, ${\bf
f}^{(1)}(W^{(1)}{\bf x}^{(1)})={\bf f}^{(1)}({\bf x}^{(1)})={\bf x}^{(1)}$.
_(iii)_ For the second and third layer we consider the so-called _sign_
perceptrons (with zero thresholds), which implies ${\bf
f}^{(i)}_{j}(W^{(i)}{\bf x}^{(i)}-{\bf b}^{(i)})=\mbox{sign}\left(W^{(i)}{\bf
x}^{(i)}\right)$. _(iv)_ Since the only changeable number of neurons is in the
hidden layer, we define $d\triangleq d_{2}$ and
$\delta\triangleq\delta_{1}=\frac{d_{1}}{d_{2}}=\frac{n}{d}$ and consequently
have the following architecture $A([n,d,1];\mbox{sign})$. _(v)_ Finally, to
ensure that the node in the last layer functions properly, we assume _odd_
values for $d$ (this can easily be modified through different definitions of
$W^{(3)}$ to account for any (including even) $d$; however, the writing
becomes more complicated and the overall presentation would lose on elegance).
The above specified architecture for general full $W^{(i)}$’s corresponds to
the so-called _fully connected committee machines_ (FCM). When $W^{(i)}$’s are
with the above mentioned particular sparse structure, we have the so-called
_treelike committee machines_ (TCM). Moreover, modulo the first layer, which
is typically included for the completeness and conventional reasons (and as
such it does not really affect the functioning of the network), the entire
structure consists of _sign_ perceptrons. We refer to such structures as
_sign_ perceptrons neural nets (SPNN). Depending on the type of $W^{(i)}$’s,
we then have FCM or TCM SPNNs. As is well known, and as we will see later on,
these objects belong to the class of _discrete_ neuronal functions and are
very difficult to analytically handle.

Technical (data related) assumptions: _(i)_ As one expects based on the above
choice of ${\bf f}$’s, we assume _binary_ labeling, i.e. we assume ${\bf
y}_{i}^{(0,k)}\in\\{-1,1\\}$ (the entire analysis directly extends to any
other form of $q$-ary labeling at the expense of writing and overall
exposition being substantially more involved). _(ii)_ We assume separable data
sets (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)_ We assume statistical data sets and, for the easiness
of the presentation, we take ${\bf x}^{(0,k)}$ as iid standard normals. While
this follows the standard statistical trend from the classical single
perceptron references [12, 16, 33, 9, 49, 48, 47], we should add that, when
one is interested in providing capacity upper bounds that hold universally, it
is sufficient to choose a particular type of the data set for which these
bounds are valid. Of course, as shown in [12, 16, 33, 9, 49, 48, 47] for
single perceptrons, and as we will see later on for the networks, for
particular statistics the bar can be raised much higher and the capacity might
potentially be determined on a very precise level.

Relevant prior work: Studying the _sign_ perceptron neurons has been around
for as long as the pattern recognition and machine learning fields have. In
fact, when repositioned within the context of integral geometry, various
related studies can be found in the works that stretch back even further (see,
e.g. [26, 9, 47, 22]). As is by now well known, the most prominent result
related to the _sign_ spherical perceptron, is that its capacity grows
linearly with the dimensionality of the data ambient space, $n$. Moreover, one
can actually precisely determine the underlying linear proportionality as
$C(A(1;\mbox{sign}))\rightarrow 2n$ as $n\rightarrow\infty$. After the initial
considerations from [26, 9, 49, 48, 47, 8, 22], this celebrated result has
been rediscovered in various forms on a multitude of occasions in various
different fields [3, 45, 10, 32, 11, 12] with particulary interesting being
statistical physics considerations from [16] and their rigorous justifications
from [33, 37].

_Multi-layer NN (FCM versus TCM):_ While all the above mentioned results
pretty much completely clarified the way a single _sign_ perceptron functions,
the picture is not remotely as clear when one moves to the corresponding
multi-perceptron counterparts. The results related to the TCM architectures
are particularly scarce. A little bit more is known regarding the behavior of
the related FCM ones. The direct connection between the two is not apparent
though. Beyond the obvious fact that the FCM capacities trivially upper-bound
the corresponding TCM ones, one may also take (in particular for the 1-hidden
layer architectures) that the TCM capacities are roughly speaking the FCM ones
scaled by $d$. Since these connections are rather interesting, it is useful to
recall on some of the known FCM results. To that end, let the total number of
the free network parameters (weights) be $w=\sum_{i=1}^{L-1}d_{i}d_{i+1}$.
Then, probably, the most closely related result to our own is the VC-dimension
_qualitative_ memory capacity upper bound $O(w\log(w))$ (for the 1-hidden
layer NNs, one has that $w=d_{1}d_{2}+d_{2}=(n+1)d$ for FCM and
$w=d_{1}+d_{2}=n+d$ for TCM which, for huge $n$ and large $d_{i}$’s, gives the
above mentioned FCM versus TCM capacity scaling by $d$). Although not directly
related, we mention a couple of results regarding the corresponding lower
bounds. First in [7], it was argued that for a shallow 3-layer network
(similar to the one that we study in this paper) the capacity scales as
$O(nd)$. In [46], it was shown for networks with more than three layers that
the capacity is (roughly speaking) at least $O(w)$. All of these results are
of the qualitative/scaling type and as such are not directly related or
comparable to the ones that we will present below. In particular, we analyze
the capacity for _any_ given $d$ and do so on the phase transition level of
precision, where the qualitative/scaling type of estimates are not allowed.
Nonetheless, we included all the known scaling estimates since they provide a
simple descriptive characterizations as to what one might expect from the
network capacities.

_Different activations:_ Among relatively simple traditionally employed
neuronal functions, the _sign_ perceptrons (of our interest in this paper) are
probably the hardest to analytically handle. The main reason is their
discreteness. If one, for example, deviates a little bit and allows for their
various well known continuous counterparts/relaxations (i.e., for ${\bf f}$’s
being sigmoid, ReLU, tanh and so on) a little bit more is known. For example,
for sigmoid, it was suggested for deep nets in [51] (and proven for 4-layer
nets in [20]) that the capacity is at least $O(w)$. Similar results were shown
in [54, 19] with an additional restriction on the number of nodes that was
later on removed in [52].

_Algorithmic achievability:_ When it comes to the continuous neuronal
functions, a whole lot of great work has been done recently on equally
important problem of actually approaching the capacity as closely as possible.
After an overwhelming empirical evidence suggested that simple gradient based
methods might be able to train the net rather well, the focus in recent years
has been on showing that the so-called mild over-parametrization (moderately
larger number of all free parameters, $w$, compared to the size of the
memorizable data set, $m$) suffices to justify its performance. A subset of
very interesting and successful approaches towards rigorously establishing
these statements can be found in e.g. [13, 17, 1, 21, 23, 25, 43, 27, 55]. A
majority of these works treats FCMs but are extendable to TCMs as well.

_Statistical physics (replica methods):_ Finally, excellent results have been
obtained through the statistical physics replica methods. While these are
mathematically non-rigorous, they are most closely related to our work in
terms of both the studied network setup and the obtained performance
predictions. In particular, [14, 5] study the very same, treelike (non-
overlapping weights) committee machine (TCM) architecture (as well as a
directly related, fully connected (overlapping weights) one). They obtained
the closed form replica symmetry based capacity predictions for any number,
$d$, of the neurons in the hidden layer. Moreover, [14, 5] proceeded even
further and studied the corresponding scaling behavior for large $d$ and
showed that the obtained bound violates the uniform bound extension of [9, 49,
48, 47] given in [15]. As a remedy to such a contradiction, they further
undertook studying of the first level of the replica symmetry breaking (rsb)
and showed that it can lower the capacity. Corresponding large $d$ scaling rsb
considerations were presented in [24] for both the committee and the so-called
parity machines (for more on earlier parity machines replica considerations,
see,e.g., [6, 4]). Also, for the fully connected committee machines
architecture, a bit later, [44, 50] obtained the large $d$ scaling that
matches the upper-bounding one of [15]. More recently, [2] obtained the first
level of rsb capacity predictions for the treelike architecture but with the
ReLU activations and [53] moved things further by obtaining similar
predictions for a few additional activations, including ReLU, erf, quadratic,
and linear.

Our contributions: We study, within the above mentioned statistical data
context, the memory capacity of TCM SPNNs with one hidden layer, i.e. we study
$C(A([n,d,1];\mbox{sign}))$. The following are the main takeaways: _(i)_ We
attack the problem on the _phase transition_ level, which does not allow for
_qualitative/scaling_ type of estimates and instead requires very _precise_
analysis of all underlying quantities. _(ii)_ Utilizing a powerful
mathematical engine, called Random Duality Theory (RDT) (see, e.g. [29, 31,
36]), we create a generic framework for the analysis of the memory
capabilities of SPNNs. _(iii)_ For _any_ (odd) given number of the nodes in
the hidden layer, $d$, we provide an explicit characterization of an upper
bound on $\lim_{n\rightarrow\infty}C(A([n,d,1];\mbox{sign}))$. _(iv)_ Somewhat
surprisingly and despite heavy underlying mathematics, the final forms of the
resulting characterizations are sufficiently elegant to even allow an
efficient numerical evaluation of the exact proportionality constants that the
analysis produces. The obtained results are shown in Table 1. The numerical
values are the upper bounds $\hat{c}(3,\mbox{sign})$ on the true values of the
$n$-scaled capacity $c(d;\mbox{sign})$ defined as

$c(d;\mbox{sign})\triangleq\lim_{n\rightarrow\infty}\frac{C(A([n,d,1];\mbox{sign}))}{n}.$
(4)

_(v)_ The obtained results exactly match the replica symmetry predictions of
[14, 5] for any $d$, thereby establishing the statistical physics predictions
as rigorous upper bounds (which is in agreement and as expected by the
postulates of the RDT). More, importantly, for $d\leq 5$ our results improve
on the best rigorously known ones of [15], thereby making the first
mathematically rigorous progress in over 30 years in studying this, rather
fundamental, neural network open problem.

Table 1: Theoretical estimates of the memory capacity upper bounds of 1-hidden layer TCM SPNN Upper bound on | Reference | $d$
---|---|---
$c(d;\mbox{sign})\triangleq\lim_{n\rightarrow\infty}\frac{C(A([n,d,1];\mbox{sign}))}{n}$ | (methodology) | $\mathbf{1}$ | $\mathbf{3}$ | $\mathbf{5}$
$\hat{c}(d;\mbox{sign})$ | this paper (RDT) | $\mathbf{2}$ | $\mathbf{4.025}$ | $\mathbf{5.769}$
$c_{RS}(d;\mbox{sign})$ | [14, 5] (Replica symmetry) | $\mathbf{2}$ | $\mathbf{4.025}$ | $\mathbf{5.769}$
$c_{CG}(d;\mbox{sign})$ | [15] (Combinatorial geometry) | $\mathbf{2}$ | $\mathbf{5.421}$ | $\mathbf{6.425}$

##  2 Technical analysis

We start things off by putting everything on the right mathematical track. To
that end we first set $W\triangleq W^{(2)}$ and after recalling that
$W^{(1)}=I$ and $W^{(3)}={\bf 1}_{d\times 1}^{T}={\bf 1}^{T}$ (where we drop
the subscript in ${\bf 1}$ to ease the writing), we 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)},$ (5)

and

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

and

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

Connecting beginning in (5) and end in (7), we have an explicit, closed-form
relation between the input and the output of the network

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

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

${\bf y}^{(0,k)}=\mbox{sign}({\bf 1}^{T}\mbox{sign}(W{\bf x}^{(0,k)})).$ (9)

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

one can rewrite (9) as

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

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}$. We can further alternatively write (11) as the following

Algebraic memorization characterization: $\displaystyle
0=\xi\triangleq\min_{W,Q}$ $\displaystyle\|{\bf
y}-\mbox{sign}(\mbox{sign}(Q){\bf 1})\|_{2}$ subject to $\displaystyle
XW^{T}=Q$ (12) $\Longleftrightarrow$ Data set $\left(X,{\bf y}\right)$ is
properly memorized.

Since the above optimization problem is the key on the path towards ensuring
proper network data memorization, we below analyze it in more detail.

###  2.1 Upper-bounding capacity via Random Duality Theory (RDT)

As discussed in the introduction, we consider statistical data sets and assume
that elements of $X$ are iid standard normals. Due to the consequential
statistical rotational symmetry, we can then, analogously and without a loss
of generality, assume that the elements of ${\bf y}$ are all equal to 1, i.e.
that ${\bf y}={\bf 1}$. Then the above key optimization becomes

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

where for the easiness of writing, we have introduced a cosmetic change
$Z=W^{T}$. We consider the TCM architecture, with the sparse $Z$ such that the
only nonzero elements of the $j$ column of $Z$ are in rows
${\mathcal{S}}^{(j)}\triangleq\\{(j-1)\delta+1,(j-1)\delta+2,\dots,j\delta\\}$.
Moreover, as the above problem is insensitive with respect to the scaling of
$Z$ or $Q$, it can be rewritten as

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

where $\|Z_{:,j}\|_{2}$ is the norm of the $j$ column of $Z$. One can then
trivially rewrite the above as

$\displaystyle\xi=\min_{{\bf z}^{(j)},Q}$ $\displaystyle\|{\bf
1}-\mbox{sign}(\mbox{sign}(Q){\bf 1})\|_{2}$ subject to $\displaystyle
X^{(j)}{\bf z}^{(j)}=Q_{:,j},1\leq j\leq d,$ (15) $\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}$. To
attack the statistical optimization in (2.1), we heavily rely on the powerful
mathematical engine called Random Duality Theory (RDT) developed in a long
series of work [29, 31, 28, 30, 36]. Also, given the difficulty of the problem
that we are facing, we assume a complete familiarity with the RDT and start by
first summarizing its main principles and then continue by showing, step-by-
step, how each of those principles applies to the problems of our interest
here.

Summary of the RDT’s main principles [29, 36]
$\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}$

To make the presentation look neat, we adopt the practice to formalize all the
key results (including both simple to more complicated ones) as lemmas and
theorems.

1) _Algebraic memorization characterization:_ The following lemma summarizes
the above algebraic discussion which ultimately provided a convenient
optimization representation of the underlying network memorization property.

######  Lemma 1.

(Algebraic optimization representation) Assume a 1-hidden layer TCM SPNN with
architecture $A([n,d,1];\mbox{sign})$. 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,$ (17)

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}-\emph{\mbox{sign}}(\emph{\mbox{sign}}(Q){\bf
1})\|_{2}+\sum_{j=1}^{d}(\Lambda_{:,j})^{T}X^{(j)}{\bf z}^{(j)}-{\rm
tr}\,(\Lambda^{T}Q),$ (18)

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

###### Proof.

One first writes the Lagrangian of the optimization in (2.1) as

$\mathcal{L}(Z,Q,\Lambda)=\|{\bf
1}-\emph{\mbox{sign}}(\emph{\mbox{sign}}(Q){\bf
1})\|_{2}+\sum_{j=1}^{d}(\Lambda_{:,j})^{T}X^{(j)}{\bf z}^{(j)}-{\rm
tr}\,(\Lambda^{T}Q),$ (19)

and then observes that

$\displaystyle\xi$ $\displaystyle\triangleq$ $\displaystyle\min_{\|{\bf
z}^{(j)}\|_{2}=1,Q,X^{(j)}{\bf z}^{(j)}=Q_{:,j}}\|{\bf
1}-\emph{\mbox{sign}}(\emph{\mbox{sign}}(Q){\bf 1})\|_{2}=\min_{\|{\bf
z}^{(j)}\|_{2}=1,Q}\max_{\Lambda}\mathcal{L}(Z,Q,\Lambda)$ (20)
$\displaystyle=$ $\displaystyle\min_{\|{\bf
z}^{(j)}\|_{2}=1,Q}\max_{\Lambda}\|{\bf
1}-\emph{\mbox{sign}}(\emph{\mbox{sign}}(Q){\bf
1})\|_{2}+\sum_{j=1}^{d}(\Lambda_{:,j})^{T}X^{(j)}{\bf z}^{(j)}-{\rm
tr}\,(\Lambda^{T}Q)$ $\displaystyle\triangleq$ $\displaystyle f_{rp}(X).$

Connecting beginning and end in (20) gives $\xi=f_{rp}(X)$. Based on (2), one
then has that the data can be properly memorized if and only if $f_{rp}(X)=0$.
This also means that as soon as $f_{rp}(X)>0$ the network can not properly
memorize the data, which is exactly what is claimed in the lemma. ∎

In what follows, we consider mathematically the most challenging, so-called
_linear_ , regime with

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

While the above lemma holds for any given data set $\left({\bf
x}^{(0,k)},1\right)_{k=1:m}$, to analyze (17) and (18), the RDT proceeds by
imposing a statistics on $X$.

2) _Determining the random dual:_ As is standard within the RDT, we also
utilize the so-called concentration of measure property, which basically means
that for any fixed $\epsilon>0$, we have (see, e.g. [29, 36, 31])

$\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.$

Another key ingredient of the RDT machinery is the following so-called random
dual theorem.

######  Theorem 1.

(Memorization characterization via random dual) Let $d$ be any odd integer.
Consider TCM SPNN with $d$ neurons in the hidden layer, and architecture
$A([n,d,1];\mbox{sign})$, 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}-\emph{\mbox{sign}}(\emph{\mbox{sign}}(Q){\bf 1})\|_{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}$
(22)

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)$ (23) $\displaystyle\Longrightarrow$
$\displaystyle\left(\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\right).$

###### Proof.

Follows as a direct $d$-fold application of the Gordon’s probabilistic
comparison theorem (see, e.g., Theorem B in [18] as well as Theorem 1,
Corollary 1, and Section 2.7.2 in [39] and Theorem 1, Corollary 1, and Section
2.3.2 in [38]).

In particular, for $d=1$, the statement of the above theorem becomes exactly
the Gordon’s comparison inequality, i.e., it becomes exactly, say, Theorem B
in [18]. For $d>1$, one then observes that

$\displaystyle f_{rd}(G,H)$ $\displaystyle\triangleq$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0,\|{\bf
z}^{(j)}\|_{2}=1}\max_{\|\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=$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0,\|{\bf
z}^{(j)}\|_{2}=1}\max_{\|\Lambda\|_{F}=1}\left(\sum_{j=1}^{d}\Lambda_{:,j}^{T}G_{:,j}+\sum_{j=1}^{d}\|\Lambda_{:,j}\|_{2}(H_{:,j})^{T}{\bf
z}^{(j)}-{\rm tr}\,(\Lambda^{T}Q)\right)$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0,\|{\bf
z}^{(j)}\|_{2}=1}\max_{\|\Lambda\|_{F}=1}\left(\sum_{j=1}^{d}\|{\bf
z}^{(j)}\|_{2}\Lambda_{:,j}^{T}G_{:,j}+\sum_{j=1}^{d}\|\Lambda_{:,j}\|_{2}(H_{:,j})^{T}{\bf
z}^{(j)}-{\rm tr}\,(\Lambda^{T}Q)\right),$

which contains exactly the summation of the $d$ terms from the lower-bounding
side of the Gordon’s inequality. Given that (18) also contains the summation
of exactly the corresponding $d$ terms from the other side of the inequality,
the proof is completed. ∎

3) _Handling the random dual:_ After solving the inner maximization over
$\Lambda$ and minimization over ${\bf z}^{(j)}$, we obtain for $f_{rd}(G,H)$
from (22)

$\displaystyle f_{rd}(G,H)$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0,\|\Lambda\|_{F}=1}\sum_{j=1}^{d}\|\Lambda_{:,j}\|_{2}\left(\|G_{:,j}-Q_{:,j}\|_{2}-\|H_{:,j}\|_{2}\right)$
(25) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\sqrt{\sum_{j=1}^{d}\left(\|G_{:,j}-Q_{:,j}\|_{2}-\|H_{:,j}\|_{2}\right)^{2}}$
$\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}}.$

Then

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}f_{rd}(G,H)$ (26)
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\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}}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\sqrt{\|G-Q\|_{F}^{2}-2d\sqrt{\frac{\|G-Q\|_{F}^{2}}{d}}\sqrt{\delta}+\delta
d}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\left(\|G-Q\|_{F}-\sqrt{\delta
d}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1.$

In the above considerations, we relied on the concentrations to obtain the
exact equalities. It is useful to note that the Cauchy-Schwartz enables to
obtain the corresponding inequalities (which are also sufficient for the
subsequent analysis) without actually relying on the concentrations. Namely,
by the Cauchy-Schwartz inequality, we first find

$\sum_{j=1}^{d}\|G_{:,j}-Q_{:,j}\|_{2}\|H_{:,j})\|_{2}\leq\sqrt{\sum_{j=1}^{d}\|G_{:,j}-Q_{:,j}\|_{2}^{2}}\sqrt{\sum_{j=1}^{d}\|H_{:,j})\|_{2}^{2}}=\|G-Q\|_{F}\|H\|_{F}.$
(27)

We then also easily obtain

$\displaystyle\sqrt{\|G-Q\|_{F}^{2}-2\sum_{j=1}^{d}\|G_{:,j}-Q_{:,j}\|_{2}\|H_{:,j})\|_{2}+\|H\|_{F}^{2}}$
$\displaystyle\geq$
$\displaystyle\sqrt{\|G-Q\|_{F}^{2}-2\|G-Q\|_{F}\|H\|_{F}+\|H\|_{F}^{2}}$ (28)
$\displaystyle\geq$ $\displaystyle\|G-Q\|_{F}-\|H\|_{F}.$

The above would then give the following inequality type alternative to (26)

$\displaystyle\phi_{0}$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}f_{rd}(G,H)$ (29)
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\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}}$
$\displaystyle\geq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-\|H\|_{F}$
$\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\left(\|G-Q\|_{F}-\sqrt{\delta
d}\right)$ $\displaystyle=$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1.$

Now we focus on the remaining optimization over $Q$. To that end we set

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

and 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(Q_{i,1:d})=1}\sum_{j=1}^{d}(G_{ij}-Q_{ij})^{2}}$
(31) $\displaystyle=$ $\displaystyle\sqrt{\sum_{i=1}^{m}z_{i}(G_{i,1:d})},$

with

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

To make generic considerations easier, we first look at the simplest scenario,
$d=3$.

_Handling $z_{i}(G_{i,1:d})$ for $d=3$:_ When $d=3$, there are four options
for signs of $Q_{i,1:3}$, i.e.
$\mbox{sign}(Q_{i,1:3})\in\\{[1,1,1],[-1,1,1],[1,-1,1],[1,1,-1]\\}$. When
signs of $G_{ij}$ and $Q_{ij}$ match the contribution of the corresponding
term $(G_{ij}-Q_{ij})^{2}$ is zero. When there is a mismatch, the contribution
is $G_{ij}^{2}$. Utilizing this observation, one then finds the corresponding
contribution for any of the four $\mbox{sign}(Q_{i,1:3})$ and ultimately, as
their minimum, the overall contribution

$\displaystyle\phi_{z}^{(1)}$ $\displaystyle=$
$\displaystyle\max(-G_{i1},0)^{2}+\max(-G_{i2},0)^{2}+\max(-G_{i3},0)^{2}$
$\displaystyle\phi_{z}^{(2)}$ $\displaystyle=$
$\displaystyle\max(-(-1)G_{i1},0)^{2}+\max(-G_{i2},0)^{2}+\max(-G_{i3},0)^{2}$
$\displaystyle\phi_{z}^{(3)}$ $\displaystyle=$
$\displaystyle\max(-G_{i1},0)^{2}+\max(-(-1)G_{i2},0)^{2}+\max(-G_{i3},0)^{2}$
$\displaystyle\phi_{z}^{(4)}$ $\displaystyle=$
$\displaystyle\max(-G_{i1},0)^{2}+\max(-G_{i2},0)^{2}+\max(-(-1)G_{i3},0)^{2}$
$\displaystyle z_{i}(G_{i,1:3})$ $\displaystyle=$
$\displaystyle\min_{i}\phi_{z}^{(i)}.$ (33)

When signs of $G_{i,1:3}$ match any of the four $\mbox{sign}(Q_{i,1:3})$
options, one clearly has $z_{i}(G_{i,1:3})=0$. The interesting cases therefore
are when there are mismatches between the signs of $G_{i,1:3}$ and allowed
signs of $Q_{i,1:3}$. Exactly four such cases exist
$\\{[-1,-1,-1],[1,-1,-1],[-1,1,-1],[-1,-1,1]\\}$. We now separately look at
the possible signs choices for $G_{i,1:3}$.

_(i) $\mbox{sign}(G_{i,1:3})=[-1,-1,-1]$:_ From (2.1), we then have

$\phi_{z}^{(1)}=G_{i1}^{2}+G_{i2}^{2}+G_{i3}^{2}\quad\phi_{z}^{(2)}=G_{i2}^{2}+G_{i3}^{2}\quad\phi_{z}^{(3)}=G_{i1}^{2}+G_{i3}^{2}\quad\phi_{z}^{(4)}=G_{i1}^{2}+G_{i2}^{2},$
(34)

and

$\displaystyle
z_{i}(G_{i,1:3})=\min_{i}\phi_{z}^{(i)}=\min\\{\phi_{z}^{(2)},\phi_{z}^{(3)},\phi_{z}^{(4)}\\}=\min\\{G_{i2}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i2}^{2}\\}.$
(35)

_(ii) $\mbox{sign}(G_{i,1:3})=[1,-1,-1]$:_ From (2.1), we then also have

$\phi_{z}^{(1)}=G_{i2}^{2}+G_{i3}^{2}\quad\phi_{z}^{(2)}=G_{i1}^{2}+G_{i2}^{2}+G_{i3}^{2}\quad\phi_{z}^{(3)}=G_{i3}^{2}\quad\phi_{z}^{(4)}=G_{i2}^{2},$
(36)

and

$\displaystyle
z_{i}(G_{i,1:3})=\min_{i}\phi_{z}^{(i)}=\min\\{\phi_{z}^{(3)},\phi_{z}^{(4)}\\}=\min\\{G_{i3}^{2},G_{i2}^{2}\\}.$
(37)

Due to symmetry, one then analogously easily finds as well

$\displaystyle\mbox{sign}(G_{i,1:3})=[-1,1,-1]$ $\displaystyle\Longrightarrow$
$\displaystyle z_{i}(G_{i,1:3})=\min\\{G_{i3}^{2},G_{i1}^{2}\\}$
$\displaystyle\mbox{sign}(G_{i,1:3})=[-1,-1,1]$ $\displaystyle\Longrightarrow$
$\displaystyle z_{i}(G_{i,1:3})=\min\\{G_{i2}^{2},G_{i1}^{2}\\}.$ (38)

A combination of (32),(32), (32), (32) , and (32) and the symmetry of standard
normals give

$\displaystyle\phi_{0}$ $\displaystyle\triangleq$
$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}f_{rd}(G,H)=\lim_{n\rightarrow\infty}{\mathbb{E}}_{G,H}\frac{1}{\sqrt{n}}\min_{\phi(Q)=0}\|G-Q\|_{F}-1$
(39) $\displaystyle=$
$\displaystyle\sqrt{\lim_{n\rightarrow\infty}{\mathbb{E}}_{G}\frac{\sum_{i=1}^{m}\left(\frac{1}{8}\min\\{G_{i2}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i2}^{2}\\}+\frac{3}{8}\min\\{G_{i2}^{2},G_{i1}^{2}\\}\right)}{n}}-1$
$\displaystyle=$
$\displaystyle\sqrt{\alpha{\mathbb{E}}_{G}\left(\frac{1}{8}\min\\{G_{i2}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i2}^{2}\\}+\frac{3}{8}\min\\{G_{i2}^{2},G_{i1}^{2}\\}\right)}-1.\vspace{-.0in}$

We summarize the above results in the following lemma.

######  Lemma 2.

(Memory capacity upper bound; $d=3$) Assume the setup of Theorem 1 with $d=3$.
For $d=3$, consider the $n$-scaled memory capacity from (4),
$c(3;\mbox{sign})$ and the following

($n$-scaled, $d=3$) memory capacity upper bound:
$\displaystyle\hat{c}(3;\mbox{sign})=\frac{4}{\frac{3}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\left(g^{2}+(1+g^{2})\mbox{erf}\left(\frac{|g|}{\sqrt{2}}\right)-\frac{2e^{-\frac{|g|^{2}}{2}}|g|}{\sqrt{2\pi}}\right)\mbox{erfc}\left(\frac{|g|}{\sqrt{2}}\right)e^{-\frac{g^{2}}{2}}dg}\approx\mathbf{4.025}.$

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

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

and

$\displaystyle\lim_{n\rightarrow\infty}{\mathbb{P}}_{X}(c(3,\mbox{sign})<\hat{c}(3,\mbox{sign}))\longrightarrow
1.$ (41)

###### Proof.

One first finds the expectations in (39) as

$\displaystyle{\mathbb{E}}_{G}\min\\{G_{i1}^{2},G_{i2}^{2}\\}$
$\displaystyle=$ $\displaystyle 2\phi_{g}^{(1)}$
$\displaystyle{\mathbb{E}}_{G}\min\\{G_{i2}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i3}^{2},G_{i1}^{2}+G_{i2}^{2}\\}$
$\displaystyle=$ $\displaystyle 6\phi_{g}^{(2)},$ (42)

where

$\displaystyle\phi_{g}^{(1)}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}g^{2}\mbox{erfc}\left(\frac{|g|}{\sqrt{2}}\right)e^{-\frac{g^{2}}{2}}dg$
$\displaystyle\phi_{g}^{(2)}$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\left((\mbox{erf}\left(\frac{|g|}{\sqrt{2}}\right)-\frac{2e^{-\frac{|g|^{2}}{2}}|g|}{\sqrt{2\pi}}+g^{2}\mbox{erf}\left(\frac{|g|}{\sqrt{2}}\right)\right)\mbox{erfc}\left(\frac{|g|}{\sqrt{2}}\right)e^{-\frac{g^{2}}{2}}dg.$
(43)

The rest follows from Theorem 1, the above discussion, and after setting
$\phi_{0}=0$ in (39). ∎

The above basically means that as long as the sample complexity $m$ is such
that $m>4.025n$ (where $n$ is the ambient dimension of the data vectors) the
network will not be able to memorize the data. Consequently, one has for the
memory capacity of the TCM SPNN with three neurons in the hidden layer,
$C(A([n,3,1];\mbox{sign}))<4.025n$.

_Handling $z_{i}(G_{i,1:d})$ for general (odd) $d$:_ For general $d$ one can
repeat the reasoning strategy presented above between (32) and (39). This time
though, there are $2^{d-1}$ options for the signs of $Q_{i,1:d}$ and one has
to be very careful to account for each of them. Eventually, one obtains the
following analogue to (39):

$\phi_{0}=\sqrt{\alpha\frac{\sum_{l=1}^{\lceil\frac{d}{2}\rceil}\binom{d}{\lceil\frac{d}{2}\rceil-l}\varphi_{1}(l;d)}{2^{d}}}-1,\quad\mbox{where}\quad\varphi_{1}(l;d)\triangleq{\mathbb{E}}_{G}\left\|\bar{G}_{1:l}^{(\lfloor\frac{d}{2}\rfloor+l)}\right\|_{2}^{2},\vspace{-.0in}$
(44)

and $\bar{G}^{(p)}$ is the vector obtained by taking the first $p$ components
of $G_{i,1:d}$ and sorting them in the increasing order of their magnitudes.
After handling the expectations, one arrives at the following theorem.

######  Theorem 2.

(Memory capacity upper bound; general $d$) Assume the setup of Theorem 1 with
general $d$. Let the network $n$-scaled capacity, $c(d,\mbox{sign})$, be as
defined in (4). First one has

$\displaystyle\varphi_{1}(l;d)=\varphi_{2}(l;d)\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\left((l-1)\varphi_{3}(g)\varphi_{4}(g)^{l-2}+g^{2}\varphi_{4}(g)^{l-1}\right)\left(1-\varphi_{4}(g)\right)^{\lfloor\frac{d}{2}\rfloor}e^{-\frac{g^{2}}{2}}dg,\vspace{-.0in}$
(45)

where

$\displaystyle\varphi_{2}(l;d)=l\binom{\lfloor\frac{d}{2}\rfloor+l}{l},\quad\varphi_{3}(g)=\mbox{erf}\left(\frac{|g|}{\sqrt{2}}\right)-\frac{2e^{-\frac{|g|^{2}}{2}}|g|}{\sqrt{2\pi}},\quad\varphi_{4}(g)\triangleq\mbox{erf}\left(\frac{|g|}{\sqrt{2}}\right).$
(46)

Further, consider the following

($n$-scaled general $d$) memory capacity upper bound:
$\displaystyle\hat{c}(d;\mbox{sign})=\frac{1}{\frac{1}{2^{d}}\sum_{l=1}^{\lceil\frac{d}{2}\rceil}\binom{d}{\lceil\frac{d}{2}\rceil-l}\varphi_{1}(l;d)}.$

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

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

and

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

###### Proof.

Clearly, there are two key components that need to be shown: __(i)__ for any
$d$, $\phi_{0}$ is as given in (44); and __(ii)__ $\varphi_{1}(l;d)$ is as
given in (45). We split the presentation into two parts. Each of the parts
addresses one of these two key proof components.

__(i)__ Determining $\phi_{0}$ for any $d$: The same mechanism presented in
(2.1)-(39) for $d=3$ applies or extrapolates to any $d$. Below we formalize
the extrapolation. Let ${\bf s}^{(i)}\triangleq\mbox{sign}(Q_{i,:})$ and ${\bf
g}^{(i)}\triangleq\mbox{sign}(G_{i,:})$. Taking ${\bf 1}$ as a column vector
(of appropriate dimension) of all ones, we have for a general $d$ analogue to
(2.1)

$z_{i}(G_{i,:})=\min_{i}\phi_{z}^{(i)}\quad\mbox{with}\quad\phi_{z}^{(i)}=\sum_{{\bf
s}^{(i)}{\bf 1}\geq 1}\sum_{j=1}^{d}\max(-s_{j}^{(i)}G_{ij},0)^{2},1\leq i\leq
2^{d-1}.$ (49)

Then, in an analogy with (34)-(2.1), the signs of $G_{i,:}$ that bring nonzero
contributions to $z_{i}(G_{i,:})$ are exactly the opposite ones of those of
$Q$. In other words, the relevant $G_{i,:}$ are those with ${\bf g}^{(i)}{\bf
1}\leq-1$.

($\star$) ${\bf g}^{(i)}{\bf 1}=-d$: Now, one observes that for ${\bf
g}^{(i)}{\bf 1}=-d$, (49) gives

$\displaystyle
z_{i}(G_{i,:})=\min_{i}\phi_{z}^{(i)}\quad\mbox{with}\quad\phi_{z}^{(i)}=\sum_{{\bf
s}^{(i)}{\bf 1}=1}\sum_{j=1}^{d}\max(-s_{j}^{(i)}G_{ij},0)^{2},1\leq i\leq
2^{d-1},$ (50)

which implies

$\displaystyle z_{i}(G_{i,:})=\min_{{\bf s}^{(i)}{\bf 1}=1}\frac{{\bf
1}^{T}+{\bf s}^{(i)}}{2}(G_{i,:}\circ
G_{i,:})^{T}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil}^{d}\right\|_{2}^{2}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil}^{(\lfloor\frac{d}{2}\rfloor+\lceil\frac{d}{2}\rceil)}\right\|_{2}^{2},$
(51)

where $\circ$ stands for the componentwise multiplication.

($\star\star$) ${\bf g}^{(i)}{\bf 1}=-d+2$: For the concreteness and without
loss of generality we take ${\bf
g}^{(i)}=\begin{bmatrix}-1&-1&\dots&-1&1\end{bmatrix}$. One then observes that
(49) gives

$z_{i}(G_{i,:})=\min_{i}\phi_{z}^{(i)}\quad\mbox{with}\quad\phi_{z}^{(i)}=\sum_{{\bf
s}_{1:d-1}^{(i)}{\bf 1}=0}\sum_{j=1}^{d}\max(-s_{j}^{(i)}G_{ij},0)^{2},1\leq
i\leq 2^{d-1},$ (52)

which implies

$z_{i}(G_{i,:})=\min_{{\bf s}_{1:d-1}^{(i)}{\bf 1}=0}\frac{{\bf
1}_{1:d-1}^{T}+{\bf s}_{1:d-1}^{(i)}}{2}(G_{i,:}\circ
G_{i,:})^{T}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil-1}^{d-1}\right\|_{2}^{2}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil-1}^{(\lfloor\frac{d}{2}\rfloor+\lceil\frac{d}{2}\rceil-1)}\right\|_{2}^{2}.$
(53)

In a similar fashion, one then finds for ${\bf g}^{(i)}{\bf 1}=-d+4$ and ${\bf
g}^{(i)}=\begin{bmatrix}-1&-1&\dots&-1&1&1\end{bmatrix}$

$z_{i}(G_{i,:})=\min_{{\bf s}_{1:d-2}^{(i)}{\bf 1}=-1}\frac{{\bf
1}_{1:d-2}^{T}+{\bf s}_{1:d-2}^{(i)}}{2}(G_{i,:}\circ
G_{i,:})^{T}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil-2}^{d-2}\right\|_{2}^{2}=\left\|\bar{G}_{1:\lceil\frac{d}{2}\rceil-2}^{(\lfloor\frac{d}{2}\rfloor+\lceil\frac{d}{2}\rceil-2)}\right\|_{2}^{2},$
(54)

and proceeds inductively until ${\bf g}^{(i)}{\bf 1}=-d+(d-1)=-1$. Taking into
account the associated combinatorial aspects, one finally has

${\mathbb{E}}z_{i}(G_{i,:})=\frac{\sum_{l=1}^{\lceil\frac{d}{2}\rceil}\binom{d}{\lceil\frac{d}{2}\rceil-l}\varphi_{1}(l;d)}{2^{d}},\quad\mbox{where}\quad\varphi_{1}(l;d)\triangleq{\mathbb{E}}_{G}\left\|\bar{G}_{1:l}^{(\lfloor\frac{d}{2}\rfloor+l)}\right\|_{2}^{2}.\vspace{-.0in}$
(55)

A combination of concentrations, (55), (22),(25), and (31) also gives

$\phi_{0}=\sqrt{\alpha\frac{\sum_{l=1}^{\lceil\frac{d}{2}\rceil}\binom{d}{\lceil\frac{d}{2}\rceil-l}\varphi_{1}(l;d)}{2^{d}}}-1,\quad\mbox{where}\quad\varphi_{1}(l;d)\triangleq{\mathbb{E}}_{G}\left\|\bar{G}_{1:l}^{(\lfloor\frac{d}{2}\rfloor+l)}\right\|_{2}^{2},\vspace{-.0in}$
(56)

which shows that $\phi_{0}$ is, indeed, exactly as stated in (44).

__(ii)__ Computing $\varphi_{1}(l;d)$: We take a vector of iid standard
normals, ${\bf g}\in{\mathbb{R}}^{\lfloor\frac{d}{2}\rfloor+l}$, and consider
$\bar{{\bf g}}$ as its sorted version, obtained by sorting the magnitudes of
${\bf g}$ in increasing order. Then assuming, without a loss of generality,
that the first $l$ magnitudes of ${\bf g}$ are the smallest and accounting for
other symmetric scenarios via a combinatorial pre-factor one has

$\displaystyle\varphi_{1}(l;d)$ $\displaystyle\triangleq$
$\displaystyle{\mathbb{E}}_{{\bf g}}\bar{{\bf
g}}_{1:l}^{2}=\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\left(\frac{1}{\sqrt{2\pi}}\right)^{\lfloor\frac{d}{2}\rfloor+l}\int_{{\bf
g}_{1:l}}\|{\bf g}_{1:l}\|_{2}^{2}\int_{|{\bf
g}_{l+1:\lfloor\frac{d}{2}\rfloor+l}|\geq\max(|{\bf
g}_{1:l}|)}e^{-\frac{\|{\bf g}\|_{2}^{2}}{2}}d{\bf g}$ (57) $\displaystyle=$
$\displaystyle\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\left(\frac{1}{\sqrt{2\pi}}\right)^{l}\int_{{\bf
g}_{1:l}}\|{\bf g}_{1:l}\|_{2}^{2}\left(1-\varphi_{4}(\max(|{\bf
g}_{1:l}|))\right)^{\lfloor\frac{d}{2}\rfloor}e^{-\frac{\|{\bf
g}_{1:l}\|_{2}^{2}}{2}}d{\bf g}_{1:l}.$

Moreover, one can again, without a loss of generality, assume that the largest
of the first $l$ smallest magnitudes of ${\bf g}$ is ${\bf g}_{l}$. Accounting
for other options through another combinatorial pre-factor, one also has

$\displaystyle\varphi_{1}(l;d)$ $\displaystyle=$
$\displaystyle\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\left(\frac{1}{\sqrt{2\pi}}\right)^{l}\int_{{\bf
g}_{1:l}}\|{\bf g}_{1:l}\|_{2}^{2}\left(1-\varphi_{4}(\max(|{\bf
g}_{1:l}|))\right)^{\lfloor\frac{d}{2}\rfloor}e^{-\frac{\|{\bf
g}_{1:l}\|_{2}^{2}}{2}}d{\bf g}_{1:l}$ $\displaystyle=$ $\displaystyle
l\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\left(\frac{1}{\sqrt{2\pi}}\right)^{l}\int_{{\bf
g}_{l}}\left(1-\varphi_{4}(|{\bf
g}_{l}|)\right)^{\lfloor\frac{d}{2}\rfloor}e^{\frac{-{\bf
g}_{l}^{2}}{2}}\int_{|{\bf g}_{1:l-1}|\leq|{\bf g}_{l}|}\|{\bf
g}_{1:l}\|_{2}^{2}e^{-\frac{\|{\bf g}_{1:l-1}\|_{2}^{2}}{2}}d{\bf
g}_{1:l-1}d{\bf g}_{l}$ $\displaystyle=$ $\displaystyle
l\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\frac{1}{\sqrt{2\pi}}\int_{{\bf
g}_{l}}\left(1-\varphi_{4}(|{\bf
g}_{l}|)\right)^{\lfloor\frac{d}{2}\rfloor}e^{\frac{-{\bf g}_{l}^{2}}{2}}$
$\displaystyle\times\left(\left(\frac{1}{\sqrt{2\pi}}\right)^{l-1}\int_{|{\bf
g}_{1:l-1}|\leq|{\bf g}_{l}|}\|{\bf g}_{1:l-1}\|_{2}^{2}e^{-\frac{\|{\bf
g}_{1:l-1}\|_{2}^{2}}{2}}d{\bf g}_{1:l-1}+{\bf g}_{l}^{2}\varphi_{4}(|{\bf
g}_{l}|)^{l-1}\right)d{\bf g}_{l}$ $\displaystyle=$ $\displaystyle
l\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\frac{1}{\sqrt{2\pi}}\int_{{\bf
g}_{l}}\left(1-\varphi_{4}(|{\bf
g}_{l}|)\right)^{\lfloor\frac{d}{2}\rfloor}e^{\frac{-{\bf g}_{l}^{2}}{2}}$
$\displaystyle\times\left(\left(\frac{(l-1)\varphi_{4}(|{\bf
g}_{l}|)^{l-2}}{\sqrt{2\pi}}\right)\int_{|{\bf g}_{1}|\leq|{\bf g}_{l}|}\|{\bf
g}_{1}\|_{2}^{2}e^{-\frac{{\bf g}_{1}^{2}}{2}}d{\bf g}_{1}+{\bf
g}_{l}^{2}\varphi_{4}(|{\bf g}_{l}|)^{l-1}\right)d{\bf g}_{l}$
$\displaystyle=$ $\displaystyle
l\binom{\lfloor\frac{d}{2}\rfloor+l}{l}\frac{1}{\sqrt{2\pi}}\int_{{\bf
g}_{l}}\left(1-\varphi_{4}(|{\bf
g}_{l}|)\right)^{\lfloor\frac{d}{2}\rfloor}e^{\frac{-{\bf
g}_{l}^{2}}{2}}\left((l-1)\varphi_{4}(|{\bf g}_{l}|)^{l-2}\varphi_{3}(|{\bf
g}_{l}|)+{\bf g}_{l}^{2}\varphi_{4}(|{\bf g}_{l}|)^{l-1}\right)d{\bf g}_{l}.$

The first combinatorial pre-factor, $\binom{\lfloor\frac{d}{2}\rfloor+l}{l}$,
accounts for the number of different smallest $l$ components locations. The
second combinatorial pre-factor, $l$, accounts for the number of different
choices for the location of the largest component among the fixed smallest $l$
ones. As (2.1) matches (45), this completes the second portion of the proof
related to computing $\varphi_{1}(l;d)$. Together with the first part, related
to determining $\phi_{0}$, this then also completes the entire proof of
Theorem 2. ∎

Despite heavy mathematics involved, the above theorem ultimately allows one to
actually obtain the concrete values for $\hat{c}(d,\mbox{sign})$ for _any_
$d$. For the first few admissible $d$’s, the capacity upper bounds that the
above theorem produces are shown explicitly in Table 1 together with the
replica symmetry based predictions of [14, 5] and the best known rigorous
upper bounds of [15]. The obtained results _exactly_ match the replica
symmetry based predictions for any $d$ and for $d\leq 5$ make the very first,
mathematically rigorous, progress in over 30 years. Also, as the results
suggest, one may expect that adding more neurons can substantially improve the
SPNN memorizing abilities.

4) _Double checking the strong random duality:_ Finally, the last step of the
RDT machinery assumes double checking if the strong random duality holds as
well. Due to highly discrete nature of the _sign_ functions, the corresponding
reversal considerations from [36] can not be applied and the strong random
duality is not in place. This implies that the presented results are indeed
strict memory capacity upper bounds.

##  3 Conclusion

In this paper we studied the memory capabilities of _sign_ perceptron neural
networks (SPNNs) with treelike committee machine (TCM) architectures. While
the abilities of the single perceptron neurons have been very _precisely_
characterized through a host of now classical works of pattern recognition,
machine learning theory, high dimensional geometry, statistics, and
information theory (see, e.g., [26, 9, 49, 48, 47, 8, 22, 3, 45, 10, 32, 11,
12, 16, 33, 37]), the corresponding network related results are much harder to
obtain and are very scarce to find in the literature even on a
_qualitative/scaling_ level. We here, in a way, bridge the gap and provide the
first mathematically rigorous progress in over 30 years.

In particular, we show that one can utilize the Random Duality Theory (RDT) as
a powerful mathematical engine to attack these types of problems. In
particular, in a statistical context, we design a generic framework for a
theoretical analysis of the memorization abilities of TCM SPNNs and
demonstrate that the framework allows for the underlying analysis to be done
on a _phase transition_ precision level for _any_ given (odd) number of the
neurons in the hidden layer. Although the underlying mathematics is quite
involved, one is eventually (perhaps surprisingly) left with a single integral
functional that allows to obtain concrete numerical estimates for the memory
capacity upper bounds. Moreover, the proven bounds precisely match the results
obtained through the statistical physics replica theory analysis in [14, 5].
For the number of hidden layer neurons $d\leq 5$, our results actually improve
on the best known mathematically rigorous ones from [15], thereby making a
first progress in studying this fundamental open NN problem in well over 30
years.

The range of possible extensions is rather wide. First, we here relied on the
basic RDT principles. The more advanced ones related to partially lifted (see,
e.g., [35, 34]) and fully lifted RDTs can be applied as well (see, e.g., [41,
42, 40]). Second, we considered the _sign_ activation functions. Many others
are of interest as well, ReLU, erf, quadratic, to name a few. The whole
machinery can be applied to all of these as well. Finally, we considered the
treelike committee machine (TCM) architecture. Various other architectures are
possible and have been of interest throughout the literature. For example, the
first next logical extension would be to the fully connected committee
machines as well as various forms of parity machines. Again, the whole
framework applies to these scenarios as well. Each of these specific problems
will be discussed 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] 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.
  * [18] Y. Gordon.  On Milman’s inequality and random subspaces which escape through a mesh in ${R}^{n}$.  Geometric Aspect of of functional analysis, Isr. Semin. 1986-87, Lect. Notes Math, 1317, 1988.
  * [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.  Various thresholds for $\ell_{1}$-optimization in compressed sensing.  available online at http://arxiv.org/abs/0907.3666.
  * [30] 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.
  * [31] 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.
  * [32] 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.
  * [33] M. Stojnic.  Another look at the Gardner problem.  2013\.  available online at http://arxiv.org/abs/1306.3979.
  * [34] M. Stojnic.  Lifting/lowering Hopfield models ground state energies.  2013\.  available online at http://arxiv.org/abs/1306.3975.
  * [35] M. Stojnic.  Negative spherical perceptron.  2013\.  available online at http://arxiv.org/abs/1306.3980.
  * [36] M. Stojnic.  Regularly random duality.  2013\.  available online at http://arxiv.org/abs/1303.7295.
  * [37] M. Stojnic.  Spherical perceptron as a storage memory with limited errors.  2013\.  available online at http://arxiv.org/abs/1306.3809.
  * [38] M. Stojnic.  Fully bilinear generic and lifted random processes comparisons.  2016\.  available online at http://arxiv.org/abs/1612.08516.
  * [39] M. Stojnic.  Generic and lifted probabilistic comparisons – max replaces minmax.  2016\.  available online at http://arxiv.org/abs/1612.08506.
  * [40] M. Stojnic.  Binary perceptrons capacity via fully lifted random duality theory.  2023\.  available online at arxiv.
  * [41] M. Stojnic.  Fully lifted random duality theory.  2023\.  available online at arxiv.
  * [42] M. Stojnic.  Studying Hopfield models via fully lifted random duality theory.  2023\.  available online at arxiv.
  * [43] R. Sun.  Optimization for deep learning: theory and algorithms.  2019\.  available online at http://arxiv.org/abs/1912.08957.
  * [44] R Urbanczik.  Storage capacity of the fully-connected committee machine.  J. Phys. A: Math. Gen., 30, 1997.
  * [45] S. Venkatesh.  Epsilon capacity of neural networks.  Proc. Conf. on Neural Networks for Computing, Snowbird, UT, 1986\.
  * [46] R. Vershynin.  Memory capacity of neural networks with threshold and ReLU activations.  2019\.  available online at http://arxiv.org/abs/2001.06938.
  * [47] J. G. Wendel.  A problem in geometric probability.  Mathematica Scandinavica, 1:109–111, 1962.
  * [48] R. O. Winder.  Single stage threshold logic.  Switching circuit theory and logical design, pages 321–332, Sep. 1961.  AIEE Special publications S-134.
  * [49] R. O. Winder.  Threshold logic.  Ph. D. dissertation, Princetoin University, 1962.
  * [50] Y. Xiong and J. H. Oh C. Kwon.  The storage capacity of a fully-connected committee machine.  NIPS, 1997.
  * [51] 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.
  * [52] 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.
  * [53] 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.
  * [54] C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals.  Understanding deep learning requires rethinking generalization.  ICLR, 2017.
  * [55] 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.