# Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation

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

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2019.

## Built on by (most cited first, 30 of 71)

- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Same Pre-training Loss, Better Downstream: Implicit Bias Matters for Language Models](https://mlsanity.com/paper/2210.14199/) (2022)
- [Improved Regularization and Robustness for Fine-tuning in Neural Networks](https://mlsanity.com/paper/2111.04578/) (2021)
- [Noisy Recurrent Neural Networks](https://mlsanity.com/paper/2102.04877/) (2021)
- [A Theoretical Study of Inductive Biases in Contrastive Learning](https://mlsanity.com/paper/2211.14699/) (2022)
- [Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion](https://mlsanity.com/paper/2302.04451/) (2023)
- [Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization](https://mlsanity.com/paper/2307.11007/) (2023)
- [Generalization bounds via distillation](https://mlsanity.com/paper/2104.05641/) (2021)
- [Noisy Feature Mixup](https://mlsanity.com/paper/2110.02180/) (2021)
- [Knowledge Overshadowing Causes Amalgamated Hallucination in Large Language Models](https://mlsanity.com/paper/2407.08039/) (2024)
- [Training robust and generalizable quantum models](https://mlsanity.com/paper/2311.11871/) (2023)
- [Integral Probability Metrics PAC-Bayes Bounds](https://mlsanity.com/paper/2207.00614/) (2022)
- [Demystifying Causal Features on Adversarial Examples and Causal Inoculation for Robust Network by Adversarial Instrumental Variable Regression](https://mlsanity.com/paper/2303.01052/) (2023)
- [Adversarial robustness of sparse local Lipschitz predictors](https://mlsanity.com/paper/2202.13216/) (2022)
- [On the Lipschitz Constant of Deep Networks and Double Descent](https://mlsanity.com/paper/2301.12309/) (2023)
- [Generalization Bound and New Algorithm for Clean-Label Backdoor Attack](https://mlsanity.com/paper/2406.00588/) (2024)
- [On Measuring Excess Capacity in Neural Networks](https://mlsanity.com/paper/2202.08070/) (2022)
- [MaxMatch: Semi-Supervised Learning with Worst-Case Consistency](https://mlsanity.com/paper/2209.12611/) (2022)
- [Koopman-based generalization bound: New aspect for full-rank weights](https://mlsanity.com/paper/2302.05825/) (2023)
- [Differentiable Neural Networks with RePU Activation: with Applications to Score Estimation and Isotonic Regression](https://mlsanity.com/paper/2305.00608/) (2023)
- [Sparsity-aware generalization theory for deep neural networks](https://mlsanity.com/paper/2307.00426/) (2023)
- [Recent Advances in Large Margin Learning](https://mlsanity.com/paper/2103.13598/) (2021)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)
- [On progressive sharpening, flat minima and generalisation](https://mlsanity.com/paper/2305.14683/) (2023)
- [Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering](https://mlsanity.com/paper/2307.11030/) (2023)
- [An Information-Theoretic Framework for Supervised Learning](https://mlsanity.com/paper/2203.00246/) (2022)
- [Max-Margin Works while Large Margin Fails: Generalization without Uniform Convergence](https://mlsanity.com/paper/2206.07892/) (2022)
- [On the Importance of Gradient Norm in PAC-Bayesian Bounds](https://mlsanity.com/paper/2210.06143/) (2022)
- [On Size-Independent Sample Complexity of ReLU Networks](https://mlsanity.com/paper/2306.01992/) (2023)

## Abstract (arXiv)

Existing Rademacher complexity bounds for neural networks rely only on norm control of the weight matrices and depend exponentially on depth via a product of the matrix norms. Lower bounds show that this exponential dependence on depth is unavoidable when no additional properties of the training data are considered. We suspect that this conundrum comes from the fact that these bounds depend on the training data only through the margin. In practice, many data-dependent techniques such as Batchnorm improve the generalization performance. For feedforward neural nets as well as RNNs, we obtain tighter Rademacher complexity bounds by considering additional data-dependent properties of the network: the norms of the hidden layers of the network, and the norms of the Jacobians of each layer with respect to all previous layers. Our bounds scale polynomially in depth when these empirical quantities are small, as is usually the case in practice. To obtain these bounds, we develop general tools for augmenting a sequence of functions to make their composition Lipschitz and then covering the augmented functions. Inspired by our theory, we directly regularize the network's Jacobians during training and empirically demonstrate that this improves test performance.