Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power
Authors: Lijia Yu
Yibo Miao
Yifan Zhu
Xiao-Shan Gao
Lijun Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: generalization bound
expressive power
Primary area: learning theory
TL;DR: We establish the generalization bound based on the expressive power for the network which minimize the Empirical Risk.

Abstract: The primary objective of learning methods is generalization. Classic generalization bounds, based on VC-dimension or Rademacher complexity, are uniformly applicable to all networks in the hypothesis space. On the other hand, algorithm-dependent generalization bounds, like stability bounds, address more practical scenarios and provide generalization conditions for neural networks trained using SGD. However, these bounds often rely on strict assumptions, such as the NTK hypothesis or convexity of the empirical loss, which are typically not met by neural networks. In order to establish generalizability under less stringent assumptions, this paper investigates generalizability of neural networks that minimize the empirical risk. A lower bound for population accuracy is established based on the expressiveness of these networks, which indicates that with adequately large training sample and network sizes, these networks can generalize effectively. Additionally, we provide a lower bound necessary for generalization, demonstrating that, for certain data distributions, the quantity of data required to ensure generalization exceeds the network size needed to represent that distribution. Finally, we provide theoretical insights into several phenomena in deep learning, including robust overfitting, importance of over-parameterization networks, and effects of loss functions.

Published as a conference paper at ICLR 2025
GENERALIZABILITY OF NEURAL NETWORKS MINIMIZ- ING EMPIRICAL RISK BASED ON EXPRESSIVE ABILITY
Lijia Yu', Yibo M Yifan Zhu Xiao-Shan 2. Lijun Zhang
Key Laboratory of System Software of Chinese Academy of Sciences Institute of Software, Chinese Academy of Sciences
2 State Key Laboratory of Mathematical Sciences
Academy of Mathematics and Systems Science, Chinese Academy of Sciences
University of Chinese Academy of Sciences
Institute of AI for Industries, Chinese Academy of Sciences
ABSTRACT
The primary objective learning methods generalization. Classic uniform gen- eralization bounds, which rely VC-dimension Rademacher complexity, fail to explain the significant attribute that over-parameterizee models deep learning exhibit nice generalizability. On the other hand, dlgorithm-dependent generaliza- tion bounds, like stability bounds, often rely on strict assumptions. To establish generalizability under less stringent assumptions, this paper investigates the gener- alizability of neural networks that minimize or approximately minimize empirical risk. We establish lower bound for population accuracy based on the expressive- ness of these networks, which indicates that with an adequate large number of training samples and network sizes, these networks, including ever-parameterized ones, can generalize effectively. Additionally, for generalization, demonstrating that, for certain data distributions, the quantity of training data required to ensure generalization exceeds the network size needed to represent the corresponding data distribution. Finally, we provide theoretical insights into several phenomena in deep learning, including robust generalization, importance of over-parameteriiztion,, and effect of loss function on generalization.
provide necessary condition
INTRODUCTION
Understanding the mechanisms behind the nice generalization ability of deep neural networks remains fundamental challenge problem in deep learning theory. By generalization, it means that neural networks trained on finite dataset give high predict accuracy on the whole data distribution. The generalization bound serves critical theoretical framework for evaluating the generalizability of learning algorithms. Let F be neural network, D the data distribution, and L(F(x), y) I(F(x)) y) where F(x:) is the classification result of F(x). For hypothesis space H and any F E H, with probability 5 of dataset D,, sampled i.i.d. from D, we have the classic uniform generalization bound (Mohri et al. 2018)
2eN E ((c.))>=(L(((()) v) (L..))e... < (8d d + In 3/N
4
(I)
where d the VC-dimension of H and N (D There exist similar generalization bounds using Radermacher Complexity (Mohri et al. 2018).
In practice, the generalizability of the networks trained by SGD is desirable. For that purpose, algorithmic-dependeet generalization bounds are derived. It is shown that if the data satisfy the NTK condition, two-layer networks have a small population risk after training (Jacot et al.) 2018 Ji & Telgarsky 2020). Stability generalization bounds also obtained by assuming the convexity and Lipschitz properties of the total loss (Hardt et al. 20166] Kuzborskij & Lampert] 2018).
"Corresponding author

---

