Year: 2021

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

text: (√ N ) parameters. Known VC-dimension upper bounds
imply that memorizing N samples requires Ω( √ N) parameters, and hence our construction is optimal up to logarithmic factors. We also give a generalized construction for networks with depth bounded by 1 ≤ L ≤ √ N , for memorizing N
samples using Õ(N/L) parameters. This bound is also optimal up to logarithmic factors. Our construction uses weights with large bit complexity. We prove that having such a large bit complexity is both necessary and sufficient for memorization with a sub-linear number of parameters.

heading: 1 INTRODUCTION
text: The expressive power of neural networks has been widely studied in many previous works. These works study different aspects of expressiveness, such as the universal approximation property (Cybenko, 1989; Leshno et al., 1993), and the benefits of depth in neural networks (Telgarsky, 2016; Eldan and Shamir, 2016; Safran and Shamir, 2017; Daniely, 2017; Chatziafratis et al., 2019). Another central and well studied question is about their memorization power.
The problem of memorization in neural networks can be viewed in the following way: For every dataset of N labeled samples (x1, y1), . . . , (xN , yN ) ∈ X × Y , construct a network N : X → Y such that N (xi) = yi for every i = 1, . . . , N . Many works have shown results regarding the memorization power of neural networks, using different assumptions on the activation function and data samples (see e.g. Huang and Babri (1998); Huang (2003); Baum (1988); Vershynin (2020); Daniely (2019; 2020); Bubeck et al. (2020); Park et al. (2020); Hardt and Ma (2016); Yun et al. (2019); Zhang et al. (2021); Nguyen and Hein (2018); Rajput et al. (2021); Sontag (1997)). The question of memorization also have practical implications on phenomenons such as ”double descent” (Belkin et al. (2019); Nakkiran et al. (2019)) which connects the memorization power of neural networks with their generalization capabilities.
A trivial lower bound on the required size of the network for memorizingN labeled points is implied by the VC dimension of the network (cf. Shalev-Shwartz and Ben-David (2014) ). That is, if a network with a certain size cannot shatter any specific set of N points, then it certainly cannot memorize all sets of N points. Known VC dimension bounds for networks with W parameters is on the order ofO(W 2) (Goldberg and Jerrum (1995); Bartlett et al. (1998; 2019)). Hence, it follows that memorizing N samples would require at least Ω ( N1/2 ) parameters. The best known upper bound is given in Park et al. (2020), where it is shown that memorizing N data samples can be done using a neural network with O ( N2/3 ) parameters. Thus, there is a clear gap between the lower and upper bounds, although we note that the upper bound is for memorization of any set of data samples, while the lower bound is for shattering a single set of data samples. In this paper we ask the following questions:
What is the minimal number of parameters that are required to memorize N labeled data samples? Is the task of memorizing any set of N data samples more difficult than shattering a single set of N samples?
We answer these questions by providing a construction of a ReLU feedforward neural network which achieves the lower bound up to logarithmic factors. In this construction we use a very deep neural network, but with a constant width of 12. In more details, our main result is the following: Theorem 1.1 (informal statement). Let (x1, y1), . . . , (xN , yN ) ∈ Rd × {1, . . . , C} be a set of N labeled samples of a constant dimension d, with ‖xi‖ ≤ r for every i and ‖xi − xj‖ ≥ δ for every i 6= j. Then, there exists a ReLU neural network F : Rd → R with width 12, depth Õ (√ N ) ,
and Õ (√ N )
parameters, such that F (xi) = yi for every i ∈ [N ], where the notation Õ(·) hides logarithmic factors in N,C, r, δ−1.
Comparing this result to the known VC bounds, we show that, up to logarithmic factors, our construction is optimal. This also shows, quite surprisingly, that up to logarithmic factors, the task of shattering a single set of N points is not more difficult than memorizing any set of N points, under the mild separability assumption of the data samples. We note that this result can also be extended to regression tasks (see Remark 3.3).
In our construction, the depth of the network is Θ̃ (√ N ) . We also give a generalized construction where the depth of the network is limited to some 1 ≤ L ≤ √ N . In his case, the number of param-
eters in our construction is Õ ( N L ) (see Theorem 5.1). We compare this result to the VC-dimension bound from Bartlett et al. (2019), and show that our construction is optimal up to logarithmic factors.
Our construction uses a bit extraction technique, inspired by Telgarsky’s triangle function (Telgarsky (2016)), and by Safran and Shamir (2017). Using this technique, we are able to use weights with bit complexity Θ̃( √ N), and deep neural networks to “extract” the bits of information from the specially crafted weights of the network. We also generalize our results to the case of having a bounded bit complexity restriction on the weights. We show both lower (Theorem 6.1) and upper (Theorem 6.2) bounds, proving that memorizing N points using a network with N1− parameters, for some ∈ [0, 0.5] can be done if the bit complexity of each weight is Θ̃ (N ). Hence, our construction is also optimal, up to logarithmic factors, w.r.t the bit complexity of the network. We emphasize that also in previous works showing non-trivial VC bounds (e.g. Bartlett et al. (1998; 2019)) weights with large bit complexity are used. We note that increasing the bit complexity beyond N1/2 cannot be used to further reduce the number of parameters (see the discussion in section 4).

heading: RELATED WORK

heading: MEMORIZATION – UPPER BOUNDS
text: The problem of memorizing arbitrary data points with neural networks has a rich history. Baum (1988) studied memorization in single-hidden-layer neural networks with the threshold activation, and showed that dNd e neurons suffice to memorize N arbitrary points in general position in R d with binary labels. Bubeck et al. (2020) extended the construction of Baum (1988) and showed that single-hidden-layer ReLU networks with 4 · dNd e hidden neurons can memorize N points in general position with arbitrary real labels. In Huang et al. (1991) and Sartori and Antsaklis (1991) it is shown that single-hidden-layer networks with the threshold activation can memorize any arbitrary set of N points, even if they are not in general position, using N − 1 neurons. Huang and Babri (1998) proved a similar result for any bounded non-linear activation function σ where either limz→∞ σ(z) or limz→−∞ σ(z) exists. Zhang et al. (2021) proved that single-hidden-layer ReLU networks can memorize arbitraryN points in Rd with arbitrary real labels usingN neurons and 2N+d parameters.
Huang (2003) showed that two-hidden-layers networks with the sigmoid activation can memorize N points with O( √ N) neurons, but the number of parameters is still linear in N . Yun et al. (2019) proved a similar result for ReLU (and hard-tanh) networks. Vershynin (2020) showed that threshold and ReLU networks can memorize N binary-labeled unit vectors in Rd separated by a distance of δ > 0, using Õ ( e1/δ 2 + √ N ) neurons and Õ ( e1/δ 2 (d+ √ N) +N ) parameters. Rajput et al.
(2021) improved the dependence on δ by giving a construction with Õ ( 1 δ + √ N ) neurons and
Õ ( d δ +N ) parameters. This result holds only for threshold networks, but does not assume that the inputs are on the unit sphere.
The memorization power of more specific architectures was also studied. Hardt and Ma (2016) proved that residual ReLU networks with O(N) neurons can memorize N points on the unit sphere separated by a constant distance. Nguyen and Hein (2018) considered convolutional neural networks and showed, under certain assumptions, memorization using O(N) neurons.
Note that in all the results mentioned above the number of parameters is at least linear in N . Our work is inspired by Park et al. (2020), that established a first memorization result with a sub-linear number of parameters. They showed that neural networks with sigmoidal or ReLU activations can memorize N points in Rd separated by a normalized distance of δ, using O ( N2/3 + log(1/δ)
) parameters (where the dimension d is constant). Thus, in this work we improve the dependence on N from N2/3 to √ N (up to logarithmic factors), which is optimal. We also note that the first stage in our construction is similar to the first stage in theirs.
Finally, optimization aspects of memorization were studied in Bubeck et al. (2020); Daniely (2019; 2020).

