An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
Authors: Shashank Rajput
Kartik Sreenivasan
Dimitris Papailiopoulos
amin karbasi
Venue: NeurIPS 2021 Poster (2021)
Keywords: Deep Learning
Memorization
Multi-layered Perceptrons

Abstract: It is well known that modern deep neural networks are powerful enough to memorize datasets even when the labels have been randomized. Recently, Vershynin(2020) settled a long standing question by Baum(1988), proving that deep threshold networks can memorize $n$ points in $d$ dimensions using $\widetilde{\mathcal{O}}(e^{1/\delta^2}+\sqrt{n})$ neurons and $\widetilde{\mathcal{O}}(e^{1/\delta^2}(d+\sqrt{n})+n)$ weights, where $\delta$ is the minimum distance between the points. In this work, we improve the dependence on $\delta$ from exponential to almost linear, proving that $\widetilde{\mathcal{O}}(\frac{1}{\delta}+\sqrt{n})$ neurons and $\widetilde{\mathcal{O}}(\frac{d}{\delta}+n)$ weights are sufficient. Our construction uses Gaussian random weights only in the first layer, while all the subsequent layers use binary or integer weights. We also prove new lower bounds by connecting memorization in neural networks to the purely geometric problem of separating $n$ points on a sphere using hyperplanes.