Published as a conference paper at ICLR 2025
Unfortunately, uniform generalization bounds fail to explain the important phenomenon that over- parameterized models exhibit nice generalizability (Belkin et al., 2211), as pointed out by Nagarajan & Kolter (2019). For example, the VC-dimension is equal to the product of the number of parameters and the depth for ReLUU networks (Bartlett et al., 2021), which renders the bound in equation | useless for over-parameterized models. Most of the algoritmnic-dependent generalization bounds make strong and unrealistic assumptions. For example, the NTK condition is used to reduce the training a convex optimization ( & Telgarsky 2020) and the strong smoothness and convexity of the empirical loss are used to measure the effect in each training epoch (Hardt et al. 2016).
In order to give generalization conditions under more relaxed assumptions, we will study the general- ization of networks that minimize or approximately minimize the empirical risk, that is, the networks F E M = arg mingeH (x.,))ED.. (x)) y)- The approach is reasonable because most practical training will lead a very small empirical risk.
In this paper, we consider two-layer networks, like many previous theoretical works (Ba et al. 2020 Ji & Telgarsky] 20200 Zeng & Lam] 2022). From the perspective of expressive ability, we obtain a new type of sample complexity bound: when the number of training data and the size of the network are independently large enough, the network has generalizability. The sample complexity bound depends only on the cost required for the network to express the data distribution, shown below.
Theorem 1.1 (Informal, Corollary 4.5p. Lei data distribution DD satisfy the condition that a two-layer network with width Wo can reach accuracy 1 over D. Then with high probability of Dir DD, if N 2 ())) and (F)th(FF 2 Q( E M, then F has high population accuracy.
From this result, we can determine the amount of training data and the size of the network that can ensure generalizability. Because the requirements for N and (J) are independent, our bounds can be used to explain the nice generalizability of over- wver-parameterized models (Belkin et al. 2019). The above result is extended to networks that approximately minimize the empirical risk.
We also give a lower bound for the sample complexity. For some data distribution, to ensure the generalizability of network which minimizes the empirical risk, the required number of data must be greater than the size of neural networks required to express such distribution, as shown below.
Theorem 1.2 (Informal, Section 5). For some data distribution D, if the width required a two- layer network with ReLU activation function express DD is at least Wo. then with high probability for a dataset with fewer than O(Wo) elements, any network that minimizes the empirical risk over 'D has poor generalization.
Finally, while deep neural networks exhibit good generalization, numerous classical experimental results indicate that these networks encounter problems such robustness and generalization. We provide some interpretability for these problems based on our theoretical results. Let Drr be a dataset and J M. Then, three phenomena of deep learning discussed with our theoretical results.
Robustness Generalization. (Section 6. It is known that robust memorization for a dataset Dty is more difficult than memorization for Drr (Park et al. 2021 Li et al., 2022, Yu et al.) 2024a). We further show that when robust memorization of Drr is much more difficult than memorization of Drr, then the robustness accuracy of F over D has an upper bound which may be low, F has no robustness generalization over D.
Importance of wve-parrameterization. (Section 6.2 It is recognized that over per-parrmeterized networks have nice generalizaility (Belkin et al., 2019 Bartlett et al. 2021). In this regard, we show that when the network is large enough, small empirical loss leads to high test accuracy. In contrast, when the network F is not large enough, there exist networks that achieve good generalization but cannot be found by minimizing the empirical risk.
Loss function. (Section We show that for some loss function, generalization may not be achieved. the loss function has reached its minimum value or is strictly decreasing concave function, then the network may have poor generalization.
2 RELATED WORK
Generalization bound. Generalization bound is the central issue of learning theory and has been
studied extensively (Valle-Pérez & A. Louis 2022 The algorithm-independent generalization
2

---

Published as a conference paper at ICLR 2025
bounds usually depend on the VC-dimension or the Rademacher complexity (Mohri et al. 2018). In (Harvey et al. Bartlett et al. 2019 Yang et al., (023), the VC-dimension has been accurately calculated in terms of width, depth, and number of parameters. In (Wei & Ma 2019 Arora et al.)
2018 Li et al.
2018), tighter generalization bounds were given based on Radermacher complexity. Generalization bounds were also studied for netwoks with special structures: Longg & Sedghi (2019);
Ledent et al. (2021); Li et al. (2018) gave the generalization bound of CNN, Vardi et al. (2022) gave the sample complexity of small networks, [Brutzkus & Globerson (202T) studied the generalization
bound of maxpooling networks, [Trageer & Tewari (2024); Li et al. (2023) gave the generalization Ma et al. (2018): & Yang (2020p; | Ba et al. (2020) studied two-layer
bound of transformers, and Ma
(2017); 7 Barron & Klusowski (2018) : Dziugaite & Roy (2017); Bartlett et al. (2017); Valle- & A. Louis (022) gave the upper bounds of the generalization error. Generalization bounds based on information theory and Bayesian theory were also given (Alquier) 2024 Hellström et al. 2023] Tolstikhin Seldin 2013). Bayesian generalization bounds do not use VC-dimension or Radermacher complexity, but they hold only for most of the networks. Unfortunately, Nagarajan & Kolter (2019) show that the uniform generalization bound cannot explain the generalizability for deep learning.
networks. Under some assumptions for the networks, Neyshabur et al. [
Algorithm-dependeen generalization bounds were established in the algorithmic stability setting (Bousquet & Elisseeff 2002: Elisseeff et al. 2005 Shalev-Shwartz et al.] 2010). Under some
assumptions. Hardt et al. (2016); [ang & Ma (2022): Kuzborskij & Lampert 2018); Lei (002))
Bassily al. (2020) gave the stability bounds under SGD. For small networks, Ji & Telgarsky (2220);
Taheri & Thrampoulidis (2024); Li et al. (2020) proved the generalization of networks under some
assumptions. Farnia & Ozdaglar (202)); Xing al, (20TT): Xiao al. (2022); Wang et al. (2025);
Allen-Zhu & Li (2022) gave stability generalization bounds for adversarial training under SGD.
Regatti al. (2019); Sun et al. (2023) gave stability generalization bounds under asynchronous SGD.
However, these algorihhmi--deendeen generalization bounds always impose strong assumptions on the training process or dataset. Generalization bounds for memorization networks were given in Yu al. (2024b). However, minimizing empirical risk for cross-entropp loss does not necessarily lead to memorization, so our assumption is weaker than memorization.
Interpretability for Deep Learning. Interpretability is dedicated to providing reasonable expla- nations for phenomena that occur in deep learning. In (Zhang et al. 2021) it was pointed out that interpretability is not always needed, but it is important for some prediction systems that are required to be highly reliable. For adversarial samples, it was shown that for certain data distributions and networks, there must be trade-off between accuracy and adversarial accuracy (Shafahi al. 2019 Bastounis et al., 202T). In (Yu et al. 2023), ), it was proven that a small perturbation of the network parameters will lead to low robustness. In (Allen-Zhu & Li 2022). it was shown that the generation of adversarial samples after training is due to dense mixtures in the hidden weights. In (Yu et al.) 2024a]
Li al., 2022). it was shown that ensuring generalization requires more parameters. For overfitiing. long-term training has been shown to lead to decrease in generalization (Xiao et al. 2022 Xing
cet al. 2021 In (Roelofs et al. 2019). comprehensive analysis of overfitting was given. In (Belkin et al. mentioned, and in Arora et al. (2019); Cao & Gu (2019): Ji & Telgarsky (2020), the training and
2019 Bartlett et al.) 202 the importance of over-parameterized interpolation networks is
generalization of DNNs in the over- wer-paramettriieed regime were studied. In this paper, we explain these phenomena from the perspective of the expressive ability of networks.
3 NOTATION
In this paper, for any A E R. (A4) means a real number no more than CA for some e and ((A) means real number not less than cA for some e <>> 0. By saying that for all (z, y) ~ 'D there is an event A, we mention IP ((axa))((A)) =
3.1 NEURAL NETWORK
In this paper, we consider two-layer neural networks F R" + E that can be written as:
F(x) = EW" (W + b.) + c,
where a is the activation function, W. E glx= is the transition matrix. by E R is the bias part, W is the width of the network, and a; e E R. Denote H., (n) the set of all two-layer neural networks
3

---

Published as a conference paper at ICLR 2025
with imput dimension n, width W, activation function 0, and all parameters are in 11. To simplify the notation, we denote HRe.. (n) by Hw (12) when using the ReLU activation function.
3.2 DATA DISTRIBUTION
In this paper, we consider binary classification problems. To avoid extreme cases, we focus primarily on the data distribution defined below.
Definition 3.1. For n E Z+. P(n) is the set of distributions D over [0, 1]a x 13 that have positive separation bound: inf (21. (a) and in zuz ||æ| ø2l12 > 0.
Remark 3.2. Equivalently, distribution that has positive separation bound means that there exists c > 0, such that ||= 22|l2 > c for all (I1, 31), (I2, y2) ~ 'D where /1 + 1/2-
The accuracy of a network F on distribution D is defined as AD(F) = P(a.y) - ((gn((((s)) = v). where Sgn is the sign function. We use Dur DN to mean that Die is dataset of N samples drawn i..d. according to D.
3.3 MINIMUM EMPIRICAL RISK
Consider the loss function L(F(z),)) v) = In(1 1ellee--i -F(())),, which is the cross- cross-entropy loss for binary classification problems. For dataset Der C [0. 1]" [-1, and hypothesis space Hip((n), To learn the features of the data in Dtr, the general method is empirical risk minimization (ERM), which minimizes empirical risk on the training dataset L(,,))D. [(F(x). y) of the network F.
In this paper, we mainly consider networks F Fel (n) that can minimize empirical risk, that is, networks in
Mir n)) arg minge (n)
Σ
L(g(z),))
(a.y)EDDor
It should be noted that such networks exist in most cases, shown below.
Proposition 3.3. Let Drr [0, {-1, and be continuous function. Then for any W E Z+, there exists an F E Hiy such that F E My (Drr.
Proof. Since is a continuous function, the empirical risk E(an)D, ((F()).))
E(gg)ED, In WEEW (W, is a continuous function the network parameters a, b,, c and W; The proposition now comes from the fact that continuous functions have reachable upper and lower bounds on closed domain [-1, 1]", of the parameters, where W,, W(n + 2) + 1 is the number of parameters of F.
GENERALIZATION BASED ON NEURAL NETWORK EXPRESSIVE ABILITY
In this section, we demonstrate that, based on the expressive ability of neural networks, the generaliz- ability of the network that minimizes the empirical risk can be established. Specifically, in Section 1, we establish the relationship between expressive ability and generalizability. In Section 4.2, we extend our conclusion to networks that approximately minimize empirical risk. In Section 4.3, we compare our generalization bounds with existing generalization bounds, showcasing the superiority of our bound.
4.1 A LOWER BOUND FOR ACCURACY BASED ON THE EXPRESSIVE ABILITY
We first define the expressive ability of neural networks to classify the data distribution.
Definition 4.1. We say that a distribution over [0, 1 x {-1,1} can be expressed by Hy, with confidence c, if there exists an F Hy such that
P ((en)D(yF(()) 2 2) =
4

---

Published as a conference paper at ICLR 2025
Remark 4.2. The smallest W that D can be expressed by Ha with confidence can be considered as a complexity measure of distribution D under confidence с and activation function d.
For any distribution D E [m), we can always find some activation function Ø, such that D can be expressed by H (12) with confidence for some W and c. Therefore, this definition is reasonable. For example, if o ReLU, according to the universal approximation theorem of neural networks (Cybenko ) any D D(n) can be represented by network with ReLU as activation function, as shown by the following proposition. The proof is given in Appendix
Proposition 4.3. For any distribution E D(n), there exist W N+ and e > such that 'D can be expressed by Hw (n) with confidence
We have the following relationship between expressive ability and generalization ability. The proof is given in Appendix B
Theorem 4.4. Let a be continuous function with Lipschitz constant Ly and D E D(n) be expressed by H with confidence c. Then for any W 2 W + 1, N E N4, 8 E (0, 1), with probubility at least 1 - 8 Der ~ DD, the following bound stands for any F E MW (Dtr,))
Wo CW +
nIIp (Wo c) Voog(nn)
In(2/0)
A 1
cVN
Proof Idea. There are two main steps in the proof. The first step tries to estimate the minimum value of the empirical risk, which mainly uses the assumption: D can be expressed by H with confidence The minimum value is based on Wo, W. Then, we use the minimum value to estimate the performance of the network on Dtr. In the second step, we can use the result the first step and the classic generalization bound to estimate the performance of the network across the entire distribution and get the result. The core idea of this step is that the minimum value of empirical risk does not depend on N, but the Radermacher complexity becomes smaller when increasing N. Then, when N is large enough, the performance of networks in 'D and Dr, is similar.
Some experimental results used to verify Theorem 4 are included in Appendix L Formula differs from the classical generalization limits in that both the number of samples N and the size of the network W are in the denominator, and therefore increasing N and W independently leads to better test accuracy. As consequence, the generalization ability of weer-parameterizee networks can be explained. Since the values of N and W ensure generalization are only influenced by the size required for the network to express the data distribution, we can infer the following corollary.
Corollary 4.5. With probubility - 6 of Der ~ D', holds AD(F) 2 1 é for any F E Mú, (Di,,, n), when W 2 ((Wo/ and N 2 2 Ln(Wotc)nn/logtam )2 + 22 (0(111//))
The above condition for generalization is different from traditional sample complexity in that be- sides the requirements on the number of samples, new requirement the size of networks is given independently, which is the reason to explain the generalization ability of over-parameterized networks.
Remark 4.6. For networks with depth larger than two, we can show that the depth and width of the network and the number of data exceed distributiio-deeenddee threshold, then with high probability, the network minimizing the empirical risk can ensure generalization, as demonstrated in Appendix K However, due to the complexity of deep networks, accurately determining the required depth, width, and data volume remains a challenge.
4.2 GENERALIZATION OF NETWORKS APPROXIMATELY MINIMIZING EMPIRICAL RISK
In practice, it is often challenging to find the networks that accurately minimize empirical risk. In this section, we show that for networks that approximately minimize empirical risk, its generalization can also be guaranteed the value of the empirical risk small. We define such set of networks.
Definition 4.7. For any 2 1 and dataset Drr, say F Hy (n) is g-approximation of minimizing empirical risk if
Σ T(F(x).v) S min (
Σ M((().v).
JEHG (m) (I.
5

---

Published as a conference paper at ICLR 2025
For all q- q-approximation networks, we have the following result. The proof is given in Appendix C Theorem 4.8. Let be continuous function with Lipschitz constant Lp and D E =(()) be expressed by Hw: with confidence c. Then for any W 2 Wo + 1, N E N+, 2 and ő E (0,1), 1). with probability at least 1 - 8 Dr ~ DA, we have
AD(F) 2 1- 0 gWo n.p(WWo + c) (og((n) cW
In(2/5)
c/N
N
for any g-approximation F Hiy (n) minimize the empirical risk.
The conditions of the above theorem can be achieved much easier than those of Theorem 4.4 because we do not need F to achieve any local or global minimum point, but only need to have small empirical risk.
4.3 COMPARISON WITH CLASSICAL CONCLUSIONS
In this section, we compare our generalization bounds with previous ones, Compared to algorithm- independent generalization bounds, our bound performs better when the data size is not significantly larger than the network size. Compared aggorthmm-deennden generalization bounds, our bound does not require overly strong assumptions as prerequisites.
Compare with the algorithm-indeependent generalization bound. When the scale of the network is bounded, a general generalization bound can be calculated by the VC-dimension.
Theorem 4.9 (P.217 of (Mohri et al.
2018 Informal), Ler Der ~ DN be the training set. For the RR -
hypothesis space H [Sgn({(x))
x
R.) and ō TR,,, with probability at least
for any Sgn F (x)) E H, we have
VC(H) + 11((1/8)
(AD(Sgn(F)) (aa.,)e,, [I(g[n(((()))) b)ll s O(y
N
When considering the local VC-dimension, we have the following result (Zhivotovskiy Hanneke 2018 Under Massart's ss bounded noise condition, let FD., be the network that has the highest accuracy over Dtr Then with probability 1 â of Dar ~ holds
VC(H) log (N/v(H())))) + log(1/0)
Ap(FD..) 2 - 22(
N
Theorem 4.9 points out that when the number of data is much more than the VC-dimension of the network hypothesis space, generalization can be ensured. Since the VC-dimension generally larger than the number of parameters of the network (Bartlett et al.) 2019), Theorem 4.9 means that to ensure generalization, the number of data must be greater than the number of parameters of the network, which is contradictory to the fact that over wee-pparamtterized models have nice generalizability (Belkin et al. 2019 Bartlett et al. 2021). Similar results hold for the generalization bound based on Radermacher complexity, due the observation that the Radermacher complexity for deep networks close to 1 (Zhang et al., 2017). On the other hand, our generalization bounds Theorem 4.4 can be used explain the fact that over-parameterizze models have nice generalizability.
Compare with the algorithm-dependent generalization bound. In the study of algorithm- dependent generalization bound, some works derive generalization bounds based gradient descent under strong assumptions not met by neural networks.
Theorem 4.10 Ji & Telgarsky (220)). Let e E (0, 8 (0,1/4) and distribution D over [0, 1]"d satisfy the NTK conditions with constant 7, Let X +2 and M 4096X² If the 70
7/1
two-layer network with width W > M and training step 1 I 1, with probability 1 1 48 of Der ~ D and training initiation point, after most ne
2x times gradient descent on Dtr, it holds for the trained
network FF
2
2 + In(4/c)
(n(2/8)
Ap(F) 2 - 2 16
6v
//N
N

---

Published as a conference paper at ICLR 2025
Theorem 4.10
requires NTK conditions for distribution. These conditions can lead the training approach to convex optimization, which is an overly strong condition. Theorem |.4 only requires that network interpolates the positive separation distribution, and it stands for any distribution D D(n) as mentioned in Proposition 4.3 Stability bounds represent another algorithn-dependen approach to generalization bound, shown below:
Theorem 4.11 (Theorem 3.7 in Hardt et al. (2016)), Assume that for every sample (z, y), L(Fo(x), y) as a function based 0 is B-smooth, convex and L-Lipschitz. Let F* be the network obtained by training on dataset Drr by using SGD T times and each step size 0₁ < 2/3. Then we have
E ED SGD
1 N
Σ (2.))ED(>
L(F"(x).)) - (F).
2T.2 Σ
N
Theorem 4.1 requires convex and smooth conditions for the loss function which are not satisfied by neural networks. Also, the Lipschitz constant is directly related to the network size, which cannot explain the over-parameterization phenomenon. In Theorem 4.4 there is no such problem because the network size W is in the denominator.
Compare with the PAC-Bayes-Ke Bound. Consider the following Bayesian generalization bound: Theorem 4.12 Tolstikhin & Seldin (2013)). For any fixed distribution π over hypothesis space H and a distribution p over H. with probability at least Dtr 'DN, we have
(L(pIT) + ((n(N/8))
BF= Bies v)]l - Baa-Deaa
[L(F(x).)))] [L
N
where KL is the Kullback-Leible divergence.
The result estimates the overall generalization bound of networks in the hypothesis space based on distribution. In contrast, we attempt to provide estimates for networks minimizing the empirical risk.
LOWER BOUND FOR SAMPLE COMPLEXITY BASED ON EXPRESSIVE ABILITY
In this section, we consider the lower bound of data complexity necessary for generalization, similar to Section 4 the lower bound of data complexity which we are looking for should only rely on the distribution itself but not rely the hypothesis space, such as the result in (Wainwright 2019).
5.1 UPPER BOUND FOR ACCURACY WITHOUT ENOUGH DATA
This section illustrates that in the worst-case scenario, the minimum number of data needed to guarantee accuracy is constrained by the VC-dimension of the smallest hypothesis space necessary to represent a distribution. We give a definition first.
Definition 5.1. For hypothesis space H C R" + I, VC(H) is the maximum number of data in VC(H)
[0, 1]" that H. can shatter. Precisely, there exist VC(H) samples {= c [0, 1)", such that for
VC(H) E 1),,1), there is an F E H such that (gn(F(z,)) = for all i E [vC(H)). But there do not exist VC(H) + such samples.
any {y:). )-))
We have the following theorem. The proof is given in Appendix D
Theorem 5.2. For any n. W, Wo E N+ and activation fanctiinnnnnionn o, there is a E D(n) that satisfies the following properties.
(1) There is an F E &H Wy (n) such that AD(F)=1 1
- 4e (2) For any given e, E (0, 1), N S VC(HG, (1 - Dir ~ DN, we have AD(F) < 1 f some F E Miy--(Dr..
then with probability 8 of
The theorem indicates that for distributions that require networks with width Wo to express, some of them require at least 92 (2V W. (n)) training data to ensure generalization. It is worth mentioning that this conclusion is true for any given W in the theorem. It easy see that a larger Wo makes VC(H;, W, (n)) larger, so as the cost of expression increases, generalization becomes difficult. However, it is difficult to accurately calculate VC(HG, (n)) for general a. If we focus on ReLU networks, by the result in (Bartlett et al. 2019, we have
7

---

Published as a conference paper at ICLR 2025
Corollary 5.3. For any given W, Wo E N4. there is D E D(n) that satisfies the following properties.
(1) There is F E (n) such that (D(F)= =1.
(2) For any given e, E (0. 1), if & O(nWo(1 4e 6)), then for all Drr ~ DN, it holds AD(F) < 1ff some F (D,,),
Besides, for any distribution, we can show that the parameters required express a distribution tend to infinity, the required number of data to ensure generalization for such distribution must also tend to infinity. As shown in the following theorem. The proof is given in Appendix
Theorem 5,4. Suppose E (n)), Wo 2 2n+1, and AD(F) & 1 - for any e and F E Hw, (n). N S W (n + 1)/e, then for any Der ~ DN and W E N4, there is an F E (Dw,Dr n) such that AD (F) S1-c
However, since Theorem 5.4 correct for all distributions and datasets, can only provide a relatively loose bound. If the distribution is given, calculate the relationship between the minimum number of data required and the minimum number of parameters required to fit it, as shown in the following section.
5.2 APPROPRIATE NETWORK MODEL HELPS WITH GENERALIZATION
As mentioned in the previous sections, expressive ability and generalization ability are closely related. Section [.1 demonstrates that simpler expressions facilitate generalization; Section [.1 reveals that, in the worst-case scenario, the amount of data required to guarantee generalization is at least the VC-dimension of the hypothesis space that express the distribution.
Therefore, for given distribution, selecting an appropriate network model that can fit the distribution easily may help facilitate better expression with fewer data and network size, ultimately leading to improved generalization. In this section, we illustrate that selecting an appropriate activation function for the neural network according to the target distribution enhances generalization.
To better explain this conclusion, us examine the following distribution.
Definition 5.5. Let Dr, be distribution defined over {{ 1, T(O)) where 1 is the vector with all one entries in IR." T((r)) = 1 if x: is odd and [(x:) 1 if is even, and the probability of each point is the same.
As shown below, ReLU networks need (()) width express this distribution and require 2(n) data to ensure generalization. The proof is given in Appendix F
Proposition 5.6. (1) For any n,, AD, < 1 for any F E Hw (n) when W n/2:
(2) N < ón where ó E (0, 1), then all Drr ~ D.N and 144, it holds AD(F) S 0.5 + 28 for some F E Mw(D,,, nt).
But if use the activation function (xr) (in() the networks only need O(1) width to express such distribution and require fewer data to ensure generalization. The proof is given in Appendix G
Proposition 5.7. (1) For any n, D, can be expressed by (n) with confidence 1;
(2) For any W 2 2,n > 2, 8 E (0, 1) and N 2 ln(5/2) 1/m0) with probability 8 of ~ DN
holds Ap(F) = for all F E M (D.r, n).
As shown in the above example, using (Ix) sin(xx) as the activation function, it only requires (In(8)) samples and O(1) width to ensure generalization, but ReLU networks require at least ((n) samples and width to ensure generalization. This demonstrates the crucial role of selecting the appropriate network models.
Remark 5.8. It is worth mentioning that for some very simple distributions like the Bernoulli distribution, the performance of various activation functions similar, so we cannot provide a general conclusion for any distribution.
8

---

Published as a conference paper at ICLR 2025
6 INTERPRETABILITY OF SOME PHENOMENA IN DEEP NEURAL NETWORK
Although networks minimizing empirical risk are good for generalization, many classic experimental results have shown that networks still have problems. this section, we will provide interpretability for some classic experimental results based our theoretical results.
6.1 WHY DO GENERAL NETWORKS LACK ROBUSTNESS?
Experiments show that deep neural networks can easily lead low robustness accuracy (Szegedy et al. 2013). In this section, we provide some explanations for this fact.
The robustness accuracy of network F under distribution DD and robust radius is defined as
RobD,c(F) = ((..))> (TFF(2)) = v), Va' E BBx,, n 1)))
The robustness accuracy requires not only correctness on the samples but also correctness within neighborhood the sample. We introduce a notation.
Definition 6.1. For a dataset Dir w:) and an > 0, define
R(Der, c) (Dr D. = Drr U [(E c. w)) for some ||</|| <)}.
It is easy see that R(Der, e) contains all the data formed by adding perturbation with budget e to Dtr. In the above section, we mainly discussed the network expression ability in distribution. On the other hand, there are also some studies the network expression ability dataset such as memorization. Moreover, previous studies (Park et al. 2021 Li et al.. 2022 Yu et al. (024a) have shown that robustly memorizing a dataset may much more difficult than memorizing dataset. So, for a given hypothesis space H that can express a normal dataset well, it may not be able to express the dataset after disturbance. In this case, order minimize the empirical risk, the network will prioritize simple features that are easy to fit, but will ignore the complex robust features, which leads low robustness, as shown in the following theorem. The proof is given in Appendix H
Theorem 6.2. Let D E D(n) and Lp be the Lipschitz constant of activation function a. No. Wo N+ and e, 6, co. C1 0 satisfy that with probability 1 - 8 of Dir DNo, , it holds
(1) there exists an F E Hw, (n) such that yF 2 co for all (x, v) E Deri
(2) there exists a D, E R(Drrr E), such that E(E)))D
xF(x)
TD. S for any F E HW, (n))
Then, for any W Wo with probability
(8)) of Drr Doo and F M (Dtr, n),
have Robp, (F) S 22( ce-201 nL,
ln(n/d) No
whp Wo
W.
This theorem implies that if the dataset after adding perturbations becomes more difficult to fit, the network may have a low robustness generalization. Please note that affects the conclusion implicitly, because C1 is related to e. Remark 6.3. Conditions (1) and (2) required in the theorem are reasonable. increases, C1 will decrease and when is large enough, have > C₁ 0. Hence, in some situation, small e is also enough to make co > C1. such as the example given in the proof of Theorem 4.3 in (Li et al. 2022).
obvious that as
6.2 IMPORTANCE OF EVEE-PARAMETERIZEI NETWORKS
In the above section, we mainly consider F Mw n). But what we really need is F E arg max (n)- Ag)).. By Theorem 4.4 it is easy to show that when the number of data and the size of the network are large enough, the generalization of F E Mw n) and F E arg max (m) (g) are close, as shown below. Following Theorem 4.4 we have
Corollary 6.4. For all Ji E Mw (Der, n)) and Fg arg maXgeHw (n) Ap()) it holds (AD(F2)
Ap(Fi) 0 Wi cW + nLy(Wo+e)) [log(an) c/N
In(2/8)

---

Published as a conference paper at ICLR 2025
Proof. Since > AD(F2) 2 AD(F)), we have (Ab(F2) - Ap(Fi) S 11 AD(F), and by Theorem 4.4 we obtain the result.
The above corollary shows that if the size of the network is large enough, the gap will be small. In the following, we point out that for some distribution D, if the size of network is too small, even with enough data, it may lead large gap of (D())) AD(F.. This emphasizes the importance of over par--aaarmtteitiionnn as shown below. The proof is given in the Appendix [|
Proposition 6.5. For some distribution D ((n). there is Wo 0, such that
(1) There exists an F (n) such that AD(F) 2 0.99.
(2) For any ó > 0, iNN Qnn In(n/6)), with probability 1 O()) of Dr, DA, we have AD(F) S 0.6 for all F E Mw. (Der, n).
Remark 6.6. In Proposition 6.5 0.99 can be changed to any real number in (0, 1) and 0.6 can be changed to any real number in (0.5, 1), and the result is still correct.
By Corollary 6.4 large width does not make (2) in Proposition 6.5 true. So, the above conclusion indicates that for some distributions, when the network is not large enough, even there exist networks with high accuracy, they cannot be found by minimizing the empirical risk. The distribution considered here contains some outliers. In order to fit these outliers, the small network must reduce generalization.
6.3 THE IMPACT OF Loss FUNCTION
In order to ensure generalizability of the network after empirical risk minimization, it is necessary to choose an appropriate loss function because minimizing some types of loss function not good for generalization. In the previous sections, we mainly discussed the crossentropy loss function. In this section, we point out that not all loss functions can reach conclusions similar to Theorem 4.4 Definition 6.7. We say that the loss function La IR2 >> IR is bad if (1) or (2) is valid.
4.4
(1) There exist 11 IR such that Lo(x-1, 1) min.eR Ls(x, -1) and Ls(x1, 1) minzeR Ls(x, 1).
(2) L)(F(x),)) d(FF(x)) where & is strictly decreasing concave function.
Condition (1) in the definition means that the loss function can reach its minimum value and condition (2) means that the loss function is concave function. Some commonly used loss functions, such as the MSE loss (Fsx(F(F), y) [1F(x) vl12. or Ly (F(x).)) (xx) are all bad loss functions.
For such bad loss functions, we have Theorem 6.8. For any and bad loss function Ls, there is a distribution D D(n) satisfying the following property. For any 2 0, there is a Wo 2 0, such that W 2 Wo. then with probability 0.99 of D,, D., we have AD(F)= < 0.5 some F E arg mingeHw (x) Ee La (g() v).
This theorem means that to ensure generalizability, it is important to choose the appropriate loss function. The proof is given the Appendix [
7 CONCLUSION
In this paper, we give a lower bound for the population accuracy of the neural networks that minimize the empirical risk, which implies that as long as there exist enough training data and the network is large enough, generalization can be achieved. The data and network sizes required only depend on the size required for the network to represent the target data distribution. Furthermore, we show that if the scale required for the network to represent a data distribution increases, the amount of data required to achieve generalization on that distribution will also inevitably increase. Finally, the results used to explain some phenomena in deep learning.
Limitation and future work. Although considering 2 layer networks is quite common in theoretical analysis of deep learning, is still desirable to extend the result to deep neural networks. Preliminary results for deep neural networks are given in Appendix K which need to be further studied. A more accurate estimate of the cost required represent given data distribution is needed.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work is supported by CAS Project for Young Scientists in Basic Research, Grant No. YSBR-040, ISCAS New Cultivation Project SSCAS-PYFX-202011 and ISCAS Basic Research ISCAS-JCZD. 202302. This work is also supported by NSFC grant No. 12288201 and No.92270001, and grant GJ0090202. The authors thank anonymous referees for their valuable comments.
REFERENCES
Zeyuan Allen-Zhr and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp- 977-988. IEEE, 2022.
Pierre Alquier.
User-friendly introduction to pac-hayes bounds. Foundations and Trends@ Machine Learning, 17(2):174-33)) 2024.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp. 254-263. PMLR, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grainee analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference Machine Learning, pp.
PMLR, 2019.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang. Generalization of two-layer neural networks: An asymptotic viewpoint. In International conference learning representations, 2020.
Andrew R Barron and Jason M Klusowski. Approximation and estimation for high-dimensional deep learning networks. arXiv preprint arXiv:1809.03000 2018
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally normallzee margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Peter L Bartleu, Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-233) -2001, 2019.
Peter L Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta numerica, 30:87-201, 2021.
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-4391, 2020.
Alexander Bastounis, Anders C Hansen, and Verner Vlačíć. The mathematics of adversarial attacks in ai-why deep learning is unstable despite the existence of stable neural networks. arXiv preprint arXiv:2109.06094 06098, 2021.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias variance trade-off. Proceedings of the National Academy of Sciences, (16632):15849-158551 2019.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-522 526, 2002.
Alon Brutzkus and Amir Globerson. An optimization and generalization analysis for max max- toxx-ppoligg networks. In Uncertainty in Artificial Intelligence, pp. 1650-1660. PMIR, 2021.
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in neural information processing systems, 32, 2019.

---

Published as a conference paper at ICLR 2025
George Cybenko.
Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, (33::333-314 1989.
Gintare Karolina
Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 2017.
Andre Elisseeff,
Theodoros Evgeniou, Massimiliano Pontil, and Leslie Pack Kaelbing. Stability of randomized learning algorithms. Journal of Machine Learning Research, 6(1), 2005.
Farzan Farnia and Asuman Ozdaglar. Train simultancously, generalize better: based minimax learners. In International Conference on Machine Learning, pp. 3174-3185. PMLR, 2021.
Stability of gradient-
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International conference on machine learning, pp. 1225-1234, PMLR, 2016.
Nick Harvey, Christopher Liaw, and Abbas Mchrabian. Nearly-tight ve-dimension bounds for piecewise linear neural networks. In Conference on learning theory, pp. 1064-1068. PMLR, 2017.
Fredrik Hellström, Giuseppe Durisi, Benjamin Guedj, and Maxim Raginsky. Generalization bounds: Perspectives from information theory and pac-bayes. arXiv preprint arXiv:2309.04388, 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31, 2018.
Ziwei Ji and Matus Telgarsky. Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks. ICLR 2020, 2020.
Ilja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 2815-2824. PMLR, 2018.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 8279-8287, 2021.
Yunwen Lei. Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems. In The Thirty Sixth Annual Conference on Learning Theory, pp. 191-227. PMLR, 2023.
Binghui Li, Jikai Jin, Han Zhong, John Hopcroft, and Liwei Wang. Why robust generalization in deep learning is difficult: Perspective of expressive power. In Advances in Neural Information Processing Systems, 2022.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint 1806.05 1559, 2018.
Yingcong Li, Muhammed Emrullah Iidiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning. In International Conference on Machine Learning, pp. 19565-19594, PMLR, 2023.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on learning theory, pp. 2613-2682. PMLR, 2020.
Philip Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks.
arXiv preprint arXiv: /2600, 2019.
Tao Luo and Haizhao Yang. Two-layer neural networks for partial differential equations: Optimization and generalization theory. arXiv preprint arXiv:2006. 15733, 2020.
Chao Ma, Lei Wu, et al. A priori estimates of the population risk for two-layer neural networks. arXiv preprint 1 1810.06397 2018
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
12

---

Published as a conference paper at ICLR 2025
Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generaliza- tion in deep learning. Advances neural information processing systems, 30, 2017.
Sejun Park, Jaeho Lee, Chulhee Yun, and Jinwoo Shin. Provable memorization via deep neural networks using sub-linear parameters. In Proceedings of Thirty Fourth Conference on Learning Theory, pp. 3627-3661. PMLR, 2021.
Jayanth Regatti, Gaurav Tendolkar, Yi Zhou, Abhishek Gupta, and Yingbin Liang. Distributed sgd generalizes well under asynchrony. In 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 963-870. IEEE, 2019.
Rebecca Roclofs, Vaishaal Shankar, Benjamin Recht, Sara Fridovich-Keil Moritz Hardt, John Miller, and Ludwig Schmidt. A meta-analysis of overfitting in machine learning. Advances in Neural Information Processing Systems, 32, 2019.
Norbert Sauer. On the density of families of sets, Journal of Combinatorial Theory, Series A, 13(1): 145-147, 1972.
Ali Shafahi, Ronny Huang, Christoph Studer, Soheil Feizi, and Tom Goldstein. Are adversarial examples inevitable? In ICLR, 2019.
Shai Shalev-Shwarte Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-6770, 2010.
Jianhui Sun, Ying Yang, Guangxu Xun, and Aidong Zhang. Scheduling hyperparameters to improve generalization: From centralized sgd to asynchronous sgd. ACM Transactions on Knowledge Discovery from Data, 17(2):1-37, 2023.
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv:1312.6199, 2013.
Hossein Taheri and Christos Thrampoulidis. Generalization and stability of interpolating neural networks with minimal width. Journal of Machine Learning Research, 25(156):1-41, 2024.
Ilya O Tolstikhin and Yevgeny Seldin. Pac--ayes-eempiical---reee -eersstteeleee inequality. Advances in Neural Information Processing Systems, 26, 2013.
Jacob Trauger and Ambuj Tewari. Sequence length independent norm-based generalization bounds for transformers. In International Conference on Artificial Intelligence and Statistics, pp. 1405-1413. PMLR, 2024.
Guillermo Valle-Pérez and Ard A. Louis. Generalization bounds for deep learning. arXiv preprint arXiv:2203.14533, 2022.
Gal Vardi, Ohad Shamir, and Nati Srebro. The sample complexity of one-hidden-layer neural networks. Advances in Neural Information Processing Systems, 35:9139-9155 9150, 2022.
Martin J Wainwright. fligh-ddmensoonal statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Mingze Wang and Chao Ma. Generalization error bounds for deep neural networks trained by sgd. arXiv preprint arXiv:2206.033:
2022.
Yihan Wang, Shuang Liu, and Xiao-Shan Gao. Data-dependent stability analysis of adversarial training. Neural Networks, 103:00 2025.
Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. Advances Neural Information Processing Systems, 32, 2019.
Ming Wen, Yixi Xu, Yunling Zheng, Zhouwang Yang, and Xiao Wang. Sparse deep neural networks using infinite- weight normalization. Statistica Sinica, 3133)113771114, 2021.
13

---

Published as a conference paper at ICLR 2025
Jiancong Xiao, Yanbo Fan, Ruoyu Sun, Jue Wang, and Zhi- Zhi-Quan Luo. Stability analysis and generalization bounds adversarial training. Advances in Neural Information Processing Systems, 15:15446-15459, 2022.
Yue Xing, Qifan Song, and Guang Cheng. On the algorithmic stability of adversarial training. Advances in neural information processing systems, 34:26523-26535, 2021.
Yahong Yang, Haizhao Yang, and Yang Xiang. Nearly optimal ve-dimension and pseudo-dimension bounds for deep neural network derivatives. Advances in Neural Information Processing Systems, 36:21721-21756, 2023.
Lijia Yu, Yihan Wang, and Xiao-Shan Gao. Adversarial parameter attack on deep neural networks. In International Conference on Machine Learning, pp. 00354-40377 PMLR, 2023.
Lijia Yu, Xiao-Shan Gao, and Lijun Zhang. Optimal robust memorization with relu neural networks. In International Conference on Learning Representations, 2024a.
Lijia Yu, Xiao-Shan Gao, Lijun Zhang, and Yibo Miao. Generalizablity of memorization neural network. In NeurlPS, 2024b.
Yibo Zeng and Henry Lam. Generalization bounds with minimal dependency hypothesis class via distributionally robust optimization. Advances in Neural Information Processing Systems, 35: 27576-27590 2022.
Chiyuan Zhang, Benjamin Recht, Samy Bengio, and Oriol Vinyals. Understanding deep learning requires re-thinking generalization. In ICLR, 2017.
Yu Zhang, Peter Tiño, Aleš Leonardis, and Ke Tang. A survey neural network interpretabillty. IEEE Transactions on Emerging Topics Computational Intelligence, 5(5):726-742, 2021.
Nikita Zhivotovskiy and Steve Hanneke. Localization of ve classes: Beyond local rademacher complexities. Theoretical Computer Science, 742:27-49) 2018
14

---

Published as a conference paper at ICLR 2025
A PROOF OF PROPOSITION 4.3
function a is sigmoidal limit, -- (z) 0 and limitz-+oo 1. Then, we have
Theorem A.1 (Theorem in Cybenko 1989)) ). For any continuous sigmoidal activation fanction
é E (0, 1) and continuous function f: 0. 1 + R. there exist 2 and F E (n)(n) such that
[f(x)) F()) <.
prove Proposition 4.3 by using the above Theorem.
Proof. is easy that (x) RcLU(x + ReLU(x)) is continuous sigmoidal activation function.
Denote Zi (n) the set of all two-layer neural networks with input dimension n, width W, and activation function For simplicity, Zw (n) means Z (n).
Firstly, it is easy to see that (n) C (n)(n) for any E N...
Then, because D has positive separation distance with different label, there is a continuous function f such that: f(x = 1 if x has label 1 in distribution D; f(x) - if x has label in distribution D.
Finally, by Theorem A.I there exist and F Zi (n) such that F(z) - f(x)] s 0.1 for all [0, 1]". Thus, F E (n) Zew (n) and ((xF)) 2 0.9)
Let the maximum the absolute value of the parameters of be A. A < 1, then F is what we want. If A >> 1, then write F aRRLUU(Wa) +b) c let FA (a= then there are FA = aRtl.U(W> b)/A² c/ = F//A2 so FA is network whose parameter is in [-1,1] 1] and FA F/A2. Hence, there FA Haw and P (e.))D(yFF( 2 0.9/42) The proposition is proved.
b/A) c/A2,
B PROOF OF THEOREM 4.4
PREPARATORY RESULTS
We give some definitions of the hypothesis space. Definition B.1. For network R. - and an a > O, Fea, that is, clamp F in [-a,a] a). Then for any hypothesis space H. let H {F-a,al H).
(x) minfmax F(x),,
define the Radermacher complexity.
Definition B.2. For a hypothesis space H and dataset D, the Radermacher complexity of H under dataset is:
Σx,eD F(ax))
Radh (D) = (1)
sup
D
FEH
where d satisfies that P(q: 1) P(g: - -1) = 0.5 and ai are i.i.d.
Here are some results about the Radermacher complexity:
Lemma B.3. For any hypothesis space H, ler H+ = (F +a H), where Then for any hypothesis space H, E R and dataset DD there are RadH(D) = RadH,. (D).
Let the L1,0 norm of matrix W be the maximum value of the L1 norm for each row of the matrix W.
Lemma B.4. Let Fn.d((..).e)) R be a network with hidden layers, L; Lipschitz-continunn activation function for i-th activation function, and the output layer does not contain an activation function. Let we be the i-th transition matrix and by be the i-th bias vector. Let the TA,s0 norm of w; plus the L1,00 norm of by be not more than C₁. Let H Lnde (Fudd.Lues Then when L; 2 2 for any {x,) C [0, 1)", there are:
Rad Rad d,c, (1x;)N II L C
(V(d 3) log(4) + / lolog))))
VN
15

