Generalizablity of Memorization Neural Network

The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily.

Question 1. Proposition 3.8 - where is the proof? Also, it is not clear to me why the constructions in [54,48] are probabilistic.

We deduce proposition 3.8 from the proof process of theorem in these papers, considering that proposition 3.8 can be directly obtained from the proof in the corresponding paper, the proof is not given. In the revised version of the paper, we will give a sketch of the proof for Proposition 3.8. This randomness comes from a technique of memorization: in the construction of a memorization network, we require a special vector to compress data into one dimension, but this vector is not easy to calculate directly. However, every time we randomly select a vector, there is a non-zero (0.5) chance of selecting the required vector, and the randomness comes from this random selection. We have described some similarities in the proof of Theorem 4.1, including lines 220-223 and 648-649 (and the proof above lines 648-649) of the paper.

Question 2. There is something unclear about the proof of Theorem 5.3.

The $D_{tr}$ and $D$ used in our proof in Appendix E4 is the $D_{tr}$ and $D$ in Theorem 5.3, they can be any distribution $D$ and a dataset $D_{tr}$ selected from it, and we will clarify this point in the future. Our proof is for any distribution $D$. The core of the proof is in lines 1060-1065, and the proof in these lines applies to any distribution. Lemma E2 is also for any distribution $D$. Therefore, the whole proof is really for any distribution. In the revised version of the paper, we will make this clear.

Question 3. The comparison between interpolation and memorization learning is unclear. Specifically, in what cases do the results on interpolation learning already provide generalization bounds for memorization learning?

Generalization bounds for interpolation learning are only established in linear or approximately linear situations. Our sample complexity results are for all memrozaition networks and hence are valid in all cases.

Question 4. Results and comparisons on implicit bias toward margin maximization of neural networks do not appear.

Thank you for pointing out this. There are many articles that analyze the margin maximization or generalization under gradient. These works can prove the results under some assumptions, such as NTK, Lip conditions, two-layer networks, etc., which are very good. In comparison, our results consider all the memorization algorithms and we have not made so many assumptions, so we believe that our work has certain advantages. We will add these in the revised version of the paper.

Question 5. The size of $N_D$ and $S_D$.

Firstly, in most cases, we have $N_D<S_D$, and $S_D$ is more susceptible to the influence of separation bound. Second, in the worst-case scenario, they are exponential in n, and this is inevitable as shown in Corollary 6.4, where a lower bound $2^{O(n)}$ for $N_D$ is given. Also, in line 1425, an upper bound $n^{O(n)}$ for $S_D$ is given. Third, for some ``good'' distributions, we believe that $N_D$ and $S_D$ are reasonably small, from the nice practical performance of deep learning.

For some simple situations, we can estimate their values. We use linear data as a simple example to calculate $N_D$ and $S_D$.

If the distribution $D\in R^n$ is linear separable and defined as: $x\in[0,1]^n$ has label $1$ if $\langle\mathbf{1},x\rangle>199n/200$, $x\in[0,1]^n$ has label $-1$ if $\langle\mathbf{1},x\rangle<n/200$, where $\mathbf{1}$ is the vector whose weight is all 1.

Then $N_D=O(n)$ for any $c$, because $D$ is linear separable.

And $S_D=2$. Because the distance between the points with different labels is at least $0.49\sqrt{n}$; and the distance between point with label 1 and point $\mathbf{1}$ is at most $\sqrt{n/50}$; and the distance between point with label -1 and origin is at most $\sqrt{n/50}$. By $0.49/3.1>\sqrt{1/50}$, then let $S=\\{0,\mathbf{1}\\}$ and by definition 7.1, we know that $S$ is a nearby set of $D$, then $S_D=2$.

Question 6. What is the size of the network defined in Theorem 7.3?

The size of the network is affected by the data distribution. In the worst-case, the network has depth 3, width N, and $O(N^2)$ parameters. As said in lines 103-107, to ensure generalization, we abandoned many classic techniques, which resulted in an increase of parameters. We will add this information in the revised version.

For Reviewer QwyD:

The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily. Also thank you for pointing out the typos in our writing, we will correct them in future versions.

Question 1. No estimates of $N_D$ and $S_D$ are given. Can $N_D$ and $S_D$ be provided even for simple toy examples (e.g., linearly separable data)?

(1): The meaning of $N_D$ and $S_D$ in terms of generalization. $O(N^2_D)$ represents the minimum amount of data required for any memorization algorithm to achieve generalization, while $O(S_D)$ represents the upper bound of the amount of data required for achieving generalization by efficient memorization algorithms. We mainly pointed out the existence of these two values, but estimated them is not the core of the paper, the estimation of them can be a future work.

