The role of invariance in spectral complexity-based generalization bounds

Abstract

Deep convolutional neural networks (CNNs) have been shown to be able to fit a random labeling over data while still being able to generalize well for normal labels. Describing CNN capacity through a posteriori measures of complexity has been recently proposed to tackle this apparent paradox. These complexity measures are usually validated by showing that they correlate empirically with GE; being empirically larger for networks trained on random vs normal labels. Focusing on the case of spectral complexity we investigate theoretically and empirically the insensitivity of the complexity measure to invariances relevant to CNNs, and show several limitations of spectral complexity that occur as a result. For a specific formulation of spectral complexity we show that it results in the same upper bound complexity estimates for convolutional and locally connected architectures (which don't have the same favorable invariance properties). This is contrary to common intuition and empirical results.

arXiv commentarXiv admin note: text overlap with arXiv:1801.00171

References in corpus (18)

• Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks
• Understanding deep learning requires rethinking generalization
• Understanding Deep Convolutional Networks
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Robust Large Margin Deep Neural Networks
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Predicting the Generalization Gap in Deep Networks with Margin Distributions
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• Uniform convergence may be unable to explain generalization in deep learning
• Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach
• Stronger generalization bounds for deep nets via a compression approach
• Norm-Based Capacity Control in Neural Networks
• Data-dependent Sample Complexity of Deep Neural Networks via Lipschitz Augmentation
• Identifying Generalization Properties in Neural Networks
• Generalization Error of Invariant Classifiers
• Understanding Generalization and Optimization Performance of Deep CNNs