Spectrally-normalized margin bounds for neural networks
By Peter L. Bartlett, Dylan J. Foster, Matus Telgarsky. 2017
1,473 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Scaling & Learning Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yoshua Bengio
- Sergey Levine
- Percy Liang
- Quoc V. Le
- Ruslan Salakhutdinov
- Mohit Bansal
- Jianfeng Gao
- Dacheng Tao
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Trevor Darrell
- Ming-Hsuan Yang
- Xiaogang Wang
- Jitendra Malik
- Andrew Zisserman
- Andrea Vedaldi
In Scaling & Learning Theory
Citations in the corpus
- mixup: Beyond Empirical Risk Minimization (2017, methodology): “Among the several methods aiming to solve this problem, some have proposed to penalize the norm of the Jacobian of the model to control its Lipschitz constant (Drucker & Le Cun, 1992; Cisse et al., 2017; Bartlett et al., 2017; Hein & Andriushchenko, 2017).”
- The Power of Interpolation: Understanding the Effectiveness of SGD in Modern Over-parametrized Learning (2017, background): “While we do not yet understand why these interpolated classifiers generalize so well to unseen data, there is ample evidence for their excellent performance in deep neural networks [GAGN15, CCSL16, ZBH + 16, HLWvdM16, SEG + 17, BFT17], kernels [MB17] and boosting [SFBL98].”
- The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “…metrics such as those based on PAC-Bayes [McAllester, 1999, Dziugaite and Roy, 2017, Neyshabur et al., 2017b], VC dimension [Vapnik and Chervonenkis, 1971], and parameter norms [Bartlett et al., 2017, Neyshabur et al., 2017a] also suggest that modern architectures have very large capacity.”
- Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “[3, 23, 21] proved spectrally-normalized margin-based generalization bounds, [9, 23] derived bounds from a PAC-Bayes approach, and [1, 33, 4] derived bounds from the compression point of view.”
- Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Replacing our current covering number arguments with more intricate notions such as margin-based bounds (Bartlett et al., 2017) would extend the scope and usefulness of our theoretical guarantees.”
- On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, positive): “Starting from the first studies focusing on this simple dichotomy, the Lipschitz constant L of a DNN has been established as a commonplace measure of both smoothness and generalization [82, 72, 39] and still constitutes a key ingredient for current evaluations of model capacity [8, 30].”
- What is being transferred in transfer learning? (2020, background): “There is a vast literature in analyzing generalization performance of DNNs by considering the ratio of Frobenius norm to spectral norm for different layers [1, 30].”
- Sorting out Lipschitz function approximation (2018, background): “The Lipschitz constant of a neural network has been connected theoretically and empirically to its generalization performance [5, 4, 35, 36, 44].”
- Regularisation of neural networks by enforcing Lipschitz continuity (2018, background): “In several of the most recent works (Bartlett et al. 2017; Neyshabur 2017; Golowich et al. 2020), some of the dominant terms in these bounds are equal to the upper bound of the Lipschitz constant of neural networks as we derive it in this paper.”
- Lipschitz-Margin Training: Scalable Certification of Perturbation Invariance for Deep Neural Networks (2018, background): “This margin has been studied in relationship to generalization bounds [17, 3, 22].”
- Exploring Generalization in Deep Learning (2017, background): “[2] suggested different norms of network parameters to measure the capacity of neural networks.”
- Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “A line of research proposed norm-based (e.g. Bartlett et al. (2017a)) and compression-based bounds (Arora et al., 2018).”
- A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks (2017, methodology): “This is an entirely different analysis approach from Bartlett et al.’s [1] covering number analysis.”
- Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers (2018, background): “Several works [6, 11, 24, 39] explain generalization by studying some other “complexity” of the learned networks.”
- Behaviour Suite for Reinforcement Learning (2019, background): “It is only now, several years after these high profile successes, that learning theory has begun to turn its attention back to deep learning [24, 3, 5].”
- Stronger generalization bounds for deep nets via a compression approach (2018, background): “Even the generalization based on parameter counting arguments does have an extra dependence on depth (Bartlett et al., 2017).”
- Randomized Prior Functions for Deep Reinforcement Learning (2018, methodology): “Instead, training an additive network via SGD (per BSP) may provide a more e ective regularization on the output function [73, 38, 5].”
- A Study on Overfitting in Deep Reinforcement Learning (2018, background): “Similar phenomenons are reported in supervised learning (Zhang et al., 2017), and recent work shows various approaches to explain this (Bartlett et al., 2017; Neyshabur et al., 2017; Advani & Saxe, 2017; Smith & Le, 2017; Dziugaite & Roy, 2017; Liang et al., 2017).”
- Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”