Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power

Thank you for acknowledging the novelty of our paper (especially in comparison to previous results) as well as for providing valuable feedback. Below we address the detailed comments, and hope that you can find our response satisfactory.

Question 1: Although the authors acknowledge that restricting the analysis to two-layer NNs is a limitation, there are some additional constraints in problem setups, such as focusing only on binary classification tasks and constraining the parameter space to $[-1,1]^{W_d}$ (in the proof of Proposition 3.2). It seems that these constraints are essential for the theoretical developments, and further relaxing these constraints does not seem straightforward.

Answer: These two constraints can be removed or reasonably relaxed as explained below.

(1) The assumption of binary classification can be removed. We use binary classification in this paper because the description of binary classification problems is very concise, and many previous papers have focused on binary classification. For multi-label classification, we can change the network output dimension and the loss function, and our proof ideas can be transferred to multi-label classification problems.

(2) The parameter domain $[-1,1]^{W_d}$ can be changed to $[-E,E]^{W_d}$ for some fixed $E\in R_+$. In order to ensure the existence of a network that minimizes the empirical risk, the parameter space must be a bounded closed set. Otherwise, the empirical risk can arbitrarily approach 0, but $argmin_{F} \sum_{(x,y)\in D_{tr}} Loss(F(x),y)$ is empty. Here is a short proof of this fact. Assume that $F$ satisfies $yF(x)>0$ for all $(x,y)\in D_{tr}$. Let $F_A(x)=AF(x)$ (only expand the value of parameters in the last layer by $A$ times) for any real number $A>1$. Then it holds that $\sum Loss(F_{A_1}(x),y)<\sum Loss(F_{A_2}(x),y)$ when $A_1<A_2$. Therefore, the empirical risk has no minimum value. On the other hand, in practice, the infinite norm of a network is easy to control and will not infinitely increase with the increase of the network. For example, use CIFAR10 to train ResNet18 with weight decay 0.0005, the $L_\infty$ norm of the parameters is smaller than $0.6$.

Question 2: My another concern arises from the use of Rademacher complexity to derive the lower bound on accuracy, which could be loose. Corollary 4.4 in this paper indicates that Theorem 4.3 requires the width and sample size to be sufficiently large for the lower bound to be non-vacuous (i.e., the lower bound itself is non-negative). Thus, outside the large-sample regime, Theorem 4.3 may lack practical relevance, limiting its applicability. In fact, considering that the paper already studies generalization for empirical risk minimizers, it might be more interesting to use bounds based on local Rademacher complexity rather than the original Rademacher complexity, which could give a decay rate of $O(1/N)$ instead of $O(1/\sqrt{N})$ for hypotheses with low risk or variance.

Answer:

(1) We believe that the statement by the reviewer that "outside the large-sample regime, Theorem 4.3 may lack practical relevance" is not complete. Large-sample size is actually a necessary condition for generalization. The main contribution of Theorem 4.3 is that the requirement for sample size $N\ge \Omega(...)$ and the requirement for the size of the neural network $W\ge \Omega(...)$ in Corollary 4.4 are separated and only depend on distribution itself, which is not the case in Theorem 4.8 (based on VC-dimension). In particular, this makes Theorem 4.3 consistent with the theoretical mystery of deep learning: “nice generalization ability of over-parameterized network” [1], whereas the VC-dimension based Theorem 4.8 contradicts this phenomenon, because $VC(H)=O(Wn)>N$ in the over-parameterized regime.

[1] M. Belkina,D. Hsuc, S. Maa, S. Mandala, Reconciling modern machine-learning practice and the classical bias–variance trade-off, 2019 (Fig. 1).

(2): Local Radermacher complexity can be used, but there exists other problems. Local Radermacher complexity is a complexity measure of the subspace composed of smooth functions in a hypothesis space, for instance the $f\in H$ satisfying $E(f^2)<r$. If we try to use local Radermacher complexity to prove Theorem 4.3, then we need to find a constant $r$ such that $E(f^2)<r$ for all these $f$ which can minimize the empirical risk based on a dataset i.i.d selected from distribution. The problem is that such an $r$ is quite big. It is easy to see that such an $r$ will depend on $W_0,c,n,W,\sigma$ (still use the symbol in Theorem 4.3). Then by the results shown in [2], the generalization bound is not more than $O(Rad(N,r)+\sqrt{rlog(1/Delta)/N}+log(1/Delta)/N)$. When $r$ is very big, the middle item involving $r$ will be a problem to achieve generalization.

