Norm-based generalisation bounds for multi-class convolutional neural networks

Abstract

We show generalisation error bounds for deep learning with two main improvements over the state of the art. (1) Our bounds have no explicit dependence on the number of classes except for logarithmic factors. This holds even when formulating the bounds in terms of the $L^2$-norm of the weight matrices, where previous bounds exhibit at least a square-root dependence on the number of classes. (2) We adapt the classic Rademacher analysis of DNNs to incorporate weight sharing -- a task of fundamental theoretical importance which was previously attempted only under very restrictive assumptions. In our results, each convolutional filter contributes only once to the bound, regardless of how many times it is applied. Further improvements exploiting pooling and sparse connections are provided. The presented bounds scale as the norms of the parameter matrices, rather than the number of parameters. In particular, contrary to bounds based on parameter counting, they are asymptotically tight (up to log factors) when the weights approach initialisation, making them suitable as a basic ingredient in bounds sensitive to the optimisation procedure. We also show how to adapt the recent technique of loss function augmentation to our situation to replace spectral norms by empirical analogues whilst maintaining the advantages of our approach.

References in corpus (15)

• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• The Singular Values of Convolutional Layers
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Norm-Based Capacity Control in Neural Networks
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience
• Lipschitz constant estimation of Neural Networks via sparse polynomial optimization
• On Generalization Bounds of a Family of Recurrent Neural Networks
• Generalization Bounds for Convolutional Neural Networks
• Why ResNet Works? Residuals Generalize
• Fast generalization error bound of deep learning without scale invariance of activation functions

Cited by in corpus (1)

• Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets