Spectrally-normalized margin bounds for neural networks

Abstract

This paper presents a margin-based multiclass generalization bound for neural networks that scales with their margin-normalized "spectral complexity": their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor. This bound is empirically investigated for a standard AlexNet network trained with SGD on the mnist and cifar10 datasets, with both original and random labels; the bound, the Lipschitz constants, and the excess risks are all in direct correlation, suggesting both that SGD selects predictors whose complexity scales with the difficulty of the learning task, and secondly that the presented bound is sensitive to this complexity.

Comparison to arXiv v1: 1-norm in main bound refined to (2,1)-group-norm. Comparison to NIPS camera ready: typo fixes

References in corpus (2)

• Explaining and Harnessing Adversarial Examples
• Implicit Regularization in Deep Learning

Cited by in corpus (87)

• mixup: Beyond Empirical Risk Minimization
• Benign Overfitting in Linear Regression
• Neural-Fly Enables Rapid Learning for Agile Flight in Strong Winds
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Learning ReLU Networks on Linearly Separable Data: Algorithm, Optimality, and Generalization
• When Do Extended Physics-Informed Neural Networks (XPINNs) Improve Generalization?
• The Modern Mathematics of Deep Learning
• Fisher-Rao Metric, Geometry, and Complexity of Neural Networks
• To understand deep learning we need to understand kernel learning
• The no-free-lunch theorems of supervised learning
• Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Stronger generalization bounds for deep nets via a compression approach
• Implicit Regularization in Deep Learning
• Predicting trends in the quality of state-of-the-art neural networks without access to training or testing data
• What Makes Multi-modal Learning Better than Single (Provably)
• Approximation and Estimation for High-Dimensional Deep Learning Networks
• Scalable End-to-End Autonomous Vehicle Testing via Rare-event Simulation
• Invariant Causal Prediction for Block MDPs
• SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks
• On the Benefit of Width for Neural Networks: Disappearance of Bad Basins
• Exactly Computing the Local Lipschitz Constant of ReLU Networks
• Rethinking generalization requires revisiting old ideas: statistical mechanics approaches and complex learning behavior
• Interpolated Adversarial Training: Achieving Robust Neural Networks without Sacrificing Too Much Accuracy
• Minimax Estimation of Conditional Moment Models
• Neural Collapse Under MSE Loss: Proximity to and Dynamics on the Central Path
• Stabilizing Gradients for Deep Neural Networks via Efficient SVD Parameterization
• Error Bounds of Imitating Policies and Environments
• How degenerate is the parametrization of neural networks with the ReLU activation function?
• Inductive Biases and Variable Creation in Self-Attention Mechanisms
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization
• System Identification Through Lipschitz Regularized Deep Neural Networks
• Generalization Bounds for Convolutional Neural Networks
• A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks
• Minnorm training: an algorithm for training over-parameterized deep neural networks
• Generalization Bounds For Unsupervised and Semi-Supervised Learning With Autoencoders
• Fix your classifier: the marginal value of training the last weight layer
• The Training Process of Many Deep Networks Explores the Same Low-Dimensional Manifold
• Learning Deep Hidden Nonlinear Dynamics from Aggregate Data
• Learning Curves for Analysis of Deep Networks
• Robustness to Pruning Predicts Generalization in Deep Neural Networks
• Gradient-Free Learning Based on the Kernel and the Range Space
• Interpreting Deep Learning: The Machine Learning Rorschach Test?
• Robust Visual Domain Randomization for Reinforcement Learning
• On the Role of Dataset Quality and Heterogeneity in Model Confidence
• Deep ReLU Networks Preserve Expected Length
• Analytic Network Learning
• Implicit Rugosity Regularization via Data Augmentation
• Lipschitz Networks and Distributional Robustness
• Deep KKL: Data-driven Output Prediction for Non-Linear Systems
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers
• Towards Understanding the Generalization Bias of Two Layer Convolutional Linear Classifiers with Gradient Descent
• Are deep ResNets provably better than linear predictors?
• Theory III: Dynamics and Generalization in Deep Networks
• Noether: The More Things Change, the More Stay the Same
• Capacity Control of ReLU Neural Networks by Basis-path Norm
• Markov-Lipschitz Deep Learning
• Spectral Pruning: Compressing Deep Neural Networks via Spectral Analysis and its Generalization Error
• Asymptotic Singular Value Distribution of Linear Convolutional Layers
• Generalization bounds for graph convolutional neural networks via Rademacher complexity
• Misclassification bounds for PAC-Bayesian sparse deep learning
• Imitation Learning from Pixel-Level Demonstrations by HashReward
• Information-Theoretic Local Minima Characterization and Regularization
• Post-mortem on a deep learning contest: a Simpson's paradox and the complementary roles of scale metrics versus shape metrics
• Deep Manifold Transformation for Nonlinear Dimensionality Reduction
• Single Layer Predictive Normalized Maximum Likelihood for Out-of-Distribution Detection
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks
• On the Robustness and Generalization of Deep Learning Driven Full Waveform Inversion
• Information Theoretic Interpretation of Deep learning
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds
• Inferential Wasserstein Generative Adversarial Networks
• Harmonic Decompositions of Convolutional Networks
• Achieving Small Test Error in Mildly Overparameterized Neural Networks
• Gentle Local Robustness implies Generalization
• Non-asymptotic Excess Risk Bounds for Classification with Deep Convolutional Neural Networks
• Revisiting hard thresholding for DNN pruning
• Residual Networks: Lyapunov Stability and Convex Decomposition
• FeTa: A DCA Pruning Algorithm with Generalization Error Guarantees
• Noise Stability Regularization for Improving BERT Fine-tuning
• Tangent Space Sensitivity and Distribution of Linear Regions in ReLU Networks
• How Analysis Can Teach Us the Optimal Way to Design Neural Operators
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics
• From deep to Shallow: Equivalent Forms of Deep Networks in Reproducing Kernel Krein Space and Indefinite Support Vector Machines
• A Theoretical Analysis of Learning with Noisily Labeled Data