[2]: P.L. Bartlett, O. Bousquet, and S. Mendelson, “Local Rademacher Complexities,” Ann. Statist., 2005.

(3): Regarding your concerns about the looseness of the bound, by using the technique from [3], we can obtain a generalization bound with a convergence speed of $1/N$. But there will be a serious problem: the sample complexity derived from this generalization bound still depends on the VC-dimension of the hypothesis space, which is avoided in our Theorem 4.3. Corollary 4.4 has already shown that the sample complexity obtained from our conclusion depends entirely on the distribution itself, which is an improvement compared to the existing results. An interesting problem is to find a generalization bound with faster convergence speed whose derived sample complexity only depends on the distribution itself? We currently do not have a particularly good idea for this issue.

[3]: E. Giné, V. Koltchinskii, Concentration inequalities and asymptotic results for ratio type empirical processes, Ann. Probab. 34 (3) (2006) 1143–1216.

Question 3: Along with the constrained parameter space, the input data space is assumed to lie within $[0,1]^n$. Is it possible to relax this requirement? I think normalizing input data to $[-1,1]^n$ is also common in practice.

Answer: This is not a strong assumption, as we can always transform the data to $[0,1]^n$. Actually, we can assume that the data is located in any bounded closed domain $[E,F]^n$ and the theory is still valid. Note that the universal approximation theorem is for compact domains, so the data must be in a bounded area.

Question 6. In the proof of Theorem 4.3, could you explain how the $L_{1,\infty}$ norm for the three transition matrices in Line 786 were obtained? Additionally, if input data is not restricted to $[0,1]^n$ and the parameter space is unbounded, can these $L_{1,\infty}$ norms still be derived? Furthermore, in Line 838-839, the inequality $S<NS^{kc/2+2}$ is only meaningful if $kc\ge 4$, as $|S|\ge N$ clearly holds. This is also implied in Line 853, where the lower bound would be vacuous for $kc\le 4$ since already holds trivially. Perhaps adding a condition such as $W\ge Frac{4(w_0+1)}{c}$ in the theorem statement might improve clarity.

Answer:

(1): The first transition matrices: this layer is the same as the first layer of $f$. Consider the bound of values of parameters of $f$, its $L_{1,\infty}$ norm is $n+1$.

The second transition matrices: Let the second transition matrices of $f$ be $W$, bias be $c$. Then the second transition matrices of $F$ is $W/k$, bias is $c/k+a/k$. Using the bound of value of parameters of $f$ and the value of $k$, we get the result.

The third transition matrix: It is $(1,1,\dots,1,-1,-1,\dots,-1)$, where there are $k$ number of 1 and $k$ number of -1 in it, and we get the result.

(2): As long as the range of data are bounded, it is fine, the difference in the final impact on the conclusion is a constant. If the value of parameters is unbounded, then there are no minimum empirical error, as said in the above questions.

(3): $K$ is directly related to the network width $W$. Because we study all $W$, it naturally includes some simple situations when $W$ is small, but we should focus mainly on the case where $W$ is large. We can add this assumption later.

Question 7: The motivation for the loose results in Section 5.1 is unclear.

Answer: Section 5.1 mainly explains the relationship between the lower bound of the sample complexity for a distribution and the network size required to express the distribution. For example, Corollary 5.3 indicates that for some data distributions requiring networks with width $W_0$ to express, there exists a network requiring at least $\Omega(nW_0)$ training data to ensure generalization, which give a NECESSARY condition for generalization.

However, in general, this relationship is difficult to obtain, so we were unable to provide a very tight conclusion. The given bounds, though relatively loose, are the first results of this type.

Our lower bound on sample complexity is entirely based on the cost of network expressed distribution. Although there have been previous studies on calculating lower bounds, there has been no work based on this, so our results are not well-known.

Question 8: In your abstract, you mention that the theoretical results in this work can provide insights into robust overfitting, but what you explore in Section 6.1 is not related to the robust overfitting phenomenon, which is proposed in [R1]. Perhaps "robust generalization", as used in the introduction, would be a more accurate term.

