Generalizablity of Memorization Neural Network
Authors: Lijia Yu
Xiao-Shan Gao
Lijun Zhang
Yibo Miao
Venue: NeurIPS 2024 poster (2024)
Keywords: generalization
memorization
sample complexity
Primary area: learning_theory
TL;DR: generalization of memorization

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.

Generalizability of Memorization Neural Networks
Lijia Yu', Xiao-Shan G.o Lijun Zhang Yibo Miao
Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences
2 Academy of Mathematics and Systems Science, Chinese Academy of Sciences Beijing 100190, China
University of Chinese Academy of Sciences, Beijing 100049, China
Abstract
The neural network memorization problem is to study the expressive power of neural networks to interpolate finite dataset. Although memorization is widely believed to have close relationship with the strong generalizability of deep learning when using over-parameterized models, to the best of our knowledge, there exists theoretical study on the generalizability of memorization neural networks. this paper, we give the first theoretical analysis of this topic. Since using i.i.d. training data is necessary condition for 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 given construct memorization networks for an i..d. dataset, which have the smallest number parameters and even constant number of parameters. Second, show that, in order for the memorization networks to be generalizable, the width of the network must be at least equal 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. It is also shown that there exist data distributions such that, to be generalizable for them, the memorization network must have 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.
Introduction
Memorization is to study the expressive power of neural networks to interpolate finite dataset [9]. The main focus of the existing work is to study how many parameters needed to memorize. For any dataset Dtr of size N and neural networks of the form F : R + RR memorization networks with O(N) parameters have been given with various model structures and activation functions 31
65 On the other hand, it is shown that in order to memorize an 56], the network must have at least 52(N) parameters, so the above algorithms are approximately optimal. Under certain assumptions, is shown that sublinear ( parameters sufficient to memorize Der [49]. Furthermore, Vardi et al. [55] give memorization network with optimal number of parameters: O(VN).
50 30
29
26
47 56
II
arbitrary dataset of size
664
Recently, is shown that memorization 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 very nice generalization on the test data 45 More precisely, the
Cooreeppndingg author.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

double descent phenomenon -5 indicates that when the networks reach the interpolation threshold, larger networks tend to have more generalizability [O]. 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 the- oretically, 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 data distribution. because i.i.d. training dataset is a necessary condition for learning algorithms to have generalizability [54, [4]. More precisely, we consider binary data distributions D over R" x {-1,1} and use Dtr ~ DM to mean that Drr is sampled i.i.d. from D and [Drr| N. All neural networks are of the form F : I + R. The main contributions of this paper include four aspects.
First, we give the smallest number of parameters required for network memorize an i..dd dataset. Theorem 1.1 (Informal. Refer to Section 4. Under mild conditions on D, if ~ DD, it holds
(1) There exists an algorithm to obtain memorization network of Der with width 6 and depth OVVN).
(2) There exists constant ND E 24 depending on DD only, such that memorization network of Dev with at most NDD parameters can be obtained algorithmicaly.
No is named as the memorization parameter complexity of DD which measures the complexity of D under which memorization network with < ND parameters exists for almost all Dar DN
Theorem allows us to give the memorization network for i.i.d dataset with the optimal number of parameters. When N small so that /N < Np. the memorization network needs at least (V(N) parameters proved in [6] and (1) of Theorem 1.1 gives the optimal construction. When N is large, (2) of Theorem I.] shows that a constant number of parameters is enough to memorize.
Second, we give necessary condition for the structure of the memorization networks to be generaliz- able, and shows that even if there enough data, memorization network may not have generalizability.
Theorem 1.2 (Informal. Refer to Section 5) Under mild conditions on D. if Drr ~ DN, it holds
(1) Let H be set of neural networks with width w. Then, there exist an integer n >> and data distribution 'D over Rha x {11,1} such that, any memorization network of Drr is not generalizable.
(2) For almost any D, there exists a memorization network of Dir. which has O(vN) parameters and is not generalizable.
Theorem 1.2 indicates that memorization networks with the optimal number of parameters O(vN) may have poor generalizability, and commonly used algorithms for constructing fixed-width memo- rization networks have poor generalization for some distributions. These conclusions demonstrate that the commonly used network structures for memorization not generalizable and new network structures are needed to achieve generalization.
Third, we give 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 Np be the memorization parameter complexity defined in Theorem [.I] Under mild conditions on 'D we have
(I) Lower bound. In order for a memorization network of any Drr ~ DDN to be generalizable, N N3
must be
(2) Upper bound. For any memorization network with at most No parameters for Der ~ DN, if
N = ON2 In ND), then the network is generalizable.
'Here, S2 and O mean that certain small quantities are omitted. Also, we keep the logarithm factor of No for comparison with the upper bound

---

Notice that the lower bound is for general memorization networks and the upper bound is for memorization networks with v ND parameters, which always exist by (2) Theorem [.]] In the latter case, the lower and upper bounds are approximately the same, which gives the exact sample complexity O(N 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)).
Remark 1.4. Unfortunately, these generalizable memorization networks cannot be computed effi- ciently, as shown by the following results proved by us.
(1) P # NP, then all networks in (2) of Theorem 1.3 cannot be computed in polynomial time.
(2) For some data distributions, 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 given in the following theorem.
Theorem 1.5 (Informal. Refer to Section 7.. There exists an Sp E 24 depending on D only such that, under mild conditions on D, if N (SD)), then we can construct a generalizable memorization network with O(N²n) parameters for any Dur DD in polynomial time.
Sp is named as the efficient memorization sample complexity for D, which measures the complexity of D that the generalizable memorization network of any D DD can be computed efficiently if N ((S)).
The memorization network in Theorem 1.5 has more parameters than the optimal number Ō(VN) of parameters required for memorization. The main reason is that building memorization networks with O(vN) parameters requires special technical skill that may break the generalization. On the other hand, as mention in [7]. pwerpparamttiization is good for generalization, so it is reasonable for us to use more parameters for memorization achieve generalization.
Remark 1.6. We explain the relationship between our results and interpolation learning 77. Inter- polation learning optimization to achieve memorization, which is while our approach gives a theoretical foundation for memorization networks. Once an interpolation is achieved, Theorem 1.2] (1) of Theorem and Theorem 1.3 valid for interpolation learning. For example, according to (1) of Theorem
practical approach,
S((NZ) is lower bound for the sample complexity 1.5 ((S)) is an upper bound for the sample complexity
1.3
of interpolation learning, and by Theorem
of efficient interpolation learning.
Main Contributions. Under mild conditions for the data distribution D, we have
We define the memorization parameter complexity ND 24 of D such that, memorization network for any D.r DD can be constructed, which has O(VN) or S Np 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 Drr in terms of the width and number of parameters of the memorization network.
We give lower bound (I(N)) of the sample complexity for general memorization networks as well as the exact sample complexity (NN3) for memorization networks with < Np parameters. We also show that for some data distribution, an exponential number of samples in is required to achieve generalization.
We define the efficient memorization sample complexity Sp E E4 for D, so that general- izable memorization network of any D DN can be computed in polynomial time, N O(Sp).
2 Related work
Memorization. The problem of memorization has a long history. In 9. it is shown that networks with depth 2 and ((V) parameters memorize binary dataset of size N. In subsequent work.

---

it is shown that networks with ((N) parameters can be a memorization for any dataset [31 50
30
26 and such memorization networks are approximately optimal for generic Since the VC dimension of neural networks with N parameters and depth /) and with ReLU as the activation function is at most (NND) [24]] S 6.. memorizing some special datasets of size N requires at least SZ(NN) parameters and there exists gap between this lower bound 27( (V and the upper bound O(N). Park et al. [49] show that network with O(N2/33 parameters is enough for memorization under certain assumptions. Vardi et al. [55] further give the memorization network with optimal number parameters [(vN)
65
29
64
56
dataset 664 56
[22], strengths of both generalization and memorization are combined in 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 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 72 38 53
59 66). For instance, Bartlett et al. (7) prove that over- parametrzzaiion allows gradient methods to find generalizable interpolating solutions for the linear regime. 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 estimate the generalization bound or sample complexity of leaning algorithms. Generalization bounds for neural networks are given in terms of the VC dimension [24 6 under
the normal training setting (27 44 g under the differential privacy training setting I. and under the adversarial training setting [60 58 In most cases, these generalization bounds imply that when the
training set 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] [1 TO 19, 20 (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.
3 Notation
In this paper, we use (A4) 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 S2(A) to mean value not less than cA for some constant c, and Z to mean that small quantities, such as logarithm, are omitted. We say for all (x, y) ~ there is event A stand means that P ((.))~-(AA) = 1.
3.1 Neural network
In this paper, we consider feedforward neural networks of the form F; IR + R and the (-th hidden layer of F(z) can be written
X, oW; + bt) ))) TR.
where o = Relu is the activation function, Xo- x and No = The last layer of is F(z) =
W, Wr+ X2 + b E. where is the number of hidden layers in F. The depth F is depth (F)
L + 1, the width of F is width(F) max the number of parameters of F is para
n + 1). Denote H(n)) be the set of all neural networks in the above form.
3.2 Data distribution
In this paper, we consider binary classification problems and use D to denote a joint distribution on D(m) = 00, 1]" x (-1,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 E Z, and E RR,, D(n, c) is the set of distributions D on D(n), which has positive separation bound: inf(e.1)(e.-I)>>) I| 2|12 2 c.

---

The accuracy of network F on distribution D is defined as
AD(F) ( Dee.))
v)
We use Dtr ~ DD to mean that D;, 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. (1) If Der ~ DN and 'D E D(n,c) c). then 23 o Ij when yi * Mjj- Such property ensures that Dtr be memorized. (2) Proposition 3 shows that there exists D such that any network is not generalizable over D, and this should be avoided. Therefore, distribution needs to meet certain requirements for dataset sampled from 'D to have generalizability. Proof of Proposition 3.3 is given in Appendix A (3) Most commonly used classification distributions should have positive separation bound.
Proposition 3.3. There exists distribution 'D such that AD(F) S 0.5 for any neural network F.
3.3 Memorization neural network
Definition 3.4. A neural network F H(n) is memorization of dataset Drr over D(n), if (z)(F( = y for any (z, y) E Dtr.
Remark 3.5. Memorization networks can also be defined more strictly as F(x) = y for any (x, y) D... 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 learning algorithm in this paper, as defined below. Definition 3.6. C Unezz 2()) + Unez, H(n) is called a memorization algorithm if for any n and D,, E (n)). ((D(r) is memorization network of D..-
Furthermore, memorization algorithm polynomial poly IR + IR such that L(D.r) can be computed in time poly(size(Dir)). where siz) the bit-size of Der-
called an efficient memorization algorithm there exists
Remark 3.7. It is clear that if C is efficient memorization algorithm, then para para()(D(r))) is also polynomial in size
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.
The methods given in 2 62) are efficient memorization algorithmss. 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.
Proposition 3.8.
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 denoted D,, D. this section, we show how to construct the memorization network with the optimal number of parameters for dataset under distribution.
4.1 Memorization network with optimal number of parameters
To memorize N samples, δ2( (NN) parameters are necessary 6 In
memorization network is given which has O (N) parameters under certain conditions, where O means that some logarithm factors in N and polynomial faccoors of other values are omitted. Therefore, Ø(VN) is the optimal number of parameters for network to memorize certain dataset. In the following theorem, we show that such result can be extended to dataset under distribution.
55
Theorem 4.1. Let D E D(n, e) and DDrr ~ DN, Then there exists memorization algorithm L such that L(Drr) has width 6 and depth (equivalently, the number of purameters) O(VN (n(Nn/c)) Furthermore, for any (0,1), L(Dre) can be computed in time poly(size(D.))).l (1/e))) with probability >
5

---

Proof Idea. This theorem can be proven using the idea from 155y. Let Dir = {(2,, vi) The mainly different is that in (53), requires ||æ; - =zıl 2 for all + j. which is no longer valid when Dtr is sampled i.i.d. from distribution 'D. Since 'D has separation bound c. > O, we have [r. 10-1 xzyll 2 foror all i.j satisfying Y: # Vj. which is weaker. Despite this difference, the idea of (55y 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 In(l/e) times, with probability 6, 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 Monte Carlo polynomial-time algorithm, that is, gives a correct answer with arbitrarily high probability. The algorithm given in [55] is also Monte Carlo algorithm.
4.2 Memorization network with constant number of parameters
In this section, we prove an interesting fact of memorization for dataset under distribution. We show that for a distribution D E D(n, c), there exists a constant ND E Z+ such that for all datasets sampled i...d from D, there exists a memorization network with ND parameters.
Theorem 4.3. There exists memorization algorithm & such that for any D E D(n, c). there is an N2 Σ+ satisfying that for any N > with probability Der DN we have para( (D((tr)) I No. The smallest N of the distribution D is called the memorization parameter complexity of D, written as ND.
Proof Idea. It suffices to show that we can find a memorization network of Der with a constant number of parameters, which depends on D only. The main idea is to take subset Dir of Dtr such that Der is contained in the neighborhood of Díy.. It can be proven that the number of elements in this subset is limited. Then construct robust memorization network Di, with certain budget (62), we obtain a memorization network of Der. which has a constant number of parameters. The proof is given in Appendix C
Combining Theorems and we can give a memorization network with the optimal number of parameters.
Remark 4.4. What we have proven in Theorem 4.3 that a memorization algorithm with a constant number of parameters can be found, but in most of times, we have No >> ND. Furthermore, if N is large for the memorization algorithm, the algorithm can efficient. Otherwise, if N is closed to ND. the algorithm is usually not efficient.
Remark 4.5. obvious that the memorization parameter compelxity Np is the minimum number of parameters required to memorize any dataset sampled i.i.d. from D. ND is mainly determined by the characteristic of E D(n, c), so ND may be related to n and It an interesting problem to estimate ND.
5 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 consequence, show that the commonly used memorization networks with fixed width is not generalizable.
First, we show that networks with tixed 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 's power, making it unable to achieve good generalization for specific distributions, as shown in the following theorem.
Theorem 5.1. Let w. E Z.4 and C be memorization algorithm such that L(Drr) has width not more than w for all D.r. Then, there exist an integer >> w, E TR and distribution DD E D(n, e) such that, for any Der DN, it holds Ap (C(,,))) < 0.51.

---

Proof Idea. As shown in 440 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 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 Theorem 3.1 further shows that large width is necessary condition for generalizabity.
Note that Theorem 5.1 is for 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.
Definition 5.2. The distribution D is said to have density т, if if PD E A)/V(A) S for any closed set A C [0, 1]", where V (A) is the volume of A.
Loosely speaking, the density of a distribution is the upper bound of the density function.
Theorem 5.3. For any n Z4,r,c E R4, if distribution D E D(n, e) has density r, then for any N E E, and Dir ~ DD,, there exists memorization network F for Drr such that para(F) O(n + VN (NIn(Nnr/o and AF(F) 0.51.
Proof Idea. We refer to the classical memorization construction idea [55]. The main body includes three parts. Firstly, compress the data in Dirr 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 control the classification results of points that do not appear in the datasel Dtr, so that the memorization network will give the wrong label to the points that are not in Der as much as possible to reduce its accuracy. The general approach is the following: (1) Find a set in which each point is nol presented in Der 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 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
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) OVVN), 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 with optimal number of parameters, the sample complexity is infinite, contrary to the uniform generalization bound for feedforward neural networks [3] 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 (4 and more details are shown in Appendix B
6 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 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.
7

---

6.1 Lower bound for sample complexity of memorization algorithm
Roughly speaking, the sample complexity of 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 ND. which has been defined in Theorem 4.3
Theorem 6.1. There exists memorization algorithm L which satisfies that for any 24, No
R+, e, 8 E (0, if E D(n,c) c) and N Z (ND) 2e - 6), it holds
PD.,NDN (A(C(D()) 2 <) 1
where v is an absolute constant which does not depend on N,,,c,,,7
Proof Idea. The mainly idea is that: for dataset Drr C C0, x (-1,1} with [Dtrl N, we can find some distributions D, D2..... such that if Dis ~ (Di)², then with a positive probability, it hold Drr -Dy- In addition, each distribution has certain degree of difference from the others. is easy to see that ((Drr) ) is a fixed network for a given f. so L(D(r) cannot fü all DD well because some degree. So, a memorization algorithm L satisfies the condition in the theorem, we try to construct some distributions (i= and use the above idea to prove that L cannot fit one of the distributions in {D:}i=1 and obtain contradictions. The proof of the theorem given in Appendix F
Dr are different
Remark 6.2. In general, the sample complexity depends on the data distribution, hypothesis space. learning algorithms, and e, 8. Since ND is related to n and the lower bound in Theorem 6. also depends on n and Here, the hypothesis space the memorization networks, which is implicitly reflected in No.
Remark 6.3. Roughly strictly, if we consider interpolation learning, that is, training network under the constraint of memorizing the dataset, then Theorem 6. also provides lower bound for the sample complexity.
This theorem shows that if we want memorization algorithms to have guaranteed generalization, then about ((N3)) samples are required. As a consequence, we show that, for some data distribution, it need an exponential number of samples achieve generalization. The proof is also in Appendix [
Corollary 6.4. For any memorization algorithm L and any å E 10, there exist E C 0 and a distribution D D(n,c), such that in order for C to have generalizability on DD that is for all N No, there is
PD.. (A(C(D()) ) - 21-6
No must be more than v(2 2 r (11 2 - 8)/n²), where u is an absolute constant not depending on N, n, C, e,
6.2 Exact sample complexity of memorization algorithm with No parameters
In Theorem 6.1 shown that {(NN)) samples are necessary for generalizability of memorization. The following theorem shows that there exists memorization algorithm that can reach generalization with ((N3) samples.
Theorem 6.5. For all memorization algorithms L. satisfies that L(Der) has at most ND parameters, with probability I for D,, ~ DNN, we have
(1) For any e E &,,,d E (0, 1),1), n 24, DED, and N vN In(No/((e6)) then PDINDN (A(C(D.,)) 21
where is an absolute constant which does not depend on N,n,c,e,d
(2) P NP, then all such algorithms are not efficient.
Proof Idea. For the proof of (1), we need to use the ND to calculate the VC- VC-dimension (6), and take such a dimension in the generalization bound theorem [44] to obtain the result. For the proof (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 an NPC problem. The proof of the theorem is given in Appendix G
8

---

Definition 6.6. Let ip be Boolean formula and & the formula obtained from yp by negating each variable. The Boolean formula yp is called reversible if either both yp and y 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 satisfiabilityy problem for CNF formulae with six variables per clause. In 4 it is shown that the reversible 6-SAT is NPC.
that N = ((N)) is the necessary and sufficient condition for the memorization algorithm to generalize, and hence O(N is the exact sample complexity for memorization algorithms with ND parameters over the distribution D(n, c).
Combining Theorems 6.1 and 6.5
Unfortunately, by (2) of Theorem 6.5 this memorization algorithm is not efficient when the memo- rization has no more than ND parameters. Furthermore, we conjecture that there exist no efficient memorization algorithms that can use O(N2) 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 generaliza- tion with (1N)) samples for all E D(n,c) c).
Remark 6.8. This result also provides certain theoretical explanation for the over-parameterization for memorization algorithms with ND parameters, the exact sample complexity O(N)) is greater than the number of parameters. Thus, the networks is under- ander-parameterized and for such a network, even if it is generalizable, it cannot be computed efficiently.
mystery 45
7 Efficient memorization algorithm with guaranteed generalization
In the preceding section, we show that there exist memorization algorithms that are generalizable when N O (NB), 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 (z,y)
D, let L(ara)
min(s.-w)>D || 2112 and B((x, v))
(2 /3.1) {= E Rm ||= =212 S [xx,,) /3.1), 1.. The nearby set S of D is subset of sample (x, y) which is in distribution 2 and satisfies: (1) for any (I,z) ~ D. a E ((z,))ss w)): (2) [S] is minimum.
Evidently, for any D E D(n, c), its nearby set is finite, as shown by Proposition 7.7 So = |S| is called the efficient memorization sample complexity of DD the meaning of which is given in Theorem L3
(..w))/.111 /311 to be the radius of B((z, v)). In fact, when 3.1 is replaced by any real number greater than 3, the following theorem is still valid.
Remark 7.2. In the above definition, we use L(a,))33
Theorem 7.3. There exists an efficient memorization algorithm such that for any E e, Sn 1n(Sp/8) then
(0, 1). n Z.. and D E D(n,c)) c), N Z
P PD..NDN (A(C(D)))) 2 21-1)21-1
Moreover, for any Der ~ DN, L(D.r) has at most O(N2n) parameters.
Proof Idea. For a given dataset Drr C 10, x 1-1,1), we use the following two steps to construct a memorization network.
Step 1. Find suitable convex sets {C.} in [0, 1Jm such that each sample in Dev in at least one of these convex sets. Furthermore, if x, E C2 and (x, yw), (z, Mz) E Dir, then Yz. and define
((C))) = Vu-
Step 2. Construct a network F such that for any X E Co Sgn(F(x)) = yC.)) This network must be memorization of Dtr. because each sample in Drr is in at least of {C,). Hence, if C2 and (c. yx) E Dtr, then Sgn(F(x)) = y(C,) = yz- The proof of the theorem is given in Appendix H Remark 7.4. Theorem 7.3 shows that there exists efficient and generalizable memorization algorithm when N O(S)). Thus, Sp is an intrinsic complexity measure of D whether it is

