Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
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). 
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
main paper provides sufficient intuition. 

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

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

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

The paper considers binary labeling. Comments on memorization problem with multiple labels (more than 2) would be useful as classification problems can have multiple labels. 

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

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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

Quality: The paper is technically sound. The theoretical results are clearly stated, and proof sketches are given in the main text.

Clarity: The paper is clearly written and well organized. The proof sketches are easy to follow.

Significance: 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.

Other comments:
- 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.
- line 308: The packing/covering number should be $\Theta((C/\delta)^d)$ for some constant $C$. Though it doesn't matter after taking logarithm.
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_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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. 

Update: Thank you for your response. I decide to increase my score to 7.
limitations_and_societal_impact: I think it would be nice to include more comparison with prior results. 
(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.
(2) On line 233, it is mentioned that Yun et al. (2019) used a similar strategy; what are the differences?

Here are some typos:
(1) On line 88, "Veshynin" should be "Vershynin".
(2) On line 261, it seems that s_i^{(2)} should have dimension K instead of d^{(2)}.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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. 
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.
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. 
It goes through a well-thought compression scheme followed by a separation procedure.
The compression allows to keep the network size small, and the separation procedure allows to memorize arbitrary labels.
The ideas are rather elegant and might even be of further use in other scenarios.

Moreover, the paper is particularly well written and does a pretty good job at introducing the relevant ideas and motivations.

Given the above, I am confident that this paper will be of interest to the NeurIPS community and am happy to recommend acceptance.

I would still like to raise a few questions/suggestions which I hope the authors can respond to:

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

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

- 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$?

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

- 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? 

- 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.
Another 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.

- 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. 
However, 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.



limitations_and_societal_impact: The authors adequately addressed the limitations and potential negative societal impact of their work
review_title: null

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