heading: MEMORIZATION – LOWER BOUNDS
text: An Ω(N) lower bound on the number of parameters required for memorizing arbitrary N points using neural networks with standard activations (e.g., threshold, sigmoid and ReLU) is given in Sontag (1997). Thus, for networks with o(N) parameters, there is a set of size N that cannot be shattered. It implies that in order to obtain memorization with a sub-linear number of parameters some assumptions are required. Our positive result circumvents this lower bound by assuming that the data is separated.
Moreover, lower bounds on the number of parameters required for memorization are implied by bounds on the VC dimension of neural networks. Indeed, if W parameters are not sufficient for shattering even a single set of size N , then they are clearly not sufficient for memorizing all sets of size N . The VC dimension of neural networks has been extensively studied in recent decades (cf. Anthony and Bartlett (2009); Bartlett et al. (2019)). The most relevant results for our work are by Goldberg and Jerrum (1995) and Bartlett et al. (2019). We discuss these results and their implications in Sections 4 and 5.
Trade-offs between the number of parameters of the network and the Lipschitz parameter of the prediction function in memorizing a given dataset are studies in Bubeck et al. (2021); Bubeck and Sellke (2021).

heading: THE BENEFITS OF DEPTH
text: In this work we show that deep networks have significantly more memorization power. Quite a few theoretical works in recent years have explored the beneficial effect of depth on increasing the expressiveness of neural networks (e.g., Martens et al. (2013); Eldan and Shamir (2016); Telgarsky (2016); Liang and Srikant (2016); Daniely (2017); Safran and Shamir (2017); Yarotsky (2017); Safran et al. (2019); Chatziafratis et al. (2019); Vardi and Shamir (2020); Bresler and Nagaraj (2020); Venturi et al. (2021); Vardi et al. (2021)). The benefits of depth in the context of the VC dimension is implied by, e.g., Bartlett et al. (2019). Finally, Park et al. (2020) already demonstrated that deep networks have more memorization power than shallow ones, albeit with a weaker bound than ours.

heading: 2 PRELIMINARIES

heading: NOTATIONS
text: For n ∈ N and i ≤ j we denote by BINi:j(n) the string of bits in places i until j inclusive, in the binary representation of n and treat is as an integer (in binary basis). For example, BIN1:3(32) = 4. We denote by LEN(n) the number of bits in its binary representation. We denote BINi(n) := BINi:i(n). For a function f and i ∈ N we denote by f (i) the composition of f with itself i times. We denote vectors in bold face. We use the Õ(N) notation to hide logarithmic factors, and use O(N) to hide constant factors. For n ∈ N we denote [n] := {1, . . . , n}. We say that a hypothesis class H shatters the points x1, . . . ,xN ∈ X if for every y1, . . . , yN ∈ {±1} there is h ∈ H s.t. h(xi) = yi for every i = 1, . . . , N .

heading: NEURAL NETWORKS
text: We denote by σ(z) := max{0, z} the ReLU function. In this paper we only consider neural networks with the ReLU activation.
Let d ∈ N be the data input dimension. We define a neural network of depth L as N : Rd → R where N (x) is computed recursively by
• h(1) = σ ( W (1)x + b(1) ) for W (1) ∈ Rm1×d,b(1) ∈ Rm1
• h(i) = σ ( W (i)h(i−1) + b(i) ) for W (i) ∈ Rmi×mi−1 ,b(i) ∈ Rmi for i = 2, . . . , L− 1
• N (x) = h(L) = W (L)h(L−1) + b(L) for W (L) ∈ R1×mL−1 ,b(L) ∈ R1
The width of the network is max{m1, . . . ,mL−1}. We define the number of parameters of the network as the number of weights of N which are non-zero. It corresponds to the number of edges when we view the neural network as a directed acyclic graph. We note that this definition is standard in the literature on VC dimension bounds for neural networks (cf. Bartlett et al. (2019)).

heading: BIT COMPLEXITY
text: We refer to the bit complexity of a weight as the number of bits required to represent the weight. Throughout the paper we use only weights which have a finite bit complexity. Specifically, for n ∈ N, its bit complexity is dlog ne. The bit complexity of the network is the maximal bit complexity of its weights.

heading: INPUT DATA SAMPLES
text: In this work we assume that we are givenN labeled data samples (x1, y1), . . . , (xN , yN ) ∈ Rd×[C], and our goal is to construct a network F : Rd → R such that F (xi) = yi for every i ∈ [N ]. We will assume that there is a separation parameter δ > 0 such that for every i 6= j we have ‖xi − xj‖ ≥ δ. We will also assume that the data samples have a bounded norm, i.e. there is r > 0 such that ‖xi‖ ≤ r for every i ∈ [N ]. We note that in Sontag (1997) it is shown that sets of size N cannot be memorized using neural networks with standard activations (including ReLU) unless there are Ω(N) parameters. Hence, to show a memorization result with o(N) parameters we must have some assumption on the data samples.
Note that any neural network that does not ignore input neurons must have at least d parameters. Existing memorization results (e.g., Park et al. (2020)) assume that d is constant. As we discuss in Remark 3.2, in our work we assume that d is at most O( √ N). 3 MEMORIZATION USING Õ (√ N ) PARAMETERS
In this section we prove that given a finite set of N labeled data points, there is a network with Õ (√ N ) parameters which memorizes them. Formally, we have the following:
Theorem 3.1. Let N, d,C ∈ N, and r, δ > 0, and let (x1, y1), . . . , (xN , yN ) ∈ Rd × [C] be a set of N labeled samples with ‖xi‖ ≤ r for every i and ‖xi − xj‖ ≥ δ for every i 6= j. Denote R := 10rN2δ−1 √ πd. Then, there exists a neural network F : Rd → R with width 12 and depth
O (√ N log(N) + √ N
log(N) ·max {log(R), log(C)}
) ,
such that F (xi) = yi for every i ∈ [N ]. From the above theorem, we get that the total number of parameters is Õ ( d+ √ N ) . For d = O( √ N) (see Remark 3.2 below) we get the lower bound presented in Theorem 1.1. Note that except for the number of data points N and the dimension d, the number of parameters of the network depends only logarithmically on all the other parameters of the problem (namely, on C, r, δ−1). We
also note that the construction can be improved by some constant factors, but we preferred simplicity over minor improvements. Specifically, we hypothesize that it is possible to give a construction using width 3 (instead of 12) similar to the result in Park et al. (2020). To simplify the terms in the theorem, we assume that r ≥ 1, otherwise (i.e., if all data points have a norm smaller than 1) we just fix r := 1 and get the same result. In the same manner, we assume that δ ≤ 1, otherwise we just fix δ := 1.
Remark 3.2 (Dependence on d). Note that any neural network that does not ignore input neurons must have at least d parameters. In our construction the first layer consists of a single neuron (i.e width 1), which means that the number of parameters in the first layer is d + 1. Hence, this dependence on d is unavoidable. Previous works (e.g., Park et al. (2020)) assumed that d is constant. In our work, to achieve the bound of Õ (√ N ) parameters we can assume that either d is constant
or it may depend on N with d = O (√ N ) .
Remark 3.3 (From classification to regression). Although the theorem considers multi-class classification, it is possible to use the method suggested in Park et al. (2020) to extend the result to regression. Namely, if the output is in some bounded interval, then we can partition it into smaller intervals of length each. We define a set of output classes C with O ( 1 ) classes, such that each class corresponds to an interval. Now, we can use Theorem 3.1 to get an approximation of the output, while the number of parameters is linear in log ( 1 ) .