(2): How big are $N_D$ and $S_D$? Firstly, in most cases, we have $N_D<S_D$, and $S_D$ is more susceptible to the influence of separation bound. Second, in the worst-case scenario, they are exponential in n, and this is inevitable as shown in Corollary 6.4, where a lower bound $2^{O(n)}$ for $N_D$ is given. Also, in line 1425, an upper bound $n^{O(n)}$ for $S_D$ is given. Third, for some ``good'' distributions, we believe that $N_D$ and $S_D$ are reasonably small, from the nice practical performance of deep learning and also be showen in the following simple example.

(3): Can we calculate $N_D$ and $S_D$? Unfortunately, because these two values are closely related to the properties of the distribution $D$, calculating these two values for any distribution is not easy, as we said in line 405 to 406. But for some simple situations, we can estimate their values. We use linear data as an example to calculate $N_D$ and $S_D$.

If the distribution $D\in R^n$ is linear separable and defined as: $x\in[0,1]^n$ has label $1$ if $\langle\mathbf{1},x\rangle>199n/200$, $x\in[0,1]^n$ has label $-1$ if $\langle\mathbf{1},x\rangle<n/200$, where $\mathbf{1}$ is the vector whose weight is all 1.

Then $N_D=O(n)$ because $D$ is linear separable.

And $S_D=2$. Because the distance between the points with different labels is at least $0.49\sqrt{n}$; and the distance between point with label 1 and point $\mathbf{1}$ is at most $\sqrt{n/50}$; and the distance between point with label -1 and origin is at most $\sqrt{n/50}$. By $0.49/3.1>\sqrt{1/50}$, then let $S=\\{0,\mathbf{1}\\}$ and by definition 7.1, we know that $S$ is a nearby set of $D$, then $S_D=2$.

The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily. Also thank you for pointing out the typos in our writing, we will correct them in future versions.

1. Question (W1): Compactness of the input domain.

The current proofs are for the compact input domain. We will change $R^n$ to $[0,1]^n$ in the Introduction Section. After evaluating the proofs, we find that only Theorems 5.1, 5.3, 6.1 still hold when we consider the distributions in $R^n$. On the other hand, the extension to a larger domain $R^n$ is not a good idea, because networks with finite parameters can not approximate many of distributions over $R^n$, so that it is impossible to study guaranteed generalization theorems under such infinite domain, and th4.1, th4.3, th6.5 and th7.3 are incorrect on $R^n$. So, if we need to study about the distributions on $R^n$, we need to add more constraints to the distributions.

2. Question (W2): Where comes the randomness in Theorem 4.1?

This randomness comes from a technique of memorization: in the construction of a memorization network, we require a special vector to compress data into one dimension, but this vector is not easy to calculate directly. However, every time we randomly select a vector, there is a non-zero (0.5) chance of selecting the required vector, and the randomness comes from this random selection. We have described this in lines 220-223 and 648-649 (and the proof above lines 648-649) of the paper. We will make this clearer in the revised version of the paper.

3. Question (W3): Efficiency of memorization algorithm in Theorem 4.3?

Theorem 4.3 is an existence result that mainly demonstrates the existence of $N_D$. The efficiency of the memorization algorithms are given in Theorem 6.5 and Theorem 7.3. If $para(L(D_{tr}))\le N_D$, (2) of Theorem 6.5 shows that such memorization algorithms are not efficient. If $N>O(S_D)$, then Theorem 7.3 shows that there exists an efficient memorization algorithm.

4. Question (W4): Parameter complexity of efficient memorization algorithm in Theorem 7.3.

The number of parameters are affected by the data distribution. In the worst-case, the network will have $O(N^2)$ parameters. As said in line 103-107, to ensure generalization, we abandoned many classic techniques, which resulted in an increase of parameters. We will add this information in the revised version.

5. Question (Q1): Architectural constraint: ReLU network

The reason why we consider the fully connected ReLU network is because this type of network is very classic, and it has been widely applied in previous related research. For other structure networks like CNN or with other activation functions, the conclusions in this paper may be different. The main results in the paper are based on the expressive power of the fully-connected ReLU network, such as VCdim, the ability to fit discrete points and so on, so after replacing the network structure, we can still use the ideas in the paper to re-establish the $N_D$, $S_D$ and so on. This is certainly an important direction for future research. We will mention this in the revised version of the paper.

6. Question (Q2): There is an $\epsilon^2$ gap between the upper and lower.

