On the Optimal Memorization Power of ReLU Neural Networks
Authors: Gal Vardi
Gilad Yehudai
Ohad Shamir
Venue: ICLR 2022 Spotlight (2022)
Keywords: Expressivness
Memorization
Theory
VC-dimension
Deep learning theory

Abstract: We study the memorization power of feedforward ReLU neural networks. We show that such networks can memorize any $N$ points that satisfy a mild separability assumption using $\tilde{O}\left(\sqrt{N}\right)$ parameters. Known VC-dimension upper bounds imply that memorizing $N$ samples requires $\Omega(\sqrt{N})$ parameters, and hence our construction is optimal up to logarithmic factors. We also give a generalized construction for networks with depth bounded by $1 \leq L \leq \sqrt{N}$, for memorizing $N$ samples using $\tilde{O}(N/L)$ parameters. This bound is also optimal up to logarithmic factors. Our construction uses weights with large bit complexity. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.

Published as a conference paper at ICLR 2022
ON THE OPTIMAL MEMORIZATION POWER OF RELU NEURAL NETWORKS
Gal Vardi; Gilad Yehudai' & Ohad Shamir
Department of Computer Science
Weizmann Institute of Science
(gal.vardi, , g lad. yehudai, sead.shhaiii (chamir)@ves @wei zmann. ac
ABSTRACT
We study the memorization power of feedforward ReLU neural networks. We show that such networks can memorize any N points that satisfy a mild separabil- ity assumption using Ô (VN] parameters. Known VC-dimension upper bounds
imply that memorizing N samples requires 22( N(v parameters, and hence our construction is optimal up to logarithmic factors. We also give a generalized con- struction for networks with depth bounded by 1 S L S /N, for memorizing N samples using ( parameters. This bound is also optimal up to logarithmic factors. Our construction uses weights with large bit complexity. We prove that having such a large bit complexity is both necessary and sufficient for memoriza- tion with a sub-linear number of parameters.
INTRODUCTION
The expressive power of neural networks has been widely studied in many previous works. These works study different aspects of expressiveness, such the universal approximation property (Cy- benko 1989 Leshno et al. 1993). and the benefits of depth in neural networks (Telgarsky 2016 Eldan and Shamir| 2016] Safran and Shamir 2017 Daniely 2017 Chatziafratis et al. 2019). An- other central and well studied question is about their memorization power.
The problem of memorization in neural networks can be viewed the following way: For every dataset of N labeled samples (X1, ),..,,... .... (XN, UN) X' V, construct network N X -> ) such that (x;)) = y/ for every memorization power of neural networks, using different assumptions the activation function and data samples (see e.g. [Huang and Babri (1998); Huang (2003); Baum ( (1988); Vershynin (2020); Danicly (2019: 2020); Bubeck et al. (2020); Park et al. 2020g Hardt and Ma (2016) Yun et al. 2019); Zhang et al. (2021): Nguyen and Hein (2018): Rajput et al. (2021); [oontg (197)). The question of memorization also have practical implications on phenomenons such "double descent"
I,..., N. Many works have shown results regarding the
[Belkin et al. (2019); Nakkiran et al.] (2019)) which connects the memorization power of neural
networks with their generalization capabilities.
trivial lower bound on the required size of the network for memorizing N labeled points is implied by the VC dimension of the network (cf. Shhlee-Shwartz and Ben-David (2014) ). That is, if network with a certain size cannot shatter any specific set of N points, then it certainly cannot memorize all sets of N points. Known VC dimension bounds for networks with W parameters is on the order of ( (Goldberg and Jerrum 1995);; Bartlett et al. (1998) 2019)). Hence, it follows that memorizing N samples would require at least Ω (N')2) parameters. The best known upper bound is given in Park et al. (2020), where is shown that memorizing N' data samples can be done using neural network with O (N223) parameters. Thus, there clear gap between the lower and upper bounds, although we note that the upper bound is for memorization of any set of data samples, while the lower bound is for shattering a single set of data samples. this paper we ask the following questions:
"Equal contribution

---

Published as a conference paper at ICLR 2022
What is the minimal number of parameters that are required memorize N la- beled data samples? Is the task of memorizing any set of N data samples more difficult than shattering single set of N samples?
We answer these questions by providing construction of ReLU feedforward neural network which achieves the lower bound up to logarithmic factors. In this construction we use a very deep neural network, but with constant width of 12. In more details,
main result is the following:
Theorem 1.1 (informal statement). Let (x1,V1),- VI)..... (XN. UN) E Rd x {1,.... C) be set of N labeled samples of a constant dimension d, with ||x:|| S r for every and ||x; - x₁ 2 8 for every
i + j. Then, there exists a ReLU neural network F R ++ with width 12, depth Ô (VN).
and Ô (VN) parameters. such that F(x,) = yt for every E [N]. where the notation (()) hides logarithmic in N, C, C,
Comparing this result to the known VC bounds. we show that, up to logarithmic factors, our con- struction is optimal. This also shows, quite surprisingly, that up to logarithmic factors, the task of memorizing any set of N points is not more difficult than shattering a single set of N points, under the mild separability assumption of the data samples. We note that this result can also be extended to regression tasks (see Remark 3.3).
In our construction, the depth of the network is Ô (VN) We also give generalized construction
where the depth of the network is limited to some L S vN. In this case, the number of param- eters in our construction Ô ) (see Theorem 5. We compare this result to the VC-dimension bound from Bartlett al. 2019). and show that our construction is optimal up logarithmic factors.
Our construction uses a bit extraction technique, inspired by Telgarsky's 's triangle function (Telgaskky 2016)), and by Safran and Shamir (2017). Using this technique, we are able to use weights with bit complexity O O(VN), and deep neural networks to "extract" the bits of information from the specially crafted weights of the network. We also generalize our results to the case of having a bounded bit complexity restriction on the weights. We show both lower (Theorem 6.1) and upper (Theorem 6.2h bounds, proving that memorizing N points using network with ! parameters, for some E E 0.5] can be done if the bit complexity of each weight Ô (N*). Hence, our construction is also optimal, up logarithmic factors, w.r. the bit complexity of the network. We emphasize that also in previous works showing non-trivial VC bounds (e.g. Barttettt et al. (1998) 2 weights with large bit complexity are used. We note that increasing the bit complexity beyond 1//2 cannot be used to further reduce the number of parameters (see the discussion in section
RELATED WORK
MEMORIZATION UPPER BOUNDS
The problem of memorizing arbitrary data points with neural networks has rich history. Baum (1988) studied memorization in single-hidden-laeer neural networks with the threshold activation, and showed that [ neurons suffice to memorize N arbitrary points in general position in Rd with binary labels. Bubeck et al. (2020) extended the construction of Baum (1988) and showed that single-hidden hidden--dd--e ReLU networks with 4 [x1 hidden neurons
memorize N points in general
position with arbitrary real labels. In Huang et al. (1991) and |aartor and Antsaklis 1991) it is shown that Migle-hidden-layer networks with the threshold activation can memorize any arbitrary points, even if they are not in general position, using N 1 neurons. Huang and Babri (1998) proved a similar result for any bounded non-linear activation function a where either lim (2) or lim (2) exists. Zhang et al. (2021) proved that magle-hidden, layer ReLU networks can memorize arbitrary N points in I with arbitrary real labels using N neurons and 2/ +- parameters.
of N
Huang (2003) showed that two-hidden-layers networks with the sigmoid activation can memorize N points with O(VN) neurons, but the number of parameters is still linear in N. Yun et al. (2019) proved a similar result for ReLU (and hard-tanh) networks. |ershynin (2020) showed that threshold and ReLU networks can memorize N binary-labeled unit vectors in I separated by distance of
> 0, using ò (02/0² + vN) neurons and Ô ( 1//8 (d v (N) + N parameters. Rajput et al.
2

---

Published as a conference paper at ICLR 2022
2021 improved the dependence on by giving a construction with ( neurons and 0 (3 + N) parameters. This result holds only for threshold networks, but does not assume that the inputs are on the unit sphere.
The memorization power of more specific architectures was also studied. Hardt and Ma (2016) proved that residual ReLU networks with O(N) neurons can memorize points on the unit sphere separated by a constant distance. Nguyen and Hein (018)) considered convolutional neural networks and showed, under certain assumptions, memorization using ((N) neurons.
Note that in all the results mentioned above the number of parameters is at least linear in N. Our work is inspired by Park et al. (2020), that established a first memorization result with a sub-linear number of parameters. They showed that neural networks with sigmoidal or ReLU activations can memorize N points in Rd separated by a normalized distance of 6, using O (N2/3 + log(1 (1))) parameters (where the dimension d is constant). Thus, in this work we improve the dependence on N from 22/3 to vN (up to logarithmic factors), which is optimal. We also note that the first stage in our construction is similar to the first stage in theirs. In Park et al. (2020) there is also discussion about the bit complexity of the network, and the necessity that the bit complexity depends on to achieve memorization with sub-linear number of parameters.
Finally, optimization aspects of memorization were studied in Bubeck et al. (2020); Daniely 20199 2020
MEMORIZATION LOWER BOUNDS
Lower bounds on the number of parameters required for memorization are implied by bounds on the VC dimension of neural networks. Indeed, if W parameters not sufficient for shattering a single set of size N. then they are clearly not sufficient for memorizing all sets of size N. The
VC dimension of neural networks has been extensively studied in recent decades (cf. [Anthony and Bartlet (2009); Bartlett et al.] (2019). The most relevant results for our work are by Goldberg and
Jerrum 1995) and Bartlett et (2019). We discuss these results and their implications in Sections 4
[ 5
Trade-offss between the number of parameters of the network and the Lipschitz parameter of the prediction function in memorizing a given dataset are studies in Bubeck et al. (202T): Bubeck and
Sellke (202I).
THE BENEFITS OF DEPTH
In this work we show that deep networks have significantly more memorization power. Quite a few theoretical works in recent years have explored the beneficial effect of depth on increasing the expressiveness of neural networks (e.g.. Martens el al. (2013)] Eldan and Shamir (2016); Telgarsky
(2016): Liang and Srikant (2016); Daniely (2017); Safran and Shamir (2017); Yarotsky (2017 7);
Safran et al. (2019); Chatziaarras et al. )0 Vardi and Shamir Shamir(2020), Bresler and Nagaraj 2020
Venturi et al. (2021) Vardi et al.
(202T 1 ).. The benefits of depth in the context of the VC dimension
implied by, e.g., |arrlett et al. 2019). Finally, Park et al.] (2020) already demonstrated that deep
networks have more memorization power than shallow ones, albeit with weaker bound than ours.
2 PRELIMINARIES
NOTATIONS
For n E and i S j we denote by (nN the string of bits in places i until j inclusive, in the
binary representation of and treat it as an integer (in binary basis). For example, BIN BIN (3()
4. We denote by LEN(M) (n) the number of bits its binary representation. We denote (IN; = (n). For a function f and E N we denote by f(i the composition of f with itself times. We denote vectors in bold face. We use the Ô(N) notation to hide logarithmic factors, and use O(N)
to hide constant factors. For N we denote [n]] == (1..... n). We say that hypothesis class H. shatters the points XI...., N E X' if for every yi..... UN E {+1} there is E H. s.t. h(x,) = y for every 1,....,. N.
3

---

Published as a conference paper at ICLR 2022
NEURAL NETWORKS
We denote by (z) max 2] the ReLU function. In this paper we only consider neural net- works with the ReLU activation.
Let d N be the data input dimension. We define neural network of depth L N Rd I where (xx is computed recursively by
h1)) (W())x b()) for W E RRmixd b(U) E mm
h() (Wl (() for W E R b(i) R for 22....,
(x)) h(4) ((-)((-1) + b(4) for W(L) E ERIML 1, ( E ER
The width of the network is max m1. max(m1.... network as the number of weights of N which non-zero. It corresponds to the number of edges when we view the neural network as a directed acyclic graph. We note that this definition is standard in the literature VC dimension bounds for neural networks (cf. Bartlett al. (2019)).
mL-1}. We define the number of parameters of the
BIT COMPLEXITY
We refer to the bit complexity of a weight as the number of bits required to represent the weight. Throughout the paper we use only weights which have a finite bit complexity. Specifically, for N, its bit complexity is [logn]. The bit complexity of the network is the maximal bit complexity of its weights.
INPUT DATA SAMPLES
In this work we assume that we are given N labeled data samples (x1,
(xN, (NN. E R [C], and our goal is to construct network F Rd -> IR such that F(x;) = y: for every E [N]. We will assume that there separation parameter > O such that for every * we have ||x; - x, 2 6. We will also assume that the data samples have bounded norm, i.c. there is r such that [|x] < r for every E [A]]
Note that any neural network that does not ignore input neurons must have least d parameters. Existing memorization results (e.g.. Park al. (2020) assume that d is constant. As we discuss in Remark 3.2 in our work we assume that at most O(vN). We also note that since our bounds depend logarithmically on ö, then even if 8 depends polynomially on N it will not change our asymptotic bounds.
MEMORIZATION USING Ô (VN) PARAMETERS
In this section we prove that given finite set of N labeled data points, there is a network with Ö VN) parameters which memorizes them. Formally, we have the following:
Theorem 3.1. Let N, C E N. and r, 8 > O, and let (x1: vi),... (XN. UN) IRd x [C] be set of N labeled samples with ||x:|| S r for every and |x; x; 2 for every + j. Denote R = 10 1 vnd. Then, there exists neural network F RRd + with width 12 and depth
o VN (VNNoB(N)) +
N log(N) .max (log(R),
such that F(x.) 3/ for every E [N].
From the above theorem, get that the total number of parameters is Ô + VN). For d
O(VN) (see Remark 3.2 below) we get the lower bound presented Theorem 1.1 Note that except for the number of data points N and the dimension d, the number of parameters of the network depends only logarithmically on all the other parameters of the problem (namely, on C, r, 8 81). We also note that the construction can be improved by some constant factors, but preferred simplicity

---

with Published as a conference paper at ICLR 2022
over minor improvements. Specifically, we hypothesize that it is possible to give construction using width (instead of 12) similar to the result in Park et al. (2020). To simplify the terms in the theorem, assume that 1, otherwise (i.e., if all data points have norm smaller than 1) we just fix r = 1 and get the same result. In the same manner, we assume that < 1, otherwise we just fix 5 1.
Remark 3.2 (Dependence on d). Note that any neural network that does not ignore input neurons must have at least d parameters. In our construction the first layer consists of single neuron (i.e width 1), which means that the number of parameters in the first layer is d + 1. Hence, this dependence on d is unavoidable. Previous works (e.g.. Park et (e.g..Paark al.) (2200) assumed that is constant.
In our work, to achieve the bound of Ô VNN) parameters we can assume that either d is constant or it may depend on N with d = (VN).
Remark 3.3 (From classification regression). Although the theorem considers multi-class clas- sification, it is possible to use the method suggested in Park et al. (2020) to extend the result to regression. Namely, if the output is in some bounded interval, then we can partition it into smaller intervals of length c each. We define a set of output classes C with O (2) classes, such that each class corresponds to an interval. Now, we can use Theorem 3.7 to get an approximation of the output, while the number of parameters is linear in log (t).
3.1 PROOF INTUITION
Below we describe the main ideas of the proof. The full proof can be found in Appendix [A] The proof is divided into three stages, where at each stage we construct network F; for i E 21, 3}, and the final network is /' P3 F2 o Fj. Each subnetwork F; has width O()), but the depth varies for each such subnetwork.
We project the data points from Rd R. This stage is similar to the one used the proof of the main result from Park et al. (2020). We use a network with 2 layers for the projection. With the correct scaling, the output of this network on X1.... XN E Ted are points #1 ,I,...,IIN [zt xzl 2 for i + j. and |aæ| < R for every i where R = O (N2
Stage I:
Stage H: Following the previous stage, our goal is now to memorize (æ1, vI). (IN, yN) E R x [C). where the x.y's 's are separated by a distance of least 2. We also reorder the indices to assume w.l.o.g that 21 < 32 < EN. We split the data points into (oogg(N) intervals,
each containing V lo data points. We also construct crafted integers w1 ..., W /NN log(N) and
M1,.... U /N Ing(N) in the following way: Note that by the previous stage, we round x; to [ma], can be represented using log(R) bits. Also, each ys can represented by at most log(C) bits. Suppose that I; is the k-th data point in the j-th interval (where j [VNlog(() and k
{o. log(N) - 13). then we define uy, wy such that
BIN Iog R3) ())
= [
BIN BIN HoN
y/:
That is, for each interval j. the number uy has log(R) bits which represent the integral value of the k-th data point in this interval. In the same manner, wy has log(C") bits which represent the label of the k-th data point in this interval. This is true for all the data points in the j-th interval, hence wy and uy are represented with log(R). V
No and log(C) v [og(N) bits respectively.
N
I3 for each Ty where the i-th data
We construct a network F2 : R + 3 such that F2(x.)
Wy, Ug.
point is in the j.-th interval. The integers wy and uy are used parameters of the network Fz. Stage III: In this stage we construct a network which uses a bit extraction technique adapting Tel- garsky's triangle function (Telgarsky 2016) extract the relevant information out of the crafted
5

---

Published as a conference paper at ICLR 2022
I
integers from the previous stage. In more details, given the input
w
we sequentially extract
from u the bits in places k (R)( + until (k + 1) log(R) for k E 0,
No
and check whether is at distance at most from the integer represented by those bits. It is, then we extract the bits in places k log(C") + until (k + 1) log( from w, and output the integer represented by those bits. By the previous stage, for each x; we know that includes the encoding of | and since |z; 2j 2 2 for every j * i (by the first stage), there is exactly one such Hence, the output this network is the correct label for each Zz..
The construction is inspired by the works of Bartlett et al. (2019); Park et al. (2020). Specifically, the first stage uses similar results from Park et al. (2020) on projection onto -ddimensional space. The main difference from previous constructions is in stages II and III where in our construction we encode the input data points the weights the network. This is the main technique which allows us to reduce the required number of parameters from the Ô (N2/3) bound in Park et al. (2020) to Ô (22) We also note, that although we use the convention of counting the number of parameters without zero-weise weights,, in this section we do count zero weights, hence this result is comparable to Park et al. (2200) where they do count zero weights.
4
ON THE OPTIMAL NUMBER OF PARAMETERS
In section we showed that a network with width ((1) and depth Ô (VN) can perfectly memorize N data points, hence only Ô (VN) parameters are required for memorization. In this section, we compare our results with the known lower bounds.
First, note that our problem contains additional parameters besides N. Namely, d, C, r and 6. As discussed in Remark 3.2. we assume that d is either constant or depends on N with d O(vN). In this comparison we also assume that r and 8-1 are either constants or depend polynomially on N. For example, assume d and r 1/2, then to have N point in Rdd with norm at most r and distance at least from one another must have that 8-1 N 1. Hence, we can bound R poly(N) (where R is defined in Theorem 3.1. which implies log( R) = Oloog(N)). Moreover, we assume that C' I poly(N), because is reasonable to expect that the number of output classes is not larger than the number of data points. Hence, also log C)- = (loog(N) ()). In regression tasks, as discussed in Remark 3.3 we can choose to consist of [ classes where e either a constant or depends at most polynomially on the other parameters.
N. We note that for constant d, either or 8-1 must depend
Using that R, C S poly(N),, and tracing back the bounds given in Theorem 3.1 we get that the number of parameters of the network O (VN log(N)). Note that here the (()) notation only hides constant factors, which can also be exactly calculated using Theorem 3.1
By Goldberg and Jerrum (1995), the VC dimension of the class of ReLU networks with W param- eters is O(W*). Thus, the maximal number of points that can be shattered is O(W3). Hence, if shatter N points then W R(VN). In particular, it gives R(VN) lower bound for the number parameters required to memorize N inputs. Thus, the gap between our upper bound and the above lower bound only (Vlog(N)). which is sub-logarithmic.
Moreover, it implies that the number of parameters required to shatter one size-N set is roughly equal (up to sub-logarithmic factor) to the number of parameters required to memorize all size-N sets (that satisfy some mild assumptions). Thus, perhaps surprisingly, the task of memorizing all size-N sets is not significantly harder than shattering a single size-N set.
If further assume that C' depends on N, i.c., the number of classes depends the number of samples (or in regression tasks, as we discussed in Remark 3.3, the accuracy depends on the number of samples), then can show that bound is tight up to constant terms. Thus, in this case the Vīog(N) () factor is unavoidable. Formally, we have the following lemma:

---

Published as a conference paper at ICLR 2022
Lemma 4.1. Let C.N E N, and assume that C N for some constant 0. If can express all the functions of the form 9 [N] + [C] using neural networks with W parameters. then W
Proof. Let be the class of all the functionns [A]] [e [og(([)) {0, 13. The VC-dimension
bound from [Goldberg and Jerrum (1995) implies that expressing all the functions from F with neural networks requires W = Ω2
VVllo((N) parameters, since is equivalent to shattering a
set of size eN log(N). Assume that we can express all the functions of the form y [N] +
[C]
using networks with W parameters. Given some function f E F we can express it with neural network as follows: define a function g [N] + [C] such that for every n E [M] and i e logg(N)) the i-th bit of g(n) is in, We construct neural network for f. such that for an input (n, computes g(n) (using W parameters) and outputs its i-th bit. The extraction of the i-th bit can be implemented using the bit extraction technique from the proof of Theorem 3.1 Overall, this network requires O(W" + log(N)) parameters, and in this manner we can express all the functions
in F. This shows that W = O(W" + log(N)), but since we also have W = 92 ( (v N log(N)) then
W = S (. (ogg((N)))
LIMITING THE DEPTH
In this section we generalize Theorem 3.1 to the case of having bounded depth. We will then compare our upper bound on memorization to the VC-dimension bound from Bartlett et al. 2019). We have the following:
Theorem 5.1. Assume the same setting as in Theorem 3.1 and denote R == ddCro-1 Let L E
[V Then, there exists a network F Rdd RR with width O ( ( depth O (Vog(L) log(())
and a total of Ly/logLL)
N
log(R) +d) parameters such that F(x;) Yz for every
every i [N].
Note that for L = VN we get a similar bound to Theorem 3.1 In the proof we partition the dataset into 1.2 subsets, each containing I data points. We then use Theorem 3.1 each such subset and width O(1) to memorize the data points in
to construct a subnetwork of depth O (L-logí the subset. We construct these subnetworks such that their output on each data point outside of their corresponding subset is zero. Finally we stack these subnetworks to construct wide network, whose output the sum of the outputs of the subnetworks.
By Bartlett et al. (2019), the VC dimension of the class of ReLU networks with W parameters and depth is O(W (olooo()))) It implies that if we can shatter N points with networks of depth L, most O(VN), and that r, 8- and C are bounded by some PNly(N). Theorem 5.1 implies that we can memorize any N points (under the mild separability assumption) using networks of depth and W Ô ( parameters. Therefore, the gap between our upper bound and the above lower bound is logarithmic. also implies that, up to logarithmic factors, the task of memorizing any set of N points using depth-L neural networks is not more difficult than shattering single set of N points with depth-L networks.
then W 2 (TTN)NT) [o) As in section assume that d is either constant
Proof of Theorem 5./ We first construct network H Rd - R in the same manner the struction of F1 is the first stage of Theorem 331 (this construction is detailed in Lemma AA.2 the appendix). This is 2-layer network with width 1. We denote the output of H on the samples XI...., XN as I1,...,, INN. Note that by the construction |as| < O(R) for every i E [N] and Jar, x.y 2 for every i i-
We split the inputs to N subsets of size L each, we denote these subsets I I1,..., I, (assume N w.l.o.g. that 1/ is an integer, otherwise replace it with 2 ). For each subset Is we use stages and III from Theorem 3.1 to construct a network Fg. such that Fe(x.) = ys if m; E Tg- Note that
7

---

Published as a conference paper at ICLR 2022
only need to the last two stages since we have already done the projection stage, hence data samples are already one-dimensional. We construct network F. + RN such that:
(1 : (N)L((T)
F(x)=
We also define network G RR-/L22 - R which adds up all its inputs. Finally, we construct the network F R R as F = G H.
By the construction of each F& from Theorem 3.1 for every æ E R. if - x;| 2 for every i E In. then F& (a) O. For every i E [N]. there is exactly one k [ such that E Ig. Using the projection H. for this k we get that Fg (244 - y/, and for every + k we get that F((x,) = 0. This means that F (xx)) ys for every i [N].
The depth of F is the sum the depths of its subnetwork. Both H and have depth O(1), and by log(R) since each such network memorizes Vog(L)
Theorem 3.1 the depth of F5 most
log(R)) Finally, the width of F is the maximal width of its subnetworks. The width of G and H is 1. The width of each Fs. is also O(1)
2 samples. Hence, the total depth of F is O Vog(LL)
by Theorem 3.1 hence the width of F O ) which also the width of F.
Recall that the number of parameters of network is the number of non-zero weights. In our case, the network consists of AN subnetworks, where the weights between these subnetworks
zero. Each such subnetwork has depth (
Vlog(Z) loog()) (R) and width O(1). Also, the pro-
jection phase requires ((d) parameters. In total, the number of parameters in the network is log(It) + +d).
N
L
Le/lo(())
6 BIT COMPLEXITY LOWER AND UPPER BOUNDS
3.1 the bit complexity of the network is roughly /N log(N) (See Theo- rem A in the appendix). On one hand, having such large bit complexity allows us "store" and "extract" information from the weights of the network using bit extraction techniques. This enable memorize N data points using significantly less than N parameters. On the other hand, having large bit complexity makes the network difficult to implement on finite precision machines.
In the proof of Theorem
In this section we argue that having large bit complexity is necessary and sufficient if we want to construct a network that memorizes N data points with less than N parameters. We show both upper and lower bounds on the required bit complexity, and prove that, up to logarithmic factors, our construction is optimal w.r.t. the bit complexity.
First, we show simple upper bound on the VC dimension of neural networks with bounded bit complexity. For this upper bound, we view the neural network directed graph with U neurons, and where each weight is represented by B bits. Note that representing each parameter requires log(I)+ 2 log(U) bits, that is log( [3 bits for the weights magnitude, and 2 log(U) (U) bits for the input and output neuron of each edge.
Theorem 6.1. Let H the hypothesis class of ReLU neural networks with W parameters, where each parameter is represented by B bits. Then, the VC dimension of H is O B + W Wog(W)))
Proof. We claim that is a finite hypothesis class with at most 20 B+W log(W)) different func- tions. Let f be neural network in H. and suppose that it has at most W parameters and U W neurons. Then, each weight of if can be represented by at most B + log(U') bits, namely, 2 log(UU) bits for the indices of the input and output neurons of the edge, and B bits for the weight magnitude. Hence, of is represented by at most (B + log()")) bits. Since U < W we get that every function in H can be represented by most O( (B + log (W)) bits, which gives the bound on the
8

---

Published as a conference paper at ICLR 2022
size of H. An upper bound the VC dimension of finite classes is the log of their size (cf. Shalev- Shwartz and Sen-David (2014)) ). and hence the VC dimension of H O(WB + W log W
This lemma can be interpreted in the following way: Assume that want to shatter single set of N points, and we use ReLU neural networks with N parameters for some e E [0, 2/1 Then, the bit complexity of each weight in the network must be at least (((N) Thus, to shatter N points with less than N parameters, we must have neural network with bit complexity that depends Also, for e 2. our construction in Theorem 3.1 (which memorizes any set N points) is optimal, up to logarithmic terms, since having bit complexity of 12( (2(N) is unavoidable. We emphasize that existing works that show non-trivial VC bounds also use large bit complexity (e.g. Bartlett et al. 1998 ).19)).
N.
We now show an upper bound on the number of parameters a network for memorizing N data points, assuming that the bit complexity of the network is bounded:
Theorem 6.2. Assume the same setting as in Theorem
3.1 and denote R == dNCro-1 Let B E log( log(()) depth
[VN]. Then, there exists a network F IRd + E with bit complexity O (Vi B..
Vlog(B)
o
(
N B) log(B) and width O(1) such that F(x;) = yi for every i E [N].
B
The full proof can be found in Appendix B The proof idea is to partition the dataset into subsets, each containing B² data points. For each such subset we construct a subnetwork using Theorem 3.1 to memorize the points in this subset. We concatenate all these subnetwork to create one deep network, such that the output of each subnetwork is added to the output of the previous one. Using a specific projection from Lemma A.2 in the appendix, this enables each subnetwork to output for each data point which is not in the corresponding subset. We get that the concatenated network successfully memorizes the N given data points.
g
Assume, as in the previous sections, that 8-1 and C' are bounded by some poly(N) and d is bounded by OVVN). Theorem 6.2 implies that we can memorize any N points (under mild as- sumptions), using networks with bit complexity B and Ô (x)) parameters. More specifically, can memorize N points using networks with bit complexity Ô (Ns) and Ô (N²-s) parameters, for e E [0, 4] Up to logarithmic factors in N, this matches the bound implied by Theorem 6.1
7 CONCLUSIONS
In this work we showed that memorization of N separated points can be done using a feedforward ReLU neural network with Ô (VN) parameters. We also showed that this construction is optimal up to logarithmic terms. This result is generalized for the cases of having a bounded depth network, and a network with bounded bit complexity. In both cases, our constructions optimal up to logarithmic terms.
An interesting future direction is to understand the connection between our results and the optimiza- tion process of neural networks. In more details, it would be interesting to study whether training neural networks with standard algorithms (e.g. GD or SGD) can converge to a solution which mem- orizes N data samples while the network have significantly less than N parameters.
Another future direction is to study the connection between the bounds from this paper and the generalization capacity of neural networks. The double descent phenomenon (Belkin et al. (2019) suggests that after network crosses the "interpolation threshold", able to generalize well. Our results suggest that this threshold may be much smaller than N for dataset with N samples, and it would be interesting to study if this is true also in practice.
Finally, it would be interesting to understand whether the logarithmic terms are indeed necessary for the construction, or these are artifacts of our proof techniques. If these logarithmic terms are not necessary, then it will show that for neural network, the tasks of shattering a single set of N points, and memorizing any set of N points are exactly as difficult (maybe up to constant factors).
upper bounds

---

Published as a conference paper at ICLR 2022
REFERENCES
M. Anthony and P. L. Bartlett. Neural network learning: Theoretical foundations. university press, 2009.
cambridge
P. L. Bartlett, V. Maiorov. and R. Meir. Almost linear ve-dimension bounds for piecewise polynomial networks. Neural computation, 10(8):255-2173, 1998.
P. L. Bartlett, N. Harvey, C. Liaw, and A. Mehrabian. Nearly-tigh ve-dimension and pseudodimen- sion bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2300 2019.
E. Baum. On the capabilities of multilayer pereeptrons. Journal of complexity, 4(3):193-215, 1988.
M. Belkin, D. Hsu, Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical bias- variance trade-off. Proceedings of the National Academy of Sciences, 116(32): 11849-158544 2019.
G. Bresler and D. Nagaraj. Sharp representation theorems for relu networks with precise dependence on depth. arXiv preprint arXiv:2006. 04048, 2020.
S. Bubeck and M. Sellke. A universal law of robustness via isoperimetry. arXiv preprint arXiv:2105. 128066 2021.
S. Bubeck, R. Eldan, Y. T. Lee, and D. Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint wxXiv:2006.02855, 2020.
S. Bubeck, Y. Li, and D. M. Nagaraj. A law of robustness for two-layers neural networks. In Conference on Learning Theory, pages 404-820, PMLR, 2021.
V. Chatziafratis, S. G. Nagarajan, I. Panageas, and X. Wang. Depth-width trade-off's for relu net- works via sharkovsky's 's theorem. arXiv preprint arXiv:1912.04372 2019.
G. Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314, 1989.
A. Daniely. Depth separation for neural networks. In Conference on Learning Theory, pages 690- 696. PMLR, 2017.
A. Daniely. Neural networks learning and memorization with (almost) no overpparamtterizaaion.. arXiv preprint 10X097991..09873, 2019.
A. Daniely. Memorizing gaussians with no over-parameterizzion via gradient decent on neural networks. arXiv preprint wrXiv:2003.1285, 2020.
R. Fldan and O. Shamir. The power of depth for feedforward neural networks. In Conference on learning theory, pages 907-940. PMLR, 2016.
W. Goldberg and M. R. Jerrum. Bounding the vapnik-chervonenkis dimension of concept classes parameterized by real numbers. Machine Learning. 18(2-3)113--14, 1995.
M. Hardt and T. Ma. Identity matters deep learning. arXiv preprint
2016.
G.-B. Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks, 14(2):274-281, 2003.
G.-B. Huang and H. A. Babri. Upper bounds the number of hidden neurons in feedforward networks with arbitrary bounded nonlinear activation functions. IEEE transactions on neural networks, 9(1):224 2299,,229, 1998.
S.-C. Huang, Y.-F Huang, et al. Bounds on the number of hidden neurons in multilayer perceptrons. JEEE transactions neural networks, 2(1):47-55, 1991.
10

---

Published as a conference paper at ICLR 2022
M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken. Multilayer feedforward networks with polynomial activation function can approximate any function. Neural networks, 6(6):861-86) 1993.
Liang and R. Srikant. Why deep neural networks for function approximation? arXiv preprint arXiv: vrXiv:/610.44000 2016.
Martens, A. Chattopadhya, T. Pitassi, and R. Zemel. On the representational efficiency of stricted boltzmann machines. In Advances in Neural Information Processing Systems, pages 2877-2885, 2013.
Nakkiran, G. Kaplun, Y. Bansal, Yang. B. Barak, and I. Sutskever, Deep double descent: Where bigger models and more data hurt. arXiv preprint arXiv:1912.00222,, 2019.
Q. Nguyen and M. Hein. Optimization landscape and expressivity of deep enns. In International conference on machine learning, pages 3730-3739, PMLR, 2018.
Park, J. Lee, C. Yun, and J. Shin. Provable memorization via deep neural networks using sub- linear parameters. arXiv preprint 0rXiv:2010.1336. 2020.
S. Rajput, K. Sreenivasan, D. Papailiopoulos, and A. Karbasi. An exponential improvement on the memorization capacity of deep threshold networks. arXiv preprint arXiv:2/06607724, 2021.
I. Safran and O. Shamir. Depth-width tradeoffs in approximating natural functions with neural networks. In International Conference on Machine Learning, pages 2979-2987. PMLR, 2017.
I. Safran, R. Eldan, and O Shamir. Depth separations in neural networks: What is actually being separated? arXiv preprint arXiv:1904.06900 06984, 2019.
M. A. Sartori and P. J. Antsaklis. simple method to derive bounds on the size and to train multilayer neural networks. IEEE transactions neural networks. 2(4):467-471, 1991.
Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
E. D. Sontag. Shattering all of 'k' 'o'points in "general position" requires (k-1)/2 parameters. Neural Computation, 9(2):337-348, 1997.
M. Telgarsky. Benefits of depth in neural networks. In Conference learning theory, pages 1517- 1539. PMLR, 2016.
G. Vardi and O. Shamir. Neural networks with small weights and depth-separation barriers. arXiv preprint arXiv:2006.00 00625, 2020.
G. Vardi, D. Reichman, T. Pitassi, and O. Shamir. Size and depth separation in approximating benign functions with neural networks. In Conference on Learning Theory, pages 4195-4223. PMLR, 2021.
L. Venturi, S. Jelassi, T. Ozuch, and J. Bruna. Depth separation beyond radial functions. arXiv preprint arXiv:2 2021.
R. Vershynin. Memory capacity of neural networks with threshold and relu activations. arXiv preprint arXiv:2001.06933, 2020.
D. Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
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 15558- 15569, 2019.
C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 2021.

---

Published as a conference paper at ICLR 2022
A PROOF FROM SECTION 3
We first give the proofs for each of the three stages of the construction, then we combine all the stages to prove Theorem 3.1 For convenience, we rewrite the theorem, and also state the bound on the bit complexity of the network:
Theorem A.I. Let N, F, C. E N. r, > O. and let (x1,9)...... (XN, UN) E R2 [C] be set of N labeled samples with ||x,|| S r for every i and ||x - x,ll 2 ó for every i # j. Denote R : 10r VTd. Then, there exists a neural network : Rd + IK with width 12, depth O ( (VN (Ng(N)) + JogiNT max (log(H), log(C))) and bit complexity bounded by
0 (log(d) log(N) max (log( R), log(C))) such that F(x:) = ye for every E [N].
A.1 STAGE I: PROJECTING ONTO A ONE-DIMENSIONAL SUBSPACE
Lemma A.2. Let XI. R& with ||x:|| for every i and [| - x,yl 8 for every i + j. Then, there exists neural network F R - R with width 1, depth 2, and bit complexity log (2d F(X,) 2 for every + j.
such that 0 F(x,) I 10rN28-1 Vdd for every
[N] and [F(x,)
To show this lemma we use a similar argument the projection phase from Park et al. 2020 where the main difference is that we use weights with bounded bit complexity. Specifically, we use the following:
Lemma A.3 (Lemma 8 from Park et al. (2020). Let N, E N, then for any distinct , X E 2 there exists a unit vector Ie such that for all + j:
8 R
1 N2 x;
x;1l S Iu (x: - x,)1 S I|x: x,ll
(1)
Proof of Lemma We first use Lemma A.3 to find u E Rdd that satisfies Eq. 1 Note that
||u|| = 1, hence every coordinate of u is smaller than 1. We define ú E Rd such that each of its coordinates is equal to the first [log (dN2 /T) bits of the corresponding coordinate of u. Note that
|| - ull 2ing(a vFj
NaVad' For every i o j we have that:
i T (x: x,)1 Z |u"
(x;
x3)1 i u)
(x: [Xx]]
M
|x;
||x; - x,| ull
Rd
N
|x; X
||x; - X₁ll
nd
N
N2 /T
1
|x x,
(2)
N2 nd
We also have for every i [N]:
xx|
< |u x
+ (u
u) T Xx
1
< |x] +
xxi|l
S 2||x|||-
N2
Let b : - min min, [[]]]] x, the network F Rd > IR in the following way:
x, + 1, and note that by Eq. 3 we have 6 S 2r + 1. We define
F(x) (2N28-1
(ū + b)
We show the correctness of the construction. Let * j. then we have that:
F((:)) F(x;)1 = - lo (ū" x; + - (ū x, + b)
= (2N28-1 Vml) x; + (ū_x, + b)
-2NN2-- û [xx - x,)l 22,
12

---

Published as a conference paper at ICLR 2022
T'x, where the second equality is because by the definition of we have that u x, + 2 0 for every
and the last inequality is by Eq. (2) and the assumption that ||x; x,l 2 8 for every i + j. Now,
let i [N], then we have:
[F(x)]] = (2NN2 o x; +))
=(2N220 (ū x, +)
S <22N2 (4r + 1) S 10r VTd,
where the second to last inequality is since b v 2r + and Eq.
The network F' has depth 2 and width 1. The bit complexity of the network can be bounded by log BddrN~/501) This is because each coordinate of i can be represented using 1og(dN2>/F) bits, the bias b can be represented using at most [log(2r+ 1)] bits and the weight the second layer can be represented using ( bits.
A.2 STAGE II: FINDING THE RIGHT SUBSET
Lemma A.4. Let 01 < .... <. EN < R with R > O, Ty E for every i E [N] and [; - xzl 2
for every i + j. Let m E N with m < N and let Wi,..., Wm E N where LEN(W;) < b for every j E [m]. ketk: := [. Then, there exists neural network F R - IR with width 4, depth 3m + and bit complexity b + [log(R) such that for every E [N] we have that F(x;) 11:
Proof. Let E [m]. We define network blocks Fy R + R and Fj : RR2 R in the following way: First, we use Lemma A.6 construct F} such that (x) 1 for every x E [[=j,a-*+I] [=nz + 1]]. and Ex(x) = 0 for x [ - or [ + +1 1. In particular, (2:) = 1 if E [j A k + 1. ke), and (z())) = 0 otherwise. Note that since k is
defined with ceil, possible that j 2 N, if this is the case we replace j with N. Next, we define:
F2
2
x + wi 12((2))
y
T
Finally we define the network F(x)
Fm o
0 (we can use one extra layer to
augment the input with an extra coordinate of 0).
We show that this construction is correct. Note that for every e [MV, if we denote [ then (x())) = and for every j' # j we have (x:) = 0. By the construction of F' we get that
F(x,) E
The width of F at every layer j is at most the width of F, + 2, since also keep copies of both and y, hence the width is at most 4. The depth of F3 is 2, and F' is composition of the Ej ) and extra layer in the output extract the last coordinate. Hence, its depth is 3m + 2. The bit complexity is bounded by the sum of the bit complexity of F; and the weights wy. hence it is bounded by b+ [log([t)].
with extra layer for the input to get x
A.3 STAGE III: BIT EXTRACTION FROM THE CRAFTED WEIGHTS
Lemma A.S. Let p,n,C E N. Let u E N with LEN(U) = p. n and let w N with Assume that for any E, (0.1...., - 1} with # ls have that BIN (IN-)(+1--((-1((m) BIN (INp:+11p((+t)(a))
LEN(W) =
2 2. Then, there exists a network F RR3 + TR with width 12, depth 3n max{p, c) + 2n - 2 and bit complexity max c} + 2, such that for every x > 0, if there exist j E I0.,...., 1) where x BIN (oNoi then:
x
F
(INesHHee(tn(uu))
13

---

Published as a conference paper at ICLR 2022
Proof. Let E {0, 1......... 1}. and denote by (p()) o(o(22) 042 2)) the triangle function
due to Telgarsky (2016). We construct the following neural network F;:
T v
T
p((+t))) m)
p((tp)
2
2
1((+)))))
F
((ie)
2
2
po(()+1)))) 1)e)
2
2
(ke)
w
fol( 1).e)
cn
20e13
y
where we define yi :- BIN ((+))) if [BIN, ((+ (u), BIN (pt1((++1)) + and
y: if BIN p
((
The construction uses two basic building blocks: The first using Lemma A.7 twice, for a and w. This way we construct smaller networks F.", F. such that:
())()+1))0) (((++)))))
so(t-p)
F
so((-p)
2"
2
BIN 1:
(o((it))c))
F
(oltec) (o(to)
2m.
2 2miet2)
p((itt))))
n
2
(nn
BIN
The second is to construct yı. We use Lemma A.8 with inputs æ and ((N))++(()))))( and denote the output this network by ys. We use the tollowing 1-layer network:
BIN BIN + a (ū.-2 2 2ct1 + BIN
Note that if 8s = then the output of the above network is BIN, BINec+1((+1))((x)))) and if g: = 0 then the output the network is since BIN;c+L(((1)))(())) 29.
The last layer of F; is just adding the output to and using the identity on the other coordinates which are being kept as the output, while the other coordinates (namely, the last output coordinates of F and F² do not appear in the output of F, Also note that all the inputs and outputs of the networks and basic building blocks are positive, hence acts as the identity on them. This means that if FI" is deeper than F." (or the other way around), then can just add identity layers to F." which do not change the output, but make the depths both networks equal. Finally we define:
== G Fa-1 o Fo H.
where: (1) G RR IR is I-layer network that outputs the last coordinate of the input, and; (2)
H 3 + R a 1-layer network such that:
H
W
2
1
2n0e
20-011
where assume that x. u.u.u. 0.
I En- Vi. As-
We show the correctness of the construction. We have that F
sume there exists j {0.1...,, n 1} such that [x] BIN JINP (: construction of Yi we have that y, BIN=)+tee(++((rr and for every other + j. since BIN (-(4)::-(e-1)(u)) BIN (IN 2 2, we must have that x > BIN--4t1.p
Then, by the
or x < BIN BIN - 2. which means that ye = 0. In total we get the the output of equal m y/ リj BINe./+1ee---1 (w) required.
14

---

Published as a conference paper at ICLR 2022
We will now calculate the width, depth and bit complexity of the network F. The width of each Ft" and F," is equal to 5 by Lemma A.7 and we need two more neurons for x and y. In total, the width is bounded by 12. Note that all other parts of the network (i.e. H, G and the network from Lemma A.8) require less width than this bound. For the depth, by Lemma A.7 the depth of each F?" and FTD is at most 3 max (p. c), adding the construction from Lemma A.8 the depth of each F, is at most 3 max c} + 2. Summing over all i, and adding the depth of G and H we get that the depth of F' is bounded by 3n max(p, c} + 2n 2. Finally, the bit complexity of P7" F and H is bounded by max c) + 2, and all other parts of the network require less bit complexity. Hence, the bit complexity of bounded by n max c) 2.
A.4 PROOF OF THEOREM 3.1
The construction is done in three phases. We first project the points onto a I-dimensional subspace, where the projection preserves distances up some error. The second step to split the points into /N log subsets, and to extract two weights containing "hints" about the points and their labels. The third step is to parse the hints using an efficient bit extraction method, and to output the correct label for each point.
Throughout the proof we assume w.l.o.g. that the following terms are integers since we use them as indices: / N log(N), [o]( log(R), log(C). If any of them is not an integer we can just replace with its ceil (i.e. [log(R)] instead lo)( This replacement changes these numbers by most 1, which in turn can only increase the number of parameters bit complexity by at most a constant factor. Since we give the result using the O()) notation, this does not change it. Also, note that the width of the network is independent of such terms.
For the first stage, we use Lemma A.2 to construct a network Fi Rdd + R such that (x:): S 10r v for every i E [N] and [x, - Fi (x,)) ) 2 2 for every i # j.
We denote R == 10r.N28-1/m,, and we denote the output of F1 on the samples x x Rd as æ1...., NN E for simplicity. We also assume that the x, 's are in increasing order, otherwise reorder the indices. This concludes the first stage.
For the second stage, we define two sets integers Wi,..., w V Mogg(N) each represented by V N ToR(NT log(C') bits, and u1.....
(N) each represented by ToR(Ny log(R) bits, in the following way: For every E [N] let j
N
i (og(N) and k : mod V v We set:
BIN tor) Jog(() (wy) = Vi
log 1(0+) (I)( (uy) = [x;]]
We now use Lemma A.4 twice to construct two networks F : IR + R and F R - R such that
log(N) N
F1" (z.) = W), and F (x:) = Uj for ji =
We construct the network F2 : - IR to
be a concatenation of the two networks, with an additional coordinate which outputs o (xx (since the inputs are positive, this coordinate just output the exact input). Namely, we construct network
such that for every E [N] we have
Fa(2s) =
Ugy
where j, =
log(N) (N)
For the third stage, we use Lemma A.5 to construct a network F3 R23 - R. such that for every x >
0, if there exist E 0,
log(N) N
}
such that [m] (NNoo(R)) ()+)) (u),
then:
F3
15

---

Published as a conference paper at ICLR 2022
Finally, construct the network F: R + Ra as F(x) = F3 o F2 Fi(x).
We show the correctness of the construction. Let E [M], and let = F(x.). By the con- struction of F2 and the numbers wi...., logg))) U1 VN log(Nij if we denote j :=
then we have that: (1) P2 Pi(x)) = (Fi
log (N) and k := i (mod, N
N [Ng
(2)
Wj
[IN (+)- (R)-((+1))( = [Fi (x:)J; and (3) (HNlo = V/. Finally,
by the construction of F3s we get that = F3 o F2 Fi(x) 4 as required.
y:
The width of the network F, namely the maximal width of its subnetworks, is the width of F3, which 12. The depth of F is the sum of the depths of each of its subnet- works. The depth of Fi is 2, the depth of F2 is O (VVNogg(N) and the depth of F3 o [N max (log(R), (ogg()),oo(())) log(())). Hence, the total depth of can be bounded by (og(())+ Tog(N) max {log( RR), lo)(.
The bit complexity of F is the maximal bit complexity of its subnetworks. The bit complexity of Fi is log (3dr (=0-1)
log(d) + log(R/3)). the bit complex- ity of F2 is O log(N] max{log(A)))) (R), log())) and the bit complexity of F3 is also N
N
log(N) max (log( (R), Iog(C))) In total, the bit complexity of F can be bounded by O (log(d) (N)(N) max max (a logg)))
o (v
A.5 AUXILIARY LEMMAS
Lemma A.6. Let a, b E N with < b. Then, there exists neural network F with depth 2, width 2 and bit complexity LEN(b) such that F(x) = 1 for x E (a, b) and F(x) = 0 for x > + or
Proof. Consider the following neural network:
F(z) a11 a (2a 2r)) a(1 o(2x - 2b)) -
easy to see that this networks satisfies the requirements. Also, its bit complexity at most LEN(b), since a < b, hence a can be represented by at most LEN(b) bits.
Lemma A.7. Let n E and let i,j E N with i < j n. Denote Telgarsky's triangle function by (p(2) := (2z)
(44=))).. Then, there exists a neural network F IR² - R with width 5, depth 3(j - i + 1), and bit complexity n + 2, such that for any x E with LEN(#) & n, if the input
(2())
(((-1)) 1) (0(1-1)
2
20
of F is
then outputs:
F
2
BIN
(z)
Proof. We use Telgarsky's function extract bits. Let N with LEN(x:) n, and let i N with i i n. Then, we have that:
(IN,(x) - 2n22-i (+())
I
(0()
(4)
2
2n+2
2n
2n+I
The intuition behind Eq. (4) is the following: The function (1))) is piecewise lincar function with 21-1 "bumps". Each such "bump" consists of two linear parts with a slope of 2 the first linear part goes from 0 to and the second goes from to O. Let E N with at most bits in its binary representation. It can be seen that the i-th bit of æ is 1 if (p()) (5= 2 is on the second linear part (i.e. descending from to and its i-th bit is 0 otherwise. This shows that (i()) ( 241z)
(p()) ( + -+r) is equal to 2i-n-2 the i-th bit is 1, and this expression is negative otherwise. The correctness of Eq. follows.
16

---

Published as a conference paper at ICLR 2022
Let j, E N with j and denote := j - i. Using the construction above as a building block, we construct network which outputs BIN in the following way: For E {0.1,...,c c define
1+6)
2
2
Fe: R3
R to be the neural network, such that for an imput
p 1+0
it outputs
2
2
(olite) plite)
x
2
2n+1
The network F3 is obtained by composing the first two coordinates with
2
20
(
Telgarsky's function so, and then the last coordinate is calculated using Eq. 4 Finally, define: F ;= Foo...o Fo. and we augment the input of Fo, such that its last coordinate is zero. The output of F is required since
2 2I BIN++e(x) = BIN (I)
t=
Finally, we compute the width, depth and bit complexity of F. Its width is bounded by twice the width of yo (which is 2). plus an extra neuron for computing the output y. hence its width is bounded 1), since we need two layers to compute &o and an extra layer
by 5. Its depth equal to 3(j to compute the output Finally, the bit complexity is bounded by n + 2, since the largest weight in the network at most 2n+2
Lemma A.8. There exists network F R R with width 2 depth and bit complexity 2 such that F
(w)
(7)
1 i E b,, y 1] and F
if > y or x prr<y-$s
Proof. We consider the following neural network:
(0)=
xc
F
- a0 o(2y 2x)) + 1000011000 02x x 2y - 2)) -
It is easy to see that this network satisfies the requirements. It has width 2, depth 2 and bit complexity
B PROOF FROM SECTION 6
Proof of Theorem 6.2 We first Lemma A.2
construct network H IRd - R in the same manner the construction of Fi is the first stage of Theorem 3.1. This a 2-layer network with width and bit complexity of Olog(())) We denote the output of H on the samples X1, ,,...., XN as I1, .i,...,, NN. Note that by the construction |x]| < O(R) for every i E [N] and j x, 2 2 for every # J.
We now split the inputs to N B2 subsets of size B each, we denote these subsets as II..... I (We M2
assume w.l.o.g. that Fr use Theorem 3. to construct a network F. which memorizes the points in Ix. with the following changes: (1) There is an additional coordinate which memorizes the input and output as is; and (2) The output of the network is added to the output of the network for the previous subset h 1.
7 N. is an integer, otherwise we can replace it with IN )). For each subset I we
For t 1, we set this coordinate to be zero. That is, if x; Iy then Fv
14 (()
23:
22
+ Vs
otherwise Fk ((+))
Finally, we construct the network F: Fdd R as:
F= G Fx o
H
where G y-
By the construction of each F5. from Theorem 3.1 for every x E R. if [x -x,1 2 for every i Ix. then (x) 0. For every [N], there is exactly one l: [N/B2] such that Jg. Using the
17

---

Published as a conference paper at ICLR 2022
Zi (1)) (8)))
projection H, for this & we get that Fi
2i y
and for every l + we get that V/
Fe
This means that P F(44)) = Yi for every E [N].
By Lemma A.4 and Lemma A.5 since each Fy. is used to memorize B samples, then its bit com- plexity is bounded by O B BBlog(BB log(R)) bits, hence this is also the bit complexity of F. The depth of each component Fix O B (og(B) [B) log and there are N such components.
N (Volg(B B)
Hence, the depth of the network F is 0 width of each component, which is O(1).
log( R) The width of F is bounded by the
18


Reviews:
[{"review_id": "woJQ0SBORu5", "reviewer": "Reviewer_sa2e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Overall, I strongly recommend accepting this paper. It improves upon the existing result by Park et al. (2020), where memorization of $N$ points by neural networks with $\\tilde \\Theta(N^{2 / 3})$ parameters was shown. The paper improves the upper bound on the number of parameters required to memorize $N$ points from $\\tilde O(N^{2 / 3})$ to $\\tilde O(N^{1 / 2})$ and closes the gap between the lower bound $\\Omega(N^{1 / 2})$.\n\n2. Another noteworthy strength of this submission is that the paper gives a careful treatment of the bit complexity. Many existing memorization results, even those that require $N$ parameters, assume infinite precision of network parameters. While these results provide valuable insights, they always face criticisms such as \"look, if you assume infinite precision, then you can memorize any dataset in a single real number, because there exists a bijection from $\\mathbb R$ to $\\mathbb R^2$!\" By carefully bounding the number of bits required, this paper constructs a memorizing ReLU network that is not only optimal in the number of parameters but also optimal in the number of bits used in the weights.\n\n3. When counting the number of parameters, the paper does NOT count the zero weights in the network as parameters, rather than \"(# of parameters) = (# of entries in weight matrices and bias vectors).\" This convention of allowing *disconnected edges* in fully-connected networks was also used in the VC-dimension lower bound construction (which involves a similar bit extraction process) in Bartlett et al. (2019). The paper exploits this convention in Theorem 5.1, where they construct $\\frac{N}{L^2}$ parallel subnetworks where each of the subnetworks is constructed using Theorem 3.1. Even though this way of construction results in a width-$O(\\frac{N}{L^2})$ network, the width does not introduce $O(\\frac{N^2}{L^4})$ parameters between each pair of hidden layers, because zero weights are not counted as parameters. While I believe ignoring zero weights is a reasonable thing to do, this allows a lot of additional freedom when constructing memorizers. It is important to note that some existing results (e.g. Park et al. (2020)) do not rely on this counting convention in their constructions.\n\n4. I am a little confused on the bit complexity results presented in Section 6, maybe because I'm not an expert on bit complexity theory. In Theorem 6.1, it is assumed that \"each parameter is represented by $B$ bits,\" but in the proof it is stated that \"each weight of f can be represented by at most $B+2\\log(U)$ bits.\" What is the difference between *representing a parameter* versus *representing a weight*? What do we mean exactly by *representing* something with a certain number of bits? Should the representation of a matrix entry include its index or not? A little more formal definition of these notions should prove helpful.\n\n5. I think the paper will benefit from a little more detailed discussion in the proof intuition section. Allow me to elaborate:\n\n5a. Park et al (2020) also use some bit extraction techniques inspired from Bartlett et al (2019). What is the key insight/trick/technique in this paper that allows a reduction from $N^{2/3}$ to $N^{1/2}$? \n\n5b. More details on depth and bit complexity of parameters would be beneficial. The sketch discusses the bit complexity of $w_j$ and $u_j$'s, but does not say that (unless I missed it) these crafted integers are used as *parameters* in the constructed network; hence, the connection between the bit complexities of these integers and the network parameters are left somewhat unclear.\n\n6. In the discussion of lower bounds, I question if Sontag (1997) really gives a lower bound of $\\Omega(N)$ for *deep* ReLU networks? If I understood correctly, the results in Sontag (1997) on \"piecewise analytic definable\" function class (Corollary 4.1) requires that the partition of the parameter/input space (which is introduced by ReLU hidden nodes) must be determined by analytic definable functions (see Page 6 of Sontag (1997)). For 1-hidden-layer ReLU networks the result can be applied, but I don't think this result applies to ReLU networks of more than 1 hidden layer? In any case, in my view, the key to achieving memorization with $o(N)$ parameter seems to lie on $L$ increasing with $N$, rather than the separation assumption on data points.\n\n7. Can the authors comment on extension to other activations? It seems that the main reason why the paper limits itself to ReLU activation is due to the Telgarsky triangle used in the bit extraction process (Lemma A.7). While I like the elegant use of the Telgarsky triangle in the lemma, I reckon there may be some other ways to extract bits sequentially without having to rely on ReLU and Telgarsky triangle.\n\n8. Minor suggestions: \n- Maybe change Lemma 4.1 to Proposition 4.1, since it is not used as a subroutine for other theorems? Also, maybe consider replacing the exponent $\\epsilon$ with some other character because it is already used in Remark 3.3 as regression accuracy.\n- Proof of Lemma A.4: In the beginning, $F_j : \\mathbb R^2 \\to \\mathbb R^2$\n- Proof of Lemma A.5: Typo in $F_i$, $2^{n\\cdot \\rho}+2$ -> $2^{n\\cdot \\rho+2}$. Also in the sentence \"We use Lemma A.8 with inputs $BIN_{i\\cdot\\rho+1:(i+1)\\cdot\\rho}(u)$ and $x$\", consider switching $BIN_{\\dots}$ and $x$ in the sentence because $BIN_{\\dots}$ is the one that is substituted to $y$.\n- Lemma A.7: This is very minor, but why necessarily $i < j$? It looks to me that $i = j$ can be allowed?\n- Proof of Lemma A.7: $\\psi^{(i)}$ has $2^{i-1}$ bumps of slope $\\pm 2^i$? The triangle $\\psi$ has one bump.\n", "summary_of_the_paper": "This paper studies memorization capacity of deep ReLU networks. For arbitrary $N$ data points in a ball of size $r$ satisfying minimum separation $\\delta$, the authors show that there exists a ReLU network of constant width and depth $\\tilde O(\\sqrt{N})$ that perfectly memorizes the entire dataset (Theorem 3.1). This means that memorizing arbitrary $N$ data points can be done using only $\\tilde O(\\sqrt{N})$ parameters, when depth increases with $N$. Combined with a classical upper bound on VC dimension (Goldberg and Jerrum (1995)), the construction is optimal up to log factors. Theorem 3.1 is extended to the case of fixed depth $L \\leq \\sqrt{N}$ (Theorem 5.1) and fixed bit complexity per parameter (Theorem 6.2), and these additional results are also optimal modulo log factors.", "summary_of_the_review": "I strongly recommend accepting this paper. The paper provides a tight construction that shows the optimal number of parameters in a ReLU network required to memorize arbitrary $N$ data points (comment 1). It also carefully discusses bit complexity and shows that the construction is also optimal in terms of the number of bits required (comment 2). For the rest of the comments (3-8), I raise some minor criticisms/questions/suggestions, but I believe the authors will clarify my concerns.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "vzoVn_63yr_", "reviewer": "Reviewer_P138", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper proves both an upper and lower bound, improving the best known upper bound (Park et al.) and showing that it is optimal up to log factors.\n- The paper is well written and the proof sketches provide sufficient intuition.\n- The discussion on related work is sufficient.\n\nConcerns/Comments:\n- In the first part of the paper (below Theorem 1.1), there is discussion about why it is surprising that shattering a single set of N points is **not** more difficult than memorizing any set of $N$ points. I don't follow this. The reason VC dimension acts as a trivial lower bound on memorization is that in the former, it suffices to just shatter _any_ set of $N$ points while this does not guarantee memorization of all sets of $N$ points even under some assumptions.\n- There appear to be a few minor typos in Section 2. Please take a look.\n- I find the definition of bit complexity of the network to be a little misleading. I would prefer if it were stated as the bit complexity of the weights of the network since one would intuitively expect the bit complexity of the network to be the bit complexity of each weight times the number of weights.\n- In section 4, I think $r=1$ or $\\delta^{-1} \\geq 2(N-1)$. It's just a constant off, so this is a minor comment.\n- In the appendix, it is mentioned that ceil's can be applied in many instances where the $\\log(\\cdot)$ terms may not be integral. Again, a minor comment but it would be useful to mention this in the preliminaries instead.\n- The proofs of the two lower bounds (for general $L$ and $L=\\sqrt{N}$) use different VC dimension bounds (Golbderg et al. and Bartlett et al.). Can you clarify the relationship between this two bounds? Is one tighter than the other in general? It seems to me that the Bartlett bound is tighter if there are no restrictions on $L$. In the discussion below Theorem 5.1, if I plug in $L=N$, then the VC dimension gives us a trivial lower bound of $W = \\tilde{\\Omega}(1)$ which doesn't seem to make sense. Can you clarify?", "summary_of_the_paper": "The paper shows that ReLU networks can memorize $N$ points using $\\tilde{O}(N)$ parameters as long as they are $\\delta-$separated.  They also prove a lower bound on number of parameters and bit complexity showing that this is optimal.", "summary_of_the_review": "Overall, I found the paper to be very well written and an excellent contribution! I recommend that it be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "P2RcnGuNZAK", "reviewer": "Reviewer_FKzU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I do not have much against the acceptance of this paper. The proof is elegant, the result is significant (providing a matching upper bound, asymptotically), and the writing is clear. It seems likely that the used proof techniques are useful for the proof of relevant theoretical results on the expression power of neural networks. In fact, the results look almost directly applicable to prove similar results on non-ReLU network.\n\n- A suggestion is to include some discussions about the \"packing\" of separated input data into a bounded input space. In particular, as this paper gives a big-O style bound which is more meaningful when $N \\to \\infty$ is very large, we should take care of the fact that the separation parameter $\\delta > 0$ of the input signals may actually depend on this $N$---one cannot expect to big $\\delta$ when $N$ is large. To my understanding, this will not alter the dominant asymptotics of the bound, but providing formal discussion on this matter may help clarify the point.\n\n- One thing I would like to point out is that there are some existing arguments surrounding the total-bit-constraints. In particular, section 4.3 of the COLT-accepted version of Park et al. (2021) gives a similar-yet-informal arguments on the required bit precision of each weight and the necessity of $N$-dependent precision.\n\n- A question that I have is whether one can use a similar technique to utilize the \"simplicity of the dataset\" to give a better bound. More specifically, note that the $\\delta$-separation assumption can be viewed as some way of imposing the assumptions on the underlying data distribution, and it seems to be a widely accepted folklore that the simpler datasets can be expressed with a smaller neural network. As is paper already gives some idea on how to utilize the label information for the construction of partitions, with formal bit-precision arguments, I am curious if authors believe that a similar technique can be used to give a result that shows \"under distribution-simplicity assumptions, one requires strictly less than $sqrt(N)$ connections or $N$ bits to memorize the dataset of size $N$.\"\n\n- In terms of the impact, the result may not give a very powerful message toward practitioners, especially because of the (somewhat depressing) bit-level constraints. However, I expect a long-lasting impact on theoretical society; indeed, this result combined with [Malach et al. (2021)](https://arxiv.org/abs/2102.00434) may indeed lead to the characterization of \"memorization threshold,\" which in turn seems to be an informative quantity in the analysis of generalization capabilities.\n\n- Typo: Page 2, line 15: In his case -> In this case. Page 3, second line of Section 2: Treat is as an integer -> Treat it as an integer. Page 5, first line of \"Stage 2\", $(x_N,y_n)$ -> $(x_N,y_N)$. Page 12, second line: to proof Theorem 3.1. -> to prove Theorem 3.1.", "summary_of_the_paper": "The paper shows that, under a mild separability condition, the number of connections in a ReLU network required to memorize N data points is of order $\\sqrt{N}$ (up to logarithmic factors). This result improves upon the recent work of Park et al. (2021), and matches the previous lower bound. One key proof-technical innovation is pairing _both the input and label informations_ for each partition and encoding them at stage 2, whereas the previous approach focused on the input only. Authors also refine the framework to incorporate the bit-precision constraints, based on which Telgarsky's bit extraction technique can be used.", "summary_of_the_review": "The provided results are significant and correct, and the proof technique seems to be useful for other domains of theoretical analyses on neural networks.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the memorization power of Relu Neural networks and obtains sharp bounds in terms of parameters. The writing is very clear and the results very interesting.
Decision: Accept (Spotlight)