heading: 3.1 PROOF INTUITION
text: Below we describe the main ideas of the proof. The full proof can be found in Appendix A. The proof is divided into three stages, where at each stage we construct a network Fi for i ∈ {1, 2, 3}, and the final network is F = F3 ◦F2 ◦F1. Each subnetwork Fi has width O(1), but the depth varies for each such subnetwork.
Stage I: We project the data points from Rd to R. This stage is similar to the one used in the proof of the main result from Park et al. (2020). We use a network with 2 layers for the projection. With the correct scaling, the output of this network on x1, . . . ,xN ∈ Rd are points x1, . . . , xN ∈ R with |xi − xj | ≥ 2 for i 6= j, and |xi| ≤ R for every i where R = O ( N2drδ−1 ) .
Stage II: Following the previous stage, our goal is now to memorize (x1, y1), . . . , (xN , yn) ∈ R× [C], where the xi’s are separated by a distance of at least 2. We can also reorder the indices to assume w.l.o.g that x1 < x2 < · · · < xN . We split the data points into √ N log(N) intervals,
each containing √
N log(N) data points. We also construct crafted integers w1 . . . , w √ N log(N) and
u1, . . . , u√N log(N) in the following way: Note that by the previous stage, if we round xi to bxic, it can be represented using log(R) bits. Also, each yi can be represented by at most log(C) bits. Suppose that xi is the k-th data point in the j-th interval (where j ∈ [√ N log(N) ] and k ∈{
0, . . . , √
N log(N) − 1 } ), then we define uj , wj such that
BINk·log(R)+1:(k+1)·log(R)(uj) = bxic BINk·log(C)+1:(k+1)·log(C)(wj) = yi .
That is, for each interval j, the number uj has log(R) bits which represent the integral value of the k-th data point in this interval. In the same manner, wj has log(C) bits which represent the label of the k-th data point in this interval. This is true for all the k data points in the j-th interval, hence wj and uj are represented with log(R) · √ N log(N) and log(C) · √ N log(N) bits respectively.
We construct a network F2 : R → R3 such that F2(xi) = ( xi wji uji ) for each xi, where the i-th data point is in the ji-th interval.
Stage III: In this stage we construct a network which uses a bit extraction technique adapting Telgarsky’s triangle function (Telgarsky, 2016) to extract the relevant information out of the crafted
integers from the previous stage. In more details, given the input ( x w u ) , we sequentially extract
from u the bits in places k · log(R) + 1 until (k + 1) · log(R) for k ∈ { 0, 1, . . . , √
N log(N) − 1
} ,
and check whether x is at distance at most 1 from the integer represented by those bits. If it is, then we extract the bits in places k · log(C) + 1 until (k + 1) · log(C) from w, and output the integer represented by those bits. By the previous stage, for each xi we know that u includes the encoding of bxic, and since |xi − xj | ≥ 2 for every j 6= i (by the first stage), there is exactly one such xi. Hence, the output of this network is the correct label for each xi.
The construction is inspired by the works of Bartlett et al. (2019); Park et al. (2020). Specifically, the first stage uses similar results from Park et al. (2020) on projection onto a 1-dimensional space. The main difference from previous constructions is in stages II and III where in our construction we encode the input data points in the weights of the network. This allows us to reduce the required number of parameters for memorization of any dataset.

heading: 4 ON THE OPTIMAL NUMBER OF PARAMETERS
text: In section 3 we showed that a network with widthO(1) and depth Õ (√ N ) can perfectly memorize
N data points, hence only Õ (√ N )
parameters are required for memorization. In this section, we compare our results with the known lower bounds.
First, note that our problem contains additional parameters besidesN . Namely, d,C, r and δ. As we discussed in Remark 3.2, we assume that d is either constant or depends on N with d = O( √ N). In this comparison we also assume that r and δ−1 are either constants or depend polynomially on N . We note that for a constant d, either r or δ−1 must depend on N . For example, assume d = 1 and r = 1/2, then to have N point in Rd with norm at most r and distance at least δ from one another we must have that δ−1 ≥ N − 1. Hence, we can bound R ≤ poly(N) (where R is defined in Theorem 3.1), which implies log(R) = O(log(N)). Moreover, we assume that C ≤ poly(N), because it is reasonable to expect that the number of output classes is not larger than the number of data points. Hence, also log(C) = O(log(N)). In regression tasks, as discussed in Remark 3.3, we can choose C to consist of ⌈ 1 ⌉ classes where is either a constant or depends at most polynomially on the other parameters.
Using that R,C ≤ poly(N), and tracing back the bounds given in Theorem 3.1, we get that the number of parameters of the network is O (√ N log(N) ) . Note that here the O(·) notation only
hides constant factors, which can also be exactly calculated using Theorem 3.1.
By Goldberg and Jerrum (1995), the VC dimension of the class of ReLU networks with W parameters is O(W 2). Thus, the maximal number of points that can be shattered is O(W 2). Hence, if we can shatter N points then W = Ω( √ N). In particular, it gives a Ω( √ N) lower bound for the number of parameters required to memorize N inputs. Thus, the gap between our upper bound and the above lower bound is only O (√ log(N) ) , which is sub-logarithmic.
Moreover, it implies that the number of parameters required to shatter one size-N set is roughly equal (up to a sub-logarithmic factor) to the number of parameters required to memorize all size-N sets (that satisfy some mild assumptions). Thus, perhaps surprisingly, the task of memorizing all size-N sets is not significantly harder than shattering a single size-N set.
If we further assume that C depends on N , i.e., the number of classes depends on the number of samples (or in regression tasks, as we discussed in Remark 3.3, the accuracy depends on the number of samples), then we can show that our bound is tight up to constant terms. Thus, in this case the√
log(N) factor is unavoidable. Formally, we have the following lemma:
Lemma 4.1. Let C,N ∈ N, and assume that C = N for some constant > 0. If we can express all the functions of the form g : [N ]→ [C] using neural networks with W parameters, then W = Ω (√ N log(N) ) .
Proof. Let F be the class of all the functions f : [N ] × [ log(N)] → {0, 1}. The VC-dimension bound from Goldberg and Jerrum (1995) implies that expressing all the functions from F with neural networks requires W = Ω (√ N log(N) ) parameters, since it is equivalent to shattering a
set of size N log(N). Assume that we can express all the functions of the form g : [N ] → [C] using networks with W ′ parameters. Given some function f ∈ F we can express it with a neural network as follows: define a function g : [N ]→ [C] such that for every n ∈ [N ] and i ∈ [ log(N)], the i-th bit of g(n) is f(n, i). We construct a neural network for f , such that for an input (n, i) it computes g(n) (using W ′ parameters) and outputs its i-th bit. The extraction of the i-th bit can be implemented using the bit extraction technique from the proof of Theorem 3.1. Overall, this network requires O(W ′ + log(N)) parameters, and in this manner we can express all the functions in F . This shows that W = O(W ′ + log(N)), but since we also have W = Ω (√ N log(N) ) then
W ′ = Ω (√ N log(N) ) .

