Year: 2020

Abstract:
It is known that O(N) parameters are sufficient for neural networks to memorize arbitrary N input-label pairs. By exploiting depth, we show that O(N) 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.

heading: 1 INTRODUCTION
text: The modern trend of over-parameterizing 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-parameterization enables us to 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-parameterizing 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, a 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 capability/incapability 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.e., “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 et 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 at least one set of N inputs can be shattered. This suggests that there may be a reasonably large family of N input-label pairs that can be memorized with o(N) parameters, which is our main interest.

heading: 1.1 SUMMARY OF RESULTS
text: In this paper, we identify a mild condition satisfied by many practical datasets, and show that o(N) parameters suffice for memorizing such datasets. In order to bypass the negative result by Sontag (1997), we introduce a condition to the set of inputs, called the ∆-separateness.
Definition 1. For a set X ⊂ Rdx , we say X is ∆-separated if sup
x,x′∈X :x 6=x′ ‖x− x′‖2 < ∆× inf x,x′∈X :x 6=x′ ‖x− x′‖2.
This condition requires that the ratio of the maximum distance to the minimum distance between distinct points is bounded by ∆. Note that the condition is milder when ∆ is bigger. By Definition 1, any given finite set of (distinct) inputs is ∆-separated for some ∆, so one might ask why ∆- separateness is different from having distinct inputs in a dataset. The key difference is that even if the number of data points N grows, the ratio of the maximum to the minimum should remain bounded by ∆. Given the discrete nature of computers, there are many practical datasets that satisfy ∆-separateness, as we will see shortly. Also, this condition is more general than the minimum distance assumptions (∀i, ‖xi‖2 = 1, ∀i 6= j, ‖xi − xj‖2 ≥ ρ > 0) that are employed in existing theoretical results (Hardt and Ma, 2017; Vershynin, 2020). To see this, note that the minimum distance assumption implies 2/ρ-separateness. In our theorem statements, we will use the phrase “∆-separated set of input-label pairs” for denoting the set of inputs is ∆-separated.
In our main theorem sketched below, we prove the sufficiency of o(N) parameters for memorizing any ∆-separated set of N pairs (i.e., any ∆-separated set of N inputs with arbitrary labels) even for large ∆. More concretely, our result is of the following form: Theorem 1 (Informal). For any w ∈ ( 23 , 1], there exists aO(N
2−2w/ logN+log ∆)-layer, O(Nw+ log ∆)-parameter fully-connected network with sigmoidal or RELU activation that can memorize any ∆-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 ∆-separated set of N pairs can be memorized by a network with o(N) parameters. Here, we can check from Definition 1 that the log ∆ term does not usually dominate the depth or 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, 1, . . . , 255}) of size a× b satisfies log ∆ < (9 + 12 log(ab)) (e.g., log ∆ < 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 dataset1 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 1 improves the sufficient number of parameters for memorizing a large class of N pairs (i.e., 2O(N
w)-separated) from O(N) down to O(Nw) for any w ∈ ( 23 , 1), for deep networks. Then, it is natural to ask whether the depth increasing with N is necessary for memorization with a sub-linear number of parameters. The following existing result on the VC-dimension implies that this is indeed necessary for memorization with o(N/ logN) parameters, at least for RELU networks. Theorem [Bartlett et al. (2019)]. (Informal) For L-layer RELU networks, Ω(N/(L logN)) parameters 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, Ω(N/ logN) parameters are necessary for memorizing at least one set of N inputs with arbitrary labels. In contrast, by increasing depth with N , Theorem 1 shows that there is a large class of datasets that can be memorized with o(N/ logN) 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(N/ logN) 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 a sigmoidal or RELU activation function, O(N2/3 + log ∆) parameters (i.e., layers) suffice for memorizing any ∆-separated set of N input-label pairs.
Theorem 2 states that under 2O(N 2/3)-separateness of inputs, the network width does not necessarily have to increase with N for memorization with sub-linear parameters. Furthermore, it shows that 1http://www.image-net.org/ 2https://storage.googleapis.com/openimages/web/index.html
even a surprisingly narrow network of width 3 has a superior memorization power than a fixed-depth network, requiring only O(N2/3) parameters.
Theorems 1 and 2 show the existence of network architectures that memorize N points with o(N) parameters, under the condition of ∆-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 a nutshell, our criteria indicate that to memorize more pairs under the same budget for the number of parameters, a network must have a 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 to the number of parameters (Yamasaki, 1993; Yun et al., 2019; Vershynin, 2020), our criteria successfully incorporate with the characteristics of datasets, the number of parameters, and the architecture, which enable us to memorize ∆-separated 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.

heading: 2 RELATED WORKS

heading: 2.1 NUMBER OF PARAMETERS FOR MEMORIZATION
text: Sufficient number of parameters for memorization. Identifying the sufficient number of parameters for memorizing arbitrary N pairs has a 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 STEP3 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 limx→−∞ σ(x) or limx→∞ σ(x) exists, without any condition on inputs. The O(N) bounds on the number of hidden neurons was improved to O( √ N) 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, O(N) parameters are sufficient. Vershynin (2020) proved a similar result for STEP (or RELU) networks with an additional logarithmic factor, i.e., Õ(N) parameters are sufficient, for memorizing arbitrary {xi : ‖xi‖2 = 1}Ni=1 satisfying ‖xi − xj‖22 = Ω( log log dmax log dmin ) and N, dmax = eO(d 1/5 min) where dmax and dmin denote the maximum 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 {xi : ‖xi‖2 = 1}Ni=1 satisfying ‖xi − xj‖2 ≥ ρ for some absolute constant ρ > 0. Nguyen and Hein (2018) studied a 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, Ω(N) parameters are necessary for memorizing arbitrary
3STEP denotes the binary threshold activation function: x 7→ 1[x ≥ 0].
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-Chervonenkis (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 a single set of N inputs with arbitrary labels. Hence, it 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 Θ(N/ logN) parameters are necessary (Baum and Haussler, 1989) and sufficient (Maass, 1997) for STEP networks. Similarly, Karpinski and Macintyre (1997) proved that Ω( √ N/U) parameters are necessary for sigmoid networks of U neurons. Recently, Bartlett et al. (2019) showed that Θ(N/(L̄ logN)) parameters are necessary and sufficient for L-layer networks using any piecewise linear activation function where L̄ := 1WL ∑L `=1W` and W` denotes the number of parameters up to the `-th layer.

heading: 2.2 BENEFITS OF DEPTH IN NEURAL NETWORKS
text: 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 a 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.

heading: 3 NOTATION AND PROBLEM SETUP
text: 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 7→ max{x, 0}. For X ⊂ R, we denote bXc := {bxc : x ∈ X}. For n ∈ N and a set X , we denote (X n ) := {S ⊂ X : |S| = n} and [n] := {0, . . . , n− 1}. For x ≥ 0 and y > 0, we denote x mod y := x− y · bxy c.
Throughout this paper, we consider fully-connected feedforward networks. In particular, we consider the following setup: Given an activation function σ, we define a neural network fθ of L layers (or equivalently L − 1 hidden layers), input dimension dx, output dimension 1, and hidden layer dimensions d1, . . . , dL−1 parameterized by θ as fθ := tL−1◦σ◦· · ·◦t1◦σ◦t0. Here, t` : Rd` → Rd`+1 is an affine transformation parameterized by θ.4 We denote a neural network using an activation function σ by a “σ network.” We define the width of fθ 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 σ : R→ R is sigmoidal if the following conditions are satisfied.
• Both limx→−∞ σ(x), limx→∞ σ(x) exist and limx→−∞ σ(x) 6= limx→∞ σ(x).
• There exists z ∈ R such that σ is continuously differentiable at z and σ′(z) 6= 0.
A class of sigmoidal functions covers many activation functions including sigmoid, tanh, hard tanh, etc.5 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.6
Lastly, we formally define the memorization as follows. Definition 3. Given C, dx ∈ N, a set of inputs X ⊂ Rdx , a label function y : X → [C], and a neural network fθ : Rdx → R parameterized by θ, we say fθ can memorize {(x, y(x)) : x ∈ X} in dx dimension with C classes if for any ε > 0, there exists θ such that |fθ(x)− y(x)| ≤ ε for all x ∈ X .
4We set d0 := dx and dL := 1. 5hard tanh activation function: x 7→ −1[x ≤ −1] + x · 1[−1 < x ≤ 1] + 1[x > 1]. 6hard tanh(x) = RELU(x+ 1)− RELU(x− 1)− 1 = RELU ( 2− RELU(1− x) ) − 1
Definition 3 defines the memorizability as the ability of a network fθ to fit a set of input-label pairs. While existing results often define memorization only for the binary labels, we consider arbitrary C classes, and prove our results for general multi-class classification problems. We often write “fθ can memorize arbitrary N pairs” without “in dx dimension with C classes” throughout the paper.

heading: 4 MAIN RESULTS

heading: 4.1 MEMORIZATION VIA SUB-LINEAR PARAMETERS
text: Efficacy of depth for memorization. Now, we are ready to introduce our main theorem on memorizing N pairs with o(N) parameters. The proof of Theorem 1 is presented in Section 5.
Theorem 1. For any C,N, dx ∈ N, for any w ∈ [2/3, 1], for any ∆ ≥ 1, for any sigmoidal activation function σ, there exists a σ network fθ of O ( log dx + log ∆ + N2−2w 1+(1.5w−1) logN logC ) hidden layers
and O ( dx + log ∆ +N w +N1−w/2 logC )
parameters such that fθ can memorize any ∆-separated set of N pairs in dx dimension with C classes.
Note that Theorem 1 covers w = 2/3 which is not included in its informal version presented in Section 1.1. However, we could only achieve O(N2/3) parameters at w = 2/3 as the logN term 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 we described in Section 3.
In Theorem 1, ∆ only incursO(log ∆) 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 ∆ is small for random inputs. For example, a set of dx-dimensional i.i.d. standard normal random vectors of size N satisfies log ∆ = O( 1dx log(N/ √ δ)) with probability at least 1− δ (see Section C). Hence, the ∆-separateness condition is often negligible.
Suppose that dx and C are treated as constants, as also assumed in existing results. Then, Theorem 1 implies that if log ∆ = O(Nw) for some w < 1, then Θ(Nw) (i.e., sub-linear to N ) parameters are sufficient for sigmoidal or RELU networks to memorize arbitrary ∆-separated set of N pairs. Furthermore, if log ∆ ≤ O(N2−2w/logN) and w ∈ ( 23 , 1), then the network construction in Theorem 1 has O(N2−2w/logN) layers and O(Nw) parameters. Note that the condition log ∆ ≤ O(N2−2w/logN) is very loose for many practical datasets, especially for those with huge N . Combined with the lower bound Ω(N/ logN) on the necessary number of parameters for RELU networks of constant depth (Bartlett et al., 2019), Theorem 1 implies that depth growing in N is necessary and sufficient for memorizing a large class (i.e., ∆-separated) of N pairs with o(N/ logN) 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) as stated in the following theorem. The proof of Theorem 2 is presented in Section F.
Theorem 2. For any C,N, dx ∈ N, for any ∆ ≥ 1, for any sigmoidal activation function σ, a σ network of Θ(N2/3 logC) hidden layers and width 3 can memorize any ∆-separated set of N pairs in dx 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 dx. This is in contrast with the recent universal approximation results that width at least dx + 1 is necessary for approximating functions having dx-dimensional domain (Lu et al., 2017; Hanin and Sellke, 2017; Johnson, 2019; Park et al., 2020). The main difference follows from the fundamental difference in the two approximation problems, i.e., approximating a function at 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 input-label pairs in dx-dimension can be easily translated into memorizing finite input-label pairs in one-dimension. In other words, the dimensionality (dx) of inputs is not very important as long as they can be translated to distinct scalar values. In contrast, there is no “natural” way to map design an injection from dx-dimensional unit cube to lower dimension. Namely, to not loose the “information” from inputs, width dx for preserving inputs is necessary. Therefore, function approximation in general cannot be done with width independent of dx.
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 d1/εe classes. Here, each class c ∈ {0, 1, . . . , d1/εe} corresponds to the target value c · ε. Hence, the regression problem can also be solved within ε error with o(N) parameters, where the sufficient number of layers and the sufficient number of parameters are identical to the numbers in Theorem 1 and Theorem 2 with the replacement of logC with log(1/ε).
Relation with benefits of depth in neural networks. Our observation that deeper RELU networks have more memorization power is closely related to the recent studies on the benefits of depth in neural networks (Telgarsky, 2016; Eldan and Shamir, 2016; Lin et al., 2017; Arora et al., 2018; Yarotsky, 2018; Chatziafratis et al., 2020a;b). While our 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 on 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).

heading: 4.2 GENERIC CRITERIA FOR IDENTIFYING MEMORIZATION POWER
text: While Theorem 1 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 σ, let fθ be a σ network of L hidden layers having d` neurons at the `-th hidden layer. Then, for any C,N, dx ∈ N and ∆ ≥ 1, fθ can memorize any ∆-separated set of N pairs in dx dimension with C classes if the following statement holds:
There exist 0 < L1 < · · · < LK < L for some 2 ≤ K ≤ logN satisfying conditions 1–4 below.
1. d` ≥ 3 for all ` ≤ LK and d` ≥ 7 for all LK < `. 2. ∏L1 `=1b(d` + 1)/2c ≥ ∆ √ 2πdx.
3. ∑Li Li−1+1 (d` − 2) ≥ 2i+3 for all 1 < i ≤ K − 1.
4. 2K · (∑LK
`=LK−1+1 (d` − 2)
) · ⌊ (L− LK − 1)/dlogCe ⌋ − 4 ≥ N2.
Our criteria in Theorem 3 require that the layers of the network can be “partitioned” into have K + 1 distinct parts characterized by L1, . . . , LK 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 d` ≥ 7 for LK < ` does not contradict Theorem 2 as we highly optimize the network architecture to fit in width 3 for Theorem 2, while we provide generic criteria here.
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 a similar budget for parameters, due to the product form ∏L1 `=1b(d` + 1)/2c. Nevertheless, the architecture of the first L1 hidden layers is not very critical as only log ∆ + 12 log(2πdx) layers are sufficient even with width 3 (e.g., log ∆ < 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 one requires doubling hidden neurons from the (L1 + 1)-th hidden layer to the LK−1-th hidden layer. Nevertheless, this doubling hidden neurons would make the LHS of the last condition double as well.
The last condition is simple. As we explained, 2K is approximately proportional to the number of hidden neurons from the (L1 + 1)-th hidden layer to the LK−1-th hidden layer. The second term in the LHS of the last condition ∑LK `=LK−1+1
(d` − 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 3 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 RELU networks to memorize with o(N) parameters (Bartlett et al., 2019).
Now, we describe how to show memorization with o(N) parameters using our criteria. For simplicity, consider the network with the minimum width stated in the first condition, i.e., d` = 3 for all ` ≤ LK and d` = 7 for all LK < `. As we explained, the second conditions can be easily satisfied. For the third condition, consider choosing K = log(N2/3), then Θ(N2/3) hidden neurons (i.e., Θ(N2/3) hidden layers) would be sufficient, i.e., LK−1 − L1 = Θ(N2/3). Likewise, we choose remaining Li to satisfy LK − LK−1 = Θ(N2/3) and L− LK = Θ(N2/3). Then, it naturally satisfy the last condition while using only Θ(N2/3) parameters.

heading: 5 PROOF OF THEOREM 1
text: In this section, we give a constructive proof of Theorem 1: We design a σ network which can memorize N inputs in dx dimension with C classes using only o(N) parameters. We note that the proofs of Theorem 2 and Theorem 3 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 4 is presented in Section E.1.
Lemma 4. For any C, V ∈ N and p ∈ [1/2, 1], there exists a σ network fθ of O (
V 1−p 1+(p−0.5) log V )
hidden layers and O(V p + V 1/2 logC) parameters such that fθ can memorize any X ∈ (R V ) with C classes satisfying bXc = [V ].
Roughly speaking, Lemma 4 states the following: Suppose that the V inputs are scalar and wellseparated, in the sense that exactly one input falls into each interval [i, i + 1). Then, such wellseparated inputs can be mapped to the corresponding labels using only O(V 1/2) parameters (with p = 1/2). Thus, what remains is to build a network mapping N arbitrary inputs to some wellseparated set bounded by some V = o(N2), again using o(N) parameters.
Projecting input vectors to scalar values. Now, we introduce our network mapping ∆-separated set of N inputs to some Z satisfying bZc ∈ ( [V ] N ) . 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 ∆-separated X ∈ (Rdx N ) , there exist v ∈ Rdx , b ∈ R such that ⌊ {v>x+ b : x ∈
X} ⌋ ∈ (
[O(N2∆d1/2x )] N
) .
Lemma 5 states that any ∆-separated N vectors can be mapped to some well-separated scalar values bounded by O(N2∆d1/2x ) using a simple projection using O(dx) parameters. Note that the direct combination of Lemma 4 and Lemma 5 gives us a σ network of O(N∆1/2d1/4x ) parameters which can memorize any ∆-separated N pairs. However, this combination is limited in at least two sense: The required number of parameters (1) has ∆1/2d1/4x multiplicative factor and (2) is not sub-linear to N . In what follows, we introduce our techniques for resolving these two issues.
Reducing upper bound to O(N2). First, we introduce the following lemma for improving the ∆1/2d 1/4 x multiplicative factor in the number of parameters to O(log ∆ + log dx) additional parameters. The proof of Lemma 6 is presented in Section E.3.
Lemma 6. For any X ∈ (R N ) such that bXc ∈ ( [K] N ) for some K ∈ N, there exists a σ network f of 1
hidden layer and width 3 such that bf(X )c ∈ (
[T ] N
) where T := max {⌈ K/2 ⌉ , bN2/4 + 1c } .
From Lemma 6, a network of O(log ∆ + log dx) hidden layers and width 3 can decrease the upper bound O(N2∆d1/2x ) to bN2/4 + 1c, which enables us to drop the dependence of ∆d1/2x on the upper bound using O(log ∆ + log dx) 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., no two inputs are mapped into the same interval) by some simple network of a small number of parameters. For example, we construct f in Lemma 6 as
f(x) :=
{ x if x ∈ [ 0, T ) x+ b mod T if x ∈ [ T,K
) (1) for some b ∈ [T ]. However, if T is not large enough compared to N (i.e., T < bN2/4 + 1c), then our network (1) cannot avoid the collision between inputs, i.e., b ∈ [T ] satisfying f(bXc) ∈ ( [T ] N )
may not exist. Hence, combining Lemmas 4–6 only gives us a σ network of O(N + log ∆ + log dx) parameters which can memorize any ∆-separated N pairs, i.e., the number of parameters is not sub-linear to N .
Reducing upper bound to o(N2). To resolve this issue, we further decrease the upper bound using the following lemma. The proof of Lemma 7 is presented in Section E.4.
Lemma 7. For any X ∈ (R N ) such that bXc ∈ ( [K] N ) for some K ∈ N, there exists a σ network f of 1
hidden layer and width O ( N2/K ) such that bf(X )c ∈ ( [T ] N ) where T := max {⌈ K/2 ⌉ , N } .
The network in Lemma 7 can reduce the upper bound by approximately half, beyond bN2/4 + 1c; however, the required number of parameters will be doubled if both the current upper bound K decreases by half. Hence, in order to decrease the upper bound from O(N2) to V = o(N2) using Θ(log(N2/V )) applications of Lemma 7, we need Θ(log(N2/V )) layers and Θ(N2/V ) parameters. Here, we construct each application of Lemma 7 using two hidden layers: one hidden layer of Θ(N2/K) hidden neurons for implementing the function and the other hidden layer of one hidden neuron for the output.
Deriving Theorem 1. Now, we choose V = Θ(N2−w) for some w ∈ [ 23 , 1]. Then, from Lemmas 5–7, O(log dx + log ∆ + logN) hidden layers and O(dx + log ∆ + Nw) parameters suffice for mapping any ∆-separated set of sizeN to someZ satisfying bZc ∈ ( [V ] N ) . Finally, from Lemma 4 and
choosing p = w2−w , additionalO (
N2−2w 1+(1.5w−1) logN logC )
hidden layers andO(Nw+N1−w/2 logC) parameters suffice for mapping Z to its labels. This completes the proof of Theorem 1.

heading: 6 EXPERIMENTS
text: 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 a similar number of parameters? For the experiments, we use residual networks (He et 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 of channels (c) and the number of residual blocks (b).

heading: 6.1 DEPTH-WIDTH TRADE-OFF IN MEMORIZATION
text: We verify the memorization power of different network architectures having a similar number of parameters. Figure 1 illustrates training and test accuracy of five different architectures with approximately 50000 parameters for 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 a 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. In Figure 1b, as the depth increases, the test accuracy also increases for the SVHN dataset. In contrast, the test
accuracy decreases for the CIFAR-10 dataset as the depth increases in Figure 1a. 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 et al., 2019; Nakkiran et al., 2020) that more expressive power can both hurt/improve the generalization.
In addition, this observation can provide guidance on the design of network architectures in applications 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 a video by neural networks and send the compressed video and the decoder network (Yeo et al., 2018). Here, the corresponding decoder is often trained only for the video to send; hence, only the training accuracy/loss matters while the decoder’s number of parameters should also be small for the traffic.

heading: 6.2 EFFECT OF WIDTH AND DEPTH
text: In this section, we observe the effect of depth and width by varying both. Figure 2 reports the training and test accuracy for the CIFAR-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× 32 successfully memorize (i.e., over 99% training accuracy). This size is much narrower than modern network architectures, e.g., ResNet-18 has 64 channels at the first hidden layer (He et al., 2016). On the other hand, too narrow network (e.g., 5-channels) fail to memorize. This result does not contradict with Theorem 2 as the test of memorization in experiments/practice involves the stochastic gradient descent. We note that similar phenomenons are observed for the SVHN dataset.
Furthermore, once the network memorize, we 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).