An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
Shashank Rajput University of Wisconsin Madison rajput3@risc.edu
Kartik Sreenivasan University of Wisconsin Madison ksreenivasa204isc. edu
Dimitris Papailiopoulos University of Wisconsin Madison
Amin Karbasi
Yale University amin. karbasi Saaeeiyyleeeee.. edu
dimitris@papail..
Abstract
It is well known that modern deep neural networks are powerful enough mem- orize datasets even when the labels have been randomized. Recently, Vershynin (2020) settled long standing question by Baum (1988), proving that deep thresh-
old networks can memorize n points dimensions using ( + +vn) neurons and (ee//² (d+ vn) + +n) weights, where is the minimum distance between the points. In this work, we improve the dependence on from exponential to almost linear, proving that Ö + /n) neurons and O + n) weights are sufficient. Our construction uses Gaussian random weights only in the first layer, while all the subsequent layers use binary or integer weights. We also prove new lower bounds by connecting memorization in neural networks to the purely geometric problem separating n points on a sphere using hyperplanes.
Introduction
The current paradigm of training neural networks is to train the networks until they fit the training dataset perfectly (Zhang et al., 2017; Arpit et al., 2017). This means that the network is able to output the exact label for every sample in the training set, a phenomenon known interpolation. Quite interestingly, modern deep networks have been known to be powerful enough to interpolate even randomized labels (Zhang et al., 2017: Liu et al., 2020), a phenomenon that is usually referred to as memorization (Yun et al., 2019; Vershynin, 2020; Bubeck et al., 2020), where the networks can interpolate any arbitrary labeling of the dataset.
Given that memorization is a common phenomenon in modern deep learning, reasonable question ask is that of how big neural network needs to be that it can memorize a dataset of points in d dimensions. This question has been of interest since the 60s (Cover, 1965; Baum, 1988; Mitchison Durbin, 1989; Sontag, 1990; Huang et al., 1991; Sartori & Antsaklis, 1991). particular, Baum (1988) proved that a single hidden layer threshold network with O (mmax(n. d)) weights and ([In/d) neurons can memorize any set of n points in d dimensions, as long as they are general position." Baum asked if going deeper could increase the memorization power of threshold networks. and in partieular one could reduce the number neurons needed for memorization (Vyn). While for ReL.U activated networks, Yun et al. (2019) were able to prove that indeed only O( (()n)) neurons were sufficient for memorization using deeper networks, the same question remained open for threshold networks.
'The "general position" assumption of vectors in Rd means that any collection d of these vectors are linearly independent.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Reference
#
Neurons
# Weights
Assumptions
Baum (1988)
([n/d])
Omaxx(n d))
General Position
Huang et al. (1991)
(n)
((d)
None
Vershynin (2020)
Oae log"(n) Vrilog2((n))
O (d vi) (n))
ó-separated, points lie on the unit sphere
logg n + Villog"))
o (d log log I n
Ours, Theorem
ó-separated
5
Table 1: Table comparing the upper bounds for the parameters needed for threshold network to memorize a dataset. General position assumption in IR means that no more than d points lie on a d 1 dimensional hyperplane. Note: log"(n) denotes poly-log factor in n.
Recently, Vershynin (2020) was able answer Baum's 's question in the positive by proving that indeed O(e4/82 + Vn) neurons were sufficient to memorize a set points on a unit sphere separated by distance at least d. Many recent works study the memorization power of neural networks under separation assumptions, e.g., Bubeck et al. (2020); Vershynin (2020); Park et al. (2020). One reason why before Vershynin's is work, it was unclear whether going deeper was helpful for threshold networks was that unlike ReLU or sigmoid functions, the threshold activation function, i.e., ((2) = 1,20. prohibits neurons from passing 'amplitude information' to the next layer.
Although the dependence of ((vn) on the number of neurons was achieved by the work of Vershynin, it is unclear that the exponential dependence on distance and the requirement that the points lie on sphere fundamental. this work, we lift the spherical requirement and offer an exponential improvement on the dependence on 8.
Theorem 1. (Informal) There exists threshold neural network with Ô (} + Vn) neurons and ( + n) weights that can memorize any 6-separated dataset of size n in d dimensions.
Please see Definition 2 for the formal definition of ò-separation; informally, it means that all the points have bounded norm and distance of at least d between them. Comparing the theorem above with Vershynin's 's result, we see that firstly we have reduced the dependence on ó from exponential to nearly linear; and secondly, in our upper bound for the number of weights, the å and n terms appear in summation rather than product (ignoring the logarithmic factors). Further, note that Vershynin (2020) needs the points to lie on a sphere, whereas we only need them to have a bounded (2 norm. We have compared our results with the existing work in Table 1.
Our construction has Olog log layers, of which only the first layer in our construction has real weights, which are i.i.d Gaussian. This layer has O (log neurons and O dddlog)) weights. All the other layers have integer weights which are bounded and are on the of order Óllog)).
Baum (1988) also proved that there exists dataset of points such that any threshold neural network would need least [n/d] neurons in the first layer to memorize it. However, the distance for this dataset is (1/n)).² Later, Baum & Haussler (1989) proved VC-dimension bounds which imply that min Vī, n neurons are necessary in a network to memorize a dataset of n points in d dimensions, and this bound is independent of the minimum distance 6. Our upper bound (Theorem 1) shows that if 8 (2n1/n), then we memorize with only O log neurons in the first layer. To complement our upper bound, we introduce a new, ö-dependent lower bound below:
de [ (t) such that any
Theorem 2. (Informal) There exists a d-separated dutaset of size n
threshold network that can memorize it needs J
neurons in the first layer.
The rest of the paper is divided into 7 sections. In Section 2, we provide the related works for memorization using neural networks. We provide definitions and notation in Section 3 and our main results in Section 4. Then, we briefly explain the constructions of our upper bound in Section 5.
Herr, we have rescaled the dataset to have maximum norm of any sample to be 1. This is done to make the dataset consistent with our minimum distance definition (see Assumption 2). The assumption in Park et al. (2020) also uses this kind of normalization.

---

Before exploring lower bounds for threshold networks, we provide sharp bounds on the minimum parameterization needed for any model (not necessarily neural network) to memorize d-separated dataset, in Section 6. We discuss our lower bound for threshold networks in Section 7. Finally, we conclude our paper with a brief conclusion in Section 8.
2 Related works
Memorization with threshold activation. There a rich history of research into the memorization capacity of threshold networks. Baum (1988) showed that a single hidden layer network with ((max(n, d)) weights and ([n//d) neurons are sufficient to memorize dataset, if the samples are in general positions. Baum also provided an instance of a dataset, where any threshold based network aiming to memorize the dataset would need at least [n/d] neurons in the first layer. However, the construction was such that ò scaled inversely with n. In this work, we show that for any minimum distance < S 2. the number of neurons in the first layer can be much smaller. Baum also proved, using the Function Counting Theorem (Cover, 1965), that (n/ log n) connections needed in any neural network that aims to memorize points in general position, regardless of the minimum distance.
Huang et al. (1991) and Sartori & Antsaklis (1991) proved that threshold networks could memorize any arbitrary set of points, that is, the points need not be in general position. However, these results needed (n 1 weights and n - neurons in the networks for memorization. Mitchison & Durbin (1989) and Kowalczyk (1997) provided upper and lower bounds when the requirement of memorizing the dataset exactly was relaxed to allow recall error of up 50%. Sontag (1990) provided evidence that suggested that adding skip connections can double the memorization capacity of single hidden layer networks. Kotsovsky et al. (2020) extended Baum's result to multiclass classification setting, using bithresholding activation functions.
Recently, Vershynin (2020) was able to show that O neurons are sufficient to memorize a set of points on the unit sphere, separated by distance of at least 8. This answered the question by Baum (1988), which was whether the number of neurons could be reduced to O(vn) by considering deeper networks. Note that Vershynin's 's and Baum's 's assumptions are fundamentally different and neither is stronger than the other. For example, Baum's 's construction would still need only O O(max(n, d)) weights even if the points are infinitesimally close to each other, whereas Vershynin's 's construction would grow as 5 decreases. On the other hand, Vershynin's 's construction works even if all the points lie a low dimensional hyperplane, whereas Baum's general position assumption would get violated in this situation. Note that naïvely extending Baum's construction the case where the points lie on very low dimensional hyperplane would result (nd) weights and (n) neurons?, which is identical to the bounds by Huang et al. (1991).
weights and (Ee2/6"
Memorization with ReLU and sigmoid activation. Due to the popularity of the ReLU activation function, there has also been an interest in their memorization capacity. Zhang et al. (2017) proved that single hidden layer ReLU network with 2n + d weights and n neurons can memorize n arbitrary points. Hardt & Ma (2017) proved that ReLU networks with residual connections also need only (n) weights memorize n points. Yun et al. (2019) were able to prove that for ReLUU, in fact, one needs only ((yn) neurons to memorize n points. Quite interestingly, the construction by Vershynin (2020) works for both threshold activated networks (as described above) as well as ReLU activated networks; and gives the same bounds for both architectures. Bubeck et al. (2020) show that under some minimum distance assumptions, ReLU networks can memorize (even real labels) with O(n/d) /d) neurons such that the total weight (Bartlett, 1998) of the network is ((v),, which is proved to be optimal for single hidden layer networks. Huang (2003) proved that a two-hidden layer network with O( (V))) sigmoid activated neurons suffices to memorize points. Recently, Park et al. (2020) have shown that ReLU or sigmoid activated networks with only Onn//3 + log(1/5)) weights are sufficient to memorize n points separated by normalized distance of 6.
Over parameterization and generalization. A large body of recent work attempts to explain why large neural networks, which are capable memorizers, can also generalize well, e.g., Neyshabur et al. (2018, 2019); Belkin et al. (2020). In this work, we only study memorization, and omit any discussion about generalization. We do not believe our results explain anything about generalization.
3 Pllease Appendix A for a detailed explanation.
3

---

3 Preliminaries
In this work, will consider feed forward neural networks 124 {0, of the form W2-20(.... +
((x) = olb + w[o(bb-1 + W WL-10(bL-2
where o-) is the threshold activation. The network has L layers, with the last layer consisting of single neuron with bias ,y E and weight vector w.. For any other layer its bias vector b, and weight matrix is W, We use the notation [n] to denote the set [I....,mI.
We formally define memorization follows:
Definition 1. A learning algorithm A can memorize dataset of feature vectors DD = {x, if for any arbitrary labeling {ys Vi of the dataset, the algorithm can output model f such that Vi E [m] f(z)) Vi-
For instance, could be the training procedure for particular neural architecture and f could be the neural network that A outputs after the training process. For neural networks, we will abuse the notation and say that neural network f can memorize dataset D { for every arbitrary labeling {ys / of the dataset, we can find a set of weights and biases for the network so that Vi E [n] fx;) = yi-
We are mainly interested the minimum size of a threshold network so that can memorize a dataset of samples. Our only assumption the dataset will be that of d-separation, which we define below.
Definition 2. We say that a dataset 8-separated if it satisfies either Assumption I or Assumption Assumption 1. (Angular separation) All the feature vectors in the dataset, {x:3/==1 satisfy
arecos
T [b
Assumption 2. (Normalized minimum distance) (alttaceeAAAr All the feature vectors in the dataset, {a,) satisfy [ < and
Vi Vi j - - x, -x, 2 6.
Remark 1. Note that the 'normalized' the name of Assumption maximum norm of any point in the dataset is bounded by 1. Our results can be easily extended to any other bounded dataset by rescaling the weights and biases of the first layer appropriately. Park et al. (2020) also use similar normalized distance assumption.
refers to the fact that the
Note that if the points lie on the unit sphere, like in Vershynin (2020) or Theorem in this paper, then both assumptions are roughly equivalent.
We use the lower case letters for scalars (w), lower case bold letters for vectors (w), and upper case bold letters for matrices (W). We denote the i-th element of vector w as w,, similarly for the case when the vectors have subscript, we denote the i-th element of wy by Wy,i. We use a tilde over (-), 22()) and ((.), i.e. O()). and ((-), to hide the logarithmic factors.
Notation:
Main results
As discussed earlier, the existing result by Vershynin (2020) has exponential dependence on 8. In this section, we provide a new and tighter upper bound on the number of weights and neurons needed for memorization, which brings the dependence down almost linear. Our result is stated below:
Theorem 1. There exists threshold activated neural network with 1oog"" Vo n) neurons and O (d+tog n) logn no n) weights that can memorize any dataset of size in d dimensions that is 5-separated.
In this construction, only the first layer has real weights. The rest of the network has binary and integer weights. In particular, the O(n log" n) term in the number of weights comes from binary and integer weights (with the integers being bounded and the order of O(log n.).. Hence, the O(n log" n)

---

lagus
indicator
Compression wsing linear codess
Down-project layer
Sparse athnetwork
Up- Up-prejection layer
Menorrioingg vi each nouron
Output
Copy a (2)
e E (0, (p
2 (0, (0,1)0045)
2
20 (0, 13OlUhlinh
R
Figure I: The schematic of the neural network that can memorize any 8-separated dataset size n in d dimensions (Theorem 1). The first layer has random Gaussian weights and projects the input from F down to {0, 1] O log The next component a sparse subnetwork that further compresses the vectors from {0, 1] O ing to f0, 10.113 ()oggg))) using linear codes. The next couple of layers lift the vectors from (0, (0(0gg))))))
{0, 1) log" while ensuring that size v that are linearly independent. Finally, we use this linear independence to memorize up to /n log" n points with a single neuron. This gives us a layer of size /n that can memorize the entire dataset. The final layer is just single neuron that sums the outputs of these /n neurons.
find sets of vectors of
weights can actually be represented by On log" log log bits. We will in Section 6 that M(n) bits are necessary for memorization by any model and hence this term is optimal, up to logarithmic factors. The d'logn weights in the bound are the weights of the first layer which has width log for which later, in Theorem 2, we will provide some indication that this factor might also be necessary,
Baum (1988) had constructed a dataset with normalized minimum distance O(1/n) and proved that for this dataset, any threshold network aiming to memorize this must have [n/d] neurons. We introduce a new, 5-dependent lower bound below:
Theorem 2. For every 0 < 8 1 and some universal constants C1 and C2 there exists a dataset of size E Cid log (d/5)
(
satisfying the ô-separation condition such that any threshold
network that can memorize it needs (v31og(118) neurons in the first layer.
Note that the dataset in this theorem actually satisfies both Assumption 1 and Assumption 2, to constant factor. To understand the implication of Theorem 2 bit better, consider two dataset D, and D2, both containing n points on the sphere. We assume that Dj has -s-sparatio and D2 has by-separation, where 81 (n--2/d and 6, (dd /n). Then, Theorem says that there exists network that memorize Dj with only (n n.) neurons in the first layer, whereas Theorem says that any network aiming to memorize D₂ would need least 52( ((/T/d) neurons in the first layer. Hence, we see that the minimum distance can have big impact on the network architecture
Comparing Theorems and 2, bound of (118)) neurons, whereas Theorem 2 proves lower bound of 52(1/ (8) neurons. We think that the gap is an artifact of the proof of Theorem 2, and tighter analysis or a better construction could result in lower bound of Q(1/5) neurons, which will match the upper bound of Theorem 1. However, this is just speculation based on intuition, and more research will needed to answer this open question.
that there is gap in the bounds: Theorem 1 proves upper
5 Memorization with threshold networks
In this section, we give proof sketch of Theorem the complete proof provided in the appendix. We will construct network that can memorize any d-separated dataset. As we discussed before,
5

---

the threshold activation prohibits the passing of amplituee information to deeper layers. This is the biggest obstacle in leveraging the benefits of multiple layers of transformation that can be obtained by networks with activations such as ReL.U. In the following, we will explain our construction layer-wise:
Step I: Generating unique binary representations. Given that the amplitude information is lost after thresholding, we want to ensure that at the least, the first layer is able to transform the inputs into binary representations such that each sample in our dataset has unique binary representation. Later, we will see that this is sufficient for memorization.
Now we give an overview of how a layer with O (Log)) neurons with random i.id. weights can convert the input into unique binary vectors of length O logn), ). In this sketch, we will do this under Assumption I, but the same technique can be extended for Assumption 2.
The key result use is that any hyperplane passing through the origin, with random Gaus- sian coefficients has at least a 6/2m probability of separating two points which have an angle of at least 5 between them. To see how this is true, consider two points æ; and æ; with an angle between them. Consider the 2-dimensional space spanned by these two vectors. Note that the intersection of the Gaussian hyperplane with the 2-dimensional space spanned by æ; and æj is just a line passing through the origin. Further, because the Gaussian hyperplane has isometric coefficients, it can be shown that the line has angle uniformly distributed in [0, 2T). This implies that the probability that this line passes in between the two points is at least 8/2T. If we take m such independent Gaussian hyperplanes, then the probability that none of them separate a pair Φ;, 2 is less than (1 - 6 ym Finally, taking simple union bound over the (*) pair of points, shows that the probability that at least one pair has no hyperplane passing in between them is at most
n 2
5 m
1
2r:
c
2T
We want this to be less than 1 to show that there exists one set of hyperplanes which can separate all the pairs. Doing that gives us m = 00 () which is our required bound.
For any input 2;, each threshold neuron in the first layer outputs either 1. We can concatenate the outputs of all the neurons in the first layer into binary vector. Let us denote this binary repre-
Figure The probability that uniformly random line pass- ing through the origin passes in between æ; and æt is 8/2m.
sentation of x; created by the first layer (1) for 1,..., n.
Further, denote the dimension of 2(" by d()), which is equal to the number neurons in the first layer, that is, (1)) O log
Step 2: Compressing the binary representations to optimal length. In order to avoid a factor in the later layers, our next task is to further compress the O (ang)) dimensional vectors returned by the first layer into vectors of length (logn). Note that Ollog n) length is optimal (up constant multiplicative factors) if we want to represent the n samples uniquely using binary vectors. For this will use linear codes where we simulate XOR operations by threshold activations.
Consider two d()) dimenniooal binary vectors z(") and 2 that differ in at least one bit. Let i represent the XOR operation. Let b be a random binary vector of length d()) where each bit is i.i.d Bemoulli(0.5). Then, we claim that
Pr((<("),)) b) + (z15" () 0.5,
where (z, b) (#1 (1) @ ..... (Zgm) bgw))
For the ease of exposition, assume that x!!) and z differ in only the first bit (the proof of the
general case is provided in the appendix). Let the first bit of 2 be 0, and that of 25") be 1, and we
have assumed that the rest of their bits are the same. Let c == (=(12 b2) @ ...... e (2)) baay) =
(1)

---

(2/,2 b2) @ ... (23,a0> bat)). Then,
Pr((z!) b) # (2/) b) = Pr(((0- b)) + + ((1 b1) @c)).
It can be verified that if b1 1, then ((0- b1) @c) # ((1 bn) @ c). Since Pr(bi 1) 0.5, we get the desired result.
We have shown that the probability that one such random vector b differentiates between pair 2; and 2) with probability 0.5. Doing an analysis similar to the one that we did for the first layer, we get that m (log v) vectors suffice to separate all pairs. The big task here, however, is to implement the XOR operation using threshold activations. In the appendix, we show that this can in fact achieved using couple of sparse layers.
Similar to the output of the first layer, let us denote the compressed binary representation of 2; created by these sparse layers z[(), for ,,..., Further, let 2!?) have dimension d(2), where d(2) (log rt), we showed above.
Step 3: Partitioning the samples into subsets of size lognnog)). Once we have d Ologn) n) length binary representations of the inputs, memorizing with single layer con- sisting of (d(2) + 1)n weights and n neurons duce the number of neurons to (Vvn logllog logn). For that, we use a strategy similar to Yun al. (2019):
difficult. However, our aim is re-
will memorize up K samples with 1 neuron, where K [( log n). Thus, we will need only O(vn) neurons in total. Roughly speaking the strategy would be the following: Let's say we have a neuron o(w 2 ++ ++b), b). Then, if for any (Vi...., 3KK E [0, all of the following equations hold at the same time,
can find a w and b such that
1 +1
w 21 91
w zK + Уk: (1)
then this neuron can memorize the K samples (21, 21,..... 2x]. To do so, need that the vectors 31,
K
=k] be linearly independent Since we have K = 2(nn l)., require that 2, ''s have dimension at least K. However, the previous few layers have com- pressed the samples into d(2) = (log n.) length binary vectors. Thus, the next task is to project these 2(22 length binary vectors to (2(K) length binary vectors. Note that first compressing down to (logn) n) length vectors and then expanding these up to !2( [ log length binary vectors seems counter intuitive. However, we were unable project the vectors directly nary vectors without incurring a large dependence on 5 and in the number of weights and neurons.
((3)
2(vn log length bi-
(2)
One more objective that we accomplish while projecting up to ((K) dimension is that both the projection and memorizing the resulting vectors can easily done with bounded integer weights. The way do this is by parti- tioning the vectors 2(2) into K subsets of size at most vn each. We prove that can find such K subsets, such that each characterized by a unique prefix, which all the elements of that subset share. These prefixes ensure that we can easily detect which subset particular zi²² belongs to, using threshold neurons. For more details on this, please refer the appendix.
Figure 3: In Step 3, x; (2)
is copied to a
location in 2, (3) depending the subset (2) belongs.
S₁ to which z,
*Yun (2019) also use this strategy. However, as will see in Step 4, are able to ensure that vectors (z),.... zk² } are linearly independent while also ensuring that their coordinates do not overlap. This helps us find vector which has integer values and satisfies (l). Further, since Yun et al. (2019) use ReLU activations, the way they achieve linear independence, and the construction of the rest of the network is different.
7

---

Let (Si...., Sk) denote the K subsets, each with unique prefix. Let 2, E {0, 1) 1]dd)) be the binary vector returned by Step above for input a., We mentioned above that by using threshold neurons,
we can create a vector s () E {0, for (2) such that šijj = 1 if and only if ESj. Then, using these prefixes and threshold neurons, we can create the expanded binary vector 2
(3) E {0. (1)
corresponding to the vector =,(²) The way create z/ from xx(²) is as follows: 2, is partitioned
(3)
into K chunks of length d(2) + 1. If 2! (2) E Sj. then the first bit of the j-th chunk is set to 1 and =!?)
copied the rest of the bits in that chunk. All the other bits in 2[(0) are O. This is shown in Figure 3. This operation can be done with threshold activated neuron, for details please refer to the appendix.
Step 4: Memorizing the samples with vn neurons key property about the vectors 2, 2 is that if we take K such vectors, each belonging to different subset Sj. then they will be linearly independent their coordinates do not overlap. Thus, we can find wr and such that (1) is satisfied. Furthermore, due to the fact that these K vectors have different supports, we can manage to satisfy (I) with w which have integer elements on the order of Olog n²).
Hence, we can memorize up to K samples with one neuron. This gives that we need vn in the second-to-lass layer memorize all the samples. The final layer is simply single neuron that sums the outputs of the second-tt last layer.
Note that threshold neuron can be approximated using three ReLU neurons. Hence, the construction described this section can also used to create a ReLU activated network with can memorize the same dataset.
5.1 Extending the construction to multiple class memorization
The construction above can be easily extended to the case when there are more than two classes. Let there be M 2 2 classes. Then, the label for each sample can be represented as sequence of loga M bits. this case, we can replicate the construction the last and the second-to-las layers log, M times so that the new network has log, M output neurons, each output neuron memorizing one bit of the label. Hence, we get the following Corollary:
Corollary 1. There exists a threshold activated neural network with O (l + vT((lo" (log M))
neurons and O (d+tog n) log" + n(log² nlolog M)) weights that can memorize any M M-class dataset size in d dimensions that is d-separated.
6 Bit complexity of memorization
Before understanding the minimum size that threshold networks have to be in order to memorize dataset, a more fundamental question is how many bits are needed to specify the models output by any learning algorithm that aims to memorize dataset. In this section, we provide two theorems that sharply characterize the bit complexity needed for memorization. The results provide the bounds in the terms of two very related quantities, the packing number and the covering number, which we define below.
Definition 3. Given real number ö O, the packing number Ps of a set S (equipped with norm ||. I)) is defined as the cardinality of the largest set X C S such that
VaL, x2 E X ||
x2ll 26.
Intuitively, the packing number is the maximum number of 8/2 radius non-overlapping balls that one can fit inside set.
Definition 4. Given a real number > O, the covering number Cs of a set S (equipped with norm ||- (I) is defined the cardinality of the smallest set X C such that
Yx E S, 3& E X || - 1 =
Intuitively, the covering number is the minimum number of radius (possibly overlapping) balls that one needs to completely cover a set.
8

---

These quantities are very useful in quantifying the "size' of a set. These are related to each other through the following relation (Vershynin. 2018, Lemma 4.2.8):
P28 S Ca Ps.
Now, we are ready to state the upper and lower bounds on the bit complexity of memorization.
Theorem 3. Let S be a set from which we select the samples. Let A be a learning algorithm that can memorize any dataset of feature vectors D E S as long as every pair of feature vectors Ri, 22 E DD satisfies || - 22 6. Then, we need least max(n, log, logg Ps) bits to represent the models output by A.
Theorem 4. Let be a set from which we select the samples. Then, there exists a learning algorithm A that can memorize any dataset of feature vectors D E S as long as every pair of feature vectors 3s 2. E DD satisfies ||æ;; - 3z 2 and the models returned by A can be represented in O( + log2 log2 C8/2) bits.
Note that since a + b = (max(a, Theorem 4 is of the same order as the lower bound from Theorem 3.
a. b)) for non-negative variables a and b, the upper bound from
It is known that the packing and covering numbers of the unit sphere are of the order ((CC and @(CC//6)4 for some universal constants Gp and Ce respectively. Substituting this into Theorems and 4, we get the following corollaries.
Corollary 2. Let 8d-1 be the unit sphere in TRd. Let A be learning algorithm that memorize any set of n points on 5d-1 as long as every pair of points F;, D. E 'D satisfies || - x.yl 2 Then, we need !2 (max((, log d + log log })) bits to represent the models output by A.
Corollary 3. Let Sd-1 be the unit sphere in Rdd Then, there exists a learning algorithm A that can memorize any set of n points on Sd-1 as long every pair of feature vectors Bi 3.j D satisfies |ac; æ2 6, and the models returned by A can be represented in O + log d log log ! bits.
Note that if we have a set of n points on the unit sphere separated by at least distance 8, then the set satisfies both Assumption 1 and Assumption 2. Hence, these two corollaries give bounds on the bit complexity of memorization under both the 5-separation assumptions.
Lower bound construction
x +
For our lower bound construction, we will have n points on the unit sphere in d-dimensions. Each neuron the first layer represents hyperplane in d-dimensions. The main observation that we use is that for every pair of points æ; and æj such that they have different labels, there should be hyperplane passing in between them. Thus, we aim to lower bound the minimum number of hyperplanes needed for this to happen. This is related to the problem of having to separate every point using hyperplanes, that is, the problem where we need to ensure that there is hyperplane passing in between every pair of points x; and vy. For this problem we have the following theorem.
Theorem 5. For every 0 S 1 and some universal constants C₁ and Cz there existy set of points the
In this figure, the black dots represent the cluster centers and the blue circles represent the samples in a cluster. In high dimensions, the points in each cluster get concentrated within distance ((/8/d) in any direction. Hence any hy- perplane, that wants to separate constant fraction of the points in a cluster, needs to pass within distance O( / //d) of the cluster center, as shown in the figure.
Figure 4:
d-dimensional sphere, with n E such that each pair of points is separated by a distance of at least 8, and one needs ? to separate them.
C.d2 log" (d/8) (C#)
log
hyperplanes
vā
log
We use essentially the same construction for both the problems. On the sphere, first we sample /n points uni- formly at random, which we call cluster centers. Around

---

each of these centers, we sample vn points uniformly at random from the cap of radius vó, and call these sets of points clusters. Hence, total we sample points on the sphere and it can be shown that with high probability these will all be at least distance away from each other as long as 6472 In high dimensions, it can be shown that for each cluster and in any direction, most
n
points lie within distance v0/d of the cluster center. Hence, if hyperplane aims to 'effectively' separate pairs of points cluster, needs pass within distance / of the cluster center. It can also be shown that in high dimensions any hyperplane can only pass within distance v of the cluster centers of v fraction of the clusters. Finally, we use the following necessary inequality to get a bound on the required number of hyperplanes:
(# hyperplanes needed)
(# clusters) (# hyperplanes needed per cluster)
(# clusters hyperplane can "effectively" separate)
We know that the number of clusters is vT,, and we showed above that (# clusters a hyperplane can 'effectively' separate) is vó fraction of the clusters, that is O(vno). Finally, for the term (# hyperplanes needed per cluster), where we need to separate points with opposite label. For the problem of separating every pair of points, we know that (# hyperplanes needed per cluster) = fo(log2 vn) since there /ni points in each cluster and hence we need at least log2 vnn hyperplanes per cluster. Substituting these values gives the bounds in Theorems 2 and 5.
for the memorization problem,
Note that we skipped many details the sketch above. The complete proof is provided in the appendix, and the construction there is slightly different.
8 Conclusion
In this work, we study the memorization capacity of threshold networks under the 5-separation assumption. We improve the existing bounds on the number of neurons and weights required, from exponential in 6, to almost linear. We also prove new, 5-dependent lower bounds for the memorization capacity of threshold networks, that together with our upper bound, shows that ō (the separation) indeed impacts the network architecture required for memorization.
Acknowledgments and Disclosure of Funding
DP acknowledges the support of NSF CAREER Award #1 144499,, Sony Faculty Innovation Award, AFOSR & AFRL Center of Excellence Award FA9550- 18-00-18---1166 NSF TRIPODS Award #1740707, and ONR YIA Grant N00014-21-1-222 I1S-184 and ONR Grant N00014-19-1-240.
AK acknowledges the support of NSF CAREER Award
References
Devansh Arpit, Stanislaw Jastrzębski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et closer look at memorization in deep networks. In International Conference Machine Learning, pp. 233-242.
PMLR, 2017.
Peter I. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525-536, 1998.
Eric B Baum. On the capabilities of multilayer perceptrons. Journal of complexity, 4(3):193-215 1988.
Eric B Baum and David Haussler. What size net gives valid generalization? Neural computation, (1):151-160, 1989.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4):1167-1188) 2020.
10

---

Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and weights size for memorization with two-layers neural networks. arXiv preprint 1xXiv:2006.02855, 2020.
Thomas Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE transactions electronic computers, 1965.
Moritz Hardt and Tengyu Ma. Identity matters in deep learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE transactions on neural networks, 14(2):274-281, 2003.
Shih-Chi Huang. Yih-Fang Huang, et al. Bounds on the number of hidden neurons in multilayer perceptrons. IEEE transactions on neural networks, 2(1):47-55, 1991.
Vladyslav Kotsovsky, Fedir Geche, and Anatoliy Batyuk. Bithreshold neural network classifier. In 2020 IEEE 15th International Conference Computer Sciences and Information Technologies (CSIT), volume 1, pp. 32-35. IEEE, 2020.
Adam Kowalczyk. Estimates of storage capacity of multilayer perceptron with threshold logic hidden units. Neural networks, 10(8):1417-1433 1997.
Shengchao Liu, Dimitris Papailiopoulos, and Dimitris Achlioptas. Bad global minima exist and sgd can reach them. Advances in Neural Information Processing Systems, 33, 2020.
GJ Mitchison and RM Durbin. Bounds on the learning capacity of some multi-layer networks. Biological Cybernetics, 1989.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of pveepaarametiizttionn in generalization of neural networks. In International Conference Learning Representations, 2018.
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. Towards un- derstanding the role of peeemttrametinntoooon in generalization of neural networks. In International Conference on Learning Representations (ICLR), 2019.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. arXiv preprint arXiv:2010.13363, 2020.
Michael A Sartori and Panos J Antsaklis. simple method derive bounds on the size and train
multilayer neural networks. IEEE transactions neural networks, 2(4):467-471, 1991.
Eduardo D Sontag. Remarks interpolation and recognition using neural nets. In NIPS, pp. 939-945. 1990.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. SIAM Journal on Mathematics of Data Science, 2(4):1004-1033 2020.
Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis memorization capacity. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 15532-15543, 2019.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Please refer to the Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "pd1c0unPjkr", "reviewer": "Reviewer_1QCv", "summary": "This paper considers the problem of memorizing n data examples in R^d using deep threshold networks. It is proved that, if the dataset is delta-separated (either in angle or in l2 distance), then for any labels, there exists a threshold network with O( (log(n)^2/delta) + sqrt{n}log(n)^2) neurons and O( (d+log(n))log(n)/delta + nlog(n)^2) weights that can memorize the dataset. This improves prior rates which either depend linearly on n or exponentially on 1/delta. Additionally, this paper also studies bit and neuron complexity, and particularly it is proved that there exists a delta-separated dataset with n examples which requires Omega(log(n)/sqrt{delta}) neurons to memorize.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies a fundamental problem, the number of neurons needed to memorize a given training set. I think the paper is clean and well-written; I appreciate the explanation of the proof ideas. There are some interesting ideas: while it seems standard to use Gaussian random vectors on the first layer to separate the training examples, as far as I know, it is a novel idea to compress the binary representations using XOR (implemented by a threshold layer). The idea to partition the dataset into subsets of size O(sqrt{n}log(n)) and learn each of them using a single neuron, and the construction in the lower bound are also interesting. \n\nUpdate: Thank you for your response. I decide to increase my score to 7.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think it would be nice to include more comparison with prior results. \n(1) Baum's construction requires n/d neurons, which is larger than sqrt{n} only when n>d^2. Even though the data assumption is different, it is still interesting to discuss the case where n<d^2.\n(2) On line 233, it is mentioned that Yun et al. (2019) used a similar strategy; what are the differences?\n\nHere are some typos:\n(1) On line 88, \"Veshynin\" should be \"Vershynin\".\n(2) On line 261, it seems that s_i^{(2)} should have dimension K instead of d^{(2)}.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "mM4NZ-jToC", "reviewer": "Reviewer_JGb5", "summary": "The paper considers a feed-forward neural network that takes inputs in $\\mathbb{R}^d$ and outputs binary labels. The neural network has $L$ layers, with each layers consisting of a bias term and the activation function is the threshold function. The paper considers the following question: What is the minimum size of a threshold network so that it can memorize a dataset of $n$ samples in $\\mathbb{R}^d$. Memorization refers to learning the parameters of the threshold network so that it can accurately output labels of the $n$ samples, for any arbitrary labeling.\nThe paper shows that a deep threshold network can memorize $n$ points in $d$ dimension using $O(\\frac{1}{\\delta} + \\sqrt{n})$ neurons $O(\\frac{d}{\\delta} +n)$ weights (up to log factors), where $\\delta$ is the minimum distance between the points (considered in angular metric and $\\ell_2$-metric). ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well written and pleasant to read. Bulk of the paper rests on the theoretical exposition. The paper provides a good description of prior work. I did not go through the theoretical proofs from the supplementary material in detail, however the proof sketch from the\nmain paper provides sufficient intuition. \n\nThe work on the paper is incremental and provides an improved dependence on the $\\delta$ for memorization using deep threshold networks. The improvement is from previously shown exponential dependence of $O(e^{1/\\delta^2} + \\sqrt{n})$ neurons and $O(e^{1/\\delta^2}(d +\\sqrt{n}) + n)$ weights to almost linear dependence on $\\delta$ of $O(\\frac{1}{\\delta} + \\sqrt{n})$ neurons $O(\\frac{d}{\\delta} +n)$ weights. Is the $O(\\frac{1}{\\delta})$  and $O(\\frac{d}{\\delta})$ dependence on $\\delta$ fundamental or can it be improved further? A discussion on this would be helpful for the readers to gauge the importance of the result presented in the paper.\n\nThe work by [Veshynin, 2020] that showed the exponential dependence $\\delta$ and $O(\\sqrt{n})$ dependence on $n$ applies to both ReLU activation network and hard threshold activation network. Is the result presented in the current paper transferable to ReLU activation network? Is a similar dependence on $\\delta$ expected there? A discussion on this would be useful as ReLU activation function are common and easy to implement in practice.\n\nThe paper constructs the threshold activation network with random weights on the first layer and subsequent layers have integer (binary) weights. Comments on whether integer restriction can be relaxed and still achieve similar performance on memorization would be useful.\n\nThe paper considers binary labeling. Comments on memorization problem with multiple labels (more than 2) would be useful as classification problems can have multiple labels. \n\nThe goal of learning a networks for classification is generally to use the learned network to correctly label points the network was not trained on. The paper does not address this issue but to state this in passing. A section detailing limitation of the work would be useful.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work does not have any immediate negative societal impact. Limitation of the work is not addressed with sufficiently. See main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "FANaOlYFunU", "reviewer": "Reviewer_Dgbz", "summary": "This paper studies the memorization capacity of deep threshold networks, and provides a significant improvement over previous work. For $n$ points in the $d$-dimensional unit ball with at least $\\delta$ separation between any two points, it is proved that a threshold network with $\\tilde{O} (\\frac1\\delta + \\sqrt n)$ neurons and $\\tilde{O} (\\frac d\\delta + n)$ weights can memorize them. The previous best result (Vershynin, 2020) has an $e^{1/\\delta^2}$ dependence in these bounds, and thus the current paper provides an exponential improvement. This paper also provides a lower bound saying that for $n$ in a certain range, the required number of neurons in the first layer must be $\\tilde{\\Omega}(1/\\sqrt\\delta)$, though this does not match the upper bound in the paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The contribution is original and provides a clear improvement on a theoretical problem studied in the past. The discussion of related work is sufficient.\n\nQuality: The paper is technically sound. The theoretical results are clearly stated, and proof sketches are given in the main text.\n\nClarity: The paper is clearly written and well organized. The proof sketches are easy to follow.\n\nSignificance: Although the memorization power of neural networks has been studied for decades, the significance to the current practice is unclear, because the existence of a network to interpolate datapoints doesn't mean that such network can be found efficiently (almost always the theoretical constructions are different from the ones actually algorithmically found), let alone saying anything about generalization. In addition, the threshold activation is not practically adopted, to the best of my knowledge. That said, from a pure theoretical perspective, this paper studies an existing well-formulated question and obtains a strong improvement. I find the construction in this paper very neat.\n\nOther comments:\n- I find it a bit weird to define memorization in terms of a learning algorithm (Definition 1), since it's really just about the existence of a neural network.\n- line 308: The packing/covering number should be $\\Theta((C/\\delta)^d)$ for some constant $C$. Though it doesn't matter after taking logarithm.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors perhaps could discuss what should be the right dependence on $\\delta$, since there is a discrepancy in the upper and lower bounds provided.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "6wH1xJoR-JJ", "reviewer": "Reviewer_JEGY", "summary": "This paper considers the memorization of data using deep neural networks and aims to minimize both the number of neurons and the number of connections in the network, where the activation function is a step function. \nThe main result is a construction of a deep and relatively sparse network that memorizes arbitrary labels of 'well-separated' data sets.\nIf the size of the data set is $n$, the number of neurons in the network is proportional to $\\sqrt{n}$ plus a linear dependence on the well-separateness parameter.\nThis is an exponential improvement over a recent result of Vershynin (which itself generalized a classical result of Baum from the 80's), which had an exponential dependence on the well-separateness parameter.\nThe authors also complement their work by proving some lower bounds, which, in particular, show that some polynomial dependence on the well-separateness parameter is necessary.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper considers a well-established line of work concerning the memorization capacity of neural networks. The case of deep networks is particularly relevant and interesting. I find the construction introduced in the paper to be both intuitive and non-trivial. \nIt goes through a well-thought compression scheme followed by a separation procedure.\nThe compression allows to keep the network size small, and the separation procedure allows to memorize arbitrary labels.\nThe ideas are rather elegant and might even be of further use in other scenarios.\n\nMoreover, the paper is particularly well written and does a pretty good job at introducing the relevant ideas and motivations.\n\nGiven the above, I am confident that this paper will be of interest to the NeurIPS community and am happy to recommend acceptance.\n\nI would still like to raise a few questions/suggestions which I hope the authors can respond to:\n\n- Line 22: This is completely nitpicky and is actually a matter of opinion, but I would say that the question of memorization can be tracked down to the 65' paper of Cover (in which he basically considers a network with a single neuron).\n\n- Line 46: \"...the $\\delta$ and $n$ terms appear in summation rather than product...\". I was slightly confused by this sentence since the same is also true for the bound proved by Vershnyn for the number of neurons. So maybe it would be better to say your specifically referring to the bound on the number of weights.\n\n- The construction provided in the paper uses a deep network whose depth depends both on $n$ and on $\\delta$. This is in contrast to Vershynin, which, as I remember, can work with a constant depth. Can the authors comment on this difference? Specifically, do they think an adaptive depth is necessary to achieve linear (or even polynomial) dependence on $\\delta$?\n\n- Line 93: I think that the comparison between Baum's and Vershynin construction is slightly misleading. It's true that having the points lie on a low dimensional hyperplane will violate the assumptions of Baum's construction, but as the authors note there is a trivial adaptation that will suffer some form of a 'dimensionality curse'. But this is also true for Vershynin construction. If the points lie on a low-dimensional hyperplane then $\\delta$ should be polynomial in $\\frac{1}{n}$ which will make for a network with a super polynomial number of neurons.\n\n- Line 274: At first glance, taking the groups so that their coordinates do not overlap seems overly excessive to me. If we just wish the vectors to be linearly independent then surely some overlap can be tolerated.  I guess that the main risk is having very sparse vectors which may induce a linear dependence on the overlapping part. Is this the reason why having a substantial overlap will not work? \n\n- The authors choose not to discuss generalization of neural networks since they claim their results cannot explain anything about generalization. I agree with this assessment, but I think a discussion about the resulting functions expressible by the authors' construction could be interesting. For example, we will certainly not expect any training algorithm like gradient descent to produce a similar network.\nAnother interesting point would be to compare it to the previous constructions. E.g. the construction of Baum results in a function that is essentially $0$ on the entire sphere, while Vershynin's construction will produce a random-looking function.\n\n- Concerning Theorem 5. I was slightly disappointed by the fact that $n$ must depend on $\\delta$. Of course, this is a necessity. otherwise, since the Theorem revolves around two-layered networks, it would contradict Baum's result. \nHowever, the Theorem applies when $n \\geq \\frac{1}{\\delta}$. We can plug this to main bound to get that the number of neurons must be at least $\\sqrt{n}$, which is not new. In particular, it does not show that a dependence on $\\delta$ is necessary for deep networks if one only wishes to use $\\sqrt{n}$ neurons. Again, I would be happy if the authors can comment on that and whether they think any dependence on $\\delta$ is necessary in this scenario.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: A solid progress in a well studied line of research
Decision: Accept (Poster)