---

easy to learn and generalize. By Theorem 6.1 Sp 2 N for some D, but for some "nice" D, Sp could be small. It an interesting problem to estimate Sp.
Remark 7.5. Theorem 7.3 uses O(N2n) parameters, highlight the importance of over-
parameterization [4 7 4.
Interestingly. Remark 6.8 shows that if the network has O(VN) parame- ters, 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 ! Unfortunately, for commonly used datasets such as CIFAR-IO, 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 polynomial-time memorization algorithm that can achieve generalization when the training dataset contains (Sp) samples. In comparison of
theoretical works, training networks is NP-hard for small networks [32 51
15
3
42
23
21
and the guarantee of generalization needs strong assumptions the loss function 58.
46
60
Finally, we give an estimate for Sp. From Corollary 6.4 and Theorem 7.3 for SD.
we obtain lower bound
Corollary 7.6. There exists a distribution D E D(n, c) such that Sp In /0) 2 57 0 2 (
We will give upper bound for Sp in the following proposition, and the proof is given in Appendix clear that Sp is finite.
H.T From the proposition,
Proposition 7.7. For any D E D(n, c). we have Sp I ([6.2n/c) + 1)".
Remark 7.8. The above proposition gives an upper bound of Sp when E D(n, c), and this does not mean that SD is exponential for all 'D E D(n, c). Determining the conditions under which Sp is small for given D is a compelling problem.
8 Conclusion
Memorization originally focuses on theoretical study of the expressive power of neural networks. Recently, memorization believed to be a key reason why over wer-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 construct memorization networks for dataset sampled i.i.d from data distri- bution, which have the optimal number of parameters, and then show that some commonly used memorization networks do not have generalizability even if the dataset drawn i.i.d. from data distribution and contains a sufficiently large number of samples. Furthermore, we establish the sample complexity of memorization algorithm in several situations, including lower bound for the memorization sample complexity and an upper bound for the efficient memorization sample complexity.
Limitation and future work Two numerical complexities Np and Sp 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. ND is also a lower bound for the sample complexity of memorization algorithms. However, No and Sp. which is an interesting future work. Conjecture 6.. tries to give a lower bound for the efficient memorization sample complexity. More generally, can write No and Sp as functions of the probability density function p(z. y) of DD
do not know how to compute
Corollary 6.4 indicates that even for the "nice" data distributions ((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 ED is an important problem.
Finally, finding a memorization algorithm that can achieve SOTA results in solving practical image classification problems is also challenge problem.
10

---

Acknowledgments
This work is supported by CAS Project for Young Scientists in Basic Research, Grant No. YSBR-040, ISCAS New Cultivation Project ISCAS-PYPX-20221,, and ISCAS Basic Research ISCAS-JCZD- 202302. This work also supported by NKRDP grant No. No.20188 NSFC grant No. 1228801... The authors thank anonymous referees for their valuable comments.
grant GJ0090202, and
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-318, 2016.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via wver-parameterization. In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 242-252. PMLR, 09-15 Jun 2019.
[3] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint arXiv:1611.00 1.0.149,,,14,,, 2016.
[4] Devansh Arpit, Stanislaw Jastrzebski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj. Asja Fischer, Aaron Courville, Yoshua Bengio, et al. closer look at memorization in deep networks. In International conference machine learning. pages 233-242. PMLR, 2017.
[5] Peter Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In M. Kearns, S. Solla, and D. Cohn, editors, Advances in Neural Information Processing Systems, volume 11. MIT Press, 1998.
[6] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, (0(1):2285-23011 2019.
[7] Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
[8] Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33:4381-4399 2020.
[9] Eric B. Baum. On the capabilities of multilayer perceptrons. Journal of Complexity 4(3): 193-215, 1988.
[10] Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning practice and the classical bias-variance trade-off. Proceedings the National Academy of Sciences, 116(32)15849-11588 2019.
[11] Sebastien Bubeck, Ronen Eldan, Yin Tat Lee, and Dan Mikulincer. Network size and size of the weights in memorization with two-layers neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4977-4988 Curran Associates, Inc., 2020.
[12] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. Journal of Machine Learning Research, 22(129):1-30, 2021.
[13] Amit Daniely. Neural networks learning and memorization with (almost) no over- parameterization. H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 9007-9016. Curran Associates, Inc., 2020.
[14] Amit Daniely. Memorizing gaussians with no over-paramettrizzion via gradient decent on neural networks. arXiv preprint arXiv:2003.12893 2020.

---

[15] Bhaskar DasGupta, Hava T. Siegelmann, and Eduardo Sontag. On learnability question associated to neural networks with continuous activations (extended abstract). In Proceedings of the Seventh Annual Conference on Computational Learning Theory, COLT "94, page 47-56, New York, NY, USA, 1994. Association for Computing Machinery.
[16] Santanu S. Dey, Guanyi Wang, and Yao Xie. Approximation algorithms for training one-node relu neural networks. IEEE Transactions on Signal Processing, 68:6696-6706, 2020.
[17] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai Gradient descent finds global minima of deep neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 1675-1685. PMLR, 09-15 Jun 2019.
[18) Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations, 2019.
[19] Vitaly Feldman. Does learning require memorization? a short tale about a long tail. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, STOC 2020, page 954-959, New York, NY, USA, 2020. Association for Computing Machinery.
[20] Vitaly Feldman and Chiyuan Zhang. What neural networks memorize and why: Discovering the long tail via influence estimation. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 2881 1-911. Curran Associates, Inc., 2020.
[21] Vincent Froese, Christoph Hertrich, and Rolf Niedermeier. The computational complexity of relu network training parameterized by data dimensionality. Journal of Artificial Intelligence Research, 74:1775-1790 1790, 2022.
[22] Prachi Garg, Shivang Agarwal, Alexis Lechervy, and Frederic Jurie. Mem- orization and generalization in deep cnns using soft gating mechanisms. https://rnahhigrgg3..iiiii wwt.ghiwww.oooooppeeeoooroo.oee. CREC.p 2019.
[23] Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight hardness results for training 2 relu networks. arXiv preprint arXiv:2011.13550, 2020.
[24] Paul Goldberg and Mark Jerrum. Bounding the appiik-chervonenkii dimension of concept classes parameterized by real numbers. Proceedings of the sixth annual conference on Computational learning theory, pages 361-369, 1993.
[25] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. fize-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299, PMLR, 06-09 Jul 2018.
[26] Moritz Hardt and Tengyu Ma. 161i 1.04311 2016
Identity matters in deep learning.
arXiv preprint
[27] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pages 1225-1234. PMLR, 2016.
[28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for im- age recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
[29] Guang-Bin Huang. Learning capability and storage capacity of two-hidden-layer feedforward networks. IEEE Transactions on Neural Networks, 14(2):274-811, 2003.
[30] Guang-Bin Huang and H.A. Babri. Upper bounds on the number of hidden neurons in feedfor- ward networks with arbitrary bounded nonlinear activation functions. IEFE Transactions on Neural Networks, 0()):224-229 Jan 1998.
12

---

[31] Shih-Chi Huang and Yin-Fang Huang. Bounds on number of hidden neurons of multilayer perceptrons in classification and recognition. In Proceedings of 1990 IEEE International Symposium on Circuity and Systems (ISCAS), pages 2500-2503, 1990.
[32] Adam R. Klivans and Alexander A. Sherstov. Cryptographic hardness for learning intersections of halfspaces. Journal of Computer and System Sciences, 75(1):2-12, 2009.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report TR-2009, 2009.
[34] Uiaa Kuzhorskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. PMLR, 2018.
[35] Binghui Li, Jikai Jin, Han Zhong, John E Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. arXiv preprint arXiv:2205. 13863, 2022.
[36] Hongkang Li, Meng Wang. Sijia Liu, and Pin- Yu Chen. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. arXiv preprint arXiv:2302.06015, 2023.
[37] Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[38] Tengyuan Liang and Benjamin Recht, Interpolating classifiers make few mistakes. Journal of Machine Learning Research, 24:1-27, 2023.
[39] Roi Livni, Shai Shalev-Shwartz, and Ohad Shamir. On the computational efficiency of training neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[40] Zhou Lu, Hongming Pu, Feicheng Wang, Zhiqiang Hu, and Liwei Wang. The expressive power of neural networks: A view from the width. In I. Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[41] Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over- parametrized learning. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3334-4334. PMLR, 10-15 Jul 2018.
[42] Pasin Manurangsi and Daniel Reichman. The computational complexity of training relu (s). arXiv preprint 1rXivv1810.04200 2018
[43] Nimrod Megiddo. On the complexity of polyhedral separability. Discrete & Computational Geometry, 3:325-331 337,, 1988.
[44] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[45] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021 (12)::12440 2021.
[46] Behnam Neyshabur, Srinadh Bhojanapalli. David McAllester, and Nati Srebro. Exploring generalization in deep learning. Advances neural information processing systems, 30, 2017.
[47] Quynh Nguyen and Matthias Hein. Optimization landscape and expressivity of deep enns. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Muchine Learning Research, pages 3730-3739. PMLR, 10-15 Jul 2018
13

---

[48] Sejun Park, Chulhee Yun, Jacho Lee, and Jinwoo Shin. Minimum width for universal approxi- mation. arXiv preprint Stti:20006008859 2020.
[49] Sejun Park, Jacho Lee, Chulhee Yun, and Jinwoo Shin, Provable memorization via deep neural networks using sub-linear parameters. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3627-3661. PMLR, 15-19 Aug 2021.
[50] Michael A. Sartori and Panos Antsaklis. A simple method to derive bounds on the size and to train multilayer neural networks. IEEE Transactions on Neural Networks, 2(4):467-471, 1991.
[51] Shalev-Shwartz Shai and Ben-David Shai. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[52] Rahul Sharma, Aditya V. Nori, and Alex Aiken. Interpolants as classifiers. In CAV 2012. LNCS 7358, pages 71-87, 2012.
[53] Ryan Theisen, Jason M. Klusowski, and Michael W. Mahoney, Good classifiers are abundant in the interpolating regime. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, pages 15532-15543, 2021.
[54] Vladimir N. Vapnik. An overview of statistical learning theory. IEEE Transactions On Neural Networks, 10(5):888999) 999, 1999.
[55] Gal Vardi, Gilad Yehudai, and Ohad Shamir. On the optimal memorization power of relu neural networks. arXiv preprint 1rXiv:2110.031853 2021.
[56] Roman Vershynin. Memory capacity of neural networks with threshold and rectified linear unit activations. Siam Math. Data Sci., 1004 2020.
[57] Martin J Wainwright. Iligh-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge university press, 2019.
[58] Yihan Wang, Shuang Liu, and Xiao-Shan Gao. Data-dependent stability analysis of adversarial training. arXiv preprint arXiv:2401.03156 2021.
[59] Zhen Wang, Lan Bai, and Yuanhai Shao. Generalization memorization machine with zero empirical risk for classification. Pattern Recognition, 152:1, 2024.
[60] Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi-Quan Luo. Stability analysis and generalization bounds of adversarial training. Advances in Neural Information Processing Systems, 35:15446-15559 2022.
[61] Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523-266 -25335, 2021.
[62] Lijia Yu, Xiao-Shan Gao, and Lijun Zhang. Optimal robust memorization with relu neural networks. In International Conference Learning Representations, 2024.
[63] Lijia Yu, Shuang Liu, Yibo Miao, Xiao-Shan Gao, and Lijun Zhang. Generalization bound and new algorithm for clean-label backdoor attack. In Proceedings of the 41st International Conference on Machine Learning, pages 235:57559-57596 2024.
[64] Chulhee Yun, Suvrit Sra, and Ali Jadbabaie. Small relu networks are powerful memorizers: a tight analysis of memorization capacity. In Advances in Neural Information Processing Systems, volume 32, pages 15532-15544 2019.
[65] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3): 107-115, 2021.
[66] Lijia Zhou, Frederic Koehler, Danica J. Sutherland, and Nathan Srebro. Optimistic rates: A unifying theory for interpolation learning and regularization in linear regression. ACM/JMS Journal of Data Science, 1(2):1-51, 2024.
[67] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterrized deep relu networks. arXiv preprint arXiv:1811.08888, 2018.
14

---

A Proof of Proposition 3.3
Using the following steps, we construct a distribution in [0, x f-1,1). We use (x, ~ D to
mean that
(1) Randomly select a number in {-1,1} as the label y-
(2) If we get as the label, then randomly select an irrational number in [0, 1] as samples o;; if we get
-1 the label, then randomly select rational number in [0, 1] samples x.
Then Proposition 3.3 follows from the following lemma.
Lemma A.1. For any neural network F, we have (D(F) & 0.5.
Proof. Let be a network. Firstly, we show that F can be written as
M
F
Σ
[xxx)((x E At),
(1)
where L, are linear functions. [(x) if is or [(x) 0. In addition, A, is an interval and Aj n A; = 0 when j & and [x) A,) is a non-negative or non-positive function for any i [M].
It is obvious that the network is a locally linear function with finite number of linear regions, so we can write
F Σ [x E
(2)
where L' are linear functions, Ai is an interval and AG n A = 9 when j + i.
Consider that [(x E A) = L(()[(< E L,(x) > 0) L((x)((r e A/, < 0).
and T( E A (x) 0) is non-negative function, fx 14,1(()) 0) is an interval
which is disjoint with {a E A,, (x) < 0}. Similarly as [[xx)(( E 41, < 0), so we use
[=) E AA) in 2 instead of (x) A [((x) 0)+ [(x))((x Ar (x)) < 0). Then
we get the equation
By equation
we have that
P(na))D(Sggn F (x)) y)
Play)>D(S Sgn EM [(x At)) =1)
(3)
= Σ P (S))
E Ai)) = =,, 5 E A.) Cgg
(S)n(L(()II(re e A.)) =y/z E A.) A.).
The second equation uses A, nAj 00
For convenience, we use æ E R, to mean that æ is an irrational number and & E2 to mean that rational number. Then, if [xxx)(( A,) is a non-negative function, then we have P (Stn)))((S(((()))) that
A:)) = y/ E A,) S ((a E R E Ai). Moreover, we have
P(a.))D((2 (z E R E Ar) (OER
((E.))
0.50 D.
P(os))D(PEA)
0.50 D P P(o (1 (oE Po. Proas- [eajs
By (2) in the definition of D, we have P(ww)n(( A/e E R2) ((ay))D(E E A,po & R.). Substituting this in equation (3), we have that (S E A,)) y/ı A,) S
Pe (( E Rg Ai) A (20ps 0.5. Proof is similar when (x A,) is non-positive function.
15

---

Using this in equation
2 we have that
P (( P =)
(eea))- A.)) u|æ (a) E A.)
E 0.51 (aw)~DD E A,) S 0.5.
The lemma is proved.
B Proof of Theorem 4.1
For the proof of this theorem, mainly follow the constructive approach of the memorization network in [55]. Our proof is divided into four parts.
B.1 Data Compression
The general method of constructing memorization networks will compress the data into low dimensional space first, and we follow this approach. We are trying compress the data into 1 --dimensional space, and we require the compressed data to meet some conditions, as shown in the following lemma.
Lemma B.1. Let DD be a distribution in [0, 1] x (-1,1} with separation bound c and D,,- ~ DN such that
Then, there exist w IR" and
(I): O /e) 2 wx + b > for all [0, 1]";
(2): weF wz 2 4 for all (r, 1), (z, -1) E Drr.
To prove this lemma, we need the following lemma. Lemma B.2. For any IR" and T 2 1, let E R be uniformly randomly sampled from the hypersphere Su-1, Then we have (u, u) ||l|
This is Lemma 13 in 49 Now, prove the lemma B.1
Proof. Let co = min ()....)))) || 21/2. Then, we prove the following result:
Result R1: Let R" be uniformly randomly sampled from the hypersphere Sm-1, then there are ANo nst V(x, 1), (2, D.r) 0.5.
(([(u, (z 2))
By lemma B.2 and take T 4N², for any x, which satisfies (z,, -)), (z, 1) E Der we have that: let u R" be uniformly randomly sampled from the hypersphere Sm-1, then there are
P(((u, (x 2)) < 4N
2Zz. using || - 2|12 2 cy here. So, it holds
P([su, (a 2))1 2 4No V no V(o, 11. (2, D.r)
()..1)).e..)EE. P([(u, (x 2))1 < AM
AN
0.5
We proved Result RI.
In practice, to find such a vector, we can randomly select vector in hypersphere Sm-1, and verify nu V(x, -1), (z, 1) E Dtr. Verifying such a fact needs poly(B(((r)) times. If such is not what want, randomly select vector and verify again.
that satisfies (u, (x - =)> IN
In each selection, with probability 0.5, we can get a vector we need, so with 1/c times the selections, we can get vector we need with probability -
Construct w. and verify their rationality
By the above result, we have that: there exists a u E R such that ||w/|2 = 1 and (u, (I - 2))1 2
Co
V(z, 1), (z, 1) E Dtr. and we can find such a a in (D))) In(1/e)) times.
INT
16

---

Now, let 16yaN2 8o (I): We have O(nN2/c) 2 wx + bb 1 for all x E [0, 1]". Firstly, because is defined in [0. 1 x { [-1,1], so it holds | S vn for any (z, v) E Drr, and consequently wz + b 2 b || 1.
and b || 2/ + 1, then show that and are what want:
On the other hand, | - || / - 0 nN2 ) so wr+bb wx/+b s O(nN2/co) S O(nN2//)
(2): We have |wo =)1 2 4 for all (z, 1), (z, -1) Der.
is easy to see that |w( =)1 2
10 u(x - 2) 16/aN²
|u(x =){. Because |u(a: 2) 2
6o
4yANT so |u(2 2)] 16/nN² |u( 2) 2
16ynN2
= 4.
co
4v
By Definition 3.1 we know that co
So, w and b are what we want. The lemma is proved.
B.2 Data Projection
The purpose of this part is to map the compressed data into appropriate values.
Let IR" and b R be given and Drr y-)) Without losing generality, assume that
0 < ux, < wz
In this section, we show that, after compressing the data into I-dimension, we can use a network F to map wx, + b to "in'"""" where { [
E IR+ are given values. This network has O(VN)
parameters and width 4, shown in the following lemma.
[
Lemma B.3. Let { CR {uzTz= width 4 and depth OVVN) (at most O O(VN) parameters) can be obtained such that F(x:) =11
C CR+. Assume that D; Ii41. Then a network JF with
for all i E [N].
Proof. Let Fi) be the i-th hidden layer of network JF, (Fi), be the j-th nodes of i-th hidden layer of network F.
Let q: 2+41 I; and f(i) argmax j[l] (b///)//i] i}. Consider the following network F; The 2i + hidden layer has width 4, and each node is:
(z2it)) (x) = Relu( (alu((()))2())) (#1(3)+1) + (4)(s)33)
(2()))2(1)) = Relu(( - (x1(4)1)) + v0(s)/3);
(1 Relu( (F²2)) (x));
(J21-1) )x()) = *Relu( (F21) (= (x)))
For the case 0, let (F²) = x and (FI) Un-
The (2i + 2)-th hidden layer is:
(F2442) RRlu (F2it((Ftt)))(2)) )s(x) U/+1 - U ((F2it)) (F22+1)2(x)))
///0/
(F21+2) 22(x) Relu( Relu((F2tt) (F2i+1) (2(+))(44))) (xx))
The output is F(z) = (JZNN//V)) (x).
This network has width 4 and ((vN) N) hidden layers. We can verify that such a network is what we want follows.
Firstly, is easy to see that (F2(+2)2(x)) Relu((F2(+)))(tz) = Relu((F2)))zz)))
Relu ( ))())) ... Relu( (elu((F)) (z)) = Relu(z) =
17

---

Then, for - (FF2+ (1)) )2(x))
% - (Relu(x- xx())+ + 22a) Relu(z-
///0/3
4/0/3
+((++11 + +0(0 /3), easy to verify that, when 2 S T((a). is 0; when x 2 I1(+1), it 1/+11 - U/.
By the above two results, we have that (F2++2) (x) = Relu Relu(( )x(2) + 20033 ( (x)
22())) = Relu(( (zx)) when x S Bs(s and (F2i+2) ) = Relu ( )a(()))))))))) +
" ((F2))))(
(F2i+)) (2())) Relu( (F21 ) (2) 21+1 U; when x 2 2(()++1.
So, we have that, t( ( S - t(i,, there are (F²) (F2)1(2)) (22)) ) = vo, ) = 01 to Uo = U1. ((3)) = 02 - 01 + t = U2
(F2i) (zz) (zz) = U/ 1;-1 + 4/-1 = 0/: and F(z;) =
(F2INIVN)) -
(2rg)
(J22) (x(() = Uz.
So, by the definition of t(i), we have that F(x,) = 1 such F is what we what and the lemma is proved.
B.3 Label determination
The purpose of this part is to use the values to which the compressed data are mapped, mentioned in the above section, determine the labels of the data.
Assuming 2; is compressed to C where C2 2 is given in section B.1 Value it in section B.2 is designed as: v.- = [
((+1)) where we treat [cy] as a w digit number for all j (w is a given number). If there exist not enough digits for some ey. we fill in 0 before it, and we use ab to denote the integer by putting a and b together.
First, prove lemma.
Lemma B.4. For given N, there exists network f R - IR2 with width 4 and at most ((w)
parameters such that, for any w digit number a; > 0, we have fla1a2..... aN) = (a1, ........))
Proof. Firstly, we show that, for any a b 0, there exists a network Fab(z) R+ E
with depth 2 and width 3, such that (x) = r when x E [0,a], and Fa,((z) = x when x E [a + b, 2a].
We just need to take Fa.(x)) = Relu(x) - a/bRclu(x - a) + a a/bRcll - +a+ + b)). It is easy to verify that this is what we want.
Now, let y E N+ satisfy < 10 1 an 24+1 > 10 and p < 10WN. We consider the following network:
== F o F2t.p ... F 1 o F2
and show that, F(a102 ... aN 100 02 ... .0....N// 1N/10((N-1)
Firstly, we have F29, [1102... ... aN/ 10 (N-1)) 1) (q)a2 ... aN. 10 where (1(9) = a1 if a1a2... aN/ (N-) < 29 and a (q) ai - 29 if alag. ... ....N (N1 29 + p. Just by the definition of q, we know that there must be ai02... uN/ 110 of p. one of the following two inequalities is true:
28+1 Further by the definition
0102 ... AN/ M (N1) 29 or 01 0142.... .. aN an..a/111000 (0w/100(N11) > 29 + p.
So using the definition of F2r.pr we get the desired result.
Similarly as before, for h: = q 1.9 2,..., O. we have Fz (1 + aw00....////0// = where a1 (k) ai (k: + 1) if a (k + l)a2... (llag...an/lll aN/10w(N-1) s 2* and aj (k) = 0, (k- + 1) 2* if a1 (k- + 1)02 ... ...
a (k) ... aN/ 111 (ax
a (1 -1) 2* +p.
Then we have the following result: a1 (k) < 2 for any k: = 1, 4. By the definition, it is easy to see that d1 < 24+1, If 01 < 29, then ag (g) < (1 < 29; if a, 2 29, then T1 ... .uN (10 > 2 + p, so 01 (q) = 01 - 2 < 2 2 = 29. Thus (1(4) < 29, When (t < 2' for a t e lg]. similar before, we have a1 (t- 1) 2t And = q is proved,
get the desired result.
It is easy to see that, 01 (k) are non negative integers, so there must be F F(a102.... ON (N-1) a (0)a2... ... ...........// (N-) ā2 ag... a 1000(111NN111 by (0) < 20 1, which implics a (0) 0.
18

---

Now we construct network F& as follows:
Fb(()) Fbi (1r such that:
Fbr(2): R - R22 and Foi( = (F(x/10m(N-1)), x)) where x is defined as before.
Fiz(x): R2 + R2 and (62((11,x22) = (z2/100(NN1) - 21,31 10w(N-1)).
Now we verify that Fb is what we want.
By the structure of F. Fi has width 4 and depth ((w), so there are at most (w) parameters.
It is easy to see that Poi (a1d2. ... uN) (a2 aN/ 10 01 ... aN). Then by the definition of (1), we have (a( = (01, 02 uN), this is what we want. The lemma is proved.
By the preceding lemma, we have the following lemma.
Lemma B.5. There is network TR2 R with at most (NNw) parameters and width and for N == where aj is a w digit number and aj 2 1, which satisfies f(x, 01 ..ay) > 0.1 if
any {a,
xx Okl for some k [N], and f(z 0102..12..... aN) 0 okl Z 1.1 all [N].
Proof. The proof idea is as follows: First, follows: Using lemma B. we calculate aj and ag... ... aN and then calculate xx a1l.
and 01d2.... aN to judge if |r a1l 1 as
If [x [1l= < I, then we let the network output a positive number; if Jæ a1l 2 1, then calculate 02 ... UN, and use and 02 a, to repeat the above process until all Ir a.l have been calculated.
The specific structure of the network as follows:
step 1: Firstly, for a given N, we introduce sub-network Sa RR2 _ RR2. which satisfies (J)) a1u2.....00. uN) > 0.1 I a1 < 1, and ʃs (ar, a102....00..... 0N) (Ja)((r, d12 ... (N) T22... a.. And Sa has O(w) parameters and width 5.
Jar ail 2 1.1, and
The first part of fa network has width 5. The second part of fa is to calculate J ail and keep 0g ... aN by using |x| = Relu(z) + Relu(-2) which has width The output of fa is Relu(1.1 |x a1 l). Easy to check that this is what we want.
calculate a₁ and 02 ... aN by lemma B.4 We also need keep x. and the
step 2: Now build the f mentioned in the lemma. Let f = g o JN o IN-1 f1. For each i E [N], we will let the input of fa which also the output of f(-1 when > 1 be the form (z, (0,0,0,1111 CN, q:), where @1 O. The detail is follows:
For E [N]. in fo, construct fa a,a;+1 aN) at first, and then let q+1 = qi (f=) 0,0;41 ... aN), to keep 4 in each layer, where need one more width than fs. Then, output (z, 0:410:42 ON, 4++1). which is also the input of (i + 1)-th part.
The output of f is gN+11 that is, g(z 0, 0N4++) = 9N+1- Now, we show that, f is what we want.
(1): f' has most ONNw) parameters and width 6, which is obvious, because each part fú. Si has (ww) parameters by lemma B.4 and / has at most parts, so we get the result.
(2): f(z, ajda....aap
0.1 if
axl < 1 for some k.
This is because when x axl
1, the k-th part will make @k+1 qu + fa agaR+1 ... aN 0.1.
because (z.) 0x44+1 ... aN) > 0.1 as said in step 1. Since 9j+1 lj + (fs)1 2 qj. we have
f(x 0102 ... aN) NN+1 2 + 0.1.
(3): fz, aid.......... aN) = 0 if [x:
0x 2 1.1 for all k.
This is because when ax > 1.1, the k-th part will make gh+1 = Qk + 0144+1 ... 0x Tk. because [a 0g48+1....00
as said step 1. Since [a(r, ag0 ...an) for all k. we
have fz, did2...aa)) QN+1 ON fz TN) QN
go = 0.
19

---

B.4 The proof of Theorem 4.1
Now, we will prove Theorem As we mentioned before, three steps are required: data compression, data projection, and label determination. The proof is as follows.
Proof. Assume that Dr, = {- without loss of generality, let 2, o zy. Now, we show that there is a memorization network J of Der with ((vN) parameters.
Part One, data compression.
The part is to compress the data in Drr into R. Let w, satisfy (1) and (2) in lemma B.1 Then, the first part of F is fi (x) Relu(wx + b).
Part two, data projection.
Let C = fi (2;), without loss of generality, we assume a S C++1 and y1 = We define df as: = if has label 1; otherwise c/ C1.
Let t(t) argmax [[/vN]] i} and ey (4(a-1)42l (( 1)+2 ... Gay)
In this part, the second part of F(z), named fz(x): R², need to satisfy f2(c;) (v) (1))
for any i E [N].
By lemma B.3 a network with O(vN) parameters and width 4 is enough to map to "[ai) and
for keeping the input, and node is needed each layer. So fa just need O( parameters and width 5.
Part Three, Label determination.
In this part, we will use the U mentioned in part two output the label of input. The third part, nameed as fs(U, c), should satisfy that:
For f3(Uk, c), where Uj = ( ((a))) is defined above, if |c dgl < 1 for
some y [1(k 1) 10++1 +1,(())), then fa(vx, c) >> 0.1; and fa(v,, c) if |c cg 1.1 for all
q E [t(k + 1, ([))).
Because the number of digits for & is ((I(nNN/c) by (1) lemma B.1 and lemma B.5 that such network need O(VN (n(n/cc) parameters.
we know
Construction of F and verify it:
Let F(x) (a([2(Ji (x))) 0.05. We show that F is what want.
(I): By parts two, three, is easy to see that F has most O(vN In(Nn/c)) parameters and width
(2): F(z) is memorization of Drr- For any (I,, ys) E Der, consider two sub-cases:
(1.1: if yı 1): Using the symbols in Part Two, [2(Ji (2::)) will output (1 (i Since
= c, because y/ 1, by part three, have fa(f2(fi 0.05 > 0.1 0.05 0.
(1.2 if 3 - fi (f [f 2 = So. by part three, we have (s(f2(())z)))
-1): By (2) in lemma B.I for 1) E Dtr. we know that (2, [f) Z
0.05 0.
The Running Time: In Part One, takes voly(B(Der)) In times to find such w and with probability 1 said in lemma B.I In other parts, the parameters are calculated deterministically. We proved the theorem.
C Proof of Theorem
Proof. It suffices to show that there exists a memorization algorithm L, such that if E D(n, c) and Dir D. then the network T.(D.r) has a constant number of parameters (independent of N). The construction has four steps.
20

---

Step One: Calculate the min( (s..).))) || 2||2, name it as co-
Step Two: There is Drr Drr, such that:
(cl): For any (z, Mn), (z) E Da, it holds ||a 2||2 > co/3:
(c2): For any (z, Vo) E Drr, it holds ||e =112 S co/3 for some (z) ) E Dz.
It is obvious that such D3 exists.
Step Three: We prove that [D,] - (1+2ca/3))
Cr(oo/3)= where C₂ is the volume of unit ball in R". Let Q C,lo/3yr consider that co 2 c. there are [D.l S Q.
(1+2e/3)*
Let (2(x,r) = {z ||| 2112 $ rr, and ((A) the volume of A.
Due to D3 C Der C [0. x [-,,1]. so (Z B2(x, c0/3) E [-co/3, 1.co/111+ co/3|". By condition (cl), we have (2, co/3) n (2, c//3) = 0 for any (I, Ve), Us) E Da. so we have
EOEDED (( ev/3)) s (1+ 2co/3)", which means [D, S (ca/3a)" < Q.
(1+2c0/3)"
Step Four: There is robust memorization network 662] with at most O(Qn) parameters for Ds with robust radius ca/3 and this memorization network is a memorization of Dir-
By condition (cl). there is a robust memorization network Fim with (([Da[n) parameters for D with radius co/3 662] By step three, have [Pa] I Q, so that such a network has at most ((Qn) parameters.
By condition (c2), for any (1) E Drr, there a (2, yz) E D3 satisfying ||2~2||2 S co/3. Firstly, there must be Ye = because the distribution D has separation bound co. and if ya # ys then ||r -0--2p z|12 co co/3. Then, since robust memorization Frm has robust radius co/3, have (g (z)) = (gn(Fmm( (z)) y/2 = Yr. so Frm is a memorization network of Der. The theorem proved.
D Proof for Theorem 5.1
In this section, will prove that networks with small width cannot have good generalization for some distributions. For given width w, we will construct distribution on which any network with width will have poor generalization. The proof consists of the following parts.
D.1 Disadvantages of network with small width
In this section, we demonstrate that 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 Wx Wz, we have F(x) = F()).
If W is full-rank, then there exist x and satisfying Wæ: Wz. Moreover, if x and have different labels, according to lemma D.I. we have F(x) F(z), so there must be an incorrect result given between F(x) and F(z).
According to the theorem matrices dccomposition, we also have the following fact.
Lemma D.2. Let the first transition weight matrix of network F R be W. If I has width < n, then exists W1 E mR=x,, whose rows are orthogonal and unit such that Wix Wi implies
Proof. Using matrix decomposition theory. we can write W NW,. where N R and W1 E Rwx" and the rows of W1 are orthogonal to each other and unit.
Next, only need to consider W, as the first transition matrix of the network JF 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.
21

---

D.2 Some useful lemmas
In this section, we introduce some lemmas which are used in the proof in section D.3 Lemma D.3. Let Br) be the ball with radius r in RR.. For any given > 0, let c = 20/n. Then we
(()) 1-18. 8.
have V(B())
Proof. we have ViB[vI-ar) V[B(r))
= (1-e)a/2 21 - -neee- = 1-
For w E Rad and q E R², g Ei= 9,0,, where qi the i-th weight of g, w/ is the i-th row of wy. Then we have
Lemma DAA. Let W R and its rows unit and orthogonal.
(1): For any qi + Q2 E IK, we have
E R" Wx W(q W)) E" Wa W( W)) = 0.
(2): S is the unit ball R,", then UgE E R" Wx = W(q o W), E S).
(3): For any q R", fo R" Wa W(q o W), 5} is a ball in mn- with volume where Ci is the volume of the unit ball in R
-
Proof. First, we define an orthogonal coordinate system {W. in R". Let W, be the i-th row of W when i S When i >> w, let W; be unit vector orthogonal with all Wj where i.
Then for all x R", we say 34 is the i-th weight of x under such coordinate system. Then, Wx = Wz if and only Fj = Σ for i E [w].
Now, we can prove the lemma.
(I): The first weight w of qı o W under orthogonal coordinate system {W.)i= is q1 so if E f R" Wx (gi W)}, we have 6, (q1); for i E [w).
The first w weight of q2 o W under orthogonal coordinate system { is q2, so if x E far e R"
Wx = ((2 o W)}, we have T; = (42); for i E [w]. Because 91 * 2 E R", we get the result.
(2): For any E R", let g(x)) (कi, T2
Fie) E Rw, It is easy to see that ||a||| = v E
so [1g(2)) la I 1 when ||0||| S 1.
Now we verify that: for any 8 E S, we have E Ex R". Wx = W(((s) W),
Firstly, we have Ws = Σ < wi, E Sww, >= Em 3r.
Secondly, we have (g(s) o W) Σn w;; W0
syw; >= Σ; s. So Ws ((((s) W).
resulting in E {x E R² Wr W W(g(s)WW), ,r S). which implies that S =
RT. : Wx = (gg W), E S}.
(3): By the proof of (2), we know that if satisfies Σ qi for i [w], then fx E R Wx=
W(q o W)). By (1), {a E R² Wx = W(q o W}} will not intersect for different q. Therefore,
x (x E R Wx W(q W)) equals F, q for i E [w].
Since ||0||2 v _ J. 2 when & E (i R= Wx W(q W)), we have To = qi for E [w].
so En Σk J. || 1/3 ||g |8. and such n w weight is optional.
Therefore, {a E R" : Wr = W(q o W), x E 5} is a ball in Ra-w with radius / || so we
get the result.
Lemma D.5. Let r3 > T2 > ri n 2 and x < rı, then (rs
13 - ri
(r1-2)"
Proof. Let (xx (19-)""(13-00" We just need to prove f(x) > f(0) when S Sn. We calculate (11-0)=
the derivative fx) at first:
fx(x) ((a-2)) - (r2
m) (rr -x) -((s x)" (r2 2)
(r1-8)
22

---

It is easy to calculate that ((r3 z)" (r2 z)²) -n x-)=11 - (r2 - z)"-1) and
((ri z) -n(ri z)n-1 Putting this into the above equation, we have
(x) = ((x) - =>"- (r2 - 1 - x) -((r3 - x)"² - (r2 - x)"1))
Where P(x)) is a positive value about z. Since
((ra - x) --" (r2 - =>)->>(n (Ti - 2) ((rg x)" - (r2 x)")
(r3 - -0- (r3 r1) + (r2 - x) n- (r2 r1)
< 0
we have ((x)) 2 0, resulting in f(x) 2 f(0). The lemma is proved.
Lemma D.6. Let b
1. If a ba 1. Then am D < 1.
Proof. We have d" 6 bad (a b()) a 6th.
Lemma D.7. Let qb where q and a, b 0. Then min b) 2 9b.
Proof. When min b) = b, by q < 1, the result is obvious. When ma, b) by qb, the result obvious.
Lemma D.8. For any w > 0, there exist 72, T3 and n such that
(I): r3
1 ri;
(2): r R-w
0.99r
Proof. Because the equations are all homogeneous, without loss generality, we assume that ri 1. We take a 21/n 1, 3 + a = 31/n 1, and to satisfy 3 < 1.001. Let 72 + a, F3 = 1 a B. We show that this is what we want.
At first, we have r r (1 + 3)" (1 + a) 3 2 rf. We also have
(1 a + 3) < 1.001, named (k1). So we have
13
T2
(1 + a + 3)n 1) -01 + aa)"
(I+++8)" -
(1ta)=
(1+a+0)" " 1 (1+c)) -(1+a)" (by (k1))
1.01
(1+a+18)" (1+0+ ((1+-= (1-a0 (1+a)"))
001
(1+a+:8)" (1+a)" -..0))-o.00000aattt
(by (k1))
(1+a+8)) (103)""(1++))) (1+a) (14101111 0.003
1.001
1-0.003
I,001
0.99.
The lemma is proved.
D.3 Construct the distribution
In this section, we construct the distribution in Theorem 5.1
Definition D.9. Let be point in [0, 1]". 0 < r < <>2 < r3, and we define (2, () = fx E R ||x - 2112 & t}, where & E N+, 2 E R² and t 2 0.
The distribution D(n, q, r1, 72, r3) is defined as:
(1): This is distirbution on R {11,1}.
(2): point has label and only if is (y ri). A point has label if and only if it is in
BY (g.rs)) ra)/ (q. r2).
(3): The points with label -1 satisfy the uniform distribution, and let the density function be
f(z) = X V(Bg (B2
23

---

We now prove Theorem 5.1
Proof. Use the notations in Definition D.9
Now, we let rú; q. 72, u satisfy:
(c1): (g. r3) E [0, 1]":
(c2): -
(c3): r3 1-- 12 0.99r
Lemma D.S ensures that such rs. exist.
Let distribution D D(n 9, 2,,,,,, ra), where ((n, 4, ri, P2; r3) is given in Definition D.9
Now,
show that D is what we want. We prove that for any given F.r with width wo we have A < 0.51.
Firstly, we define some symbols. Using lemma D.2
let W Ig whose rows are unit and F(z).
orthogonal and satisfy that WI r = Wz implying F(x)
Then define S1,z Bi (g. r3)/ B3 (q. r2)}.
{z Wz = Wæ, E (g, and S2.5 {= WN = Wx, E
By lemma D.2 we know that, for any given æ, the points in S1,5 U S2,2 have the same output after inputting F. but the points in S1,z have label and the points in S2,5 have label -1. So F must give the wrong label to the point in S1,z or S2,x-
The proof is then divided into two parts.
Let h BY (0,r1), and x<hh = a h W E R", where is defined in section D.2 Consider that for any given h, F must give the wrong label to the point in S'L((k) or S22(h), we have that JF will give the wrong label with probability at least min (Paa.))D(x E ) P(o E (2)( So, now we only need to sum these values about h.
Part One:
For any different 1 h2 E (0, ri), have s1a()) 0 S1 0, (21) (22) 0, and Une ( Sl,(()) B% (q.rr) By (1) and (2) in lemma D.4 Proof is similar for S2,((k) Then, by the volume of Slg(k). $2z(k) calculated lemma D.4 we know that, the probability of producing
an error on distribution D is least
(o.)) min E P( E S2x(k))
ACn-w ( min - ||-|| (2) w//
(33-11112))
(r2 ||x]|2 (x-)))2-))))))) w) dd
where Cn-w is the volume of the unit ball IR" R- as mentioned in lemma D.4 Next, we will estimate the lower bound of this value
Part Two: Firstly, by lemma D.5 we know that (r) |an Byta w1/2
(r 10
w1/2
(rf -=
(n w//2 (1 (1
Then, by lemma D.6 and (c2), we know that (r3) w1/2 (r3) w1/2
1. Thus by lemma D.7
have
XC Jneny(or)) (0.)) min ( ||x|1] (m (m-w//2 (r3 (1 w)/2 (r3 -11=113) (m- w) 2d
XCn-w Juee (r min
{ (rī ||0 (m (m-w//2 w2/2
(r2 11 2012
(=1)))) w)/2
(r?
||
(n- (n-w)/2
wi/2
XCn-m (reny (0.m) muin((?
||x|
(n-1//1
w12
(r22) w/ (13) (n 2//2
(r
| (3) (n-
w)/
(7) (n (r wi/22 wi/2
2 XCn-w (r 10--)/
J2EBy (0.r)
(r7
|| (n- dx
(n -1/)
2//
(
(r)) w/7
24

---

From r3 - 2 =ri. we know that XV (1) = ((V (g. 0.5, so
(ayy))D( -1] = ( = = = 0.5, and further consider the (c3), we have
((
(ン w0/2
(13)) (2-w//2
N W
0.5
(r7)(m-w172
0.49.
The theorem proved.
E Proof of Theorem 5.3
Firstly, note that Theorem 5.3 cannot be proved by the following classic result.
Theorem E.1 (157). Ler D be any joint distribution over R" {-1,1}, Der a dataset of size N
selected i.dd from D, and (h:RR* R. + R] the hypothesis space. Then with probability at least 1 1-6,
Rad (H)
In 1/6 N
sup (R(h, D) R(h, Drt)
OOV
kEH
2
where R(h, D) is the population risk, Rh, Der) is the empirical risk, and Rady (H) is the Rader- mecher complexity of H.
Theorem E.1 is the classical conclusion about the lower bound of generalization error, and theorem and Theorem T.T are different. Firstly, Theorem E. is established the basis of probability,
5.3 and whereas Theorem
5.3 is not. Secondly, Theorem F. highlights the existence of gap between the empirical error and the generalization eгтог 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, Theorem E. cannot directly address Theorem 5.3 Lastly, Theorem E. relies on Radermacher complexity, which can be
challenging calculate, while Theorem 5.3 does not have such requirement.
3.33 we mainly follow the constructive approach memorization network in (55), but during the construction process, will also consider the accuracy of the memorization network. Our proof is divided into four parts.
For the proof of Theorem 5.3
E.1 Data Compression
The general method of constructing memorization networks compresses the data into a low dimen- sional space at first, and adopt this approach. We trying compress the data into I-dimension space. However, we require the compressed data to meet some conditions, as stated in the following lemma.
Lemma E.2. Let 'D be distribution in [0. 1 (-1,1) with separation bound e and density r, and Der ~ DDN Then, there are w E RR" and E R that satisfy:
(I): O(nNar/e 2
b > 1 for all x E 00 1]":
(2): wx wz| > foror all (x, 1), (z, 1) E D
(3): P (3
Der, ww wz < 3) < 0.01.
Proof. Since distribution D is definition on j0, 1]", we have e < and 1.
Because the density function of D is т, we have ((z,))<( E B2(2,r1) I (V <
r(2r))" 400.7 for all E R", where ri N4 It is easy to see that ri < 1 because
r r21. 1.
Then, have the following two results:
Result one: Let u In" be uniformly randomly sampled from the hypersphere 1 Then we have V(z, 1)) (z, 1) Drr) > 0.5.The proof is similar to that of lemma
(u (x - z)) Z INT
B.I
25

---

Result Two: Let u E R be uniformly randomly sampled from the hypersphere sn-1, Then (u(P(ra)=D((((
U4) E Der, (z z+)) < 800N2 < 0.01) > 0.5.
Firstly, by lemma B.2] and take = S00N2, we can get that: for any given e E R", if E R be Mella 800N
uniformly randomly sampled from the hypersphere S then P(Kuu, w) <
nス < 200.7
Thus, by such inequality, the density of D and the definition of r1, we have that:
Pu,(ns)) (1,, (xr - -0)} <
F1
80ON
Pa,(a ([u,, (xr - -w)) < 800N
F1
|| 0l12 2 m )P (a - 2 mi)
(P.)) (uu (a r}}l 800
|| 0112
< ri PP (.)))> 0112 < m)
na
Pu,())))DD (I ((u,, (x - -))1l <
| ---v|l
|| 2112 2 mı) + P (ayy) e11 < m)
800.
nm
Pu(l(u, (x (x- w)}) ||z
+ P
(xg))
w < <)
800
1 On the other hand, we have
400N + 400.2 / (200N²)
P Pa(tn))D(((u (x 10--0)) T)}1
800 PLST
2 (a (Ku,, (x--
M 0.01/N) * 0.01/N.
800
So, we have (P (x..) (Ku,, (u, (x- 800. Name this inequality as (*).
8 nm
0.01/N) < 200 (0.01/ 1/(2)
On the other hand, we have
P. (P.((..))D(((( yi) Der. Ku, (I r;)3]l 800N
8
0.01)
n=
1- (a.)) 1E (3 E Deri Ku, (x xzii S0UNE
8
> 0.01)
Then, if a u E R satisfies P ((I,)))((((T)))) vi) E Der, Ku, (x xx)) < S00NE
N 0.01, then
we have P(ax))D((u(t -;)l 80ON
0.01/N for some (ISs; Mi) E Drr-
So taking as n, in inequality (*) and using the above result, we have
Pa (P (Z.)) vi) E Der. K2, (x - r;)iil < SOUNT
8
0.01)
= (M (a. (F Ui) E Dtr, K(,, (r x3:M < SOON
2 0.01)
2 1 1 Σ (x..))DD Pu (P (an)) (x -x;) < 800 V ruT
2 0.01/N)
1 1 2N 0.5.
So we get the result. This is what we want.
Construct w. and verify their property
Consider the fact: if A(u), B(u) are two events about random variable u, and Pa (A(u) True) > 0.5, (Buu) True) > 0.5, then there is a u, which makes events A(u) and B(u) occurring simultancously. By the above fact and Results one and two, we have that there exist ||ul/2 1
and u E RRDh such that Ku, (xc 2))1 2 IN
nX V(z, -1), (2, D., and P P(a.)~ (3 Bi)
Der, (u, (I x3)1)) < 800N
0.01.
PST
Now, let w = max 2
16/
Yu and b = ||w| //wll2//n + 1, then we show that w and b are
what we want:
(I): we have O(nN2) > war + b for all x [0,
Firstly, because D is defined [0, 11ah x {-1, 1}, we have | S vn, resulting in and we + bb
b - / > 1.
26

---

On the other hand, using e S 1 and S 1, we have |war| S /wllav S 0 OON |wa]| + b S OnnN311/n// /c).
(( 5O wx + b 5
(2): We have |u( 2)1 2 4 for all (z, 1), -1) E Der.
is easy to see that |0(r 2)]
16yáN2
u(x -2) 16yWN2
|u(a -=]l. Because |u(a 2)
LyANz so 1wox - 2)1 10v#N2 |u(x 2)1 16vūN²
4/ONZ 4.
c
(3): we have PP (F E Der: |ur w2 s 3) 0.01.
Because ww(x 2)
2400/TN22
ju( 2)1 2 lu(x =)1, and consider that ((rr)))(((2,))
Drr, |u(r =)] < 800. Z
8
< 0.01, we get the result. So, and b are what we want. and the
lemma is proved.
E.2 Data Projection
The purpose of this part is to map the compressed data to appropriate values. Let w RR" and E IR be given, and Dr, {xx,, ) Without losing generality, we assume that wxy, < wx
In this section, we show that, after compressing the data into I-dimension, we can use a network JF
|
to map wx; + of where {u, 1 are the given values. Furthermore, FF should also satisfy
Flur + b) E (1n)g 1= for all x E [0, 1)"h except for small portion.
This network has (VN) parameters, as shown below.
( Lemma F.3. Let E Th and b E R be given, {uz}}=o CR and <>>> O be given.
Let Der = wE++1 +b.
and Der DN where D is a distribution, and assume that wx, + b
Then a network F with width O(VN), depth 2, and at most O(VN) parameters, can satisfy that:
(I): F(wx; + b) ! all i E [N];
(2): ((x.g))D(F(uz (Fwx + b) E {oy} { |
2216
Proof. Let qi = (wTi+1 1 + - (wx, b) and q min, Then we consider the set of points
S: = {wr; + bb
ge 2N
[w/c|+1 for any i. We have that: j} j=ز
EvEs, PlawiiD(wx +be (s // 12/ + // 2)) ((ag))D(3s E S,, we + bb --//// /2 2N 22)
Consider that |S,1 2 N/e, so for any i, there is a 8 E S,, makes that IP ((r.))D((u (wx + b E (st ge
2N /2, 8i + NN 2)) < f-
And it is easy to see that S; satisfies the following result: if 2 E S; then:
wT: + b < uzz + b +
qE
< z < wa; + b+ 9e
2N (IN/c + 1) wr; + b + = w0++1 b.
2N
So we have (8:
ge
2, 8:
ge 2N
/2) E (wxz b. WxF + b), Name this inequality as (+).
2N
Let is N
and t(i) argmax je(N]] [l//V i}. Now, we define such network:
[VM)
F(x) = - Pi-1
(Relu(x - 8((()
ge 2N
(2) Relu(x - -11))
ge 2N /2)) + vo-
AN
This network has width 2k: depth 2 and O N) parameters. We can verify that such networks satisfy (1) and (2).
27

---

Verify (1): For a given [M] let c()) = [ Then, when j < c(i), we have t(j) < i, so 8((5)
2N /2 S w1+ + b < w + b (this has been shown in (+)), resulting in: 5 -- (Relu(wa: 2N
b S(g) + 2N/2) Rehu wwz; + b (t()) - 2N (2) = Bj 1ー When j 2 c(t), similar to before,
we have s(() g- 2 > wa; + b, resulting in _ (Relu wx; + b s(()) 2/v /2) Relu (wz, +
TV
b b- S(()) we want.
(2) = O. So F(z:) do + (0) - vo) + +... (ve(i) 1e(()-1) = Mc(()- this is what 2N
Verify (2); At first, we show that for any x E [0, 1 satisying wa + & 1 - 2N 2, 8: 2N/22) we have F(x) E {et}.
This is because: for any x satisfies wi + b & ( (8; / 8; + 2N /2), we have F(we + b) No (w) un) + +.... (vx- Uk-1) = Uk. where lt satisties ((k) < wx b and & is the maximum. The proof is similar as above.
Second, show that the probability of such x is at least 1 c.
2N /2, + 2N /2) I ñ for any i, we have P(a.))D(3ii, wr + (s, 2N 82, + 2N /2)) S E ((aa))DD(( (wee + b E (s, ox /2, 8/
By P ((aa)=D(wx + bE E (s;
ge
+
EN / S e/N N =
this is what we want. So F is what we want. The lemma is proved.
E.3 Label determination
This is the same as in section B.3
E.4
The proof of Theorem 5.3
Three steps are required: data compression, data projection, label determination. The specific proof as follows.
Proof. Assume that Dr, = [ without loss of generality, let d; A Ty. Now, we show that there is a memorization network F of Der with Ō /N) parameters but with poor generalization.
Part One, data compression. The first part is to compress the data in D., into R, let w, b satisfy (1),(),(3) in lemma E.2 Then, the first part of F is (xx = Relu wx + b).
On the other hand, not just samples in Dty, all the data in Ihth have been compressed into R by f1
By (3) in lemma E.2 we have IP (((z,))> (3, y²) E Der, |wr - wz| I 3) < 0.01, resulting in, we
have P ((..y)>((
we1 for ((2 yz) E D.r)) > 0.99. By the probability theory, we have
P P(a.v)
w2| for V(2 E Drr > 0.99)
=
P P(a.v>D( ww wz > 3 for ((z E Drr > 0.99, y -1)+
P P(r.w)D( Wx w2 for (22 E Drr > 0.99, y 1)
0.99.
Without losing generality, we assume that P (a..y)- (V yz) E Ders |wx - w2 > 3,y 1) > 0.99/2, which represents the following fact. Define = {xr x has label and |w.r w2| > 3 for V(2, y=) E ). 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.
Part two, data projection.
Let Q = fz. Without losing generality, we will assume c, S Cs+1.
No Now, assume that we have No samples in Dir with label 1, and (1 C [N] such that day has label 1, and i, fj+1- Let t()- argmax (rgmax,etty (li/VNo) =i} and Uk [Cia-- (iaaa-1422 [C In this part, the second part of F(x), named fa(x:, need to satisfy fe(cz,) ( Furthermore, also hope that P (f (x) (x+)) 2 0.999, where fx(fixx)) is the i-th weight of fe (x)), and ((o.))-(((((((()]1 fi(x).
28

---

By lemma B.3 network with O(VN) parameters and depth 2 is enough to calculate 11 xx1l by Cit, and the output in {1:} has probability 0.999. Retaining & just need one node. So ʃ2 need O(VN) parameters.
Part Three, Label determination. In this part, we will use the th mentioned in part two to output the label of inputs. The third part, named as fa(2,c), c), should satisfy that for fa(u:: c). where vq [Ceck- ICaaa ... [Ctzog] as mentioned above, if |c Ct,y < for some g [t(k 1) 1, [k)], then fs(v.. > 0.1, and fa(Ue, c) when |c Ci. 2 1.1 for all q [t(k - 1) 1, t(A)].
This network need OV In(Norr/c)) parameters, by (1) in lemma E.2 and lemma B.5 Construction of F and verify it:
Let F(x) fs(ff(f1(z)) 0.05. We show that FF is what we want.
(I) By parts one, two, three, and the fact No S N, it is easy to see that JF has at most O(n
VN In(Nnr/ parameters.
(2): F(z) is memorization of Drr. For any (2, E Der, two cases are consided.
(1.1, if 1): using the symbols in Part two, because y 1, Di, for some k. As mentioned in (x)). Then, by part three, because (x) - [f(())] < 1,
part two, fa(fi (x)) will output (e;
so we have fs(f2(f(xz)) - 0.05 2 0.1 - 0.05 > O.
(1.2 y - - 1): By (2) in lemma E.2 for (z, 1) Der, we know that (f) - (z) - (()) []](]]] 2 4 3. So, by part three, we have (a(f(fi(z)) = 0.05 < 0.
(3): AF(F) < 0.51. We show that, almost all E S (S is mentioned in part one) will be given wrong label.
For x S. we have |uer - wxx 2 3, so wx + b [wr; + +b] 2 2 for all (z,, E Der. Then for any u, by part three and the definition of Us. we have (v,, wr + b) = when x E S. So, when
fz(f(x)) {u;} and E S, we have fa fa(f2(fi - 0.05 = 0 0.05 < 0.
Consider that for any (x)( E {wih. we find that f(x) gives the wrong label to x. Since P(r E 5) 2 0.99/2 and (()(1)+)) E {m:)) 0.999, we have P(x E (2))(((=)) E {w:}) 2 0.99/2 0.001 > 0.49.
S, the label of x is in distribution D. So when E S satisfies
By the above result, we have that, with probability at least 0.49, Sgn(f # y. AD(f) 0.51. So, we prove the theorem.
F Proof of Theorem 6.1
We first give three simple lemmas.
Lemma F.1. We can find 2 T points in [0, 11", and the distance between any two points shall not be less than c.
Proof. Let 1= ( We just need to consider following points in j0, 1)":
For any given i1, é2, és. ... is f0, 1}. let ta.... be the vector in [0, 1]" satisfying: for any j E [4, the (j - 1) + to jic21 weights of ia.i.... is ij; other weights are O.
We will show that, if {i1, i2,
4. i.) # (ir fi.Je.Ja.. Ja...... ft). then it holds [| d2.a....
Ji ll 2 Without losing generality, let in # J1- Then the first [c²] weights of io and Ji..sss...... are different: one is all 1, and the other is all 0. So, the distance between such two points is at least V 2
Then fademan J Ji Ej0,1] is the 2 point we want, so we prove the lemma.
29

---

Lemma F2. 1fe, E (0, 1) and k E Z, satisfy that: S k(1 - 2e - 6), then 2 (=> 2 - 6).
(2j=0 (k)²) <
[ke]
Proof. We have
Mel 2 (E)= (()=)) S 2-2
k-z < 21 8). 2 k-
The first inequality sign uses 23= (m) m2" /n where S n/2, and by S k(1 - -ee - 6), so
[ke] (A: z)/2. The third inequality sign uses the fact v k(1 2e 5).
Lemma F.3. If k v E IR+ such that kv > 3, and a = [bte] and 3 $ - Vienn (k((V)), then 2 (b/ (n()) 0/2.
Proof. If Vk s b/ ln)),, then b & In (n())) Inbbbb) S b, which impossible. So < Viln(VE), and then vh 2 b/ In(b). Resulting 2 kv - 1 z ku/2 2 (b/ b/())
Now, we prove Theorem 6.1
Proof. By Theorem 4.1
know that there is 1, when vN 2 n, for any distribution D& Der has memorization with i V In(Nn/c) parameters. We will
D E D(n, and D
show that Theorem 6.1 is true for 3207
Assume Theorem 6.1 is wrong, then there exists memorization algorithm &. such that for any n E c, (0, 1). Df E D(n, c) and 2 1 No (1 2e 5), we have
3202
In
PD.NDDN (A(C(D,) 21 - 1- 5.
We will derive contradictions based on this L.
Part 1: Find some points and values.
We can find k. n2, c, ò, satisfying
(1): we have n, k Z4 and 12v; <n Vk. Let 1, and find i points in [0, 1]" and the distance between any pair of these points is greater than c;
(2): 6,6 E (0. and [A(1 2c 8)] 2 3.
By lemma F.1 make (1) valid, just need n² k < 2n, and (2) is easy to satisfy.
Part Construct some distribution
Let [u,}kmn satisfy u, E [0, 1J" and ||u; -11l2 2 By (1) mentioned in (1) in Part 1, such {u;) must exist. Now, we consider the following types of distribution D:
(cl): D is distribution in Dnn, c) and P ((ay)-((> (x E {ui = 1.
(c2): ((ra))a(I w:) (xx,)))(( uy) 1/k for any i.j E [k:].
It is obvious that, by ||u; uylla 2 such distribution exists. Let S' be the set that contains all such distributions. We will show that for D E S, it holds No S v1 vnVVlnn(kn
By Theorem [.1 and definition of U1, we know that for any distribution D E S, let yi be the label of u, in distribution D S. Then there is memorization F of {(u;, b with at most Vl In (kn/c) parameters. Then by (c1), the above result implies Ap(F(z)) 1, so we know that ND < V1 In for any E S. Moreover, by k 2 1 and it is easy to that No 2 n. We thus have 3 < No < 4vy / In(k).
Part 3: A definition.
Moreover, for D S, we define S(D) as the following set:
30

---

Z E S(D) if and only if Z E [k]] is a vector satisfying: Define D as D(2) = {(u,. Vs, )
then Ao(C(D(Z)) 2 1-6, where 2, is the i-th weight of Z and yz, is the label of ug in distribution D.
It is easy to see that, if we i.i.d select samples in distribution D to form dataset Dtr, then
(I): By c2, with probability 1, Drr only contains the samples (uj Ms) where j [A]]
(2): Let Drr has the form shown in (1). Then every time sample is selected, it is in {(u,, y:)
Now we construct a vector in [k]9 as follows: the index of i-th selected samples as the i-th component of the vector. Then each selection situation corresponds before. Then by the definition of SDD), we have Ap (Dr)) 2 1 e if and only if the corresponding vector of Dr S(D).
vector in [k]* which is constructed as
Putting ND < 4e Vav/ll(Vk and q = [k:1 - 2e -8]] in lemma F33
we have q 2
Np/(4v1)
)²(1
(n(Nn/(44))
21
2c 5)/2 320f IuP(No)
By the above result and the by the assumption of L at the beginning of the proof, so that for any D E S we h
[S(D)
PD (A(C(D()( -c) -))=
2 -.
k9
Part 4: Prove the Theorem.
Let S. be subset of S, and S, = ig di C S, where distribution Pay satisfies the label of uj is ij. where j E [k).
We will show that there exists least one 'D C S., such that [S(D) < (1 - 5)44, which is contrary equation 4 To prove that, we just need prove that Σ EDeS, [S(D) (1 b))=*** ka, use |SS 2* here.
To prove that, for any vector Z [k:]%, estimate how many D E Sg which makes Z to be included in SDD).
Part 4.1, situation of a given vector Z and a given distribution D.
For Z (z))=1 and such that S(D), let len {c [k]] c= } We consider the distributions in S₂ that satisfy the following condition: for E len (2), the label of u, is equal to the label of u, in D.
Obviously, we have (l-nlen(2) distributions that can satisfy the above condition in S., Let such distributions make up set S., satisfy Z E ((D)).
(D, (D, Now, we estimate how many distributions D, in SD, Z)
For any distribution G E Ss, let v(G); be the label of us in distribution G, and define the dataset D., = (u,,, vDD),, )) Then E S(D.) if and only for at least [ke]] of E [k)) L(D..) gives the label y(D)): : to u4.
Firstly, consider that when [(D,r) must give the label y(D), to u, so when E len ()) ((D,r) gives the label (D))); to Ui.
(Z). For any D, E SD, Z). we have y(D.): y(D); and
Then, consider & len (Z). Because Z is given vector, if Z E S(D,), the label (DD)); where i & len(2) (Z) are at most [kc] different from the label of u, given by L(Dr)).
So, by the above two results, this kind of D, is at most Σ [ke] (k- (k-llen(Z))), So, we have Σi=0
[(kd] (<-Iem(Z))) lem()))) number of distributions D, in S.a (D, 2) satisfy S(D.). Part 4.2, for any vector Z and distribution D.
Firstly, for given Z, we have most 2)(en(Z)) different S., (D, Z) for D Ds-
Because when D, and D2 satisfy y(Di); = y(22); for any E len(Z), we have D.o (D,, 2) (D2, 7), and 2]len(Z)] situations of label of u, where E len (2), so there exist at most 2 2(len(2) different Sae (s,(D,25 Z).
31

---

By part 4.1, for a (D, at most Σi=o
[ke] (k-1lea(2)1) of of E (D, 2) satsify Z E S(D,). So
by the above result and consider that D. = UDED Saa(D, (D, 2), at most 2)1en(2)1 (2) > [ke]] (k-lleu(2))) number D2 E Sg such that Z E (D2)).
And there exist k9 different Z, so EDeS, |S(D) < Ex 211ea(2)1 E/ed (k-1len(2))) s E2 2t
5) = 1:22 (1 - 6). For the last inequality, we use 2 |lea 2)1 D/1 (K-llen())) < 2 (1 - 6), which
can be shown by [len(2) Z) I and lemma
This is what we want, we proved the theorem.
We now prove Corollary 6.4
Proof. Using lemma
F.I we can find 2 ( points in [0, 1]" and the distance between any two points
shall not be less than So we take a e, 5 such that 1 - 2x 8 > 0, 3[12v1/(1 2e 6)]
c= 1 and k = 2 pan in the (1) in the part I of the proof of Theorem then similar the proof of Theorem 6. and we get this corollary.
G Proof of Theorem 6.5
G.1 The Existence
Firstly, it is easy to show that there exists memorization algorithm which satisfies C(D;,) S ND when Der ~ with probability 1. We just consider the following memorization algorithm:
For given dataset D, let C(D) be the memorization of D with minimum parameters, shown in Theorem 4.1 Then para( (DD) < O(v(D)).
And if D is i.d selected from distribution D, where D E D(n, c). then by the definition of L and ND in Theorem 4.3 we have para (D)) ND with probability 1. So L is what we want.
G.2 The Sample Complexity of Generalization
To prove (1) in the theorem, we need three lemmas.
Lemma G.1 (E Let H be a hypothesis space with VCdim h and DD is distribution of data, if N h, then with probability 8 of Drr DN, have
8h NcN 81m 4 8 h N
ED(F) ED. (F) S
(F)
for any F H. Here, ED(F) ((x)))D([(F() = U)l, ED. (F) = [(aNED.)) [[F((x) y)]
and I(x) i is true or I (xx =
Moreover, when 2 1, we have
ScN [E((F) F.. ln
oh
Lemma G.2. I S ba/c, then we have a (n(bb)) S cu when 2a In(ba/c)/c.
Proof. Firstly, we have al((bu) =
au(ba/eleu/an and we just need to show ln(ba/ (a(ba/clcu/u)) ca/e
< 1.
eu/a
Then, we show that there are 2 lmbba/c) < ba/c. c. Just consider the function g(x) = x 2 In x. by g'(x) 2/z, so g' (x) when x 2 2, so g(ba/c) 2 g(e) e 0, this what we want.
Now we consider the function f(x) = In((ba/ ( xr. by the above result, we have that s 2 In(ba/cc < ba/c have that
((21n(aa/c)
In(2(ba/ e) (anbaa/a (ao(ba/))) (nlaa///)
In (ba/c) /) * (ba/c) / (2 In in(ba/c)
(b)/
I.
32

---

And consider that (x) = 1_Lu((ba/c)r)) I 0 when 2 1, so, when 2 2lm(ba/c), we have
f()) & ((2 I 1, which means that when cu/a 2 2 In(ba/c), it holds In(ba/cl In(ba/c(cu//))
cuja S 1.
The lemma is proved.
Lemma G.3 (6)). Let Hm be the hypothesis space composed of the networks with at most m parameters. Then the VCdim of Hm is not more than qm² In(m), where is a constant not dependent on m.
Then we can prove (1) in the theorem.
Proof. Let Der D., Because the algorithm satisfies the condition in theorem, then [(Drr) HND where HND is defined in lemma G.3 By lemma
G.3 the VCdim of HD., is not
more than q (N) for some q I. Using lemma
G.I to this fact, we have N 2
16 (n(N)) In( SageNg 1n(N))
Take these values in lemma G.1 and considering that the memoriza-
tion algorithm L must satisfy that Ep,, (C(D,r)) = 1, using lemma G.2 b = 8c/6 6 and e² in lemma G.2 we have
(just take a = 8q.2 In(Np)
Nq In In Sa.V
ED(((((,)) VV
Se
which implies 1 e ED(C(D,,)) The theorem is proved.
G.3 More Lemmas
We need three more lemmas to prove Theorem 6.5
Lemma G.4. Let D C [0, 1]" x 1),, Then D has a memorization with width 1 if and only if is linearly separable.
Proof. If D is linearly separable, then it obviously has a memorization with width 1.
If D has memorization with width 1, we show that D is linearly separable. Let F be the memoriza- tion network of 'D with width 1, and Fi the first layer of F.
Part I: We show that it is impossible to find any (æ1, 1), (z2g, 11), (1z, 1) E D such that Fi(11) <
Fi (x2) < Fi (x3). If we can, then contradiction will be obtained.
Assume (I1, 1), (I2, -), (I3, 1) D such that Fi < Fi(22) < (23).
is easy see that, for any linear function w and and S S k we have wn we+b < wk+b or wu + b 2 we + 2 wk b, which implies Relu ww + b) s Relu(wv + b)) s Relu(wk + b) or Relu(wu + 2 Relu( we + b) 2 Relu(wk + b).
Because (a), 1), (22, -1), (x3, 1) E satisfy that (x1) < Fi(2) <F (2g),, and each layer of F is linear function composite Relu, so after each layer, the order of Fi Fiz)) Fi (1aa is not changed or contrary. So there must be F(a,) S F(#2) S F(xr) or F(x)) 2 F(x2) F(zy). Then F cannot classify I1, x2, 23 correctly, which contradicts to the fact that F is memorization of D.
Part 2: We show that, is impossible to find any (x1, -1), (I2, 1), (I3, -1) E D such that Fi < Fi (x22 FF(1(3)) (1x3)
This is similar to Part 1.
By parts and 2, without losing generalization, we know that for any (I11, 1), (22, -) E D. it holds
Fi Fi(z)) ) > Fi (x22. Since F, is a linear function composite Relu, is linear separable.
Lemma G.5. Let D (Ir vi)} C [0 x f-1.1}. Then D has a memorization with width 2 and depth 2 if and only if at least one of the following conditions is valid.
(cl): There is a closed interval such that: if (a, 1) E D then x E I and if (x. -1) 1) E D then x & T.
(c2): There is closed interval such that: if (z, 1) D then of I and (z, -1) e D then I.
33

---

Proof. Part 1: We show that if condition (c1) is valid, then D has memorization with width 2 and depth It is similar for (c2) to be valid.
Let = [a, b). If for all (x. -1) E D, we have I < a, then D is linear separable, and the result is b. then D is linear separable, and the result is valid. Now
valid. If for all (1) E D, we have we consider the situation where x > a for some (z, -1) E D and x < b for some (I, E D.
Let x-1 ma (1,-(),,)ele))) 1 < a). Then for Fi = ( + a)/2. it is easy to verify that for all (zo: -1 E D such that To a.
(i()) > - for all 2 and (z) <
Let 2 = (2, -1) f > b). Then for F2(x) = x- (01 + /2, 2, it is casy to verify that F2(2) < 0 for all x I b and (2 > (I1 6)/2 for all (Zo. -1) E D such that zu > b. Let the network F be defined by F = Relu(Fi (x)) TRelu(Pa(x)) positive real number, and s-x-1 > 0.
L, where T
b1-b is
Now we prove F is what we want. It is easy to see that, F is a depth 2 width 2 network. When
E (a, b). then (xr) >> e-x and (2(x) S 0, so F(x)= > 0. For -1) E D such that x < we
have Fi (z) < and F2(2) < 0, so F(x) < 0; for (x, -1) E D such that x > b, we have Fi()) < 1 ボ1ー6
and (2) > 1 so = 11 8- < O, this is what we want.
Part 2: If D has 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, as- sume that (x1, 1), (I2, 1),, (1z, 1) E D such that 2 22 < 23 (for the situation that (01,-10 (22, 1), (23, -1] E D such that T1 < x2 < 23, the proof is similar). Then we show that if (z. -1 D, we have Iı < < X3. Assume -1) D such that zo Iı, then we have that zo < 21 < 22 < 23, then we can deduce the contradiction.
Let F aRelu(Fi Fi (=)) + (Relu(F2(z)) e be the memorization network of D, where F(()) is linear function. Let u. e E R such that Fi (u) = F2(1)= = O, without loss generality, let u S v.
Then we know that F is linear in such three regions: (-oo, u). [u, u] and [v, (c). We call the three regions as linear regions of F. We prove the following three results at first.
(I): The slope of F on (-c0, u| is positive.
Firstly, we show that .p E (-o0, ut]. If not, since (1), (x1, 1), (r2, 1) are not linear separa- ble, and (21, 1), (222- -1] -1). (I3, 1) are not linear separable, we have (xo. -1), 11) E [u. v| and (x22 -1), (Iz, 1) E [u. 0.). Then, because œ1 > Zg and F(x1)= > F(zu), and F is linear in [u, n). we have that F(o) 2 F(11)= > O. Now we consider the points (v. 1), (x2, -1), (Iz. 1). It easy to see that F memorizes such three points and they are in the linear region of F, so (u, 1), ( -1), (zz3, 1) is linear separable, which is impossible because v < 32 S Dg and resulting in contradiction, so Tr E (-o0, u).
the slope of F on (-oo, u| is not positive, since u 2 Ho. we have F(u) < 0. Now we consider the points (u, 1)), (æ1, 1), (12;-1), (I3, 1). Just similar to above get the contradiction. So the slope of F on (-oc,u) u| is positive.
(2): The slope of F on co) is positive. Similar to (1).
(3): The slope of F on (-o0, u] is negative. If not, F must be non-decreasing function, which is
impossible.
Using (1), we can get a contradiction, which means that there is (zo. -1) E D such that Fo < x1 is not possible.
Consider that, in a linear region of F. if the activation states of F1 and F3 are both not activated, then on such linear regions, the slope of F is O. But due to (1), all linear regions have non-zeros slope of F, so on each linear regions, at least one of F1 and Fg is activated. So, the activation states of F1 and Fg at (-o0, u]. [u, v) and [v. 2o) is (-, +), (+, +), (+, (+.-) (+ means activated, means not activated).
34

---

Then the slope of F on [u, e] is equal to the sum of the slopes of F on (-oc, u] and the slope of F on [v. oo). But by (1), that means negative number is equal the sum of two positive numbers, which is impossible. So we get a contradiction.
So if (ro: 1) E D, we have 2i 31. Similar before, have 30 2/3- So we get the result.
By the above result, all the samples (xo. 1) E D satisfies x E (21, so there is a close interval in 23) such that: if (zo, -1) E D, then zo 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.3 that is, all such algorithm is not efficient if P # NP. We need the reversible 6-SAT problem defined in definition 6.6
Proof. We will show that, if there is efficient memorization algorithm which satisfies the conditions of the theorem (has at most Np parameters with probability 1), then we can solve the reversible 6-SAT in polynomial time, which implies P P= NP.
Firstly, for the 6-SAT problem, we write it as the following form.
Tū. and Ti,j is either x. or -x for some E [n] (see Definition 6.6). Then, we define some vectors in IR" based on (v,(n, m).
Let y 10: m) be 6-SAT for n variables, where (i,n, m) = "r=
For i E [m/] define Q E R as follows: L 1 1I x, occurs in (n m); Qr = -1 if - occurs in (n, m); Q [o] = 0 otherwise. Q []] is the j-th entry in Q then six entries in Q are
or 11 and all other entries are zero.
Now, we define a binary classification dataset D(p)) {1x, (.c..,)) c 10, x [2] as follows.
(1) For i E [m], H; = 1,/3 3 + 1.11/3, 3, = 1.
(2) For i E {n + 1, + 2.... 2n rr 1. 1, / 1.11/3, = -.
(3) For i (2n + 1,2n 2, 2,... 3m) 3; -1:-21 +.11 /3, 9/ 1.
(4) For i E (3n + 1,3n 2..... 4n). = -1.11,,- 1.11/3 1/11//3/////31 yi -1
(5) For i E {4n+ + 1,4n - 2,..., 4n + m). I; = 1/120 + 1.11/3, yi 1.
=
Here, 1, is the vector whose i-th weight is and other weights are 0, 1 is the vector whose weights are all
Let L be an efficient memorization algorithm which satisfies the condition in the theorem. Then we prove the following result: n 2 4 and yp is reversible 6-SAT problem, then para(L(D((p)) = n+88 if and only if &p has solution, which means P = N and leads to that L does not exist when P & NP. The proof is divided into two parts.
Part 1: If po is reversible 6-SAT problem that has solution, then para(C(D(p))) = n
To prove this part, we only need to prove that para(L(D({))) 2 n and para (ar(((())))) + 8.
Part 1.1: we have para( ((D(())) 2 n n
Firstly, we show that [(11, 1), (Im+1,, (I2n+1, 1 1), (I3n+1, -1)} C D(p) are not lin- early separable. This is because {21, Nn 1, 22n+1 F3441 is linear transformation of 1.1,1,11, 1,, ,,, so ((21, 1), (I,41, - -1), (22n+1, (Xga+1, -1)} C D(e)) are not lin- carly separable and only if {(11, 1), (1.11,,-1), (-1,, (-1, (-1.11, (-1.11,,-11 are not linearly separa- - ble, by the definition of 1,, easy to see that (11,1), -1), (-1,, (-1.11,, -1)} are not linearly separable, so we get the result.
By the above result, a subset of D(p) is not linearly separable, so we have that D(p) is not linearly separable. So, by lemma G.4 L(D((p) must have width more than 1. For 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 2 4, have para(C(( ((((()))) 2 n + 8.
Part 1.2: If to is a reversible 6-SAT problem that has a solution, then para(((D()))) S +
35

---

We define distribution D at first. D is defined on D(p), and each point has the same probability. It easy to see that, D E (n, 1/30).
Since when N 2 m + 4n, we have PD.,-DN (Dzr = D())) > 0, so by the definition of ND and the fact L satisfies the conditions in the theorem, we have para ((D()))) S ND. Moreover, because 'D is defined on D(p)), we will construct network with n + 8 parameters to memorize D(p) to show that ND I n + 8, which implies para(C(D(o))) S ND I n + because C 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 = (#1, $2...., 8n) {-1, be solution of Then the first layer is Fi (x) Relu(3s(x- 1.11/3) + 3). Then we have the following results:
(1): = 4.1 or (x) = 1.9 for all (x,, -1) E D(g):
(2) < [+)( < 4 for all (z, 1) E D(p))
(I) is very easy to validate. We just prove (2).
For E [n] and E {2n + 1...., 3n), because & E {-1,1)", so 3s(x - 1111133 = or 3s(r (1.().)
1.11/3) = 1, which implies
For E { (4n + 1,..., 4n + m) x; 1.11/3 has only six components that are not O. Because 8 is the solution of sp. which indicates that at least one of the six non-zero components of a; 1.11/3 has the same positive or negative shape as the corresponding component of 8. Consider that such six non-zero components of x,- 1.11/3 3 are in (-1/12,
so 3s(2; - 1111/3) 2 1/4 1244-5/15 5/4 -1
Moreover, because yp is a reversible problem, so ( m) and (o,(n, m) are both in the s. which indicates that the positive and negative forms of the six non-zero components of r; - 1.11/3 cannot be exactly the same as the positive and negative forms of the corresponding components in s, or there must be pa (n, (n)
which contradicts to is the solution of p. So, we have 3s(r; - (.11/33 = 5/4- - 1/4= = 1.
Then we have that, for i E {4n + 1......4n + m), it holds 3s - 1.11/3) E [-1,1], resulting in 2 < [i (zx)) < 4. We proved (2).
By (1) and (2), and using lemma G.5 there is a network F2 : R + R with width 2, depth 2 and 7 parameters that can classify the { (z:), ")) so F2 o Fi is the network we want.
By such a network, we have that No I n + 8, and then, we have para(C(D({))) S No S n n+8 8. We proved the result.
Part Two: If to is a reversible 6-SAT problem and para(L(D(e)) = n + 8, then has a solution.
If C(D(s)) has width 2 of the first layer, then para(C(D(p))) 2 2n + 5 > + 8, so when para( (ara((((()))) = n + 8, the first layer has width 1.
Write C(D())) = (z),, and write Fi as Fi) Relu(3s(I - 1.11/3) + b), and let (51, ,,,,,,,....... sn).
We will prove that Sgn(s) (s) = (Sgn(s1). Sgn( s2), Sgn( Ss.). Sgn(s,)) is a solution of p. The proof is given in two parts.
Part 2.1 we have 1.1|s/| 2 |sy| for any i,j E [n]. Firstly, we have 8; + 0 for any E [n]]. Because if 8; = 0, it holds Fi (x:) = Fi (x),+)), which implies that ((D(()) gives the same label to x;; and
Tati; but v, and Ta have the different labels in dataset D(y)), so it contradicts (()(())) is the
memorization of ((p).
Without losing generality, let |s1| 2 |s2| 2 ... |.,l
Then we just need to prove that 1.1 s, 2 |s1]-
Because ((p)) is not linear separable, so by lemma G.4 L(D(g)) has width more than 1. Because Fi has width 1, so Fu has width 2 and 7 parameters, resulting in that Fg is a network with width and depth 2. And F2 can classify such six points: ((Fi(x;), y1) bi (1,m+ 1,2e+1,,+1,1000 1,30+ 1,2n,
If s > taking the values of I1, Fnt, T2++1 T3++1 in Fj, we have 1.1s; + b Fi (((211) $1 + +-b= = Fi())) 2 -s +b b- = Fi(22a))) 2 -1.1s1 +b = Fi (23n+1), which implies Fi(ent1)
36

---

(11) 2 Fi 2 Fi (f < 0. Similarly as before, we have (1 S {Fi(a1) S Fi (12++1) S Fi (23a+1). So, Fi (21) and Fi (12++1) are always in the interval from Fi (Tn+1) to Fi (I3++1)-
Consider that 2n+1 and +3 have label 11, #1 and x2n++ have label 1, by Lemma G.5 if ((F( (1, 1,,,1,2n,4nn can be memorized by a depth 2 width 2 network, then (122) and Fi (Zan) must be not in the interval from (111 to (122221)), or we cannot find a interval satisfies the conditions of lemma
1.1[sal + b, to ensure that Fi (x22)) and Fi (i are not in the interval from Fi (m) to Fi (12n+1)) we have max(Fi (I2m) Fi (man)) = 1.1|8al
Since max(Fii (222);; Fi [2(4n)
b 2 max (F((1))) (222+4)
[81] + or max (F(((e))) F, (1)
1.1/spl + b <
(x1), (I(24411)) --ss+++ 6. The second case is impossible, so we have 1.1|sp]
2 |11/-
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 p. There is a E {4n + 1....,,47 + m), such that the positive and negative forms of the six non-zero components of x; are exactly the same as the positive and negative forms of the corre- sponding components in s. Then sx, + b 2 6/4[sn + b 2 6/4.4|s + b 2 1.1 + b. So, by (i (1) = |.1[s]] + b and min (Fi (11+a), (13n+1)) 1]] = -1.1/81 + b, we max (Fi (z)+n), Fi
know that Fi (a:)) is not in the interval from Fi (x144)) to Fi (13++1)-
Then similar to part 2.1, consider the point (xx), 31) hie (1, 1, we have that Fi (x1) and Fi (12n++11 are always in the interval from F (Tn+1) to Fi (13++1), but Fi (2x) is not in the interval from Fi (x11+) to F (I3n+1). By lemma G.5 and the fact that the label of Fi (1n+1) and
Fi (I3++1) is different from that of other three samples, we cannot find an interval satisfying the con- dition in lemma G.5, so F2 (x:) cannot classify such five points: {(Fi (at)), yi) +1 1,2n 1,++1,3m 1,30+ 1,
This is contradictory, as ((D())) is the memorization of D(()). So, the assumption is wrong, we prove the theorem.
H Proof of Theorem 7.3
H.1 Proof of Proposition 7.7
Proof. It suffices to prove that we can find an SD(D) C {(z, ((),,)) ~ D} such that for any (x. v) D, we have E (B(
Let S. = ( igc/ (6., in (6.2m)) رi E {0, 1,....,.66 ......,(..2n//4 /cc + 1}}, and define (DD as: for any (6.c/66.1)) /2c/ // satisfying || - (fcc/(6.2)) i2c
(6.2n)) E Se. randomly take a (z. y) D
in (6.2m))) S c/(6.2n) (if we have such a æ), and
put (z, y) into (D))
Then, we have that, for any (z. y) ~ D, there is a point 2 E S. such that ||2 - ællo S <c((6.2m) and there is (xz, Vz) (D) such that || xz c/(6.n), so ||=, xl 00100 I c3(3.n,), which implies || - x=2lla lloc I c/3.1.
Since the radius of B((2,w) w)) is more than c/3.1, for any (α,y) D. we have (G..))ES.DD))(( B((z, w)), we prove the lemma.
H.2
Main idea
For a given dataset Drr C 10, x 13, we use the following two steps to construct a memoriza- tion network:
(cl): Find suitable convex sets {C+} in [0, 1]", ensuring that: each sample in D,, is in at least one of these convex sets. Furthermore, if x, C, and (a, Ux), (z) E Dir, then yı Vz. and define
v(C))) = Va-
(c2): Construct a network F satisfying that for any E C, Sgn(F(x)) v(C)). Such a network must be a memorization of Dtr, because each sample in D,, at least one of (C.), so x E C, and (zz yx) Der. then Sgn(F(x)) y(C,) yz. which is the network we want.
37

---

H.3 Finding convex sets
For given dataset Der C 10 x f-1,1), let Der {(1,, u)) and for i [n], the convex
sets C, are constructed as follows:
(I): For any i.j [M]] define Sz)(x) (x; xz)(1 (0.51 * 0.49 x2))) it is easy to see that
Sig is a vertical between 2; and Z;;
(2): The convex sets C; are defined as C; mw {x E (1. 2 0}.
Now, we have the following lemma, which implies that C₁ satisfies conditions (cl) mentioned in above.
Lemma H.1. If are constructed as above, then
(1): 2; E C;;
(2): If C; and (z,yz) E Dir, then y= = y::
(3): C is a convex set.
Proof. Firstly, we show that Iy E C. For any i.j E [N], taking I; into Si,(2), we have (1,( = 0.49 - 1y 2 > O, so 2, E fo e [0, | 2 0}. Thus x, E Ey for (0) 2 0} C..
Then, we show that: if yj # yr then xj & Ci, which implies (2) of lemma is valid.
For any j.j E [N], taking Bj into (r), we have (t, 0.51|| 2,113 < O. s, & for (x) 2 0}. Thus 2j & M fo E 1 1
2 0) = C Finally, we show C2 is a convex set. Because for any i,j E [N], for E [0,, 2 0) is convex set, and the combination of convex sets is also convex set, so C. is a convex set.
O
H.4 Construct the Network
We show how construct a network F, such that (gn(F())) y(C)) for any Ci, where C, is defined in section H.
For given dataset Der U:)), construct network F which has three layers as following.
(1): Letr= 0.01 * ming,e ||:; 1.11ß. For any i,j E [N]. Si, defined in section H.3 let
(z(x) = EEE Relu(-Si, - r. It is easy to see that u; is a depth 2 network.
(2): The first two layers are Fi : R + R. Let F [x) be the i-th output of Fi(),, then let
Fi [x) equal to Relu(-u,(1)) It is easy to see that, Fi (x) requires O(N2n) parameters.
(3): The third layer is F2 RN + R. and Fe(u) Σ yerr where is is the i-th weight of v,
Now, we prove that Sgn(Fmem (1)) y(C) for any x E C₁. We need the following lemma. Lemma H.2. For any x E C,, we have uxxx)= < 0 and u (x) > O when y: + y,-
Proof. Assume that Cj. We prove the following two properties, and hence the lemma.
P1. u(x)) <
By the definition of C, we have Szz(2) 2 0 for all j E [N] staisfying yi + yj. so ui(x) = EjeMaayy Relu(-Sa,(z)) -err-=ejetenn bjE(M),,yu. 0-
O.
P2. uz(x) when y: # Vj-
For any j such that yi * yj, we show S),(2) < -0.02 - =x,122 at first. Because E C., so
(x) 2 0, that is (xt - (2) (0.51 * x; +.49 2 0, so
(z; 2z (I
* +
(I, 1=--z,)0 (I (0.49 22, 0.02 2., - 22
-S)((z) - -0.02||2; [all|;--,,10 1
w
38

---

Thus Sza(z) v -0.02| -zyll-- Then, by the above result, taking the value of r in it, we have uz(x)) 2
- -r 0.02|| |. x,11 > 0.
By the above lemma, we can prove the result. Lemma H.3. we have Sgn(Fmem({H)
for any x E Ci.
Proof. Let x E C.. By lemma H.2 we have Fi > O. and F1(x = 0 when j satisfies
y, # Yo, so F(z) =e)==jjeNN EjENN yj b = Y: ΣjeM [1) by (z) 0, and we thus have Sgn(F(x)) =
H.S Effective and Generalization Guarantee
In this section, we prove that the above algorithm is an effective memorization algorithm with guaranteed generalization. We give lemma.
Lemma H.4. For any a, b, c E IK" such that ||b a 2 3.1||a let V be the plane (b - cx (0.5Ic+ 0.49b)). Then the distance of the plane is greater than ||6 all/3.1.
Proof. Let ||a - b|[2 Lab- ||a - cl|2 Traes l|c - b112 Lbbe Let the angle Zabe Then the distance between a and the plane V is Lab cos - Lic.
Using cosine theorem, we have cos Lb L. -Lac so we just need to prove that L2 L.c 0.5 2 Lab/3.1, that is 151.,-0.511
21.bc Luab
2L.e
> 0.01. It is easy to see that such value is 3.1 and Lice S Lac + Lub S 4.1 we 0.5 15-003/331/-41//88
L.os Lno/3.1
inversely proportional to Lue and Loc. By Lac S L have 0.51. 0.51." Figt /3./3311
> 0.01. The lemma is proved.
(4.1/3.1)²
We now show that the algorithm is effective and has generalization guarantee.
Proof. Let Fmem be the memorization network of Der constructed by the above algorithm. Effective. We show that Fmem is a memorization of DDr can be constructed in polynomial time.
It is easy to see that, u, has width at most N, and each value of parameters can be calculated by Der in polynomial time. So Fi defined in (1) in section H.4 can be calculated in polynomial time. is easy to that the F2 defined in (1) in section H.4 can be calculated in polynomial time. This, F can be calculated in polynomial time.
Generalization Guarantee. Let {(1;, yo.) be the nearby set defined in Definition 7.1 Then, we show the result in two parts.
Part One, we show that: for (wi, w:) Der. if; E (((u))));)) for j E [So], then Sgn(F(x)) y: for any B( Ve,)).
Firstly, we show that it holds B( Ve, )) E C.. For any & E [N] such that yı + we have ||, - 1xll2 2 3.1r 2 3.11|u, - zill. where r is the radius of B(u,,, Bc,)) )) so by lemma H.4 the distance from ny to Sit (x) is greater than r. which means that the points in B((;;- Mo,)) are on the same side of the plane Sa( by a, E B((j,, Vo,) )) and (z,) > 0 as said in lemma H. Thus,
for any E B( Vey) }), we have (x(x)) 2 O. By C, Dje[M]au fx [0. || we know that ((1), Ve,) )) Ct.
0}.
By the above result, if x E B((1,, Vo,)), then x E C₁ so by lemma H.3 we have Sgn(F(x)) y: for all x E B((e,, Vo,)).
Part Two, we show that if Der DN and N 2 1-e E) 5.
then P PA. (Ap(F N
Let Qi (P(xng)DD B( Bo, then without losing generality, we assume that Q1 S Q2 S
< Qsp. Then, for the dataset D,r = ((x, y:) let (DD,,) = (j E [S>]] E [N], xz E
B( Moy ))}. The proof is given in three parts.
39

---

part 2.1. Firstly, we show that (p(mmem) 21 - Li42(De.) Qs
If E Z(Drr): then by the definition of 2(D we know that there is a j [N] such that Ty E B(( Vo.)), so by part one, we have Sgn(F Femm (x)) = yj for any x E B((u;, Vo.)).
Moreover, for any (I, ~ D and x E (( (o,)), by lemma H.l and B((,; ((;)),,,)) E C3 which has been shown in part one, we know that y - 1/j-
So Sgn(Fmem(a)) (x)) = y, = y for any (I. ~ D and x E B((v).yr.) )), which means that Frem gives the correct label to all x B((c, vo.)) when i E Z(Drr, S). So AD(mmem) 2 LiE Qi 2 1- Ei Qi
part 2.2. Now, we show that IP DD.NDN (Eigz(D..) c) 2012101 1-
Let Cc: Dr DN,, $ (Dr) and E (Drr)) for Vj > i), easy see that Cej NCanaa 0 when i + j and Σ Ei=u 1p D..-DDN (Drr E Cc.) It easy see that, DD. (Dor E Cc.) S --) when 1.
Firstly we have that, if some E [Sp] makes that Q= < e/i, then for any Der E Ccj where j 1 1, we have ExzZ(D,,) Qx S Ek_ Qx s jQ₂ S iQ; < E.
So that, we consider two situations.
Situation 1: There is aic [Sp] such that Q, < e//i. Let Ng be the biggest number in [Sp] such that QNo < c/Ng. Then we have that:
PDINDDNN ( (ZizZ(,,, Qi Se)
NDN E EiEZ(D..) Qi e| E N Ca,)P (Der Cc) [8p]
+PD.,.DN (E Di. Q: S Dr E EU
(Drr [pp]
|Sa] + (5)
.DDD,DDN (Der U Cck)
Cc.) + PDDDDNN NDN (ZEeZD,,.) Qi s Der U= Cck)
DDN (Drr k Cc.)
Hence, we have
P PD.DDN((D, E [L/so]
k=No++ Cck)
i=N++1 P D.,NDDN (Der E Ccs)
Noo++1 (1 - Q1)
No+1 -NQ.
i -Ne/i
VIVII
2i=1 e -Nc/i
Spe Ne/SD
6.
The last step take N N> Sp/cIn(Sp// in. So, taking the above result equation we have
PD.NDN (Ein( (e)
1 1- 8 + PD.,.DN (E Qi 5 DD E [[! t1 Cc
1
which is what we want. Situation 2: There is no i [Sp] such that Q, e/i.
40

---

Then, we have
P D (Drr E Cck)
2F P DDMDDN (Der Cos)
(1 Qi)
VI IA
NNQQ
Li=1 NNe//i Spe -Ne/Sp
So with probability 1- 6, we have Drr E Cep. When Drr E Cop, we have ((Drr) = |Sp], that Eiez(D..) Q; = Hence, PD,,.DNN (2 (D).....) Qi S 5e) ) 2
part 2.3 Now we can prove the part 2, by part 2.1 and part 2.2, we have that PD. poxx(App (Ap(Fmem)
1 c) P DD, Eigz(D...)) Qi 2 1 c) - 8. The theorem is proved.
I Experiments
We try to verify Theorem 7.3 on MNIST and CIFARIO 33
L1 Experiment on MNIST
For MNIST, we tested all binary classification problems with different label compositions. For each pair of labels, new dataset Der, and then construct memorization network for Dor by Theorem 7.3 For each binary classification problem, Table shows the accuracy on the samples with such two labels in testset.
500 corresponding samples with each label in the original dataset form
Table 1: On MNIST, accuracy for all binary classification problems with different label compositions, use memorization algorithm by theorem 7.3 classifying classes and j.
The result in row i and column j is the result for
category 0
0
2
4
6
8
0.99
0.96
0.99
0.99
0.97
0.96
0.98
0.98
0.97
1
0.99
0.97
0.99
0.98
0.99
0.98
0.98
0.98
0.99
2
0.96
0.97
0.96
0.97
0.96
0.96
0.97
0.93
0.97
3
0,99
0.99
0.96
0.98
0.95
0.98
0.95
0.92
0.96
4
0.99
0.98
0.97
0.98
0.98
0.97
0.96
0.95
0.91
5
0.97
0.99
0.96
0.95
0.95
0.96
0.97
0.91
0.96
6
0.96
0.98
0.96
0.98
0.97
0.96
0.99
0.95
0.98
7
0.98
0.98
0.97
0.95
0.96
0.97
0.99
0.95
0.91
8
0.98
0.98
0.93
0.92
0.95
0.91
0.95
0.95
0.96
9
0.97
0.99
0.97
0.96
0.91
0.96
0.98
0.91
0.96
From [a 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%.
I.2 Experiment on CIFAR10
For CIFAR1O, 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 Dtr. and then construct memorization network for Der by Theorem 7.3 For each binary classification problem, Shows the accuracy on the samples with such two labels in testset.
From Table 2 we see that, most of the accuracies above 70%. but for certain pairs, the results may be poor, such as cat and dog (category and category 5).
Our memorization algorithm cannot exceed the training methods empirically. Training, as method each pair of labels, we use 3000 corresponding samples with each label in the original dataset to form a training set Dtr, and train Resnet18 (28 on Der (with 20 epochs, learning rate 0. 1, use crossentropy as loss function, device GPU NVIDIA GeForee RTX 3090), the accuracy of the obtained network is shown in Table 3
that has been developed for long time, is undoubtedly effective.
41

---

Table 2: On CIFAR 10, accuracy for all binary classification problems with different label composi- tions, use memorization algorithm by theorem classifying classes and j.
The result in row and column is the result for
category
0
2
4
6
8
0
0.77
0.74
0.78
0.81
0.81
0.85
0.85
0.68
0.73
1
0.77
0.78
0.75
0.82
0.78
0.82
0.87
0.79
0.63
2
0.74
0.78
0.61
0.61
0.65
0.67
0.67
0.82
0.77
3
0.78
0.75
0.61
0.71
0.54
0.67
0.69
0.83
0.76
4
0.81
0.82
0.61
0.71
0.66
0.62
0.65
0.82
0.79
5
0.81
0.78
0.65
0.54
0.66
0.73
0.67
0.81
0.78
6
0.85
0.82
0.67
0.67
0.62
0.73
0.71
0.86
0.81
7
0.85
0.87
0.67
0.69
0.65
0.67
0.71
0.82
0.73
8 0.68
0.79
0.82
0.83
0.82
0.81
0.86
0.82
0.69
9
0.73
0.63
0.77
0.76
0.79
0.78
0.81
0.73
0.69
Table On CIFAR1O, accuracy for all binary classification problems with different label composi- tions, use normal training algorithm. The result in row and column j is the result for classifying classes and j.
category
2
4
6
8
0
0.99
0.98
0.99
0.99
0.99
0.99
0.99
0.98
0.99
1
0.99
0.99
0.98
0.99
0.99
0.99
0.99
0.99
0.99
2
0,98
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
3
0.99
0.98
0.99
0.98
0.96
0.97
0.99
0.98
0.99
4
0.99
0.99
0.99
0.98
0.99
0.99
0.99
0.99
0.99
5
0.99
0.99
0.99
0.96
0.99
0.99
0.99
0.99
0.99
6
0,99
0.99
0.99
0.97
0.99
0.99
0.98
0.99
0.99
7
0.99
0.99
0.99
0.99
0.99
0.99
0.98
0.99
0.99
8
0.98
0.99
0.99
0.98
0.99
0.99
0.99
0.99
0.99
9
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
0.99
Comparing Tables 2 3 it can be seen that the training results are significantly better.
1.3 Compare with other memorization algorithm
Three memorization network construction methods are considered in this section: (M1): Our algo-
rithm theorem 7.3 (M2): Method in 49]; (M3): Method in [55).
In particular, we do experiments on the classification of such five pairs of numbers in MNIST: I and 2 and 4 and
and and to compare methods M1, M2, M3. The main basis for selecting such pairs of labels is the similarity of the numbers. For any pair of numbers, we label the smaller number -1 and the larger number 1, Other settings follow section [.I] and the result is given in Table We can see that our method performs much better in all cases.
From table our method gets the best accuracy. When constructing memorization network, the methods (M2), (M3) compress data into one dimension, such action will break the feature of the image, they cannot get good generalization.
42

---

Table 4: On MNIST, accuracy about different memorization algorithm.
pair (1.7)
Accuracy
M1
0.98
M2
0.51
M3
0.46
pair (2,3)
Accuracy
M1
0.96
M2
0.50
M3
0.51
pair (4,9)
Accuracy
M1
0.91
M2
0.45
M3
0.46
pair (5,6)
Accuracy
M1
0.96
M2
0.59
M3
0.47
pair (8,9)
Accuracy
M1
0.96
M2
0.41
M3
0.48
43

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our paper supports the claims made in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We have discussed limitations in Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
44

---

We have provided the full set of assumptions in every theorem and made complete proof in Appendix to appendix
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification:
We have provided reproductive details in Appendix
!
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
45

---

Answer: [Yes]
Justification:
We have provided our codes in the supplemental matrial.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
onliiicyn for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ctpppp.ccppulli//uuiiie wwwpc//ggue////eee CoodeSubeiiieeee ssi wswinnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We have provided experimental details in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
Justification: Our main contribution is in terms of theory.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
46

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have provided them in Appendix !
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: httprrpp....ppplooc.ccccccccooed
Answer: [NA]
Justification: Our main contribution is in terms of theory.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: None of this.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
47

---

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 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 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 models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We use open-source dataset and models our paper, and have cited the original paper of these dataset and models presented in Appendix!]
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 dataset.
The authors should state which version of the asset used and, possible, include 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, wwwprspipetattteeeeee thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
48

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "G72fyEOFdi", "reviewer": "Reviewer_dviZ", "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.\n- 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}$.\n- 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).\n- 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.\n- Lastly, they study the algorithm constructing a PAC-generalizable memorization network in poly$(N)$ time.", "questions": "- Q1. Architectural constraint: ReLU network\n    - A clear limitation of this work is that it is limited to a fully-connected ReLU network.\n    - Can you imagine how the change in activation function will affect the memorization capacity, $N_{\\mathcal{D}}$, and $S_{\\mathcal{D}}$?\n- Q2. Sample complexity bound gap of memorization algorithms in Section 6\n    - 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?\n- Q3. Proof of Corollary 6.4\n    - 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.\n- Q4. Algorithm in Theorem 7.3 as an initialization\n    - 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?\n- Q5. Generalizability of memorization v.s. non-memorization networks\n    - 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": "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}}$.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- S1. As far as I know, this is the first work studying the generalizability of the memorization ReLU network, under the binary classification task.\n- S2. In terms of ReLU networks, they discover two novel complexity terms $N_{\\mathcal{D}}$ (smallest number of parameters to memorize i.i.d. dataset (of any size) from $\\mathcal{D}$) and $S_{\\mathcal{D}}$ (”efficient memorization sample complexity”; minimum size of the nearby set of  $\\mathcal{D}$) which depend only on the true data distribution.\n- S3. The paper is well-written and easy to follow.", "weaknesses": "- W1. Compactness of the input domain\n    - 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.\n- W2. Randomness in Theorem 4.1\n    - Theorem 4.1 contains a probabilistic argument. However, it is unclear where the randomness comes from, with the theorem statement alone.\n- W3. Efficiency of memorization algorithm in Theorem 4.3\n    - It would be meaningful to mention whether the memorization algorithm in Theorem 4.3 is efficient.\n- W4. Parameter complexity of efficient memorization algorithm in Theorem 7.3\n    - It would be meaningful to clarify how many parameters the network constructed by the efficient memorization algorithm in Theorem 7.3 should have.\n- W6. Minor comments on notations/typos (There are so many typos…)\n    - Title: “Generalizablity” → “Generalizability”\n    - Line 60: “…, (2) of Theorem 1.1…”\n    - Please use $\\overline{O}$ for upper bounds, $\\overline{\\Omega}$ for lower bounds, and $\\overline{\\Theta}$ for tight bounds (up to logarithmic factors).\n    - Section 3.1: “$X_0 = x$” and “$n_0 = n$” must be explicitly mentioned.\n    - 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.\n    - Line 250: “generaizable” → “generalizable”\n    - Line 274: “The density of distribution $\\mathcal{D}$”\n    - Line 279: “$A_{\\mathcal{D}} (\\mathcal{F}) \\le 0.51$”\n    - Line 291: “generazable” → “generalizable”\n    - Line 309: “generalizability,.” → “generalizability.”\n    - Line 321: “$N_D$” → “$N_{\\mathcal{D}}$” (calligraphic D)\n    - Line 325: “bpund” → “bound”\n    - Line 337: “$\\mathcal{D}_{\\rm tr} \\sim \\mathcal{D}^N$\n    - Lines 340 and 472: “Proof Idea.” is not in a bold font.\n    - Line 367: What does it mean by “a subset of $(x,y)\\sim \\mathcal{D}$”?\n    - 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.\n    - Line 619: “Uisng” → “Using”\n    - Step Three in the proof of Theorem 4.3 (Appendix C): Please make clear which theorem of [61] you refer to.\n    - Line 1052: “Tree” → “Three”\n    - 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.\n    - 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.\n    - Lines 1148-1149: Make clear that $S(\\mathcal{D}) \\subset [k]^q$.\n    - 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.\n    - Line 1189: “Because” → “This is because”\n    - Lines 1189-1192: several “$S_{ss}(\\mathcal{D},Z)$”s are written in wrong symbols.\n    - 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)$ ”.\n    - Line 1224: “$n$” → “$m$”\n    - Line 1249: “similarto” → “similar to”\n    - and many more…", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily. Also thank you for pointing out the typos in our writing, we will correct them in future versions.\n\n1. Question (W1): Compactness of the input domain.\n\nThe current proofs are for the compact input domain. We will change $R^n$ to $[0,1]^n$ in the Introduction Section.  After evaluating the proofs, we find that only Theorems 5.1, 5.3, 6.1 still hold when we consider the distributions in $ R^n$. On the other hand, the extension to a larger domain $R^n$ is not a good idea, because networks with finite parameters can not approximate many of distributions over $R^n$, so that it is impossible to study guaranteed generalization theorems under such infinite domain, and th4.1, th4.3, th6.5 and th7.3 are incorrect on $R^n$. So, if we need to study about the distributions on $R^n$, we need to add more constraints to the distributions. \n\n2. Question (W2): Where comes the randomness in Theorem 4.1?\n\nThis randomness comes from a technique of memorization: in the construction of a memorization network, we require a special vector to compress data into one dimension, but this vector is not easy to calculate directly. However, every time we randomly select a vector, there is a non-zero (0.5) chance of selecting the required vector, and the randomness comes from this random selection. We have described this in lines 220-223 and 648-649 (and the proof above lines 648-649) of the paper. We will make this clearer in the revised version of the paper.\n\n3. Question (W3): Efficiency of memorization algorithm in Theorem 4.3?\n\nTheorem 4.3 is an existence result that mainly demonstrates the existence of $N_D$. The efficiency of the memorization algorithms are given in Theorem 6.5 and Theorem 7.3. If $para(L(D_{tr}))\\le N_D$, (2) of Theorem 6.5 shows that such memorization algorithms are not efficient.  If $N>O(S_D)$, then Theorem 7.3 shows that there exists an efficient memorization algorithm.  \n\n4. Question (W4): Parameter complexity of efficient memorization algorithm in Theorem 7.3.\n\nThe number of parameters are affected by the data distribution. In the worst-case, the network will have $O(N^2)$ parameters. As said in line 103-107, to ensure generalization, we abandoned many classic techniques, which resulted in an increase of parameters. We will add this information in the revised version. \n\n5. Question (Q1): Architectural constraint: ReLU network\n\nThe reason why we consider the fully connected ReLU network is because this type of network is very classic, and it has been widely applied in previous related research.  For other structure networks like CNN or with other activation functions, the conclusions in this paper may be different. The main results in the paper are based on the expressive power of the fully-connected ReLU network, such as VCdim, the ability to fit discrete points and so on, so after replacing the network structure, we can still use the ideas in the paper to re-establish the $N_D$, $S_D$ and so on. This is certainly an important direction for future research. We will mention this in the revised version of the paper.\n\n6. Question (Q2): There is an $\\epsilon^2$ gap between the upper and lower.\n \nYou are right. We want to mention that the lower and upper bounds are at the same order of magnitude for the number of samples $N^2_D$. We believe that it is still room to improve the factor $(1-2\\epsilon-\\delta)$ in the lower sample complexities. But currently, we do not achieve this yet.\n \n7. Question (Q3): How to get the proof of Corollary 6.4?\n\nAccording to Lemma E.2, for any $n,c$, we can find $2^{n/[c^2]}$ points with distance $c$ in $[0,1]^n$. Then we take suitable $n,c,k=2^{n/[c^2]}$ to make the contents in lines 1131 to 1133 of the proof of Theorem 6.1 valid. Finally, follow the part 2-4 in the proof of Theorem 6.1, according to line 1159-1162 and the begining of part 4, we can prove Corollary 6.4. We will add more details about the proof in the future.\n\n8. Question (Q4): Algorithm in Theorem 7.3 as an initialization. \n\nWe can only now provide some simple experiments. In the case of a small sample size, using our method as initialization for training may be helpful; while in the case of a large sample size, the training with random initialization can reach a very high level, so using our method for training does not bring significant improvement.\n\nWe do binary classification problems on CIFAR-10 dataset by considering 5 pairs binary classification problems: samples with label 2i and label 2i+1, where $i=0,1,2,3,4$. Randomly select 1000 samples from each category as the training set. We compare four methods: train a DNN, train a VGG-16, ours, training with our methods as initialization. The accuracies are given below.\n\n|Pair of Label|CNN|DNN|Ours|Ours+Training|\n|0,1|0.95|0.85|0.76|0.90|\n|2,3|0.84|0.73|0.59|0.75|\n|4,5|0.87|0.72|0.65|0.77|\n|6,7|0.98|0.84|0.69|0.84|\n|8,9|0.92|0.82|0.68|0.84|\n\nIt is easy to see that:\n(1): Our methods cannot go beyond training.\n(2): If the dataset is relatively small, using our method as an initialization can help improve accuracy.\n(3): Since the paper focuses on a fully connected network structure, its performance is inferior to that of CNN in image classification tasks.\n\n9. Question (Q5): Generalizability of memorization v.s. non-memorization networks. \n\nWe believe that a non-memorization network can generalize better than some memorization networks mainly in the following situation: The data set contains significant bad data, such as outliers. One weakness of memorization algorithm is that it must fit all the data, and the network will learn non-existent features from outliers, thus harming generalization. In this situation, a non-memorization algorithm can ignore the bad data in certain sense and thus work better.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "AG3612jLyI", "reviewer": "Reviewer_R3pV", "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.", "questions": "Major Comments:\n1. 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.\n2. 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.\n3. 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?\n\n\n\nMinor comments:\n1. 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": "See the Questions above.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Overall, the paper is well-written, the results are novel and comprehensive, and it makes a clear contribution to the theoretical community.", "weaknesses": "There are some comments, shown in the Questions below, but I recommend accepting this paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily.\n\nQuestion 1. Why consider the distribution D(n,c) defined in Definition 3.1? \n\nD(n,c) is indeed a distribution with relatively good properties, as we explain this in Remark 3.2 of the paper, there are three main reasons and advantages to use such a distribution: \n\n(1): Proposition 3.3 shows that there exists a distribution D not in D(n,c),  such that any network is not generalizable over D, so if conisdering general distributions, we cannot have a general generalization theory at all. \n\n(2): D(n,c) is suitable for most of real-world distributions, like image classification.\n\n(3): D(n,c)  is abstracted from previous related work. In order to achieve memorization with networks with sub-linear number of parameters, it requires that data has a positive separation bound, like [48] and [54]. So, when studying the distribution in $D(n,c)$, many related techniques and classic conclusions can be used in the memorization, such as [48] and [54], on the other hand, we need to point out that the existing conclusions cannot directly derive our theorem. \n\nFor the relationship between the parametric rate and error rate you mentioned, we need to point out that if we know which regions the network can correctly classify, we can indeed estimate the error rate using density. However, based on our research, we only know that the network has memorized a dataset, and we cannot directly obtain which regions the network can correctly predict. \nResearch on more complex distributions or noisy distributions can be a future research direction.\n\nQuestion 2. In Theorem 4.3, whether the memorization algorithm L is dependent on D, or at least c. It will be good if such an algorithm can obtain memorization agnostic to the knowledge of c.\n\nIn the proof, such algorithm is depended on c. But it is easy to make it no longer dependent on c, we will add an additional step to the memorization algorithm, we calculate the shortest distance $c '$ between two samples with different labels in the input dataset at first, easy to see that $c'\\ge c$, and then use $c'$ to replacing $c$ in the proof of th4.3. After doing this, such an algorithm is  completely only dependent on the input dataset, and for any distribution, there is an upper bound on the number of parameters of output network.\n\nThis is a good suggestion, and we will make modifications in future versions, thank you.\n\nQuestion 3. The upper bound and lower bound does not exactly match in its current form in terms of epsilon. \n\nYou are right that this lower bound only reaches tightness for $N^2_D$, but there is still room to improve the factor $(1-2\\epsilon-\\delta)$. But currently, we do not achieve this yet.\n\nQuestion 4. I think the introduction part can make a clear, or informal definition of what is generalization under the well-separated classification task.\n\nWe will do this in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MYBfkLTfWv", "reviewer": "Reviewer_QwyD", "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.", "questions": "Can estimates of $N_\\mathcal{D}$ and $S_\\mathcal{D}$ be provided even for simple toy examples (e.g., linearly separable data)?", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Solid mathematical paper with several novel results in DL theory. Mostly clearly written.", "weaknesses": "-\tThe significance of the theoretical results are not very clear because no estimates of $N_\\mathcal{D}$ and $S_\\mathcal{D}$ are given.\n\n-\tWriting 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "For Reviewer QwyD:\n\nThe authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily. Also thank you for pointing out the typos in our writing, we will correct them in future versions.\n\nQuestion 1. No estimates of $N_D$ and $S_D$  are given. Can $N_D$ and $S_D$ be provided even for simple toy examples (e.g., linearly separable data)?\n\n(1): The meaning of $N_D$ and $S_D$ in terms of generalization. $O(N^2_D)$ represents the minimum amount of data required for any memorization algorithm to achieve generalization, while $O(S_D)$ represents the upper bound of the amount of data required for achieving generalization by efficient memorization algorithms. We mainly pointed out the existence of these two values, but estimated them is not the core of the paper, the estimation of them can be a future work.\n\n(2): How big are $N_D$ and $S_D$? \nFirstly, in most cases, we have $N_D<S_D$, and $S_D$ is more susceptible to the influence of separation bound. Second, in the worst-case scenario, they are exponential in n, and this is inevitable as shown in Corollary 6.4, where a lower bound $2^{O(n)}$ for $N_D$ is given. Also, in line 1425, an upper bound $n^{O(n)}$ for $S_D$ is given. Third, for some ``good'' distributions, we believe that $N_D$ and $S_D$ are reasonably small, from the nice practical performance of deep learning and also be showen in the following simple example.\n\n(3): Can we calculate $N_D$ and $S_D$? Unfortunately, because these two values are closely related to the properties of the distribution $D$, calculating these two values for any distribution is not easy, as we said in line 405 to 406. But for some simple situations, we can estimate their values. We use linear data as an example to calculate $N_D$ and $S_D$.\n\nIf the distribution $D\\in R^n$ is linear separable and defined as: $x\\in[0,1]^n$ has label $1$ if $\\langle\\mathbf{1},x\\rangle>199n/200$, $x\\in[0,1]^n$ has label $-1$ if $\\langle\\mathbf{1},x\\rangle<n/200$, where $\\mathbf{1}$ is the vector whose weight is all 1.\n\nThen $N_D=O(n)$ because $D$ is linear separable. \n\nAnd $S_D=2$. Because the distance between the points with different labels is at least $0.49\\sqrt{n}$; and the distance between point with label 1 and point $\\mathbf{1}$ is at most  $\\sqrt{n/50}$; and the distance between point with label -1 and origin is at most $\\sqrt{n/50}$. By $0.49/3.1>\\sqrt{1/50}$, then let $S=\\\\{0,\\mathbf{1}\\\\}$ and by definition 7.1, we know that $S$ is a nearby set of $D$, then $S_D=2$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jMP354Bw5l", "reviewer": "Reviewer_8736", "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.", "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?\n\n- What is the size (num of parameters, width, depth) of the network defined in Theorem 7.3?", "limitations": "The authors discuss the limitations of their results.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- I think this research direction is novel and interesting. It puts a spotlight on memorization results, which may be efficient in terms of expressiveness but their generalization capabilities are unclear.\n\n- The presentation of the paper is good and it is easy to follow, while also providing sufficient proof intuitions.\n\n- Section 5 is particularly interesting since it shows the limitations of efficient memorization results, and specifically that memorization networks cannot generalize well.\n\n- Section 6 is also very extensive, and provides tight sample complexity bounds on memorization learning, that connects the size of the memorization network to the number of required samples for learning.", "weaknesses": "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:\n- Proposition 3.8 - where is the proof? Also, it is not clear to me why the constructions in [54,48] are probabilistic. \n\n- 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.\n\n- 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? \n\nSome minor comments:\n\n- 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.\n\n- In the main contribution, point 3, it is better to write lower bound is \\Omega rather than O.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors thank the reviewer for the valuable and insightful questions and hope that we have answered these questions satisfactorily.\n\nQuestion 1. Proposition 3.8 - where is the proof? Also, it is not clear to me why the constructions in [54,48] are probabilistic.\n\nWe deduce proposition 3.8 from the proof process of theorem in these papers, considering that proposition 3.8 can be directly obtained from the proof in the corresponding paper, the proof is not given. In the revised version of the paper, we will give a sketch of the proof for Proposition 3.8. This randomness comes from a technique of memorization: in the construction of a memorization network, we require a special vector to compress data into one dimension, but this vector is not easy to calculate directly. However, every time we randomly select a vector, there is a non-zero (0.5) chance of selecting the required vector, and the randomness comes from this random selection. We have described some similarities in the proof of Theorem 4.1, including lines 220-223 and 648-649 (and the proof above lines 648-649) of the paper. \n\nQuestion 2. There is something unclear about the proof of Theorem 5.3.\n\nThe $D_{tr}$ and $D$ used in our proof in Appendix E4 is the $D_{tr}$ and $D$ in Theorem 5.3, they can be any distribution $D$ and a dataset $D_{tr}$ selected from it, and we will clarify this point in the future. Our proof is for any distribution $D$. The core of the proof is in lines 1060-1065, and the proof in these lines applies to any distribution. Lemma E2 is also for any distribution $D$. Therefore, the whole proof is really for any distribution. In the revised version of the paper, we will make this clear.\n\nQuestion 3. The comparison between interpolation and memorization learning is unclear. Specifically, in what cases do the results on interpolation learning already provide generalization bounds for memorization learning?\n\nGeneralization bounds for interpolation learning are only established  in linear or approximately linear situations. Our sample complexity results are for all memrozaition networks and hence are valid in all cases.\n\nQuestion 4. Results and comparisons on implicit bias toward margin maximization of neural networks do not appear.\n\nThank you for pointing out this. There are many articles that analyze the margin maximization or generalization under gradient. These works can prove the results under some assumptions, such as NTK, Lip conditions, two-layer networks, etc., which are very good. In comparison, our results consider all the memorization algorithms and we have not made so many assumptions, so we  believe that our work has certain advantages. We will add these in the revised version of the paper.\n\nQuestion 5. The size of $N_D$ and $S_D$.\n\nFirstly, in most cases, we have $N_D<S_D$, and $S_D$ is more susceptible to the influence of separation bound. Second, in the worst-case scenario, they are exponential in n, and this is inevitable as shown in Corollary 6.4, where a lower bound $2^{O(n)}$ for $N_D$ is given. Also, in line 1425, an upper bound $n^{O(n)}$ for $S_D$ is given. Third, for some ``good'' distributions, we believe that $N_D$ and $S_D$ are reasonably small, from the nice practical performance of deep learning.\n\nFor some simple situations, we can estimate their values. We use linear data as a simple example to calculate $N_D$ and $S_D$.\n\nIf the distribution $D\\in R^n$ is linear separable and defined as: $x\\in[0,1]^n$ has label $1$ if $\\langle\\mathbf{1},x\\rangle>199n/200$, $x\\in[0,1]^n$ has label $-1$ if $\\langle\\mathbf{1},x\\rangle<n/200$, where $\\mathbf{1}$ is the vector whose weight is all 1.\n\nThen $N_D=O(n)$ for any $c$, because $D$ is linear separable. \n\nAnd $S_D=2$. Because the distance between the points with different labels is at least $0.49\\sqrt{n}$; and the distance between point with label 1 and point $\\mathbf{1}$ is at most  $\\sqrt{n/50}$; and the distance between point with label -1 and origin is at most $\\sqrt{n/50}$. By $0.49/3.1>\\sqrt{1/50}$, then let $S=\\\\{0,\\mathbf{1}\\\\}$ and by definition 7.1, we know that $S$ is a nearby set of $D$, then $S_D=2$.\n\nQuestion 6. What is the size of the network defined in Theorem 7.3?\n\nThe size of the network is affected by the data distribution. In the worst-case, the network has depth 3, width N, and $O(N^2)$ parameters. As said in lines 103-107, to ensure generalization, we abandoned many classic techniques, which resulted in an increase of parameters. We will add this information in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)