Answer: This is true, and we have modified these. Theorem 6.2 gives an upper bound for robust accuracy. Thanks.

Question 9: Some references are missing.

Answer: Thanks for pointing out the related works. We will provide a more detailed discussion on these related works in the next revision.

Question 10: The paper would benefit from substantial proofreading.

Answer: Thanks for pointing out these issues. We will correct them in the revision.

Question 4: In the proof of Proposition 3.2, it seems that the bounded domain of the parameter space play a critical role in proving the existence of an empirical risk minimizer. How would this apply to practical scenarios with an unbounded parameter space? Moreover, if the cross-entropy loss used in Proposition 3.2 has the reachable upper and lower bounds, does that imply it is also a "bad" loss function as defined in Definition 6.6?

Answer: (1) In order to ensure the existence of a network that minimizes the empirical risk, the parameter space must be a bounded closed set. Otherwise, the empirical risk can arbitrarily approach 0, but $argmin_{F} \sum_{(x,y)\in D_{tr}} Loss(F(x),y)$ is empty. Here is a short proof of this fact. Assume that $F$ satisfies $yF(x)>0$ for all $(x,y)\in D_{tr}$. Let $F_A(x)=AF(x)$ for any real number $A>1$. Then it holds $\sum Loss(F_{A_1}(x),y)<\sum Loss(F_{A_2}(x),y)$ when $A_1<A_2$. Therefore, the empirical risk has no minimum value.

(2) We say that a network $F$ can minimize empirical risk under a dataset when using cross-entropy loss, which means that $argmin_{f\in H} \sum_{L_{CE}(F(x),y)}$ is not empty.

In Definition 6.6, we say that a loss function $L$ is bad in (1) means $argmin_{x\in R}L(x,1)$ and $argmin_{x\in R}L(x,-1)$ have solutions for some $x$, which is not related to the dataset and network, only related to the function itself.

These two concepts are totally different and have no relationship.

Question 5: In the proof of Proposition 4.2, in Line 723-725. Could you clarify why the equality $F_A=F/A^2$ holds? In addition, if $A<1$, then each parameter of $F_A$ might exceed the domain [-1,1], it seems that the parameter domain constraint will be violated.

Answer: As said in the proof, $A$ is the maximal value of network $F$, where $F=\sum a_i Relu(W_ix+b_i)$ given by Theorem A.1 (Please note that the network considered in the work [George Cybenko 1989] does not have the last bias value $c$). Then $F_A=\sum (a_i/A)Relu((W_i/A)x+b_i/A)=\sum (a_i/A)Relu(W_ix+b_i)/A=\sum a_iRelu(W_ix+b_i)/(A^2)=F/(A^2)$. Because $|a_i/A|\le 1$, $||W_i/A||_\infty\le1$, $|b_i/A|\le 1$. So $F_A$ is what we want.

If we consider the last bias value $c$, then $F=\sum a_iRelu(W_ix+b_i)+c$. Also, let $A$ be the maximum value of network $F$. Then when $A\le 1$, $F$ is what we want. If not, let $F_A=\sum (a_i/A)Relu((W_i/A)x+b_i/A)+c/A^2=\sum (a_i/A)Relu(W_ix+b_i)/A+c/A^2=\sum (a_iRelu(W_ix+b_i)+c)/(A^2)=F/(A^2)$, and that is what we want.

However, you did remind us to only consider the situation where $A>1$, which we have added in the next version of the article.

We kindly invite you to review our rebuttal as the discussion period comes to an end. We also welcome your opinions on this paper or any questions we have not yet resolved.

Thank you for your reply. We would like to emphasize a few more points here:

1: Firstly, there are indeed many studies that have achieved a generalization bound convergence speed of $1/N$, and from this perspective, this is a weakness for us. However, the core purpose of this article is not to improve convergence speed, as mentioned in our article, the advantage of our generalization bound is

the number of data and network size is entirely on the denominator in the generalization bound,

, which was not achieved by previous generalization bounds, based on that, we can explain phenomena such as over-parameterized, and get the number of data and network size which depend only on the distribution required to ensure generalization.