heading: 5 LIMITING THE DEPTH
text: In this section we generalize Theorem 3.1 to the case of having a bounded depth. We will then compare our upper bound on memorization to the VC-dimension bound from Bartlett et al. (2019). We have the following:
Theorem 5.1. Assume the same setting as in Theorem 3.1, and denote R := dNCrδ−1. Let L ∈ [ √ N ]. Then, there exists a network F : Rd → R with width O ( N L2 ) , depth O ( L√ log(L) · log(R) ) and a total of O ( N
L √ log(L) · log(R) + d
) parameters such that F (xi) = yi for every i ∈ [N ].
Note that for L = √ N we get a similar bound to Theorem 3.1. In the proof we partition the dataset into NL2 subsets, each containing L 2 data points. We then use Theorem 3.1 on each such subset to construct a subnetwork of depth O (L · log(R)) and width O(1) to memorize the data points in the subset. We construct these subnetworks such that their output on each data point outside of their corresponding subset is zero. Finally we stack these subnetworks to construct a wide network, whose output is the sum of the outputs of the subnetworks.
By Bartlett et al. (2019), the VC dimension of the class of ReLU networks with W parameters and depth L is O(WL log(W )). It implies that if we can shatter N points with networks of depth L, then W = Ω ( N
L log(N)
) . As in section 4, assume that d is either constant or at most O( √ N), and
that r, δ−1 and C are bounded by some poly(N). Theorem 5.1 implies that we can memorize any N points (under the mild separability assumption) using networks of depth L and W = Õ ( N L ) parameters. Therefore, the gap between our upper bound and the above lower bound is logarithmic. It also implies that, up to logarithmic factors, the task of memorizing any set of N points using depth-L neural networks is not more difficult than shattering a single set of N points with depth-L networks.
Proof of Theorem 5.1. We first construct a network H : Rd → R in the same manner as the construction of F1 is the first stage of Theorem 3.1 (this construction is detailed in Lemma A.2 in the appendix). This is a 2-layer network with width 1. We denote the output of H on the samples x1, . . . ,xN as x1, . . . , xN . Note that by the construction |xi| ≤ O(R) for every i ∈ [N ] and |xi − xj | ≥ 2 for every i 6= j.
We split the inputs to NL2 subsets of size L 2 each, we denote these subsets as I1, . . . , I N L2 (assume w.l.o.g. that NL2 is an integer, otherwise replace it with ⌈ N L2 ⌉ ). For each subset Ik we use stages II and III from Theorem 3.1 to construct a network Fk such that Fk(xi) = yi if xi ∈ Ik. Note that we only need to use the last two stages since we have already done the projection stage, hence are data
samples are already one-dimensional. We construct a network F̃ : R→ RN/L2 such that:
F̃ (x) =  F1(x)... FN/L2(x)  . We also define a network G : RN/L2 → R which adds up all its inputs. Finally, we construct the network F : Rd → R as F := G ◦ F̃ ◦H . By the construction of each Fk from Theorem 3.1, for every x ∈ R, if |x−xi| ≥ 2 for every i ∈ Ik, then Fk(x) = 0. For every i ∈ [N ], there is exactly one k ∈ [N/L2] such that i ∈ Ik. Using the projection H , for this k we get that Fk(xi) = yi, and for every ` 6= k we get that F`(xi) = 0. This means that F (xi) = yi for every i ∈ [N ]. The depth of F is the sum of the depths of its subnetwork. Both H and G have depth O(1), and by
Theorem 3.1, the depth of Fk is at mostO (
L√ log(L)
· log(R) ) , since each such network memorizes
L2 samples. Hence, the total depth of F is O (
L√ log(L)
· log(R) ) . Finally, the width of F is the
maximal width of its subnetworks. The width of G and H is 1. The width of each Fk is also O(1) by Theorem 3.1, hence the width of F̃ is O ( N L2 ) , which is also the width of F .
Recall that the number of parameters of a network is the number of non-zero weights. In our case, the network consists of NL2 subnetworks, where the weights between these subnetworks are zero. Each such subnetwork has depth O (
L√ log(L)
· log(R) ) and width O(1). Also, the pro-
jection phase requires O(d) parameters. In total, the number of parameters in the network is
O
( N
L √ log(L) · log(R) + d
) .

heading: 6 BIT COMPLEXITY - LOWER AND UPPER BOUNDS
text: In the proof of Theorem 3.1 the bit complexity of the network is roughly √ N log(N) (See Theorem A.1 in the appendix). On one hand, having such large bit complexity allows us to ”store” and ”extract” information from the weights of the network using bit extraction techniques. This enable us to memorize N data points using significantly less than N parameters. On the other hand, having large bit complexity makes the network difficult to implement on finite precision machines.
In this section we argue that having large bit complexity is necessary and sufficient if we want to construct a network that memorizes N data points with less than N parameters. We show both upper and lower bounds on the required bit complexity, and prove that, up to logarithmic factors, our construction is optimal w.r.t. the bit complexity.
First, we show a simple upper bound on the VC dimension of neural networks with bounded bit complexity: Theorem 6.1. Let H be the hypothesis class of ReLU neural networks with W parameters, where each parameter is represented by B bits. Then, the VC dimension ofH is O(WB +W log(W )).
Proof. We claim that H is a finite hypothesis class with at most 2O(WB+W log(W )) different functions. Let f be a neural network in H, and suppose that it has at most W parameters and U ≤ W neurons. Then, each weight of f can be represented by at most B+ 2 log(U) bits, namely, 2 log(U) bits for the indices of the input and output neurons of the edge, and B bits for the weight magnitude. Hence, f is represented by at most O(W (B + log(U))) bits. Since U ≤ W we get that every function inH can be represented by at mostO(W (B+log(W ))) bits, which gives the bound on the size ofH. An upper bound on the VC dimension of finite classes is the log of their size (cf. ShalevShwartz and Ben-David (2014)), and hence the VC dimension ofH is O(WB +W log(W )).
This lemma can be interpreted in the following way: Assume that we want to shatter a single set of N points, and we use ReLU neural networks with N1− parameters for some ∈ [ 0, 12 ] . Then,
the bit complexity of each weight in the network must be at least Ω(N ). Thus, to shatter N points with less thanN parameters, we must have a neural network with bit complexity that depends onN . Also, for = 12 , our construction in Theorem 3.1 (which memorizes any set of N points) is optimal, up to logarithmic terms, since having bit complexity of Ω( √ N) is unavoidable. We emphasize that existing works that show non-trivial VC bounds also use large bit complexity (e.g. Bartlett et al. (1998; 2019)).
We now show an upper bound on the number of parameters of a network for memorizing N data points, assuming that the bit complexity of the network is bounded: Theorem 6.2. Assume the same setting as in Theorem 3.1, and denote R := dNCrδ−1. Let B ∈ [ √ N ]. Then, there exists a network F : Rd → R with bit complexity O ( B√
log(B) · log(R)
) , depth
O
( N √ log(B) B · log(R) ) and width O(1) such that F (xi) = yi for every i ∈ [N ].
The full proof can be found in Appendix B. The proof idea is to partition the dataset into NB2 subsets, each containing B2 data points. For each such subset we construct a subnetwork using Theorem 3.1 to memorize the points in this subset. We concatenate all these subnetwork to create one deep network, such that the output of each subnetwork is added to the output of the previous one. Using a specific projection from Lemma A.2 in the appendix, this enables each subnetwork to output 0 for each data point which is not in the corresponding subset. We get that the concatenated network successfully memorizes the N given data points.
Assume, as in the previous sections, that r, δ−1 and C are bounded by some poly(N) and d is bounded by O( √ N). Theorem 6.2 implies that we can memorize any N points (under mild as-
sumptions), using networks with bit complexity B and Õ ( N B ) parameters. More specifically, we
can memorize N points using networks with bit complexity Õ (N ) and Õ ( N1− ) parameters, for
∈ [ 0, 12 ] . Up to logarithmic factors in N , this matches the bound implied by Theorem 6.1.