heading: 7 CONCLUSION
text: In this paper, we prove that Θ(N2/3) parameters are sufficient for memorizing arbitraryN input-label pairs under the mild ∆-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 1 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 of networks. Finally, we empirically confirm our theoretical results.

heading: A EXPERIMENTAL SETUP
text: 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, a convolutional layer and RELU maps a 3-channel input image to a c-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 x 7→ RELU(CONV ◦RELU ◦CONV(x) +x) while preserving the number of channels and the size of feature map. Finally, we apply an average pooling layer and a fully-connected layer. We train the model for 5× 105 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× 105-th iteration and the 3.5× 105-th iteration by a multiplicative factor 0.1. All presented results are averaged over three independent trials.

heading: B TRAINING AND TEST ACCURACY FOR SVHN DATASET

heading: C ∆-SEPARATENESS OF GAUSSIAN RANDOM VECTORS
text: While we mentioned in Section 1.1 that digital nature of data enables the ∆-separateness of inputs with small ∆, random inputs are also ∆-separated with small ∆ with high probability. In particular, we prove the following lemma. Lemma 8. For any dx ∈ N, consider a set of N vectors X = {x1, . . . , xN} ⊂ Rdx where each entry of xi is drawn from the i.i.d. standard normal distribution. Then, for any δ > 0, X is(
(N/ √ δ)2/dx √ 3e+ 5edx ln(N/ √ δ) ) -separated with probability at least 1− δ.
Lemma 8 implies that Theorem 1 and Theorem 2 can be successfully applied to random Gaussian input vectors as the O ( (N/ √ δ)2/dx √ ln(N/ √ δ) ) -separateness condition in Lemma 8 is much
weaker than our 2O(N 2/3)-separateness condition for memorization with o(N) parameters.
Proof of Lemma 8. To begin with, we first prove that for i 6= j, the following bound holds:
P
(√ 2
e · ( N√
δ
)−2/dx ≤ 1√
dx ‖xi − xj‖2 ≤
√ 6 + 10
dx ln N√ δ
)
= P ( 2 e · ( N√
δ )−4/dx ≤ 1 dx ‖xi − xj‖22 ≤ 6 + 10 dx ln N√ δ ) = P ( 2 e · ( N√
δ )−4/dx ≤ 2 dx X ≤ 6 + 10 dx ln N√ δ ) = 1− P ( 2 e · ( N√
δ
)−4/dx > 2
dx X
) − P ( 2
dx X > 6 +
10 dx ln N√ δ ) = 1− P ( 1 e · ( N√
δ
)−4/dx · dx > X ) − P ( X > ( 3 + 5
dx ln N√ δ
) · dx )
≥ 1− ( 1 e · ( N√
δ
)−4/dx e 1− 1e ·( N√ δ )−4/dx )dx/2 − (( 3 + 5
dx ln N√ δ
) e−2 ( N√
δ )−5/dx)dx/2 = 1− δ N2 · ( e − 1e ·( N√ δ )−4/dx )dx/2 − δ N2 · (( 3 + 5 dx ln N√ δ ) e−2 ( N√ δ )−1/dx)dx/2
≥ 1− δ N2 − δ N2 ·  3 e2N1/dx + 5 e2 · ln ( N√ δ )1/dx( N√ δ )1/dx dx/2
≥ 1− δ N2 − δ N2 · ( 3 e2 + 5 e3 )dx/2 ≥ 1− δ
N2 − δ N2 = 1− 2δ N2
(2)
where X denotes a chi-square random variable with dx degrees of freedom. For the first inequality in (2), we use the inequalities
P(X < z · dx) ≤ inf t>0 E[e−tX ] e−t(z·dx) = inf t>0 (1 + 2t)−dx/2 e−t(z·dx) = (ze1−z)dx/2 for 0 < z < 1
P(X > z · dx) ≤ inf t>0 E[etX ] et(z·dx) = inf 0<t<1/2 (1− 2t)−dx/2 et(z·dx) = (ze1−z)dx/2 for z > 1
which directly follow from the Chernoff bound for the chi-square distribution. For the third inequality in (2), we use the fact that maxx>0(lnx)/x = 1/e and N ≥ 1. For the last inequality in (2), we use 3 e2 + 5 e3 < 1.
Then, X is ( (N/ √ δ)2/dx √ 3e+ 5edx ln(N/ √ δ) )
-separated with probability at least 1 − δ as the following bound holds:
P
(√ 2
e δ1/dxN−2/dx ≤ 1√ dx ‖xi − xj‖2 ≤
√ 6 + 10
dx ln N√ δ , ∀i 6= j
)
= 1− P ( ∃i 6= j s.t. ‖xi − xj‖2 > √ 6 + 10
dx ln N√ δ
or ‖xi − xj‖2 < √ 2
e δ1/dxN−2/dx
)
≥ 1− ∑ i 6=j P
( ‖xi − xj‖2 > √ 6 + 10
dx ln N√ δ
or ‖xi − xj‖2 < √ 2
e δ1/dxN−2/dx
)
= 1− ∑ i 6=j
( 1− P (√ 2
e δ1/dxN−2/dx ≤ 1√ dx ‖xi − xj‖2 ≤
√ 6 + 10
dx ln N√ δ
))
≥ 1− N(N − 1) 2 × 2δ N2 ≥ 1− δ
where the first inequality follows from the union bound and the second inequality follows from (2). This completes the proof of Lemma 8.

