Provable Memorization via Deep Neural Networks using Sub-linear Parameters
Authors: Sejun Park
Jaeho Lee
Chulhee Yun
Jinwoo Shin
Venue:  (2021)
Keywords: memorization

Abstract: It is known that $\Theta(N)$ parameters are sufficient for neural networks to memorize arbitrary $N$ input-label pairs. By exploiting depth, we show that $\Theta(N^{2/3})$ parameters suffice to memorize $N$ pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width $3$) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works on the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.

Under review as a conference paper at ICLR 2021
PROVABLE MEMORIZATION VIA DEEP NEURAL NETWORKS USING SUB-LINEAR PARAMETERS
Anonymous authors Paper under double-blind review
ABSTRACT
It is known that O(N) parameters are sufficient for neural networks to memorize arbitrary N input-label pairs. By exploiting depth, show that ( parame- ters suffice to memorize N pairs, under a mild condition on the separation of input points. In particular, deeper networks (even with width 3) are shown to memorize more pairs than shallow networks, which also agrees with the recent line of works the benefits of depth for function approximation. We also provide empirical results that support our theoretical findings.
INTRODUCTION
The modern trend of ovver-araaeterizzinn neural networks has shifted the focus of deep learning theory from analyzing their expressive power toward understanding the generalization capabilities of neural networks. While the celebrated universal approximation theorems state that over- wver-praameterization enables us approximate the target function with a smaller error (Cybenko, 1989; Pinkus, 1999), the theoretical gain is too small to satisfactorily explain the observed benefits of over-paramettrrzing already-big networks. Instead of "how well can models fit," the question of "why models do not overfit" has become the central issue (Zhang et al., 2017).
Ironically, recent breakthrough on the phenomenon known as the double descent (Belkin et al., 2019; Nakkiran et al., 2020) suggests that answering the question of "how well can models fit" is in fact an essential element in fully characterizing their generalization capabilities. In particular, the double descent phenomenon characterizes two different phases according to the capabilityiinaaaaiiity of the network size for memorizing training samples. If the network size is insufficient for memorization, the traditional bias-variance trade-off occurs. However, after the network reaches the capacity that memorizes the dataset, i.c., 'interpolation threshold," larger networks exhibit better generalization. Under this new paradigm, identifying the minimum size of networks for memorizing finite input-label pairs becomes a key issue, rather than function approximation that considers infinite inputs.
The memory capacity of neural networks is relatively old literature, where researchers have studied the minimum number of parameters for memorizing arbitrary N input-label pairs. Existing results showed that O(N) parameters are sufficient for various activation functions (Baum, 1988; Huang and Babri, 1998; Huang, 2003; Yun et al., 2019; Vershynin, 2020). On the other hand, Sontag (1997) established the negative result that for any network using analytic definable activation functions with o(N) parameters, there exists a set of N input-label pairs that the network cannot memorize. The sub-linear number of parameters also appear in a related topic, namely the VC-dimension of neural networks. It has been proved that there exists a set of N inputs such that a neural network with o(N) parameters can "shatter," i.e., memorize arbitrary labels (Maass, 1997; Bartlett al., 2019). Comparing the two results on o(N) parameters, Sontag (1997) showed that not all sets of N inputs can be memorized for arbitrary labels, whereas Bartlett et al. (2019) showed that al least one set of N inputs can be shattered. This suggests that there may be reasonably large family of N input-label pairs that can be memorized with o(N) parameters, which is our main interest.
1.1 SUMMARY OF RESULTS
In this paper, we identify mild condition satisfied by many practical datasets, and show that ((N parameters suffice for memorizing such datasets. In order to bypass the negative result by Sontag (1997), introduce condition the set of inputs, called the A A-separateness.

---

Under review as a conference paper at ICLR 2021
Definition 1. For set X' C R we say X is A separated if
sup x
|| x' 1|2 < A
inf 2,. Exaatta
1|:0 x' 1/112-
This condition requires that the ratio of the maximum distance to the minimum distance between distinct points is bounded by A. Note that the condition is milder when A is bigger. By Definition I, any given finite set of (distinct) inputs is A-separated for some A, so one might ask why A- separateness is different from having distinct inputs in a dataset. The key difference is that even the number of data points N grows, the ratio of the maximum to the minimum should remain bounded by A. Given the discrete nature of computers, there are many practical datasets that satisfy A --epaaateness, as we will see shortly. Also, this condition is more general than the minimum distance assumptions (Vi, ||اح||2 theoretical results (Hardt and Ma, 2017; Vershynin, 2020). To see this, note that the minimum distance assumption implies 2/ psseparaateness. In our theorem statements, we will use the phrase A -epearrtt set of input-label pairs" for denoting the set of inputs is A A-separated.
1. Vi & j. ||,; x,112 2 p > 0) that are employed in existing
In our main theorem sketched below, prove the sufficiency of o(N) parameters for memorizing any A-separated set of N pairs (i.e., any A-separated set of N inputs with arbitrary labels) even for large A. More concretely, our result is of the following form:
Theorem 1 (Informal). For any w E (3. 1). there exists a O / /log N log Alyyyyer, O(N" log A) A fully-connected nefwork with sigmoidal RELU activation that can memorize any A-separated set of N input-label pairs.
We note that log has base 2. Theorem 1 states that if the number of layers increases with the number of pairs N, then any A-separated set of N pairs can be memorized by network with o(N) parameters. Here, we can check from Definition that the log A term does not usually dominate the depth the number of parameters, especially for modern deep architectures and practical datasets. For example, it is easy to check that any dataset consisting of 3-channel images (values from (0. 255)) of size a x b satisfies log A < (9 + 2 log(ab) (ab) (e.g., log A < 17 for the ImageNet dataset), which is often much smaller than the depth of modern deep architectures.
For practical datasets, we can show that networks with parameters fewer than the number of pairs can successfully memorize the dataset. For example, in order to perfectly classify one million images in ImageNet dataset' with 1000 classes, our result shows that 0.7 million parameters are sufficient. The improvement is more significant for large datasets. To memorize 15.8 million bounding boxes in Open Images V62 with 600 classes, our result shows that only 4.5 million parameters suffice.
Theorem improves the sufficient number of parameters for memorizing a large class of N pairs (i.e., 20(N") -sparrtted) from ONN down to ONN)) for any w (3. 1), for deep networks. Then, it is natural to ask whether the depth increasing with N is necessary for memorization with a sub-liness number of parameters. The following existing result on the VC-dimension implies that this is indeed necessary for memorization with o/N/ log N) parameters, at least for RELU networks.
Theorem [Bartlett et al. (2019)]. (Informal) For L-layer RELU networks, ([ log N)) parame- ters are necessary for memorizing at least a single set of N inputs with arbitrary labels.
The above theorem implies that for RELU networks of constant depth, (NNN log N) parameters are necessary for memorizing at least one set of N inputs with arbitrary labels. In contrast, by increasing depth with N, Theorem shows that there is a large class of datasets that can be memorized with o(N/ log N) parameters. Combining these two results, one can conclude that increasing depth is necessary and sufficient for memorizing a large class of N pairs with o log N) parameters.
Given that the depth is critical for the memorization power, is the width also critical? We prove that it is not the case, via the following theorem.
Theorem 2 (Informal). For a fully-connected network of width 3 with sigmoidal or RELU activa- tion function, O(N2/3 + log A) parameters (i.e., layers) suffice for memorizing any A-separated set of N input-label pairs.
Theorem states that under 20(N"/3) -separtteness of inputs, the network width does not necessarily have to increase with N for memorization with sub- aub-linear parameters. Furthermore, it shows that
20(NN"")
hhtp://wwwwimmgeennttrrr//
2

---

Under review as a conference paper at ICLR 2021
even a surprisingly narrow network of width 3 has superior memorization power than fixed-depth network, requiring only O(N2/3) parameters.
Theorems and 2 show the existence of network architectures that memorize N points with o ((N) parameters, under the condition of Á A-separateness. This means that these theorems do not answer the question of how many such data points can a given network memorize. We provide generic criteria for identifying the maximum number of points given general networks (Theorem 3). In nutshell, our criteria indicate that to memorize more pairs under the same budget for the number of parameters, network must have deep and narrow architecture at the final layers of the network. In contrast to the prior results that the number of arbitrary pairs that can be memorized is at most proportional the number of parameters (Yamasaki, 1993; Yun al., 2019; Vershynin, 2020), our criteria successfully incorporate with the characteristics of datasets, the number of parameters, and the architecture, which enable to memorize A -separrtedd datasets with number of pairs super-linear in the number of parameters,
Finally, we provide empirical results corroborating our theoretical findings that deep networks often memorize better than their shallow counterparts with a similar number of parameters. Here, we emphasize that better memorization power does not necessarily imply better generalization. We indeed observe that shallow and wide networks often generalize better than deep and narrow networks, given the same (or similar) training accuracy.
Organization. We first introduce related works in Section 2. In Section 3, we introduce necessary notation and the problem setup. We formally state our main results and discuss them in Section 4. In Section 6, we provide empirical observations on the effect of depth and width in neural networks. Finally, we conclude the paper in Section 7.
2 RELATED WORKS
2.1 NUMBER OF PARAMETERS FOR MEMORIZATION
Sufficient number of parameters for memorization. Identifying the sufficient number of pa- rameters for memorizing arbitrary N pairs has long history. Earlier works mostly focused on bounding the number of hidden neurons of shallow networks for memorization. Baum (1988) proved that for 2-layer STEP* networks, O(N) hidden neurons (i.e., O(N) parameters) are sufficient for memorizing arbitrary N pairs when inputs are in general position. Huang and Babri ( (1998) showed that the same bound holds for any bounded and nonlinear activation function satisfying that either limg---oo (xx) or lim (x) exists, without any condition on inputs. The O(N) bounds on the number of hidden neurons was improved to O(vN) by exploiting an additional hidden layer by Huang (2003); nevertheless, this construction still requires O(N) parameters.
With the advent of deep learning, the study has been extended to modern activation functions and deeper architectures. Zhang et al. (2017) proved that O(N) hidden neurons are sufficient for 2-layer RELU networks to memorize arbitrary N pairs. Yun et al. (2019) showed that for deep RELU (or hard tanh) networks having at least 3 layers, ( parameters are sufficient. Vershynin (2020) proved similar result for STEP (or RELU) networks with an additional logarithmic factor, i.e., O(N) parameters are sufficient, for memorizing arbitrary (x, ||ai||2 = 1) satisfying ||,; - 1 2 log log dmaxx and N, d,aax = e oid where dmax and dmin denote the maximum log dmii
and the minimum hidden dimensions, respectively.
In addition, the memorization power of modern network architectures has also been studied. Hardt and Ma (2017) showed that RELU networks consisting of residual blocks with O(N) hidden neurons can memorize arbitrary {z; : ||=,||| 1 satisfying I|æ; - x2ylı 2 p for some absolute constant 0. Nguyen and Hein (2018) studied broader class of layers and proved that O(N) hidden neurons suffice for convolutional neural networks consisting of fully-connected, convolutional, and max-pooling layers for memorizing arbitrary N pairs having different patches.
Necessary number of parameters for memorization. On the other hand, the necessary number of parameters for memorization has also been studied. Sontag (1997) showed that for any neural network using analytic definable activation functions. I(N) parameters are necessary for memorizing arbitrary
SSTE denotes the hinary threshold activation function: 1 [x 2 0).
3

---

Under review as a conference paper at ICLR 2021
N pairs. Namely, given any network using analytic definable activation with o(N) parameters, there exists a set of N pairs that the network cannot memorize.
The Vapnik- Chenik-Chervosnnii (VC) dimension is also closely related to the memorization power of neural networks. While the memorization power studies the number of parameters for memorizing arbitrary N pairs, the VC-dimension studies the number of parameters for memorizing at least single set of N inputs with arbitrary labels. Hence, naturally provides the lower bound on the necessary number of parameters for memorizing arbitrary N pairs. The VC-dimension of neural networks has been studied for various types of activation functions. For memorizing at least a single set of N inputs with arbitrary labels, it is known that ( log N) parameters are necessary (Baum and Haussler, 1989) and sufficient (Maass, 1997) for STEP networks. Similarly, Karpinski and Macintyre (1997) proved that 2 ((VN/U) parameters are necessary for sigmoid networks of U neurons. Recently, Bartlett et al. (2019) showed that ((N/(L log N)) parameters are necessary and sufficient for L-layer networks using any piecewise linear activation function where T. == WE ΣE= of parameters up to the l-th layer.
Wt and W2 denotes the numher
2.2 BENEFITS OF DEPTH IN NEURAL NETWORKS
To understand deep learning, researchers have investigated the advantages of deep neural networks compared to shallow neural networks with a similar number of parameters. Initial results discovered examples of deep neural networks that cannot be approximated by shallow neural networks without using exponentially many parameters (Telgarsky, 2016; Eldan and Shamir, 2016; Arora et al., 2018) Recently, it is discovered that deep neural networks require fewer parameters than shallow neural networks to represent or approximate class of periodic functions (Chatziafratis et al., 2020a;b). For approximating continuous functions, Yarotsky (2018) proved that the number of required parameters for RELU networks of constantly bounded depth are square to that for deep RELU networks.
3 NOTATION AND PROBLEM SETUP
In this section, we introduce notation and the problem setup. We use log to denote the logarithm to the base 2. We let RELU be the function x + max 0}. For X' C R, we denote [X] : {[3]
X). For N and a set X, denote (*) (S X |S| n and [n]] == {0, .......... n 1}.
For 2 O and > O, we denote x: mod == y
Throughout this paper, we consider fully-connected feedforward networks. In particular, we consider the following setup: Given an activation function o, we define neural network So of layers (or cquivalently L 1 hidden layers), imput dimension dz, output dimension 1, and hidden layer dimensions di,.... .,, d parameterized by as fa := 1 .ot porot- Here, te Rd + Rdet is an affine transformation parameterized by 0.4 We denote a neural network using an activation function a by a "a network." We define the width of fo as max(d1....,dL-1).
As we introduced in Section 1.1, our main results hold for any sigmoidal activation function and RELU. Here, we formally define the sigmoidal functions as follows.
Definition 2. We say a function o R > R is sigmoidal if the following conditions are satisfied.
Both lim a (xt), limz (xx exist and lim,->-o axx) & lim, (xx).
-Theee exists E R such that a is continuously differentiable at z and d'(z) + 0.
class of sigmoidal functions covers many activation functions including sigmoid, tanh, hard tanh, etc. Furthermore, since hard tanh can be represented as a combination of two RELU functions, all results for sigmoidal activation functions hold for RELU as well."
Lastly, we formally define the memorization as follows.
Definition 3. Given C, dg E N. a set of inputs X' C. Rd,,, label function y X + [C]. and a neural network So dh + R parameterized by 0, we say fo can memorize ((x, y(x)) x E X) in dz dimension with C classes if for any e >> 0, there exists 0 such that (fo(x) b(z) for all E X.
WWe set do de and dr. :=
hard tanh activation function: x + -1x < -1| + 1 < <
hard tanh(x) RELU((= + 1) RFI.U(z 1) - RELU RELU(1 (1-())))) x))
4

---

Under review as a conference paper at ICLR 2021
Definition 3 defines the memorizability the ability of network fe to fit set of input-label pairs. While existing results often define memorization only for the binary labels, we consider arbitrary C classes, and prove results for general multi-class classification problems. We often write "fo can memorize arbitrary N pairs" without "in dz dimension with C' classes" throughout the paper.
4
MAIN RESULTS
4.1
MEMORIZATION VIA SUB-LINEAR PARAMETERS
Efficacy of depth for memorization. Now, we ready to introduce our main theorem memo- rizing N pairs with (NN) parameters. The proof of Theorem is presented in Section 5.
Theorem 1. For any C, N, du E N. for any w E [2/3, for any A Z L, for any sigmoidal activation function o, there exists network so of O (log d, + log A + 1+(1.ww 1yggg log C*) hidden layers
N2-2"
and Ofd + log A + N + +N log C') parameters such that fe can memorize any A separated set of N pairs d₂ dimension with C classes.
Note that Theorem covers w 2/3 which is not included in its informal version presented in Section 1.1. However, could only achieve O(N2/3) parameters disappears. In addition, while we only address sigmoidal activation functions in the statement of Theorem 1, note that the same conclusion naturally holds for RELU as described in Section 3.
2/3 the log N term
In Theorem 1, A only incurs Ologg A) overhead to the number of layers and the number of parameters. As we introduced in Section 1.1, log Á for modern datasets is often very small. Furthermore, log A is small for random inputs. For example, a set of dy-dimensional i.i.d. standard normal random vectors of size N satisfies log A 0 d log( (N) with probability at least 1 5 (see Section C). Hence, the A-separateness condition is often negligible.
Suppose that de and C are treated as constants, as also assumed in existing results. Then, Theorem I implies that if log A = () for some w < 1, then (NN") (i.e., sub-linear to N) parameters are sufficient for sigmoidal or RELU networks to memorize arbitrary A-separated
of N pairs. Furthermore, if log A < O(N2-2" /log N) and w E (2. 1), then the network construction in Theorem 1 has O(N 2222-2 /log N)) layers and O(N#) parameters. Note that the condition log A < O(N2-2 /log N) very loose for many practical datasets, especially for those with huge N. Combined with the lower bound Q log N) on the necessary number of parameters for RELU networks of constant depth (Bartlett et al., 2019), Theorem implies that depth growing in N is necessary and sufficient for memorizing large class (i.e., A A-separated) of N pairs with o(N/ log N) parameters. In other words, deeper RELU networks have more memorization power.
(
Unimportance of width for memorization. While depth is critical for the memorization power, we show that the width is not very critical. In particular, we prove that extremely narrow networks of width 3 can memorize with O(N2/3) layers (i.e., O(N2/3) parameters) stated in the following theorem. The proof of Theorem 2 is presented in Section F.
Theorem 2. For any C, N, dz E N, for any A 2 1, for any sigmoidal activation function a, network of (N log C.) hidden layers and width 3 can memorize any A-separated set of N pairs in dy dimension with C classes.
The statement of Theorem 2 might be somewhat surprising since the network width for memorization does not depend to the input dimension dz This is in contrast with the recent universal approximation results that width at least d₂ + is necessary for approximating functions having d, di-dimmnsional domain (Lu al., 2017: Hanin and Sellke, 2017: Johnson, 2019; Park et al., 2020). The main differ- ence follows from the fundamental difference in the two approximation problems, i.c., approximating a function finite inputs versus infinite inputs, e.g., the unit cube. Any set of N input vectors can be easily mapped to N "distinct" scalar values by simple projection using inner product. Hence, memorizing finite lnput-label pairs in d,-dimension can be easily translated into memorizing finite input-label pairs in one-dimension. In other words, the dimensionality (dzz) of inputs is not very important as long as they can be translated to distinct scalar values. In contrast, there no "natural" way to map design an injection from d, dimdinnnsional unit cube to lower dimension. Namely, to not loose the "information" from inputs, width d, for preserving inputs is necessary. Therefore, function approximation in general cannot be done with width independent of dz.
5

---

Under review as a conference paper at ICLR 2021
Extension to regression problem. The results of Theorem 1 and Theorem 2 can be easily applied to the regression problem, i.e, when labels are from [0, 1]. This is because one can simply translate the regression problem with some > 0 error tolerance to the classification problem with [1/=] classes. Here, each class c E {0, 1.... [1/1]} regression problem can also be solved within E error with o(N) parameters, where the sufficient number of layers and the sufficient number of parameters are identical to the numbers in Theorem and Theorem 2 with the replacement of log C' with (og()/)).
corresponds to the target value e 6. Hence, the
Relation with benefits of depth in neural networks. Our observation that deeper REL.U networks have more memorization power is closely related to the recent studies the benefits of depth in neural networks (Telgarsky, 2016; Eldan and Shamir, 2016; Lin et al., 2017; Arora et al., 2018; Yarotsky, 2018; Chatziafratis al., 2020a;b). While observation indicates that depth is critical for the memorization power, these works mostly focused on showing the importance of depth for approximating functions. Here, the existing results benefits of depth for function approximation cannot directly imply the benefits of depth for memorization since they often focus on specific classes of functions or require parameters far beyond O(N).
4.2 GENERIC CRITERIA FOR IDENTIFYING MEMORIZATION POWER
While Theorem proves the existence of networks having o(N) parameters for memorization, the following theorem states the generic criteria for verifying the memorization power of network architectures. The proof of Theorem 3 is presented in Section G.
Theorem 3. For some sigmoidal activation function o, let fo be a a network of L hidden layers
having de neurons the L-th hidden layer. Then, for any C.N, E N and A 2 1, fo can memorize any A separated set of N pairs in dy dimension with C classes if the following statement holds:
There exist 0 < L1 <
LK- < for some S K S log N satisfying conditions 1-4 below.
1. de 2 for all 8 S Lx and de 2 7 for all Lx < f.
2. II h L(de + 1)/2] 2 2V2
3. Etar+1 (de 2) 2 2++ for all 1 <is K-1 1.
bi
4. 2k. (Etatr--tldd (de (de |L- LL - 1)/ log CT| 4 142N2 N
Our criteria in Theorem 3 require that the layers of the network can be "partitioned" into have K + 1 distinct parts characterized by ,1,...,, Lx for some K 2. Under this partition, we describe the four conditions in Theorem 3 in detail. The first condition suggests that the network width is not very critical. We note that de 2 for LK network architecture to fit in width 3 for Theorem 2. while we provide generic criteria here.
does not contradict Theorem 2 as we highly optimize the
The second condition considers the first L1 hidden layers. In order to satisfy this condition, deep and narrow architectures are better than shallow and wide architectures under similar budget for parameters, due the product form I T. [(de + 1)/2j. Nevertheless, the architecture of the first L1 hidden layers is not very critical only log A + 1 log( (g((2dd.)) layers sufficient even with width 3 (e.g., log A < 17 for the ImageNet dataset).
The third condition is closely related to the last condition: As K increases, the LHS in the last condition increases. However, the third condition states that it requires more hidden neurons. Simply, increasing K by requires doubling hidden neurons from the (L, + 1)-th hidden layer to the LK-1-th hidden layer. Nevertheless, this doubling hidden neurons would make the LHSS of the last condition double well.
The last condition is simple. As we explained, 2 is approximately proportional to the number of hidden neurons from the (Li + 1)-th hidden layer to the 1-th hidden layer. The second term in the LHS of the last condition Σ/*x 1+1(de (de- - 2) is even more simple; it only requires counting hidden neurons. On the other hand, the last term counts the number of layers. This indicates that to satisfy conditions in Theorem using few parameters, the last layers of the network should be deep and narrow. In particular, we note that such a deep and narrow architecture in the last layers is indeed necessary for REL. networks memorize with o(N) parameters (Bartlett al., 2019).

---

Under review as a conference paper at ICLR 2021
Now, describe how to show memorization with (NN) parameters using our criteria. For simplicity, consider the network with the minimum width stated in the first condition, i.., de = 3 for all & & LK and de = 7 for all Lx < f. As explained, the second conditions can be easily satisfied. For the third condition, consider choosing K log(N2/33 then ((N2/3) hidden neurons (i.e., ((V2/3) hidden layers) would be sufficient, i.e., LK-1 Li ((N2/5). Likewise, we choose remaining I to satisfy T-K- ---- 1 (N22/3) and I, - Lx= = ((N2/5). Then, it naturally satisfy the last condition while using only @(N2/3) parameters.
5 PROOF OF THEOREM 1
In this section, we give a constructive proof of Theorem 1: memorize N inputs in dN dimension with C' classes using only o(N) parameters. We note that the proofs of Theorem and Theorem also utilize similar constructions. To construct networks, we first introduce the following lemma, motivated by the RELU networks achieving nearly tight VC-dimension (Bartlett et al., 2019). The proof of Lemma is presented in Section E.I.
We design a network which can
Lemma 4. For any C, V E N and p E [1/2, 1}, there exists a a network Se of O Vl
hidden layers and O(VP + V1/2 log C)) parameters such that fo can memorize any X E (x) with C classes satisfying
[ = [V].
Roughly speaking, Lemma 4 states the following: Suppose that the V inputs are scalar and well- separated, in the sense that exactly one input falls into each interval [i, + 1). Then, such well- separated inputs can be mapped to the corresponding labels using only O(V2/2) parameters (with p 1/2). Thus, what remains is to build network mapping N arbitrary inputs to some well- separated set bounded by some V = o(N2), again using (N) parameters.
Projecting imput vectors to scalar values. Now, we introduce our network mapping A A-separated set of N inputs to some Z satisfying |z] E ((W). First, we map the input vectors to scalar values using the following lemma. The proof of Lemma 5 is presented in Section E.2.
Lemma 5. For any A A-separated X' E (*x) there exist v E RRd=, b E IR such that [(u x bbob x} (O(N*Ad)/))) N
Lemma 5 states that any A-separated N vectors can be mapped some well-separated scalar values bounded by O(N [d using a simple projection using (d2z) parameters. Note that the direct combination of Lemma 4 and Lemma 5 gives us network of O ((22 ///////) parameters which can memorize any A-separated N pairs. However, this combination is limited in at least two sense: The required number of parameters (1) has A d/22 multiplicative factor and (2) is not sub-linees to N. In what follows, we introduce our techniques for resolving these two issucs.
Reducing upper bound to O(N2). First, we introduce the following lemma for improving the A 11/2 1/4 multiplicative factor in the number of parameters to O(log A + dz) additional parame- ters. The proof of Lemma is presented in Section E.3.
Lemma 6. For any X E (xr such that |X]] E ([K)) for some K E N. there exists a a network f of
hidden layer and width 3 such that [](x)] E (1) where T : max { [[K/2], [N3/4+1]].
From Lemma 6, a network of O(log A + log dz)) hidden layers and width 3 can decrease the upper bound (N !/ to [N2/4+ which enables us drop the dependence of Ad!/2 on the upper bound using Ologg A + log dxz) parameters. The intuition behind Lemma 6 is that if the number of target intervals T is large enough compared to the number of inputs N, then inputs can be easily mapped without collision (i.e., two inputs are mapped into the same interval) by some simple network of a small number of parameters. For example, we construct ff in Lemma as
x I mod T if
i 0.
f(x)
[T
for some b E [T]. However, if T is not large enough compared to N (i.e., T < [N3/4+ 1]), then network (1) cannot avoid the collision between inputs, i.e., [T] satisfying [(xx)) E (W)
7

---

Under review as a conference paper at ICLR 2021
98
96
Accuracy
Accuracy
92
89
Train Test
Train
83
90
Test
25x3 22x4
20x5
29x2 25x3 22x4 20x5 19x6
#channels #blocks
#channels 4blocks
(a) CIFAR-10
(b) SVHN
Figure Depth-width trade-off under similar number of parameters.
may not exist. Hence, combining Lemmas 4-6 only gives us a a network O(N + log A log du) parameters which can memorize any A separated N pairs, i.e., the number of parameters is not sub-linear to N.
Reducing upper bound to of 2 To resolve this issue, we further decrease the upper bound using the following lemma. The proof of Lemma is presented in Section E.4.
Lemma 7. For any X (x) such that [X] E ((x) for some K N, there exists a a network f of hidden layer and width ( such that Lf(x)) E ((W) where T == max { [K/2), NV..
The network in Lemma
reduce the upper bound by approximately half, beyond [N2 /4 1J; however, the required number of parameters will be doubled if both the current upper bound K decreases by half. Hence, in order decrease the upper bound from O(N to V (2 using (log( N2 /V)) applications of Lemma 7, we need (log( N2 N2/V)) layers and O /V) parameters. Here, we construct each application of Lemma using two hidden layers: one hidden layer of 2 K) hidden neurons for implementing the function and the other hidden layer of one hidden neuron for the output.
[ Deriving Theorem Now, we choose V ((N==w for some w E [3. 1]. Then, from Lemmas
5-7, Ollo de + log A + log N) hidden layers and O(d log A + N parameters suffice for mapping any A-separated of size N
Z satisfying [Z] (%) Finally, from Lemma 4 and N2
choosing p 2-16 additional ( 1+:11.5m T) Ing log C') hidden layers and O(N +M1-w// log C*)
parameters suffice for mapping 2 to its labels. This completes the proof of Theorem 1.
EXPERIMENTS
In this section, we study the effect of depth and width. In particular, we empirically verify whether our theoretical finding extends to practices: Can deep and narrow networks memorize more training pairs than their shallow and wide counterparts under similar number of parameters? For the experiments, we use residual networks (He al., 2016) having the same number of channels for each layer. The detailed experimental setups are presented in Section A. In the following experiments, we observe the training and test accuracy of networks by varying the number channels (c) and the number of residual blocks (b).
6.1 DEPTH-WHL WIDTH TRADE-OFF IN MEMORIZATION
We verify the memorization power of different network architectures having a similar number of parameters. Figure illustrates training and test accuracy of five different architectures with approximately 50000 parameters classifying the CIFAR-10 dataset (Krizhevsky and Hinton, 2009) and the SVHN dataset (Netzer et al., 2011). One can observe that as the network architecture becomes deeper and narrower, the training accuracy increases. Namely, deep and narrow networks memorize better than shallow and wide networks under similar number of parameters. This observation agrees with Theorem 1, which states that increasing depth reduces the required number of parameters for memorizing the same number of pairs
However, more memorization power does not always imply better generalization. Figure 1b, the depth increases, the test accuracy also increases for the SVHN dataset. In contrast, the test.
8

---

Under review as a conference paper at ICLR 2021
Training accuracy
Test accuracy
67.5
00.9
89.3
95.7
96.7
99.6
69.2
70.4
81.6
01.3
06.3
10
71.8
86.0
95.8
99.4
99.9
100.0
10
72.0
80.0
82.6
84.1
86.3
87.1
100.0
86.5
20
15.7
92.2
99.2
100.0
100.0
100.0
90
20
24.1
80.4
63.5
85.3
87.3
87.1
90
25
100.0
25
80.5
87.0
78.6
95.3
98.5
100.0
100.0
100.0
75.1
80.5
83.2
85.7
86.8
87.9
35
78.3
95.5
99.7
99.9
100.0
100.0
78
35
75.
80.3
84.6
87.6
07.5
99.4
100.0
97.1
45
78.9
96.9
96.8
96.9
100.0
100.0
72
45
75.1
81.0
84.0
85.3
86.5
87.1
72
5
Figure 2: Training and test accuracy by varying width and depth for the CIFAR-10 dataset. The r-axis denotes the number of channels and the y-axis denotes the number of residual blocks.
accuracy decreases for the CIFAR-I0 dataset as the depth increases in Figure la. In other words, overfitting occurs for the CIFAR- 10 dataset while classifying the SVHN data receive benefits from more expressive power. Note that a similar observation has also been made in the recent double descent phenomenon (Belkin al., 2019; Nakkiran al., 2020) that more expressive power both hurt/improve the generalization.
In addition, this observation can provide guidance on the design of network architectures in ap- plications where the training accuracy and small number of parameters are critical. For example, recent development in video streaming services tries to reduce the traffic by compressing video by neural networks and send the compressed video and the decoder network (Yco et al., 2018 ()... Here, the corresponding decoder is often trained only for the video send; hence, only the training accuracy/loss matters while the decoder's number of parameters should also be small for the traffic.
6.2 EFFECT OF WIDTH AND DEPTH
In this section, observe the effect depth and width by varying both. Figure 2 reports the training and test accuracy for the CIFAR-10 10 dataset by varying the number for channels from 5 to 30 and the number of residual blocks from 5 to 50. We present the same experimental results for the SVHN dataset in Section B. First, we observe that a network of 15 channels with feature map size 32 x 32 successfully memorize (i.e., over 99% training accuracy). This size much narrower than modern network architectures, c.g., ResNet-18 18 has 64 channels at the first hidden layer (He al., 2016). On the other hand, too narrow network (c.g., 5-channels) fail to memorize. This result does not contradict with Theorem 2 as the test of memorization in experiments/prann descent. We note that similar phenomenons are observed for the SVHN dataset.
involves the stochastic gradient
Furthermore, the network memorize, observe that increasing width is more effective than increasing depth for improving test accuracy. These results indicate that width is not very critical for the memorization power, while it can be effective for generalization. Note that similar observations have been made in Zhang et al. (2017).
7 CONCLUSION
In this paper, we prove that ((N2/3) parameters are sufficient for memorizing arbitrary innuut-label labell pairs under the mild A-separateness condition. Our result provides significantly improved results, compared to the prior results showing the sufficiency of ((N) parameters with/without conditions on pairs. In addition, Theorem shows that deeper networks have more memorization power. This result coincides with the recent study on the benefits of depth for function approximation. On the other hand, Theorem 2 shows that network width is not important for the memorization power. We also provide generic criteria for identifying the memorization power networks. Finally, we empirically confirm theoretical results.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Representations, 2018.
Peter L. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 2019.
Eric B. Baum. On the Capabilities of Multilayer Perceptrons. Journal of Complexity, 4(3):193-215, 1988. ISSN 0885-064X
Eric B. Baum and David Haussler. What size gives valid generalization? In Advances in Neural Information Processing Systems, 1989.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-leamnin practice and the classical varinner trade-off. Proceedings of the National Acudemy of Sciences, 116632):15849-1533 2019.
Vaggos Chatziafratis, Sai Ganesh Nagarajan, and Ioannis Panageas. Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systems. In International Conference on Machine Learning, 2020a.
Vaggos Chatziafratis, Sai Ganesh Nagarajan, Ioannis Panageas, and Xiao Wang. Depth-width trade-offss for relu networks via sharkovsky's theorem. In International Conference on Learning Representations, 2020b.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-314, 1989.
Ronen Eldan and Ohad Shamir. The power depth for feedforward neural networks. In Conference Learning Theory, 2016.
Walter Gautschi. Some elementary inequalities relating the gamma and incomplete gamma function. Journal of Mathematics and Physics, 38(1-4):77-81 1959.
Boris Hanin and Mark Sellke. Approximating continuous functions by ReLU nets of minimal width. arXiv preprint
2017.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In International Conference on Learning Representations, 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, 2016.
Guang-Bi Bin Huang. Learning capability and storage capacity of swo-hidden-layer feedforward networks. IEEE Transactions on Neural Networks, 14(2):274-25 28,, 2003.
Guang-Bi Bin Huang and Haroon A Babri. Upper bounds on the number of hidden neurons in feed- forward networks with arbitrary bounded nonlinear activation functions. IEEE Transactions on Neural Networks, 9(1):224-22) 229, 1998.
Jesse Johnson. Deep, skinny neural networks are not universal approximators. International Conference on Learning Representations, 2019.
Marek Karpinski and Angus Macintyre. Polynomial bounds for dimension of sigmoidal and general pfaffian neural networks. Journal of Computer and System Sciences, 54(1):169-176, 1997.
Patrick Kidger and Terry Lyons. Universal approximation with deep narrow networks. In Conference on Learning Theory, 2020.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
10

---

Under review as a conference paper at ICLR 2021
Henry W Lin, Max Tegmark, and David Rolnick. Why does deep and cheap learning work well? Journal of Statistical Physics, 168(6):123-1247, 2017.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In Advances in Neural Information Processing Systems, 2017.
Wolfgang Maass. Bounds for the computational power and learning complexity of analog neural nets. SIAM Journal on Computing, 26(3):708-77) -322, 1997.
Prectum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and llya Sutskever. Deep Double Descent: Where Bigger Models and More Data Hurt. In International Conference Learning Representations, 2020.
Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. In NeurIPS Deep Learning and Unsupervised Feature Learning Workshop, 2011.
Quynh Nguyen and Matthias Hein. Optimization Landscape and Expressivity of Deep CNNs. In International Conference on Machine Learning, 2018.
Sejun Park, Chulhee Yun, Jacho Lee, and Jinwoo Shin. Minimum Width for Universal Approximation. arXiv preprint arXiv:2006.08859, 2020.
Allan Pinkus. Approximation theory of the MLP model in neural networks. Acta Numerica, 143-195, 1999.
Eduardo D. Sontag. Shattering all sets of k points in "general position" requires 1k-1)/2 parameters. Neural Computation, 9(2):337-348, 1997.
Matus Telgarsky. Benefits of depth neural networks. Conference on Learning Theory, 2016.
Roman Vershynin. Memory capacity of neural networks with threshold and ReLU activations. arXiv preprint 2001.06938, 2020.
Masami Yamasaki. The lower bound of the capacity for neural network with multiple hidden layers. In International Conference on Artificial Neural Networks, 1993.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on Learning Theory, 2018
Hyunho Yeo, Youngmok Jung, Jaehong Kim, Jinwoo Shin, and Dongsu Han. Neural Adaptive Content-aware Internet Video Delivery. In USENIX Symposium Operating Systems Design and Implementation, 2018.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity. Advances in Neural Information Processing Systems, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference Learning Representations, 2017.

---

Under review as a conference paper at ICLR 2021
A EXPERIMENTAL SETUP
In this section, we described the details on residual network architectures and hyper-parameter setups.
We use the residual networks of the following structure. First, convolutional layer and RELU maps a 3-channel input image to e-channel feature map. Here, the size of the feature map is identical to the size of input images. Then, we apply b residual blocks where each residual block maps + RELU RELU CoNv(z) + x) while preserving the number of channels and the size of feature map. Finally, we apply an average pooling layer and fully-connected layer. We train the model for 5 x 10 iterations with batch size 64 by the stochastic gradient descent. We use the initial learning rate 0.1, weight decay 10-4, and the learning rate decay at the 1.5 10% -th iteration and the 3.5 x 10 iteration by a multiplicative factor 0.1.
All presented results are averaged over three independent trials.
12

---

Under review as a conference paper at ICLR 2021
B
TRAINING AND TEST ACCURACY FOR SVHN DATASET
Training accurecy
Test acturacy
90
99
88.3
94.0
96.5
96.4
99.5
99.3
10
88.3
92.3
92.8
92.6
92.7
92.9
15
85.8
99.5
96
15
92.6
92-9
96
96.2
96.3
25
91.8
97.0
96.8
98.9
99.9
100.0
25
91.1
92.8
52.7
98.2
92.4
93.3
35
92 9
97.3
99.3
99.3
100.0
100.0
35
91.5
92.7
93.1
93.1
94.1
96.0
40
98.5
03.8
97.0
99.0
99.8
99.5
100.0
92.9
92.9
03.6
98.4
98.2
93.6
30
96.2
97.0
99.2
99.5
99.8
100.0
30
92.3
92.8
93.1
93.5
93.8
10
20
25
10
25
Figure 3: Training and test accuracy by varying width and depth for the SVHN dataset. The rr-axis denotes the number of channels and the y-axis denotes the number of residual blocks.
13

---

Under review as a conference paper at ICLR 2021
C A A-SEPARATENESS OF GAUSSIAN RANDOM VECTORS
While we mentioned Section 1.1 that digital nature of data enables the A-separateness of inputs with small A, random inputs are also A-separated with small A with high probability, In particular, we prove the following lemma.
Lemma 8. For any dæ E N, consider a set of N vectors X == (xi...,, .NN C IR where each entry of is drawn from the i.idd standard normal distribution. Then, for any 8 X is (IN/V5522/ /
5e de
In(N/V5) -separated with probability at least 1 - 5.
Lemma 8 implies that Theorem and Theorem 2 can be successfully applied to random Gaussian input vectors the O (N/ / separateness condition in Lemma 8 is much weaker than our 201N2/8) -separateness condition for memorization with o(N) parameters.
Proof of Lemma 8. To begin with, we first prove that for + j. the following bound holds:
2
N
2/d
1
10
N
P
1
S
6
+
In
vdz
d
v6
2
N
4/4
10 In
N
P
$
12 - x,11 $ 6 +
d2
de
2
N
1/d
10 ln
N
P
X
$ 6 +
V
d₂
dz
V8
N
-//d
2
2
10
1
P
X
- P
X
>
6 +
In
d
de
d
V8
1
1/d
5
N
1 P
d,
X
PP
X
3 +
In
dz
d
V
2 1
1
N
4/d
1
4/4
de/2
(3
5
In
N
N
-5/d,
du
dx
V8
V8
(e
1
1/22
d2/2
8
N
-1/d2)
da12
3
In
e
N2
N2
dx
V8
V8
1/da
de/2
5
3
5
In
V8
2
N2
N
?
N/d.
e2
N
1/d,
v8)
d,12
5
2
222
N2
6
8
28
> 1
22
N2
N2
where X denotes chi-square random variable with d, degrees of freedom. For the first inequality in (2), we use the inequalities
E[e-tX] t>0 ((zdd,)
(1 + 26) d2//2
P(X- 22) I inf
inf
=226--3 for 0
e (2)d))
E E(e2X
(1- 21) 21)-21/d2 da/2
P(X > 2 d < inf
inf 0ct<11/2
(zet-syde/2 for > 1
(=.dd_)
cl(xdd2)
which directly follow from the Chernoff bound for the chi-square distribution. For the third inequality
(2), we use the fact that max (In 2)/2 1/e and N 2 1. For the last inequality in (2), we use
3 + 5 < 1.
14

---

Under review as a conference paper at ICLR 2021
Then, X' is (IN/VO)R/L, /3e + z Ln(N/Vo) separated with probability at least 1 - å as the following bound holds:
V 2
gl/d= N 2/dx 1 vd
N-2/d=
|2g - 23yl2 S
6 +
10
In
vi +1)
dp
vo
10
N
| 2zll2 < v 2 82/d N 2-2/d
=1
=1-P - P
Ri j s.t. ||=r -2yll2> >
6 +
d
In
vo
or
21 Σ
P
11 - 2z112
6
10
In
N
or
az 2yll2 V
22id N2/dd
dz
v
(F1
=1 - Σ
1-P PP
(2
28//dd
N
2/dd
1
| xylla S V
6 +
10
In
N
vdz
dz
V8
itj
N(N
28
2
2
N2
2
where the first incquality follows from the union bound and the second inequality follows from (2). This completes the proof of Lemma 8.
15

---

Under review as a conference paper at ICLR 2021
D MAIN PROOF IDEA: MEMORIZATION USING STEP AND ID
D.1 MAIN IDEA
In the proofs of Theorem 1, Theorem 2, and Theorem we use each sigmoidal activation for approximating either the identity function (ID x + x)) the binary step function (STEP I r 1[x 2 O... Thus, we construct our network for the proofs using only ID and STEP activation functions, which directly provides the network construction using sigmoidal activation functions (see Section D.2 and Section D.3 for details).
D.2 TOOLS
We present the following claims important for the proofs. In particular, Claim and Claim 10 guide how to approximate STEP and ID by a single sigmoidal neuron.
Claim [Kidger and Lyons (2020, Lemma 4.1)). For any sigmoidal activation furictoioonfuunction a, for any bounded interval I for any > there exist a, b, c, d IR such that la-ola- (c for all x E I.
Claim 10. For any sigmoidal activation ffnction o, for any e, > 0, there exist a, b, c E R such that 1[ 0] < e for all $ 6,8]
Ja: (e. x)
Proof of Claim 10. We assume that = limy o (x) < lim (xx =: 3 where the case that < a can be proved in a similar mannerwdd. From the definition of a, B, there exists & >> 0 such that (x(x) al (3 ai) if < k and (xx) 3 (B a)e if > k. Then, choosing
B-a+ and
completes the proof of Claim 10.
Claim 11. For any a, x E R such that a + for any E N, it holds that
x a-b
[a/a] b
Proof of Claim 11. It trivially holds that [a/a]
<
b [2/a]] 1. Now, we show a contradiction if < [
a-b
Suppose that a-b
<
[m/a]]
Then, there exists an integer such that
x
[x/a] b
x
m
and hence,
<
m
a
which leads to a contradiction. This completes the proof of Claim 11.
D.3 TRANSFORMING STEP+ID NETWORK TO SIGMOIDAL NETWORK
In this section, we describe how transform STEP + ID network into a sigmoidal network within arbitrary error. Formally. we prove the following lemma.
Lemma 12. For any finite set of inputs X, for any STEP + ID network f, for any & > O, for any sigmoidal activation function a, there exists a network g having the same architecture with fo such that
(f(x) - g(x)l <
for all x E X.
Then, the construction in Lemma 12 enables to construct STEP ID networks instead of networks using a sigmoidal activation function for proving Theorem 1, Theorem 2, and Theorem
Proof of Lemma 12. Without loss of generality, we first assume that for any STEP ID network h. in the evaluation of fz),, all inputs to STEP neurons (i.c., 1[r 2 0)) is non-zero for all e X. This assumption can be casily satisfied by adding some small bias to the inputs of STEP neurons where such bias alwasy exists since | < cc. Furthermore, introdueing this assumption does not change h(x)) for all x E X'
Now, we describe construction of Let 8 be number satisfying that the absolute value of all inputs to STEP neurons in the evaluation of f (x) for all x E is at least 5. Such 8 always exists due the assumption made. Let L. be the number of hidden layers in Starting from f,
16

---

Under review as a conference paper at ICLR 2021
iteratively substitute the STEP and ID hidden neurons into the sigmoidal activation from the last hidden layer to the first hidden layer. In particular, by using Claim 9 and Claim 10, we replace ID and STEP neurons in the é-th hidden layer by neurons approximating ID and STEP.
First, let 91. be a network identical to f except for its L-th hidden layer consisting of a neurons approximating ID and STEP in f. Here, accurately approximate ID and STEP neurons by using Claim 9 and Claim 10 so that 9r. (z) f()) < E for all x E X. Note that such approximation always exists due to the existence of å O. Now, let 9t-1 be a network identical to fr. except for its (L- 1)-th hidden layer consisting of a neurons approximating ID and STEP of gr. Here, we also accurately approximate ID and STEP neurons by using Claim and Claim 10 so that (x)(x) - 91-1(z)) < E for all z E X. If we repeat this procedure until replacing the first hidden layer, then g == 9i would be the desired network satisfying that (f g(x) < & for all E X. This completes the proof of Lemma 12.
L
17

---

Under review as a conference paper at ICLR 2021
E PROOF OF LEMMAS FOR THEOREM
For proving each of Lemma 4-7, we prove stronger technical lemma, as stated in Sections E.1-E.4, and transform the STEP + ID networks to a networks using Lemma 12.
E.1 PROOF OF LEMMA
To prove Lemma 4, we introduce the following lemma. We note that Lemma follows the construction for proving VC-dimension lower bound of RELU networks (Bartlett et al., 2019). The proof Lemma 13 presented in Section H.4.
Lemma 13. For any A, B, D, K, R E N such that AB 2 K, there exists a STEP + ID network fe 2f BD 2 hidden layers and 4A + ((2R + 5)2% + 2R² 8R + 7) B R22 112 parameters satisfying the following property: For any an finite set X C [0, K), for any y [K] - [2P]. there exists O such that fe(x) = v([=l) for all X.
By choosing K + v, A (VV)), B + @(VI-"), R 1 (2p log V, and D [log C
Vi-p in Lemma 13, there exists a STEP + ID network of 0 1II1--003)) log log C*) hidden layers and O(VP) parameters which can memorize any X' C R of size V with C' classes satisfying [X] [V] Combining this with Lemma 12 completes the proof of Lemma
E.2 PROOF LEMMA
Since the proof trivial when dg 1, we consider de 2. To this end, we first project all X to E R. by choosing some unit vector u E IR so that
max (x,x))() |u (x - x')l lu (z x')l
TdZ 8
< N
min (x)))E()))
Such a unit vector u always exists due to the following lemma. The proof of Lemma 14 is presented in Section H.I.
Lemma 14. For any N,d, E N. for any X E (K*)), there exists a unit vector u E Rda such that No r'1l2 |u (x x')l < || x' 2|2 for all x, E X.
Finally, construct the desired map by
u x min (u x: X1}
min (2.2 (2 (())) Iu (x x')] = xb
This completes the for some u e IR and e so that [( buu=+b:r x) ( ( proof of Lemma 4.
E.3 PROOF OF LEMMA
To prove Lemma 6, we introduce the following lemma. The proof of Lemma 15 is presented in Section H.2.
Lemma 15, For any N, K, d E N, for any X such that [X] E (1K)), there exists a STEP ID network
of hidden layer and width d such that [f(x) (TT) where T max { [ 1. N² + +1]].
From Lemma 15, hidden neuron which can map any Z such that [Z] ((K)) Z' such that [z'] E ((F) where
observe that STEP ID network of 1 hidden layer consisting of
T : max { Lemma 6. [
K
1 + 1]} Combining Lemma 15 and Lemma 12 completes the proof of
N²
18

---

Under review as a conference paper at ICLR 2021
E.4 PROOF OF LEMMA
In the compression 2 step, we further improve the bound :- I + 1 on the hidden feature values V ((N2-w), Namely, we map X3 to X4 such that [Xa] we introduce the following lemma. The proof of Lemma 16 is presented in Section H.3.
To construct such mapping.
Lemma 16. For any N, K L, d1...., dg E such that N < K and de 2 for all e, for any X such that [X] E (1K).. there exists a STEP + ID network f of L hidden layers having dy neurons at and
the E-th hidden layer such that Lf(X)] E (X) where T == :=min K, max {N
N 1
c 1 (d= -2]]
-
From Lemma 16, a STEP ID network f one hidden layer having O 9(x2) hidden neurons can map any X' such that [X] N Combining this and Lemma 12 completes the proof of Lemma 7.
((K) to f(X') such that [f(x)) = (x) where T := max N, [4
19

---

Under review as a conference paper at ICLR 2021
F PROOF OF THEOREM 2
In this proof, we construct a STEP + ID network and transform it to a a network using Lemma 12, as in the proof of Theorem I in Section and Section E. particular, Theorem 2 a direct consequence of Lemma 14, Lemma 15, Lemma 16, and Lemma 17 presented as follows. The proof Lemma 17 is presented in Section H.7.
Lemma 17. For any A, B, D. K N such that AB z K, there exists STEP ID network fo of A + (2D + B)B hidden layers and width 3 satisfying the following property: For any finite set X E [0, K),fon for any y [K] (22), there exists 0 such that Fo(x) (((o)>((Laa v((=])
From Lemma 14, Lemma 15, and Claim STEP ID network of [log(A Log(Av2Td)) 2 hidden layers
and width can map --sepparteed set of inputs X1 to Xg such that [ E ((0) where U := 22
1 +1J. From Lemma 16, a STEP+ network of E/=r [log(U/V)]11 (1
[FF(((N) +) [V/N] 1-1
hidden layers and width can map X2 to X3 such that [2g]] E (IV) for some N S V S U. Here, we will choose V = ((N43). Finally, from Lemma 17, for any A, B E N such that AB 2 V, STEP ID network of A (2D + B) hidden layers and width
map X3 their labels where D llog C1. We will choose B ((V2/3) satisfy AB 2 O(N4/3).
< U and AB 2 V. a STEP + ID network of Hence, for any A, B, E N such that < 2N (lod(A)2Td..) E Li= [og(U/V\] (I [7/22 - +
+ A (2D + 1)B hidden layers and width 3 can memorize arbitrary A-separated set of size N. Note that combining functions does not require additional hidden layer as the linear maps constructing the outputs of functions can be absorbed into the first linear map in the next function.
2N
[V/N]
Finally, substituting V < [N4/31, A IV (2D + 1)V1, and [V TV/(22D + 1)] and using Lemma 12 result in the statement of Theorem 2. This completes the proof of Theorem 2.
20

---

Under review as a conference paper at ICLR 2021
G PROOF OF THEOREM 3
The proof of Theorem have the same structure of the proof of Theorem consisting of four steps: projection, compression I, compression 2, and learning. In partieular, we construct STEP + ID network and use Lemma 12 as in the proofs of Theorem and Theorem 2.
For the network construction, we divide the function of fe into four disjoint parts, in Section 5. The first part does not utilize a hidden layers but construct project input vectors into scalar values. The second part corresponds to the first In hidden layers decreases the upper bound on scalar values to ((N2). The third part corresponds to the next LK-1 11 hidden layers further decreases the upper bound to of ). The last part corresponds to the rest hidden layers construct a network mapping hidden features to their labels.
Now, we describe our construction in detail. To begin with, let us denote A-separated set of inputs by X1. First, from Lemma 14, one can project X1 to X2 such that [X2] E (IINAAVrd that the projection step does not require to use hidden layers as it can be absorbed into the linear map before the next hidden layer. Then, from Lemma 15, the first L1 hidden layers can map Xr to X3. since
Note
N
([LN2/4+1J)
such that [xs]
N
L1
dg +
d, +1
N Td_/8
II
2
A
/
2Td
2
2
N2/4
8=1
N2
N V Tdz/ /8
4
I Lide + 1)/2]
N2
N2 A / Tdz//
+1
4
IT Ide + +1//2]
N2
NºA / rT2//8
+1
1122, + 1)/2]
Note that we also utilize Claim 11 for the sequential application of Lemma 15, Consecutively, from Lemma 16, the next LK-1 - L1 hidden layers can map X's to X₂ such that [Xc] E (1rv/2" "I)) since the third condition holds and
N
L
(de 2) 2 2
(de 2) 2 2
R= 1+1
1=
1+1
L
(de 2) 2 2'+2
1=4-111
N
I N
Et=L, 1+1 11111114 (de - -2)
2i+2
N
N
<
Li
(dle - -2) i
21+1
N
N2/4
NNx
2i-1
t== L tiide
(de 2)
N
No +
+NX
2
N
1N2/4+11 +1
SNx x
Li=L- E
Σ L
21
21

---

Under review as a conference paper at ICLR 2021
where the inequality [a] - 2a for 2 1/2 and the assumption K < log N, ie., N/2 2 1 for $ log - 1. Here, we also utilize Claim 11 for the sequential application of Lemma 16.
Now, we reinterpret the last condition as follows.
LK
2x
Σ
(de de-22) (7. Lx 1)/oog
2 N2 -4
(=LK-i+1
LK
N2/4+11 +1
(de - 2)
[L- LK 11/[llgg7]
2
2k
FmLx
1+1
Lx
LNV /4+/4+1]
(de - 2)
(I- Lx 11//log C7
2
f=
Finally, using the following lemma and the above inequality, the rest hidden layers can map X4 to their corresponding labels (by choosing L' := L3). The proof of Lemma 18 is presented in Section H.8.
Lemma 18. For D, K, L, di,.... de E N. suppose that there exist
L'
and
TV-11.... .LL-1 E N satisfying that for TL = =rL- =1
3'
)
1-1 De DE
Σ (de 2) 8=1
2)
2 K and 2 + +r +3 de for all L'+1seSL
D
Then, there exists a STEP + ID network fo of L hidden layers having de hidden neurons at the f-th hidden layer such that for any finite X [0, K), for any [K] - [2P), there exists O satisfying fo(x) = v([=]) all a E X.
Choose K + [U/2K-21 and rz = all Lemma 18 completes our construction of the STEP ID network. Note that we utilize the condition that de 2 7 for all Lx < & here. Using Lemma 12 completes the proof of Theorem
22

---

Under review as a conference paper at ICLR 2021
H PROOFS OF TECHNICAL LEMMAS
H. 1 PROOF OF LEMMA 14
Since the upper bound holds for any unit vector E Rdr, we focus on the lower bound. In addition, 8
if N 1, the result of Lemma 14 trivially holds. Hence, we assume N 2 2, i.e.,
Rd. N² < 1. In
this proof, we show that given any vector Rdd such that ||l||2 * random unit vector E Rd, from the uniform distribution satisfies that
1u vl
8
2
P
(4)
|0012
T Td2 N2
N
This implies that there exists a unit vector E R& such that
Td= N2 || x'1l2 S |u (x )
8
for all 2,, x' X, due the following union bound: for V f x' : [x, (2) x S x for some total order I on X.
Iu
8 Td2
N(N
2
TdZ N }
2 x
N 1.
|
|0o12
N
NEE
DEV
Now we prove (4). To begin with, we show that the following equality holds for any e E R:
P a
8
N2 P
[uil
|el|a
zdz
xd N2
Here, the equality follows from choosing v/ e/|uu|22 = (1, 0, ...., using the symmetry. Furthermore,
P
[uui
8 can be bounded by
nd,
N=
8
= P (0 (0<uu> u1
1
ddz N2 < 41 S 0))
1
P
|u1l
+P
Td
N2
Tdz N2
8
2 x P 0 ui V
Tdl N2
2
Aread, (1)
X
Jarccos rdu N2
Aread (sin Φ)
=2x x Area,, (1)
de ods
X
Aread (1)
arrcos
mdy N
2m 1 /T( 2
2 X
sin d. -2 odg
2T 4 (T(4))
arcoos
The
dir
2 X
1dØ
arccos
Tay NT
2d
π
(V
8
arccos
π
2
Td
N2
2d
(V
8
1
aresin
Td. N
2d
π X RdZ N2
1
<
2
N2
where Area.(r) 2n 2 /I' (4) denotes the surface area of a hypersphere of radius in Rd and [(x) denotes the gamma function. Here, the second equality follows from the symmetry and P(u = 0) = The first inequality follows from sin Φ S and
r(4)
7 < < de from the Gautschi's
inequality (see Lemma 19). The second inequality follows from @ < sin for 0 < < z. This completes the proof of Lemma 14.
23

---

Under review as a conference paper at ICLR 2021
Lemma 19 [Gautschi's 's inequality (Gautschi, 1959)]. For any x > 0. for any E (0, 1).
[(x + 1) [(x + 8) < (z + 1)
24

---

Under review as a conference paper at ICLR 2021
H.2 PROOF OF LEMMA 15
In this proof, we assume that K > /4 and
[[a+1/22
K
where other cases trivially follow from
this case. To begin with, we first define network fz) K)) (0, for (b.) (dd-1//1 [T]
x
i <T if S x < 2T
T + bi mod T
f(()) =
b2 mod T
if < 37
x blid 1)/2] mod T
if d-1
T S
2
1)/1)
i-1
= x - T x 1 2
Σ
b (h~
Σ b)
x 1sx 2 iT] - T 1 + 2 (i 1)T]
(5)
One can easily observe that can be implemented by STEP ID network of 1 hidden layer and
width as 1[x 2 T] in (5) can be absorbed into (b, Σド= 6,) 1(2 2 i7 (5) for
Now, we show that if T > N? /4, then there exist b E [T] such that [[f((()]| = N to complete the proof. Our proof utilizes the mathematical induction on If there exist b1...., ,b; (I') such that
[T]
(6)
then there exists b, [T] such that
[b((x < < (1 x
(t x 1771))
Here, one can observe that the statement trivially holds for the base case, i.c., for {- E X : < T}. Now, using the induction hypothesis, suppose that there exist bi..... b-t [2]] satisfying (6). Now, we prove that there exists b, E [T] such that Sp., == [fo(fx E X' iT < < (i 1)T)) does not
intersect with T = [ff(f X x H)), i., (7) holds. Consider the following inequality:
2
Σ Sb. n |S,,1 x ITIS 1EI
where the equality follows from the fact that for each {x X : iT S x < (i+1)T), there exists exactly [T] values of b; so that [x mod T] E T. However, since the number of possible choices of T. T N2 N2/4, /4, then there exists b; [T' such that Sa nt 0, ie.. (7) holds. This completes the proof of Lemma 15.
25

---

Under review as a conference paper at ICLR 2021
H.3 PROOF OF LEMMA 16
The proof of Lemma 16 is similar to that of Lemma 15. To begin with, we first define a network
[x(x:) [0, K) + [0, for (b;) [T]C and T =: Mi < M2 < < Mc+1 K so that
1x X: M, M = T [
for all i as
x
i < T if M1 T S M2
+ b mod T
[((x)
x + b2 mod T
if M2 S x < M3
x + be mod? T Mc x
i-1
27 x 1 7 + Σ
(T+b;
1/r Mi]
j=1
x
1 x 2 min - bi, M++1]]
(8)
where (8) holds as T > [ Here, layer and dz neurons at the f-th hidden layer by utilizing one neuron for storing the input æ; another neuron for storing the temporary output, and other neurons implement indicator functions each layer. This is because one do not require to store x in the last hidden layer and there exists 2C' indicator functions to implement (T' x 1[x 2 T) in (8) can be absorbed into (T + b, Σ}= by) in (8) for = 1).
easily implement fo by STEP + ID network of L hidden
1 2 M,]
Now, we show that if N, then there exist E [T]] such that [fo(X)] N to completes the proof. Our proof utilizes the mathematical induction on é: If there exist , E [T] such that
[fo( E X: <
(1 x: M
(9)
then there exists 6; [T'] such that
[T] Li(lx E E < M+11)]] = (1tto E X : < M
(10)
Here, one can observe that the statement trivially holds for the base case, i.e., for fo X : < T) From the induction hypothesis, suppose that there exist bj....,b, prove that there exists b, E [T'] such that Sb. := [fa(( E X : M, S < M,+1)) }]] does not intersect
E [T) satisfying (9). Now, we
with T = [s((x X : x S M,H],, i.e., (10) holds. Consider the following inequality:
Σ S. T I 6.E[T]
(N
J) <T
1 and for each (x E X': M₁ S x M,+1), there exists exactly IT| values of by so that [ mod T| E T. However, since the number of possible choices of b; is T, there exists by E [T] such that Sz nt 0. Le, (10) holds. This completes the proof Lemma 16.
where the first inequality follows from the fact that |Sp J.
26

---

Under review as a conference paper at ICLR 2021
H.4 PROOF OF LEMMA 13
In this proof, we explicitly construct fa satisfying the desired property stated in Lemma 13. To begin with, we describe the high-level idea of the construction. First, construct a map g : + [L mod B) to transforming an input x E [0, K) to a pair (a, b) such that a E [A] and [b] E [B]. Here, we give labels to the pair (a. b) corresponding to the input x as y(a, [b]) = v([= Note that
this label is well-defined as if [21] # | then [g(x))] A [g(x2)]] Now, construct parameters
wo, - containing the label information of X' as
Wa = Σ
y(a, c) 2 (=+1)) cE
(11)
i... from the (16] D + 1)-th bit the (16) D D)-th bit of the a-th parameter (w,) contains the label information of (a, [6]). Under this construction, we recover the label of E X' by first mapping the pair (o, b) and extracting the z-th parameter wa- Then, using STEP, we extract bits from the (Lb] D + 1)-th bit to the (Lb] D + D)-th bit of w, to recover the label.
Now, we explicitly construct the above procedure. To this end, we introduce the following lemma. The proof of Lemma 20 is presented in Section H.5.
Lemma 20. For any A, B, K, L, d,,1,...dd, dr E N such that AB 2 K and de 2 for all f, for any wo; ..... WA-1 E B. for any finite set X C [0, K), if it (de (de-2) 2 A, then there exists a STEP + ID network of layers and de neurons at the E-th layer such that fxx [w| [/ x mod B) for all X.
From Lemma 20, a STEP + ID network of hidden layer consisting of A + 2 hidden neurons can map X to (wl [w|//B] o mod B). Note that this network requires overall 4.4 + 10 parameters (3.4 + edges and A + 4 biases).
Finally, we introduce the following lemma for extracting from the (16) D 1)-th bit to the (L6] D + D)-th bit of Wa The proof of Lemma 21 is presented in Section H.6.
Lemma 21. For any D. B, R E N. for any finite set X' C [0. B), there exists a STEP + ID network f
2 BDT hidden layers and ((2R + 5)2 + 2R + +8R + 7) R R2 R² + 3 parameters
R
satisfying the following property: For any w BD U, 2 such that u, E (0, f(x, w)
E UIz]-D+i x D- for all x X.
From Lemma 21, STEP ID network of 2 BD1 hidden layers and ((2R+5)22) + 5)2 +2R + 8R 7) BB1 TP R2 R² 3 parameters. Hence, by combining Lemma 20 and Lemma 21, So can be implemented by a STEP + ID network of 2 BD + 2 hidden layers and 4A + ((2R + +5)2R + 2R 8R + 7) BD R R² + 3 parameters. This completes the proof of Lemma 13.
R
27

---

Under review as a conference paper at ICLR 2021
H.5
PROOF OF LEMMA 20
We design I as f == Jr. o ... S (0, where each fe represents the function of the 8-th layer consisting of de neurons. In particular, construct as follows:
fe(w,z)= = ( + wp x 1le = +|+ d
Σ
(worts wocti-1) 1[x 2 iB),
de
--
Σ
B x 1/ 2
1=1
where w-11 == 0 and og = E - 2) Then, f is the desired function and each fz can be implemented by STEP + ID networks of 1 hidden layer consisting of de hidden neurons (two neurons for storing w and other neurons are for de 2 indicator functions). This completes the proof of Lemma 20.
28

---

Under review as a conference paper at ICLR 2021
H.6
PROOF OF LEMMA 21
We construct (x, w) := 2 BD/R|+D x [[BD/R o... fi( w) where ft is defined as
n1 U2V im1 U((-1)R4+ x x (t-1)--
Ei= (U(E-1)R++ A 1. S x < m4 + 11) x 2-
if <
BD π
fz(
U(t-1))(+i x x (1-1)R-i
Ei= (u(-1))R+i 1mma Sx < m,, + 11) 2
if
where u, denotes the i-th bit of the binary representation, A denotes the binary 'and' operation, and m4,e, Tie are defined as
mi,e (e 1)R
D
BD
R+ ((e-))++i- mod D) +
Tie =
R
Namely, each ft extracts R bits from the input w and store the extracted bits to the last bits of v the extracted bits are in from ([æ:] D + 1)-th bit the ([x] D D)-th bit of w. Thus, f(r w) is the desired function for Lemma 21.
To implement each ft by STEP ID network, we introduce Lemma 22. Note that we extract u, from w in Lemma 22, i.e., we do not assume that un is given. From Lemma 22, a STEP + ID network 2 B. hidden layers consisting of 2 R and R + hidden neurons alternatively can map (z. w) to Els MIzJ-D+i x 2 for all E X. By considering the input dimension 2 and the output
dimension 1, this network requires (2R + 5)2 + 2R² + 8R 7) R R22 R2 + 3 parameters
((2R + 4)2 + 2R² 6R + 4) BD R2 R² + edges and (2 + 2R + 3) This completes the proof of Lemma
R + biases).
R 21.
Lemma 22. STEP + ID network of hidden layers having 2 + R + 1 and R R+2 hidden neurons at the first and the second hidden layer, respectively, can implement ft-
Proof of Lemma 22. We construct fe == gs (g2 @ 91) where 92 @ 91 denotes the function concate- nating the outputs of 91, 92. In this proof, we mainly focus on constructing fe for l < R since fIBD/RD R can be implemented similarly. We define 91, 92: as
2
(I. w) = x, U,
mi x
x
ER So <o< (
2
MRs x 1/i 1 en <u <o< (
1=0
= U, ((--((()))))))) 1)1++).......... : u(R)
(2( v) = 1/mi, S x < m.. + 1l...., 1mm S m
R
03 (0) 92)
r,
u(c 1 (1-1))-- (---t))
R
[((e-1)R+5 + 1[max S x < mi, + 1] 2 2] Ti,e
t=1
R
M(1-1)R-i x (2-1))-)
8, U
1=1
(u(E-1)844 A 1/mie S < m4, + 1]) -ir
29

---

Under review as a conference paper at ICLR 2021
FR implies that the ( + r)-th bit of a is and 7/, = otherwise. Here, one can easily observe that 91 can be implemented by a linear combinations of 1( 2 2 2n] " 1/e 2 (2 - 1) 2-t as trivially holds that 1 2 0] and 1[ < 2 2-(11)) i... 2 indicator functions are enough for 91. Hence, 91 be implemented by STEP ID network of 1 hidden layer consisting of 2 + hidden neurons where additional neurons are for passing z; u. In addition, 92 can be implemented by STEP ID network of It hidden neurons. Finally, ga can be implemented by STEP + ID network of hidden layer consisting of R + 2 hidden neurons (R neurons for R indicator functions and neurons for passing z, v).
where 7/ is a constant such that Tr. = 1 if 2 I (i + 1) 2 2
Therefore, fe can be implemented by STEP ID network of 2 hidden layers consisting of 2d +/++ R++1 1 hidden neurons for the first hidden layer and I hidden neurons for the second hidden layer. Note that inplementation within two hidden layer is possible since the outputs of 91. are simply linear combination of their hidden activation values and hence, can be absorbed into the linear map between hidden layers. This completes the proof of Lemma 22.
30

---

Under review as a conference paper at ICLR 2021
H.7 PROOF OF LEMMA 17
The main idea of the proof of Lemma 17 is identical to that of Lemma 13. Recall A, B and wo,...; WA-1 E R from the proof of Lemma 13. From Lemma 20, for any finite set & [0, K), for any wo:-.... WA-- E R,, a STEP + ID network of A hidden layers and width 3 can map x to [z/]] x mod B) for all E X. Now, we introduce the following lemma replacing Lemma 21.
DB Lemma 23. For any D, B E N, for any finite set X B), for any w Eim1 u, 2 for some W; E {0, 11. there exists a STEP + ID network f of (2D + B)B hidden layers and width 3 such that f(z, w) E D++ D+i 2 for all E X.
Using Lemma 20 and Lemma 23, can easily find STEP + ID network of A (2D + 1)B hidden layers and width satisfying the condition in Lemma 17. This completes the proof of Lemma 17.
Proof of Lemma 23. We construct f(x, w) == 20(++1) x fDB o 9DB LDB .... fi h1 where Jts gt, he defined
rr, w)
if mod #
he(a, w)
x - + 3K x 1/r < 0).w)
if mod D =
ge(2,, w) (I, 2 1 [[ 2 2 2 1/w 2 2-
fe(æ, w, n) (x, w 2- DK-d(()))))))) 1[x - < 11)
where d(E) := f 1- 1. Now, explain the constructions of fe, he. Let d E [0, B) and v E [0, be inputs of f. i.e. consider f(b, u). First, the indicator function in he is activated only l [[b] +)
+ 1 as b B. In particular, the first entry of the output of h((b+1)) D+1 is greater than 2B and this is the maximum value of the first entry of the output of (1) as monotonically decreases as l grows. The indicator function in Se extracts and outputs the E-th bit of u. Lastly, fe add the f-th bit of u if and only if f E [1b]- D + 1..... (Lb) + + D). This is because (16) + 1) D).
[[1, 0) if and only if E {[6]- D
Here, fig at l mod D can be implemented by STEP + ID network of hidden layer and width 3, ge can be implemented by STEP + ID network of hidden layer and width 3, and fa can be implemented by STEP + ID network of hidden layer and width 3. Hence, f can be implemented by STEP + ID network of (2D + B) hidden layers and width This completes the proof of Lemma 23.
31

---

Under review as a conference paper at ICLR 2021
H.8 PROOF OF LEMMA 18
The proof of Lemma 18 is almost identical to the proof of Lemma 13. Recall A, B and Wo,...; WA-1 1 R in the proof of Lemma 13. From Lemma 24, for any finite set & [0, K), for any Wo,, WA-1 E IR, the first I'' hidden layers of the STEP + ID network Se can map x to (u|z/B]a mod B) for all x E X. Now, we introduce the following lemma replacing Lemma 21. Using Lemma 24 completes the proof of Lemma 18.
Lemma 24, For any D, B, R. L,, L,,d,,.... dr E N, for any finite set X C [0, B), suppose that there exists 1by-----b-1 E N satisfying that for ro rL 1,
1-1
Σ rr BD, 1=1
2 +re ré-1 +35 de for all
ises L.
Then, there exists STEP ID network I of L. hidden layers having de hidden neurons the 8-th BD
hidden layer satisfying the following property: For any EBD us 2 such that uy {0, 1}. f(z, w) = Eist Dxx x D for all a E X.
Proof of Lemma 24. The proof Lemma utilizes the network constructions the proof' of Lemma 21 and Lemma 22. In particular, we construct f(z, w) == 2/= xxx ft-10.... fz w) defined as
12 Eis unati x 2- Ri-i
ve( =
+ + (URE4i 1[mi, S x < mit + 11) x x
if <
BD H
1= URe+i x 2 Ri-i
- (UR A 1[m4, S x < m,, + 1I) x 2 sie
if l =
BD π
where denotes the i-th bit of w in the binary representation, A denotes the binary 'and" operation, and Re, mi,e, Si,e are defined
Rs =
TE:
i=1
+
m,, =
D
$1,8 == RL + (Re +i- mod D) + 1.
Note that R₁ = O as the summation starts from i and R2 = -1 rt- Namely, each ft extracts rz bits from the input and it store the extracted bits the last bits of if the extracted bits are in from (|æ) D + 1)-th bit to the ([x] + D) bit of w. Thus, fxr w) is the desired function for Lemma 24.
We construct [e( v) using the f-th hidden layer and the (E+ 1)-th hidden layer, i.e., there exists an overlap between constructions of [x, v) and Set1 (x, v). In particular, Lemma 22 directly allows us to obtain such a construction under the assumption in Lemma 18 that
n + r2 + T + S de for all
LEE5L.
This completes the proof of Lemma 24.
32


Reviews:
[{"review_id": "Vl32bwa6hCw", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:  \n\nThis paper makes the following four contributions. \n\nFirstly, it is shown (Theorem 1) that \\Theta(N^{2/3}) parameters are sufficient for neural networks --with sigmoidal activation functions -- to memorize N input-label pairs, under an admittedly mild “\\Delta-separated” assumption on the input points (Definition 1). This is an improvement over existing results which show that \\Theta(N) parameters suffice, albeit typically for arbitrary N input-label pairs. As discussed in the paper, this result implies that depth is crucial for memorization with sub-linear parameters.  \n\nSecondly, the authors show (Theorem 2) that for fully connected networks of width 3, with sigmoidal activations,  \\Theta(N^{2/3} + log(\\Delta)) parameters suffice for memorizing any \\Delta-separated set of N input-label pairs. This implies that the network width does not necessarily have to increase with N for memorization with sub-linear number of parameters. \n\nThirdly, the authors study the question of identifying the maximum number of input-label pairs a given network can memorize and provide general criteria (Theorem 3) for the same. Existing results for this problem show that the number of arbitrary input-label pairs that can be memorized is at most linear in the number of parameters. The result in this paper shows that memorization of \\Delta separated points can be done with the number of pairs super linear in the number of parameters.\n\nFinally, empirical evidence is provided which support their theoretical results, namely that deep networks memorize better than shallow networks (With the same number of parameters).\n\n\n----------------------------------------------------------------------------\nReasons for score:  \n\nThe paper provides novel theoretical results for the problem of memorization via deep neural networks. After the discussion phase, however, the significance of these results is a bit unclear to me.\n\n------------------------------------------------------------------------------\nPros:\n\n-\tVery well written and clearly structured paper. The problem has been motivated nicely in the introduction.\n-\tThe related work section is rigorous and clearly details the current results for this problem.\n-\tThe empirical results are convincing and support the theoretical claims in the paper. \n\n-------------------------------------------------------------------------------\nCons: \n\nNo proof sketch is provided within the main text for any of the theorems. Studying finite sample expressivity of a network in an infinite precision setting also seems a bit strange (See \"post discussion\" below). Some minor remarks (typos etc.) are listed below, I am hoping that the authors will provide the clarifications stated therein in the rebuttal phase.\n\n------------------------------------------------------------------------------\nMinor comments:\n-\tTypo on pg. 3 (Section 2.1): d_{max} and d_{max} --> d_{max} and d_{min}\n-\tTypo on pg. 5: Definition 3 define the memorizability … --> Definition 3 defines memorizability …\n-\tOn pg. 2, 3rd para after Theorem 1: I think the opening sentence is true provided  \nlog(\\Delta) is less than N^{w}, isn’t it?\n-\tTowards the bottom of pg. 2, after the Theorem of Bartlett et al., it is mentioned that Theorem 1 together with Bartlett’s theorem imply that depth necessarily has to increase with N for memorization with sublinear number of parameters (this is stated on pg. 5 as well). This implication was not clear to me, some additional explanation will be helpful.\n-\tThe discussion after theorem 2 (starting on pg. 5) involving the comparison with the function approximation problem is a bit unclear, especially the part on pg. 6 which discusses transforming the d_x dimensional inputs to “distinct” scalar values.\n\n-----------------------------------------------------------------------------\nPost discussion: \n\nFollowing the discussion phase, the significance of these results seems to be a bit unclear to me. For instance, suppose that we are allowed to construct the sigmoidal activation. Theorem 2.1 in  the following paper https://hal.archives-ouvertes.fr/hal-01256489/document  states that for any continuous + univariate function $f$, and $\\epsilon > 0$, there exists a sigmoidal activation function in $C^{\\infty}$ and an associated neural network with one neuron in the hidden layer (with the aforementioned sigmoidal activation) such that $f$ can be uniformly approximated to accuracy $\\epsilon$ by this neural network. Therefore the set of N points in $\\mathbb{R}^{d_X}$ can be first mapped to distinct points on a line, and then be  shattered/memorized by the aforementioned one-neuron neural network. Of course, the setup in the present paper considers the sigmoidal activation to be fixed (e.g., ReLU) and this is a non-trivial difference. But still, it is not clear just how big of a difference this is. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "4we_TlLDQAp", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proves that $\\Theta(N^{2/3})$ parameters are sufficient for memorizing arbitrary N input-label pairs under the mild $\\Delta$-separation condition. Overall, it is an interesting theoretical paper and obtains an improved rate over previous works. There are some concerns given as follows:\n1. The $\\Delta$-separated set seems to be an important condition. The paper claims that $\\log \\Delta$ is not a big number. I am wondering, when the data points are iid from some distribution such as a multivariate normal distribution, what is $\\Delta$ in terms of sample size? In this case, $\\Delta$ will depends on both the sample size and the input dimension.\n2. The theoretical developments in this paper are for fully connected feedforward networks. How to extend it to CNNs? The experiments are for ResNets. There seems to have a gap.\n3.The paper considers the network where the output dimension is 1. How to extend this to networks with more than 1-dimensional output? It is not clear to me in the Definition 3, how to use a network with 1-d output to memorize data with C classes.\n4. What is the connection among memorization, training/testing accuracy, and generalization? In the experiment part, the authors sometimes try to show there are some connection but sometimes try to show there are no relationship. It is confusing.\n5. Can authors highlight the novelty of the proof? Are there any new techniques beyond those from previous papers? ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-46mkP3lD1X", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "==== Summary ====\n\nThe paper studies the memorization capacity of deep networks as a function of the number of parameters. Many prior works have shown that to memorize $N$ examples $O(N)$ parameters are sufficient and that to memorize any set of $N$ examples $\\Omega(N)$ parameters are necessary. This work shows that under very mild and commonly satisfied conditions, $O(N^{\\frac{2}{3}})$ parameters and layers are sufficient for memorizing $N$ examples, a significant improvement over prior results. Additionally, they show that even very narrow width-bounded networks can memorize with sub-linear parameters, but the same is not true for depth-bounded networks, demonstrating a new capability unlocked by deeper networks. Finally, they characterize the properties sufficient for memorizing $N$ examples by a given network.\n\n\n==== Detailed Review ====\n\nMain strengths:\n* A significant improvement over prior bounds. Memorization with sub-linear parameters impacts our understanding of how networks work and has practical implications.\n* Presents a novel perspective on the benefits of depth, showing that it is critical for optimal utilization of parameters for memorization.\n\nMain weaknesses:\n* The proof method is not discussed in the main body. The proof sketch that is in the appendix provides very little insight and is hard to digest.\n\nI recommend acceptance in light of the drastic reduction in the bound and its implications, as well as the novel perspective on the role of depth. The authors mention large supervised datasets as a motivation, but my impression is that the real implications are for self-supervised learning, where datasets are 100 times larger. For instance, GPT-3, a 170B-parameters model, was trained to predict roughly 240B unique tokens. Results prior to this suggested that even with this enormous model, it would be hard to overfit all the examples. In contrast, this new result indicates that a model 5x smaller could memorize this huge dataset completely.\n\nDespite the above, while I'm in favor of accepting the paper, I gave it only a score of 6 because of the lack of discussion and motivation of the proof techniques used in the appendices. The proof sketch in the appendix is too dense and technical, making it hard to decipher without going into the details of the actual proofs. For example, just by looking at the sketch, there seems to be no difference between the first and second compression stages. While it is clear the need for the first stage (dropping dependency on $\\Delta$), going from $U$ to $V$ seems meaningless because $V$ barely characterized beyond being between $N$ and $U$. I will be more than happy to raise my score once the authors update the paper with a clearer proof sketch and discussion of key proof methods in the body of the paper.\n\nAs a minor note, it seems as though everywhere where $\\Theta$ is used, it should be replaced with big-O notation instead, as most of these instances are upper-bounds and not tight bounds on the minimal number of parameters sufficient to achieve memorization.\n\n==== Update following rebuttal and discussion ====\n\nThe AC has raised an important point that the paper does not discuss its reliance on infinite precision. While using infinite precision is not necessarily wrong, it does make the paper's result less relevant in practice, narrowing its contributions to being mostly about theoretical aspects. More importantly, by hiding this technical detail deep within the proofs, the authors missed the opportunity to discuss the difference between the number of bits used by the parameters and the number of edges (operations) necessary for memorization. It seems to me that the number of bits is linear with the number of examples, even as you can reduce the number of edges, which does have practical implications about the utilization of the memory bought by depth. Moreover, if the authors had discussed this topic, it would've been accepted more easily.\n\nDespite the above flaws, I still find value in this article, even if its contributions are mostly theoretical.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The AC, the reviewers, and the authors had many discussions about the results in the paper during the discussion period. Below is a brief summary. 

1. The paper shows that with $O(N^{⅔})$ parameters, a feedforward neural network can memorize $N$ inputs with arbitrary labels if the inputs satisfy some mild assumptions. 

2. AC brought up in the discussion phase two central questions (one of which has been raised by R3 as well) 

a. The results rely on using the infinite precisions of real values in the neural networks. The results wouldn’t hold if the precision of the neural nets is finite. The subtlety about the infinite precision was not prominently discussed in the paper. 

b. It’s unclear to the AC what’s the practical implication of the results to generalization or optimization. In particular, it’s unclear to the AC what a finite-sample memorization result within infinite precisions would entail. The AC thinks there is a fundamentally big difference between expressivity and finite-sample expressivity. Expressivity is a very important topic to study, whereas the motivation for studying finite sample expressivity with infinite precision is unclear. (This is raised by R3 in the reviews as well.)

3. R1 supports the paper with the following main points (The AC rephrased these with some approximations, and might misinterpret to a certain degree.)

a. The paper’s result is surprising and mathematically non-trivial.

b. Memorization is an important question to study. Many prior works study it, e.g., for showing tight VC dimension bound. It can be considered as an established setting. 

c. Relying on the infinite dimension is not uncommon in ML theory. 

4. R2 does not object R1’s point 3a, but seems to have a reservation to strongly recognize the technical significance of the results because it seems potentially likely to obtain the results by combining existing methods. Both R2 and the AC had some (partial) arguments to obtain the results of the paper with non-standard architecture or non-standard activations (which doesn’t subsume the paper’s results because the paper uses standard activations and feedforward net). This does make the AC unwilling to strongly recognize the technical significance of the result, but the AC doesn’t think the results are trivial either. In any case, this issue is not among the main concerns of the AC. 

5. Regarding 3b, the AC thinks that unlike the prior work, the memorization results in this paper do not have an implication to the VC dimension (and in return, the dependency on $N$ is better), and this makes the significance and impact of the result in this paper somewhat unclear.

6. In summary, because the paper’s average score is somewhat borderline and because the AC has the concern 2a and 2b and was not quite convinced by the R1’s points or the authors’ responses, the AC is recommending rejection for the paper. The AC personally thinks the paper’s result has a strong potential and with additional clarification for the subtlety in 2a and additional results on the connections to generalization or optimization, the paper can be a strong one for future ML venues. 

Decision: Reject