heading: 7 CONCLUSIONS
text: In this work we showed that memorization of N separated points can be done using a feedforward ReLU neural network with Õ (√ N )
parameters. We also showed that this construction is optimal up to logarithmic terms. This result is generalized for the cases of having a bounded depth network, and a network with bounded bit complexity. In both cases, our constructions are optimal up to logarithmic terms.
An interesting future direction is to understand the connection between our results and the optimization process of neural networks. In more details, it would be interesting to study whether training neural networks with standard algorithms (e.g. GD or SGD) can converge to a solution which memorizes N data samples while the network have significantly less than N parameters.
Another future direction is to study the connection between the bounds from this paper and the generalization capacity of neural networks. The double descent phenomenon (Belkin et al. (2019)) suggests that after a network crosses the ”interpolation threshold”, it is able to generalize well. Our results suggest that this threshold may be much smaller than N for a dataset with N samples, and it would be interesting to study if this is true also in practice.
Finally, it would be interesting to understand whether the logarithmic terms on our upper bounds are indeed necessary for the construction, or these are artifacts of our proof techniques. If these logarithmic terms are not necessary, then it will show that for neural network, the tasks of shattering a single set of N points, and memorizing any set of N points are exactly as difficult (maybe up to constant factors).

heading: A PROOF FROM SECTION 3
text: We first give the proofs for each of the three stages of the construction, then we combine all the stages to proof Theorem 3.1. For convenience, we rewrite the theorem, and also state the bound on the bit complexity of the network: Theorem A.1. Let N, d,C ∈ N, r, δ > 0, and let (x1, y1), . . . , (xN , yN ) ∈ Rd × [C] be a set of N labeled samples with ‖xi‖ ≤ r for every i and ‖xi − xj‖ ≥ δ for every i 6= j. Denote R := 10rN2δ−1 √ πd. Then, there exists a neural network F : Rd → R with width
12, depth O (√ N log(N) + √
N log(N) ·max {log(R), log(C)}
) and bit complexity bounded by
O ( log(d) + √
N log(N) ·max{log(R), log(C)} ) such that F (xi) = yi for every i ∈ [N ].

heading: A.1 STAGE I: PROJECTING ONTO A ONE-DIMENSIONAL SUBSPACE
text: Lemma A.2. Let x1, . . . ,xN ∈ Rd with ‖xi‖ ≤ r for every i and ‖xi − xj‖ ≥ δ for every i 6= j. Then, there exists a neural network F : Rd → R with width 1, depth 2, and bit complexity log ( 3drN2 √ πδ−1 ) , such that 0 ≤ F (xi) ≤ 10rN2δ−1 √ πd for every i ∈ [N ] and |F (xi) − F (xj)| ≥ 2 for every i 6= j.
To show this lemma we use a similar argument to the projection phase from Park et al. (2020), where the main difference is that we use weights with bounded bit complexity. Specifically, we use the following: Lemma A.3 (Lemma 8 from Park et al. (2020)). Let N, d ∈ N, then for any distinct x1, . . . ,xN ∈ Rd there exists a unit vector u ∈ Rd such that for all i 6= j:√
8 πd · 1 N2 ‖xi − xj‖ ≤ |u>(xi − xj)| ≤ ‖xi − xj‖ (1)
Proof of Lemma A.2. We first use Lemma A.3 to find u ∈ Rd that satisfies Eq. (1). Note that ‖u‖ = 1, hence every coordinate of u is smaller than 1. We define ũ ∈ Rd such that each of its coordinates is equal to the first dlog ( dN2 √ π ) e bits of the corresponding coordinate of u. Note that ‖ũ− u‖ ≤ √ d
2log(dN 2√π) ≤ 1 N2 √ πd . For every i 6= j we have that:
|ũ>(xi − xj)| ≥ |u>(xi − xj)| − |(ũ− u)>(xi − xj)| ≥ √ 8
πd
1
N2 ‖xi − xj‖ − ‖ũ− u‖ · ‖xi − xj‖ ≥ √ 8
πd
1
N2 ‖xi − xj‖ −
1
N2 √ πd · ‖xi − xj‖
≥ 1 N2 √ πd ‖xi − xj‖ . (2)
We also have for every i ∈ [N ]: |ũ>xi| ≤ |u>xi|+ |(ũ− u)>xi|
≤ ‖xi‖+ 1
N2 √ πd ‖xi‖ ≤ 2‖xi‖ . (3)
Let b := −min{0,mini{bũ>xic}} + 1, and note that by Eq. (3) we have b ≤ 2r + 1. We define the network F : Rd → R in the following way:
F (x) = (2N2δ−1 √ πd) · σ ( ũ>x + b ) .
We show the correctness of the construction. Let i 6= j, then we have that: |F (xi)− F (xj)| = (2N2δ−1 √ πd) ∣∣σ (ũ>xi + b)− σ (ũ>xj + b)∣∣ = (2N2δ−1 √ πd)
∣∣ũ>xi + b− (ũ>xj + b)∣∣ = (2N2δ−1 √ πd) ∣∣ũ>(xi − xj)∣∣ ≥ 2 ,
where the second equality is because by the definition of b we have that ũ>xi + b ≥ 0 for every i, and the last inequality is by Eq. (2) and the assumption that ‖xi − xj‖ ≥ δ for every i 6= j. Now, let i ∈ [N ], then we have:
|F (xi)| = (2N2δ−1 √ πd) · σ(ũ>xi + b)
= (2N2δ−1 √ πd) · (ũ>xi + b) ≤ (2N2δ−1 √ πd) · (4r + 1) ≤ 10rN2δ−1 √ πd ,
where the second to last inequality is since b ≤ 2r + 1 and Eq. (3). The network F has depth 2 and width 1. The bit complexity of the network can be bounded by log ( 3drN2 √ πδ−1 ) . This is because each coordinate of ũ can be represented using dlog(dN2 √ π)e bits, the bias b can be represented using at most dlog(2r+1)e bits and the weight in the second layer can be represented using dlog(2N2 √ πdδ−1)e bits.