You are right. We want to mention that the lower and upper bounds are at the same order of magnitude for the number of samples $N^2_D$. We believe that it is still room to improve the factor $(1-2\epsilon-\delta)$ in the lower sample complexities. But currently, we do not achieve this yet.

7. Question (Q3): How to get the proof of Corollary 6.4?

According to Lemma E.2, for any $n,c$, we can find $2^{n/[c^2]}$ points with distance $c$ in $[0,1]^n$. Then we take suitable $n,c,k=2^{n/[c^2]}$ to make the contents in lines 1131 to 1133 of the proof of Theorem 6.1 valid. Finally, follow the part 2-4 in the proof of Theorem 6.1, according to line 1159-1162 and the begining of part 4, we can prove Corollary 6.4. We will add more details about the proof in the future.

8. Question (Q4): Algorithm in Theorem 7.3 as an initialization.

We can only now provide some simple experiments. In the case of a small sample size, using our method as initialization for training may be helpful; while in the case of a large sample size, the training with random initialization can reach a very high level, so using our method for training does not bring significant improvement.

We do binary classification problems on CIFAR-10 dataset by considering 5 pairs binary classification problems: samples with label 2i and label 2i+1, where $i=0,1,2,3,4$. Randomly select 1000 samples from each category as the training set. We compare four methods: train a DNN, train a VGG-16, ours, training with our methods as initialization. The accuracies are given below.

|Pair of Label|CNN|DNN|Ours|Ours+Training| |0,1|0.95|0.85|0.76|0.90| |2,3|0.84|0.73|0.59|0.75| |4,5|0.87|0.72|0.65|0.77| |6,7|0.98|0.84|0.69|0.84| |8,9|0.92|0.82|0.68|0.84|

It is easy to see that: (1): Our methods cannot go beyond training. (2): If the dataset is relatively small, using our method as an initialization can help improve accuracy. (3): Since the paper focuses on a fully connected network structure, its performance is inferior to that of CNN in image classification tasks.

9. Question (Q5): Generalizability of memorization v.s. non-memorization networks.

We believe that a non-memorization network can generalize better than some memorization networks mainly in the following situation: The data set contains significant bad data, such as outliers. One weakness of memorization algorithm is that it must fit all the data, and the network will learn non-existent features from outliers, thus harming generalization. In this situation, a non-memorization algorithm can ignore the bad data in certain sense and thus work better.

The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily.

Question 1. Why consider the distribution D(n,c) defined in Definition 3.1?

D(n,c) is indeed a distribution with relatively good properties, as we explain this in Remark 3.2 of the paper, there are three main reasons and advantages to use such a distribution:

(1): Proposition 3.3 shows that there exists a distribution D not in D(n,c), such that any network is not generalizable over D, so if conisdering general distributions, we cannot have a general generalization theory at all.

(2): D(n,c) is suitable for most of real-world distributions, like image classification.

(3): D(n,c) is abstracted from previous related work. In order to achieve memorization with networks with sub-linear number of parameters, it requires that data has a positive separation bound, like [48] and [54]. So, when studying the distribution in $D(n,c)$, many related techniques and classic conclusions can be used in the memorization, such as [48] and [54], on the other hand, we need to point out that the existing conclusions cannot directly derive our theorem.

For the relationship between the parametric rate and error rate you mentioned, we need to point out that if we know which regions the network can correctly classify, we can indeed estimate the error rate using density. However, based on our research, we only know that the network has memorized a dataset, and we cannot directly obtain which regions the network can correctly predict. Research on more complex distributions or noisy distributions can be a future research direction.

Question 2. In Theorem 4.3, whether the memorization algorithm L is dependent on D, or at least c. It will be good if such an algorithm can obtain memorization agnostic to the knowledge of c.

In the proof, such algorithm is depended on c. But it is easy to make it no longer dependent on c, we will add an additional step to the memorization algorithm, we calculate the shortest distance $c '$ between two samples with different labels in the input dataset at first, easy to see that $c'\ge c$, and then use $c'$ to replacing $c$ in the proof of th4.3. After doing this, such an algorithm is completely only dependent on the input dataset, and for any distribution, there is an upper bound on the number of parameters of output network.

This is a good suggestion, and we will make modifications in future versions, thank you.

Question 3. The upper bound and lower bound does not exactly match in its current form in terms of epsilon.

You are right that this lower bound only reaches tightness for $N^2_D$, but there is still room to improve the factor $(1-2\epsilon-\delta)$. But currently, we do not achieve this yet.

Question 4. I think the introduction part can make a clear, or informal definition of what is generalization under the well-separated classification task.

We will do this in the revised version.