heading: D MAIN PROOF IDEA: MEMORIZATION USING STEP AND ID

heading: D.1 MAIN IDEA
text: In the proofs of Theorem 1, Theorem 2, and Theorem 3, we use each sigmoidal activation for approximating either the identity function (ID : x 7→ x) or the binary step function (STEP : x 7→ 1[x ≥ 0]). 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).

heading: D.2 TOOLS
text: We present the following claims important for the proofs. In particular, Claim 9 and Claim 10 guide how to approximate STEP and ID by a single sigmoidal neuron. Claim 9 [Kidger and Lyons (2020, Lemma 4.1)]. For any sigmoidal activation function σ, for any bounded interval I ⊂ R for any ε > 0, there exist a, b, c, d ∈ R such that |a ·σ(c ·x+d)+b−x| < ε for all x ∈ I. Claim 10. For any sigmoidal activation function σ, for any ε, δ > 0, there exist a, b, c ∈ R such that |a · σ(c · x) + b− 1[x ≥ 0]| < ε for all x /∈ [− δ, δ].
Proof of Claim 10. We assume that α := limx→−∞ σ(x) < limx→∞ σ(x) =: β where the case that β < α can be proved in a similar mannerwdd. From the definition of α, β, there exists k > 0 such that |σ(x) − α| < (β − α)ε if x < −k and |σ(x) − β| < (β − α)ε if x > k. Then, choosing a = 1β−α , b = − α β−α , and c = k δ completes the proof of Claim 10.
Claim 11. For any a, x ∈ R such that a 6= 0, for any b ∈ N, it holds that ⌈ x a·b ⌉ = ⌈ dx/ae b ⌉ .
Proof of Claim 11. It trivially holds that d xa·be ≤ d dx/ae b e. Now, we show a contradiction if d x a·be < d dx/aeb e. Suppose that d x a·be < d dx/ae b e. Then, there exists an integer m such that
x a · b ≤ m < dx/ae b and hence,
x a ≤ ⌈x a ⌉ ≤ b ·m < ⌈x a ⌉ which leads to a contradiction. This completes the proof of Claim 11.