heading: A.2 STAGE II: FINDING THE RIGHT SUBSET
text: Lemma A.4. Let x1 < · · · < xN < R with R > 0, xi ∈ R for every i ∈ [N ] and |xi − xj | ≥ 2 for every i 6= j. Let m ∈ N with m < N and let w1, . . . , wm ∈ N where LEN(wj) ≤ b for every j ∈ [m]. Let k := ⌈ N m ⌉ . Then, there exists a neural network F : R→ R with width 4, depth 3m+ 2 and bit complexity b+ dlog(R)e such that for every i ∈ [N ] we have that F (xi) = wd ik e.
Proof. Let j ∈ [m]. We define network blocks F̃j : R → R and Fj : R → R2 in the following way: First, we use Lemma A.6 to construct F̃j such that F̃j(x) = 1 for every x ∈ [bxj·k−k+1c, bxj·k + 1c], and F̃j(x) = 0 for x < bxj·k−k+1c − 12 or x > bxj·k + 1c + 1 2 . In particular, F̃j(xi) = 1 if i ∈ [j · k − k + 1, j · k], and F̃j(xi) = 0 otherwise. Note that since k is defined with ceil, it is possible that j · k ≥ N , if this is the case we replace j · k with N . Next, we define:
Fj (( x y )) = ( x
y + wj · F̃j(x)
) .
Finally we define the network F (x) = (
0 1
)> Fm ◦ · · · ◦ F1 (( x 0 )) (we can use one extra layer to
augment the input with an extra coordinate of 0).
We show that this construction is correct. Note that for every i ∈ [N ], if we denote j = d ik e, then F̃j(xi) = 1 and for every j′ 6= j we have F̃j′(xi) = 0. By the construction of F we get that F (xi) = wd ik e.
The width of F at every layer j is at most the width of F̃j + 2, since we also keep copies of both x and y, hence the width is at most 4. The depth of F̃j is 2, and F is a composition of the F̃j’s
with an extra layer for the input to get x 7→ ( x 0 ) , and an extra layer in the output to extract the
last coordinate. Hence, its depth is 3m + 2. The bit complexity is bounded by the sum of the bit complexity of F̃j and the weights wj , hence it is bounded by b+ dlog(R)e.

