Generalizablity of Memorization Neural Network

Authors: lijia  yu
xiao-shan  gao
lijun  zhang
yibo  miao
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-13 10:53:12

Abstract: The neural network memorization problem is to study the expressive power of neural networks to interpolate a finite dataset. Although memorization is widely believed to have a close relationship with the strong generalizability of deep learning when using overparameterized models, to the best of our knowledge, there exists no theoretical study on the generalizability of memorization neural networks. In this paper, we give the first theoretical analysis of this topic. Since using i.i.d. training data is a necessary condition for a learning algorithm to be generalizable, memorization and its generalization theory for i.i.d. datasets are developed under mild conditions on the data distribution. First, algorithms are given to construct memorization networks for an i.i.d. dataset, which have the smallest number of parameters and even a constant number of parameters. Second, we show that, in order for the memorization networks to be generalizable, the width of the network must be at least equal to the dimension of the data, which implies that the existing memorization networks with an optimal number of parameters are not generalizable. Third, a lower bound for the sample complexity of general memorization algorithms and the exact sample complexity for memorization algorithms with constant number of parameters are given. As a consequence, it is shown that there exist data distributions such that, to be generalizable for them, the memorization network must have an exponential number of parameters in the data dimension. Finally, an efficient and generalizable memorization algorithm is given when the number of training samples is greater than the efficient memorization sample complexity of the data distribution.

Main paper: 
 introduction: 
 Memorization is to study the expressive power of neural networks to interpolate a finite dataset [9] . The main focus of the existing work is to study how many parameters are needed to memorize. For any dataset D tr of size N and neural networks of the form F : R n → R, memorization networks with O(N ) parameters have been given with various model structures and activation functions [31, 50, 30, 29, 26, 47, 56, 11, 65] . On the other hand, it is shown that in order to memorize an arbitrary dataset of size N [64, 56] , the network must have at least Ω(N ) parameters, so the above algorithms are approximately optimal. Under certain assumptions, it is shown that sublinear O(N 2/3 ) parameters are sufficient to memorize D tr [49] . Furthermore, Vardi et al. [55] give a memorization network with optimal number of parameters: O(√ N ).Recently, it is shown that memorization is closely related to one of the most surprising properties of deep learning, that is, over-parameterized neural networks are trained to nearly memorize noisy data and yet can still achieve a very nice generalization on the test data [45, 7, 4] . More precisely, the double descent phenomenon [45] indicates that when the networks reach the interpolation threshold, larger networks tend to have more generalizability [41, 10] . It is also noted that memorizing helps generalization in complex learning tasks, because data with the same label have quite diversified features and need to be nearly memorized [19, 20] . A line of research to harvest the help of memorization to generalization is interpolation learning. Most of recent work in interpolation learning shows generalizability of memorization models in linear regimes [7, 12, 38, 53, 59, 66] .As far as we know, the generazability of memorization neural networks has not been studied theoretically, which is more challenging compared to the linear models, and this paper provides a systematic study of this topic. In this paper, we consider datasets that are sampled i.i.d. from a data distribution, because i.i.d. training dataset is a necessary condition for learning algorithms to have generalizability [54, 44] . More precisely, we consider binary data distributions D over R n × {-1, 1} and use D tr ∼ D N to mean that D tr is sampled i.i.d. from D and |D tr | = N . All neural networks are of the form F : R n → R. The main contributions of this paper include four aspects.First, we give the smallest number of parameters required for a network to memorize an i.i.d. dataset.Theorem 1.1 (Informal. Refer to Section 4). Under mild conditions on D, if D tr ∼ D N , it holds (1) There exists an algorithm to obtain a memorization network of D tr with width 6 and depth O( √ N ).(2) There exists a constant N D ∈ Z + depending on D only, such that a memorization network of D tr with at most N D parameters can be obtained algorithmically.N D is named as the memorization parameter complexity of D, which measures the complexity of D under which a memorization network with ≤ N D parameters exists for almost all D tr ∼ D N .Theorem 1.1 allows us to give the memorization network for i.i.d dataset with the optimal number of parameters. When N is small so that √ N ≪ N D , the memorization network needs at least Ω( √ N ) parameters as proved in [6] and (1) of Theorem 1.1 gives the optimal construction. When N is large, (2) of Theorem 1.1 shows that a constant number of parameters is enough to memorize.Second, we give a necessary condition for the structure of the memorization networks to be generalizable, and shows that even if there is enough data, memorization network may not have generalizability.Theorem 1.2 (Informal. Refer to Section 5) . Under mild conditions on D, if D tr ∼ D N , it holds (1) Let H be a set of neural networks with width w. Then, there exist an integer n > w and a data distribution D over R n × {-1, 1} such that, any memorization network of D tr in H is not generalizable.(2) For almost any D, there exists a memorization network of D tr , which has O( √ N ) parameters and is not generalizable. Theorem 1.2 indicates that memorization networks with the optimal number of parameters O( √ N ) may have poor generalizability, and commonly used algorithms for constructing fixed-width memorization networks have poor generalization for some distributions. These conclusions demonstrate that the commonly used network structures for memorization is not generalizable and new network structures are needed to achieve generalization.Third, we give a lower bound for the sample complexity of general memorization networks and the exact sample complexity for certain memorization networks.Theorem 1.3 (Informal. Refer to Section 6) . Let N D be the memorization parameter complexity defined in Theorem 1.1. Under mild conditions on D, we have (1) Lower bound. In order for a memorization network of any D tr ∼ D N to be generalizable, N must be ≥ Ω(N 2 D ln 2 (N D ) ) 2 .(2) Upper bound. For any memorization network with at most N D parameters for D tr ∼ D N , if N = O(N2 D ln N D ), then the network is generalizable.Notice that the lower bound is for general memorization networks and the upper bound is for memorization networks with ≤ N D parameters, which always exist by (2) of Theorem 1.1. In the latter case, the lower and upper bounds are approximately the same, which gives the exact sample complexity O(N 2 D ) in this case. In other words, a necessary and sufficient condition for the memorization network in (2) of Theorem 1.1 to be generalizable is N = O(N 2 D ). Remark 1.4. Unfortunately, these generalizable memorization networks cannot be computed efficiently, as shown by the following results proved by us.(1) If P ̸ = N P , then all networks in (2) of Theorem 1.3 cannot be computed in polynomial time.(2) For some data distributions, an exponential (in the data dimension) number of samples is required for memorization networks to achieve generalization.Finally, we want to know that does there exist a polynomial time memorization algorithm that can ensure generalization, and what is the sample complexity of such memorization algorithm? An answer is given in the following theorem. Theorem 1.5 (Informal. Refer to Section 7) . There exists an S D ∈ Z + depending on D only such that, under mild conditions on D, if N = O(S D ), then we can construct a generalizable memorization network with O(N 2 n) parameters for any D tr ∼ D N in polynomial time.S D is named as the efficient memorization sample complexity for D, which measures the complexity of D so that the generalizable memorization network of any D tr ∼ D N can be computed efficiently if N = O(S D ).The memorization network in Theorem 1.5 has more parameters than the optimal number O( √ N ) of parameters required for memorization. The main reason is that building memorization networks with O( √ N ) parameters requires special technical skill that may break the generalization. On the other hand, as mention in [7] , over-parametrization is good for generalization, so it is reasonable for us to use more parameters for memorization to achieve generalization.Remark 1.6. We explain the relationship between our results and interpolation learning [7] . Interpolation learning uses optimization to achieve memorization, which is a more practical approach, while our approach gives a theoretical foundation for memorization networks. Once an interpolation is achieved, Theorem 1.2, (1) of Theorem 1.3, and Theorem 1.5 are valid for interpolation learning. For example, according to (1) of Theorem 1.3, Ω(N 2 D ) is a lower bound for the sample complexity of interpolation learning, and by Theorem 1.5, O(S D ) is an upper bound for the sample complexity of efficient interpolation learning.Main Contributions. Under mild conditions for the data distribution D, we have • We define the memorization parameter complexity N D ∈ Z + of D such that, a memorization network for any D tr ∼ D N can be constructed, which has O( √ N ) or ≤ N D parameters. Here, the memorization network has the optimal number of parameters.• We give two necessary conditions for the construction of generalizable memorization networks for any D tr in terms of the width and number of parameters of the memorization network.• We give a lower bound Ω(N 2 D ) of the sample complexity for general memorization networks as well as the exact sample complexity O(N 2 D ) for memorization networks with ≤ N D parameters. We also show that for some data distribution, an exponential number of samples in n is required to achieve generalization.• We define the efficient memorization sample complexity S D ∈ Z + for D, so that generalizable memorization network of any D tr ∼ D N can be computed in polynomial time, if N = O(S D ). 
related work: 
 Memorization. The problem of memorization has a long history. In [9] , it is shown that networks with depth 2 and O(N ) parameters can memorize a binary dataset of size N . In subsequent work, it is shown that networks with O(N ) parameters can be a memorization for any dataset [31, 50, 11, 30, 65, 29, 64, 56, 26, 47] and such memorization networks are approximately optimal for generic dataset [64, 56] . Since the VC dimension of neural networks with N parameters and depth D and with ReLU as the activation function is at most O(N D) [24, 5, 6] , memorizing some special datasets of size N requires at least Ω( √ N ) parameters and there exists a gap between this lower bound Ω( √ N ) and the upper bound O(N ). Park et al. [49] show that a network with O(N 2/3 ) parameters is enough for memorization under certain assumptions. Vardi et al. [55] further give the memorization network with optimal number of parameters O( √ N ). In [22] , strengths of both generalization and memorization are combined in a single neural network. Recently, robust memorization has been studied [35, 62] . As far as we know, the generazability of memorization neural networks has not been studied theoretically.Interpolation Learning. Another line of related research is interpolation learning, that is, leaning under the constraint of memorization, which can be traced back to [52] . Most recent works establish various generalizability of interpolation learning in linear regimes [7, 12, 38, 53, 59, 66] . For instance, Bartlett et al. [7] prove that over-parametrization allows gradient methods to find generalizable interpolating solutions for the linear regime. In relation to this, how to achieve memorization via gradient descent is studied in [13, 14] . Results of this paper can be considered to give sample complexities for interpolation learning.Generalization Guarantee. There exist several ways to ensure generalization of networks. The common way is to estimate the generalization bound or sample complexity of leaning algorithms. Generalization bounds for neural networks are given in terms of the VC dimension [24, 5, 6] , under the normal training setting [27, 44, 8] , under the differential privacy training setting [1] , and under the adversarial training setting [60, 58] . In most cases, these generalization bounds imply that when the training set is large enough, a well-trained network with fixed structure has good generalizability. On the other hand, the relationship between memorization and generalization has also been extensively studied [45, 41, 10, 19, 20] . In [25] , sample complexity of neural networks is given when the norm of the transition matrix is limited, in [36] , sample complexity of shallow transformers is considered. This paper gives the lower bound and upper bound (in certain cases) of the sample complexities for interpolation learning. 
notation: 
 In this paper, we use O(A) to mean a value not greater than cA for some constant c, and O to mean that small quantities, such as logarithm, are omitted. We use Ω(A) to mean a value not less than cA for some constant c, and Ω to mean that small quantities, such as logarithm, are omitted.In this paper, we consider feedforward neural networks of the form F : R n → R and the l-th hidden layer of F(x) can be written asX l = σ(W l X l-1 + b l ) ∈ R n l ,where σ = Relu is the activation function,X 0 = x and N 0 = n. The last layer of F is F(x) = W L+1 X L + b L+1 ∈ R, where L is the number of hidden layers in F. The depth of F is depth(F) = L + 1, the width of F is width(F) = max L i=1 {n i }, the number of parameters of F is para(F) = L i=0 n i (n i+1 + 1). Denote H(n) to be the set of all neural networks in the above form.In this paper, we consider binary classification problems and use D to denote a joint distribution onD(n) = [0, 1] n × {-1, 1}.To avoid extreme cases, we focus mainly on a special kind of distribution to be defined in the following. Definition 3.1. For n ∈ Z + and c ∈ R + , D(n, c) is the set of distributions D on D(n), which has a positive separation bound: inf (x,1),(z,-1)∼D ||x -z|| 2 ≥ c.The accuracy of a network F on a distribution D is defined as A D (F) = P (x,y)∼D (Sgn(F(x)) = y).We use D tr ∼ D N to mean that D tr is a set of N data sampled i.i.d. according to D. For convenience, dataset under distribution means that the dataset is i.i.d selected from a data distribution. Remark 3.2. We define the distribution with positive separation bound in for the following reasons. Remark 3.5. Memorization networks can also be defined more strictly as F(x) = y for any (x, y) ∈ D tr . In Proposition 4.10 of [62] , it is shown that these two types of memorization networks need essentially the same number of parameters.To be more precise, we treat memorization as a learning algorithm in this paper, as defined below.Definition 3.6. L :∪ n∈Z+ 2 D(n) → ∪ n∈Z+ H(n) is called a memorization algorithm if for any n and D tr ∈ D(n), L(D tr ) is a memorization network of D tr .Furthermore, a memorization algorithm L is called an efficient memorization algorithm if there exists a polynomial poly : R → R such that L(D tr ) can be computed in time poly(size(D tr )), where size(D tr ) is the bit-size of D tr . Remark 3.7. It is clear that if L is an efficient memorization algorithm, then para(L(D tr )) is also polynomial in size(D tr ).There exist many methods which can construct memorization networks in polynomial times, and all these memorization methods are efficient memorization algorithms, which are summarized in the following proposition. Proposition 3.8. The methods given in [9, 62] are efficient memorization algorithms. The methods given in [55, 49] are probabilistic efficient memorization algorithms, which can be proved similar to that of Theorem 4.1. More precisely, they are Monte Carlo polynomial-time algorithms. 
optimal memorization network for dataset under distribution: 
 By the term "dataset under distribution", we mean datasets that are sampled i.i.d. from a data distribution, and is denoted as D tr ∼ D N . In this section, we show how to construct the memorization network with the optimal number of parameters for dataset under distribution.To memorize N samples, Ω( √ N ) parameters are necessary [6] . In [55] , a memorization network is given which has O( √ N ) parameters under certain conditions, where O means that some logarithm factors in N and polynomial factors of other values are omitted. Therefore, O( √ N ) is the optimal number of parameters for a network to memorize certain dataset. In the following theorem, we show that such a result can be extended to dataset under distribution. Proof Idea. This theorem can be proven using the idea from [55] . Let D tr = {(x i , y i )} N i=1 . The mainly different is that in [55] , it requires ||x i -x j || ≥ c for all i ̸ = j, which is no longer valid when D tr is sampled i.i.d. from distribution D. Since D has separation bound c > 0, we have ||x i -x j || ≥ c for all i, j satisfying y i ̸ = y j , which is weaker. Despite this difference, the idea of [55] can still be modified to prove the theorem. In constructing such a memorization network, we need to randomly select a vector, and each selection has a probability of 0.5 to give the correct vector. So, repeat the selection ln(1/ϵ) times, with probability 1 -ϵ, we can get at least one correct vector. Then we can construct the memorization network based on this vector. Detailed proof is given in Appendix B. Remark 4.2. The algorithm in Theorem 4.1 is a Monte Carlo polynomial-time algorithm, that is, it gives a correct answer with arbitrarily high probability. The algorithm given in [55] is also a Monte Carlo algorithm.In this section, we prove an interesting fact of memorization for dataset under distribution. We show that for a distribution D ∈ D(n, c), there exists a constant N D ∈ Z + such that for all datasets sampled i.i.d. from D, there exists a memorization network with N D parameters. Proof Idea. It suffices to show that we can find a memorization network of D tr with a constant number of parameters, which depends on D only. The main idea is to take a subset D ′ tr of D tr such that D tr is contained in the neighborhood of D ′ tr . It can be proven that the number of elements in this subset is limited. Then construct a robust memorization network of D ′ tr with certain budget [62] , we obtain a memorization network of D tr , which has a constant number of parameters. The proof is given in Appendix C.Combining Theorems 4.1 and 4.3, we can give a memorization network with the optimal number of parameters. Remark 4.4. What we have proven in Theorem 4.3 is that a memorization algorithm with a constant number of parameters can be found, but in most of times, we have N ′ D > N D . Furthermore, if N ′ D is large for the memorization algorithm, the algorithm can be efficient. Otherwise, if N ′ D is closed to N D , the algorithm is usually not efficient.  