heading: D.3 TRANSFORMING STEP+ID NETWORK TO SIGMOIDAL NETWORK
text: In this section, we describe how to transform a 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 ε > 0, for any sigmoidal activation function σ, there exists a σ network g having the same architecture with fθ such that |f(x)− g(x)| < ε for all x ∈ X .
Then, the construction in Lemma 12 enables us to construct STEP + ID networks instead of networks using a sigmoidal activation function for proving Theorem 1, Theorem 2, and Theorem 3.
Proof of Lemma 12. Without loss of generality, we first assume that for any STEP + ID network h, in the evaluation of h(x), all inputs to STEP neurons (i.e., 1[x ≥ 0]) is non-zero for all x ∈ X . This assumption can be easily satisfied by adding some small bias to the inputs of STEP neurons where such a bias alwasy exists since |X | <∞. Furthermore, introducing this assumption does not change h(x) for all x ∈ X Now, we describe our construction of g. Let δ > 0 be a number satisfying that the absolute value of all inputs to STEP neurons in the evaluation of f(x) for all x ∈ X is at least δ. Such δ always exists due to the assumption we made. Let L be the number of hidden layers in f . Starting from f , we
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 gL be a network identical to f except for its L-th hidden layer consisting of σ neurons approximating ID and STEP in f . Here, we accurately approximate ID and STEP neurons by σ using Claim 9 and Claim 10 so that |gL(x)− f(x)| < ε/L for all x ∈ X . Note that such approximation always exists due to the existence of δ > 0. Now, let gL−1 be a network identical to fL except for its (L − 1)-th hidden layer consisting of σ neurons approximating ID and STEP of gL. Here, we also accurately approximate ID and STEP neurons by σ using Claim 9 and Claim 10 so that |gL(x)− gL−1(x)| < ε/L for all x ∈ X . If we repeat this procedure until replacing the first hidden layer, then g := g1 would be the desired network satisfying that |f(x) − g(x)| < ε for all x ∈ X . This completes the proof of Lemma 12.

heading: E PROOF OF LEMMAS FOR THEOREM 1
text: 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 σ networks using Lemma 12.

heading: E.1 PROOF OF LEMMA 4
text: To prove Lemma 4, we introduce the following lemma. We note that Lemma 13 follows the construction for proving VC-dimension lower bound of RELU networks (Bartlett et al., 2019). The proof of Lemma 13 is presented in Section H.4.
Lemma 13. For any A,B,D,K,R ∈ N such that AB ≥ K, there exists a STEP + ID network fθ of 2dBDR e + 2 hidden layers and 4A + ( (2R + 5)2R + 2R2 + 8R + 7 ) dBDR e − R2
R − R2 + 3 parameters satisfying the following property: For any finite set X ⊂ [0,K), for any y : [K]→ [2D], there exists θ such that fθ(x) = y(bxc) for all x ∈ X .
By choosing K ← V , A ← Θ(V p), B ← Θ(V 1−p), R ← 1 + (2p − 1) log V , and D ← dlogCe in Lemma 13, there exists a STEP + ID network of O ( V 1−p 1+(p−0.5) log V logC )
hidden layers and O(V p) parameters which can memorize any X ⊂ R of size V with C classes satisfying bXc = [V ]. Combining this with Lemma 12 completes the proof of Lemma 4.

