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

Abstract

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.

Cited by in corpus (20)

• Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss
• Theoretical Analysis of Self-Training with Deep Networks on Unlabeled Data
• Optimal Regularization Can Mitigate Double Descent
• On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learning
• The Implicit and Explicit Regularization Effects of Dropout
• Heteroskedastic and Imbalanced Deep Learning with Adaptive Regularization
• Learning Optimal Representations with the Decodable Information Bottleneck
• Shape Matters: Understanding the Implicit Bias of the Noise Covariance
• Quantifying the generalization error in deep learning in terms of data distribution and neural network smoothness
• Noisy Recurrent Neural Networks
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks
• Norm-based generalisation bounds for multi-class convolutional neural networks
• Reinforcement Learning for Industrial Control Network Cyber Security Orchestration
• A Law of Robustness for Weight-bounded Neural Networks
• Composed Fine-Tuning: Freezing Pre-Trained Denoising Autoencoders for Improved Generalization
• Neural Abstract Reasoner
• Heating up decision boundaries: isocapacitory saturation, adversarial scenarios and generalization bounds
• The role of invariance in spectral complexity-based generalization bounds
• Recent Advances in Large Margin Learning
• Identifying and Exploiting Structures for Reliable Deep Learning