condition on the network structure for generalizable memorization: 
 In the preceding section, we show that for the dataset under distribution, there exists a memorization algorithm to generate memorization networks with the optimal number of parameters. In this section, we give some conditions for the generalizable memorization networks in terms of width and number of parameters of the network. As a consequence, we show that the commonly used memorization networks with fixed width is not generalizable.First, we show that networks with fixed width do not have generazability in some situations. Reducing the width and increasing depth is a common way for parameter reduction, but it inevitably limits the network's power, making it unable to achieve good generalization for specific distributions, as shown in the following theorem. Theorem 5.1. Let w ∈ Z + and L be a memorization algorithm such that L(D tr ) has width not more than w for all D tr . Then, there exist an integer n > w, c ∈ R + , and a distribution D ∈ D(n, c) such that, for any D tr ∼ D N , it holds A D (L(D tr )) ≤ 0.51.Proof Idea. As shown in [40, 48] , networks with small width are not dense in the space of measurable functions, but this is not enough to estimate the upper bound of the generalization. In order to further measure the upper bound of generalization, we define a special class of distributions. Then, we calculate the upper bound of the generalization of networks with fixed width on this class of distribution. Based on the calculation results, it is possible to find a specific distribution within this class of distributions, such that the fixed-width network exhibits a poor generalization of this distribution. The proof is given in Appendix D.It is well known that width of the network is important for the network to be robust [2, 17, 18, 37, 67] . Theorem 5.1 further shows that large width is a necessary condition for generalizabity.Note that Theorem 5.1 is for a specific data distribution. We will show that for most distributions, providing enough data does not necessarily mean that the memorization algorithm has generalization ability. This highlights the importance of constructing appropriate memorization algorithms to ensure generalization. We need to introduce another parameter for data distribution. Loosely speaking, the density of a distribution is the upper bound of the density function. Proof Idea. We refer to the classical memorization construction idea [55] . The main body includes three parts. Firstly, compress the data in D tr into one dimension. Secondly, map the compressed data to some specific values. Finally, use such a value to get the label of input. Moreover, we will pay more attention to points outside the dataset. We use some skills to control the classification results of points that do not appear in the dataset D tr , so that the memorization network will give the wrong label to the points that are not in D tr as much as possible to reduce its accuracy. The general approach is the following: (1) Find a set in which each point is not presented in D tr and has the same label under distribution D. Without loss of generality, let they have label 1.(2) In the second step mentioned in the previous step, ensure that the mapped results of the points in the set mentioned in (1) are similar to the samples with label -1. This will cause the third step to output the label -1, leading to an erroneous classification result for the points in the set. The proof is given in Appendix E.Remark 5.4. Theorem 5.1 shows that the width of the generazable memorization network needs to increase with the increase of the data dimension. Theorem 5.3 shows that when para(F) = O( √ N ), the memorization network may have poor generalizability for most distributions. The above two theorems indicate that no matter how large the dataset is, there always exist memorization networks with poor generalization. In terms of sample complexity, it means that for the hypotheses of neural networks with fixed width or with optimal number of parameters, the sample complexity is infinite, contrary to the uniform generalization bound for feedforward neural networks [63, Lemma D.16 ].Remark 5.5. It is worth mentioning that the two theorems in this section cannot be obtained from the lower bound of the generalization gap [44] , and more details are shown in Appendix E. 
sample complexity for memorization algorithm: 
 As said in the preceding section, generalization of memorization inevitably requires certain conditions. In this section, we give the necessary and sufficient condition for generalization for the memorization algorithm in Section 4 in terms of sample complexity.We first give a lower bound for the sample complexity for general memorization algorithms and then an upper bound for memorization algorithms which output networks with an optimal number of parameters. The lower and upper bounds are approximately the same, thus giving the exact sample complexity in this case.Roughly speaking, the sample complexity of a learning algorithm is the number of samples required to achieve generalizability [44] . The following theorem gives a lower bound for the sample complexity of memorization algorithms based on N D , which has been defined in Theorem 4.3. Theorem 6.1. There exists no memorization algorithm L which satisfies that for any n∈ Z + , c ∈ R + , ϵ, δ ∈ (0, 1), if D ∈ D(n, c) and N ≥ v N 2 D ln 2 (N D ) (1 -2ϵ -δ), it holds P Dtr∼D N (A(L(D tr )) ≥ 1 -ϵ) ≥ 1 -δwhere v is an absolute constant which does not depend on N, n, c, ϵ, δ.Proof Idea. The mainly idea is that: for a dataset D tr ⊂ [0, 1] n × {-1, 1} with |D tr | = N , we can find some distributions D 1 , D 2 , . . . , such that if D tr,i ∼ (D i ) N , then with a positive probability, it hold D tr,i = D tr . In addition, each distribution has a certain degree of difference from the others. It is easy to see that L(D tr ) is a fixed network for a given L, so L(D tr ) cannot fit all D i well because D i are different to some degree. So, if a memorization algorithm L satisfies the condition in the theorem, we try to construct some distributions {D i } n i=1 , and use the above idea to prove that L cannot fit one of the distributions in {D i } n i=1 , and obtain contradictions. The proof of the theorem is given in Appendix F. Remark 6.2. In general, the sample complexity depends on the data distribution, hypothesis space, learning algorithms, and ϵ, δ. Since N D is related to n and c, the lower bound in Theorem 6.1 also depends on n and c. Here, the hypothesis space is the memorization networks, which is implicitly reflected in N D . Remark 6.3. Roughly strictly, if we consider interpolation learning, that is, training network under the constraint of memorizing the dataset, then Theorem 6.1 also provides a lower bound for the sample complexity.This theorem shows that if we want memorization algorithms to have guaranteed generalization, then about O(N 2 D ) samples are required. As a consequence, we show that, for some data distribution, it need an exponential number of samples to achieve generalization. The proof is also in Appendix F. Corollary 6.4. For any memorization algorithm L and any ϵ, δ ∈ (0, 1), there exist n ∈ Z + , c > 0 and a distribution D ∈ D(n, c) such that in order for L to have generalizability, that is,P Dtr∼D N (A(L(D tr )) ≥ 1 -ϵ) ≥ 1 -δ, N must be more than v(2 2[ n ⌈c 2 ⌉ ] c 4 (1 -2ϵ -δ)/n 2 ), where v is an absolute constant not depending on N, n, c, ϵ, δ.In Theorem 6.1, it is shown that Ω(N 2 D ) samples are necessary for generalizability of memorization. The following theorem shows that there exists a memorization algorithm that can reach generalization with O(N 2 D ) samples. Theorem 6.5. For all memorization algorithms L satisfies that L(D tr ) has at most N D parameters, with probability 1 for D tr ∼ D N , we have(1) For any c ∈ R, ϵ, δ ∈ (0, 1), n ∈ Z + , if D ∈ D(n, c) and N ≥ vN 2 D ln(N D /(ϵ 2 δ)) ϵ 2, thenP Dtr∼D N (A(L(D tr )) ≥ 1 -ϵ) ≥ 1 -δ,where v is an absolute constant which does not depend on N, n, c, ϵ, δ.(2) If P̸ = NP, then all such algorithms are not efficient.Proof Idea. For the proof of (1), we need to use the N D to calculate the VC-dimension [6] , and take such a dimension in the generalization bound theorem [44] to obtain the result. For the proof of (2), we show that, if such algorithm is efficient, then we can solve the following reversible 6-SAT [43] problem, which is defined below and is an NPC problem. The proof of the theorem is given in Appendix G. Definition 6.6. Let φ be a Boolean formula and φ the formula obtained from φ by negating each variable. The Boolean formula φ is called reversible if either both φ and φ are satisfiable or both are not satisfiable. The reversible satisfiability problem is to recognize the satisfiability of reversible formulae in conjunctive normal form (CNF). By the reversible 6-SAT, we mean the reversible satisfiability problem for CNF formulae with six variables per clause. In [43] , it is shown that the reversible 6-SAT is NPC.Combining Theorems 6.1 and 6.5, we see that N = O(N 2 D ) is the necessary and sufficient condition for the memorization algorithm to generalize, and hence O(N 2 D ) is the exact sample complexity for memorization algorithms with N D parameters over the distribution D(n, c).Unfortunately, by (2) of Theorem 6.5, this memorization algorithm is not efficient when the memorization has no more than N D parameters. Furthermore, we conjecture that there exist no efficient memorization algorithms that can use O(N 2 D ) samples to reach generalization in the general case, as shown in the following conjecture. Conjecture 6.7. If P̸ = NP, there exist no efficient memorization algorithms that can reach generalization with O(N 2 D ) samples for all D ∈ D(n, c). Remark 6.8. This result also provides certain theoretical explanation for the over-parameterization mystery [45, 7, 4] : for memorization algorithms with N D parameters, the exact sample complexity O(N 2 D ) is greater than the number of parameters. Thus, the networks is under-parameterized and for such a network, even if it is generalizable, it cannot be computed efficiently. 
efficient memorization algorithm with guaranteed generalization: 
 In the preceding section, we show that there exist memorization algorithms that are generalizable when N = O(N 2 D ), but such an algorithm is not efficient. In this section, we give an efficient memorization algorithm with guaranteed generalization.First, we define the efficient memorization sample complexity of D. Definition 7.1.For (x, y) ∼ D, let L (x,y) = min (z,-y)∼D ||x -z|| 2 and B((x, y)) = B 2 (x, L (x,y) /3.1) = {z ∈ R n : ∥z -x∥ 2 ≤ L (x,y) /3.1}. The nearby set S of D is a subset of sample (x, y) which is in distribution D and satisfies: (1) for any (x, y) ∼ D, x ∈ ∪ (z,w)∈S B((z, w)); (2) |S| is minimum.Evidently, for any D ∈ D(n, c), its nearby set is finite, as shown by Proposition 7.7. S D = |S| is called the efficient memorization sample complexity of D, the meaning of which is given in Theorem 7.3. Remark 7.2. In the above definition, we use L (x,y) /3.1 to be the radius of B((x, y)). In fact, when 3.1 is replaced by any real number greater than 3, the following theorem is still valid. Theorem 7.3. There exists an efficient memorization algorithm L such that for any c ∈ R, ϵ, δ ∈ (0, 1), n ∈ Z + , and D ∈ D(n, c), if N ≥ S D ln(S D /δ) ϵ , thenP Dtr∼D N (A(L(D tr )) ≥ 1 -ϵ) ≥ 1 -δ. Moreover, for any D tr ∼ D N , L(D tr ) has at most O(N 2 n) parameters.Proof Idea. For a given dataset D tr ⊂ [0, 1] n × {-1, 1}, we use the following two steps to construct a memorization network.Step 1. Find suitable convex sets {C i } in [0, 1] n such that each sample in D tr is in at least one of these convex sets. Furthermore, if x, z ∈ C i and (x, y x ), (z, y z ) ∈ D tr , then y x = y z , and define y(C i ) = y x .Step 2. Construct a network F such that for any x ∈ C i , Sgn(F(x)) = y(C i ). This network must be a memorization of D tr , because each sample in D tr is in at least one of {C i }. Hence, if x ∈ C i and (x, y x ) ∈ D tr , then Sgn(F(x)) = y(C i ) = y x . The proof of the theorem is given in Appendix H. Remark 7.4. Theorem 7.3 shows that there exists an efficient and generalizable memorization algorithm when N = O(S D ). Thus, S D is an intrinsic complexity measure of D on whether it is easy to learn and generalize. By Theorem 6.1, S D ≥ N 2 D for some D, but for some "nice" D, S D could be small. It is an interesting problem to estimate S D .Remark 7.5. Theorem 7.3 uses O(N 2 n) parameters, highlight the importance of overparameterization [45, 7, 4] . Interestingly, Remark 6.8 shows that if the network has O( √ N ) parameters, even if it is generalizable, it cannot be computed efficiently.The experimental results of the memorization algorithm mentioned in Theorem 7.3 are given in Appendix I. Unfortunately, for commonly used datasets such as CIFAR-10, this algorithm cannot surpass the network obtained by training with SGD, in terms of test accuracy. Thus, the main purpose of the algorithm is theoretical, that is, it provides a polynomial-time memorization algorithm that can achieve generalization when the training dataset contains O(S D ) samples. In comparison of theoretical works, training networks is NP-hard for small networks [32, 51, 39, 15, 3, 42, 16, 23, 21] and the guarantee of generalization needs strong assumptions on the loss function [46, 27, 34, 61, 60, 58] .Finally, we give an estimate for S D . From Corollary 6.4 and Theorem 7.3, we obtain a lower bound for S D .Corollary 7.6. There exists a distributionD ∈ D(n, c) such that S D ln(S D /δ) ≥ Ω( c 4 n 2 2 2[ n ⌈c 2 ⌉ ]).We will give an upper bound for S D in the following proposition, and the proof is given in Appendix H.1. From the proposition, it is clear that S D is finite.  
