Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Ability
This provides theoretical insights into generalization in deep learning, addressing a foundational issue for researchers and practitioners, though it is incremental as it builds on existing bounds with less stringent assumptions.
The paper tackles the problem of explaining why over-parameterized neural networks generalize well despite classic theory failing to account for it, establishing a lower bound for population accuracy based on network expressiveness and showing that with sufficient data and network size, such networks can generalize effectively.
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.