An Exponential Improvement on the Memorization Capacity of Deep Threshold Networks
Year: 2021

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 Õ(e1/δ2 +√n) neurons and Õ(e1/δ2(d+√n) +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 Õ( 1δ + √ n) neurons and Õ(δ + 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.

text: √ n) neurons and Õ(dδ + 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.

heading: 1 Introduction
text: 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 as 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, a reasonable question to ask is that of how big a neural network needs to be so that it can memorize a dataset of n 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). In particular, Baum (1988) proved that a single hidden layer threshold network withO(max(n, d)) weights andO(dn/de) neurons can memorize any set of n points in d dimensions, as long as they are in general position.1 Baum asked if going deeper could increase the memorization power of threshold networks, and in particular if one could reduce the number of neurons needed for memorization to O(√n). While for ReLU activated networks, Yun et al. (2019) were able to prove that indeed onlyO(√n) neurons were sufficient for memorization using deeper networks, the same question remained open for threshold networks.
1The “general position” assumption of n vectors in Rd means that any collection of d of these n vectors are linearly independent.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Recently, Vershynin (2020) was able to answer Baum’s question in the positive by proving that indeed Õ(e1/δ2 +√n) neurons were sufficient to memorize a set of n points on a unit sphere separated by a distance at least δ. 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 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., σ(z) = 1z≥0, prohibits neurons from passing ‘amplitude information’ to the next layer. Although the dependence ofO( √ n) 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 a sphere is fundamental. In this work, we lift the spherical requirement and offer an exponential improvement on the dependence on δ. Theorem 1. (Informal) There exists a threshold neural network with Õ ( 1 δ + √ n )
neurons and Õ ( d δ + n ) weights that can memorize any δ-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 a distance of at least δ between them. Comparing the theorem above with Vershynin’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 O(log lognδ ) layers, of which only the first layer in our construction has real weights, which are i.i.d Gaussian. This layer has O( lognδ ) neurons and O( d logn δ ) weights. All the other layers have integer weights which are bounded and are on the of order O(log n). Baum (1988) also proved that there exists a dataset of n points such that any threshold neural network would need at least dn/de neurons in the first layer to memorize it. However, the distance for this dataset is O(1/n).2 Later, Baum & Haussler (1989) proved VC-dimension bounds which imply that min{√n, n/d} 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 δ. Our upper bound (Theorem 1) shows that if δ = Ω(1/n), then we can memorize with only O( lognδ ) neurons in the first layer. To complement our upper bound, we introduce a new, δ-dependent lower bound below: Theorem 2. (Informal) There exists a δ-separated dataset of size n ∈ [ d2 δ , ( 1 δ ) d 2 ] such that any threshold network that can memorize it needs Ω̃ (
1√ δ
) 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.
2Here, 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 a neural network) to memorize a δ-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.

heading: 2 Related works
text: Memorization with threshold activation. There is a rich history of research into the memorization capacity of threshold networks. Baum (1988) showed that a single hidden layer network with O(max(n, d)) weights andO(dn/de) neurons are sufficient to memorize a 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 dn/de 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 0 < δ ≤ 12 , the number of neurons in the first layer can be much smaller. Baum also proved, using the Function Counting Theorem (Cover, 1965), that O(n/ log n) connections are 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)d weights and n− 1 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 a 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 thatO(e1/δ2(d+√n)+n) weights andO(e1/δ2 +√n) neurons are sufficient to memorize a set of n points on the unit sphere, separated by a distance of at least δ. This answered the question by Baum (1988), which was whether the number of neurons could be reduced to O(√n) by considering deeper networks. Note that Vershynin’s and Baum’s assumptions are fundamentally different and neither is stronger than the other. For example, Baum’s construction would still need only O(max(n, d)) weights even if the points are infinitesimally close to each other, whereas Vershynin’s construction would grow as δ decreases. On the other hand, Vershynin’s construction works even if all the points lie on a low dimensional hyperplane, whereas Baum’s general position assumption would get violated in this situation. Note that naïvely extending Baum’s construction to the case where the points lie on a very low dimensional hyperplane would result in Õ(nd) weights and Õ(n) neurons3, which is identical to the bounds by Huang et al. (1991).
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 a 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 O(n) weights to memorize n points. Yun et al. (2019) were able to prove that for ReLU, in fact, one needs only O(√n) 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) neurons such that the total weight (Bartlett, 1998) of the network is O(√n), which is proved to be optimal for single hidden layer networks. Huang (2003) proved that a two-hidden layer network with O(√n) sigmoid activated neurons suffices to memorize n points. Recently, Park et al. (2020) have shown that ReLU or sigmoid activated networks with onlyO(n2/3 + log(1/δ)) weights are sufficient to memorize n points separated by a normalized distance of δ.
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.
3Please see Appendix A for a detailed explanation.

heading: 3 Preliminaries
text: In this work, we will consider feed forward neural networks f : Rd → {0, 1} of the form f(x) := σ(bL + w > Lσ(bL−1 + WL−1σ(bL−2 + WL−2σ(. . . σ(b1 + W1x) . . . )))),
where σ(·) is the threshold activation. The network has L layers, with the last layer consisting of a single neuron with bias bL ∈ R, and weight vector wL. For any other layer l, its bias vector is bl and weight matrix is Wl. We use the notation [n] to denote the set {1, . . . , n}. We formally define memorization as follows: Definition 1. A learning algorithm A can memorize a dataset of feature vectors D = {xi}ni=1 if for any arbitrary labeling {yi}ni=1 of the dataset, the algorithm can output a model f such that ∀i ∈ [n] : f(xi) = yi.
For instance, A could be the training procedure for a 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 a neural network f can memorize a dataset D = {xi}ni=1 if for every arbitrary labeling {yi}ni=1 of the dataset, we can find a set of weights and biases for the network so that ∀i ∈ [n] : f(xi) = yi. We are mainly interested in the minimum size of a threshold network so that it can memorize a dataset of n samples. Our only assumption on the dataset will be that of δ-separation, which we define below.
Definition 2. We say that a dataset is δ-separated if it satisfies either Assumption 1 or Assumption 2. Assumption 1. (Angular separation) All the feature vectors in the dataset, {xi}ni=1 satisfy
arccos ( 〈xi,xj〉 ‖xi‖‖xj‖ ) ≥ δ
Assumption 2. (Normalized minimum distance) All the feature vectors in the dataset, {xi}ni=1 satisfy ‖xi‖ ≤ 1 and
∀i 6= j : ‖xi − xj‖ ≥ δ. Remark 1. Note that the ‘normalized’ in the name of Assumption 2 refers to the fact that the 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 a similar normalized distance assumption.
Note that if the points lie on the unit sphere, like in Vershynin (2020) or Theorem 2 in this paper, then both assumptions are roughly equivalent.
Notation: 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 wi, similarly for the case when the vectors have subscript, we denote the i-th element of wj by wj,i. We use a tilde over O(·), Ω(·) and Θ(·), i.e., Õ(·), Ω̃(·) and Θ̃(·), to hide the logarithmic factors.