2: Can we get a generalization boundary with a convergence speed of $1/N$, and guarantee the number of data and network size is entirely on the denominator in the generalization bound? At present, we do not know how to achieve it. The technique from [3] can not make the number of data and network size to be entirely on the denominator in the generalization bound, bacause VCdim is on the numerator. The Radermacher Complexity calculated during our proof does not consider the loss function, if the loss function is considered in local Radermacher Complexity, it is still hard to give the upper bound about $1/\sqrt{N}$ for $r$. More over, the resulting generalization bound also cannot make the number of data and network size to be entirely on the denominator in the generalization bound, bacause Rad(N,r) is on the numerator, such value is obviously influenced by network size. At last, because what we want to prove is a generalization bound for any network, and the PAC-Bayes technique is to prove the bound for most networks, so such techniques may not be applicable to us here.

This idea can be a future work.

Question 7: Under Theorem 6.2, it would be better to elucidate more on the dependency of $c_1$ on $\epsilon$.

Answer: We have add it in remark 6.3.

Question 8: In Proposition 6.5, how do the numbers "0.9" and "0.6" come out? Similarly for Theorem 6.7.

Answer: We use 0.99 to express high accuracy for some $f\in H_{W_0}(n)$, and it can be changed as $1-\delta$ for any $\delta$.

We use 0.6 to express low accuracy for any $f\in M_{W_0}( D_{tr},n)$, it can be changed as $0.5+\delta$ for any $\delta$.

We provide specific numbers only for simple expression and writing. We will add this information in the revised edition of the paper.

We thank you for acknowledging the novelty of our paper as well as providing the valuable feedback. Below we address the detailed comments, and hope that you can find our response satisfactory.

Question 1: The focus on two-layer networks might limit the applicability of the findings to more complex and deeper network architectures prevalent in practice.

Answer: First, it should be mentioned that many theoretical papers focus on two-layer networks, although lacking some practical applications, it can help understand and explain some phenomena in neural networks.

Second, extending our results to deep networks is actually a challenge; the real difficulty is how to ensure that sample complexity is independent of network size. At present, we do not have a way to achieve that. Moreover, because most theoretical analyses are difficult on the deep network, (without special assumptions), not just in terms of Radermacher Complexity, but also Gradient Descent Analysis, Robustness Analysis and so on, so it is not practical to directly use these methods, and new methods need to be developed to extend our result to deep network.

Question 2: The paper primarily focuses on theoretical analysis and does not include empirical studies to validate its claims and insights.

Answer: This is indeed a theoretical paper which provides a new and better generalization bound such that BOTH the network size and number of training data are completely in the denominator, as shown in Theorem 4.3.

For experiments in the revised paper, we can consider the following experiments: We training the network and control the absolute values of the parameters not more than 1 during training. Then we observe the relationship curve between the generalization and the network size, number of data. Contrast the relationship between this curve and Theorem 4.3.

Question 3: The assumptions on separable data distributions potentially oversimplifies the complexities of real-world deep learning applications. Why is "positive separation bound" important for the data distributions? How would the results change if the data distribution does not have a positive separation bound?

Answer: In fact, most classification problems are separable in the real world, such as MNIST, where different numbers cannot be infinitely close to each other.

We use the separability assumption because the distribution that satisfies this assumption must can be expressed by the network, as said in Pro3.2. In fact, the conclusion of Theorem 4.3 applies to all distributions that can be expressed by network even without separability.

If without such assumption, some inseparable data can lead to networks being unable to learn. Here is an example: we construct a distribution $D$ in $[0,1]\times\{-1,1\}$ which can not be learned by network.

The $(x,y)\sim D$ is: (1) Randomly select a number in $\{-1,1\}$ as the label $y$. (2) If we get $1$ as the label, then randomly select an irrational number in $[0,1]$ as samples $x$; if we get $-1$ as the label, then randomly select a rational number in $[0,1]$ as samples $x$.

Question 4: In Theorem 1.1, please clarify the meanings of "expressing the data distribution with a neural network" and "with high probability of a dataset".

Answer: Thank you, we have rewrite the th1.1 in the paper. ''expressing the data distribution with a neural network" means the definnition 4.1, ''with high probability of a dataset" means $1-\delta$ mentioned in th4.3.

Question 5: Under Theorem 1.2, what are the definitions of "robust memorizing" and "robust fitting"?