heading: E.2 PROOF OF LEMMA 5
text: Since the proof is trivial when dx = 1, we consider dx ≥ 2. To this end, we first project all x ∈ X to u>x ∈ R by choosing some unit vector u ∈ Rdx so that
max{x,x′}∈(X2) |u>(x− x′)| min{x,x′}∈(X2) |u>(x− x′)| < N2∆
√ πdx
8 . (3)
Such a unit vector u always exists due to the following lemma. The proof of Lemma 14 is presented in Section H.1.
Lemma 14. For any N, dx ∈ N, for any X ∈ (Rdx N ) , there exists a unit vector u ∈ Rdx such that√
8 πdx 1 N2 ‖x− x ′‖2 ≤ |u>(x− x′)| ≤ ‖x− x′‖2 for all x, x′ ∈ X .
Finally, we construct the desired map by
x 7→ u >x−min{u>x : x ∈ X1}
min{x,x′}∈(X12 ) |u>(x− x′)|
=: v>x+ b
for some v ∈ Rdx and b ∈ R so that b{v>x+ b : x ∈ X}c ∈ ([dN2∆√πdx/8e]
N
) . This completes the
proof of Lemma 4.

heading: E.3 PROOF OF LEMMA 6
text: To prove Lemma 6, we introduce the following lemma. The proof of Lemma 15 is presented in Section H.2.
Lemma 15. For anyN,K, d ∈ N, for anyX such that bXc ∈ (
[K] N
) , there exists a STEP+ID network
f of 1 hidden layer and width d such that bf(X )c ∈ (
[T ] N
) where T := max {⌈ K b(d+1)/2c ⌉ , bN 2 4 +1c } .
From Lemma 15, one can observe that a STEP + ID network of 1 hidden layer consisting of 3 hidden neuron which can map any Z such that bZc ∈ ( [K] N ) to Z ′ such that bZ ′c ∈ ( [T ] N ) where
T := max {⌈
K b(d+1)/2c
⌉ , bN 2 4 + 1c }
. Combining Lemma 15 and Lemma 12 completes the proof of Lemma 6.

heading: E.4 PROOF OF LEMMA 7
text: In the compression 2 step, we further improve the bound U := bN 2
4 + 1c on the hidden feature values to V = Θ(N2−w). Namely, we map X3 to X4 such that bX4c ∈ ( [V ] N ) . To construct such a mapping, we introduce the following lemma. The proof of Lemma 16 is presented in Section H.3. Lemma 16. For any N,K,L, d1, . . . , dL ∈ N such that N < K and d` ≥ 3 for all `, for any X such that bXc ∈ ( [K] N ) , there exists a STEP + ID network f of L hidden layers having d` neurons at
the `-th hidden layer such that bf(X )c ∈ (
[T ] N
) where T := min { K,max { N × dNC e, d K 2 e }} and
C := b 12 + 1 2 ∑L `=1(d` − 2)c.
From Lemma 16, a STEP + ID network f of one hidden layer having Θ ( N2
K
) hidden neurons can
map any X such that bXc ∈ (
[K] N
) to f(X ) such that bf(X )c = ( [T ] N ) where T := max{N, dK2 e}.
Combining this and Lemma 12 completes the proof of Lemma 7.

heading: F PROOF OF THEOREM 2
text: In this proof, we construct a STEP + ID network and transform it to a σ network using Lemma 12, as in the proof of Theorem 1 in Section 5 and Section E. In particular, Theorem 2 is 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 ≥ K, there exists a STEP + ID network fθ of A + (2D + 1)B hidden layers and width 3 satisfying the following property: For any finite set X ∈ [0,K), for any y : [K]→ [2D], there exists θ such that fθ(x) = y(bxc).
From Lemma 14, Lemma 15, and Claim 11, a STEP + ID network of dlog(∆ √
2πdx)e hidden layers and width 3 can map a ∆-separated set of inputs X1 to X2 such that bX2c ∈ ( [U ] N ) where U := bN 2 4 +1c. From Lemma 16, a STEP+ID network of ∑dlog(U/V )e−1 i=1 (⌈ 2N bU/(2iN)c ⌉ −1 ) + ⌈ 2N bV/Nc ⌉ −1
hidden layers and width 3 can map X2 to X3 such that bX3c ∈ ( [V ] N ) for some N ≤ V ≤ U . Here, we will choose V = Θ(N4/3). Finally, from Lemma 17, for any A,B ∈ N such that AB ≥ V , a STEP + ID network of A+ (2D + 1)B hidden layers and width 3 can map X3 to their labels where D := dlogCe. We will choose A,B = Θ(N2/3) to satisfy AB ≥ V = Θ(N4/3). Hence, for any A,B, V ∈ N such that N ≤ V ≤ U and AB ≥ V , a STEP + ID network of dlog(∆ √ 2πdx)e + ∑dlog(U/V )e−1 i=1 (⌈ 2N bU/(2iN)c ⌉ − 1 ) + ⌈ 2N bV/Nc ⌉ + A + (2D + 1)B − 1 hidden layers and width 3 can memorize arbitrary ∆-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.
Finally, substituting V ← dN4/3e, A ← d √ (2D + 1)V e, and B ← d √ V/(2D + 1)e and using Lemma 12 result in the statement of Theorem 2. This completes the proof of Theorem 2.

heading: G PROOF OF THEOREM 3
text: The proof of Theorem 3 have the same structure of the proof of Theorem 1 consisting of four steps: projection, compression 1, compression 2, and learning. In particular, we construct a STEP + ID network and use Lemma 12 as in the proofs of Theorem 1 and Theorem 2.
For the network construction, we divide the function of fθ into four disjoint parts, as 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 L1 hidden layers decreases the upper bound on scalar values to O(N2). The third part corresponds to the next LK−1 − L1 hidden layers further decreases the upper bound to o(N2). 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 bX2c ∈ ([dN2∆√πdx/8e]
N
) . Note
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 X2 to X3 such that bX3c ∈ ( [bN2/4+1c]
N
) since
L1∏ `=1 ⌊d` + 1 2 ⌋ ≥ ∆ √ 2πdx ⇒ L1∏ `=1 ⌊d` + 1 2 ⌋ ≥ N2∆ √ πdx/8 N2/4
⇒N 2
4 ≥ N2∆ √ πdx/8∏L1
`=1b(d` + 1)/2c ⇒ ⌊N2 4 + 1 ⌋ ≥ N2∆ √ πdx/8∏L1
`=1b(d` + 1)/2c ⇒ ⌊N2 4 + 1 ⌋ ≥ ⌈ N2∆√πdx/8∏L1
`=1b(d` + 1)/2c
⌉ .
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 X3 to X4 such that bX4c ∈
( [dU/2K−2e]
N ) since the third condition holds and
Li∑ `=Li−1+1 (d` − 2) ≥ 2i+3 ⇒ 1 2 Li∑ `=Li−1+1 (d` − 2) ≥ 2i+2
⇒ ⌊1
2 +
1
2 Li∑ `=Li−1+1 (d` − 2) ⌋ ≥ 2i+2
⇒ N⌊ 1 2 + 1 2 ∑Li `=Li−1+1 (d` − 2) ⌋ ≤ N 2i+2
⇒ ⌈ N⌊
1 2 + 1 2 ∑Li `=Li−1+1 (d` − 2) ⌋⌉ ≤ N 2i+1
⇒N × ⌈ N⌊
1 2 + 1 2 ∑Li `=Li−1+1 (d` − 2) ⌋⌉ ≤ N2/4 2i−1
⇒N × ⌈ N⌊
1 2 + 1 2 ∑Li `=Li−1+1 (d` − 2) ⌋⌉ ≤ bN2/4 + 1c 2i−1
⇒N × ⌈ N⌊
1 2 + 1 2 ∑Li `=Li−1+1 (d` − 2) ⌋⌉ ≤ ⌈bN2/4 + 1c 2i−1 ⌉
where we use the inequality dae ≤ 2a for a ≥ 1/2 and the assumption K ≤ logN , i.e., N/2i+1 ≥ 1 for i ≤ logN − 1. Here, we also utilize Claim 11 for the sequential application of Lemma 16. Now, we reinterpret the last condition as follows.
2K ·  LK∑ `=LK−1+1 (d` − 2)  · ⌊(L− LK − 1)/dlogCe⌋ ≥ N2 − 4 ⇒
 LK∑ `=LK−1+1 (d` − 2)  · ⌊(L− LK − 1)/dlogCe⌋ ≥ N2/4 + 1 2K−2