---

Published as a conference paper at ICLR 2025
The above lemma is obvious corollary of Theorem in (Wen et al. 2021 By the above two lemmas we can calculate the Radermacher complexity of (n
Lemma B.5. Let be Lp Lipschitz-continee
activation function and Lp 1, and let H {F(x, v) F(r, v) = , E HW (n) where a > 0 is given in Definition B.1 Then
for any S = {(1,, wi)l C [0, 1 x 1-,,1}. there are
Radh (S) 5 p 1)( +1+ +1+a) a)
(v 5log(4) + 2log(2n)
N
Proof. First, have
Σ (ilkf(za))
Radæ (5) = Radæ (((z,,))) (())) = E (g)) m
sup SeHW (n)-a,a
Taking into account the definition of in definition
B.2 there are RadH 11)) =
Σx g.f( = RadHa (m) a..
E (g)) (sup (m)-...
(
D
So, just need calculate RadHş (n)-a.a (( (
First, for any function and 0, N we have
s-aa(x) (e) + aa ReIUU((()) a) a) (ReLU + a/k)- - ReLU(S())/k- a/k))
On the other hand, let H4 {f + alls E (n) Then for any F H there are F = f-ao (z) + for some f E H (n)) Then by the above form of expression, take [W/2].
F and write as network with:
(I): Depth 3. Because has depth after adding ReLU activation function, it was depth 3.
(2): The first layer has an Tp Lipschiz--comtimuuus activation function; the second layer has Lipschite-continuuus activation function, that is, ReLU.
(3): The 11.00 norm of the three transition matrices plus bias vectors are n 1, W+1+e and 22W/2), as shown in the below.
[W/2]
The first transition matrices: this layer is the same the first layer of f. Consider the bound of values of parameters of f is not more than 1, and the first transition matrix has n weights in each row, and with the bias added, there are total of n + weights, its norm is n + 1.
The second transition matrices: Let the second transition matrices of f be Wr and bias be Then the second transition matrices of F is W //, bias is c/k + a/k or c/k a/k Using the bound of value of parameters of f, the width of Wy is W + 1, and the value of k, so we get the result.
The third transition matrix: It is (1, I...., 1, -1, 1, -1, ....... -1,, where there are num- ber of and & number of in it, and we get the result.
So, by Lemmas B.4 and B.3
there are Radh .. ((n)))
(()
(L, log(4)
/2 log(2n)) The theorem proved.
VN
Another important Theorem is required.
Theorem B.6 (Theorem in Mohri et al. (0118) Let (F R
aa,a],, and D be
distribution, then with probability - ò of Drr DN, there are:
F(x)
In(2/0)
E Bx-D(F(x)]
Σ
< (Da.)((D..)). + +ba/
N
2N
BEDr
for any F E H.
We give simple lemma below.
16

---

Published as a conference paper at ICLR 2025
Lemma B.7. (I): When 0 e, there are in(1 x) 2 x/(e + 1).
(2): When x > 0, there are ze" + - 1/e.
Proof. For (1): Consider f(x) = In x) x there are (z 1// so (xx) 2 f()) = O, which means that In(1 + + x/(e 0.
For (2): Consider f(xx) xe- there are (²) =1 x), it easy that f'(x) become
positive then negative when x from to oc, and (1) = 0, so ((x) - f(1) = 1/e.
B.2 PROOF OF THEOREM 4.4
Proof. Let Drr DN and JF be network in My (Dor, n). We prove Theorem 4.4 in four parts: Part one: We have Σ (a.))E,, ((F(x), N In ol (T
Because D can be expressed by H (n) with confidence c. so there is a network Fo E (W + b;) + such that yF((x) 2 c for all (x, ~ D. Moreover, we can write such network as Fo D a, + 6,). where aw Sgn(c:), Wwo+1 0. bwo+1 /cr/. Now, we consider the following network in (n):
1[ W Σ E=1
Fw
(WW + box(W+t)))
Here, we stipulate that 1%(Wo + 1) = Wo + when Wo + 1/.. Then we have Fw(x) = Fo(x) and (x) E (n). Morcover, there are (F)(x) = yl W 2 W le for all (r.y) ~ D. so E(E,)ED. ((Fw(r),)) I Nin(1 + c l So for any F E arg mig (n) EirnED L(f(x),)) there are EiE,)ED, L(F(x).v) I
E ((F((z).)) v) & N In(1 ++ (lw).))).
Part Two: Let 1- lw by the assumption in Theorem, there is h: 1. We will show that H(I,v) (x, E DDr, ((r) S kc/2]| < ke/242.
Let (<x,y) : (2, Der, D(ry)((x) & 2). then according part one, there are: [S]nn( (-ke/2) 5 (aayes L(F(x), S (an))D L(F(x),)) N e s -e-
kee So, there
are |S| In + + ke/2 < Ne-
ke/2 By Lemma B.7 there are |S|e-ke/2 kn/2 + + kc/2 S NN-kk so |S| S Ne kc/2 (c
1) < Ne- kc/242
Part Three: By Definition B.I let network g F -ek/22.k//2 show that, with high probability, (())))DU((()) has lower bound.
Firstly, by part two, there are EinnED, vg(x) 2 N(ke(1 e ko/2222//2 kce kk/222 22/22+2/2)
Nke(1 2e Re-Ro/242)/
Then, let H = (yF(x) F(x) E H. ke/2/k//// (n) (V5log(4) 4) lo (2n)), Rad defined in definition B.2
by Lemma B.5 there are Rad (D.r) S
VN
So, considering that yg(x) E Hl and by Theorem B.6 with probability 1 - 8 of Dzr. there are E ((Lz))DU9(())
N E(r.y)eD, vg(x) - Radd(HH (n)) - 3key
In(2/5) 2N
kc(1 2e ke/2+2)/2//2
(W 55log(4) + 22log(2n) 3kcy/ 2N
(n(2//))
VN
Part Four: Now, prove Theorem 4.4
17

---

Published as a conference paper at ICLR 2025
Firstly, there are Ag( ((a.))))(( (1g(x)) > 0) 2 E (a.y)> (oloo//g(x))/(////// use [g(x)) - kc/2
in here. So, by part three, with probability of Drr, there are
4(n 1)L + + ke/2) (v (V5log(4) + log((2)) - 61
In(2/8)
Ag 2 2e kc/2+2
VNkc
2N
By Lemma B.7 and k = [W/(Wo- - 2
W which is because
and Wo 2 2.
2Wa
there are 2e ke/22++ < uu 8nW L 2/WW/) WN[W(Wo++])e
de
4e
8eWaa and it is easy to that </kkc <
We
4 Wn+1) (2tke/////
8n (4Wottc the last inequality uses [W/(W++I]]
VNke
VNc
2W6'
The last step uses k = W/(Wo+W]]] W So there are:
And v 2og((2n) & log(44)
2W6
8eWo
8nLp (1 + wh
In(2/5)
Ap(g) 21
(V5+ v2) /lggA))(44)) - 6V
Wc
VN
2NN
Lastly, because Ap(g) = (F))), we have AD(F) 2 1 - -0
We We +
In(2/8)
VNc
The theorem is proved.
C PROOF OF THEOREM 4.8
The proof is similar to the proof of Theorem 4.4
just follow the proof of Theorem 4.4
Proof. Let Drr ~ DV F be a network in M (Dor, n), and Fg be network that a approxima- tion of the empirical risk minimization.
We prove Theorem 4.8 in four parts below.
Part one: It holds Σ (aayee, L(F(x),)) & NIn(1 + wlwlwal)) This is the same as in Part one in the proof of Theorem 4.4
Part Two: Let k
W
2 1. Then, [[ y): (z,8) E Dtr, (F, - kc/2]l S -Ne-kee/e kc/2+2
Wo-I
Let S = {xr,) (x. v) E DFr (z) < kc/2], then according to part one, there are: |S| In(1
e ko/2)) I (xx)Ee L(F (x), [(F,(r),)) v) I (m.))ED L(F(r).)) & NNin + e < gNe ke. So.
there are |S] In 1 + e kc/2 < Ne
By Lemma B.7 there are SS|e kn/2 /et & hm kn/2 & NNe he so ss |S| S (o/2
1) < qNe kc/2+2
Part Three: By Definition B.1 let network g (Fa)-ke/2ke//z We will show that, with high probability, E(na)) x) has lower bound.
Firstly, by part two, have E ((a.))D vg(x) 2 N(ke(1 qe -e- qkee kc/2+2 /2)
Nke(1 ke/e22/2+2)/
So, with probability 5 of Der. holds that
((rg)))8)(())
N Σ E( Vg(x) 2Rad (Rad(HH ko/2,bo) -o0) - 3kc
In(2/8)
2N
kc(1 29e kc/2 2 I., +1 (v (log((4) + / 222g))2) -3kcy
In(2/8) 2N
VN
Part Four: Now, prove Proposition 4.8
18

---

Published as a conference paper at ICLR 2025
Firstly, there are Ap(g) P ((..))p((g(())) 0) ((x.g)) (uxx))/olgg())/(k///// with 8 probability of Drr, there are
So, by part three,
Ap(s) 2 2qe kc/2+2 4(n (W +1+ kc/2)
In l2/2/))
(v (1 5/llo(()++ (2log)2))))l((2n)) -6V
VNkc
2N
Then, similar as part four in proof of Theorem 4.4
there are
SgeWo
8nIp
Wo)
ln(2/6)
Ap 2
(v5 log(An))) 6v
We
VN
2.V
which is what we want.
D PROOF OF THEOREM 5.2
Proof. Assume that Theorem 5.2 is wrong, then there exist n, W and Wn such that for given 6, E (0, 1), if D (n)) and N VC (n)) 4c 6), with probability 1 - 8 of Dr, have (D(F) 2 1 for all F E arg yi (i..eD. L(f(z).v.
We will derive contradictions the basis of this conclusion.
Part 1: Find some points and values.
For simple expression, let k VC(HG, (n)). and {w: be k points that can be shattered by VC(H Wo (n)). Let VC(H (n))(1 4e -6). 8).
Now, we consider the following types of distribution
(c1): D is distribution in D(n) and ((naa)=(( E {u:} )im) 1.
(c2): ((rw)~D(< = u&) = P(x,))=(a = uj) = 1// for any i, E [A:]
Let S be the set that contains all such distributions, and it is easy to see that for any 'D S, can be expressed by H (n).
Part 2: Some definition.
Moreover, for E S, we define S(D) as the following set:
Z E S(D) if and only if Z [R:] is vector satisfying: Define D(Z) as D(Z) {uuz Vz, )2, ) then (D(F) 2 1-c c for all F E arg min E(z)))D2 L(f(x), y), where 2; is the i-th weight of Z and yı, is the label of uz in distribution D.
It is easy with probability 1, Drr only contain the samples (Ny, Mj) where j E [R)..
that if we i.i.d. select q samples in distribution D to form dataset Dtr, then by c2,
Now for any D.r selected from D. we construct vector in [k:] follows: the index of i-th selected samples as the i-th component of the vector. Then each selection situation corresponds to a vector in [k]9 which is constructed before. Then by the definition of S(D), we have AD(F) all F E arg gew (n) ((.y))D, ((f(r),) v) if and only if the corresponding vector of Dur is in S(D).
for
By the above result and by the assumption at the beginning of the proof, for any D E we have [S(D) 1- -.
Part 3: Prove the theorem.
Let S, be subset of S, and S, = b... satisfies the label of u, is ig. where j E [k].
C. where the distribution D Dir.ia....kk
We will show that there exists least D Ss, such that [S(D) < (1 5)g*. which is contrary to the inequality (S(P))
g² 2 1 - as shown the above. To prove that, we only need to prove that EDES, [S(D) (1 8)2* th, use |S.| 2 here.
To prove that, for any vector Z [k]], estimate how many D S, make Z included in S(D).
19

---

Published as a conference paper at ICLR 2025
Part 3.1, situation of a given vector Z and a given distribution D.
For Z (2))== and D such that Z E S(D), let (Zn = fc E [k] := 24 We consider the distributions in Sg that satisfy the following condition: for E len(Z), ( the label of u, is equal the label of in D. Obviously, we have 2 2 distributions that can satisfy the above condition in S.. Let such distributions make up a set (D, Z). Now, we estimate how many distributions D, in (D, Z) satisfy Z S(D.).
is easy to see that if D3 E See(D, such that there are more than [2ke] of E [k], D3 and D have different labels of u4s then min (FD AD, (F)) < for any F. So considering AD(F) 21 for all F E arg minneenwitie (m) L(ay)E [(f(r),)) v). by the above result, such kind
of D. is at most ii= Ch "l-llen())]' So, we have that: There are at most Σ i== of distributions D, in (D, Z) satisfy Z E
[2ke] Ch (=Il)e((2) numbers
Part 3.2, for any vector Z and distribution D.
For any distribution D E Sg, let (D), be the label of u, in distribution D.
Firstly, for given Z, we have at most 2(len(2)) different Sae (D, Z) for D Ds. Because when D1 and D2 satisfy y(D1); = y(2)), for any E len(Z). we have Dee (D 2) = D (D2 Z), and 2)len(2)) situations of label of u; where i E len(Z), so there exist at most 2)len(2)) different (D,
Then, by part 3.1, for an (D, 2), at most _.tkel C
k- (le))l)( of D, E Se, 2) satisfies Z E S(D.). ). So by the above result and consider that D. = UDED, (D, Z). at most 21len(2)1 [22dd C k-]lle(2)] number of D2 E S, such that Z E S(D.).
And there exist 9² different Z, so EpES, |S(D)
Epes, I(Z E S(D)) < Σn 21len(2)] (22ke] C [l|le)(2) S Σし 2* - 8) = (1 8). For the last inequality, we 22c]
2 (e--lee((1)) (1 8). which can be shown by [len(Z) S q S k(1 4e 8) use 2i=0 [-]len(2)
and Lemma D.I
This is what we want. We proved the theorem.
required lemma given.
Lemma D.1. Ifc, E (0.1) and k. x E Z, satisfy that: x S k(1 2c - 8), then 2 (E/1e)
[ke]
Ch <
2 8).
Proof. We have
2
(E f Ca-aa) < 2=2k x
[ke] k-
2k ke <
x-E < 2² -8).
The first inequality sign uses Ey= C m2n /n where S n/2,, and by k:1 2e 6). so
[ke] (k- z)/2. The third inequality sign uses the fact æ S k(1 2e 6).
E PROOF OF THEOREM 5.4
We give the proof Theorem 5.4
Proof. Let Der D. and Der {I, M For any given W, let F be network in a;RcLU(W,r b,) +c.
W Mc (Dir, n) and J E Then, we consider another network Fy that is constructed in the following way:
(I): a E 1 we say E S, if: ReLU(W,, + +b) 2 for all j such that vj = 1; ReLU(Wa, + bi) < 0 for all j such that U,- -1.
(2): For any (-1,1) if S, # 6. let PP,, Eies, aW./|S, and Q. Eies, aub:/1S.l
20

---

Published as a conference paper at ICLR 2025
(3): Define Fy as: Fy(x) Eve(-1,1)N,op4 Σ S.l PF, Qc) +
Then have the following result:
(rl): Fy E arg seg (w) E(EYEDD
L(f(x),)).
Firstly, it is easy to see that each parameter of Fy is in [-1,1], because for any v, |P = and 11Qulloo Eies. S. 1l I
EiEs, a:Wi [S. 1lc0 I Eies, [al:Wlll || [S0] 1 |See [S,1
[S < |
Eies.
=1.
Then, Fy has width W, because for each i, there is only one v such that E Su, so Ee | W, which implies that Fj has width W.
Finally, there are Fy(x;) = F(x)) for all (Ii, Us) E Der. We just need to show that for æ1, others are similar.
W There are F(z1) E a, Re + +b) + W wan +6.20 as (W,21 + by)
Hence, letting VI = {u : E {-1,1],, .21 = 1). then there is Ff(21) = L0E 55 | RPLU((P, + +00 EVEVI,, E (P. Qa) +c.
-c
Consider that {i E [W]. Wan + 6, 2 20 = Ei: V1J.
F(a))
Lie(W],Waa 0 (W,x + b,) +
Lisesw.eEv a (Wa1 b,) +
LVEVI. to Lies, (WWT + b,) +c
2.EV (P b.) F(((1).
By such three points and considering J E argmin E(en)ED, [((()),)) v). there Fy E arg min seH EanweD, L(f(x).)).
मां (n 1)/e, where Wo defined in Theorem. This is what (r2): AD(F)) s when N < Wot we want.
eN a+1 Firstly, we show that [v S. + Φt1 S max
). just by Lemma E.1
n+1
Re..U([S,,P,.aa) + [S.(Qu) + c. By Secondly, consider the network Fý1 EvE(- eN ++1 the assumption of 'D and [v : S, * +i| & max (2
m+1 }. then we know that, when
N W m- (n + 1)/e, there are Ap FF)) S 8.
8.
Moreover, there are (x) = Σ 10 $.$6 ReI. + 18.12)) + (E E.s, ReLU - + Qo) + Ff(2), so AD(F,) Ab(Fn) $ 6, this is what we want.
A required lemma is given:
Lemma E.1. For any = [ C R", ler ([S) = (S W e R e R).
Then [I((S) max (2a+1 eN n+1
n+1
Proof. It is easy to see that [T(()] S 2 because Sgn(Wan x; + b) E [-1,1]. So, when N s n + is obviously correct.
When N > n 1. Consider that the VC-dim of the linear space is n n 1, and II(S) = {(Sgn(Wn Wi; +
b))z W E 1 b R} is the growth function of linear space under dataset S. So by Theorem of Sauer 1972 we have [TT(S)
m1+1 C
Moreover, there I Cl
cN n+1
shown in (Sauer 1972,, this what want.
T
21

---

Published as a conference paper at ICLR 2025
F PROOF OF PROPOSITION
We give the proof of Proposition 5.6
Proof. Firstly, it is easy to show that D, cannot be expressed by Hw (n) when W < <n/2 by Lemma so we have proved (1) of Proposition 5.6
Let Der D. and N I nô, for any given W, let F be network in M (D n). and F En a,ReLU(W,x + b,)+c.
Now we prove (2) of Proposition 5.6 Let Dr, { [(x)))=== where 3; E [n]] be selected from the distribution, without loss of generality, let 22 < F++1 for any E [N].
We will divide [W] into several subsets based the intersection of the plane War + b and the line -001 c01, let [W] U S;, and:
For any i E [ - 1]: jf E [W] such that Es W, 1 + b, < 0 and #c+1 W + bj 2 then j E s;
2. jf [W] such that z: W + by < <0 for any i [M] then sN;
3. For any i E {N + 1, N + ,,...,2N 2N 1}: if E [W] such that " + b 2 0 and
2: M1 W,1 + < 0. then s;
4. j E [W] such that # W, + b, 2 for any i E [N], then 82N.
Now, by such 2N subset, we consider another network Fy that is defined as:
For any [2N]. if S. * o, define P; Ejes, a,W./|Sil and Qi = Ejes, (Ssl Then [ee|RUU Qi) + c.
Fy EEERN),SS S.S ReL.U(P,r + Qi) cc= EiE(2N
Because there is only one intersection point between straight line and a plane, each j E [W] is only in one subset 8t. So, F, E (n). Moreover, show that Ff(x) F(x) for any (x, y) E Din. which implies Fy E arg min JEHH (x) E(,,)ED, L(J(x),))
For any j [N], by the definition of si know that Za 5,1 + b, 2 0 if and only if i 2, (1, 13 (N+ +N+ ...,,,NN.... so: n
Fy(mg)
EiERNNISE Σ
S J ReLU Q.) +
26 Σ E/=1 (P.z, + Q,) +
E
ΣKE CE(1 N-J. N-)
(WED,) + bk) +
Exeln ReI.U(Wez, bk) + F(zz)
This is what want. At last, by Fy - |S, ReL,U(P) Q.) c has width at most 2N and Lemma F.1 and consider that N no, we have that: Ap(F,) < 0.5 + 28, this what we want.
required lemma is given below.
Lemma F.1. If < x2 < 23 < < INN and x; has label y1 1 when i odd, or I; has label
= 11 We consider dataset S two-layer network width M, this network can correctly classify at most to M + samples in S.
where 1 is all-one vector in RR. Then: For any
N.
Proof. Let F
EM a, (W. + b:) +b) + Let W,x + b, and the line -col(n) + c01(n) intersect point (.l Let P, < &P, j. Let PM+1 co.
22

---

Published as a conference paper at ICLR 2025
Then it is easy to see that in the line segment P.1(n) + Pi))l(n), F(x) is linear function. So, there is Pi+0.5 E (P,, P(41) such that FF maintains the positive and negative polarity unchanged in (n)(n) + (() and Pito.s((n) + P().
< Zutk < Pi+0.s. F gives the same label to T. I (n), Fa)11(n),........ ...,, Tutk (m)), which means that F can classify at most [ samples them. Similar to when Pitos= S Fu < Iut1 <.. < Tuth < Pi+1-
So if P. S Iu < zutl <
Ta+1
(n).....,
Let 9. = 10: Pa/2 S 23 P./240.5|l where i E [2M]. Consider that each sample in S is appeared in P, + P.+0.s or P(+0.5((n) + P.+1 (n), so
D=l = N.
2M
So, the whole network can classify at most > 1=
2M 1+th
2M
1+% M
N T
2
G PROOF OF PROPOSITION 5.7
Proof. Proof of (1): Let be the all one vector, Σ② = >i= T, where H, is the i-th weight of r. We show that F = d1r 0.5) E (n) is what we want. Because if Σ a: is odd, then
o1r - 0.5) = (5 r 0.5) = sin(T( x 0.5)) = 1; if Σ x is even, then o(1 - 0.5) =
o{ x 0.5) = sin π 3 x 0.5)) = -I
Proof of (2): we will prove it into three parts:
Part one: For any W and DDy ~ DA let E M (Drr, n) and F= W (W + b:) + Then there are: for any (z, v) E Drr, there are yo + by) = 1 for any i E W
=
If not, without loss of generality, assume that yo + bn) < 1 for some (x. y) E Dir. According to the proof of (1), there are Wo and bn such that yo (Woz + bo) = 1 for any (x, y) E Dir. Now we consider the network Fe(z)= =
+ b,) - (Wox + bo) + c, then we have that:
Firstly, it is easy to see that F. E Hº, (nt)
Secondly, we show that yF(x) S yF((r) for any (x,y) E Drr and yF(x) < yFo(x)) for some (x,,y) E Dr..
By the definition of F and Fr, for any (x. v) E Dir. there are yFa(()) - yF(x) = y(a + bo) a (Wiz + b1)) =1 yo + bi) 2 O, and by the assumption, there is a (I, y) E Dr, such that 1 > go + b)),, then yF.(() - yFx) > O for such (z, y) Der. this is what we want.
By the above two results, and considering that L(F(x),)) is strictly decreasing function about yF()), there are L(en)ED L(F(x).v) > E(wwiED. L(F.(r),)) which is contradictory to F E arg min sen (n) (aw))D, ((f()),)). So we prove part one.
Part Two. For any j E Z, let zj = L1 and y, = I'(j), where I(x)) is defined in the definition of distribution Dn, If i, Z where j E [4] such that i is and is is are co-prime, then there are: if Wo E [-1, 1 and by E [-1, 1] such that yi, (Wazi, + bo) = 1 for any j E [4], then
(WoT bu)
for all p Z.
When there is yı, [W,,,, +b0) = y sin( (Woz,, +bb)) = yr sin(T(< Wo. > 2s/n+bb)) = 1, consider that yi, E (-1, then there is Wo, > iz/n by mi, 0.5 for mi, E Z, moreover, mi, and iy are same parity.
Now consider (Wozs, + by) (Woz;, + bo) and (Wozi, + bu) (Wozi, , + bu). there are < Wo, 1 > (i1 - ii)/n = my - m4, and < Wo, > (ia- in//n = m4a - m4--- So, there are وااي 1g-ts my mc,
mig
By i 12 and is is co-prime, and |m,, m. m,, m., = < Wo. 1 > (is iz)/nl I li is). there are < Wo, 1 > /n = 1 < W 1
Wo. 1 (i iz)/nl < lii 12
/n /n=
Hence, by m;, - << Wo. > by and < Wo. 1 > n = or < Wo. 1 > /n = 11
consider that m., and i; are the same parity, so b 0.5.
So for any p E Z, there are (Wo + bp) = spsin(T(<< Wo, > p/n + bo)) = y,,in(=(p 0.5)) 1, this is what we want.
23

---

Published as a conference paper at ICLR 2025
Part Three, if Dry DWW, and N 2 4 ln(6/2) (24,3k) where E [4] in Drr, such that z; m: 1, my m2 and mg - m4 are co-prime.
In(005511v) with probability 6, there four samples
By the definition of Dr,, it is equivalent repeatable randomly select N > 4 ln(6/2 (0.55++1/m) points from
[n]. with probability - 6, there are four samples my such that m2 - m2 and mg m, are co-pon co-prime.
By Lemma G.I when N 2 4 In(6/2)
ln/6/2) In(0.++1/n) with probability at least (0.5 + 1/m) (n00.347mm) /(0.5
1/n) = 1 0/ 2/n) 2 1 - 8. This is what we want.
Part Four, we prove the result.
Let Dr D. For any W, let F E arg eeg Eley)e L(f(x),) and F
EE oW +c.
Firstly, with probability 1- 8, there are four samples in Drr satisfying part three. Then, according to part one, there are yo + b,) 1 for such four samples. Finally, in part two, there are
yo +;, = yorl x) 1 for any (z.y) ~ Dn. So, yF(x) z W >>> for any (x, Da we prove the result.
required lemma is given.
Lemma G.1. Randomly select N points from [n), where n. 3 and N 2 4. With probability
1 (0.5 + 1/n)///a11, there are four samples my such that mi 112 and mg 1144 are co-prime.
Firstly, we consider the situation that N = 4, let [m=] are the selected number. Then we have
Proof.
P((m - m2, my - m4) 1)
P(m1 - -m2 * 0, m3 m4 + 0) - P((m - m2, m3 - m4) + 1, - m2 * m2 - m4 # 0)
(1-1)) (1/n)211- P((mm m2/, mm mal) 1|m m2 F 0, m3 m44 7 0))
IV WVM
(1 (1-1/n/ (1-1/n)2(1 Σ LgePrime Primme P(q (lm1 m2l. |mg mal)|m m2 + 0, m3
+ 0))
(1 (1-1/n)²(1 LqePrime +
0.5(1-1/m) 2 0.5 - 1/n
where Prime the set of primes. For the second inequality sign, we use
P(glm m2 [mi
m2 * 0)
Σ == P(gli, [m m21 [m1 m2 + 0)
(n 1)/9l
1/4.
Similar for my m4. For the last inequality sign, we use P(2) Eie Prime 0.5, where P is Riemann function.
So. when we select N' samples, it contains [N/4] > N/4 pairs of four independent samples
randomly selected. So, with probability 1- (0.5 + 1/n) N/4-1 there are four samples my such that
m2 and mg my are co-prime.
H PROOF OF THEOREM 6.2
Now, we prove Theorem 6.2
Proof. we prove the proposition into three parts.
Part One, with probability 1 - 28 of Diy No, there are Ee-DlyF(x)) 2 No.Nol
W
2 Dii (og(4))+ / (log(2n)) 6.F / No
ln(2/6)
for all F E M (Der: n)). where Fmax 2No
max
[F ( 5)1.
Firstly, we show that there are E(EyED yF(x)) 2 Nol w for all F E M (De,, n) when
Drr No satisfies the conditions of the proposition.
24

---

Published as a conference paper at ICLR 2025
Because Drr can be expressed in the network space Hw,, (n) with confidence co, there is network Fo = Σi a,o + b.) + such that yF(x) 2 co for all (I,y) E Dtr. Moreover, we can write such networks Fo E 0,0 (W b.), where owo+1 Sgn(c), Wwo+1 bwo+1 = lcl.
Now, we consider the following network in H (n):
(Wo+1)larr)
Fw Σ
(M(WW+))0(WW<(Woo11 bo%(w++)))
Here, we stipulate that i%WW +1) ) Wo+1 when Wo 1 Then we have Fw (x) = Wo+i (o and Fwr (x) H. (n). Moreover, there are (Fw = y yl l 2 W for (x, y)
w
1 Dir, so E(En)ED (F)w s In +e -oll
Then, because In 1 + e" is a convex function, so that:
No + e Elavie N xF(a)
(r.))ED, In e (F())
(.,))ED M(F(x), y)
E (ag))ED [(F.(D)).))
-o w wat
No 1oln(1 -e
So (x,))ED (F(x) 2 N
W
W
Hence, by Lemma B.4 and Theorem
B.6 with probability - 8 of Drr, there are:
F(x)
L (W + 1)(n + 1)(( ()(((1)(1g)) (lgg(4) + (2log(2n)
In(2/8)
(E>D(F(x)) Σ
< 2
+6F max
No
VNo
2NNo
REDir
for all F (n(n).
Finally, combining the above two results, with probability 26, there (FaDD(((x)) 2
W W 1 2 ([ (lgg((n)) 6J max
In(2/8)
No
VNo
2No
Part Two, there is an upper bound of E (x,,)) [min FF (xc + 5)). if Der satisfies Part One.
For any F Hw (n),,, we can write F= 1= Ey ReLU W + bawot)) c, which is representation of the sum of [ W the assumption in the theorem, with probability
small networks with width of Wo. So by part one and by of Der DN there is D, E R(D
W.
such that (x,))),, (z) I 2Noc1 for all Fi (n). Then we have E(ZW)D, FF(x) S
2.ooc1
W. by the definition of D,. which implics that ((,)))D min yF +
2N
W
Wo
And then, by McDiarmid inequality, with probability - of Der ~ DNo, there are (E) |min 8llse yF 5) + yF(x)) N, EuneE, min yF(x + 8) + yF(xx) S
2.F max
1/
So if there are ((w.)- yF(x + yF(x)] > 2c1 W
2No
2F max
l/
according to McDiarmid inequality, with probability 1 of Drr DNo, stand, which is contradiction with Wo
2No
E(n))ED, minjjllss yF + 8) yF(x)) > 2Noc1
w
the above result.
So there must be E( [min S yFr + 8) + yF(()) < 20, considering the result in Part one, have that: (kz.y>D(mmnjjee W W.
W Wo + +2 /
1n88 Finally, 2No
yF + 8)] W colo FT + (W +DW+++++++(66060
< 2c
(loo()))))))))))+++)))))))))))+) (log(4)+ (log(2n))
+ 8F 8F
max
In(2/8) 2No
/No
25

---

Published as a conference paper at ICLR 2025
Part Three, Now can get the result.
By Lemma H.1 and part two, there RobD,,(F) S col WT+
+ 8V 2//
Jmax
2No
2 2 +1) C0KKK///gg/// V and we consider that each parameter of F. is not greater
VNNomaax max
than 1 and Lipschitz constant of is not more than Lp, Fmax maxx+6 F 6) max) [F(x)) (n + +1) +
Let T 1o by Lp n, Wo and W 2 Wo 1, there are:
co colwo=1 1- 1-2cg 1
L, (n++++++++
4. 201 (++)) +1)
1, (TT++1 WW (1+
2n 2cy
der (oo (ow L,Wo(Wot))(ttDH
2a
Lp (T+1) [
20s
W/Wo + Wo
SLp Won
I, Won
and
1, 1)( 4 (4g((4) (2n()
No
L ((W+1)(++D)))) log(d)+ + (2gg(2n)
2 2v/ (W (m++1)
Alog( +)+ (2n)
VNg
So, there are RobD,e(F) < Merge some items and ignore constants, this is what we want.
co 20
Z, Won w/w, Wo 2
In 2/6
(log(4)+ / (2g)
BL, Won
2No
VNo
required lemma given below.
Lemma H.1. F R" + R and the distribution D E =0, {-1,1} satisfy ()) (( S
and m0. F(x)] < B, then AD(F)= 1 1.
Proof. There are (( 2 - ((maxre(0,1'> (1))))()))) # Sgn(F(x))) -B(1 AD(F)), so 2 -B (AD that is, AD(F) I
A
B.
1 PROOF OF PROPOSITION 6.5
Proof. We take a > 0 such that In(1 + e- 2 In2 - 1n228800 - (1/e) < 0.1. Then
take an such that In(1 e m/2426) In 2/2.. Let N satisfy ( (1 / (lg(()) 2log2m) + 6(n
v /98N/200
2)
In(2/8) 2N
In 2/800.
We consider the following distribution D:
(cl): Let s1 (xx x === |x| 2 2c/n), |||||-00 mean the minimum of
the weight of |r| 82 (1z,-l) I n/2 -, ||>||> I 3c 83 = {(z, -1)
[0, E x = ec;
(c2): P (m)))D Σ x -- c) 1/100, and D is uniform distribution in 83;
(c3): P P(
E x = n/2 + c) = (e.)) E x n/2 - c) = 99/200, and D is a uniform
distribution in U U2-
Let W, = 1, then we show this distribution and Wo are what we want.
(1) in Theorem: Let Relu Ix) c/2 H (n). Then Fi (x) for all such that Σ
and Fi < 0 for all x such that Σ x = -c, so (D(Fi) 2 0.99.
(2) in Theorem: We use the following parts show the (2) in the Theorem.
26

---

Published as a conference paper at ICLR 2025
Part One. With probability at least - -Ne-2/200' of Day DN, there are at least 2/20 points in Dir n S3, and at least 98/200.N points with label in Der, at least 98/200N points with label -1 in Dtr.
Using the Hoeffding incquality and ((x.))>> Σ x n c) = 1/100, we know that with probability 1 220 /200* of Dir there at least N/200 points in 83- Using also the Hoeffding inequality and PP (zz,))=(( = 1) = 99/200, we know that with probability at least e (99 98/2000² of Dtr, there are at least 9 N00.N points with label in Desi similar, with probability at least of Der, there are at least 98/ 28/200N points with label -1 in Dyy Adding
1 - e-
them, we get the result.
Part Two. For Der that satisfies Part One, if F E arg min (H) EleWnED L(((),,)) then there is E(,,)eD, L(F(z).)) < 19 2+111++++ -2/2222)
N.
200
We just consider the following network F1 E Hi(n): F1 = 11rLU(1r - (n/2
c)), then E(an)ED (x)) = 1n2 + Inl + e 2 n 23l S
199 In 2n+e 2/2122) Hence, for any FF E arg wugmin (e) (n) ElEwEDD L(f()),)) v). there must be EE [(F(),,) S (LnED. ((F(()),)) v 199 2 2 N, which is what we want.
200
200
Part Three. If E (n) such that F(x) 2 0 for all (r, -1) E 83. Then ([F())) 99/100 + + +11000 2.
Consider that for any (x1,1) 1) E 81, there must be (æ1 2c1 /n, -1) E 82: the other hand, if (22,-1) E s2, there must be (z2 + 2c1/n,, f,.11 1) E 31. So we can match the points in s and s2 one by one by adding or subtracting a vector 2c1/n.
Moreover, for any x E [o, 1] and x E H, (n), there are FF(x) - FF(x 2c1/n)| < 2c, which implies
L(F(x), 1) + L[F(z= - 2c1 /n), 1) = In(1 + e e-(()) + In(1 + / > 21n + e So for (I1, 1) 31 and (22. -20-1))))) 1) E $2 where 22 = Φ1 2c1/n, there must be LFF(x1). 1)
((F(22), 1) 2 Ihlle
Hence, by F(x) > 0 for all (a, -1) E $3, (er)) -D D [L > 99/200 In(1 + e 9 + In 100
Part Four. For any network F E H1 (n) such that F(x) < 0 for a E $3, then (FF) < 60%.
Firstly, we show that if ø1, 22, 23 are collinear, without loss of generality, assuming 22 is between
#1 and 23, then F(21) 2 F(22)
F(2s) F(21) F(22) < F(2)). Consider that 21, 22, 23
are collinear, so 22 = λ21 + (1 (1- A)23 for some X E (0,1), 1). So let f(k) = ReLUU.:(222
b) + (1 k) 23 + b)), there are f(0) - ReLU(W2) 23 + b). f(1)
ReLU(WZ) 21 b) and f(A) = ReLUUA(W' 21 + +b) + (1 A)(W 23 + b)) ReLU(W z2 + b). Consider that ReLU(.) is a
monotonic function, so that [kk) is also an monotonic function about R. we get the result.
Secondly, for any (2, 1) E s2, let Fg satisfy: (xz, 1) E and x, Zz, 2 are collinear. Then we have that:
(I): For any (z, -1) E 32, F must give the wrong label to Ig or z. If not, there are F(x) < O, F(x.) > 0 and F(z) < O. By the above result, it not possible.
(2): Let S = {I,: (z, 1) E 22} C $1, then IP (=. (z E S|x E s1) 2 (1 - 4c/n)nn Because for 1|2-8.1le
any (z, 1) E 82, 2
[(== n/2-2c which is a constant value, where Σ. x means the 2-4c we get the result. 22
n/2
sum of the weights of x. so S is a proportional scaling of 8 with the ratio
So, there are: AD(F) < max [P ((x,)))((( E 82), P (( v) E 8)} + P(ee.)/ v) E
sa) + P(e.)))(ss/SS)
< 101+99(11 (1 1440/))"") < 101 2002000-000 + 99/209 (1 - (1/e)49) S 0.6, use the definition of c.
200
Part Five. Prove the Theorem.
27