Answer: Robust memorizing means that the network is robust on a given dataset $D_{tr}$: $F(x+\epsilon)=y$ for all $||\epsilon||<r$ and $(x,y)\in D_{tr}$. Robust fitting is the same as robust memorizing. We will correct this problem in the revision.

Question 6: In Section 5, the authors provide an upper bound for accuracy without enough data. Could the authors relate the upper bound and the previously derived lower bound and have some discussions?

Answer: Our lower and upper bounds depend only on the cost required for the network to express the distribution itself, upper bounds for sufficient conditions for generalization and lower bounds for necessary conditions for generalization. They reflects the relationship between the amount of data required for generalization and the cost of expressing the distribution. We cannot make them equal yet. In the future, if we can make them equal, we have found the necessary and sufficient conditions for achieving generalization.

Thank you for appreciating our new contributions as well as providing the valuable feedback. Below we address the detailed comments, and hope that you can find our response satisfactory.

Question 1: Many grammatical errors and typos. Most of them are inconsequential for comprehension, but some actually make check the validity difficult: Line 723: “Miximum” is that a maximum or a minimum?

Answer: It is maximum. Sorry for that. We have modified these typos in the revised paper.

Question 2: Although the authors state their positive separation assumption in Definition 3.1, it would improve clarity if they repeated in the statements of subsequent theorems that they only apply to distributions that satisfy the separation. Same for Lin 304-305. The results are discussed as if they hold for any distribution, which is not true.

Answer: Thank you, we have already explained it in the new revised paper.

Question 3: Line 721: “for all $(x,y)$~$D$” is an odd statement. It is not clear whether the authors mean “surely” or “almost surely” with respect to distribution D.

Answer: ‘for all $(x,y)$~$D$’ has been replaced with 'with probability 1 under distribution D', we have modified these typos in the revised paper.

Question 4: The infimum in Definition 3.1 is not well defined. Is (z,-1)~D meant to signify any z in the support of D conditional on the label being -1? This needs to be clarified.

Answer: Yes, this represents any sample z with the label -1 selected from the distribution.

Question 5: The pervasive use of passive voice can be confusing. The authors use passive voice interchangeably for their own contributions, and for existing results (by other authors) in literature.

Answer: Thanks for pointing out the potential confusion caused by the frequent use of passive voice, such as lines 19–21. We will address this issue in the revised version.

Thank you for acknowledging the novelty of our paper as well as providing the valuable feedback. Below we address the detailed comments, and hope that you can find our response satisfactory.

We divide these questions into two sub-questions.

Question 1: This maybe not a significant contribution since it seems really natural. Intuitively, if the data distribution can be separated by a network, there must exist functions in the class of larger networks that can also separate the data distribution.

Answer: It is well known that the more data there is, the better the generalization, which is obvious. However, the specific amount of data required to achieve generalization is indeed of great research significance.

Similar, it is reasonable that distribution which can be expressed by small networks can be expressed by large networks naturally. However, the corresponding generalization bound and sample complexity need to be calculated to help us better understand generalization.

Question 2: And techinically, there are Rademacher complexity type bounds with sample complexity [1]. The only difficult of the main theorem is to estimate the Rademacher complexity of the class of larger ReLU networks.

Answer:

(1) The Rademacher complexity type bounds with sample complexity [1] are uniform bounds, that is, bounds are correct for all networks in the hypothesis space. But, our bounds are not uniform bounds and they are valid for those networks that minimize the empirical risks. The main difficulty of Theorem 4.3 is to use this condition to give a better generalization bound.

(2) We give a new and better generalization bound such that BOTH the network size and number of training data are completely in the denominator, as shown in Theorem 4.3. The sample complexity derived based on this generalization bound only depends on the distribution itself, which has not been achieved before, as shown in Corollary 4.4.

For example, the generalization bound based on VC-dimension in Theorem 4.8 contains the term $\frac{VC(H)}{N}$. This implies that over-parameterized models do not generalize, contradicting the experimental results that over-parameterized models generalize well [2]. However, our generalization bounds can be used to explain this important phenomenon.

(3) Extending our conclusions to deep networks is actually a challenge, the real difficulty is how to ensure that sample complexity is independent of network size. At present, we do not have a way to achieve that. Moreover, because most theoretical analyses are difficult on the deep network, (without special assumptions), not just in terms of Radermacher Complexity, but also Gradient Descent Analysis, Robustness Analysis, and so on, so it is not practical to directly use these methods, and new methods need to be developed to extend our result to deep network.