heading: 4 Main results
text: As discussed earlier, the existing result by Vershynin (2020) has an exponential dependence on δ. In this section, we provide a new and tighter upper bound on the number of weights and neurons needed for a memorization, which brings the dependence down to almost linear. Our result is stated below: Theorem 1. There exists a threshold activated neural network with O( log2 nδ + √ n log2 n) neurons
and O (
(d+logn) logn δ + n log
2 n )
weights that can memorize any dataset of size n in d dimensions that is δ-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 log2 n) term in the number of weights comes from binary and integer weights (with the integers being bounded and on the order of O(log n)). Hence, the O(n log2 n)
n that are linearly independent. Finally, we use this linear independence to memorize up to√
n log2 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 a single neuron that sums the outputs of these √ n neurons.
weights can actually be represented by O(n log2 n log log n) bits. We will see in Section 6 that Ω(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 logn δ , 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 dn/de neurons. We introduce a new, δ-dependent lower bound below: Theorem 2. For every 0 < δ ≤ 12 and some universal constants C1 and C2, there exists a dataset of size n ∈ [ C1d
2 log2(d/δ) δ , ( C2 δ ) d 2 ] satisfying the δ-separation condition such that any threshold
network that can memorize it needs Ω (
1√ δ log(1/δ)
) neurons in the first layer.
Note that the dataset in this theorem actually satisfies both Assumption 1 and Assumption 2, up to a constant factor. To understand the implication of Theorem 2 a bit better, consider two dataset D1 and D2, both containing n points on the sphere. We assume that D1 has δ1-separation and D2 has δ2-separation, where δ1 = Θ(n−2/d) and δ2 = Θ̃(d2/n). Then, Theorem 1 says that there exists a network that can memorize D1 with onlyO(n2/dlog n) neurons in the first layer, whereas Theorem 2 says that any network aiming to memorize D2 would need at least Ω̃( √ n/d) neurons in the first layer. Hence, we see that the minimum distance can have a big impact on the network architecture.
Comparing Theorems 1 and 2, we see that there is a gap in the bounds: Theorem 1 proves an upper bound of Õ(1/δ) neurons, whereas Theorem 2 proves a lower bound of Ω̃(1/ √ δ) neurons. We think that the gap is an artifact of the proof of Theorem 2, and a tighter analysis or a better construction could result in a lower bound of Ω̃(1/δ) neurons, which will match the upper bound of Theorem 1. However, this is just speculation based on intuition, and more research will be needed to answer this open question.

heading: 5 Memorization with threshold networks
text: In this section, we give a proof sketch of Theorem 1, the complete proof is provided in the appendix. We will construct a network that can memorize any δ-separated dataset. As we discussed before,
the threshold activation prohibits the passing of amplitude 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 ReLU. In the following, we will explain our construction layer-wise:
Step 1: 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 a unique binary representation. Later, we will see that this is sufficient for memorization.
Now we give an overview of how a layer with O( lognδ ) neurons with random i.i.d. weights can convert the input into unique binary vectors of length O( lognδ ). In this sketch, we will do this under Assumption 1, but the same technique can be extended for Assumption 2.
The key result we use is that any hyperplane passing through the origin, with random Gaussian coefficients has at least a δ/2π probability of separating two points which have an angle of at least δ between them. To see how this is true, consider two points xi and xj 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 xi and xj 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, 2π). This implies that the probability that this line passes in between the two points is at least δ/2π.
If we take m such independent Gaussian hyperplanes, then the probability that none of them separate a pair xi,xj is less than (1− δ2π )m. Finally, taking a simple union bound over the ( n 2 ) pair of points, shows that the probability that at least one pair has no hyperplane passing in between them is at most
( n
2
)( 1− δ
2π
)m .
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 = O( lognδ ), which is our required bound. For any input xi, each threshold neuron in the first layer outputs either 0 or 1. We can concatenate the outputs of all the neurons in the first layer into a binary vector. Let us denote this binary representation of xi created by the first layer as z (1) i , for i = 1, . . . , n. Further, denote the dimension of z(1)i by d (1), which is equal to the number neurons in the first layer, that is, d(1) = O( lognδ ).
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( lognδ ) dimensional vectors returned by the first layer into vectors of length O(log n). Note that O(log n) length is optimal (up to constant multiplicative factors) if we want to represent the n samples uniquely using binary vectors. For this we will use linear codes where we simulate XOR operations by threshold activations.
Consider two d(1)-dimensional binary vectors z(1)i and z (1) j that differ in at least one bit. Let ⊕ represent the XOR operation. Let b be a random binary vector of length d(1) where each bit is i.i.d Bernoulli(0.5). Then, we claim that
Pr(〈z(1)i , b〉⊕ 6= 〈z (1) j , b〉⊕) = 0.5,
where 〈z, b〉⊕ = (z1 · b1)⊕ · · · ⊕ (zd(1) · bd(1))
For the ease of exposition, assume that z(1)i and z (1) j differ in only the first bit (the proof of the general case is provided in the appendix). Let the first bit of z(1)i be 0, and that of z (1) j be 1, and we have assumed that the rest of their bits are the same. Let c := (z(1)i,2 · b2)⊕ · · · ⊕ (z (1) i,d(1) · bd(1)) =
(zj,2 · b2)⊕ · · · ⊕ (zj,d(1) · bd(1)). Then,
Pr(〈z(1)i , b〉⊕ 6= 〈z (1) j , b〉⊕) = Pr(((0 · b1)⊕ c) 6= ((1 · b1)⊕ c)).
It can now be verified that if b1 = 1, then ((0 · b1)⊕ c) 6= ((1 · b1)⊕ c). Since Pr(b1 = 1) = 0.5, we get the desired result.
We have shown that the probability that one such random vector b differentiates between a pair z(1)i and z(1)j with probability 0.5. Doing an analysis similar to the one that we did for the first layer, we get that m = O(log n) 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 be achieved using a couple of sparse layers.
Similar to the output of the first layer, let us denote the compressed binary representation of z(1)i created by these sparse layers as z(2)i , for i = 1, . . . , n. Further, let z (2) i have dimension d
(2), where d(2) = O(log n), as we showed above.
Step 3: Partitioning the samples into subsets of size O(√n log n). Once we have d(2) = O(log n) length binary representations of the inputs, memorizing with a single layer consisting of (d(2) + 1)n weights and n neurons is not difficult. However, our aim is to reduce the number of neurons to O(√n log n). For that, we use a strategy similar to Yun et al. (2019): we will memorize up to K samples with 1 neuron, where K = Ω( √ n log n).
<latexit sha1_base64="CT4yGyPd9yKRaT3sRHqHVHroeXs=">AAA2R3icnZvbctxIcoY569NaPu3al75BWFLs2iExJM1o13u3PIoUm+ejONRMAOjsbojoBoSqBkl1tF/At/ZD+RH8FL5z+NJZVaj+s9CgZmMZMUPU9yeqgaq/KhNNKCnzTOlXr/77m5/9yZ/+2Z//xc//8slf/fXf/O3f/eKXf3+himmV0nla5EV1lcSK8mxC5zrTOV2VFcXjJKfL5HbD6Jc1VSorJmf6oaSP43g4yQZZGmtGx3s//uLpq9VX9idaPnjdHDxdaX6Ofvzl21c3/SKdjmmi0zxW6vvXr0r9cRZXOktzmj+5mSoq4/Q2HtL3fDiJx6Q+zuyVzqPnTPrRoKj4v4mOLJVnzOKxUg/jhCPHsR6psDc9+NePs2xSTjVNUtfZYJpHuojMrUX9rKJU5w98EKdVxtcTpaO4ilPNA/DkyZPn5ic62LqM9tfOdqLNre3dg92z3cOD08hKT9pXYi7hBf8216peJOPg5mZJC3xvrzitPs5omsb5nLub0F1ajMfxpD+76e9P57MbTfd6UlTjOJ/15zfj6bwVdLAcNFkKOhplS1Els1aYagepdoRuR+h2xNLlLF1M3Y6o2xH37Yj7dsRDO+KhHfGlHfGFx9fMabQfV7eR4olnP6uoGERpXLpjY7OKBlRV2WRoXNLP6kz5sEE2nFakws9hmNOAh2V2Q+Po1z0+/uf5fCkmZfNT5aM2bKsrrsqGo0VnJ6bRFaWL0secFWVXRFJoXYx90LptLcU19x37sPixiMRHJI9FpD4ifSyi7yP6JoKnYYfvLjd3GMURx5tVSAPelPoRj8047IOPDZx///oj95IMoqevTSfcy/No206Lmzde5fQiyos7ql6mvMmtcsQNd2uHlgZPX8/cJP7bDbdmtpPuLviiMx3nq9E2W0Jp3quMA5SZN9Z9r9u+1+3lXm2Aviv8Jz9903y2inxYxPfWNN7gnM/TuI+Tnn779LulE18szvJH38rOvmtu69R5/CeGhleCu4lmSbTGpqMTPzi+h1Pfw2lnDyf+TLvv3hWLtbcqhsldhbLjtFibjw5Uu9NRRbTcrejz6bfLvWIURf/fdvUfTyLiaTGndw4hfXb374O+NgBBX9OypCoyffmutpqutrq7Wouq+A5z0erw5cuXcV1k/WiqzAaWDaKyUCrj1O67L/OYl1jzGV+7SpMIS15znfdrNNdFE/VH3PCis41FZxt/QGd8/5Mh2V3bRSvfjxUWV8Y28gG+u5cvv2Ihvso4HxZcBIzGnffMqrvKRdhP3LToruOu13x3a53d+WXhP5VvZ9HfT20gZ8Fpa3/AaUuDXPKG14xC4E7D3WWbo69PlOtj2eFHiz6O2n34u158DF+/OX700p84O1KWGzvn5oBTAweYo7lTB3lRVFa2R063h00AS8l41lyBzDq64sXCZYQp07g+m20uh9RxnvVlyI/uuBrPnDTv6JaU7j7FKvPFfVGpTM4sVZYXkybfnXAXxTiq4yqLeV0rF1mRjmdBvfPshtEz01ezOEI5hpKESgIlDZUUSn/WKq4WCoUKQRmEygDKMFSGUEahMoKShUoG5VOofIJyGyq3UPJQyd2sVeMoU7yO+fGo/2C2RDeDL6JPU6WjfjH5lY7M0wqb8sHsS8HEROOm70nY9wSfWoRKAaUMlRLK51D5DKUKlQqKChUFRYeKhjINlSmUOlRqKHehcgflPlTuoTyEygOUL6HyZe7KRr8AOJsXlbd/3SySmVtKyUAsm8V165FbJT7CtoUuNIkTYLE26hRYLIy6DyxWRU3AYknUA2CxHuohsFgM9QhYrIR6CiyWQf0JWKyB+hZYLIA6B84FHgOPBRYDLUe4ABZmrktg4eT6M7CwcV0BCw/XCljJSQXW3WMirVsDC9/Wd8DCtPU9sHBs/QAs7Fp/AfZe3crJfOthnx6rDt+SM13nvkzOeZ07Mzn7de7N5DzYuTuTM2Ln/kzOjZ07NDlLdu7R5HzZuUuz9ug+Tc6hnTs1OZt27tXkvNrerb02DrWx1B7diclZt3MvJuffzt2YnIk792NyTu7ckcnZuXNPJufpzl2ZnLE792Vy7u7cmclZvHNvJufzzt2ZnNk792dyjn98h+a1UGXpokIZr2F9rGHZjNeB1wXeAN4QeBN4U+At4C2Bt4G3BX4H/E7gHeAdgXeBdwV+D/xe4D3gPYF7wD2B94H3BT4APhD4EPhQ4CPgI4GPgY8FPgE+EfgU+FTgM+Azgc+BzwW+AL4Q+BL4UuAr4CuBPwB/EPga+Prx7TU0HTnXCY+uCf9a6wltXWobobYhtc1Q25TaVqhtSW071Lal9i7U3kltJ9R2pLYbartSex9q76W2F2p7UuuFWk9q+6G2L7WDUDuQ2mGoHUrtKNSOpHYcasdSOwm1E6mdhtqp1M5C7Uxq56F2LrWLULuQ2mWoXUrtKtSupPYh1D5I7TrUvO0vZAlRX5N9juAn2FeLc+vDCc38U61n46lD5m8IC+hrYsPDerhusCCJI6hDbBXCBNWHrT2YoOaomytBpWHrDCaoL2x1wQRVha0pmKCWsJUEE1QQtn5ggrrBVg1MUC3YWoFJLsbBEVQGti5ggnqgbkYUVYCtAZgg99vMzwQZ3+Z7JsjzNsszUWLAHUFOr5tpEZNSO4L8bbM3E2Rtm7OZIFfbTM0EGdrmZyZd1WhYhtZxXo7MfNvfCwfWSWMO6wsP8aiFbyYaKY/HSd+c4Q4gFGMaGm5/A1tLGjt6wB0y4f8DqWw4Nqfa38DeuI1pFzcym8nrnxmz+habNUWLjdoXNzUzBvUtNugALTbnEC025ggtvlxxrWzIT2ixGW/F2MyMCRd3PjMG9C0eTDGKbL5CDMnMmM632HSf0WLDVWKkZsZoiwGaGZP5Fg+0GGY2WI0Wm+sOLTbWPVpsqge02FBfnJf2TZ69d9zmWPYZcqvNrEyQUW0+ZYI8arMoE2RPmzuZIGfajMkEmdLmSSbIjzY7MkFWtDmRCXKhzYRMkAFt/mOCvGezHhNkO5vrmCDH2QzHBJnN5jUmyGc2mzFBFrM5jAlyl81cTJCxbL5igjxlsxQTZCebm5ggJ9mMxASZyOYhJsg/NvswQdaxOYcJco3NNEyuxQwiLyQyLYyPRs1GfGP+qIzR80vfKL1m+S9urlnDRjt169i66Iwmyvw5f5PSPK6ITTVaMzsQf6Ir9tQgM1+V0iQt+tlkyJ3F09wQNVgcj+czZb7rPSX9WAdJkfd/qpvkfs6L8Enrm9qJsn9zdHmz6c9+W93cmnb15UQJ9+t1z+B/veEZVoDe9AxrQG95hlWgtz3DOtDvPMNK0DueYS3oXc+wGvR7z7Ae9J5nWBG65xnWhN73DKtCH3iGdaEPPcPK0EeeYW3oY8+wOvSJZ1gf+tQzrBB95hnWiD73DKtEX3iGdaIvPcNK0VeeYa3oD55htehrz1xFxkZO4zzPhlVcjrLUBaX+cTcNnjrSdYFhj3RDYDgk3RQYJkm3BIZP0m2BYZX0ncBwS7ojMAyT7goMz6TvBYZt0j2B4Zy0JzDMk+4LDP+kBwLDQumhwHBReiQwjJQeCwwvpScCw07pqcBwVHomMEyVngsMX6UXAsNa6aXAcFd6JTAMln4QGB5LrwX2hX+Sx+ltUsRV3wUlrsy3T8VBrZ8svmtJhPeSdVBYL9kAhfOSTVBrvOfRpv17x1RRFEeKtPU89aOtF1FCaWy4HmUquiumeZ8RtyhS9q8jXHFOq8i8pVXk3JF5y4buS65A7R+FV5tP3MInwtPJNigsnbwDhaOTHVAYOtkFhZ+T96Cwc7IHCjcnPVCYOdkHhZeTA1BYOTkEhZOTI1AYOTkGhY+TE1DYODkFhYuTM1CYODkHhYeTC1BYOLkEhYOTK1AYOPkACv8m16DeviqtslI7XXmHMhQWVesCw6NqQ2CYVG0KjO1RbQkMK6ltgeEl9U5gmEntCAw3qV2BYSf1XmD4Se0JDEOpnsBwlNoXGJZSBwLDU+pQYJhKHQkMV6ljgWErdSIwfKVOBYax1JnAcJY6FxjWUhcCw1vqUmCYS10JDHepDwLDXupa4MXXgRN+JiH7eBu7LwKbBxRCddoLH0zNo8saWuy+dbTYdBtosdc20WKLbaHFztpGiw31Di320Q5abJ9dtNg179Fis+yhxR7pocXW2EeLHXGAFhvhEC2e/yO0eNqP0eLZPkGLJ/kULZ7bM7R4Ss/R4pm8QIsn8BItnrcrtHi6PqDFs3QtPq95CmieAMyUkZwy7Z4GnkenJmvY1305dTj6IrrL9KiY6ohL8eiOK62SqrBYJ1TrQaXefLxeeMAGLj2kkC3lqVXLky3mqVXNky3nqVXPky3oqVXRky3pqVXTky3qqVXVky3rqVXXky3sqVXZky3tqVXbky3uqVXdky3vqVXfky3wqVXhky3xqVXjky3yqVXlky3zqVXnky30qVXpky31qVXrky32qVXtky33qVXvky34qVXxky35qVXzky36qVX1ky37qVX3ky38qVX5ky39qVX7ky3+SVT//BTLhY6uphRNJ32q8gfz6l0/1nE0pAlVXOOYdqbY6cnUFDyhbUsTOp+VP85uqvHMNmy5ZXqlcZlVGRdawfmL92STB1tk2deUzIdwVdbq27/BNIr1rJyHHxFEHsnIo3nXxYyLPuVfuxEbsLgT11r6nCbo6GtBpc7yPjWRN7axuPrFGbxN6CIdxcq8tR9PdWGf7qkKrrD1snbpYhbX2JyyfAF9CuJcsyOuYoE3HR/nmuyF1H6/Gwbnccn1OzVvfnF0rwHz6HnUHIfDG56/NZf1caj1lHihrNdWT3DmSVtji4kxbol5NfffCYdCRcP54lvetpRq3KNpZYOMqnbXqhjocXyPSA/acZwsCvuKnfsCeLmXMp+au/9ivqUK1b3eXL5dt9dbmsCLuMIVmEa7f82/+HmLqqoQkadLE7BR1JBNwxj0ssgHVTw2X5aO7oqKH4tU/KCiZ70f3jwzb5bZf9Uynbj3q1XJ86/s+43PbijPRYz/sv55tM4JkJf8xPzvgdc7jc27lubZy3Uqos1L0cV0aHOmfRTLNL2w3asi6hdkurvLbrOS+lm82nrdvqjG+Reqivms98OreYdYTMhor7s0fWfPe9OllUYpOxTrhd4PN9lkoB/aS6eMK/OHC9424rl9JZ33WhUPKcom0aRoHiM13a9GG6NCmeEpTAGYjqLNuBxN6FcqSoridvVJ8FXjYWl256L6F/Z4NbQXwL9vXpijrwWafdIF8lF3l9atHGb//0jEGRvqzLyDmpO+iRNeZ3lxl1QU3z6x/8bqd/Yncge//a45+N3rxb+xuniz+vo3q2+Ov3v6+zfNv7b6+co/rvzTyq9XXq/8duX3KzsrRyvnK+kKrfz7yn+s/Ofb/3r7P2//9+3/udCffdOc8w8rwc9vvvl/vKr6dQ==</latexit>
Thus, we will need onlyO(√n) neurons in total. Roughly speaking the strategy would be the following: Let’s say we have a neuron σ(w>z + b). Then, if for any {y1, . . . , yK} ∈ {0, 1}K , we can find a w and b such that all of the following equations hold at the same time,
w>z1 + b = y1, . . . ,w >zK + b = yK , (1)
then this neuron can memorize the K samples {z1, . . . zK}. To do so, we need that the vectors {z1, . . . ,zK} be linearly independent4. Since we have K = Ω( √ n log n), we require that zi’s have dimension at least K. However, the previous few layers have compressed the samples into d(2) = O(log n) length binary vectors. Thus, the next task is to project these d(2) length binary vectors to Ω(K) length binary vectors. Note that first compressing down to O(log n) length vectors and then expanding these up to Ω( √ n log n) length binary vectors seems counter intuitive. However, we were unable to project the vectors directly to Ω( √ n log n) length binary vectors without incurring a large dependence on δ and n in the number of weights and neurons.
One more objective that we accomplish while projecting up to Ω(K) dimension is that both the projection and memorizing the resulting vectors can be easily done with bounded integer weights. The way we do this is by partitioning the n vectors z(2)i into K subsets of size at most√ n each. We prove that we can find such K subsets, such
that each is characterized by a unique prefix, which all the elements of that subset share. These prefixes ensure that we can easily detect which subset a particular z(2)i belongs to, using threshold neurons. For more details on this, please refer to the appendix.
4Yun et al. (2019) also use this strategy. However, as we will see in Step 4, we are able to ensure that the vectors {z1, . . . , zK} are linearly independent while also ensuring that their coordinates do not overlap. This helps us find a vector w which has integer values and satisfies (1). 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.
Let {S1, . . . , SK} denote theK subsets, each with a unique prefix. Let z(2)i ∈ {0, 1}d (2)
be the binary vector returned by Step 2 above for input xi. We mentioned above that by using threshold neurons, we can create a vector s(2)i ∈ {0, 1}K for z (2) i such that si,j = 1 if and only if z (2) i ∈ Sj . Then, using these prefixes and threshold neurons, we can create the expanded binary vector z(3)i ∈ {0, 1}K(d (2)+1) corresponding to the vector z(2)i . The way we create z (3) i from z (2) i is as follows: z (3) i is partitioned into K chunks of length d(2) + 1. If z(2)i ∈ Sj , then the first bit of the j-th chunk is set to 1 and z (2) i is copied to the rest of the bits in that chunk. All the other bits in z(3)i are 0. 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 √ n neurons A key property about the vectors z(3)i is that if we take K such vectors, each belonging to a different subset Sj , then they will be linearly independent as their coordinates do not overlap. Thus, we can find w and b such that (1) is satisfied. Furthermore, due to the fact that these K vectors have different supports, we can manage to satisfy (1) with w which have integer elements on the order of O(log n). Hence, we can memorize up to K samples with one neuron. This gives that we need √ n in the second-to-last layer to memorize all the samples. The final layer is simply a single neuron that sums the outputs of the second-to-last layer.
Note that a threshold neuron can be approximated using three ReLU neurons. Hence, the construction described in this section can also be used to create a ReLU activated network with can memorize the same dataset.