⇒  LK∑ `=LK−1+1 (d` − 2)  · ⌊(L− LK − 1)/dlogCe⌋ ≥ ⌈bN2/4 + 1c 2K−2 ⌉
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, d1, . . . , dL ∈ N, suppose that there exist 0 < L′ < L and rL′+1, . . . , rL−1 ∈ N satisfying that for rL′ = rL = 1 L′∑
`=1
(d` − 2)  · ⌊∑L−1`=L′+1 r` D ⌋ ≥ K and 2r` + r` + r`−1 + 3 ≤ d` for all L′ + 1 ≤ ` ≤ L.
Then, there exists a STEP + ID network fθ of L hidden layers having d` hidden neurons at the `-th hidden layer such that for any finite X ⊂ [0,K), for any y : [K] → [2D], there exists θ satisfying fθ(x) = y(bxc) for all x ∈ X .
Choose K ← dU/2K−2e and r` = 1 for all ` in Lemma 18 completes our construction of the STEP + ID network. Note that we utilize the condition that d` ≥ 7 for all LK < ` here. Using Lemma 12 completes the proof of Theorem 3.

heading: H PROOFS OF TECHNICAL LEMMAS

heading: H.1 PROOF OF LEMMA 14
text: Since the upper bound holds for any unit vector u ∈ Rdx , we focus on the lower bound. In addition, if N = 1, the result of Lemma 14 trivially holds. Hence, we assume N ≥ 2, i.e., √ 8 πdx 1 N2 < 1. In this proof, we show that given any vector v ∈ Rdx such that ‖v‖2 6= 0, a random unit vector u ∈ Rdx from the uniform distribution satisfies that
P ( |u>v| ‖v‖2 < √ 8 πdx 1 N2 ) < 2 N2 . (4)
This implies that there exists a unit vector u ∈ Rdx such that √
8 πdx 1 N2 ‖x − x ′‖2 ≤ |u>(x − x′)| for all x, x′ ∈ X , due to the following union bound: for V = { x− x′ : {x, x′} ∈ (X 2 ) , x ≤ x′ } for some total order ≤ on X ,
P (⋃ v∈V { |u>v| ‖v‖2 < √ 8 πdx 1 N2 }) ≤ ∑ v∈V P ( |u>v| ‖v‖2 < √ 8 πdx 1 N2 ) < N(N − 1) 2 × 2 N2 < 1.
Now we prove (4). To begin with, we show that the following equality holds for any v ∈ R: P ( |u>v| ‖v‖2 < √ 8 πdx 1 N2 ) = P ( |u1| < √ 8 πdx 1 N2 ) . Here, the equality follows from choosing v/‖v‖2 = (1, 0, . . . , 0) using the symmetry. Furthermore, P ( |u1| < √ 8 πdx 1 N2 ) can be bounded by
P ( |u1| < √ 8
πdx
1
N2
) = P ( 0 < u1 < √ 8
πdx
1
N2
) + P ( − √ 8
πdx
1
N2 < u1 ≤ 0 ) = 2× P ( 0 < u1 < √ 8
πdx
1
N2 ) = 2
Areadx(1) × ∫ π 2 arccos (√
8 πdx 1 N2
) Areadx−1(sinφ)dφ
= 2× Areadx−1(1) Areadx(1)
× ∫ π 2
arccos (√
8 πdx 1 N2
) sindx−2 φdφ
= 2× 2π
dx−1 2 /Γ(dx−12 )
2π dx 2 /Γ(dx2 )
× ∫ π 2
arccos (√
8 πdx 1 N2
) sindx−2 φdφ
< 2× √ dx 2π × ∫ π 2 arccos (√
8 πdx 1 N2
) 1dφ
= √ 2dx π ( π 2 − arccos (√ 8
πdx
1
N2 )) = √ 2dx π arcsin (√ 8
πdx
1
N2 ) ≤ √
2dx π × π 2 × √ 8
πdx
1
N2 =
2
N2
where Aread(r) := 2π d 2 rd−1/Γ ( d 2 ) denotes the surface area of a hypersphere of radius r in Rd and Γ(x) denotes the gamma function. Here, the second equality follows from the symmetry and P(u1 = 0) = 0. The first inequality follows from sinφ ≤ 1 and Γ( dx2 ) Γ( dx−12 ) < √ dx 2 from the Gautschi’s inequality (see Lemma 19). The second inequality follows from φ ≤ π2 sinφ for 0 ≤ φ ≤ π 2 . This completes the proof of Lemma 14.
Lemma 19 [Gautschi’s inequality (Gautschi, 1959)]. For any x > 0, for any s ∈ (0, 1),
x1−s < Γ(x+ 1)
Γ(x+ s) < (x+ 1)1−s.

heading: H.2 PROOF OF LEMMA 15
text: In this proof, we assume thatK > N2/4 and T = ⌈
K b(d+1)/2c
⌉ where other cases trivially follow from
this case. To begin with, we first define a network fb(x) : [0,K)→ [0, T ) for b = (bi)b(d−1)/2ci=1 ∈ [T ]b(d−1)/2c as
fb(x) :=  x if x < T x+ b1 mod T if T ≤ x < 2T x+ b2 mod T if 2T ≤ x < 3T
... x+ bb(d−1)/2c mod T if bd−12 cT ≤ x
= x− T × 1[x ≥ T ] + b(d−1)/2c∑
i=1 (bi − i−1∑ j=1 bj ) × 1[x ≥ iT ]− T × 1[x+ bi ≥ (i+ 1)T ]  . (5)
One can easily observe that fb can be implemented by a STEP + ID network of 1 hidden layer and width d as T × 1[x ≥ T ] in (5) can be absorbed into ( bi − ∑i−1 j=1 bj ) × 1[x ≥ iT ] in (5) for i = 1.
Now, we show that if T > N2/4, then there exist b ∈ [T ]b(d−1)/2c such that ∣∣bfb(X )c∣∣ = N to complete the proof. Our proof utilizes the mathematical induction on i: If there exist b1, . . . , bi−1 ∈ [T ] such that
bfb({x ∈ X : x < iT})c = ( [T ]∣∣b{x ∈ X : x < iT}c∣∣ ) , (6)
then there exists bi ∈ [T ] such that bfb({x ∈ X : x < (i+ 1)T})c = ( [T ]∣∣b{x ∈ X : x < (i+ 1)T}c∣∣ ) . (7)
Here, one can observe that the statement trivially holds for the base case, i.e., for {x ∈ X : x < T}. Now, using the induction hypothesis, suppose that there exist b1, . . . , bi−1 ∈ [T ] satisfying (6). Now, we prove that there exists bi ∈ [T ] such that Sbi := bfb({x ∈ X : iT ≤ x < (i+ 1)T})c does not intersect with T := bfb({x ∈ X : x < iT})c, i.e, (7) holds. Consider the following inequality:∑
bi∈[T ]
|Sbi ∩ T | = |Sbi | × |T | ≤ N2
4
where the equality follows from the fact that for each x ∈ {x ∈ X : iT ≤ x < (i+ 1)T}, there exists exactly |T | values of bi so that bx mod T c ∈ T . However, since the number of possible choices of bi is T , if T > N2/4, then there exists bi ∈ [T ] such that Sbi ∩T = ∅, i.e., (7) holds. This completes the proof of Lemma 15.

heading: H.3 PROOF OF LEMMA 16
text: The proof of Lemma 16 is similar to that of Lemma 15. To begin with, we first define a network fb(x) : [0,K)→ [0, T ) for b = (bi)Ci=1 ∈ [T ]C and T =: M1 < M2 < · · · < MC+1 := K so that |{x ∈ X : Mi ≤ x < Mi+1}| ≤ dNC e ≤ b T N c for all i as
fb(x) :=  x if x < T x+ b1 mod T if M1 = T ≤ x < M2 x+ b2 mod T if M2 ≤ x < M3
... x+ bC mod T if MC ≤ x
= x− 2T × 1[x ≥ T ] + C∑ i=1
(( T + bi −
i−1∑ j=1 bj ) × 1[x ≥Mi]
− T × 1 [ x ≥ min{2T − bi,Mi+1} ]) (8)
where (8) holds as T ≥ dK2 e. Here, one can easily implement fb by a STEP + ID network of L hidden layer and d` neurons at the `-th hidden layer by utilizing one neuron for storing the input x, another one neuron for storing the temporary output, and other neurons implement indicator functions at 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 ×1[x ≥ T ] in (8) can be absorbed into ( T + bi− ∑i−1 j=1 bj ) ×1[x ≥Mi] in (8) for i = 1).
Now, we show that if T ≥ N , then there exist b ∈ [T ]C such that ∣∣bfb(X )c∣∣ = N to completes the proof. Our proof utilizes the mathematical induction on i: If there exist b1, . . . , bi−1 ∈ [T ] such that
bfb({x ∈ X : x < Mi})c = ( [T ]∣∣b{x ∈ X : x < Mi}c∣∣ ) , (9)
then there exists bi ∈ [T ] such that bfb({x ∈ X : x < Mi+1})c = ( [T ]∣∣b{x ∈ X : x < Mi+1}c∣∣ ) . (10)
Here, one can observe that the statement trivially holds for the base case, i.e., for {x ∈ X : x < T}. From the induction hypothesis, suppose that there exist b1, . . . , bi−1 ∈ [T ] satisfying (9). Now, we prove that there exists bi ∈ [T ] such that Sbi := bfb({x ∈ X : Mi ≤ x < Mi+1})c does not intersect with T := bfb({x ∈ X : x ≤Mi})c, i.e., (10) holds. Consider the following inequality:∑
bi∈[T ]
|Sbi ∩ T | ≤ b TN c × ( N − b TN c ) < T
where the first inequality follows from the fact that |Sbi | ≤ b TN c, |T | ≤ ( N − b TN c ) , and for each x ∈ {x ∈ X : Mi ≤ x < Mi+1}, there exists exactly |T | values of bi so that bx mod T c ∈ T . However, since the number of possible choices of bi is T , there exists bi ∈ [T ] such that Sbi ∩ T = ∅, i.e, (10) holds. This completes the proof of Lemma 16.

heading: H.4 PROOF OF LEMMA 13
text: In this proof, we explicitly construct fθ satisfying the desired property stated in Lemma 13. To begin with, we describe the high-level idea of the construction. First, we construct a map g : x 7→(⌊
x B
⌋ , x mod B ) to transforming an input x ∈ [0,K) to a pair (a, b) such that a ∈ [A] and bbc ∈ [B]. Here, we give labels to the pair (a, b) corresponding to the input x as y(a, bbc) := y(bxc). Note that this label is well-defined as if bx1c 6= bx2c, then bg(x1)c 6= bg(x2)c. Now, we construct parameters w0, . . . , wA−1 containing the label information of X as
wa := ∑ c∈[B] y(a, c)× 2−(c+1)D, (11)
i.e., from the (bbc ·D + 1)-th bit to the (bbc ·D +D)-th bit of the a-th parameter (wa) contains the label information of (a, bbc). Under this construction, we recover the label of x ∈ X by first mapping x to the pair (a, b) and extracting the z-th parameter wa. Then, using STEP, we extract bits from the (bbc ·D + 1)-th bit to the (bbc ·D +D)-th bit of wa 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, d1, . . . dL ∈ N such that AB ≥ K and d` ≥ 2 for all `, for any w0, . . . , wA−1 ∈ R, for any finite setX ⊂ [0,K), if ∑L `=1(d`−2) ≥ A, then there exists a STEP+ID network f of L layers and d` neurons at the `-th layer such that f(x) = (wbx/Bc, x mod B) for all x ∈ X .
From Lemma 20, a STEP + ID network of 1 hidden layer consisting of A+ 2 hidden neurons can map x ∈ X to (wbx/Bc, x mod B). Note that this network requires overall 4A+ 10 parameters (3A+ 6 edges and A+ 4 biases).
Finally, we introduce the following lemma for extracting from the (bbc · D + 1)-th bit to the (bbc ·D +D)-th bit of wa. The proof of Lemma 21 is presented in Section H.6. Lemma 21. For any D,B,R ∈ N, for any finite set X ⊂ [0, B), there exists a STEP + ID network f of 2dBDR e hidden layers and ( (2R + 5)2R + 2R2 + 8R + 7 ) dBDR e − R2
R − R2 + 3 parameters satisfying the following property: For any w = ∑BD i=1 ui × 2−i such that ui ∈ {0, 1}, f(x,w) =∑D
i=1 ubxc·D+i × 2D−i for all x ∈ X .
From Lemma 21, a STEP + ID network of 2dBDR e hidden layers and ( (2R + 5)2R + 2R2 + 8R +
7 ) dBDR e −R2
R −R2 + 3 parameters. Hence, by combining Lemma 20 and Lemma 21, fθ can be implemented by a STEP + ID network of 2dBDR e+ 2 hidden layers and 4A+ ( (2R+ 5)2R + 2R2 +
8R+ 7 ) dBDR e −R2 R −R2 + 3 parameters. This completes the proof of Lemma 13.

heading: H.5 PROOF OF LEMMA 20
text: We design f as f := fL ◦ · · · ◦ f1(0, x) where each f` represents the function of the `-th layer consisting of d` neurons. In particular, we construct f` as follows:
f`(w, x) := ( w + w0 × 1[` = 1] + d`−2∑ i=1 (wc`+i − wc`+i−1)× 1[x ≥ iB],
x− d`−2∑ i=1 B × 1[x ≥ iB] )
where w−1 := 0 and c` := ∑`−1 i=1(d` − 2). Then, f is the desired function and each f` can be implemented by a STEP + ID networks of 1 hidden layer consisting of d` hidden neurons (two neurons for storing x,w and other neurons are for d` − 2 indicator functions). This completes the proof of Lemma 20.

heading: H.6 PROOF OF LEMMA 21
text: We construct f(x,w) := 2RdBD/Re+D × fdBD/Re ◦ · · · ◦ f1(x,w) where f` is defined as
f`(x, v) :=  ( x, v − ∑R i=1 u(`−1)R+i × 2−(`−1)R−i + ∑R i=1 ( u(`−1)R+i ∧ 1[mi,` ≤ x < mi,` + 1] ) × 2−ri,` ) if ` < dBDR e v − ∑R i=1 u(`−1)R+i × 2−(`−1)R−i
+ ∑R i=1 ( u(`−1)R+i ∧ 1[mi,` ≤ x < mi,` + 1] ) × 2−ri,` if ` = dBDR e
.
where ui denotes the i-th bit of w in the binary representation, ∧ denotes the binary ‘and’ operation, and mi,`, ri,` are defined as
mi,` := ⌊ (`− 1)R+ i
D ⌋ ri,` := ⌈BD R ⌉ R+ ( (`− 1)R+ i− 1 mod D ) + 1.
Namely, each f` extracts R bits from the input w and it store the extracted bits to the last bits of v if the extracted bits are in from (bxc ·D + 1)-th bit to the (bxc ·D +D)-th bit of w. Thus, f(x,w) is the desired function for Lemma 21.
To implement each f` by a STEP + ID network, we introduce Lemma 22. Note that we extract ui from w in Lemma 22, i.e., we do not assume that ui is given. From Lemma 22, a STEP + ID network of 2dBDR e hidden layers consisting of 2
R +R+ 1 and R+ 2 hidden neurons alternatively can map (x,w) to ∑D i=1 ubxc·D+i × 2D−i for all x ∈ X . By considering the input dimension 2 and the output
dimension 1, this network requires ( (2R+5)2R+2R2 +8R+7 ) dBDR e−R2
R−R2 +3 parameters ( ( (2R+ 4)2R + 2R2 + 6R+ 4 ) dBDR e−R2
R−R2 + 2 edges and (2R + 2R+ 3)dBDR e+ 1 biases). This completes the proof of Lemma 21. Lemma 22. A STEP + ID network of 2 hidden layers having 2R +R+ 1 and R+ 2 hidden neurons at the first and the second hidden layer, respectively, can implement f`.
Proof of Lemma 22. We construct f` := g3 ◦ (g2 ⊕ g1) where g2 ⊕ g1 denotes the function concatenating the outputs of g1, g2. In this proof, we mainly focus on constructing f` for ` < dBDR e since fdBD/Re can be implemented similarly. We define g1, g2, g3 as
g1(x, v) :=
( x, v,
2R−1∑ i=0 η1,i × 1[i× 2−`R ≤ v < (i+ 1)× 2−`R],
..., 2R−1∑ i=0 ηR,i × 1[i× 2−`R ≤ v < (i+ 1)× 2−`R] ) =(x, v, u(`−1)R+1, . . . , u`R)
g2 ( x, v) := ( 1[m1,` ≤ x < m1,` + 1], . . . ,1[mR,` ≤ x < mR,` + 1] ) g3 ◦ (g1 ⊕ g2) := ( x, v −
R∑ i=1 u(`−1)R+i × 2−(`−1)R−i
+ R∑ i=1 1 [ u(`−1)R+i + 1[mi,` ≤ x < mi,` + 1] ≥ 2 ] × 2−ri,`
)
= ( x, v −
R∑ i=1 u(`−1)R+i × 2−(`−1)R−i)
+ R∑ i=1
(u(`−1)R+i ∧ 1[mi,` ≤ x < mi,` + 1])× 2−ri,` ) .
where ηr,i is a constant such that ηr,i = 1 if i × 2−`R ≤ x < (i + 1) × 2−`R implies that the ((`− 1)R + r)-th bit of x is 1 and ηr,i = 0 otherwise. Here, one can easily observe that g1 can be implemented by a linear combinations of 1[v ≥ 2−`R], . . . ,1[v ≥ (2R − 1)× 2−`R] as it trivially holds that 1[v ≥ 0] and 1[v < 2−(`−1)R], i.e., 2R − 1 indicator functions are enough for g1. Hence, g1 can be implemented by a STEP + ID network of 1 hidden layer consisting of 2R + 1 hidden neurons where additional 2 neurons are for passing x, v. In addition, g2 can be implemented by a STEP + ID network of R hidden neurons. Finally, g3 can be implemented by a STEP + ID network of 1 hidden layer consisting of R + 2 hidden neurons (R neurons for R indicator functions and 2 neurons for passing x, v).
Therefore, f` can be implemented by a STEP + ID network of 2 hidden layers consisting of 2R+R+1 hidden neurons for the first hidden layer and R+ 2 hidden neurons for the second hidden layer. Note that implementation within two hidden layer is possible since the outputs of g1, g2 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.

heading: H.7 PROOF OF LEMMA 17
text: The main idea of the proof of Lemma 17 is identical to that of Lemma 13. Recall A,B and w0, . . . , wA−1 ∈ R from the proof of Lemma 13. From Lemma 20, for any finite set X ⊂ [0,K), for any w0, . . . , wA−1 ∈ R, a STEP + ID network of A hidden layers and width 3 can map x to (wbx/Bc, x mod B) for all x ∈ X . Now, we introduce the following lemma replacing Lemma 21.
Lemma 23. For any D,B ∈ N, for any finite set X ⊂ [0, B), for any w = ∑DB i=1 ui × 2−i for some ui ∈ {0, 1}, there exists a STEP + ID network f of (2D + 1)B hidden layers and width 3 such that f(x,w) = ∑D i=1 ubxc·D+i × 2−i for all x ∈ X .
Using Lemma 20 and Lemma 23, one can easily find a STEP + ID network of A+ (2D+ 1)B hidden layers and width 3 satisfying the condition in Lemma 17. This completes the proof of Lemma 17.
Proof of Lemma 23. We construct f(x,w) := 2D(B+1) × fDB ◦ gDB ◦ hDB ◦ · · · ◦ f1 ◦ g1 ◦ h1 where f`, g`, h` are defined as
h`(x,w) :=
{( x,w ) if ` mod D 6= 1(
x− 1 + 3K × 1[x < 0], w ) if ` mod D = 1
g`(x,w) := ( x,w − 2−` × 1[w ≥ 2−`],1[w ≥ 2−`] ) f`(x,w, n) = ( x,w + 2−DK−d(`) × 1[x− n < −1]
) where d(`) := ` − b `−1D c + 1. Now, we explain the constructions of f`, g`, h`. Let b ∈ [0, B) and v ∈ [0, 1) be inputs of f , i.e., consider f(b, v). First, the indicator function in h` is activated only at ` = (bbc + 1) · D + 1 as b < B. In particular, the first entry of the output of h(bbc+1)·D+1 is greater than 2B and this is the maximum value of the first entry of the output of h(bbc+1)·D+1 as it monotonically decreases as ` grows. The indicator function in g` extracts and outputs the `-th bit of u. Lastly, f` add the `-th bit of u if and only if ` ∈ {bbc ·D + 1, . . . , (bbc+ 1) ·D}. This is because x ∈ [−1, 0) if and only if ` ∈ {bbc ·D + 1, . . . , (bbc+ 1) ·D}. Here, h` at ` mod D = 1 can be implemented by a STEP + ID network of 1 hidden layer and width 3, g` can be implemented by a STEP + ID network of 1 hidden layer and width 3, and f` can be implemented by a STEP + ID network of 1 hidden layer and width 3. Hence, f can be implemented by a STEP + ID network of (2D + 1)B hidden layers and width 3. This completes the proof of Lemma 23.

heading: H.8 PROOF OF LEMMA 18
text: The proof of Lemma 18 is almost identical to the proof of Lemma 13. Recall A,B and w0, . . . , wA−1 ∈ R as in the proof of Lemma 13. From Lemma 24, for any finite set X ⊂ [0,K), for any w0, . . . , wA−1 ∈ R, the first L′ hidden layers of the STEP + ID network fθ can map x to (wbx/Bc, x mod B) for all x ∈ 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, d1, . . . , dL ∈ N, for any finite set X ⊂ [0, B), suppose that there exists r1, . . . , rL−1 ∈ N satisfying that for r0 = rL = 1,
L−1∑ `=1 r` ≥ BD, 2r` + r` + r`−1 + 3 ≤ d` for all 1 ≤ ` ≤ L.
Then, there exists a STEP + ID network f of L hidden layers having d` hidden neurons at the `-th hidden layer satisfying the following property: For any w = ∑BD i=1 ui × 2−i such that ui ∈ {0, 1},
f(x,w) = ∑D i=1 ubxc·D+i × 2D−i for all x ∈ X .
Proof of Lemma 24. The proof of Lemma 24 utilizes the network constructions in the proofs of Lemma 21 and Lemma 22. In particular, we construct f(x,w) := 2D+ ∑L−1 `=1 r`×fL−1◦· · ·◦f1(x,w) defined as
f`(x, v) :=  ( x, v − ∑r` i=1 uR`+i × 2−R`−i + ∑r` i=1 ( uR`+i ∧ 1[mi,` ≤ x < mi,` + 1] ) × 2−si,` ) if ` < dBDR e
v − ∑r` i=1 uR`+i × 2−R`−i + ∑r` i=1 ( uR`+i ∧ 1[mi,` ≤ x < mi,` + 1] ) × 2−si,` if ` = dBDR e .
where ui denotes the i-th bit of w in the binary representation, ∧ denotes the binary ‘and’ operation, and R`,mi,`, si,` are defined as
R` := `−1∑ i=1 r`,
mi,` := ⌊R` + i
D
⌋ ,
si,` := RL + ( R` + i− 1 mod D ) + 1.
Note that R1 = 0 as the summation starts from i = 1 and RL = ∑L−1 `=1 r`. Namely, each f` extracts r` bits from the input w and it store the extracted bits to the last bits of v if the extracted bits are in from (bxc ·D + 1)-th bit to the (bxc ·D +D)-th bit of w. Thus, f(x,w) is the desired function for Lemma 24.
We construct f`(x, v) using the `-th hidden layer and the (`+ 1)-th hidden layer, i.e., there exists an overlap between constructions of f`(x, v) and f`+1(x, v). In particular, Lemma 22 directly allows us to obtain such a construction under the assumption in Lemma 18 that
2r` + r` + r`−1 + 3 ≤ d` for all 1 ≤ ` ≤ L.
This completes the proof of Lemma 24.

Review summaries:
The 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.