A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks

By Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, Nati Srebro. 2017

677 citations recorded by the source corpus.

We present a generalization bound for feedforward neural networks in terms of the product of the spectral norm of the layers and the Frobenius norm of the weights. The generalization bound is derived using a PAC-Bayes analysis.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Control and Systems Engineering, 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

In Computer Vision and Pattern Recognition

In Control and Systems Engineering

In Scaling & Learning Theory

Citations in the corpus

A Constructive Prediction of the Generalization Error Across Scales (2019, background): “Theoretical error bounds: Much attention has been given to theoretical explanations of the generalization capabilities of deep neural networks (Neyshabur et al., 2017a;b; Allen-Zhu et al., 2018a;b; Arora et al., 2018).”
The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, methodology): “…a crude approximation of a model’s capacity, more sophisticated 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…”
Initialization and Regularization of Factorized Neural Layers (2021, methodology): “…that a small rank r also improves generalization, e.g. for a factorized fully-connected ReLU network, applying } W } 2 F {} W } 22 ď rank p W q to Neyshabur et al. (2018, Theorem 1) and substituting W i “ U i V T i gives a w.h.p. margin-bound ˜ O p a mr {| S |q suggesting that generalization…”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “[6, 45] established tight sample complexity results for deep networks based on the product of appropriately normalized spectral norms.”
Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Several lines of recent work explain the generalization phenomenon of overparam-eterized networks by low complexity of the learned networks, from the point views of spectrally-normalized margins [3, 23, 21], compression [1, 33, 4], and PAC-Bayes [9, 23].”
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, methodology): “Neyshabur et al. (2017) speculate that Lipschitz continuity alone is insuﬃcient to guarantee generalisation.”
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].”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, background): “Researchers have proposed norm-based generalization bounds (Bartlett & Mendelson, 2002; Bartlett et al., 2017a; Neyshabur et al., 2015, 2017, 2019; Konstantinos et al., 2017; Golowich et al., 2017; Li et al., 2018a) and compression-based bounds (Arora et al., 2018).”
Stronger generalization bounds for deep nets via a compression approach (2018, background): “A simple induction (see Neyshabur et al. [2017a] if needed) can now show the total error incurred in all layers is bounded by γ .”
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).”
Fantastic Generalization Measures and Where to Find Them (2019, methodology): “…measures that we consider in this work belong to a few different families: PAC-Bayes (McAllester, 1999; Dziugaite and Roy, 2017; Neyshabur et al., 2017); VC-dimension (Vapnik and Chervonenkis, 1971); and norm-based bounds (Neyshabur et al., 2015b; Bartlett et al., 2017; Neyshabur et al., 2018a).”
An analytic theory of generalization dynamics and transfer learning in deep linear networks (2018, background): “…theories that upper bound generalization error (Bartlett & Mendelson, 2002; Neyshabur et al., 2015; Dziugaite & Roy, 2017; Golowich et al., 2017; Neyshabur et al., 2017; Bartlett et al., 2017; Arora et al., 2018, e.g) in terms of various measures of network complexity yield very loose bounds.”
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, methodology): “Neyshabur et al. [20], Keskar et al. [11], Neyshabur et al. [22], Bartlett et al. [4], Neyshabur et al. [23], Golowich et al. [7] and Arora et al. [1] suggested different norm, margin and sharpness based measures, to measure the capacity of neural networks, in an attempt to explain the…”
Bayesian Deep Learning and a Probabilistic Perspective of Generalization (2020, background): “In general, PAC-Bayes provides a compelling framework for deriving explicit non-asymptotic generalization bounds [31, 23, 7, 36, 37, 30, 17].”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, methodology): “However, all of these notions fail to explain the generalization performance of over-parameterized networks (Neyshabur et al., 2017a).”