---

Published as a conference paper at ICLR 2025
We show that with probability 1 arg s L(.)))D, [(f(z).)) y), F must give the correct label to some points in s3. Then by part four, we can get the result.
3e Be-2N/200
of Dir, for any F
By part one, with probability at least 1 - 3e 2N/220000' of Dir, there are at least N/200 points in Der n S3, and at least 9 /200) points has label I(-1). Hence, by Lemma L. and Theorem 4.9. we know that, with probability 1 of Der, there are (L L(F(x), V)
4 [ 22loggm)) + 6(n 2)v 1n(2/6)) ). So, with probability V98.N220
E (x. (LF(()). v)]
1- 3e 2ON/200000 8, Der satisfies the above two conditions.
For such a Dtr. assume that F E arg J EmREED L((()),) and F. must give the correct label to some points in $3.
not, by part two, we know that ((S)))D. I(F(x)))) -
199 In 2+ 2m 2/2420 N.
200
Then, by part three, (( 2 99/100 In + e 1/100 In 2. Hence, by the
definition of Der, there are El,,)ED, L(F(x).)) v) Z N999/100 + e + 1/100
(log))5)))/ 6(n + v Im(2/8) 2N
N
V98N/220
By the definition of c, n and N, there are EONDEDD L(F(x). v)/N
2
(99/100/
e + 1/100
4(n- 1)( (5g(()))))))))))) + (Zlgzn) 6(n + 2)v
(n(2/5)
IV
199.5 200
V98N/200
2N
199 Ia h1teeeeeem/////ieee1 2122220)
(E L(F(x),U)/N) which leads to contradiction. And we prove
200
the result.
required lemma given below.
Lemma L1. For any given D {x; y.)) i= if there at least K samples have label I in it and there are at least K samples have label -1 in it, then there are:
1
N
4(n + 1)( ()(55)(000)) log(() + 1/2 log(2n))
ES
max (EH
o, (FFs)))) 9:)] <
N
VK
1=1
where o, are i.id and P(o = = P(a, = -1) = 0.5.
Proof. We have
E,, (ma
N
i T [;
E,, (m) N i= o In ex.)
< E7, m (n) ExED, o; Inln + e Fl0) + E., [maxFeH. Dal ExED, ai In + eF())
Hence, see 2n(1 + 6*)) as an activation of the second layer, and the output layer is J2 (x) = x//2. By
1 |Pal ExED, o, In F((o) < 2(++1) 5 logg(4) V 22ogg(2))
Lemma B.4 we have E,,
VIDi
Similar for other part, get the result.
J PROOF OF THEOREM 6.8
At first, we give the proof when the loss function La satisfies condition (1) in Definition 6.7
Proof. We first define some symbols.
Let the loss function Lg be a bad loss function that satisfies (1) in Definition 6.7 Let Lo(21, 1) mingeR Ls(x, 1) and Lo(2-1, given x E R", let I, = (Iz, Fz. In) ,,. E g where x; is the i-the weight of x; let r! (0, F2, -3, v.) R=+1
mingeR Lo(æ, - 1), assume |21 + 2--1 2. For any
28

---

Published as a conference paper at ICLR 2025
Then prove the Theorem in three parts:
Part One: We construct the following distribution D, E [0,1]" x {-1,1];
(I): Dj is defined on {o E [0, 11", 0.6 S x1 or 0.4] {-1, 1,, where 21 is the first weight of æ.
(2): x has label if and only x; 2 0.6, has label -I.
(3): The marginal distribution about of D, an uniform distribution.
Part Two: For any Der ~ Dj we consider the following network FD...
Let D {(1,, (a. y) E }. By Lemma J.2 with probability 0.99, there is a Fo with width W not greater than O(zN8n²) such that: if (It, 1) E Dir-t, there are Fi(1a) 21i if (x4,-1) -1) E Pi--c there are (z+) 2-1. Let F((x) Σ a,ReLU +b,) +c.
Then, we construct FD.. : R as F
Wh R.ReLU b;) +c.
Part Three: We prove the Theorem.
For any Der ~ DN,, we consider the network FD., mentioned in part two. Firstly, we show that FD., (x) E arg Few (n) EizweD, L(F(z), v)- Because FD.. (2) F(( 21 when 1x. E Der and FD.. (x) (14) = 2-1 when (r. -1) E Dtr- So (x),,. y) reaches the minimum value for any (2, E Drr, which implies FD.. E arg Hww
Secondly, there are (D. (x)) = 0.5. If (x)) > 0.5, then there must be pair of (xr1,), 1) and (x2g -1) in distribution D, such that (x1), (x2)) and (x) give the correct label to Ø1 and 22. But it is easy to see that FD., (I) = =F((xe) where J, is mentioned in part two, so, (((2)((12)) = FD.,( (22), which is in contradiction to FD... (z) gives the correct label to 2n and Z2. This is what we want.
FD. (21) (=))(()
Some required lemmas are given. Lemma J.1. For any v E R" and 2 1, let u E R" be uniformly randomly sampled from the hypersphere Sm-1, Then we have (u, r)] < IIllla 2
This is Lemma 13 in (Park et al.
2021
Lemma J.2. For any N points ( randomly selected in (0, 1) and any N given point (ys N in [-a, a). With probability 0.99 of { there is a network F with width not more than O(N2
and F(I.)) = yi
Proof. Part One: First, we show that with probability 0.99, there is ||x; x;l12 2 2N pm pairs i,j.
for all
For any i.j E N and >> there are:
-
- P(E
n ((T)): - (1,)a)² 2
W Mww
11 P(((z,) 2 2//n)
I 1 )
2
So P[[| xyl12 2 e, Vi..j) we get the result.
Eips 25112 <)) 1 2ee/nN2 Take
0.01 2/aNZ
Part Two: There is a w E R such that ||w/|12 = and |ur(2; - x1y) 2 AN
By Lemma J.1 for any pair i. Pu - x1)1 < 1|mg-m;ill
2N
<
NZ.
So. P. (u(((((; - -x,)1= 2
||
8 v(i.)) 2 1 - Eee, Po(lu(< -133] <
[|, 11n--a a.
8
> -
0, which
2N
2N
29

---

Published as a conference paper at ICLR 2025
implies that there is a w such that ||l||2 1 and for any pair (i,j), there are |w](2; 2351 2
n A. use the result of part one.
2N
FLITT
Part Three: Prove the result.
0.01 Let w be the vector mentioned in part two, and wx; wxy when i # j. Let 5 we consider the following network:
Now,
IN
yi (ReLU(wr (waz + 6)) + ReLU (wrx 6)) -2ReLU(wx wr:)). 8
F())
Easy to verify F(2;)= yi- Consider |wnn and // <400aN n, so F E Ho(aN3n3)(1) This is what we want.
We now give the proof of when the loss function La satisfies (2) in definition 6.7
Proof. In this proof, we only consider very simple distribution D: P P(aa))D((zz, v) = (0. -1))
((r.)))(((x;)) y) = (1, 1)) = 0.5, where is a all one vector.
We show that for any Der and W, let J E arg feg (m) E(MA)ED (z((())))) there are AD(F) 0.5.
Part one: When Dr, contains only (0, (1), then there must be F= 2i=1 = RReLU(W, 1) for some 24, which implies F(1) < 0. so (p(F) = 0.5.
Part two: When Drr contains only (1, 1), then there must be F Em ReLU + which implies F(0)= O, AD(F)= 0.5.
Part Three: When Dr, contains (1, 1) and -1), we will show that Σin (1
1 E arg ee (n) Ls(f(0),-)) -1) + L,( Consider that AD(F) = 0.5 for such F. we can prove the Theorem.
If = E ReLU(1# + 1) +1 & arg argmin seg [,((()), -1 + (f(1),, Let Fo(x) = 1). Then, let Fo(0)
Σ R. bi) +c arg mig Ls(f(0), Ll) (400)))))))_ and F1)
By = = (,0 (4 1)+Ø(- W 11), and @ decreasing concave function, there must be W (1++1+++11-- -b+W+1, which implies la - bl Wn.
Consider la b Σ - ReL)) - - - R. + 6:)l S SEEW a, a;1W S Wn. This a contradiction to la bl > Wn which was shown above. So, assumption is wrong, so F = Ew (ez + 1) + 1 E arg (o()(0), -1) + (s(f(1), 1), this is what we want.
K EXTEND THE RESULT TO GENERAL NEURAL NETWORK
For multi-layer neural networks, we can show that if there is enough data and the network is large enough, then generalization can also be ensured for the network which can minimum the empirical risk. Unfortunately, due to the complexity of depth networks, we are unable to provide a good generalization bound of such network.
Denote (w) to be the set of all neural networks of layers D with input dimension width W for each hidden layer, activation function ReI.U, and all parameters of the transition matrix are in 1]. Then, there are:
Theorem K.1. For any given n N,, ifD E D(n) satisfies: there is network F H Do (n) such that ((..)>p(yy(() > c) = 1 for a Wo. Do E N+,c > 0. Then we have that for any
W 2 O(Wo), D > R(Do) and 8 0, with probability at least 1-8 of DN, it holds Ap Z
1 0 WD + KmM [n(K/8), for all Mw.D n), where K = 12 Po-1
30

---

Wisi other weights of Published as a conference paper at ICLR 2025
However, this bound is relatively loose, and how to obtain bound that is polynomial in Wo, Da, is an important question.
Proof. Part One. For any given Dtr D', we show that there is network F E Hw,D such that (F( 2
W Wo Do ww---y for any (I, y) E Dtr.
By the assumption of D in the theorem, let Fi E Do (n) satisfy P ( 2 c) = 1. And W, the i-th transition matrix of Fi. b, is the i-th bias vector of Fi.
We will construct F as F = F22 o FpI, and we construct the two networks Fpp and Fp2 as following:
Fo Rd + W which has width W and depth Do. and the output layer of Fpt also uses the ReLU activation function.
Let W be matrix in IR where a, b E N+, and T(W, a1 b1) is a matrix in RRis defined as: for any [a].j [6], k1, l E ž, there are T(W, 01 b1) (1
T(W, a1, 61) are O. Then Fp1 is defined as:
(I): The first transition matrix is T(W1, W),), and the first bias vector is T(b,, W, 1):
(2): When i > 2. the i-th transition matrix is T(W; W, W), and the i-th bias vector is W Th,e W, 1).
W.
Then, have Fp = "
For Fp2: : RRW + R, which has width W and depth D - Do, we define it as:
(1): When i D Do. the i-th transition matrix is w,,, and the i-th bias vector is O, where T means all one matrix;
W (2): The last transition matrix is [(1, W). and the last bias vector is - Wo
1 D-
Then, F = F2 o Fi is what we want.
Part two. Similar to the proof of 4.4 there are at most Ne -Ww Po-1ow D-w.woa that (z) S W.
points in Dry such
Po- D-
Part three. If (F(x)
W Do D
then yF((z') > 0 for all ||2 - x1100 20o+.
As shown in Lemmal K.2 there yF(x'))
Do eW eW D-Po W wn-1n|/l x' lo00 So when W W
<l WW 4nW
100
||x 10o
2 W T there yF(x') 0.
Part four. Let = 20ot- Po-T we can divide [0, 1 into 2-/ disjoint cubes that have side
length r/2. Then by part three, we know that in a cube, F gives the same label to every point in such cube when [F(x)] > Po-1 c DW Do
2 for least in such cube.
Part Five. Prove the result.
By part four, name such m cubes as C1, 02, " Cm. and let P, = P P(a.))-(( Ec) and P. 2 P, when 2
As shown in part four, let S {i e [2,,) Der n Nc.yFFFFF FF() 2 [ [ Po Po then we have Ap(F) 2 Pr.
For any i, by Hoeffding inequality, with probability 1 1- -N there are at least NP,/2 points in cube c,. So for any given cn > let Pk, 2 cu. then, with probability least Em e Neg/2 of Drr. there are at least. NP,/2 points C, for any kn-
As shown in part two, there are at most Ne -
Po 1
points in Der such that yF(x) < So, by the above result, let T (ko, +1... NJ/S and N(C.) the number
Do-1 D-
W
31

---

Published as a conference paper at ICLR 2025
of points in C₁ with probability at least 1 Σ e-oo0/2 of Drr there E NP,/2 1 Po- aw Po +2
Eier N(C.) x Ne 1 100 Hence,
(D(F)
Σ LiesE P.
Eie(ho) P.- EiEr P.
I meo 2e -w 100 e/ Do +2
Now, we take Eo
2 2lm(m/8)
We get the result.
A required lemma is given below.
Lemma K.2. If a network with depth L and width W, the Los norm of each transition matrix does exceed 1. Then F(x) F(=) nW4-1||r
21loo.
Proof. is easy to see that
& $
|| co,0l=
2|1oo- Let F3 is the output of i-th layer of F, then
-(=)
I IAIA
W FD- - FD-1(2)lls>
W ( FD-2(2)llo
W (x) - (=)llo
nWD-1|lx - 2/|cc
which proves the lemma.
L EXPERIMENTS
In this section, we give some simple experiments to validate our theoretical conclusions. Our experimental setup as follows. We used MNIST data set and two-layer networks with ReLU activation function. When training the network, we ensure that the absolute value of each parameter smaller than by weight-clipping after each gradient descent. Two experiments are considered:
About size and accuracy: For networks with widths 100_200....90011100 ,900,1000, we observe their accuracy on the test after training. The results are shown Figure
About data and precision: Using training sets with 10% 20%, 90%, 100% of the original training set to train network with widths 200, 400 and 600. The results are shown in Figure 2
96.4
95.9
Acceracy
95.4
94.9
94.1
100
200
300
400
500
600
700
800
900
1030
Width
Figure 1: The accuracy on the different width networks.
Based on the experimental results, we have the following conclusions which confirm the correctness of Theorem 4.3.
32

---

Published as a conference paper at ICLR 2025
96.5
90.5
94.5
93.5
93
925
92
70%
90%
100%
Figure 2: The accuracy the 200,400,600 width networks with different number of data.
(I) Increasing the amount data or enlarging the network leads to greater accuracy. Specifically, when there are fewer data (smaller networks), increasing the number of data (width of the network) leads to a greater improvement in accuracy, which is consistent with Theorem 4.3 where the number of data (network size) is located on the denominator.
(2) When the number data fixed, increasing the network size has a limitation effect on improving accuracy, shown in Figure [ which is consistent with Theorem 4.3, because the number of data cannot affect the item in the generalization bound about network size.
(3) When the network is small, increasing the number of data only have limited effect improving accuracy, as shown in Figure 2 Accuracy on training 200-width network with the entire dataset is almost equivalent accuracy training 400-width network with 40% data in the entire dataset. This is consistent with Theorem 4.3, because the size of the network cannot affect the item in the generalization bound about the number of data.
33


Reviews:
[{"review_id": "Nwv1TM30Ko", "reviewer": "Reviewer_LSKf", "summary": "This paper studies generalization error of 2 layer neural networks that minimize empirical risk in a binary classification problem. The authors present a lower bound for accuracy based on the expressiveness of these networks, indicating that, with a sufficiently large training sample and network size, these networks can generalize. They offer an extension of the result to approximate empirical risk minimizers. They consider several other implications (relationship between the size of the neural network needed to represent the target distribution, and the quantity of data required to ensure generalization, robustness, etc.).", "questions": "How do the results relate to Buzaglo et al (ICML 2024)?\n\nHow do the results relate to Nagarajan and Kolter (NeurIPS best paper: arXiv:1902.04742)? How do you sidestep the issues they raise?\n\nWhat would empirical validation of these theories look like?\n\n\n\n## FOLLOW UP QUESTIONS - PLEASE RESPOND IF YOU CAN ##\n\nI have a question that would help me move to quickly resolve my concerns. The questions/remarks below (\"Other questions / comments.\") are less important and you should simply aim to address these in your own revisions. They are likely small typos or minor points that would confuse readers.\n\nKey questions:\n\n1. \nIn the proof of Lemma B.5, in (3) you write \"The L1,Inf norm of the three transition matrices...\". It would seem that there is assumption hidden here about the L1,Inf norms of the networks in H_W(n). I don't see any assumptions about the L1,Inf norms in definition of H_W(n) at the top of page 4. Can you maybe offer a bit more detail on the arguments arriving at these three norm bounds?\n\n\n\nOther questions / comments.\n\n1. It seems that the (W0,c) delivered by Proposition 4.2 are rather important in practice. These terms appear in the final bound as (W0 + c)/ cN and so, in particular, the tradeoff between W0 and c is essential. It may be the case that the minimum W0 is W0** but for that width W0**, the corresponding c** might be 2^{-100}, and maybe each increase in W0 only brings you a small improvement in c. Of course, these are just constant, but they would make the bounds impractical (and thus not explain practice).\n\n2. Defn 3.1. There is no standard notion of inf over a pair of random variables. You should make a probability one statement over the two samples: y_1 != y_2 ==> ||x_1 - x_2||_2 > 0. In particular, this implies no noise and a zero Bayes error rate. These are strong assumptions that should be highlighted with a remark. There is no role for the L2 norm here. The assumption is simply that H(y|x) = 0. for (x,y) ~ D, IINM.\n\n3. Proposition 3.2 is written in an odd way. M_W \\subset H_W and so you are simply arguing that M_W is non-empty, using uniform continuity (compactness + continuity).\n\n4. Proof of Proposition 4.2. There is a claim that I do not believe is true, starting \"Then, because D has a positive separation distance, [there exists a continuous function that f(x)=y with probability one under D]\" You would likely need a uniform gap ||x_1 - x_2||_2 >= gap  for some constant gap > 0. Regardless, it seems the only use of this assumption is to guarantee this continuous function f, and so just make that your assumption in the first place, which is then the weakest assumption that makes your argument go through, and is also the clearest explanation of your assumption.\n\n5. Theorem A.1. Missing quantification over x. \n\n6. Lemma B.4. b_i is a vector and so it doesn't have an L1,Inf norm. Do you mean L1. Wen et al. talk about the L1,inf of the combined bias and weights, so I believe you want L1?  And what is the justification for the claim that the L1,Inf norms at layer i are bounded by c_i? Or is this mean to be a definition? (If so, remove \"Then\" and write \"We also assume...\". \n\nWen et al. (Statistica Sinica 31 (2021), 1397-1414 doi:10.5705/ss.202018.0468) On CIFAR, c >= 15 in their experiments to \n\n\nNotation:\n\n7. Using W for the width and W_i for weight matrices is rather nonstandard. You elsewhere use w_i for whole matrices. Would be nice to have the notation consistent throughout the work.\n\n\n\n## UPDATE TO REVIEW\n\nThank you to the authors for answering my last minute questions.\n\n\nI'm finding it very hard to get comfortable with these results, but after considerable effort studying some key proofs in detail, I cannot find any errors, and so I will upgrade my score. I will lower my confidence, however, to reflect the fact that my intuition is feeling off. \n\nTheorem 4.3 is, in many ways, exactly what we would want to prove. But I'm finding it very difficult to believe that the ingredients assembled here are what has achieved it. I suspect that one of the assumptions is doing a lot more heavy lifting than is evident. Even so, this would be progress.\n\nIn terms of key assumptions, the existence of a finite width (W0) network that has confidence c with probability 1 is essential to the current proof. The proof also relies on a Rademacher bound for L1,Inf bounded networks. I have had to assume that this bound is correct. It is published in a reputable journal (Statistical Sinica), and so I think this is a fair assumption.\n\nI'm skeptical of ERM on the cross entropy as a model of standard deep learning algorithms, and so this is another source of my unease. The local minimum result alleviates this concern somewhat, but I've no idea how big the multiplicative factor (q) would be in practice and so I don't know if this is realistic for standard amounts of overparameterization. (And overparameterization likely affects q, so it is not solved by making W bigger.)\n\nI'm somewhat skeptical that H_W(n) has weights in [-1,1]. Standard overparameterized networks will have most weights MUCH smaller than this at initialization. It seems like a large space for ERM to operate over.\n\nTypos/comments:\n\nThe paper (especially the appendix) is full of English grammar errors. \n\nI'm still confused by the statement of Lemma B.4. I think the last sentence of the 1st paragraph (\"Then the L1,Inf norm of wi plus the L1,inf norm of bi is not more than ci.\") should start \"Assume the ...\" because there is no way to deduce these bounds from anything stated earlier. Indeed, the word \"then\" and \"there\" are misused throughout the paper and generally there are many language issues, but they are relatively easy to ignore.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "One strength is that the work is studying an important problem: explaining deep learning generalization.\n\nAnother strength is that they are using unconventional hypotheses, namely relying on the size of a network that exactly matches the data. This hypothesis was considered by Buzaglo et al in recent work (ICML 2024).", "weaknesses": "There are many weaknesses. \n\nPerhaps the biggest issue is that there's no new insight here. We have old school uniform convergence analyses, coming together with universal approximation arguments, but what have we learned? Negative results are for \"some distribution\" and don't explain practice. And there's no evidence the accuracy lower bounds (use error not accuracy) are strong enough to explain practice.\n\nThe 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 don't help here.)\n\nThe 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "1AsPTEUyQG", "reviewer": "Reviewer_WTwE", "summary": "The paper addresses the generalization of neural networks from the perspective of their expressive power. The authors provide new generalization bounds based on a network’s expressive capacity and without strong assumptions. The paper also provide a lower bound of generalizability. Additionally, the paper explores implications for over-parameterized networks, robustness, and the impact of different loss functions on generalizability.", "questions": "See weakness part.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "This paper provide a novel generalization bound based on expressive power of the network, which is different to traditional bounds. The assumption that there exists a network separates the distribution is more natural in practice than convexity or NTK. With rigorous analysis to both sample comlexity and lower bound of generalizability, the paper shows integrity of this research topic. Moreover, this work also provide some insights to the phenomena in deep learning such as overparameterization, robustness and the effect of different loss functions. Additionally, the paper is well organized and easy to understand.", "weaknesses": "This is a good paper in general. But I have some concerns about the contribution. The main results of the paper is showing the generalizability of shallow ReLU networks on a positive separated distribution that can be expressed by a smaller network. This maybe not a siginificant 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. With large enough sample size, the ERM solution certainly can generalize with high probability. And techinically, there are Rademacher complexity type bounds with sample complexity $O(1/\\sqrt{N})$ [1]. The only difficult of the main theorem is to estimate the Rademacher complexity of the class of larger ReLU networks. \nSo I doubt a little bit about the contribution of this paper.\n\n[1] Shai Shalev-Shwartz & Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "0ekOjdkszO", "reviewer": "Reviewer_6ywY", "summary": "The authors provide a number of useful generalization results for neural networks. They base their analysis on a definition of expressivity of *distributions* rather than functions (the classic universal approximation theory framework), and focus specifically on the case of distributions that satisfy a strict separability assumption, that implies that the Bayes risk is 0. The expressivity definition gives a natural, architecture-dependent measure of distribution complexity, W0. The authors focus do an algorithm-dependent analysis, focusing of empirical risk minimizers.\n\nThe main result is a lower bound on test accuracy of ERM, which depends on the ratio between W0 and the network’s width, W, and the number of training examples, N. Roughly, it implies that having a network width greater than W0 and a number of training examples which exceeds W0*[dimension] is sufficient for generalization.\n\nThey provide further analysis to follow-up on the main result, including upper bounds on generalization when the dataset is not big enough, generalization results for when ERM yields a local optimal point, and the explanation for various interesting phenomena (robustness, overparametrization, etc). The authors also provide discussion of implications of their results, and comparison to other existing results in literature.", "questions": "Please look at weaknesses section for some comments that might require a response.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The explicit dependence of the bounds on both training set size, but also the width of the network is not common in statistical learning theory bounds and is very important to explain various width-related generalization phenomena. \n\nThere is thorough analytical follow-up of the main result, including upper bounds on generalization when the dataset is not big enough, generalization results for when ERM yields a local optimal point, and the explanation for various interesting phenomena (robustness, overparametrization, etc). The authors also provide good discussion of implications of their results, and comparison to other existing results in literature.\n\nThe literature review, and comparison to relevant literature is complete.", "weaknesses": "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? \n\n2. While 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. \n\n3. There are some minor issues with rigour: \n- 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.\n- 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.\n\n4. [minor] 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "vs4DVhLWJI", "reviewer": "Reviewer_1rDw", "summary": "This paper investigates the generalizability of neural networks trained by empirical-risk-minimization (ERM) algorithms, focusing on understanding the factors that contribute to their ability to generalize well to unseen data. The authors consider two-layer networks and approach generalizability from the perspective of the network's expressive ability, which refers to the network's capacity to represent complex functions and effectively fit the underlying data distribution. The paper establishes a lower bound for the accuracy of neural networks that minimize empirical risk, suggesting that these networks can generalize effectively given sufficiently large training datasets and network sizes. The paper further investigates the lower bound by examining scenarios without enough data. The paper finally provides insights into several observed phenomena in deep learning, including robust overfitting, the importance of over-parameterization, and the impact of loss functions.", "questions": "1. In Theorem 1.1., please clarify the meanings of \"expressing the data distribution with a neural network\" and \"with high probability of a dataset\". \n2. Under Theorem 1.2, what are the definitions of \"robust memorizing\" and \"robust fitting\"?\n3. 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?\n4. In Section 5, the authors provide upper bound for accuracy without enough data. Could the authors relate the upper bound and the previously derived lower bound and have some discussions?\n5.  Under Theorem 6.2, it would be better to elucidate more on the dependency of $c_1$ on $\\epsilon$.\n6. In Proposition 6.5, how do the numbers \"0.9\" and \"0.6\" come out? Similarly for Theorem 6.7.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper explores generalization from a unique perspective by connecting it to the expressive ability of neural networks, providing a fresh perspective on understanding why neural networks generalize well.\n2. The paper do not place strong assumptions on data or loss functions, making the results more applicable to practical scenarios.\n3. The paper highlights the importance of choosing appropriate network models and activation functions tailored to the specific data distribution to enhance generalization capabilities.", "weaknesses": "1. The focus on two-layer networks might limit the applicability of the findings to more complex and deeper network architectures prevalent in practice. \n2. The paper primarily focuses on theoretical analysis and does not include empirical studies to validate its claims and insights.\n3. The assumptions on separable data distributions potentially oversimplifies the complexities of real-world deep learning applications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "2bQBTcOj1f", "reviewer": "Reviewer_soP8", "summary": "This paper studies the generalization capabilities of two-layer neural networks (NNs) with small empirical error. Based on the expressive power of NNs, the authors derive a lower bound for classification accuracy, or equivalently, an upper bound for classification error, in NNs trained with minimum empirical risk. Their results show that large network width and large sample size can lead to high classification accuracy. Additionally, this conclusion extends to NNs with somewhat higher empirical risk. By their theoretical analysis, the authors provide insights on factors influencing generalization, such as the choice of activation functions, the role of overparameterization, and the impact of loss function selection", "questions": "1. 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.\n\n2. 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?\n\n3. In the proof of Proposition 4.2, in Line 723-725, it’s stated that $\\mathcal{F}_A$ is a network whose parameter is the corresponding parameter of $\\mathcal{F}$ divided by $A$, with $\\mathcal{F}_A=\\mathcal{F}/{A^2}$. Could you clarify why this equality holds? In addition, if $A<1$, then each parameter of $\\mathcal{F}_A$ might exceed the domain $[-1,1]$, it seems that the parameter domain constraint will be violated.\n\n4. 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|< Ne^{-kc/2+2}$ is only meaningful if $kc\\geq 4$, as $|S|\\leq N$ clearly holds. This is also implied in Line 853, where the lower bound would be vacuous for $kc\\leq 4$ since $\\mathbb{E}_{(x,y)\\sim\\mathcal{D}}yg(x)\\geq -\\frac{kc}{2}$ already holds trivially. Perhaps adding a condition such as $W\\geq \\frac{4(W_0+1)}{c}$ in the theorem statement might improve clarity.\n\n5. The motivation for the loose results in Section 5.1 is unclear, as the conclusions and insights from these $W$-independent results seem well-known.\n\n6. 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.\n\n[R1] Leslie Rice, Eric Wong, and Zico Kolter. \"Overfitting in adversarially robust deep learning.\" International conference on machine learning. PMLR, 2020.\n\nMinor comments:\n\n1. Some references are missing. For example, stability-based bounds have been extended beyond Hardt et al. (2016) to cover nonsmooth cases (e.g., [R2, R3]), among others. Additionally, PAC-Bayesian and information-theoretic generalization bounds are well-known for being algorithm-dependent and, in some cases, data-dependent. These methods generally do not assume Lipschitz continuity, convexity, or smoothness and some derive fast-rate bounds in the low empirical risk regime. Refer to [R4, R5] for further reading on these types of generalization bounds.\n\n[R2] Raef Bassily, et al. \"Stability of stochastic gradient descent on nonsmooth convex losses.\" Advances in Neural Information Processing Systems 33 (2020): 4381-4391.\n\n[R3] Yunwen Lei. \"Stability and generalization of stochastic optimization with nonconvex and nonsmooth problems.\" The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.\n\n[R4] Pierre Alquier. \"User-friendly introduction to PAC-Bayes bounds.\" Foundations and Trends® in Machine Learning 17.2 (2024): 174-303.\n\n[R5] Fredrik Hellström, et al. \"Generalization bounds: Perspectives from information theory and PAC-Bayes.\" arxiv preprint arxiv:2309.04381 (2023).\n\n2. The paper would benefit from substantial proofreading, as there are numerous typos (e.g., Line 092: \"reached is minimum\" ---> \"reached its minimum\"; Line 082: \"robust memorizing\"--->\"robustly memorizing\", ...) and inconsistencies in notation (e.g., $\\mathcal{F}$ vs. $F$; $Z_{2W}(n)$ vs. $\\mathbf{H}_{2W}(n)$, ...). Please review the manuscript carefully to identify and fix these issues.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Unlike many previous results that rely on bounded loss functions, this paper analyzes the more practically relevant cross-entropy loss. Additionally, the theoretical results in this paper do not depend on any convexity or smoothness assumptions of the loss function.\n\n2. The derived lower bound on classification accuracy suggests that wider NNs have more potential for high accuracy, which is desirable for deep learning theory.", "weaknesses": "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]^d$ (where $d$ is the number of total parameters). It seems that these constraints are essential for the theoretical developments, and further relaxing these constraints does not seem straightforward.\n\n2. My another concern arises from the use of Rademacher complexity to derive the lower bound on accuracy (or equivalently, the upper bound on error), which could be loose. For example, 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.\n\nAdditional concerns are outlined in the questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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:

Decision: Accept (Poster)