# Generalization bounds for regression and classification on adaptive covering input domains

arXiv: https://arxiv.org/abs/2407.19715 · HTML: https://mlsanity.com/paper/2407.19715/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 51 references that are in the map.
- First posted on arXiv 29 Jul 2024.

## Builds on (most cited first, 27 of 27)

- [Score-Based Generative Modeling through Stochastic Differential Equations](https://mlsanity.com/paper/2011.13456/) (2020)
- [Deep Unsupervised Learning using Nonequilibrium Thermodynamics](https://mlsanity.com/paper/1503.03585/) (2015)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [On the Number of Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1402.1869/) (2014)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks](https://mlsanity.com/paper/1703.02930/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [Generalization in diffusion models arises from geometry-adaptive harmonic representations](https://mlsanity.com/paper/2310.02557/) (2023)
- [Bounding and Counting Linear Regions of Deep Neural Networks](https://mlsanity.com/paper/1711.02114/) (2017)
- [On the number of response regions of deep feed forward networks with piece-wise linear activations](https://mlsanity.com/paper/1312.6098/) (2013)
- [Deep vs. shallow networks : An approximation theory perspective](https://mlsanity.com/paper/1608.03287/) (2016)
- [Why Do Deep Residual Networks Generalize Better than Deep Feedforward Networks? -- A Neural Tangent Kernel Perspective](https://mlsanity.com/paper/2002.06262/) (2020)
- [Implicit Regularization in ReLU Networks with the Square Loss](https://mlsanity.com/paper/2012.05156/) (2020)
- [Nearly Optimal VC-Dimension and Pseudo-Dimension Bounds for Deep Neural Network Derivatives](https://mlsanity.com/paper/2305.08466/) (2023)
- [Generalization Error Bounds for Deep Neural Networks Trained by SGD](https://mlsanity.com/paper/2206.03299/) (2022)
- [Wide and Deep Neural Networks Achieve Optimality for Classification](https://mlsanity.com/paper/2204.14126/) (2022)
- [Analysis of function approximation and stability of general DNNs in directed acyclic graphs using un-rectifying analysis](https://mlsanity.com/paper/2206.05997/) (2022)
- [Representation and decomposition of functions in DAG-DNNs and structural network pruning](https://mlsanity.com/paper/2306.09707/) (2023)

## Abstract (arXiv)

Our main focus is on the generalization bound, which serves as an upper limit for the generalization error. Our analysis delves into regression and classification tasks separately to ensure a thorough examination. We assume the target function is real-valued and Lipschitz continuous for regression tasks. We use the 2-norm and a root-mean-square-error (RMSE) variant to measure the disparities between predictions and actual values. In the case of classification tasks, we treat the target function as a one-hot classifier, representing a piece-wise constant function, and employ 0/1 loss for error measurement. Our analysis underscores the differing sample complexity required to achieve a concentration inequality of generalization bounds, highlighting the variation in learning efficiency for regression and classification tasks. Furthermore, we demonstrate that the generalization bounds for regression and classification functions are inversely proportional to a polynomial of the number of parameters in a network, with the degree depending on the hypothesis class and the network architecture. These findings emphasize the advantages of over-parameterized networks and elucidate the conditions for benign overfitting in such systems.