heading: 5.1 Extending the construction to multiple class memorization
text: The construction above can be easily extended to the case when there are more than two classes. Let there be M ≥ 2 classes. Then, the label for each sample can be represented as a sequence of log2M bits. In this case, we can replicate the construction of the last and the second-to-last layers log2M times so that the new network has log2M 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 withO( log2 nδ + √ n(log2 n)(logM))
neurons andO (
(d+logn) logn δ + n(log
2 n)(logM) )
weights that can memorize anyM -class dataset of size n in d dimensions that is δ-separated.

heading: 6 Bit complexity of memorization
text: Before understanding the minimum size that threshold networks have to be in order to memorize a dataset, a more fundamental question is how many bits are needed to specify the models output by any learning algorithm that aims to memorize a 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 a real number δ > 0, the packing number Pδ of a set S (equipped with norm ‖ · ‖) is defined as the cardinality of the largest set X ⊂ S such that
∀x1, x2 ∈ X : ‖x1 − x2‖ ≥ δ.
Intuitively, the packing number is the maximum number of δ/2 radius non-overlapping balls that one can fit inside a set. Definition 4. Given a real number δ > 0, the covering number Cδ of a set S (equipped with norm ‖ · ‖) is defined as the cardinality of the smallest set X ⊂ S such that
∀x ∈ S,∃x̂ ∈ X : ‖x− x̂‖ ≤ δ.
Intuitively, the covering number is the minimum number of δ radius (possibly overlapping) balls that one needs to completely cover a set.
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):
P2δ ≤ Cδ ≤ Pδ.
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. LetA be a learning algorithm that can memorize any dataset of feature vectors D ∈ Sn as long as every pair of feature vectors xi,xj ∈ D satisfies ‖xi − xj‖ ≥ δ. Then, we need at least max(n, log2 log2 Pδ) bits to represent the models output by A. Theorem 4. Let S 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 ∈ Sn as long as every pair of feature vectors xi,xj ∈ D satisfies ‖xi − xj‖ ≥ δ, and the models returned by A can be represented in O(n+ log2 log2 Cδ/2) bits.
Note that since a + b = O(max(a, b)) for non-negative variables a and b, the upper bound from Theorem 4 is of the same order as the lower bound from Theorem 3.
It is known that the packing and covering numbers of the unit sphere are of the order Θ((Cp/δ)d) and Θ((Cc/δ)
d), for some universal constants Cp and Cc respectively. Substituting this into Theorems 3 and 4, we get the following corollaries. Corollary 2. Let Sd−1 be the unit sphere in Rd. Let A be a learning algorithm that can memorize any set of n points on Sd−1 as long as every pair of points xi,xj ∈ D satisfies ‖xi−xj‖ ≥ δ. Then, we need Ω(max(n, log d+ log log 1δ )) bits to represent the models output by A. Corollary 3. Let Sd−1 be the unit sphere in Rd. Then, there exists a learning algorithm A that can memorize any set of n points on Sd−1 as long as every pair of feature vectors xi,xj ∈ D satisfies ‖xi − xj‖ ≥ δ, and the models returned by A can be represented in O(n+ log d+ log log 1δ ) bits. Note that if we have a set of n points on the unit sphere separated by at least distance δ, 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 δ-separation assumptions.
7 Lower bound construction <latexit sha1_base64="+ylOiStgDxoFXt3+VoSwF3sCjo8=">AAA2V3icnZtrc9tIdoa1m2QzUS47k3zMF1Rs124SW2V7Lrv7IVWrqyWLul+toccFgIckLICA0U1IMov5I/ma/Kj9NcnpBprvaRDybEVVM0I/70ET6H67zwEFR0WaKP3y5Z9+8cu/+Mu/+tVff/U3q3/7d3//D7/++pt/vFT5tIzpIs7TvLyOQkVpMqELneiUrouSwixK6Sq63TT6VUWlSvLJuX4o6H0WjibJMIlDzejD17/uV3c/9XVe9Kv7f4/+4+WHr5+8XHtpf4Llg1fNwZOV5uf4wzffv+wP8nia0UTHaajUj69eFvr9LCx1Eqc0X+1PFRVhfBuO6Ec+nIQZqfcze+Xz4BmTQTDMS/5vogNL5RmzMFPqIYs4Mgv1WPm96eHv38+SSTHVNInrzobTNNB5YG41GCQlxTp94IMwLhO+niAeh2UYax6Q1dXVZ+YnONy+Cg7Wz3eDre2dvcO9872jw7PASqvtKzGX8Jx/m2tVz6PMu7lZ1AI/2iuOy/czmsZhOufuJnQX51kWTgaz/uBgOp/1Nd3rSV5mYTobzPvZdN4KOlwOmiwFHY+TpaiCWStMtYNUO0K3I3Q7Yulyli6makdU7Yj7dsR9O+KhHfHQjvjcjvjM42vmNDgIy9tA8cSzv1WQD4M4LOpjY7OShlSWyWRkXDJIqkS5sGEympak/M9hmNKQh2XWpyz4bY+P/3U+X4qJ2fxUuqhN2+qKK5PReNHZqWl0RfFqdDHnedEVEeVa55kL2rCtpbjmvkMXFj4WEbmI6LGI2EXEj0UMXMTARPA07PLdpeYOgzDgeLMKacib1CDgscn8PvjYwPmPr95zL9EwePLKdMK9PAt27LTU88arnJ4HaX5H5YuYN701juhzt3Zoafjk1ayexP/sc2tmO+nugi860WG6FuywJZTmvco4QJl5Y931uuN63Vnu1Qbou9x98pPXzWerwIUFfG9N4zXO+TQNBzjpybdPvls68fniLHf0rezsu+a2zmqP/8zQ8Eqob6JZEq2x6ejEDY7r4cz1cNbZw6k70+67d/li7a2JYaqvQtlxWqzNRweq3em4JFruVvT55NvlXjGKov9vu/oPJwHxtJjTO4eQPtX374K+NABeX9OioDIwfbmutpuutru7Wg/K8A5z0erwxYsXYZUng2CqzAaWDIMiVyrhVO+6L9KQl1jzGV+6SpMIC15znfdrtLqLJur/ccOLzjYXnW3+GZ3x/U9GZHftOlq5fqywuDK2kQtw3b148QUL8VWG6SjnImCcdd4zq/VVLsJ+5qZFdx13ve66W+/szi0L96l8O4v+fm4DOfdOW/8zTlsa5II3vGYUPHcaXl+2OfryRNV9LDv8eNHHcbsPd9eLj+HrN8ePXvpqbUdKUmPn1BxwauAAczSv1WGa56WV7VGt28MmgKUomzVXILOOLnmxcBlhyjSuz2ZbyyFVmCYDGfKhPi6zWS3NO7olpbtPscp8cV9UKJMzC5Wk+aTJd6fcRZ4FVVgmIa9rVUeWpMOZV+887TN6avpqFocvh1AiX4mgxL4SQxnMWsXVQiFfIShDXxlCGfnKCMrYV8ZQEl9JoHz0lY9Qbn3lFkrqK2k9a2UWJIrXMT8uDR7MlljP4PPg41TpYJBPfqMD87TCpnww+5I3MUHW9D3x+57gU3NfyaEUvlJA+eQrn6CUvlJCUb6ioGhf0VCmvjKFUvlKBeXOV+6g3PvKPZQHX3mA8tlXPs/rstEtAM7meensXzWLZFYvpWgols3iuvW4XiUuwraFLjSJI2CxNqoYWCyMagAsVkVFwGJJVENgsR6qEbBYDNUYWKyEagoslkH1EVisgeoWWCyAKgVOBc6AM4HFQMsRzoGFmasCWDi5+gQsbFyVwMLDlQJWclKBdfeYSOtWwMK31R2wMG11DywcWz0AC7tWn4GdV7dTMt962KfHssO3VJuuc1+m2nmdOzPV9uvcm6n2YOfuTLURO/dnqt3YuUNTbcnOPZpqX3bu0qw9uk9T7dDOnZpqm3bu1VR7tb1bOy3ztUxqj+7EVFu3cy+m2r+duzHVJu7cj6l2cueOTLWdO/dkqj3duStTbezOfZlqd3fuzFRbvHNvptrnnbsz1Wbv3J+pdvzjOzSvhTKJFxVKto71sY5lk20Abwi8Cbwp8BbwlsDbwNsC7wDvCPwG+I3Au8C7Au8B7wn8FvitwPvA+wL3gHsCHwAfCHwIfCjwEfCRwMfAxwKfAJ8IfAp8KvAZ8JnA58DnAl8AXwh8CXwp8BXwlcDXwNcCvwN+J/AN8M3j26tvOqpdJzy6LvxrrSe0Dalt+tqm1LZ8bUtq2762LbUdX9uR2htfeyO1XV/bldqer+1J7a2vvZXavq/tS63naz2pHfjagdQOfe1Qake+diS1Y187ltqJr51I7dTXTqV25mtnUjv3tXOpXfjahdQufe1Sale+diW1a1+7lto7X3sntRtfc7a/lCVEdUP2OYKfYF8uzq2OJjRzT7WOZdMamb8hLKCriQ336+GqwYJENUEdYqsQJqg+bO3BBDVH1VwJKg1bZzBBfWGrCyaoKmxNwQS1hK0kmKCCsPUDE9QNtmpggmrB1gpMUjEONUFlYOsCJqgHqmZEUQXYGoAJcr/N/EyQ8W2+Z4I8b7M8EyUGvCbI6VUzLWJSqpogf9vszQRZ2+ZsJsjVNlMzQYa2+ZlJVzXql6FVmBZjM9/298KBVdSYw/rCQTxq4ZuJRkrDLBqYM+oDCHlGI8Ptb2BrSWNHB7hDJvx/IJWMMnOq/Q3sjNuYdnEjs5m8/pkxq2uxWWO02KgDcVMzY1DXYoMO0WJzjtBiY47R4ssV18qG/IgWm/FWjM3MmHBx5zNjQNfiwRSjyObLxZDMjOlci033CS02XClGamaMthigmTGZa/FAi2Fmg1Vosbnu0GJj3aPFpnpAiw31ufbSgcmz9zW3OZZ9htxqMysTZFSbT5kgj9osygTZ0+ZOJsiZNmMyQaa0eZIJ8qPNjkyQFW1OZIJcaDMhE2RAm/+YIO/ZrMcE2c7mOibIcTbDMUFms3mNCfKZzWZMkMVsDmOC3GUzFxNkLJuvmCBP2SzFBNnJ5iYmyEk2IzFBJrJ5iAnyj80+TJB1bM5hglxjMw2TGzGDyAuRTAvZ8bjZiPvmj8oYPbf0jdJrlv/i5po1bLSzeh1bF53TRJk/529RnIYlsanG62YH4k+siz01TMxXpTSJ80EyGXFn4TQ1RA0Xx9l8psx3vWekH+sgytPBz3UT3c95Ea62vqmdKPs3xzpvNv3Zb6ubW9N1fTlRwv16wzH4X286hhWgtxzDGtDbjmEV6B3HsA70G8ewEvSuY1gLes8xrAb91jGsB73vGFaE7jmGNaEPHMOq0IeOYV3oI8ewMvSxY1gb+sQxrA596hjWhz5zDCtEnzuGNaIvHMMq0ZeOYZ3oK8ewUvS1Y1gr+p1jWC36xrG6ImMjx2GaJqMyLMZJXAfF7nE39p464g2BYY94U2A4JN4SGCaJtwWGT+IdgWGV+I3AcEu8KzAME+8JDM/EbwWGbeJ9geGcuCcwzBMfCAz/xIcCw0LxkcBwUXwsMIwUnwgML8WnAsNO8ZnAcFR8LjBMFV8IDF/FlwLDWvGVwHBXfC0wDBa/Exgei28EdoV/lIbxbZSH5aAOiuoy3z4Ve7V+tPiuJRLeizZAYb1oExTOi7ZArfGeBVv27x1TRUEYKNLW8zQItp8HEcWh4XqcqOAun6YDRtyiQNm/jnDFOS0D85ZWnnJH5i0bui+4ArV/FF5rPnEbnwhPRzugsHT0BhSOjnZBYehoDxR+jt6Cws7RPijcHPVAYeboABRejg5BYeXoCBROjo5BYeToBBQ+jk5BYePoDBQujs5BYeLoAhQeji5BYeHoChQOjq5BYeDoHSj8G92AOvuquEwKXevKOZShsKjaEBgeVZsCw6RqS2Bsj2pbYFhJ7QgML6k3AsNMaldguEntCQw7qbcCw09qX2AYSvUEhqPUgcCwlDoUGJ5SRwLDVOpYYLhKnQgMW6lTgeErdSYwjKXOBYaz1IXAsJa6FBjeUlcCw1zqWmC4S70TGPZSNwIvvg6c8DMJ2cfbsP4isHlAIVSnPf/B1Dy6rKPF7ttAi023iRZ7bQstttg2WuysHbTYUG/QYh/tosX22UOLXfMWLTbLPlrskR5abI0DtNgRh2ixEY7Q4vk/Roun/QQtnu1TtHiSz9DiuT1Hi6f0Ai2eyUu0eAKv0OJ5u0aLp+sdWjxLN+LzmqeA5gnATBnJKdP108Cz4MxkDfu6L6eOmj4P7hI9zqc64FI8uONKq6DSL9YJ1bpXqTcfrxcesIFLDylkS3lq1fJki3lqVfNky3lq1fNkC3pqVfRkS3pq1fRki3pqVfVky3pq1fVkC3tqVfZkS3tq1fZki3tqVfdky3tq1fdkC3xqVfhkS3xq1fhki3xqVflky3xq1flkC31qVfpkS31q1fpki31qVftky31q1ftkC35qVfxkS35q1fxki35qVf1ky35q1f1kC39qVf5kS39q1f5ki38S1T8/xXKho8spBdPJgMr0wbx6Nwh1GIxoQiXXOKadKHZ6NDUFj2/bwoTOZ8WHWb/MZrZhyy3TK2VFUiZcaHnnL96TjR5skWVfUzIfwlVZq2/3BtM41LNi7n+EF3ksI4/nXReT5QNKv3QjNmBxJ3Vr6XOaoOMvBRU6SQfURPZtY3H1izN4m9B5PA6VeWs/nOrcPt1T6V1h62Xtoo5ZXGNzyvIFDMiLq5sdcSULvOm4uLrJXojt97t+cBoWXL9T8+YXR/caMA+eBc2xP7z++dtzWR/7Wk+JF8p6bfUUZ562NbaYGOOWmJZz952wL5Q0mi++5W1LscY9mlYyTKhsd63yoc7Ce0Q60I7jZJHbV+zqL4CXeynSqbn7z+ZbKl/d783l23X7vaUJvAxLXIFptPvX/Iuft6gscxF5tjQBm3kF2TSMQa/ydFiGmfmydHyXl/xYpMIHFTzt/fT6qXmzzP6rlumkfr9aFTz/yr7f+LRPaSpi3Jf1z4INToC85Cfmfw+83ikz71qaZ6+6UxFtXorOpyObM+2jWKLpue1e5cEgJ9PdXXKbFDRIwrXW6/Z5maWfqczns95PL+cdYj4ho73q0vSdPe91l1YYpehQrBd6P/WTyVA/tJdOEZbmDxe8bYRz+0o677UqHFGQTIJJ3jxGarpfCzbHuTLDk5sCMB4HW2ExntBvVBDl+e3aqvdV41Fhdue8/Df2eDmyF8C/+8/N0ZcCzT5ZB/JRd5fWrRxm//9IxDkb6ty8g5qS7ocRr7M0v4tKCm9X7b+x+oP9CeqD333XHPzh1eLfWF2+Xnv1w9rrk++e/PH3zb+2+mrln1f+ZeW3K69Wfrfyx5XdleOVi5V4ZbryXyv/vfI/3//p+//94Vc/fFWH/vIXzTn/tOL9/PDN/wF4h/6J</latexit>
w >x + b
= 0
<latexit sha1_base64="J+zy/cNO/UaBS+UvTgP++WBUlis=">AAA2X3icnZtdc9zIdYZp58MOkzjr+MKVyg0qlMpOSmKJ2rVs35mfIsXh96e41KoAzJkZiMAAQveApKYmfya3yQ/KZf5JTjfQ857GgFqXWbVL9PMe9ADdb/c5GEJRkSZKv3r1vz/56V/99d/87c9+/nfLf/8P//iLf/rml/98qfJJGdNFnKd5eR2FitJkTBc60SldFyWFWZTSVXS3afSrikqV5ONz/VjQhywcjpNBEoea0cdvfn2rPpd6ejsow3h626dUh7Npfzb7+M3Kq9VX9idYPFhrDlaWmp/jj7/83avbfh5PMhrrOA2V+n7tVaE/TMNSJ3FKs+XbiaIijO/CIX3Ph+MwI/Vhau9gFjxn0g8Gecn/jXVgqTxjGmZKPWYRR2ahHim/Nz34w4dpMi4mmsZx3dlgkgY6D8wtB/2kpFinj3wQxmXC1xPEo5BvWPPALC8vPzc/weH2VXCwfr4bbG3v7B3une8dHZ4FVlpuX4m5hBf821yrehFl3s1Noxb43l5xXH6Y0iQO0xl3N6b7OM+ycNznMT+YzKa3mh70OC+zMOXRv80ms1bQ4WLQeCHoeJQsRBXMWmGqHaTaEbododsRC5ezcDFVO6JqRzy0Ix7aEY/tiMd2xJd2xBceXzOnwUFY3gWKJ559roJ8EMRhUR8bm5U0oLJMxkPjkn5SJcqFDZLhpCTlfw7DlAY8LNNbyoLf9vj432ezhZiYzU+li9q0ra64MhmO5p2dmkZXlM4LF3OeF10RUa51nrmgDdtaiGvuO3Rh4VMRkYuInoqIXUT8VETfRfRNBE/DLt9dau4wCAOON6uQBrxZ9QMem8zvg48NnH2/9oF7iQbByprphHt5HuzYaannjVc5vQjS/J7KlzFvfqscwXvXwA4tDVbWpvUk/uctt6a2k+4u+KITHaarwQ5bQmneq4wDlJk31l2vO67XncVebYC+z90nr7xuPlsFLizge2sar3HO50nYx0kr3658t3Dii/lZ7uhb2dl3zW2d1R7/kaHhlVDfRLMkWmPT0YkbHNfDmevhrLOHU3em3Xfv8/naWxXDVF+FsuM0X5tPDlS701FJtNit6HPl28VeMYqi/2+7+g/HAfG0mNM7h5A+1/fvgr42AF5fk6KgMjB9ua62m662u7taD8rwHnPR6vDly5dhlSf9YKLMBpYMgiJXKuGU77ov0pCXWPMZX7tKkwgLXnOd92u0uosm6i+44Xlnm/PONv+Mzvj+x0Oyu3YdrVw/VphfGdvIBbjuXr78ioX4KsN0mHMRMMo675nV+irnYT9y06K7jrted92td3bnloX7VL6deX8/toGce6et/xmnLQxywRteMwqeOw2vL9scfX2i6j4WHX487+O43Ye76/nH8PWb4ycvfbm2IyWpsXNqDjg1cIA5mtXqIM3z0sr2qNbtYRPAUpRNmyuQWUeXvFi4jDBlGtdn063FkCpMk74M+Vgfl9m0lmYd3ZLS3adYZTa/LyqUyZmFStJ83OS7U+4iz4IqLJOQ17WqI0vS4dSrd57dMnpm+moWhy+HUCJfiaDEvhJD6U9bxdVcIV8hKANfGUAZ+soQyshXRlASX0mgfPKVT1DufOUOSuoraT1rZRYkitcxPzb1H82WWM/gi+DTROmgn49/owPztMKmfDT7kjcxQdb0Pfb7HuNTc1/JoRS+UkD57CufoZS+UkJRvqKgaF/RUCa+MoFS+UoF5d5X7qE8+MoDlEdfeYTyxVe+zOqy0S0AzuZ56exfNYtkWi+laCCWzfy69aheJS7CtoUuNIkjYLE2qhhYLIyqDyxWRUXAYklUA2CxHqohsFgM1QhYrIRqAiyWQfUJWKyB6g5YLIAqBU4FzoAzgcVAyxHOgYWZqwJYOLn6DCxsXJXAwsOVAlZyUoF195hI61bAwrfVPbAwbfUALBxbPQILu1ZfgJ1Xt1My33rYp8eyw7dUm65zX6baeZ07M9X269ybqfZg5+5MtRE792eq3di5Q1Ntyc49mmpfdu7SrD25T1Pt0M6dmmqbdu7VVHu1vVs7LfO1TGpP7sRUW7dzL6bav527MdUm7tyPqXZy545MtZ0792SqPd25K1Nt7M59mWp3d+7MVFu8c2+m2ueduzPVZu/cn6l2/NM7NK+FMonnFUq2jvWxjmWTbQBvCLwJvCnwFvCWwNvA2wLvAO8I/Bb4rcC7wLsC7wHvCfwO+J3A+8D7AveAewIfAB8IfAh8KPAR8JHAx8DHAp8Anwh8Cnwq8BnwmcDnwOcCXwBfCHwJfCnwFfCVwNfA1wK/B34v8A3wzdPbq286ql0nPLou/GutJ7QNqW362qbUtnxtS2rbvrYttR1f25HaW197K7VdX9uV2p6v7Untna+9k9q+r+1LredrPakd+NqB1A597VBqR752JLVjXzuW2omvnUjt1NdOpXbma2dSO/e1c6ld+NqF1C597VJqV752JbVrX7uW2ntfey+1G19ztr+UJUR1Q/Y5gp9gX83PrY7GNHVPtY5lkxqZvyHMoauJDffr4arBgkQ1QR1iqxAmqD5s7cEENUfVXAkqDVtnMEF9YasLJqgqbE3BBLWErSSYoIKw9QMT1A22amCCasHWCkxSMQ41QWVg6wImqAeqZkRRBdgagAlyv838TJDxbb5ngjxvszwTJQa8JsjpVTMtYlKqmiB/2+zNBFnb5mwmyNU2UzNBhrb5mUlXNeqXoVWYFiMz3/b33IFV1JjD+sJBPGrhm4lGSsMs6psz6gMIeUZDw+1vYGtJY0cHuEMm/H8glQwzc6r9DeyM25h2fiPTqbz+qTGra7FZY7TYqH1xU1NjUNdigw7QYnMO0WJjjtDiyxXXyob8hBab8U6MzdSYcH7nU2NA1+LBFKPI5svFkEyN6VyLTfcZLTZcKUZqaow2H6CpMZlr8UCLYWaDVWixue7RYmM9oMWmekSLDfWl9tKBybMPNbc5ln2G3GozKxNkVJtPmSCP2izKBNnT5k4myJk2YzJBprR5kgnyo82OTJAVbU5kglxoMyETZECb/5gg79msxwTZzuY6JshxNsMxQWazeY0J8pnNZkyQxWwOY4LcZTMXE2Qsm6+YIE/ZLMUE2cnmJibISTYjMUEmsnmICfKPzT5MkHVszmGCXGMzDZMbMYPIC5FMC9nxqNmIb80flTF6bukbpdcs//nNNWvYaGf1OrYuOqexMn/O36I4DUtiU43WzQ7En1gXe2qQmK9KaRzn/WQ85M7CSWqIGsyPs9lUme96z0g/1UGUp/0f6yZ6mPEiXG59UztW9m+Odd5s+rPfVje3puv6cqyE+/WGY/C/3nQMK0BvOYY1oLcdwyrQO45hHei3jmEl6F3HsBb0nmNYDfqdY1gPet8xrAjdcwxrQh84hlWhDx3DutBHjmFl6GPHsDb0iWNYHfrUMawPfeYYVog+dwxrRF84hlWiLx3DOtFXjmGl6GvHsFb0e8ewWvSNY3VFxkaOwzRNhmVYjJK4Dord427sPXXEGwLDHvGmwHBIvCUwTBJvCwyfxDsCwyrxW4HhlnhXYBgm3hMYnonfCQzbxPsCwzlxT2CYJz4QGP6JDwWGheIjgeGi+FhgGCk+ERheik8Fhp3iM4HhqPhcYJgqvhAYvoovBYa14iuB4a74WmAYLH4vMDwW3wjsCv8oDeO7KA/Lfh0U1WW+fSr2av1o/l1LJLwXbYDCetEmKJwXbYFa4z0PtuzfOyaKgjBQpK3nqR9svwgiikPD9ShRwX0+SfuMuEWBsn8d4YpzUgbmLa085Y7MWzb0UHAFav8ovNp84jY+EZ6OdkBh6egtKBwd7YLC0NEeKPwcvQOFnaN9ULg56oHCzNEBKLwcHYLCytERKJwcHYPCyNEJKHwcnYLCxtEZKFwcnYPCxNEFKDwcXYLCwtEVKBwcXYPCwNF7UPg3ugF19lVxmRS61pVzKENhUbUhMDyqNgWGSdWWwNge1bbAsJLaERheUm8FhpnUrsBwk9oTGHZS7wSGn9S+wDCU6gkMR6kDgWEpdSgwPKWOBIap1LHAcJU6ERi2UqcCw1fqTGAYS50LDGepC4FhLXUpMLylrgSGudS1wHCXei8w7KVuBJ5/HTjmZxKyj7dh/UVg84BCqE57/oOpeXRZR4vdt4EWm24TLfbaFlpssW202Fk7aLGh3qLFPtpFi+2zhxa75h1abJZ9tNgjPbTYGgdosSMO0WIjHKHF83+MFk/7CVo826do8SSfocVze44WT+kFWjyTl2jxBF6hxfN2jRZP13u0eJZuxOc1TwHNE4CZMpJTpuungefBmcka9nVfTh01fRHcJ3qUT3TApXhwz5VWQaVfrBOqda9Sbz5ezz1gAxceUsiW8tSq5ckW89Sq5smW89Sq58kW9NSq6MmW9NSq6ckW9dSq6smW9dSq68kW9tSq7MmW9tSq7ckW99Sq7smW99Sq78kW+NSq8MmW+NSq8ckW+dSq8smW+dSq88kW+tSq9MmW+tSq9ckW+9Sq9smW+9Sq98kW/NSq+MmW/NSq+ckW/dSq+smW/dSq+8kW/tSq/MmW/tSq/ckW/ySqf36K5UJHlxMKJuM+lemjefWuH+owGNKYSq5xTDtR7PRoYgoe37aFCZ1Ni4/T2zKb2oYtt0yvlBVJmXCh5Z0/f082erRFln1NyXwIV2Wtvt0bTKNQT4uZ/xFe5LGMPJ51XUyW9yn92o3YgPmd1K2Fz2mCjr8WVOgk7VMTeWsb86ufn8HbhM7jUajMW/vhROf26Z5K7wpbL2sXdcz8GptTFi+gT15c3eyIK1ngTcfF1U32Qmy/3/WD07Dg+p2aN784uteAWfA8aI794fXP357J+tjXekq8UNZrq6c487StscXEGLfEtJy574R9oaThbP4tb1uKNe7RtJJBQmW7a5UPdBY+INKBdhwni9y+Yld/AbzYS5FOzN1/Md9S+ep+bybfrtvvLUzgZVjiCkyj3b/mX/y8RWWZi8izhQnYzCvIpmEMepWngzLMzJelo/u85MciFT6q4Fnvh9fPzJtl9l+1TMb1+9Wq4PlX9v3GZ7eUpiLGfVn/PNjgBMhLfmz+98jrnTLzrqV59qo7FdHmpeh8MrQ50z6KJZpe2O5VHvRzMt3dJ3dJQf0kXG29bp+XWfqFynw27f3watYh5mMy2lqXpu/tea+7tMIoRYdivdD74TYZD/Rje+kUYWn+cMHbRjizr6TzXqvCIQXJOBjnzWOkpofVYHOUKzM8uSkA41GwFRajMf1GBVGe360ue181HhVmd87L/2CPl0N7Afz79oU5+lqg2SfrQD7q7tK6lcPs/5+IOGdDnZt3UFPSt2HE6yzN76OSwrtl+2+s/mh/gvrg9981B39cm/8bq8vXq2tvVl+ffLfypz80/9rq50v/uvRvS79dWlv6/dKflnaXjpculuKl2dJ/Lf330v/87v/e/OzNL958U4f+9CfNOb9a8n7e/Mv/A1bEAh8=</latexit>
d
<latexit sha1_base64="tf+EhrqYO0X2W5NmyDzSzoBqWOk=">AAA2U3icnZtdc9zIdYbptZM4TJzY8WVuUJFUdlISS9J+2L4zP0WKww/xW1xqtwDMmRmIwABC9wxJTU3+Rm6TH5WL/Jbc5HQ3et7TGFDrCqt2iX7egx6g++0+B0MoqfJM6Zcv/+dnX/38F3/113/zy79d/bu//9U//OOvf/NPF6qc1Cmdp2Ve1ldJrCjPxnSuM53TVVVTXCQ5XSa3m0a/nFKtsnJ8ph8q+lDEw3E2yNJYM/pwoz7VenbTp1zH8x9//eTl2kv7Ey0fvGoOnqw0P8c//ubblzf9Mp0UNNZpHiv1/auXlf4wi2udpTnNV28miqo4vY2H9D0fjuOC1IeZvep59IxJPxqUNf831pGl8oxZXCj1UCQcWcR6pMLe9OCPH2bZuJpoGqeus8Ekj3QZmduM+llNqc4f+CBO64yvJ0pHcR2nmgdjdXX1mfmJDrcvo4P1s91oa3tn73DvbO/o8DSy0mr7SswlPOff5lrV86QIbm6WtMD39orT+sOMJmmcz7m7Md2lZVHE4z6P98FkPrvRdK/HZV3E+aw/vykm81bQ4XLQeCnoeJQtRVXMWmGqHaTaEbododsRS5ezdDHTdsS0HXHfjrhvRzy0Ix7aEZ/bEZ95fM2cRgdxfRspnnj2torKQZTGlTs2NqtpQHWdjYfGJf1smikfNsiGk5pU+DkMcxrwsMxuqIh+3+Pjf53Pl2JSNj/VPmrTtrri6mw4WnR2YhpdUbqsfMxZWXVFJKXWZeGDNmxrKa6579iHxY9FJD4ieSwi9RHpYxF9H9E3ETwNu3x3ubnDKI443qxCGvAG1Y94bIqwDz42cP79qw/cSzKInrwynXAvz6IdOy1u3niV0/MoL++ofpHyhrfGEbxvDezQ0uDJq5mbxH+/4dbMdtLdBV90puN8LdphSyjNe5VxgDLzxrrvdcf3urPcqw3Qd6X/5Cevm89WkQ+L+N6axmuc82kS93HSk6+ffLN04vPFWf7oa9nZN81tnTqP/8TQ8EpwN9EsidbYdHTiB8f3cOp7OO3s4cSfaffdu3Kx9tbEMLmrUHacFmvz0YFqdzqqiZa7FX0++Xq5V4yi6P/rrv7jcUQ8Leb0ziGkT+7+fdCXBiDoa1JVVEemL9/VdtPVdndX61Ed32EuWh2+ePEinpZZP5oos4Flg6gqlco4zfvuqzzmJdZ8xpeu0iTCitdc5/0azXXRRP0/bnjR2eais82/oDO+//GQ7K7topXvxwqLK2Mb+QDf3YsXX7AQX2WcD0suAkZF5z2z6q5yEfYTNy2667jrdd/demd3fln4T+XbWfT3UxvIWXDa+l9w2tIgV7zhNaMQuNNwd9nm6MsT5fpYdvjxoo/jdh/+rhcfw9dvjh+99FVnR8pyY+fcHHBq4ABzNHfqIC/L2sr2yOn2sAlgKSlmzRXIrKNrXixcRpgyjeuz2dZyyDTOs74M+dEd18XMSfOObknp7lOsMl/cF1XK5MxKZXk5bvLdCXdRFtE0rrOY17VykTXpeBbUO09vGD01fTWLI5RjKEmoJFDSUEmh9Get4mqhUKgQlEGoDKAMQ2UIZRQqIyhZqGRQPobKRyi3oXILJQ+V3M1aXUSZ4nXMj0r9B7Mluhl8Hn2cKB31y/HvdGSeVtiUD2ZfCiYmKpq+x2HfY3xqGSollCpUKiifQuUTlDpUaigqVBQUHSoayiRUJlCmoTKFchcqd1DuQ+UeykOoPED5HCqf565s9AuAs3lZe/tPm0Uyc0spGYhls7huPXKrxEfYttCFJnECLNbGNAUWC2PaBxarYkrAYklMB8BiPUyHwGIxTEfAYiVMJ8BiGUw/Aos1ML0FFgtgmgPnAhfAhcBioOUIl8DCzNMKWDh5+glY2HhaAwsPTxWwkpMKrLvHRFp3Cix8O70DFqad3gMLx04fgIVdp5+BvVe3czLfetinx7rDt+RM17kvk3Ne585Mzn6dezM5D3buzuSM2Lk/k3Nj5w5NzpKdezQ5X3bu0qw9uk+Tc2jnTk3Opp17NTmvtndrrxWhVkjt0Z2YnHU792Jy/u3cjcmZuHM/Jufkzh2ZnJ0792Rynu7clckZu3NfJufuzp2ZnMU792ZyPu/cncmZvXN/Juf4x3doXgt1li4qlGId62Mdy6bYAN4QeBN4U+At4C2Bt4G3Bd4B3hH4DfAbgXeBdwXeA94T+C3wW4H3gfcF7gH3BD4APhD4EPhQ4CPgI4GPgY8Ffgf8TuAT4BOBT4FPBT4DPhP4HPhc4AvgC4EvgS8FvgK+Evg98HuBr4GvH99eQ9ORc53w6Lrwr7We0Dakthlqm1LbCrUtqW2H2rbUdkJtR2pvQu2N1HZDbVdqe6G2J7W3ofZWavuhti+1Xqj1pHYQagdSOwy1Q6kdhdqR1I5D7Vhq70LtndROQu1Eaqehdiq1s1A7k9p5qJ1L7SLULqR2GWqXUrsKtSupvQ+191K7DjVv+wtZQkyvyT5H8BPsy8W506MxzfxTrWfFxCHzN4QF9DWx4WE9PG2wIIkjqENsFcIE1YetPZig5pg2V4JKw9YZTFBf2OqCCaoKW1MwQS1hKwkmqCBs/cAEdYOtGpigWrC1ApNcjIMjqAxsXcAE9cC0GVFUAbYGYILcbzM/E2R8m++ZIM/bLM9EiQF3BDl92kyLmJSpI8jfNnszQda2OZsJcrXN1EyQoW1+ZtJVjYZl6DTOq5GZb/t74cBp0pjD+sJDPGrhm4lGyuMi6Zsz3AGEsqCh4fY3sLWksaMH3CET/j+QyoaFOdX+BvbGbUy7uJHZTF7/zJjVt9isKVps1L64qZkxqG+xQQdosTmHaLExR2jx5YprZUN+RIvNeCvGZmZMuLjzmTGgb/FgilFk85ViSGbGdL7FpvuEFhuuFiM1M0ZbDNDMmMy3eKDFMLPBpmixue7QYmPdo8WmekCLDfXZeenA5Nl7x22OZZ8ht9rMygQZ1eZTJsijNosyQfa0uZMJcqbNmEyQKW2eZIL8aLMjE2RFmxOZIBfaTMgEGdDmPybIezbrMUG2s7mOCXKczXBMkNlsXmOCfGazGRNkMZvDmCB32czFBBnL5ismyFM2SzFBdrK5iQlyks1ITJCJbB5igvxjsw8TZB2bc5gg19hMw+RazCDyQiLTQnE8ajbiG/NHZYyeX/pG6TXLf3FzzRo22qlbx9ZFZzRW5s/5W5TmcU1sqtG62YH4E12xpwaZ+aqUxmnZz8ZD7iye5IaoweK4mM+U+a73lPRjHSRl3v+pbpL7OS/C1dY3tWNl/+bo8mbTn/22urk17erLsRLu1xuewf960zOsAL3lGdaA3vYMq0DveIZ1oN94hpWgdz3DWtB7nmE16LeeYT3ofc+wInTPM6wJfeAZVoU+9AzrQh95hpWhjz3D2tDvPMPq0CeeYX3oU8+wQvSZZ1gj+twzrBJ94RnWib70DCtFX3mGtaLfe4bVoq89cxUZGzmN8zwb1nE1ylIXlPrH3TR46kg3BIY90k2B4ZB0S2CYJN0WGD5JdwSGVdI3AsMt6a7AMEy6JzA8k74VGLZJ9wWGc9KewDBPeiAw/JMeCgwLpUcCw0XpscAwUvpOYHgpPREYdkpPBYaj0jOBYar0XGD4Kr0QGNZKLwWGu9IrgWGw9L3A8Fh6LbAv/JM8Tm+TMq77LihxZb59Kg5q/WTxXUsivJdsgMJ6ySYonJdsgVrjPYu27N87JoqiOFKkreepH20/jxJKY8P1KFPRXTnJ+4y4RZGyfx3hinNSR+YtrTLnjsxbNnRfcQVq/yi81nziNj4Rnk52QGHp5A0oHJ3sgsLQyR4o/Jy8BYWdk31QuDnpgcLMyQEovJwcgsLKyREonJwcg8LIyTtQ+Dg5AYWNk1NQuDg5A4WJk3NQeDi5AIWFk0tQODi5AoWBk/eg8G9yDertq9I6q7TTlXcoQ2FRtSEwPKo2BYZJ1ZbA2B7VtsCwktoRGF5SbwSGmdSuwHCT2hMYdlJvBYaf1L7AMJTqCQxHqQOBYSl1KDA8pY4EhqnUscBwlXonMGylTgSGr9SpwDCWOhMYzlLnAsNa6kJgeEtdCgxzqSuB4S71XmDYS10LvPg6cMzPJGQfb2P3RWDzgEKoTnvhg6l5dFlHi923gRabbhMt9toWWmyxbbTYWTtosaHeoMU+2kWL7bOHFrvmLVpsln202CM9tNgaB2ixIw7RYiMcocXzf4wWT/s7tHi2T9DiST5Fi+f2DC2e0nO0eCYv0OIJvESL5+0KLZ6u92jxLF2Lz2ueAponADNlJKdMu6eBZ9GpyRr2dV9OHY4+j+4yPSonOuJSPLrjSquiOizWCdV6UKk3H68XHrCBSw8pZEt5atXyZIt5alXzZMt5atXzZAt6alX0ZEt6atX0ZIt6alX1ZMt6atX1ZAt7alX2ZEt7atX2ZIt7alX3ZMt7atX3ZAt8alX4ZEt8atX4ZIt8alX5ZMt8atX5ZAt9alX6ZEt9atX6ZIt9alX7ZMt9atX7ZAt+alX8ZEt+atX8ZIt+alX9ZMt+atX9ZAt/alX+ZEt/atX+ZIt/EtU/P8VyoaPrCUWTcZ/q/MG8etePdRwNaUw11zimnSl2ejIxBU9o28qEzmfVj7ObupjZhi23TK9UVFmdcaEVnL94TzZ5sEWWfU3JfAhXZa2+/RtMo1jPqnn4EUHksYw8nnddTFH2Kf/SjdiAxZ241tLnNEHHXwqqdJb3qYm8sY3F1S/O4G1Cl+koVuat/XiiS/t0T3Vwha2XtSsXs7jG5pTlC+hTEOeaHXE1C7zp+DjXZC+k9vvdMDiPK67fqXnzi6N7DZhHz6LmOBze8PztuayPQ62nxAtlvbZ6gjNP2hpbTIxxS8zruf9OOBRqGs4X3/K2pVTjHk0rG2RUt7tW5UAX8T0iPWjHcbIo7St27gvg5V6qfGLu/rP5lipU93tz+Xbdfm9pAi/iGldgGu3+Nf/i5y2q61JEni5NwGY5hWwaxqCXZT6o48J8WTq6K2t+LFLxg4qe9n54/dS8WWb/Vctk7N6vVhXPv7LvNz69oTwXMf7L+mfRBidAXvJj878HXu9UmHctzbOX61REm5eiy8nQ5kz7KJZpem67V2XUL8l0d5fdZhX1s3it9bp9WRf5Z6rL+az3w8t5h1iOyWivujR9Z8973aVVRqk6FOuF3g832XigH9pLp4pr84cL3jbiuX0lnfdaFQ8pysbRuGweIzXdr0Wbo1KZ4SlNAZiOoq24Go3pdypKyvJ2bTX4qvGoMrtzWf8be7we2gvg3zfPzdGXAs0+6QL5qLtL61YOs/9/JOKMDXVm3kHNSd/ECa+zvLxLaopvV+2/sfqT/YncwR++aQ7+9Grxb6wuXq+9+m7t9btvnvz5j82/tvrlyj+v/MvK71derfxh5c8ruyvHK+cr6cqnlf9Y+c+V//r2v7/93++++u4XLvSrnzXn/HYl+PnuV/8HSpr+Lg==</latexit>
Figure 4: 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 O( √ δ/d) in any direction. Hence any hyperplane, that wants to separate a constant fraction of the points in a cluster, needs to pass within distance O( √ δ/d) of the cluster center, as shown in the figure.
For our lower bound construction, we will have n points on the unit sphere in d-dimensions. Each neuron in the first layer represents a hyperplane in d-dimensions. The main observation that we use is that for every pair of points xi and xj such that they have different labels, there should be a 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 a hyperplane passing in between every pair of points xi and xj . For this problem we have the following theorem. Theorem 5. For every 0 < δ ≤ 12 and some universal constants C1 and C2, there exists a set of n points on the
d-dimensional sphere, with n ∈ [ C1d
2 log5(d/δ) δ , ( C2 δ ) d 2 ] ,
such that each pair of points is separated by a distance of at least δ, and one needs Ω ( logn√
δ log lognδ
) hyperplanes
to separate them.
We use essentially the same construction for both the problems. On the sphere, first we sample √ n points uniformly at random, which we call cluster centers. Around
each of these centers, we sample √ n points uniformly at random from the cap of radius √ δ, and call these sets of points clusters. Hence, in total we sample n 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 n ∈ [ d2
δ , 1 δd/2
] . In high dimensions, it can be shown that for each cluster and in any direction, most
points lie within a distance √ δ/d of the cluster center. Hence, if a hyperplane aims to ‘effectively’ separate pairs of points in a cluster, it needs to pass within distance √ δ/d of the cluster center. It can also be shown that in high dimensions any hyperplane can only pass within distance √ δ/d of the cluster centers of √ δ 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 a hyperplane can ‘effectively’ separate) .
We know that the number of clusters is √ n, and we showed above that (# clusters a hyperplane can ‘effectively’ separate) is √ δ fraction of the clusters, that is O( √ nδ). Finally, for the term (# hyperplanes needed per cluster), we use 1 for the memorization problem, 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) = Ω(log2 √ n) since there √ n points in
each cluster and hence we need at least log2 √ n hyperplanes per cluster. Substituting these values gives us the bounds in Theorems 2 and 5.
Note that we skipped many details in the sketch above. The complete proof is provided in the appendix, and the construction there is slightly different.

heading: 8 Conclusion
text: In this work, we study the memorization capacity of threshold networks under the δ-separation assumption. We improve the existing bounds on the number of neurons and weights required, from exponential in δ, to almost linear. We also prove new, δ-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 #1844951, Sony Faculty Innovation Award, AFOSR & AFRL Center of Excellence Award FA9550-18-1-0166, NSF TRIPODS Award #1740707, and ONR YIA Grant N00014-21-1-2806. AK acknowledges the support of NSF CAREER Award IIS-1845032, and ONR Grant N00014-19-1-240.

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

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. The 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). 

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.

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.  The main result is a construction of a deep and relatively sparse network that memorizes arbitrary labels of 'well-separated' data sets. If 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. This 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. The 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.