[2] M. Belkina,D. Hsuc, S. Maa, S. Mandala, Reconciling modern machine-learning practice and the classical bias–variance trade-off, 2019 (Fig. 1).

We thank the authors for the detailed responses. I will remain the score.

Question 3: What would empirical validation of these theories look like?

Answer: We can consider the following experiments: We training the network and control the absolute values of the parameters not more than 1 during training. Then we observe the relationship curve between the generalization and the network size, number of data. Contrast the relationship between this curve and Theorem 4.3.

Question 4: The hypothesis that some network exactly labels the data with a margin c is too strong in practice. This hypothesis rules out situations where there is label noise. It even rules out situations where there is no noise, but the decision boundary cannot be exactly represented by a neural network. (Approximation theorems do not help here.)

Answer: Firstly, we point out that in Proposition 4.2, we have already shown that all distributions with positive separation distances satisfy this assumption, so this assumption is not that strong as it appears.

Secondly, the confidence $c$ in Definition 4.1 must be incurred when considering minimizing cross-entropy empirical risks, because among all distributions that can be expressed by networks of the same size, some are easily learned by networks, while others are not. If we do not introduce $c$, it will lead to the same generalization bound for the distribution of those that are easy to learn and those that are difficult to learn, which is obviously unreasonable.

We give a simple example. Let $D$ be defined in $B_2(x_1,1)\cup B_2(x_2,1)$. The points in $B_2(x_1,1)$ have label 1. The points in $B_2(x_2,1)$ have label -1. When $||x_1-x_2||_2>2$, it is linearly separable.

For situations $||x_1-x_2||_2>>2$ and $||x_1-x_2||_2=2.01$, it is obvious that the first situation is easier to learn. Because for the first situation, minimizing the empirical error for any two points with different labels must lead to the linear function being able to separate these two spheres, because the dividing line created by the linear function is inevitably far away from these points and it will not divide a ball into two.

But when $||x_1-x_2||_2=2.01$, consider that these two balls are too close, so if the points are taken unevenly, it may lead to inaccurate delineation of the boundary between these two balls during minimize the empirical error and lead to bad generalization.

Thank you for acknowledging the importance of the problem studied in our paper as well as providing the valuable feedback. Below we address the detailed comments, and hope that you can find our response satisfactory.

Question 1: Perhaps the biggest issue is that there is no new insight here. The results are uniform convergence results and so it's not clear how they get around the roadblock identified by Nagarajan and Kolter (2022)'s work on uniform convergence not explaining deep learning. How do the results relate to Nagarajan and Kolter? How do you sidestep the issues they raise?

Answer: We believe that our results provide new insights compared to existing results in that we provide a better generalization bound that can be used to explain the over-parameterized models generalize well to some extent.

(1): In our generalization bound, BOTH the network size and number of training data are completely in the denominator, as shown in Theorem 4.3. And the sample complexity for generalization, the network size required for generalization got by our generalization only depended on the distribution itself(Corollary 4.4). Previous conclusions have been unable to achieve this point, such as the results mentioned in Nagarajan and Kolter (2022). This implies that when the size of the network and the number of training samples are both large, we have shown the generalizable of network, consistent with the theoretical mystery that over-parameterized models generalize well [1].

Our generalization bound is derived under the assumption that the $L_\infty$ norm of parameters $\le1$, which is reasonable in the sense explained below. By increasing the size of the network, it is easy to control the $L_\infty$ norm of the parameters after training not more than 1 and ensure the accuracy of the training set. For example, use CIFAR10 to train ResNet18 with weight decay 0.0005, after training, the $L_\infty$ norm of the parameters is smaller than $0.6$, and the network has accuracy 99$\%$ on the training set.

(2): The core contradiction pointed out in Nagarajan and Kolter (2022)'s paper is that: under big dataset, to get a better performance on a training set, training need to increase the norm of network weights, which in turn leads to an increase of the Radermacher Complexity, and thus will increase the generalization bound.

