Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive ability
Lijia Yu, Yibo Miao, Yifan Zhu, Xiao-Shan Gao, Lijun Zhang · 2025
Read Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive ability by Lijia Yu, Yibo Miao, Yifan Zhu, Xiao-Shan Gao, Lijun Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-04111.txt.
Introduction
Lijia Yu and co-authors bound how well risk trim nets can do on new data by how much they can say, in a paper from 2025. Old bounds lean on size counts that fail for fat nets, which oft read new data well in the field. Their bound rests on the net own say span.
With data and net size both rich, such nets can reach a set floor of new data truth, fat or lean. A must term flips the tale: for some data kinds, the data bulk a net needs to read true past its own size. Fruit reads shed light on firm truth, fat gain, and loss pick in deep learn, they say.
Catalog record
| CREATOR | Lijia Yu, Yibo Miao, Yifan Zhu, Xiao-Shan Gao, Lijun Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 119 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-04111
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive ability Lijia Yu, Yibo Miao, Yifan Zhu, Xiao-Shan Gao, Lijun Zhang Abstract The primary objective of learning methods is generalization. Classic uniform generalization bounds, which rely on VC-dimension or Rademacher complexity, fail to explain the significant attribute that over-parameterized models in deep learning exhibit nice generalizability. On the other hand, algorithm-dependent generalization bounds, like stability bounds, often rely on strict assumptions. To establish generalizability under less stringent assumptions, this paper investigates the generalizability of neural networks that minimize or approximately minimize empirical risk. We establish a lower bound for population accuracy based on the expressiveness of these networks, which indicates that with an adequate large number of training samples and network sizes, these networks, including over-parameterized ones, can generalize effectively. Additionally, we provide a necessary condition 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-parameterization, and effect of loss function on generalization. 1 Introduction Understanding the mechanisms behind the nice generalization ability of deep neural networks remains a 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 as a critical theoretical framework for evaluating the generalizability of learning algorithms. Let {\mathcal{F}} be a neural network, {\mathcal{D}} the data distribution, and L({\mathcal{F}}(x),y)={\mathbb{I}}(\widehat{\mathcal{F}}(x)=y) where \widehat{\mathcal{F}}(x) is the classification result of {\mathcal{F}}(x) . For a hypothesis space {\mathbf{H}} and any {\mathcal{F}}\in{\mathbf{H}} , with probability 1-\delta of dataset {\mathcal{D}}_{tr} sampled i.i.d. from {\mathcal{D}} , we have the classic uniform generalization bound ( Mohri et al., 2018 ) |{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}[L({\mathcal{F}}(x),y)]-{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{tr}}[L({\mathcal{F}}(x),y)]|<\sqrt{(8d\ln\frac{2eN}{d}+8\ln\frac{4}{\delta})/N} (1) where d is the VC-dimension of {\mathbf{H}} and N=|{\mathcal{D}}_{tr}| . 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-dependent 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 are also obtained by assuming the convexity and Lipschitz properties of the total loss ( Hardt et al., 2016 ; Kuzborskij & Lampert, 2018 ) . Unfortunately, uniform generalization bounds fail to explain the important phenomenon that over-parameterized models exhibit nice generalizability ( Belkin et al., 2019 ) , 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 ReLU networks ( Bartlett et al., 2021 ) , which renders the bound in equation 1 useless for over-parameterized models. Most of the algorithmic-dependent generalization bounds make strong and unrealistic assumptions. For example, the NTK condition is used to reduce the training to a convex optimization ( Ji & 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 generalization of networks that minimize or approximately minimize the empirical risk, that is, the networks {\mathcal{F}}\in{\mathbf{M}}=\arg\min_{{\mathcal{G}}\in{\mathbf{H}}}\sum_{(x,y)\in{\mathcal{D}}_{tr}}L({\mathcal{G}}(x),y) . The approach is reasonable because most practical training will lead to a very small empirical risk. In this paper, we consider two-layer networks, like many previous theoretical works ( Ba et al., 2020 ; Ji & Telgarsky, 2020 ; 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, as shown below. Theorem 1.1 (Informal, Corollary 4.5 ) . Let data distribution {\mathcal{D}} satisfy the condition that a two-layer network with width W_{0} can reach accuracy 1 over {\mathcal{D}} . Then with high probability of {\mathcal{D}}_{tr}\sim{\mathcal{D}}^{N} , if N\geq\Omega(W_{0}^{2}) and \hbox{width}({\mathcal{F}})\geq\Omega(W_{0}) for {\mathcal{F}}\in{\mathbf{M}} , then {\mathcal{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 \hbox{width}({\mathcal{F}}) are independent, our bounds can be used to explain the nice generalizability of over-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 a distribution, as shown below. Theorem 1.2 (Informal, Section 5 ) . For some data distribution {\mathcal{D}} , if the width required for a two-layer network with {{\rm{ReLU}}} activation function to express {\mathcal{D}} is at least W_{0} , then with high probability for a dataset with fewer than O(W_{0}) elements, any network that minimizes the empirical risk over {\mathcal{D}} has poor generalization. Finally, while deep neural networks exhibit good generalization, numerous classical experimental results indicate that these networks encounter problems such as robustness and generalization. We provide some interpretability for these problems based on our theoretical results. Let {\mathcal{D}}_{tr} be a dataset and {\mathcal{F}}\in{\mathbf{M}} . Then, three phenomena of deep learning are discussed with our theoretical results. Robustness Generalization. (Section 6.1 ) It is known that robust memorization for a dataset {\mathcal{D}}_{tr} is more difficult than memorization for {\mathcal{D}}_{tr} ( Park et al., 2021 ; Li et al., 2022 ; Yu et al., 2024a ) . We further show that when robust memorization of {\mathcal{D}}_{tr} is much more difficult than memorization of {\mathcal{D}}_{tr} , then the robustness accuracy of {\mathcal{F}} over {\mathcal{D}} has an upper bound which may be low, or {\mathcal{F}} has no robustness generalization over {\mathcal{D}} . Importance of over-parameterization. (Section 6.2 ) It is recognized that over-parameterized networks have nice generalizaility ( Belkin et al., 2019 ; Bartlett et al., 2021 ) . In this regard, we show that when the network is large enough, a small empirical loss leads to high test accuracy. In contrast, when the network {\mathcal{F}} is not large enough, there exist networks that achieve good generalization but cannot be found by minimizing the empirical risk. Loss function. (Section 6.3 ) We show that for some loss function, generalization may not be achieved. If the loss function has reached its minimum value or is a 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 bounds usually depend on the VC-dimension or the Rademacher complexity ( Mohri et al., 2018 ) . In ( Harvey et al., 2017 ; Bartlett et al., 2019 ; Yang et al., 2023