conclusion: 
 Memorization originally focuses on theoretical study of the expressive power of neural networks.Recently, memorization is believed to be a key reason why over-parameterized deep learning models have excellent generalizability and thus the more practical interpolation learning approach has been extensively studied. But the generalizability theory of memorization algorithms is not yet given, and this paper fills this theoretical gap in several aspects.We first show how to construct memorization networks for dataset sampled i.i.d from a data distribution, which have the optimal number of parameters, and then show that some commonly used memorization networks do not have generalizability even if the dataset is drawn i.i.d. from a data distribution and contains a sufficiently large number of samples. Furthermore, we establish the sample complexity of memorization algorithm in several situations, including a lower bound for the memorization sample complexity and an upper bound for the efficient memorization sample complexity.Limitation and future work Two numerical complexities N D and S D for a data distribution D are introduced in this paper, which are used to describe the size of the memorization networks and the efficient memorization sample complexity for any i.i.d. dataset of D. N D is also a lower bound for the sample complexity of memorization algorithms. However, we do not know how to compute N D and S D , which is an interesting future work. Conjecture 6.7 tries to give a lower bound for the efficient memorization sample complexity. More generally, can we write N D and S D as functions of the probability density function p(x, y) of D? Corollary 6.4 indicates that even for the "nice" data distributions D(n, c), to achieve generalization for some data distribution requires an exponential number of parameters. This indicates that there exists "data curse of dimensionality", that is, to achieve generalizability for certain data distribution, neural networks with exponential number of parameters are needed. Considering the practical success of deep learning and the double descent phenomenon [45] , the data distributions used in practice should have better properties than D(n, c), and finding data distributions with polynomial size efficient memorization sample complexity E D is an important problem.Finally, finding a memorization algorithm that can achieve SOTA results in solving practical image classification problems is also a challenge problem. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes] Justification: We use open-source dataset and models in our paper, and have cited the original paper of these dataset and models as presented in Appendix I.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 
 
 Appendix: Using the following steps, we construct a distribution D in [0, 1] × {-1, 1}. We use (x, y) ∼ D to mean that(1) Randomly select a number in {-1, 1} as the label y.(2) If we get 1 as the label, then randomly select an irrational number in [0, 1] as samples x; if we get -1 as the label, then randomly select a rational number in [0, 1] as samples x.Then Proposition 3.3 follows from the following lemma.Lemma A.1. For any neural network F, we have A D (F) ≤ 0.5.Proof. Let F be a network. Firstly, we show that F can be written asEQUATIONwhere L i are linear functions, I(x) = 1 if x is true or I(x) = 0. In addition, A i is an interval andA j ∩ A i = ∅ when j ̸ = i, and L i (x)I(x ∈ A i ) is a non-negative or non-positive function for any i ∈ [M ].It is obvious that the network is a locally linear function with a finite number of linear regions, so we can writeEQUATIONwhereL ′ i are linear functions, A ′ i is an interval and A ′ j ∩ A ′ i = ∅ when j ̸ = i. Consider that L ′ i (x)I(x ∈ A ′ i ) = L ′ i (x)I(x ∈ A ′ i , L ′ i (x) > 0) + L ′ i (x)I(x ∈ A ′ i , L ′ i (x) < 0), and L ′ i (x)I(x ∈ A ′ i , L ′ i (x) > 0) is a non-negative function, {x ∈ A ′ i , L ′ i (x) > 0} is an interval which is disjoint with {x ∈ A ′ i , L ′ i (x) < 0}. Similarly as L ′ i (x)I(x ∈ A ′ i , L ′ i (x) < 0), so we use L ′ i (x)I(x ∈ A ′ i ) in (2) instead of L ′ i (x)I(x ∈ A ′ i , L ′ i (x) > 0) + L ′ i (x)I(x ∈ A ′ i , L ′ i (x) < 0). Then we get the equation (1) .By equation (2), we have thatEQUATIONThe second equation usesA i ∩ A j = ∅.For convenience, we use x ∈ R r to mean that x is an irrational number and x / ∈ R r to mean that x is a rational number. Then, if L i (x)I(x ∈ A i ) is a non-negative function, then we have By (2) in the definition of D, we have P (x,y)∼D (xP (x,y)∼D (Sgn(L i (x)I(x ∈ A i )) = y|x ∈ A i ) ≤ P (x,y)∼D (x ∈ R r |x ∈ A i ). Moreover, we have that P (x,y)∼D (x ∈ R r |x ∈ A i ) = P (x,∈ A i |x ∈ R r ) = P (x,y)∼D (x ∈ A i |x / ∈ R r ). Substituting this in equation (3), we have that P (x,y)∼D (Sgn(L i (x)I(x ∈ A i )) = y|x ∈ A i ) ≤ P (x,y)∼D (x ∈ R r |x ∈ A i ) = P (x,y)∼D (x∈Ai|x∈Rr) P (x,y)∼D (x∈Ai|x∈Rr)+P (x,y)∼D (x∈Ai|x / ∈Rr) = 0.5. Proof is similar when L i (x)I(x ∈ A i ) is a non-positive function.Using this in equation ( 2), we have thatP (x,y)∼D (Sgn(F(x)) = y) = M i=1 P (x,y)∼D (Sgn(L i (x)I(x ∈ A i )) = y|x ∈ A i )P (x,y)∼D (x ∈ A i ) ≤ M i=1 0.5P (x,y)∼D (x ∈ A i ) ≤ 0.5.The lemma is proved.For the proof of this theorem, we mainly follow the constructive approach of the memorization network in [55] . Our proof is divided into four parts.The general method of constructing memorization networks will compress the data into a low dimensional space at first, and we follow this approach. We are trying to compress the data into a 1-dimensional space, and we require the compressed data to meet some conditions, as shown in the following lemma.Lemma B.1. Let D be a distribution in [0, 1] n × {-1, 1} with separation bound c and D tr ∼ D N . Then, there exist w ∈ R n and b ∈ R such that (1): O(nN 2 /c) ≥ wx + b ≥ 1 for all x ∈ [0, 1] n ;(2): |wx -wz| ≥ 4 for all (x, 1), (z, -1) ∈ D tr .To prove this lemma, we need the following lemma. Lemma B.2. For any v ∈ R n and T ≥ 1, let u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 . Then we haveP (|⟨u, v⟩| < ||v||2 T 8 nπ ) < 2 T .This is Lemma 13 in [49] . Now, we prove the lemma B.1.Proof. Let c 0 = min (x,-1),(z,1)∈Dtr ||x -z|| 2 . Then, we prove the following result:Result R1: Let u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 , then there areEQUATIONnπ , ∀(x, -1), (z, 1) ∈ D tr ) > 0.5.By lemma B.2, and take T = 4N 2 , for any x, z which satisfies (x, -1), (z, 1) ∈ D tr , we have that: let u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 , then there areP (|⟨u, (x -z)⟩| < c0 4N 2 8 nπ ) < 2 4N 2 , using ||x -z|| 2 ≥ c 0 here. So, it holds P (|⟨u, (x -z)⟩| ≥ c0 4N 2 8 nπ , ∀(x, -1), (z, 1) ∈ D tr ) ≥ 1 -(x,-1),(z,1)∈Dtr P (|⟨u, (x -z)⟩| < c0 4N 2 8 nπ ) > 1 -2N 2 4N 2 . = 0.5We proved Result R1.In practice, to find such a vector, we can randomly select a vector u in hypersphere S n-1 , and verify that if it satisfies |⟨u, (x -z)⟩| ≥ c0 In each selection, with probability 0.5, we can get a vector we need, so with ln 1/ϵ times the selections, we can get a vector we need with probability 1 -ϵ.By the above result, we have that: there exists a u ∈ R n such that ||u|| 2 = 1 and |⟨u, (x -z)⟩| ≥ On the other hand, |wx| ≤ ||w|| 2 √ n ≤ O( nN 2 c0 ), so wx+b ≤ |wx|+b ≤ O(nN 2 /c 0 ) ≤ O(nN 2 /c). (2): We have |w(x -z)| ≥ 4 for all (x, 1), (z, -1) ∈ D tr . It is easy to see that |w(x -z)| ≥ | 16 √ nN 2 c0 u(x -z)| = 16 √ nN 2 c0 |u(x -z)|. Because |u(x -z)| ≥ c0 4 √ nN 2 , so |w(x -z)| = 16 √ nN 2 c0 |u(x -z)| ≥ 16 √ nN 2 c0 c0 4 √ nN 2 =The purpose of this part is to map the compressed data into appropriate values.Let w ∈ R n and b ∈ R be given and D tr = {(x i , y i )} N i=1 . Without losing generality, we assume that 0 < wx i < wx i+1 .In this section, we show that, after compressing the data into 1-dimension, we can use a networkF to map wx i + b to v [ i [ √ N ]] , where{v j } [ N [ √ N ] ] j=0 ∈ R + are given values. This network has O( √ N )parameters and width 4, as shown in the following lemma.Lemma B.3. Let {x i } N i=1 ⊂ R + , {v j } [ N [ √ N ] ] j=0 ⊂ R + . Assume that x i < x i+1 . Then a network F with width 4 and depth O( √ N ) (at most O( √ N ) parameters) can be obtained such that F(x i ) = v [ i √ N ] for all i ∈ [N ].Proof. Let F i (x) be the i-th hidden layer of network F, (F i ) j be the j-th nodes of i-th hidden layer of network F.Let q i = x i+1 -x i and t(i) = argmax j∈[N ] {[j/ √ N ] = i}.Consider the following network F:The 2i + 1 hidden layer has width 4, and each node is:(F 2i+1 ) 1 (x) = Relu((F 2i ) 2 (x) -(x t(i)+1 ) + 2q t(i) /3); (F 2i+1 ) 2 (x) = Relu((F 2i ) 2 (x) -(x t(i)+1 ) + q t(i) /3); (F 2i+1 ) 3 (x) = Relu((F 2i ) 1 (x)); (F 2i+1 ) 4 (x) = Relu((F 2i ) 2 (x)).For the case i = 0, let(F 0 ) 2 (x) = x and (F 1 ) 3 (x) = v 0 .The (2i + 2)-th hidden layer is:(F 2i+2 ) 1 (x) = Relu((F 2i+1 ) 3 (x) + v i+1 -v i q t(i) /3 ((F 2i+1 ) 1 (x) -(F 2i+1 ) 2 (x))); (F 2i+2 ) 2 (x) = Relu((F 2i+1 ) 4 (x)).The output isF(x) = (F 2[N/ √ N ] ) 1 (x).This network has width 4 and O( √ N ) hidden layers. We can verify that such a network is what we want as follows.Firstly, it is easy to see that(F 2i+2 ) 2 (x) = Relu((F 2i+1 ) 4 (x)) = Relu((F 2i ) 2 (x)) = Relu((F 2i-1 ) 4 (x)) = • • • = Relu((F 1 ) 4 (x)) = Relu(x) = x.Then, for vi+1-vi q t(i) /3 ((F 2i+1 ) 1 (x)-(F 2i+1 ) 2 (x)) = vi-vi-1 q t(i) /3 (Relu(x-x t(i)+1 +2q t(i) /3)-Relu(xx t(i)+1 + q t(i) /3), easy to verify that, when x ≤ x t(i) , it is 0; whenx ≥ x t(i+1) , it is v i+1 -v i .By the above two results, we have that(F 2i+2 ) 1 (x) = Relu((F 2i+1 ) 3 (x) + vi-vi-1 q t(i) /3 ((F 2i+1 ) 1 (x) - (F 2i+1 ) 2 (x))) = Relu((F 2i ) 1 (x)) when x ≤ x t(i) ; and (F 2i+2 ) 1 (x) = Relu((F 2i+1 ) 3 (x) + vi-vi-1 q t(i) /3 ((F 2i+1 ) 1 (x) -(F 2i+1 ) 2 (x))) = Relu((F 2i ) 1 (x) + v i+1 -v i ) when x ≥ x t(i)+1 .So, we have that, if t(i-1)+1 ≤ j ≤ t(i), there are(F 2 ) 1 (x j ) = v 0 , (F 4 ) 1 (x j ) = v 1 -v 0 +v 0 = v 1 , (F 6 ) 1 (x j ) = v 2 -v 1 + v 1 = v 2 , . . . , (F 2i ) 1 (x j ) = v i -v i-1 + v i-1 = v i ; and F(x j ) = (F 2[N/ √ N ] ) 1 (x j ) = (F 2[N/ √ N ]-2 ) 1 (x j ) = • • • = (F 2i ) 1 (x j ) = v i .So, by the definition of t(i), we have thatF(x j ) = v [ j √ N] , such F is what we what and the lemma is proved.The purpose of this part is to use the values to which the compressed data are mapped, mentioned in the above section, to determine the labels of the data.Assuming x i is compressed to c i where c i ≥ 1 is given in section B.1. Value v i in section B.2 is designed as: v i = [c i[ √ N ]+1 ] . . . [c (i+1)[ √ N ] ],where we treat [c j ] as a w digit number for all j (w is a given number). If there exist not enough digits for some c j , we fill in 0 before it, and we use ab to denote the integer by putting a and b together.First, prove a lemma. Lemma B.4. For a given N , there exists a network f : R → R 2 with width 4 and at most O(w) parameters such that, for any w digit number a i > 0, we have f (a 1 a 2 . . . a N ) = (a 1 , a 2 . . . a N ).Proof. Firstly, we show that, for any a > b > 0, there exists a network F a,b (x) : R + → R + with depth 2 and width 3, such that F a,b (x) = x when x ∈ [0, a], andF a,b (x) = x -a when x ∈ [a + b, 2a].We just need to take F a,b (x) = Relu(x) -a/bRelu(x -a) + a/bRelu(x -(a + b)).l It is easy to verify that this is what we want. Now, let q ∈ N + satisfy 2 q ≤ 10 w+1 -1 an 2 q+1 > 10 w+1 and p < 1 10 wN . We consider the following network:F = F 2 0 ,p • F 2 1 ,p • • • • F 2 q-1 ,p • F 2 q ,p ,and show that, F (a 1 a 2 . . . a N /10 w(N -1) ) = a 2 . . . a N /10 w(N -1) .Firstly, we have F 2 q ,p (a 1 a 2 . . . a N /10 w(N -1) ) = a 1 (q)a 2 . . . a N /10 w(N -1) , where a 1 (q) = a 1 if a 1 a 2 . . . a N /10 w(N -1) ≤ 2 q and a 1 (q) = a 1 -2 q if a 1 a 2 . . . a N /10 w(N -1) > 2 q + p. Just by the definition of q, we know that there must be a 1 a 2 . . . a N /10 w(N -1) ≤ 2 q+1 . Further by the definition of p, one of the following two inequalities is true:a 1 a 2 . . . a N /10 w(N -1) < 2 q or a 1 a 2 . . . a N /10 w(N -1) > 2 q + p.So using the definition of F 2 q ,p , we get the desired result.Similarly as before, for k = q -1, q -2, . . . , 0, we haveF 2 k ,p (a 1 (k + 1)a 2 . . . a N /10 w(N -1) ) = a 1 (k)a 2 . . . a N /10 w(N -1) , where a 1 (k) = a 1 (k + 1) if a 1 (k + 1)a 2 . . . a N /10 w(N -1) ≤ 2 k and a 1 (k) = a 1 (k + 1) -2 k if a 1 (k + 1)a 2 . . . a N /10 w(N -1) > 2 k + p.Then we have the following result: a 1 (k) < 2 k for any k = 0, 1, . . . , q. By the definition, it is easy to see that a 1 < 2 q+1 . If a 1 < 2 q , then a 1 (q) ≤ a 1 < 2 q ; if a 1 ≥ 2 q , then a 1 a 2 . . . a N /10 w(N -1) > 2 q + p, so a 1 (q) = a 1 -2 q < 2 q+1 -2 q = 2 q . Thus a 1 (q) < 2 q . When a 1 (t) < 2 t for a t ∈ [q], similar as before, we have a 1 (t -1) < 2 t-1 . And t = q is proved, so we get the desired result.It is easy to see that, a 1 (k) are non negative integers, so there must be F (a 1 a 2 . . . a N /10 w(N -1) ) = a 1 (0)a 2 . . . a N /10 w(N -1) = a 2 . . . a N /10 w(N -1) , by a 1 (0) < 2 0 = 1, which implies a 1 (0) = 0.Now we construct a network F b as follows:F b (x) = F b1 • F b1 (x) such that:F b1 (x) : R → R 2 and F b1 (x) = (F (x/10 w(N -1) ), x) where x is defined as before.F b2 (x) : R 2 → R 2 and F b2 ((x 1 , x 2 )) = (x 2 /10 w(N -1) -x 1 , x 1 * 10 w(N -1) ). By the preceding lemma, we have the following lemma.Lemma B.5. There is a network R 2 → R with at most O(N w) parameters and width 6, and for any {a i } N i=1 where a j is a w digit number anda j ≥ 1, which satisfies f (x, a 1 a 2 . . . a N ) > 0.1 if |x -a k | < 1 for some k ∈ [N ], and f (x, a 1 a 2 . . . a N ) = 0 if |x -a k | ≥ 1.1 for all k ∈ [N ].Proof. The proof idea is as follows: First, we use x and a 1 a 2 . . step 2: Now we build the f mentioned in the lemma.Let f = g • f N • f N -1 • • • • f 1 .For each i ∈ [N ], we will let the input of f i which is also the output of f i-1 when i > 1 be the form (x, a i a i+1 . . . a N , q i ), where q 1 = 0. The detail is as follows:For i ∈ [N ], in f i , construct f s (x, a i a i+1 . . . a N )at first, and then let q i+1 = q i + (f s ) 1 (x, a i a i+1 . . . a N ), to keep q i in each layer, where we need one more width than f s . Then, output (x, a i+1 a i+2 . . . a N , q i+1 ), which is also the input of (i + 1)-th part.The output of f is q N +1 , that is, g(x, 0, q N +1 ) = q N +1 . Now, we show that, f is what we want.(1): f has at most O(N w) parameters and width 6, which is obvious, because each part f i , f i has O(w) parameters by lemma B.4, and f has at most N parts, so we get the result.(EQUATIONThis is because when |x -a k | < 1, the k-th part will make q k+1 = q k + f s (x, a k a k+1 . . . a N ) > 0.1, because (f s ) 1 (x, a k a k+1 . . . a N ) > 0.1 as said in step 1. Since q j+1 = q j + (f s ) 1 ≥ q j , we have f (x, a 1 a 2 . . . a N ) = q N +1 ≥ q k+1 > 0.1.(3): f (x, a 1 a 2 . . . a N ) = 0 if |x -a k | ≥ 1.1 for all k.This is because when |x-a k | ≥ 1.1, the k-th part will make q k+1 = q k +f s (x, a k a k+1 . . . a N ) = q k , because f s (x, a k a k+1 . . . a N ) = 0 as said in step 1. Since f s (x, a k a k+1 . . . a N ) = 0 for all k, we have 4 The proof of Theorem 4.1f (x, a 1 a 2 . . . a N ) = q N +1 = q N + f s (x, a N ) = q N = • • • = q 0 = 0. B.Now, we will prove Theorem 4.1. As we mentioned before, three steps are required: data compression, data projection, and label determination. The proof is as follows.Proof. Assume that D tr = {x i } N i=1 , without loss of generality, let x i ̸ = x j . Now, we show that there is a memorization network F of D tr with O( √ N ) parameters.Part One, data compression.The part is to compress the data in D tr into R. Let w, b satisfy (1) and ( 2) in lemma B.1. Then, the first part of F is f 1 (x) = Relu(wx + b).Part two, data projection.Let c i = f 1 (x i ), without loss of generality, we assume c i ≤ c i+1 and y 1 = 1. We define c ′ i as:c ′ i = c i if x i has label 1; otherwise c ′ i = c 1 . Let t(i) = argmax j∈[N ] {[j/ √ N ] = i} and v k = [c ′ t(k-1)+1 ][c ′ t(k-1)+2 ] . . . [c ′ t(k) ]. In this part, the second part of F(x), named as f 2 (x) : R → R 2 , need to satisfy f 2 (c i ) = (v [ i √ N 0 ] , c i ) for any i ∈ [N ].√ N ) parameters and width 4 is enough to mapx i to v [ i √ N] and for keeping the input, and one node is needed at each layer. So f 2 just need O( √ N ) parameters and width 5.Part Three, Label determination.In this part, we will use the v k mentioned in part two to output the label of input. The third part, nameed as f 3 (v, c), should satisfy that:For f 3 (v k , c), where v k = [c ′ t(k-1)+1 ][c ′ t(k-1)+2 ] . . . [c ′ t(k) ] is defined above, if |c -c ′ q | < 1 for some q ∈ [t(k -1) + 1, t(k)], then f 3 (v k , c) > 0.1; and f 3 (v k , c) = 0 if |c -c ′ q | ≥ 1.1 for all q ∈ [t(k -1) + 1, t(k)].Because the number of digits for c i is O(ln(nN/c)) by ( 1 Construction of F and verify it:Let F(x) = f 3 (f 2 (f 1 (x))) -0.05. We show that F is what we want.(1): By parts one, two, three, it is easy to see that F has at most O( √ N ln(N n/c)) parameters and width 6.(2): F(x) is a memorization of D tr . For any (x i , y i ) ∈ D tr , consider two sub-cases:(1.1: if y i = 1): Using the symbols in Part Two, f 2 (f 1 (x i )) will output (v [ i √ N ] , f 1 (x i )). Since c ′ i = c i because y i = 1, by part three, we have f 3 (f 2 (f 1 (x))) -0.05 ≥ 0.1 -0.05 > 0. (1.2 if y i = -1): By (2) in lemma B.1, for ∀(z, 1) ∈ D tr , we know that |f 1 (x i ) -[f 1 (x 1 )]| ≥ |f 1 (x i ) -f 1 (x 1 )| -|f 1 (x 1 ) -[f 1 (x 1 )]| ≥ 4 -1 = 3. So, by part three, we have f 3 (f 2 (f 1 (x i ))) = 0 -0.05 < 0.The Running Time: In Part One, it takes poly(B(D tr ), ln ϵ) times to find such w and b with probability 1 -ϵ, as said in lemma B.1. In other parts, the parameters are calculated deterministically. We proved the theorem.Proof. It suffices to show that there exists a memorization algorithm L, such that if D ∈ D(n, c) and D tr ∼ D N , then the network L(D tr ) has a constant number of parameters (independent of N ). The construction has four steps.Step One: Calculate the min (x,yx),(z,yz)∈Ds ||x -z|| 2 , name it as c 0 .Step Two: There is a D tr ⊂ D tr , such that: (c1): For any (x, y x ), (z, y z ) ∈ D s , it holds ||x -z|| 2 > c 0 /3; (c2): For any (x, y x ) ∈ D tr , it holds ||x -z|| 2 ≤ c 0 /3 for some (z, y z ) ∈ D s .It is obvious that such D s exists.Step Three: We prove that |D s | ≤ (1+2c0/3) n Cn(c0/3) n , where C n is the volume of unit ball in R n . Let Q = (1+2c/3) n Cn(c/3) n , consider that c 0 ≥ c, so there are|D s | ≤ Q. Let B 2 (x, r) = {z : ||z -x|| 2 ≤ r}, and V (A) the volume of A. Due to D s ⊂ D tr ⊂ [0, 1] n × {-1, 1}, so ∪ (x,y)∈Ds B 2 (x, c 0 /3) ∈ [-c 0 /3, 1 + c 0 /3] n . By condition (c1), we have B 2 (x, c 0 /3) ∩ B 2 (z, c 0 /3) = ∅ for any (x, y x ), (z, y z ) ∈ D s , so we have (x,y)∈Ds V (B 2 (x, c 0 /3)) ≤ (1 + 2c 0 /3) n , which means |D s | ≤ (1+2c0/3) n Cn(c0/3) n < Q.Step Four: There is a robust memorization network [62] with at most O(Qn) parameters for D s with robust radius c 0 /3, and this memorization network is a memorization of D tr .By condition (c1), there is a robust memorization network F rm with O(|D s |n) parameters for D s with radius c 0 /3 [62] . By step three, we have |D s | ≤ Q, so that such a network has at most O(Qn) parameters.By condition (c2), for any (x, y x ) ∈ D tr , there is a (z, y z ) ∈ D s satisfying ||x -z|| 2 ≤ c 0 /3. Firstly, there must be y x = y z , because the distribution D has separation bound c 0 , and if y x ̸ = y z then ||x -z|| 2 ≥ c 0 > c 0 /3. Then, since robust memorization F rm has robust radius c 0 /3, we have Sgn(F rm (x)) = Sgn(F rm (z)) = y z = y x , so F rm is a memorization network of D tr . The theorem is proved.In this section, we will prove that networks with small width cannot have a good generalization for some distributions. For a given width w, we will construct a distribution on which any network with width w will have poor generalization. The proof consists of the following parts.In this section, we demonstrate that a network with a small width may have some unfavorable properties. We have the following simple fact. Lemma D.1. Let the first transition weight matrix of network F be W . Then if W x = W z, we haveF(x) = F(z).If W is not full-rank, then there exist x and z satisfying W x = W z. Moreover, if x and z have different labels, according to lemma D.1, we have F(x) = F(z), so there must be an incorrect result given between F(x) and F(z).According to the theorem of matrices decomposition, we also have the following fact. Lemma D.2. Let the first transition weight matrix of network F : R n → R be W . If W has width w < n, then exists a W 1 ∈ R w×n , whose rows are orthogonal and unit such thatW 1 x = W 1 z implies F(x) = F(z).Proof. Using matrix decomposition theory, we can write W = N W 1 , where N ∈ R w×w and W 1 ∈ R w×n and the rows of W 1 are orthogonal to each other and unit.Next, we only need to consider W 1 as the first transition matrix of the network F and use lemma D.1.At this point, we can try to construct a distribution where any network with small width will have poor generalization.In this section, we introduce some lemmas which are used in the proof in section D.3. Lemma D.3. Let B(r) be the ball with radius r in R n . For any given δ > 0, let ϵ = 2δ/n. Then we haveV (B( √ 1-ϵr)) V (B(r)) > 1 -δ. Proof. we have V (B( √ 1-ϵr)) V (B(r)) = (1 -ϵ) n/2 ≥ 1 -nϵ/2 = 1 -δ.For w ∈ R a,b and q ∈ R a , let q • w = a i=1 q i w i , where q i is the i-th weight of q, w i is the i-th row of w i . Then we have Lemma D.4. Let W ∈ R w×n , and its rows are unit and orthogonal.(1): For anyq 1 ̸ = q 2 ∈ R w , we have {x ∈ R n : W x = W (q 1 • W )} ∩ {x ∈ R n : W x = W (q 2 • W )} = ∅.(EQUATION(EQUATION, where C i is the volume of the unit ball in R i .Proof. First, we define an orthogonal coordinate system {W i } n i=1 in R n . Let W i be the i-th row of W when i ≤ w. When i > w, let W i be a unit vector orthogonal with all W j where j < i.Then for all x ∈ R n , we say x i is the i-th weight of x under such coordinate system. Then, W x = W z if and onlyx i = z i for i ∈ [w].Now, we can prove the lemma.(1): The first weight w of q 1 • W under orthogonal coordinate system{W i } n i=1 is q 1 , so if x ∈ {x ∈ R n : W x = W (q 1 • W )}, we have x i = (q 1 ) i for i ∈ [w].The first w weight of q 2 • W under orthogonal coordinate system {W i } n i=1 is q 2 , so if x ∈ {x ∈ R n : W x = W (q 2 • W )}, we have x i = (q 2 ) i for i ∈ [w]. Because q 1 ̸ = q 2 ∈ R w , we get the result.(2): For any x ∈ R n , let q(x) = ( x 1 , x 2 , . . . , x w ) ∈ R w . It is easy to see that||x|| 2 = n i=1 x i 2 , so ||q(x)|| 2 ≤ 1 when ||x|| 2 ≤ 1.Now we verify that: for any s ∈ S, we have s ∈ {x ∈ R n : W x = W (q(s) • W ), x ∈ S}.W s = w i=1 < w i , N i=1 s i w i >= w i=1 s i . Secondly, we have W (q(s) • W ) = w i=1 < w i , w i=1 s i w i >= w i=1 s i . So W s = W (q(s) • W ), resulting in s ∈ {x ∈ R n : W x = W (q(s)•W ), x ∈ S}, which implies that S = ∪ q∈R w ,||q||2≤1 {x ∈ R n : W x = W (q • W ), x ∈ S}.(3): By the proof of (2), we know that if x satisfiesx i = q i for i ∈ [w], then x ∈ {x ∈ R n : W x = W (q • W )}. By (1), {x ∈ R n : W x = W (q • W )} will not intersect for different q. Therefore, x ∈ {x ∈ R n : W x = W (q • W )} equals x i = q i for i ∈ [w]. Since ||x|| 2 = n i=1 x i 2 , when x ∈ {x ∈ R n : W x = W (q • W )}, we have x i = q i for i ∈ [w], so n i=w+1 x i 2 = ||x|| 2 2 -||q|| 2 2, and such n -w weight is optional.Therefore, {x ∈ R n : W x = W (q • W ), x ∈ S} is a ball in R n-w with radius 1 -||q|| 2 2 , so we get the result.Lemma D.5. Let r 3 > r 2 > r 1 , n ≥ 1 and x ≤ r 1 , then (r3-x) n -(r2-x) n (r1-x) n ≥ r n 3 -r n 2 r n 1 . Proof. Let f (x) = (r3-x) n -(r2-x) n (r1-x) n. We just need to prove f (x) ≥ f (0) when x ≤ r 1 . We calculate the derivative f (x) at first:f ′ (x) = ((r3-x) n -(r2-x) n ) ′ (r1-x) n -((r3-x) n -(r2-x) n )((r1-x) n ) ′ (r1-x) 2n . It is easy to calculate that ((r 3 -x) n -(r 2 -x) n ) ′ = -n((r 3 -x) n-1 -(r 2 -x) n-1 ) and ((r 1 -x) n ) ′ = -n(r 1 -x) n-1. Putting this into the above equation, we havef ′ (x) = -P (x)(((r 3 -x) n-1 -(r 2 -x) n-1 )(r 1 -x) -((r 3 -x) n -(r 2 -x) n ))Where P (x) is a positive value about x. Since((r 3 -x) n-1 -(r 2 -x) n-1 )(r 1 -x) -((r 3 -x) n -(r 2 -x) n ) = -(r 3 -x) n-1 (r 3 -r 1 ) + (r 2 -x) n-1 (r 2 -r 1 ) ≤ 0 we have f ′ (x) ≥ 0, resulting in f (x) ≥ f (0). The lemma is proved. Lemma D.6. Let a > b > 1, n > m ≥ 1. If a n -b n = 1. Then a m -b m ≤ 1. Proof. We have 1 = a n -b n ≥ b n-m (a m -b m ) > a m -b m .Lemma D.7. Let a > qb where q < 1 and a, b > 0. Then min{a, b} ≥ qb.Proof. When min{a, b} = b, by q < 1, the result is obvious. When min{a, b} = a, by a > qb, the result is obvious.Lemma D.8. For any w > 0, there exist r 1 , r 2 , r 3 and n such that (1):r n 3 -r n 2 = r n 1 ; (2): r n-w 3 -r n-w 2 ≥ 0.99r n-w 1 .Proof. Because the equations are all homogeneous, without loss of generality, we assume that r 1 = 1. We take α = 2 1/n -1, β + α = 3 1/n -1, and n to satisfy 3 w/n < 1.001. Let r 2 = 1 + α, r 3 = 1 + α + β. We show that this is what we want.At first, we haver n 3 -r n 2 = (1 + α + β) n -(1 + α) n = 3 -2 = 1 = r n 1 .We also have (1 + α + β) w < 1.001, named (k1). So we haver n-w 3 -r n-w 2 = (1 + α + β) n-w -(1 + α) n-w = (1+α+β) n-w (1+α) w -(1+α) n (1+α) w ≥ (1+α+β) n-w (1+α) w -(1+α) n 1.001 (by (k1)) = (1+α+β) n -(1+α+β) n-w ((1+α+β) w -(1+α) w )-(1+α) n 1.001 ≥ (1+α+β) n -(1+α) n -0.001(1+α+β) n 1.001 (by (k1)) = (1+α+β) n -(1+α) n -0.003 1.001 = 1-0.003 1.001 ≥ 0.99.The lemma is proved.In this section, we construct the distribution in Theorem 5.1. Definition D.9. Let q be a point in [0, 1] n , 0 < r 1 < r 2 < r 3 , and we defineB k 2 (z, t) = {x ∈ R k : ||x -z|| 2 ≤ t}, where k ∈ N + , z ∈ R k and t ≥ 0.The distribution D(n, q, r 1 , r 2 , r 3 ) is defined as:(1): This is a distirbution on R n × {-1, 1}.(2): A point has label 1 if and only if it is in B n 2 (q, r 1 ). A point has label -1 if and only if it is in B n 2 (q, r 3 )/B n 2 (q, r 2 ). (3): The points with label 1 or -1 satisfy the uniform distribution, and let the density function bef (x) = λ = 1 V (B n 2 (q,r3))-V (B n 2 (q,r2))+V (B nFrom r n 3 -r n 2 = r n 1 , we know that λV (B n 2 (q, r 1 )) = λ(V (B n 2 (q, r 3 )) -V (B n 2 (q, r 2 ))) = 0.5, so P (x,y)∼D (y = -1) = P (x,y)∼D (y = -1) = 0.5, and further consider the (c3), we have (r 23 ) (n-w)/2 -(r 2 2 ) (n-w)/2 (r 2 1 ) (n-w)/2 P (x,y)∼D (y = 1)≥ 0.5 (r 2 3 ) (n-w)/2 -(r 2 2 ) (n-w)/2 (r 2 1 ) (n-w)/2 ≥ 0.49.The theorem is proved.Firstly, note that Theorem 5.3 cannot be proved by the following classic result.). Let D be any joint distribution over R n × {-1, 1}, D tr a dataset of size N selected i.i.d. from D, and H = {h : R n → R} the hypothesis space. Then with probability at least 1 -δ,sup h∈H |R(h, D) -R(h, D tr )| ≥ Rad N (H) 2 -O( ln 1/δ N ),where R(h, D) is the population risk, R(h, D tr ) is the empirical risk, and Rad N (H) is the Radermecher complexity of H.Theorem E.1 is the classical conclusion about the lower bound of generalization error, and theorem 5.3 and Theorem E.1 are different. Firstly, Theorem E.1 is established on the basis of probability, whereas Theorem 5.3 is not. Secondly, Theorem E.1 highlights the existence of a gap between the empirical error and the generalization error for certain functions within the hypothesis space, and does not impose any constraints on the value of empirical error. However, memorization networks, which perfectly fit the training set, will inherently have a zero empirical error, so Theorem E.1 cannot directly address Theorem 5.3. Lastly, Theorem E.1 relies on Radermacher complexity, which can be challenging to calculate, while Theorem 5.3 does not have such a requirement.For the proof of Theorem 5.3, we mainly follow the constructive approach of memorization network in [55] , but during the construction process, we will also consider the accuracy of the memorization network. Our proof is divided into four parts.The general method of constructing memorization networks compresses the data into a low dimensional space at first, and we adopt this approach. We are trying to compress the data into 1-dimension space. However, we require the compressed data to meet some conditions, as stated in the following lemma.Lemma E. Because the density function of D is r, we haveP (x,y)∼D (x ∈ B 2 (z, r 1 )) ≤ rV (B 2 (z, r 1 )) < r(2r 1 ) n = 1 400N 2 for all z ∈ R n , where r 1 = 1 2(400rN 2 ) 1/n . It is easy to see that r 1 ≤ 1 because r ≥ 1.Result one: Let u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 . Then we have Result Two: Let u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 . ThenP (|⟨u, (x -z)⟩| ≥ cP u (P (x,y)∼D (∃(x i , y i ) ∈ D tr , |⟨u, (x -x i )⟩| < r 800N 2 8 nπ ) < 0.01) > 0.5.Firstly, by lemma B.2, and take T = 800N 2 , we can get that: for any given v ∈ R n , if u ∈ R n be uniformly randomly sampled from the hypersphere S n-1 , then P (|⟨u, v⟩| < ||v||2800N 2 8 nπ ) < 1 400N 2 .Thus, by such inequality, the density of D and the definition of r 1 , we have that:P u,(x,y)∼D (|⟨u, (x -v)⟩| < r1 800N 2 8 nπ ) = P u,(x,y)∼D (|⟨u, (x -v)⟩| < r1 800N 2 8 nπ | ||x -v|| 2 ≥ r 1 )P (x,y)∼D (||x -v|| 2 ≥ r 1 ) +P u,(x,y)∼D (|⟨u, (x -v)⟩| < r1 800N 2 8 nπ | ||x -v|| 2 < r 1 )P (x,y)∼D (||x -v|| 2 < r 1 ) < P u,(x,y)∼D (|⟨u, (x -v)⟩| < ||x-v||2 800N 2 8 nπ | ||x -v|| 2 ≥ r 1 ) + P (x,y)∼D (||x -v|| 2 < r 1 ) ≤ P u (|⟨u, (x -v)⟩| < ||x-v||2 800N 2 8 nπ ) + P (x,y)∼D (||x -v|| 2 < r 1 ) < 1 400N 2 + 1 400N 2 = 1/(200N 2). On the other hand, we haveP u,(x,y)∼D (|⟨u, (x -v)⟩| < r1 800N 2 8 nπ ) ≥ P u (P (x,y)∼D (|⟨u, (x -v)⟩| < r1 800N 2 8 nπ ) ≥ 0.01/N ) * 0.01/N. So, we have P u (P (x,y)∼D (|⟨u, (x-v)⟩| < r 800N 2 8 nπ ) ≥ 0.01/N ) < 1 200N 2 /(0.01/N ) = 1/(2N ).On the other hand, we haveEQUATIONnπ ) ≥ 0.01/N for some (x i , y i ) ∈ D tr . So taking v as x i in inequality (*) and using the above result, we haveP u (P (x,y)∼D (∃(x i , y i ) ∈ D tr , |⟨u, (x -x i )⟩| < r 800N 2 8 nπ ) < 0.01) = 1 -P u (P (x,y)∼D (∃(x i , y i ) ∈ D tr , |⟨u, (x -x i )⟩| < r 800N 2 8 nπ ) ≥ 0.01) ≥ 1 -(xi,yi)∈Dtr P u (P (x,y)∼D (|⟨u, (x -x i )⟩| < r 800N 2 8 nπ ) ≥ 0.01/N ) > 1 -N 1 2N = 0.5.Consider the fact: if A(u), B(u) are two events about random variable u, and P u (A(u) = T rue) > 0.5, P u (B(u) = T rue) > 0.5, then there is a u, which makes events A(u) and B(u) occurring simultaneously. By the above fact and Results one and two, we have that there exist ||u|| 2 = 1 (1): we haveand u ∈ R n such that |⟨u, (x -z)⟩| ≥ c 4N 2 8 nπ , ∀(x, -1), (z, 1) ∈ D tr and P (x,y)∼D (∃(x i , y i ) ∈ D tr , |⟨u, (x -x i )⟩)| < rO(nN 3 ) ≥ wx + b ≥ 1 for all x ∈ [0, 1] n . Firstly, because D is defined in [0, 1] n × {-1, 1}, we have ||x|| 2 ≤ √ n, resulting in and wx + b ≥ b -||w|| 2 √ n ≥ 1.On the other hand, using c ≤ 1 andr 1 ≤ 1, we have |wx| ≤ ||w|| 2 √ n ≤ O( nN 2 r1c ), so wx + b ≤ |wx| + b ≤ O(nN 3 r 1/n /c).(2): We have |w(x -z)| ≥ 4 for all (x, 1), (z, -1) ∈ D tr . EQUATIONThe purpose of this part is to map the compressed data to appropriate values. Let w ∈ R n and b ∈ R be given, and D tr = {(x i , y i )} N i=1 . Without losing generality, we assume that wx i < wx i+1 . In this section, we show that, after compressing the data into 1-dimension, we can use a network Fto map wx i + b to v [ i [ √ N ]] , where{v j } [ N [ √ N ] ] j=0are the given values. Furthermore, F should also satisfyF(wx + b) ∈ {v j } [ N [ √ N ]]+1 j=0 for all x ∈ [0, 1] n except for a small portion.This network has O( √ N ) parameters, as shown below.Lemma E.3. Let w ∈ R n and b ∈ R be given, {v j } [ N [ √ N ] ] j=0⊂ R and 1 > ϵ > 0 be given. (1):Let D tr = {(x i , y i )} N i=1F(wx i + b) = v [ i √ N] for all i ∈ [N ];(2):P (x,y)∼D (F(wx + b) ∈ {v j } [ N [ √ N ] ] j=0 ) ≥ 1 -ϵ.Proof. Let q i = (wx i+1 + b) -(wx i + b) and q = min i {q i }. Then we consider the set of pointsEQUATION, for any i. We have that:s∈Si P (x,y)∼D (wx + b ∈ (s -qϵ 2N /2, s + qϵ 2N /2)) = P (x,y)∼D (∃s ∈ S i , wx + b ∈ (s -qϵ 2N /2, s + qϵ 2N /2)) ≤ 1 Consider that |S i | ≥ N/ϵ, so for any i, there is a s i ∈ S i , makes that P (x,y)∼D (wx + b ∈ (s i - qϵ 2N /2, s i + qϵ 2N /2)) ≤ ϵ N .And it is easy to see that S i satisfies the following result: if z ∈ S i , then:wx i + b < wx i + b + qϵ 2N ≤ z ≤ wx i + b + qϵ 2N ([N/ϵ] + 1) < wx i + b + q i = wx i+1 + b. So we have (s i -qϵ 2N /2, s i + qϵ 2N /2) ∈ (wx i + b, wx i+1 + b), Name this inequality as ( * ). Let k = [ N [ √ N ] ] and t(i) = argmax j∈[N ] {[j/ √N ] = i}. Now, we define such a network:F(x) = k i=1 vi-vi-1 qϵ 2N (Relu(x -s t(i) + qϵ 2N /2) -Relu(x -s t(i) -qϵ 2N /2)) + v 0 .This network has width 2k, depth 2 and O( √ N ) parameters. We can verify that such networks satisfy (1) and (2).i ∈ [N ], let c(i) = [ i √ N ].Then, when j < c(i), we have t(j) < i, so s t(j) + qϵ 2N /2 ≤ wx t(j)+1 + b ≤ wx i + b (this has been shown in ( * )), resulting in:vj -vj-1 qϵ 2N (Relu(wx i + b -s t(j) + qϵ 2N /2) -Relu(wx i + b -s t(j) -qϵ 2N /2) = v j -v j-1 . When j ≥ c(i), similar to before, we have s t(j) -qϵ 2N /2 > wx i + b, resulting in vj -vj-1 qϵ 2N (Relu(wx i + b -s t(j) + qϵ 2N /2) -Relu(wx i + b -s t(j) -qϵ 2N /2) = 0. So F(x i ) = v 0 + (v 1 -v 0 ) + • • • + (v c (i) -v c(i)-1 ) = v c(i) ,this is what we want. Verify (2): At first, we show that for anyx ∈ [0, 1] n satisying wx + b / ∈ ∪ k i=1 (s i -qϵ 2N /2, s i + qϵ 2N /2), we have F(x) ∈ {v i }.This is because: for any x satisfies wx+ b / ∈ ∪ k i=1 (s i -qϵ 2N /2, s i + qϵ 2N /2), we have F(wx + b) = v 0 + (v 1 -v 0 ) + • • • + (v k -v k-1 ) = v k ,where k satisfies s t(k) < wx + b and k is the maximum. The proof is similar as above.Second, we show that the probability of such x is at least 1 -ϵ.By P (x,y)∼D (wx + b ∈ (s i -qϵ 2N /2, s i + qϵ 2N /2)) ≤ ϵ N for any i, we have P (x,y)∼D (∃i, wx + b ∈ (s i -qϵ 2N /2, s i + qϵ 2N /2)) ≤ k i=1 P (x,y)∼D (wx + b ∈ (s i -qϵ 2N /2, s i + qϵ 2N /2)) ≤ ϵ/N * N = ϵ,this is what we want. So F is what we want. The lemma is proved.This is the same as in section B.3.Three steps are required: data compression, data projection, label determination. The specific proof is as follows. Without losing generality, we assume that P (x,y)∼D (∀(z, y z ) ∈ D tr , |wx -wz| > 3, y = 1) > 0.99/2, which represents the following fact. Define S = {x : x has label 1 and |wx -wz| > 3 f or ∀(z, y z ) ∈ D tr }. Then the probability of points in S is at least 0.99/2. In the following proof, in order to make the network having bad generalization, we will make the network giving these points (the points in S) incorrect labels.Let c i = f 1 (x i )/ Without losing generality, we will assume c i ≤ c i+1 . Now, assume that we have N 0 samples in D tr with label 1, and {i j } N0 j=1 ⊂ [N ] such that x ij has label 1, andi j < i j+1 . Let t(i) = argmax j∈[N ] {[j/ √ N 0 ] = i} and v k = [c i t(k-1)+1 ][c i t(k-1)+2 ] . . . [c i t(k) ].In this part, the second part of F(x), named as f 2 (x), need to satisfyf 2 (c ij ) = (v [ j √ N] , c ij ). Furthermore, we also hope that P (x,y)∼D (f 2 (f 1 (x)) [1] ] by c ij , and the output in {v i } has probability 0.999. Retaining c i just need one node. So∈ {v i }) ≥ 0.999, where f 2 (f 1 (x))[i] is the i-th weight of f 2 (f 1 (x)), and P (x,y)∼D (f 2 (f 1 (x))[2]) = f 1 (x).f 2 need O( √ N ) parameters.Part Three, Label determination. In this part, we will use the v k mentioned in part two to output the label of inputs. The third part, named as f 3 (v, c), should satisfy that for f 3 (v k , c),where v k = [c i t(k-1)+1 ][c i t(k-1)+2 ] . . . [c i t(k) ] as mentioned above, if |c -c iq | < 1 for some q ∈ [t(k -1) + 1, t(k)], then f 3 (v k , c) > 0.1, and f 3 (v k , c) = 0 when |c -c iq | ≥ 1.1 for all q ∈ [t(k -1) + 1, t(k)].This network need O( √ N 0 ln(N 0 nr/c)) parameters, by (1) in lemma E.2 and lemma B.5.Construction of F and verify it:Let F(x) = f 3 (f 2 (f 1 (x))) -0.05. We show that F is what we want.(1): By parts one, two, three, and the fact N 0 ≤ N , it is easy to see that F has at most O(n + √ N ln(N nr/c)) parameters.(2): F(x) is a memorization of D tr . For any (x, y) ∈ D tr , two cases are consided.(1.1, if y = 1): using the symbols in Part two, because y = 1, so x = x i k for some k. As mentioned in part two,f 2 (f 1 (x)) will output (v i [ k √ N 0 ] , f 1 (x)). Then, by part three, because |f 1 (x) -[f 1 (x)]| < 1, so we have f 3 (f 2 (f 1 (x))) -0.05 ≥ 0.1 -0.05 > 0. (1.2 if y = -1): By (2) in lemma E.2, for ∀(z, 1) ∈ D tr , we know that |f 1 (x) -[f 1 (z)]| ≥ |f 1 (x) - f 1 (z)| -|f 1 (z) -[f 1 (z)]| ≥ 4 -1 = 3. So, by part three, we have f 3 (f 2 (f 1 (x))) = 0 -0.05 < 0.(3): A D (F) < 0.51. We show that, almost all x ∈ S (S is mentioned in part one) will be given wrong label.For x ∈ S, we have |wx -wx i | ≥ 3, so |wx + b -[wx i + b]| ≥ 2 for all (x i , y i ) ∈ D tr .Then for any v i , by part three and the definition of v i , we have f 3 (v i , wx + b) = 0 when x ∈ S. So, when f 2 (f 1 (x)) [1] ∈ {v i } and x ∈ S, we have f 3 (f 2 (f 1 (x))) -0.05 = 0 -0.05 < 0.Consider that for any x ∈ S, the label of x is 1 in distribution D. So when x ∈ S satisfies f 2 (f 1 (x)) [1] ∈ {v i }, we find that f (x) gives the wrong label to x. Since P (x ∈ S) ≥ 0.99/2 and P (f 2 (f 1 (x)) [1] ∈ {v i }) > 0.999, we have P (x ∈ S, f 2 (f 1 (x)) [1] ∈ {v i }) ≥ 0.99/2 -0.001 > 0.49.By the above result, we have that, with probability at least 0.49, Sgn(f (x)) ̸ = y, so A D (f ) < 0.51. So, we prove the theorem.We first give three simple lemmas.Lemma F.1. We can find 2[ n ⌈c 2 ⌉ ] points in [0, 1] n ,and the distance between any two points shall not be less than c.Proof. Let t = [ n ⌈c 2 ⌉ ].We just need to consider following points in [0, 1] n : For any given i 1 , i 2 , i 3 , . . . , i t ∈ {0, 1}, let x i1,i2,i3,...,it be the vector in [0, 1] n satisfying: for any j ∈ [t], the (j -1)⌈c 2 ⌉ + 1 to j⌈c 2 ⌉ weights of x i1,i2,i3,...,it is i j ; other weights are 0.We will show that, if {i 1 , i 2 , i 3 , . . . , i t } ̸ = {j 1 , j 2 , j 3 , . . . , j t }, then it holds ||x i1,i2,i3,...,itx j1,j2,j3,...,jt || 2 ≥ c. Without losing generality, let i 1 ̸ = j 1 . Then the first ⌈c 2 ⌉ weights of x i1,i2,i3,...,it and x j1,j2,j3,...,jt are different: one is all 1, and the other is all 0. So, the distance between such two points is at least ⌈c 2 ⌉ ≥ c.Then {x i1,i2,i3,...,it } ij ∈[0,1] is the 2 t point we want, so we prove the lemma. Lemma F.2. If ϵ, δ ∈ (0, 1) and k, x ∈ Z + satisfy that:x ≤ k(1 -2ϵ -δ), then 2 x ( [kϵ] j=0 k-x j ) < 2 k (1 -δ).Proof. We have2 x ( [kϵ] j=0 k-x j ) ≤ 2 x 2 k-x [kϵ] k-x ≤ 2 k kϵ k-x < 2 k (1 -δ).The first inequality sign uses m j=0 n m ≤ m2 n /n where m ≤ n/2, and byx ≤ k(1 -2ϵ -δ), so [kϵ] ≤ (k -x)/2. The third inequality sign uses the fact x ≤ k(1 -2ϵ -δ). Lemma F.3. If k, v ∈ R + such that kv > 3, and a = [kv] and 3 ≤ b ≤ √ k ln( √ k), then a ≥ (b/ ln(b)) 2 v/2. Proof. If √ k ≤ b/ ln(b), then b ≤ √ k ln( √ k) < √ k ln(b) ≤ b, which is impossible. So b ≤ √ k ln( √ k), and then √ k ≥ b/ ln(b). Resulting in a ≥ kv -1 ≥ kv/2 ≥ (b/ ln(b)) 2 v/2.Now, we prove Theorem 6.1Proof. By Theorem 4.1, we know that there is a v 1 > 1, when √ N ≥ n, for any distribution D ∈ D(n, c) and D tr ∼ D N , D tr has a memorization with v 1 √ N ln(N n/c) parameters. We will show that Theorem 6.1 is true for v = 1 32v 2 1 . Assume Theorem 6.1 is wrong, then there exists a memorization algorithm L such that for anyn ∈ Z + , c, ϵ, δ ∈ (0, 1), if D ∈ D(n, c) and N ≥ 1 32v 2 1 * N 2 D ln 2 (N D ) (1 -2ϵ -δ), we have P Dtr∼D N (A(L(D tr )) ≥ 1 -ϵ) ≥ 1 -δ.We will derive contradictions based on this L.Part 1: Find some points and values.We can find k, n, c, δ, ϵ satisfying (1): we have n, k ∈ Z + and 12v 1 ≤ n ≤ √ k. Let c = 1, and we can find k points in [0, 1] n and the distance between any pair of these points is greater than c;(2): δ, ϵ ∈ (0, 1) and q = [k(1 -2ϵ -δ)] ≥ 3.By lemma F.1, to make (1) valid, we just need n 2 < k ≤ 2 n , and (2) is easy to satisfy. Part 2: Construct some distributionLet {u i } k i=1 satisfy u i ∈ [0, 1] n and ||u i -u j || 2 ≥ c. By (1) mentioned in (1) in Part 1, such {u i } k i=1must exist. Now, we consider the following types of distribution D:(c1): D is a distribution in D(n, c) and P (x,y)∼D (x ∈ {u i } k i=1 ) = 1. (c2): P (x,y)∼D (x = u i ) = P (x,y)∼D (x = u j ) = 1/k for any i, j ∈ [k].It is obvious that, by ||u i -u j || 2 ≥ c, such a distribution exists. Let S be the set that contains all such distributions. We will show that for D ∈ S, it holdsN D ≤ v 1 √ k ln(kn/c).By Theorem 4.1 and definition of v 1 , we know that for any distribution D ∈ S, let y i be the label of u i in distribution D ∈ S. Then there is a memorization F of {(u i , y i )} k i=1 with at most v 1 √ k ln(kn/c) parameters. Then by (c1), the above result implies A D (F(x)) = 1, so we know thatN D ≤ v 1 √ k ln(kn/c) for any D ∈ S. Moreover, by k ≥ n ≥ 3, c = 1 and it is easy to see that N D ≥ n. We thus have 3 ≤ N D ≤ 4v 1 √ k ln( √ k).Part 3: A definition.Moreover, for D ∈ S, we define S(D) as the following set:Z ∈ S(D) if and only if Z ∈ [k] q is a vector satisfying: Define D(Z) as D(Z) = {(u zi , y zi )} q i=1 , then A D (L(D(Z))) ≥ 1 -ϵ,where z i is the i-th weight of Z and y zi is the label of u zi in distribution D.It is easy to see that, if we i.i.d select q samples in distribution D to form a dataset D tr , then (1): By c2, with probability 1, D tr only contains the samples (u j , y j ) where j ∈ [k];(2): Let D tr has the form shown in (1) . Then every time a sample is selected, it is in {(u i , y i )} k i=1 . Now we construct a vector in [k] q as follows: the index of i-th selected samples as the i-th component of the vector. Then each selection situation corresponds to a vector in [k] q which is constructed as before. Then by the definition of S(D), we have A D (L(D tr )) ≥ 1-ϵ if and only if the corresponding vector of D tr is in S(D).Putting N D ≤ 4v 1 √ k ln( √ k) and q = [k(1-2ϵ-δ)] in lemma F.3, we have q ≥ ( N D /(4v1) ln(N D /(4v1)) ) 2 (1- 2ϵ -δ)/2 ≥ N 2 D (1-2ϵ-δ) 32v 2 1 ln 2 (N D ) .By the above result and the by the assumption of L at the beginning of the proof, so that for any D ∈ S we have tEQUATIONPart 4: Prove the Theorem.Let S s be a subset of S, andS s = {D i1,i2,...,i k } ij ∈{-1,1},j∈[k] ⊂ S, where distribution D i1,i2,...,i k satisfies the label of u j is i j , where j ∈ [k].We will show that there exists at least one D ⊂ S s , such that |S(D)| < (1 -δ)k q , which is contrary to equation 4. To prove that, we just need to prove thatD∈Ss |S(D)| < (1 -δ)2 k k q , use |S s | = 2 k here.To prove that, for any vector Z ∈ [k] q , we estimate how many D ∈ S s which makes Z to be included in S(D).Part 4.1, situation of a given vector Z and a given distribution D.For a Z = (z i ) q i=1 and D such that Z ∈ S(D), let len(Z) = {c ∈ [k] : ∃i, c = z i }. We consider the distributions in S s that satisfy the following condition: for i ∈ len(Z), the label of u i is equal to the label of u i in D.Obviously, we have 2 k-|len(Z)| distributions that can satisfy the above condition in S s . Let such distributions make up a set S ss (D, Z). Now, we estimate how many distributions D s in S ss (D, Z) satisfy Z ∈ S(D s ).For any distribution G ∈ S s , let y(G) i be the label of u i in distribution G, and define the datasetD tr = {(u zi , y(D) zi )} q i=1 . Then Z ∈ S(D s ) if and only if: for at least k -[kϵ] of i ∈ [k], L(D tr ) gives the label y(D s ) i to u i .Firstly, consider that when i ∈ len(Z). For any D s ∈ S ss (D, Z), we have y(D s ) i = y(D) i and L(D tr ) must give the label y(D) i to u i , so when i ∈ len(Z), L(D tr ) gives the label y(D s ) i to u i .Then, consider i / ∈ len(Z). Because Z is a given vector, so if Z ∈ S(D s ), the label y(D s ) i where i / ∈ len(Z) are at most [kϵ] different from the label of u i given by L(D tr ).So, by the above two results, this kind of D s is at most[kϵ] i=0 k-|len(Z)| i. So, we have And there exist[kϵ] i=0 k-|len(Z)| i number of distributions D s in S ss (D, Z) satisfy Z ∈ S(D s ).k q different Z, so D∈Ss |S(D)| ≤ Z 2 |len(Z)| [kϵ] i=0 k-|len(Z)| i ≤ Z 2 k (1 - δ) = k q 2 k (1 -δ).For the last inequality, we use2 |len(Z)| [kϵ] i=0 k-|len(Z)| i < 2 k (1 -δ), which can be shown by |len(Z)| ≤ q and lemma F.2.This is what we want. we proved the theorem.We now prove Corollary 6.4.Proof. Using lemma F.1, we can find 2 1] n and the distance between any two points shall not be less than c. So we take a ϵ, δ such that (1) in the part 1 of the proof of Theorem 6.1, then similar as the proof of Theorem 6.1, and we get this corollary.[ n ⌈c 2 ⌉ ] points in [0,1 -2ϵ -δ > 0, n = 3[12v 1 /(1 -2ϵ -δ)] + 3, c = 1 and k = 2 [ n ⌈c 2 ⌉ ] in theG Proof of Theorem 6.5Firstly, it is easy to show that there exists a memorization algorithm which satisfies L(D tr ) ≤ N D when D tr ∼ D N with probability 1. We just consider the following memorization algorithm: To prove (1) in the theorem, we need three lemmas. Lemma G. 1 ([44] ). Let H be a hypothesis space with VCdim h and D is distribution of data, if N ≥ h, then with probability 1 -δ of D tr ∼ D N , we have And consider that f ′ (x) = 1-ln((ba/c)x)x 2 ≤ 0 when x ≥ 1, so, when x ≥ 2 ln(ba/c), we have f (x) ≤ f (2 ln(ba/c)) ≤ 1, which means that when cu/a ≥ 2 ln(ba/c), it holds ln(ba/c(cu/a)) cu/a ≤ 1. The lemma is proved.Lemma G. 3 ([6] ). Let H m be the hypothesis space composed of the networks with at most m parameters. Then the VCdim of H m is not more than qm 2 ln(m), where q is a constant not dependent on m.Then we can prove (1) in the theorem.Proof. Let D tr ∼ D N . Because the algorithm satisfies the condition in theorem, then L(D tr ) ∈ H N D , where H N D is defined in lemma G. 3 . By lemma G.3, the VCdim of H Dtr is not more than qN 2 D ln(N D ) for some q ≥ 1. Using lemma G.1 to this fact, we have N ≥16qN 2 D ln(N D ) ln( 64qeN 2 D ln(N D ) δϵ 2 ) ϵ 2. Take these values in lemma G.1, and considering that the memorization algorithm L must satisfy that E Dtr (L(D tr )) = 1, using lemma G.2 (just take a = 8qN 2 D ln(N D ), b = 8e/δ and c = ϵ 2 in lemma G.2), we have1 -E D (L(D tr )) ≤ 8qN 2 D ln(N D ) ln 8eN δ N ≤ ϵ which implies 1 -ϵ ≤ E D (L(D tr )).The theorem is proved.We need three more lemmas to prove Theorem 6.5.Lemma G.4. Let D ⊂ [0, 1] n × {-1, 1}.Then D has a memorization with width 1 if and only if D is linearly separable.Proof. If D is linearly separable, then it obviously has a memorization with width 1.If D has a memorization with width 1, we show that D is linearly separable. Let F be the memorization network of D with width 1, and F 1 the first layer of F.We show that it is impossible to find any (x 1 , 1), (x 2 , -1), (x 3 , 1) ∈ D such that F 1 (x 1 ) < F 1 (x 2 ) < F 1 (x 3 ). If we can, then contradiction will be obtained.Assume (x 1 , 1), (x 2 , -1), (x 3 , 1) Because (x 1 , 1), (x 2 , -1), (x 3 , 1) ∈ D satisfy that F 1 (x 1 ) < F 1 (x 2 ) < F 1 (x 3 ), and each layer of F is a linear function composite Relu, so after each layer, the order of F 1 (x 1 ), F 1 (x 2 ), F 1 (x 3 ) is not changed or contrary. So there must be F(x 1 ) ≤ F(x 2 ) ≤ F(x 3 ) or F(x 1 ) ≥ F(x 2 ) ≥ F(x 3 ). Then F cannot classify x 1 , x 2 , x 3 correctly, which contradicts to the fact that F is a memorization of D.∈ D such that F 1 (x 1 ) < F 1 (x 2 ) < F 1 (x 3 ).Part 2: We show that, it is impossible to find any (x 1 , -1), (x 2 , 1), (x 3 , -1) ∈ D such thatF 1 (x 1 ) < F 1 (x 2 ) < F 1 (x 3 ).This is similar to Part 1.By parts 1 and 2, without losing generalization, we know that for any (x 1 , 1), (x 2 , -1) ∈ D, it holds If for all (x, -1) ∈ D, we have x < a, then D is linear separable, and the result is valid. If for all (x, -1) ∈ D, we have x > b, then D is linear separable, and the result is valid. Now we consider the situation where x > a for some (x, -1) ∈ D and x < b for some (x, -1) ∈ D.F 1 (x 1 ) > F 1 (x 2 ). SinceLet x -1 = max (x,-1)∈D {x < a}. Then for F 1 (x) = x -(x -1 + a)/2, it is easy to verify that F 1 (x) > a-x-1 2 for all x ≥ a and F 1 (x) < 0 for all (x 0 , -1) ∈ D such that x 0 < a.Let x 1 = min (x,-1)∈D {x > b}. Then for F 2 (x) = x -(x 1 + b)/2, it is easy to verify that F 2 (x) < 0 for all x ≤ b and F 2 (x) > (x 1 -b)/2 for all (x 0 , -1) ∈ D such that x 0 > b.Let the network F be defined by F = Relu(F 1 (x)) -T Relu(F 2 (x)) -t, where T = 8 x1-b is a positive real number, and t = a-x-1 4 > 0.Now we prove F is what we want. It is easy to see that, F is a depth 2 width 2 network. When x ∈ [a, b], then F 1 (x) > a-x-1 2 and F 2 (x) ≤ 0, so F (x) > 0. For (x, -1) ∈ D such that x < a, we have F 1 (x) < 0 and F 2 (x) < 0, so F (x) < 0; for (x, -1) ∈ D such that x > b, we haveF 1 (x) < 1 and F 2 (x) > x1-b 4 , so F (x) ≤ 1 -2 -a-x-1 4 < 0,this is what we want.Part 2: If D has a memorization with width 2 and depth 2, then we show that D satisfies conditions (c1) or (c2).If D is linear separable, (c1) and (c2) are valid. If not, without losing generality, assume that (x 1 , 1), (x 2 , -1), (x 3 , 1) ∈ D such that x 1 < x 2 < x 3 (for the situation that (x 1 , -1), (x 2 , 1), (x 3 , -1) ∈ D such that x 1 < x 2 < x 3 , the proof is similar). Then we show that if (x, -1) ∈ D, we have x 1 < x < x 3 . Assume (x 0 , -1) ∈ D such that x 0 < x 1 , then we have that x 0 < x 1 < x 2 < x 3 , then we can deduce the contradiction.Let F = aRelu(F 1 (x)) + bRelu(F 2 (x)) + c be the memorization network of D, whereF i (x) is a linear function. Let u, v ∈ R such that F 1 (u) = F 2 (v) = 0, without loss generality, let u ≤ v.Then we know that F is linear in such three regions: (-∞, u], [u, v] and [v, ∞). We call the three regions as linear regions of F . We prove the following three results at first.(1): The slope of F on (-∞, u] is positive.Firstly, we show that x 0 ∈ (-∞, u]. If not, since (x 0 , -1), (x 1 , 1), (x 2 , -1) are not linear separable, and (x 1 , 1), (x 2 , -1), (x 3 , 1) are not linear separable, we have (x 0 , -1), (x 1 , 1) ∈ [u, v] and (x 2 , -1), (x 3 , 1) ∈ [v, ∞). Then, because x 1 > x 0 and F (x 1 ) > F (x 0 ), and F is linear in [u, v], we have that F (v) ≥ F (x 1 ) > 0. Now we consider the points (v, 1), (x 2 , -1), (x 3 , 1). It is easy to see that F memorizes such three points and they are in the linear region of F , so (v, 1), (x 2 , -1), (x 3 , 1) is linear separable, which is impossible because v ≤ x 2 ≤ x 3 and resulting in contradiction, sox 0 ∈ (-∞, u].If the slope of F on (-∞, u] is not positive, since u ≥ x 0 , we have F (u) < 0. Now we consider the points (u, -1), (x 1 , 1), (x 2 , -1), (x 3 , 1). Just similar to above to get the contradiction. So the slope of F on (-∞, u] is positive.(2): The slope of F on [v, ∞) is positive. Similar to (1) .(3): The slope of F on (-∞, u] is negative. If not, F must be a non-decreasing function, which is impossible.Using (1),( 2),(3), we can get a contradiction, which means that there is a (x 0 , -1) ∈ D such that x 0 < x 1 is not possible.Consider that, in a linear region of F , if the activation states of F 1 and F 2 are both not activated, then on such linear regions, the slope of F is 0. But due to (1),( 2),(3), all linear regions have non-zeros slope of F , so on each linear regions, at least one of F 1 and F 2 is activated. So, the activation states of F 1 and F 2 at (-∞, u], [u, v] and [v, ∞) is (-, +), (+, +), (+, -) (+ means activated, -means not activated).Then the slope of F on [u, v] is equal to the sum of the slopes of F on (-∞, u] and the slope of F on [v, ∞). But by ( 1),( 2), (3) , that means a negative number is equal to the sum of two positive numbers, which is impossible. So we get a contradiction.So if (x 0 , -1) ∈ D, we have x 0 > x 1 . Similar to before, we have x 0 < x 3 . So we get the result.By the above result, all the samples (x 0 , -1) ∈ D satisfies x ∈ (x 1 , x 3 ), so there is a close interval in (x 1 , x 3 ) such that: if (x 0 , -1) ∈ D, then x 0 is in such interval, then (c2) is vald, and we prove the lemma.G. 4 The algorithm is no-efficient. Now we prove (2) of theorem 6.5, that is, all such algorithm is not efficient if P ̸ = N P . We need the reversible 6-SAT problem defined in definition 6.6.Proof. We will show that, if there is an efficient memorization algorithm which satisfies the conditions of the theorem (has at most N D parameters with probability 1), then we can solve the reversible 6-SAT in polynomial time, which implies P = N P .Firstly, for the 6-SAT problem, we write it as the following form.Let φ = ∧ m i=1 φ i (n, m) be a 6-SAT for n variables, where φ i (n, m) = ∨ 6 j=1 xi,j and xi,j is either x s or ¬x s for some s ∈ [n] (see Definition 6.6). Then, we define some vectors in R n based on φ i (n, m).For i ∈ [m], define Q φ i ∈ R n as follows: Q φ i [j] = 1 if x j occurs in φ i (n, m); Q φ i [j] = -1 if ¬x j occurs in φ i (n, m); Q φ i [j] = 0 otherwise. Q φ i [j]is the j-th entry in Q φ i , then six entries in Q φ i are 1 or -1 and all other entries are zero.D(φ) = {(x i , y i )} m+4n i=1 ⊂ [0, 1] n × [2] as follows. (1) For i ∈ [n], x i = 1 i /3 + 1.11/3, y i = 1.(2) For i ∈ {n + 1, n + 2, . . . , 2n}, x i = 1.11 i-n /3 + 1.11/3, y i = -1.(3) For i ∈ {2n + 1, 2n + 2, . . . , 3n}, x i = -1 i-2n /3 + 1.11/3, y i = 1.(4) For i ∈ {3n + 1, 3n + 2, . . . , 4n}, x i = -1.11 i-3n /3 + 1.11/3, y i = -1.(5) For i ∈ {4n + 1, 4n + 2, . . . , 4n + m}, x i = 1/12Q φ i-4n + 1.11/3, y i = 1. Here, 1 i is the vector whose i-th weight is 1 and other weights are 0, 1 is the vector whose weights are all 1.Let L be an efficient memorization algorithm which satisfies the condition in the theorem. Then we prove the following result: If n ≥ 4 and φ is a reversible 6-SAT problem, then para(L(D(φ))) = n+8 if and only if φ has a solution, which means P = N P and leads to that L does not exist when P ̸ = N P . The proof is divided into two parts. Firstly, we show that {(x 1 , 1), (x n+1 , -1), (x 2n+1 , 1), (x 3n+1 , -1)} ⊂ D(φ) are not linearly separable. This is because {x 1 , x n+1 , x 2n+1 , x 3n+1 } is a linear transformation of {1 1 , 1.11 1 , -1 1 , -1.11 1 }, so {(x 1 , 1), (x n+1 , -1), (x 2n+1 , 1), (x 3n+1 , -1)} ⊂ D(φ) are not linearly separable if and only if {(1 1 , 1), (1.11 1 , -1), (-1 1 , 1), (-1.11 1 , -1)} are not linearly separable, by the definition of 1 1 , easy to see that {(1 1 , 1), (1.11 1 , -1), (-1 1 , 1), (-1.11 1 , -1)} are not linearly separable, so we get the result.By the above result, a subset of D(φ) is not linearly separable, so we have that D(φ) is not linearly separable. So, by lemma G.4, L(D(φ)) must have width more than 1. For a network with width at least 2, when it has depth 2, it has at least 2n + 5 parameters; when it has depth 3, it has at least n + 8 parameters; when it has depth more than 3, it has at least n + 10 parameters. So when n ≥ 4, we have para(L(D(φ))) ≥ n + 8. Part 1.2: If φ is a reversible 6-SAT problem that has a solution, then para(L(D(φ))) ≤ n + 8.We define a distribution D at first. D is defined on D(φ), and each point has the same probability. It is easy to see that, D ∈ D(n, 1/30).Since when N ≥ m + 4n, we have P Dtr∼D N (D tr = D(φ)) > 0, so by the definition of N D and the fact L satisfies the conditions in the theorem, we have para(L(D(φ))) ≤ N D . Moreover, because D is defined on D(φ), we will construct a network with n + 8 parameters to memorize D(φ) to show that N D ≤ n + 8, which implies para(L(D(φ))) ≤ N D ≤ n + 8 because L satisfies the condition in the theorem. This network has three layers, the first layer has width 1; the second layer has width 2; the third output layer has width 1.Let s = (s 1 , s 2 , . . . , s n ) ∈ {-1, 1} n be a solution of φ. Then the first layer is F 1 (x) = Relu(3s(x -1.11/3) + 3). Then we have the following results:(1): F 1 (x) = 4.1 or F 1 (x) = 1.9 for all (x, -1) ∈ D(φ);(2): 2 ≤ |F 1 (x)| ≤ 4 for all (x, 1) ∈ D(φ).(1) is very easy to validate. We just prove (2) .For i ∈ [n] and i ∈ {2n + 1, . . . , 3n}, because s ∈ {-1, 1} n , so 3s(x -1.11/3) = 1 or 3s(x - 1.11/3) = -1, which implies 2 ≤ |F 1 (x i )| ≤ 4.For i ∈ {4n + 1, . . . , 4n + m}, x i -1.11/3 has only six components that are not 0. Because s is the solution of φ, which indicates that at least one of the six non-zero components of x i -1.11/3 has the same positive or negative shape as the corresponding component of s. Consider that such six non-zero components of x i -1.11/3 are in {-1/12, 1/12}, so 3s(x i -1.11/3) ≥ 1/4 -5/4 = -1.Moreover, because φ is a reversible problem, so φ i (n, m) and φ i (n, m) are both in the φ, which indicates that the positive and negative forms of the six non-zero components of x i -1.11/3 cannot be exactly the same as the positive and negative forms of the corresponding components in s, or there must be φ i (n, m) = 0, which contradicts to s is the solution of φ. So, we have 3s(x i -1.11/3) ≤ 5/4 -1/4 = 1.Then we have that, for i ∈ {4n + 1, . . . , 4n + m}, it holds 3s(x i -1.11/3) ∈ [-1, 1], resulting in 2 ≤ |F 1 (x i )| ≤ 4. We proved (2) .By (1) and (2), and using lemma G.5, there is a network F 2 : R → R with width 2, depth 2 and 7 parameters that can classify the {(F 1 (x i ), y i )} 4n+m i=1 , so F 2 • F 1 is the network we want. By such a network, we have that N D ≤ n + 8, and then, we have para(L(D(φ))) ≤ N D ≤ n + 8. We proved the result.Part Two: If φ is a reversible 6-SAT problem and para(L(D(φ))) = n + 8, then φ has a solution.If L(D(φ)) has width 2 of the first layer, then para(L(D(φ))) ≥ 2n + 5 > n + 8, so when para(L(D(φ))) = n + 8, the first layer has width 1.Write L(D(φ)) = F 2 (F 1 (x)), and write F 1 as F 1 (x) = Relu(3s(x -1.11/3) + b), and let s = (s 1 , s 2 , . . . , s n ).We will prove that Sgn(s) = (Sgn(s 1 ), Sgn(s 2 ), Sgn(s 3 ), . . . , Sgn(s n )) is a solution of φ. The proof is given in two parts. i ̸ = 0 for any i ∈ [n]. Because if s i = 0, it holds F 1 (x i ) = F 1 (x n+i ), which implies that L(D(φ)) gives the same label to x i and x n+i , but x i and x n+i have the different labels in dataset D(φ), so it contradicts L(D(φ)) is the memorization of D(φ). Because D(φ) is not linear separable, so by lemma G.4, L(D(φ)) has width more than 1. Because F 1 has width 1, so F 2 has width 2 and 7 parameters, resulting in that F 2 is a network with width 2 and depth 2. And F 2 can classify such six points: {(F 1 (x i ), y i )} i∈{1,n+1,2n+1,3n+1,2n,4n} .1 | ≥ |s 2 | ≥ • • • ≥ |s n |.If s 1 > 0, taking the values of x 1 , x n+1 , x 2n+1 , x 3n+1 in F 1 , we have 1.1s 1 + b = F 1 (x n+1 ) ≥ s 1 + b = F 1 (x 1 ) ≥ -s 1 + b = F 1 (x 2n+1 ) ≥ -1.1s 1 + b = F 1 (x 3n+1 ), which implies F 1 (x n+1 ) ≥ F 1 (x 1 ) ≥ F 1 (x 2n+1 ) ≥ F 1 (x 3n+1 ); if s 1 < 0. Similarly as before, we have F 1 (x n+1 ) ≤ F 1 (x 1 ) ≤ F 1 (x 2n+1 ) ≤ F 1 (x 3n+1 ). So, F 1 (x 1 ) and F 1 (x 2n+1 ) are always in the interval from F 1 (x n+1 ) to F 1 (x 3n+1 ).Consider that x n+1 and x 3n+1 have label -1, x 1 and x 2n+1 have label 1, so by Lemma G.5, if {(F 1 (x i ), y i )} i∈{1,n+1,2n+1,3n+1,2n,4n} can be memorized by a depth 2 width 2 network, then F 1 (x 2n ) and F 1 (x 4n ) must be not in the interval from F 1 (x 1 ) to F 1 (x 2n+1 ), or we cannot find a interval satisfies the conditions of lemma G.5.Since max{F 1 (x 2n ), F 1 (x 4n )} = 1.1|s n | + b, to ensure that F 1 (x 2n ) and F 1 (x 4n ) are not in the interval from F 1 (x 1 ) to F 1 (x 2n+1 ), we have max{F1 (x 2n ), F 1 (x 4n )} = 1.1|s n | + b ≥ max{F 1 (x 1 ), F 1 (x 2n+1 )} = |s 1 | + b or max{F 1 (x 2n ), F 1 (x 4n )} = 1.1|s n | + b ≤ min{F 1 (x 1 ), F 1 (x 2n+1 )} = -|s 1 | + b. The second case is impossible, so we have 1.1|s n | ≥ |s 1 |.This is what we want in this part.Part 2.2 We show that Sgn(s) is the solution of φ. Assume that Sgn(s) is not the solution of φ. There is a i ∈ {4n + 1, . . . , 4n + m}, such that the positive and negative forms of the six non-zero components of x i are exactly the same as the positive and negative forms of the corresponding components in s.Then sx i + b ≥ 6/4|s n | + b ≥ 6/4.4|s 1 | + b ≥ 1.1|s 1 | + b. So, by max{F 1 (x 1+n ), F 1 (x 3n+1 )} = 1.1|s 1 | + b and min{F 1 (x 1+n ), F 1 (x 3n+1 )} = -1.1|s 1 | + b, we know that F 1 (x i ) is not in the interval from F 1 (x 1+n ) to F 1 (x 3n+1 ).Then similar to part 2.1, consider the point {(F 1 (x i ), y i )} i∈{1,n+1,2n+1,3n+1,i} , we have that F 1 (x 1 ) and F 1 (x 2n+1 ) are always in the interval from F 1 (x n+1 ) to F 1 (x 3n+1 ), but F 1 (x i ) is not in the interval from F 1 (x 1+n ) to F 1 (x 3n+1 ). By lemma G.5 and the fact that the label of F 1 (x n+1 ) and F 1 (x 3n+1 ) is different from that of other three samples, we cannot find an interval satisfying the condition in lemma G.5, so F 2 (x) cannot classify such five points: {(F 1 (x i ), y i )} i=1,n+1,2n+1,3n+1,i . This is contradictory, as L(D(φ)) is the memorization of D(φ). So, the assumption is wrong, we prove the theorem. Let S c = {(i 1 c/(6.2n), i 2 c/(6.2n), . . . , i n c/(6.2n))∥i j ∈ {0, 1, . . . , [6.2n/c] + 1}}, and define S c (D) as: for any (i 1 c/(6.2n), i 2 c/(6.2n), . . . , i n c/(6.2n)) ∈ S c , randomly take a (x, y) ∼ D satisfying ||x -(i 1 c/(6.2n), i 2 c/(6.2n), . . . , i n c/(6.2n))|| ∞ ≤ c/(6.2n) (if we have such a x), and put (x, y) into S c (D).Then, we have that, for any (x, y) ∼ D, there is a point z ∈ S c such that ||z -x|| ∞ ≤ c/(6.2n), and there is a(x z , y z ) ∈ S c (D) such that ||z -x z || ∞ ≤ c/(6.2n), so ||x z -x|| ∞ ≤ c/(3.1n), which implies ||x -x z || ∞ ≤ c/3.1.Since the radius of B((z, w)) is more than c/3.1, for any (x, y) ∼ D, we have x ∈ ∪ (z,w)∈Sc(D) B((z, w)), we prove the lemma.For a given dataset D tr ⊂ [0, 1] n × {-1, 1}, we use the following two steps to construct a memorization network: (c1): Find suitable convex sets {C i } in [0, 1] n , ensuring that: each sample in D tr is in at least one of these convex sets. Furthermore, if x, z ∈ C i and (x, y x ), (z, y z ) ∈ D tr , then y x = y z , and define y(C i ) = y x .(c2): Construct a network F satisfying that for any x ∈ C i , Sgn(F(x)) = y(C i ). Such a network must be a memorization of D tr , because each sample in D tr is in at least one of {C i }, so if x ∈ C i and (x, y x ) ∈ D tr , then Sgn(F(x)) = y(C i ) = y x , which is the network we want. part 2.1. Firstly, we show that A D (F mem ) ≥ 1i / ∈Z(Dtr) Q i . If i ∈ Z(D tr ), then by the definition of Z(D tr ), we know that there is a j ∈ [N ] such that x j ∈ B((v i , y vi )), so by part one, we have Sgn(F mem (x)) = y j for any x ∈ B((v i , y vi )).Moreover, for any (x, y) ∼ D and x ∈ B((v i , y vi )), by lemma H.1 and B((v i , y vi )) ∈ C j which has been shown in part one, we know that y = y j . So Sgn(F mem (x)) = y j = y for any (x, y) ∼ D and x ∈ B((v i , y vi )), which means that F mem gives the correct label to all x ∈ B((v i , y vi )) when i ∈ Z(D tr , S). So A D (F mem ) ≥ i∈Z(Dtr,S) Q i ≥ 1i / ∈Z(Dtr,S) Q i . part 2.2. Now, we show that P Dtr∼D N ( i / ∈Z(Dtr) Q i ≤ ϵ) ≥ 1 -δ. Let Cc i = {D tr ∥D tr ∼ D N , i / ∈ Z(D tr ) and j ∈ Z(D tr ) f or ∀j > i}, easy to see that Cc j ∩Cc i = ∅ when i ̸ = j and N i=0 P Dtr∼D N (D tr ∈ Cc i ) = 1. It is easy to see that, P Dtr∼D N (D tr ∈ Cc i ) ≤ (1 -Q i ) N when i ≥ 1.Firstly we have that, if some i ∈ [S D ] makes that Q i < ϵ/i, then for any D tr ∈ Cc j where j ≤ i, we have k / ∈Z(Dtr) Q k ≤ j k=1 Q k ≤ jQ j ≤ iQ i < ϵ. So that, we consider two situations.Situation 1: There is a i ∈ [S D ] such that Q i < ϵ/i.Let N 0 be the biggest number in [S D ] such that Q N0 < ϵ/N 0 . Then we have that: P Dtr∼D N ( i / ∈Z(Dtr) Q i ≤ ϵ) = P Dtr∼D N ( i / ∈Z(Dtr) Q i ≤We try to verify Theorem 7.3 on MNIST and CIFAR10 [33] .For MNIST, we tested all binary classification problems with different label compositions. For each pair of labels, we use 500 corresponding samples with each label in the original dataset to form a new dataset D tr , and then construct memorization network for D tr by Theorem 7.3. For each binary classification problem, Table 1 shows the accuracy on the samples with such two labels in testset. 1 , we can see that the algorithm shown in the theorem 7.3 has good generalization ability for mnist, almost all result is higher than 90%.For CIFAR10, we test all binary classification problems with different label combinations. For each pair of labels, we use 3000 corresponding samples with each label in the original dataset to form a new dataset D tr , and then construct memorization network for D tr by Theorem 7.3. For each binary classification problem, Table 2 shows the accuracy on the samples with such two labels in testset.From Table 2 , we can see that, most of the accuracies are above 70%, but for certain pairs, the results may be poor, such as cat and dog (category 3 and category 5).Our memorization algorithm cannot exceed the training methods empirically. Training, as a method that has been developed for a long time, is undoubtedly effective. For each pair of labels, we use 3000 corresponding samples with each label in the original dataset to form a training set D tr , and train Resnet18 [28] on D tr (with 20 epochs, learning rate 0.1, use crossentropy as loss function, device is GPU NVIDIA GeForce RTX 3090), the accuracy of the obtained network is shown in Table 3 . generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If we have negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).Here, Ω and O mean that certain small quantities are omitted. Also, we keep the logarithm factor of ND for comparison with the upper bound(q,r1)) . 


Decision: This paper presented a novel and extensive theoretical studies of the generalization capabilities of memorization networks that interpolate a finite training set. The results provide valuable new insights into the understanding of key properties of neural network generalization.

Reviews: review: paper_summary: paper_summary: - The authors study the memorization capacity of ReLU networks and its generalization theory for i.i.d. datasets over the compact domain, under a binary classification setting.
- They propose two different memorization capacity upper bound of ReLU networks. One bound depends on the size $N$ of the training dataset ($O(\sqrt{N}\ln{N})$) and the other bound is independent of $N$. Notably, the second bound implies that even with an arbitrarily large dataset sampled i.i.d., a constant number $N_{\mathcal{D}}$ of the parameters is enough to memorize the dataset, where $N_{\mathcal{D}}$ depends only on the true data distribution $\mathcal{D}$.
- They show that memorization is not enough for generalization with concrete examples. First, a generalizable memorization network must have a width of at least $n$ (the data dimension). Second, for almost every data distribution, there exists a non-generalizable memorization network with $O(\sqrt{N}\ln{N})$ parameters ($N$: size of training dataset).
- They study the sample complexity for $(\\epsilon,\\delta)$-PAC-generalizable memorization networks. First, they provide a lower bound of sample complexity for general memorization networks. Second, they provide an upper bound of sample complexity for particular memorization networks with at most $N_{\mathcal{D}}$ parameters. Both bounds are tight in terms of $N_{\mathcal{D}}$ up to logarithmic factors.
- Lastly, they study the algorithm constructing a PAC-generalizable memorization network in poly$(N)$ time.
strength_weakness: strength_weakness: - W1. Compactness of the input domain
    - Line 47 of the introduction says the paper will consider the open domain $\mathbb{R}^n$ of input. However, only the compact input domain $[0,1]^n$ is considered throughout the paper. It is unclear whether the results on the compact domain can be easily extended to the  $\mathbb{R}^n$ case. In the approximation literature, it is important whether the input domain is compact or not. Thus, the authors should mention whether the extension to a larger domain $\mathbb{R}^n$ is easy. Or, it would be better to replace $\mathbb{R}^n$ with a compact input domain in the introduction.
- W2. Randomness in Theorem 4.1
    - Theorem 4.1 contains a probabilistic argument. However, it is unclear where the randomness comes from, with the theorem statement alone.
- W3. Efficiency of memorization algorithm in Theorem 4.3
    - It would be meaningful to mention whether the memorization algorithm in Theorem 4.3 is efficient.
- W4. Parameter complexity of efficient memorization algorithm in Theorem 7.3
    - It would be meaningful to clarify how many parameters the network constructed by the efficient memorization algorithm in Theorem 7.3 should have.
- W6. Minor comments on notations/typos (There are so many typos…)
    - Title: “Generalizablity” → “Generalizability”
    - Line 60: “…, (2) of Theorem 1.1…”
    - Please use $\overline{O}$ for upper bounds, $\overline{\Omega}$ for lower bounds, and $\overline{\Theta}$ for tight bounds (up to logarithmic factors).
    - Section 3.1: “$X_0 = x$” and “$n_0 = n$” must be explicitly mentioned.
    - As far as i know, $\mathbb{R}\_{+}$ and $\mathbb{Z}\_{+}$ usually include zero. To exclude zero, $\mathbb{R}\_{++}$ (or $\mathbb{R}\_{>0}$) and $\mathbb{Z}\_{++}$ (or $\mathbb{Z}\_{>0}$) are better to use.
    - Line 250: “generaizable” → “generalizable”
    - Line 274: “The density of distribution $\mathcal{D}$”
    - Line 279: “$A_{\mathcal{D}} (\mathcal{F}) \le 0.51$”
    - Line 291: “generazable” → “generalizable”
    - Line 309: “generalizability,.” → “generalizability.”
    - Line 321: “$N_D$” → “$N_{\mathcal{D}}$” (calligraphic D)
    - Line 325: “bpund” → “bound”
    - Line 337: “$\mathcal{D}_{\rm tr} \sim \mathcal{D}^N$
    - Lines 340 and 472: “Proof Idea.” is not in a bold font.
    - Line 367: What does it mean by “a subset of $(x,y)\sim \mathcal{D}$”?
    - Line 382: Is “$S_{\mathcal{D}} \ge N_{\mathcal{D}}^2$” really true? I guess it should be “$S_{\mathcal{D}} \gtrsim N_{\mathcal{D}}^2$”, ignoring logarithmic factors.
    - Line 619: “Uisng” → “Using”
    - Step Three in the proof of Theorem 4.3 (Appendix C): Please make clear which theorem of [61] you refer to.
    - Line 1052: “Tree” → “Three”
    - Section F: a very non-standard notation is used here: “$C^m_n$” means a binomial coefficient “$\binom{n}{m}$”! This makes the proof really hard to read. Please consider changing the notation.
    - Part 2 in the proof of Theorem 6.1: I guess $12v_1 \le N_{\mathcal{D}} \le 4v_1 \sqrt{k} \ln(\sqrt{k})$ is required for the later use, rather than $3 \le N_{\mathcal{D}} \le 4v_1 \sqrt{k} \ln(\sqrt{k})$. This can be fixed with minor changes.
    - Lines 1148-1149: Make clear that $S(\mathcal{D}) \subset [k]^q$.
    - Equation (4) and the rest of the proof of Theorem 6.1: I think $q^k$ should be replaced with $k^q$. See lines 1166, 1167, 1195, and 1196.
    - Line 1189: “Because” → “This is because”
    - Lines 1189-1192: several “$S_{ss}(\mathcal{D},Z)$”s are written in wrong symbols.
    - Line 1213: “Here, $E\_{\mathcal{D}}(\mathcal{F}) = \mathbb{E}\_{(x,y)\sim \mathcal{D}} [I(\operatorname{Sgn}(\mathcal{F}(x))=y)]$,  $E\_{\mathcal{D}\_{\rm tr}}(\mathcal{F}) = \frac{1}{N} \sum_{(x,y) \in \mathcal{D}\_{\rm tr}} I(\operatorname{Sgn}(\mathcal{F}(x))=y)$ ”.
    - Line 1224: “$n$” → “$m$”
    - Line 1249: “similarto” → “similar to”
    - and many more…
questions: questions: - Q1. Architectural constraint: ReLU network
    - A clear limitation of this work is that it is limited to a fully-connected ReLU network.
    - Can you imagine how the change in activation function will affect the memorization capacity, $N_{\mathcal{D}}$, and $S_{\mathcal{D}}$?
- Q2. Sample complexity bound gap of memorization algorithms in Section 6
    - Currently, there is an $\epsilon^{-2}$ gap between the upper and lower sample complexity for the generalization of memorization networks. I guess this is quite huge. Do you think this gap can be reduced?
- Q3. Proof of Corollary 6.4
    - The proof is too short. How did you get to the statement of Corollary 6.4 by plugging $k=2^{[\tfrac{n}{\lceil c^2 \rceil}]}$? It seems unclear to me.
- Q4. Algorithm in Theorem 7.3 as an initialization
    - Empirically, what if you run SGD (or other standard optimizers) with logistic loss starting from the network parameters constructed by the algorithm of Theorem 7.3? Will it be better than the result of SGD from random initialization?
- Q5. Generalizability of memorization v.s. non-memorization networks
    - I know this question is somewhat out of topic, but can you discuss the generalizability of memorization and non-memorization networks? Can a non-memorization network generalize better than some memorization networks? If so, when can it happen?
limitations: limitations: The authors have discussed the limitation in Section 8 (Conclusion). The major limitation is that it is unclear how to compute the numerical complexities $N_{\mathcal{D}}$, $S_{\mathcal{D}}$.
paper_summary: paper_summary: This paper provides a first, thorough theoretical understanding of the generalization ability of the memorized neural network, including the existence of the memorized neural network, the matching upper bound and lower bound on the sample complexity, the computational infeasibility of attaining optimal sample complexity, and a computation-efficient but sub-optimal remedy.
strength_weakness: strength_weakness: There are some comments, shown in the Questions below, but I recommend accepting this paper.
questions: questions: Major Comments:
1. I think the hypothesis class D(n,c) is simple to be learned. I guess, for fixed (c, n), if the density in the support of X is bounded from below and above, then the minimax (worst D) error rate in D is the parametric rate? Hence this is a relatively easy class of function to be analyzed, and there is almost no noise, which may weaken the results of this paper.
2. The existence result in Theorem 4.3 is nice. But it should be clear 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.
3. The upper bound and lower bound does not exactly match in its current form in terms of epsilon. I guess the lower bound is not tight, because it does not rule out the possibility that a fixed number of samples can have exact recovery (eps=delta=0), this is relatively loose. Can it be improved?



Minor comments:
1. I think the introduction part can make a clear, or informal definition of what is generalization under the well-separated classification task given it lists all the theoretical results.
limitations: limitations: See the Questions above.
paper_summary: paper_summary: This work studies the generalization properties of neural network memorization algorithms. Several results are proved: (1) Construction of a memorization network for a sampled dataset, with an optimal number of parameters. (2) There exists a constant such that for all datasets sampled from a distribution, there exists a memorization network with at most the constant number of parameters. (3) Sample complexity lower and upper bounds for memorization algorithms. (4) An efficient memorization algorithm with a generalization guarantee.
strength_weakness: strength_weakness: -	The significance of the theoretical results are not very clear because no estimates of $N_\mathcal{D}$ and $S_\mathcal{D}$ are given.

-	Writing can be improved, e.g.: “is also a challenge problem” line 408, “which is more challenging compare to linear model” line 44, “and shows that even if there is enough data” line 63, “In other word” line 87.
questions: questions: Can estimates of $N_\mathcal{D}$ and $S_\mathcal{D}$ be provided even for simple toy examples (e.g., linearly separable data)?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper studies the generalization capabilities of memorization networks, specifically networks that achieve optimal memorization capacity (i.e. O(sqrt(N)) parameters for memorizing N samples). The authors present a memorization algorithm that is based on the construction of Vardi et al. Next, they show that memorization with fixed width or small number of parameters cannot generalize well. They also provide upper and lower bounds for the communication complexity of learning with a memorization algorithm, while also providing an efficient memorization algorithm.
strength_weakness: strength_weakness: I think this paper is very nice overall, however, there are some issues with specific results which I would be happy to see the author’s response about:
- Proposition 3.8 - where is the proof? Also, it is not clear to me why the constructions in [54,48] are probabilistic. 

- There is something unclear about the proof of Theorem 5.3. The theorem statement is that for every distribution D and any test set D_tr there exists a memorization network that doesn’t generalize. However, in the proof, the authors begin with a given set D_tr, and then define D based on this training set, i.e. D is defined by some set S which in itself depends on D_tr. I think the statement should be that there exists a distribution D such that for all training set D_tr  there exists a memorization network that doesn’t generalize. Note that the current proof doesn’t show it, because D is constructed such that it depends on D_tr.

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

Some minor comments:

- Results and comparisons on implicit bias toward margin maximization of neural networks do not appear (e.g. https://arxiv.org/abs/1906.05890, https://arxiv.org/abs/2006.06657). They also study a regime where the optimization converged to 100% accuracy on the dataset and provide generalization guarantees based on margin arguments.

- In the main contribution, point 3, it is better to write lower bound is \Omega rather than O.
questions: questions: - How large can S_D be? It seems that for any continuous distribution on [0,1]^n, S_D is already exponential in n, hence having such a large sample complexity makes this bound vacuous. Can the authors provide some examples where S_D and N_D are not very far apart?

- What is the size (num of parameters, width, depth) of the network defined in Theorem 7.3?
limitations: limitations: The authors discuss the limitations of their results.

Comments: title: Thank you
Remaining Questions
comment: Thank you again for your nice review !
Thank you for the clarification, I'll keep the score.
Thank you again for your nice insights！
Thank you for your nice insights. About how to take the value of $n,c$  in the proof of Corollary 6.4, using the notation in the proof of th6.1, for the situation of $1-2\epsilon-\delta>0$, we can take $n=3[12v_1/(1-2\epsilon-\delta)]+3$ and $c=1$ to make them satisfies line 1130-1133; when $1-2\epsilon-\delta\le0$, the Corollary 6.4 is obvious stand for any $n$ and $c$, because the lower bound is a negative when $1-2\epsilon-\delta\le0$. We will give more detailed to the proof of Corollary 6.4 in the future version.
Thank you for your further reply.

* I guess they meant by Lemma F.1 (instead of Lemma E.2) in #7 of the author's response. Also, in the sentence "Then we take suitable n, c,... valid.", I am curious about what values of $n$ and $c$ are indeed suitable. Thus, I hope the authors will add much more detail to the proof of Corollary 6.4.

Given all the promises about further revisions, I am satisfied with the author's responses. I retain my score.
Thank you for your answer, my questions have been answered and I will keep my score.
I'm glad you replied to us, taking this opportunity, we would like to provide some more detailed responses.

For Question (W3): This proof of th4.3 uses the method in [61] and gives an algorithm with a large $N'_D$, and such algorithm is effective. But if we want to get an algorithm with a smaller $N_D'$, it's quite difficult, and it is NPC when $N_D'=N_D$.

For Question (Q4): Due to formatting issues, the table format is not easy to read, we show it at here:

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

For line 367: We want to express a subset composed by samples in a distribution. Strictly speaking for it, if the distribution $D$ is defined on $A\subset [0,1]^n\times\{-1,1\}$, then it means a subset composed of samples in $A$. For example, $D$ is defined as: $P_{(x,y)\sim D}((x,y)=(x_0,-1))=P_{(x,y)\sim D}((x,y)=(x_1,1))=0.5$, then $A=\\{(x_0,-1),(x_1,1)\\}$.

For line 382: You are right, we mainly want to express a possible relationship between $N_D$ and $S_D$, our expression is not strict, your recommendation is correct.
Thank you for your kind reply. I am happy with most of the answered questions/comments. 
I have to take some time to digest the responses for W1, W3, W4, and Q3. I will come back again after carefully checking these responses.

Unfortunately, the two questions in my original review are not answered yet, mainly inside the "minor typo/comment" part. Let me bring them here again:

1. Line 367: What does it mean by “a subset of $(x,y)\sim \mathcal{D}$”?
2. Line 382: Is “$S_{\mathcal{D}} \ge N_{\mathcal{D}}^2$” really true? I guess it should be “$S_{\mathcal{D}} \gtrsim N_{\mathcal{D}}^2$”, ignoring logarithmic factors.

I am looking forward to further responses to these unanswered questions. Also, if there are missing details for the response above due to the space limit, please leave them as a comment here, then I'll happily read them all.