In fact, our bound is not UNIFORM in that it holds for neural networks that minimize empirical risk, and such problem does not bother us. Since the network size $W$ and number of training data $N$ are in the denominator of the generalization bound, so training the network will not lead to an increase in our generalization bound, so our results can truly explain practice.

Specifically, we use Theorem 4.3 to explain our results how to avoid Nagarajan and Kolter (2022)'s paper’s problem: We can use training to find a network with minimal empirical error, and we set the size of the network to be very large and limit the absolute values of the parameters during training such as weight decay. After training, we can obtain a large network with the $L_\infty$ norm of its parameters no more than $1$. Consider our generalization bound: the network size is completely on the denominator, so no matter how large the network, even if it far more the number of data in training set, it can only provide positive effects on the generalization. Therefore, our conclusion can fully demonstrate that large-scale but bounded-value networks must have good generalization performance.

[1] Belkina.et, Reconciling modern machine-learning practice and the classical bias–variance trade-off, 2019 (Fig.1).

Question 2: How do the results relate to Buzaglo et al (ICML 2024)?

Answer: In our opinion, our work has some similarities and many major differences with Buzaglo (ICML 2024).

Similarity: We both assume that distribution can be expressed by a network; we both try to find the sample complexity based on the expressive of distribution.

Differences:

(1): Our samples complexity only depends on data distribution and does not depend on the hypothesis space of networks (Corollary 4.4). This is the main contribution of our paper. But the sample complexity obtained by Buzaglo still depends on hypothesis space of network.

(2): Our paper focuses on the networks that make the empirical risk minimum (use cross-entropy loss), which does not imply INTERPOLATION. Buzaglo et al focus on INTERPOLATION network obtained by an algorithm designed by themselves, and such networks make the accuracy on training set to be 1 and they do not consider the empirical risk defined by cross-entropy loss. Therefore, our generalization bound is superior in terms of its applicability.

(3): We give the samples complexity to make $A_D(F)\ge1-\epsilon$ for all ERM networks, but Buzaglo et al just find the samples complexity to make their algorithm give a high accuracy network with high probability.

We kindly invite you to review our rebuttal as the discussion period comes to an end. We also welcome your opinions on this paper or any questions we have not yet resolved.

Key Question 1:

Please note that in lines 168-170 (revision), we have declared that the $L_\infty$ norm of network in H_W(n) is not more than 1. Based on this, we show how we get such three $L_{1,\infty}$ norm:

The first transition matrices: this layer is the same as the first layer of $f$. Consider the $L_{\infty}$ bound of values of parameters of $f$ is not more than 1, and the first transition matrix of $f$ has $n$ weights in each row, and with the bias added, there are a total of n+1 weights, so its $L_{1,\infty}$ norm is $n+1$.

The second transition matrices: Let the second transition matrices of $f$ be $W_f$, bias be $c$. Then the second transition matrices of $F$ is $W_f/k$, bias is $c/k+a/k$ or $c/k-a/k$. Using the bound of value of parameters of $f$ and the value of $k$, and $W_f$ has width $W$, so we get the result.

The third transition matrix: It is $(1,1,\dots,1,-1,-1,\dots,-1)$, where there are $k$ number of 1 and $k$ number of -1 in it, and we get the result.

Others Question: About the proof of Proposition 4.2.

Please note the Definition 3.1, we want distribution $D$ to satisfies: $inf _{(x_1,y_1),(x_2,y_2),y_1\ne y_2}||x_1-x_2||>0$. This actually implies that the distance between different label samples in distribution $D$ cannot be arbitrarily close to 0 (which means the gap you mentioned does exist), or there will be $inf _{(x_1,y_1),(x_2,y_2),y_1\ne y_2}||x_1-x_2||=0$. We will clarify this in the next version.

About Lemma B4. $b_i$ is a vector and so it doesn't have an $L_{1,\infty}$ norm.

In the whole proof, we see vector as a matrix with one column. More specific, we write one layer of a neural network is $Wx+b$, see $W,x,b$ as matrix, from the perspective of matrix multiplication, there are $W\in[-1,1]^{m,n}$, $x\in[0,1]^{n,1}$ and $b\in[0,1]^{m,1}$. So $L_{1,\infty}$ norm of $b$ is the maximum weights of $|b|$. We will clarify this in the next version.

Thank you for raising these questions. We will make modifications in future versions.