heading: A.3 STAGE III: BIT EXTRACTION FROM THE CRAFTED WEIGHTS
text: Lemma A.5. Let ρ, n, c ∈ N. Let u ∈ N with LEN(u) = ρ · n and let w ∈ N with LEN(w) = c · n. Assume that for any `, k ∈ {0, 1, . . . , n − 1} with ` 6= k we have that∣∣BINρ·`+1:ρ·(`+1)(u)− BINρ·k+1:ρ·(k+1)(u)∣∣ ≥ 2. Then, there exists a network F : R3 → R with width 12, depth 3n ·max{ρ, c} + 2n + 2 and bit complexity nmax{ρ, c} + 2, such that for every x > 0, if there exist j ∈ {0, 1, . . . , n− 1} where bxc = BINρ·j+1:ρ·(j+1)(u), then:
F (( x w u )) = BINc·j+1:c·(j+1)(w) .
Proof. Let i ∈ {0, 1, . . . , n−1}, and denote by ϕ(z) := σ(σ(2z)−σ(4z−2)) the triangle function due to Telgarsky (2016). We construct the following neural network Fi:
Fi :  x ϕ(i·ρ) ( u 2n·ρ + 1 2n·ρ+1 ) ϕ(i·ρ) ( u 2n·ρ + 1 2n·ρ+2 ) ϕ(i·c) ( w 2n·c + 1 2n·c+1 ) ϕ(i·c) ( w
2n·c + 1 2n·c+2 ) y
 7→  x ϕ((i+1)·ρ) ( u 2n·ρ + 1 2n·ρ+1 ) ϕ((i+1)·ρ) ( u 2n·ρ + 1 2n·ρ+2 ) ϕ((i+1)·c) ( w 2n·c + 1 2n·c+1 ) ϕ((i+1)·c) ( w
2n·c + 1 2n·c+2 ) y + yi  where we define yi := BINi·c+1:(i+1)·c(w) if x ∈ [BINi·ρ+1:(i+1)·ρ(u), BINi·ρ+1:(i+1)·ρ(u)+1], and yi = 0 if x > BINi·ρ+1:(i+1)·ρ(u) + 32 or x < BINi·ρ+1:(i+1)·ρ(u)− 1 2 .
The construction uses two basic building blocks: The first is using Lemma A.7 twice, for u and w. This way we construct two smaller networks Fwi , F u i , such that:
Fui :
( ϕ(i·ρ) ( u
2n·ρ + 1 2n·ρ+1 ) ϕ(i·ρ) ( u
2n·ρ + 1 2n·ρ+2
)) 7→ ϕ((i+1)·ρ) ( u2n·ρ + 12n·ρ+1 )ϕ((i+1)·ρ) ( u2n·ρ + 12n·ρ+2 )
BINi·ρ+1:(i+1)·ρ(u)  Fwi : ( ϕ(i·c) ( w 2n·c + 1 2n·c+1 ) ϕ(i·c) ( w
2n·c + 1 2n·c+2
)) 7→ ϕ((i+1)·c) ( w2n·c + 12n·c+1 )ϕ((i+1)·c) ( w2n·c + 12n·c+2 )
BINi·c+1:(i+1)·c(w)  . The second is to construct yi. We use Lemma A.8 with inputs BINi·ρ+1:(i+1)·ρ(u) and x, and denote the output of this network by ỹi. We use the following 1-layer network:(
ỹi BINi·c+1:(i+1)·c(w)
) 7→ σ ( ỹi · 2c+1 − 2c+1 + BINi·c+1:(i+1)·c(w) ) Note that if ỹi = 1 then the output of the above network is BINi·c+1:(i+1)·c(w), and if ỹi = 0 then the output of the network is 0 since BINi·c+1:(i+1)·c(w) ≤ 2c. The last layer of Fi is just adding the output yi to y, and using the identity on the other coordinates which are being kept as the output, while the other coordinates (namely, the last output coordinates of Fwi and F u i ) do not appear in the output of Fi. Also note that all the inputs and outputs of the networks and basic building blocks are positive, hence σ acts as the identity on them. This means that if Fui is deeper than F w i (or the other way around), then we can just add identity layers to F w i which do not change the output, but make the depths of both networks equal. Finally we define:
F := G ◦ Fn−1 ◦ · · · ◦ F0 ◦H ,
where: (1) G : R5 → R is a 1-layer network that outputs the last coordinate of the input, and; (2) H : R3 → R6 is a 1-layer network such that:
H : ( x w u ) 7→  x u 2n·ρ + 1 2n·ρ+1 u 2n·ρ + 1 2n·ρ+2 w 2n·c + 1 2n·c+1
w 2n·c + 1 2n·c+2
0  where we assume that x,w, u > 0.
We show the correctness of the construction. We have that F (( x w u )) = ∑n−1 i=0 yi. Assume there exists j ∈ {0, 1 . . . , n − 1} such that bxc = BINρ·j+1:ρ·(j+1)(u). Then, by the construction of yi we have that yj = BINc·j+1:c·(j+1)(w), and for every other ` 6= j, since∣∣BINρ·`+1:ρ·(`+1)(u)− BINρ·j+1:ρ·(j+1)(u)∣∣ ≥ 2, we must have that x > BINρ·`+1:ρ·(`+1)(u) + 32 or x < BINρ·`+1:ρ·(`+1)(u)− 12 , which means that y` = 0. In total we get the the output of F is equal to ∑n−1 i=0 yi = yj = BINc·j+1:c·(j+1)(w) as required.
We will now calculate the width, depth and bit complexity of the network F . The width of each Fwi and F u i is equal to 5 by Lemma A.7, and we need two more neurons for x and y. In total, the width is bounded by 12. Note that all other parts of the network (i.e. H, G and the network from Lemma A.8) require less width than this bound. For the depth, by Lemma A.7, the depth of each Fui and F w i is at most 3 ·max{ρ, c}, adding the construction from Lemma A.8, the depth of each Fi is at most 3 ·max{ρ, c}+ 2. Summing over all i, and adding the depth of G and H we get that the depth of F is bounded by 3n ·max{ρ, c}+ 2n+ 2. Finally, the bit complexity of Fui , Fwi and H is bounded by nmax{ρ, c}+ 2, and all other parts of the network require less bit complexity. Hence, the bit complexity of F is bounded by n ·max{ρ, c}+ 2.

heading: A.4 PROOF OF THEOREM 3.1
text: The construction is done in three phases. We first project the points onto a 1-dimensional subspace, where the projection preserves distances up to some error. The second step is to split the points into√ N log(N) subsets, and to extract two weights containing “hints” about the points and their labels. The third step is to parse the hints using an efficient bit extraction method, and to output the correct label for each point.
Throughout the proof we assume w.l.o.g. that the following terms are integers since we use them as indices: √ N log(N), √ N
log(N) , log(R), log(C). If any of them is not an integer we can just
replace it with its ceil (i.e. dlog(R)e instead of log(R)). This replacement changes these numbers by at most 1, which in turn can only increase the number of parameters or bit complexity by at most a constant factor. Since we give the result using the O(·) notation, this does not change it. Also, note that the width of the network is independent of such terms.
For the first stage, we use Lemma A.2 to construct a network F1 : Rd → R such that F1(xi) ≤ 10rN2δ−1 √ πd for every i ∈ [N ] and |F1(xi)− F1(xj)| ≥ 2 for every i 6= j. We denote R := 10rN2δ−1 √ πd, and we denote the output of F1 on the samples x1, . . . ,xN ∈ Rd as x1, . . . , xN ∈ R for simplicity. We also assume that the xi’s are in increasing order, otherwise we reorder the indices. This concludes the first stage.
For the second stage, we define two sets of integers w1, . . . , w√N log(N) each represented by√ N log(N) · log(C) bits, and u1, . . . , u√N log(N) each represented by √ N log(N) · log(R) bits, in the
following way: For every i ∈ [N ] let j := ⌈ i · √
log(N) N
⌉ and k := i ( mod √ N
log(N)
) . We set:
BINk·log(C)+1:(k+1)·log(C)(wj) = yi
BINk·log(R)+1:(k+1)·log(R)(uj) = bxic . We now use Lemma A.4 twice to construct two networks Fw2 : R → R and Fu2 : R → R such that
Fw2 (xi) = wji and F u 2 (xi) = uji for ji =
⌈ i · √
log(N) N ⌉ . We construct the network F2 : R→ R to
be a concatenation of the two networks, with an additional coordinate which outputs σ(x) (since the inputs xi are positive, this coordinate just output the exact input). Namely, we construct a network such that for every i ∈ [N ] we have
F2(xi) = ( xi wji uji ) ,
where ji = ⌈ i · √ log(N) N ⌉ .
For the third stage, we use Lemma A.5 to construct a network F3 : R3 → R such that for every x > 0, if there exist j ∈ { 0, 1, . . . , ⌈√ log(N) N ⌉ − 1 } such that bxc = BINlog(R)·j+1:log(R)·(j+1)(u),
then:
F3 (( x w u )) = BINlog(C)·j+1:log(C)·(j+1)(w) .
Finally, we construct the network F : Rd → R as F (x) = F3 ◦ F2 ◦ F1(x). We show the correctness of the construction. Let i ∈ [N ], and let y := F (xi). By the construction of F2 and the numbers w1, . . . , w√N log(N), u1, . . . , u√N log(N), if we denote j :=⌈ i · √
log(N) N
⌉ and k := i ( mod √ N
log(N)
) , then we have that: (1) F2 ◦ F1(xi) = ( F1(xi) wj uj ) ; (2)
BINlog(R)·k+1:log(R)·(k+1)(uj) = bF1(xi)c; and (3) BINlog(C)·k+1:log(C)·(k+1)(wj) = yi. Finally, by the construction of F3 we get that y = F3 ◦ F2 ◦ F1(xi) = BINlog(C)·k+1:log(C)·(k+1)(wj) = yi as required.
The width of the network F , namely the maximal width of its subnetworks, is the width of F3, which is 12. The depth of F is the sum of the depths of each of its subnetworks. The depth of F1 is 2, the depth of F2 is O (√ N log(N) ) and the depth of F3
is O (√
N log(N) ·max {log(R), log(C)}
) . Hence, the total depth of F can be bounded by
O (√ N log(N) + √
N log(N) ·max {log(R), log(C)}
) .
The bit complexity of F is the maximal bit complexity of its subnetworks. The bit complexity of F1 is log ( 3drN2 √ πδ−1 ) = log(d) + log(R/3), the bit complex-
ity of F2 is O (√ N log(N) ·max{log(R), log(C)} ) and the bit complexity of F3 is also
O (√
N log(N) ·max{log(R), log(C)}
) . In total, the bit complexity of F can be bounded by
O ( log(d) + √
N log(N) ·max{log(R), log(C)}
) .

heading: A.5 AUXILIARY LEMMAS
text: Lemma A.6. Let a, b ∈ N with a < b. Then, there exists a neural network F with depth 2, width 2 and bit complexity LEN(b) such that F (x) = 1 for x ∈ [a, b] and F (x) = 0 for x > b + 12 or x < a− 12 .
Proof. Consider the following neural network:
F (x) = σ(1− σ(2a− 2x)) + σ(1− σ(2x− 2b))− 1 . It is easy to see that this networks satisfies the requirements. Also, its bit complexity is at most LEN(b), since a < b, hence a can be represented by at most LEN(b) bits.
Lemma A.7. Let n ∈ N and let i, j ∈ N with i < j ≤ n. Denote Telgarsky’s triangle function by ϕ(z) := σ(σ(2z) − σ(4z − 2)). Then, there exists a neural network F : R2 → R3 with width 5, depth 3(j − i+ 1), and bit complexity n+ 2, such that for any x ∈ N with LEN(x) ≤ n, if the input
of F is ( ϕ(i−1) ( x 2n + 1 2n+1 ) ϕ(i−1) ( x 2n + 1 2n+2 )), then it outputs: ϕ(j) ( x2n + 12n+1 )ϕ(j) ( x2n + 12n+2 )
BINi:j(x) . Proof. We use Telgarsky’s function to extract bits. Let x ∈ N with LEN(x) = n, and let i ∈ N with i ≤ n. Then, we have that:
BINi(x) = 2 n+2−iσ ( ϕ(i) ( x
2n +
1
2n+2
) − ϕ(i) ( x
2n +
1
2n+1
)) . (4)
The intuition behind Eq. (4) is the following: The function ϕ(i) is a piecewise linear function with 2i ”bumps”. Each such ”bump” consists of two linear parts with a slope of 2i+1, the first linear part goes from 0 to 1, and the second goes from 1 to 0. Let x ∈ N with at most n bits in its binary representation. It can be seen that the i-th bit of x is 1 if ϕ(i) ( x 2n + 1 2n+1 ) is on the second linear
part (i.e. descending from 1 to 0) and its i-th bit is 0 otherwise. This shows that ϕ(i) ( x 2n + 1 2n+2 ) −
ϕ(i) ( x 2n + 1 2n+1 ) is equal to 2i−n−2 if the i-th bit of x is 1, and this expression is negative otherwise. The correctness of Eq. (4) follows.
Let j, i ∈ N with i < j and denote c := j − i. Using the construction above as a building block, we construct a network which outputs BINi:j(x) in the following way: For ` ∈ {0, 1, . . . , c} define
F` : R3 → R3 to be the neural network, such that for an input ϕ(i−1+`) ( x2n + 12n+1 )ϕ(i−1+`) ( x2n + 12n+2 ) y , it outputsϕ(i+`) ( x2n + 12n+1 )ϕ(i+`) ( x2n + 12n+2 ) y + 2c−`BINi+`(x)
. The network F` is obtained by composing the first two coordinates with Telgarsky’s function ϕ, and then the last coordinate is calculated using Eq. (4). Finally, we define: F := Fc ◦ · · · ◦F0, and we augment the input of F0, such that its last coordinate is zero. The output of F is as required since
c∑ `=0 2c−`BINi+`(x) = BINi:i+c(x) = BINi:j(x) .
Finally, we compute the width, depth and bit complexity of F . Its width is bounded by twice the width of ϕ (which is 2), plus an extra neuron for computing the output y, hence its width is bounded by 5. Its depth is equal to 3(j − i + 1), since we need two layers to compute ϕ and an extra layer to compute the output y. Finally, the bit complexity is bounded by n+ 2, since the largest weight in the network is at most 2n+2.
Lemma A.8. There exists a network F : R2 → R with width 2 depth 2 and bit complexity 2 such that F ((
x y
)) = 1 if x ∈ [y, y + 1] and F (( x y )) = 0 if x > y + 32 or x < y − 1 2 .
Proof. We consider the following neural network:
F (( x y )) = σ(1− σ(2y − 2x)) + σ(1− σ(2x− 2y − 2))− 1 .
It is easy to see that this network satisfies the requirements. It has width 2, depth 2 and bit complexity 2.

heading: B PROOF FROM SECTION 6
text: Proof of Theorem 6.2. We first use Lemma A.2 to construct a network H : Rd → R in the same manner of the construction of F1 is the first stage of Theorem 3.1. This is a 2-layer network with width 1 and bit complexity of O(log(R)). We denote the output of H on the samples x1, . . . ,xN as x1, . . . , xN . Note that by the construction |xi| ≤ O(R) for every i ∈ [N ] and |xi − xj | ≥ 2 for every i 6= j. We now split the inputs to NB2 subsets of size B
2 each, we denote these subsets as I1, . . . , I N B2 (We assume w.l.o.g. that NB2 is an integer, otherwise we can replace it with ⌈ N B2 ⌉ ). For each subset Ik we use Theorem 3.1 to construct a network Fk which memorizes the points in Ik, with the following changes: (1) There is an additional coordinate which memorizes the input and output as is; and (2) The output of the network is added to the output of the network for the previous subset k − 1.
For k = 1, we set this coordinate to be zero. That is, if xi ∈ Ik then Fk ((
xi y
)) = ( xi
y + yi
) ,
otherwise Fk (( xi y )) = ( xi y ) .
Finally, we construct the network F : Rd → R as: F = G ◦ F N
B2 ◦ · · · ◦ F1 ◦H , where G ((
x y
)) = y.
By the construction of each Fk from Theorem 3.1, for every x ∈ R, if |x−xi| ≥ 2 for every i ∈ Ik, then Fk(x) = 0. For every i ∈ [N ], there is exactly one k ∈ [N/B2] such that i ∈ Ik. Using the
projection H , for this k we get that Fk (( xi y )) = ( xi
y + yi
) , and for every ` 6= k we get that
F` (( xi y )) = ( xi y ) . This means that F (xi) = yi for every i ∈ [N ].
By Lemma A.4 and Lemma A.5, since each Fk is used to memorize B2 samples, then its bit complexity is bounded by O ( B √ log(B) · log(R) ) bits, hence this is also the bit complexity of F .
The depth of each component Fk is O ( B √ log(B) · log(R) ) , and there are NB2 such components.
Hence, the depth of the network F is O ( N √ log(B)
B log(R)
) . The width of F is bounded by the
width of each component, which is O(1).

Review summaries:
This paper studies memorization capacity of deep ReLU networks. For arbitrary $N$ data points in a ball of size $r$ satisfying minimum separation $\delta$, the authors show that there exists a ReLU network of constant width and depth $\tilde O(\sqrt{N})$ that perfectly memorizes the entire dataset (Theorem 3.1). This means that memorizing arbitrary $N$ data points can be done using only $\tilde O(\sqrt{N})$ parameters, when depth increases with $N$. Combined with a classical upper bound on VC dimension (Goldberg and Jerrum (1995)), the construction is optimal up to log factors. Theorem 3.1 is extended to the case of fixed depth $L \leq \sqrt{N}$ (Theorem 5.1) and fixed bit complexity per parameter (Theorem 6.2), and these additional results are also optimal modulo log factors.

The paper shows that, under a mild separability condition, the number of connections in a ReLU network required to memorize N data points is of order $\sqrt{N}$ (up to logarithmic factors). This result improves upon the recent work of Park et al. (2021), and matches the previous lower bound. One key proof-technical innovation is pairing _both the input and label informations_ for each partition and encoding them at stage 2, whereas the previous approach focused on the input only. Authors also refine the framework to incorporate the bit-precision constraints, based on which Telgarsky's bit extraction technique can be used.