Size-Independent Sample Complexity of Neural Networks

By Noah Golowich, Alexander Rakhlin, Ohad Shamir. 2017

640 citations recorded by the source corpus.

We study the sample complexity of learning neural networks by providing new bounds on their Rademacher complexity, assuming norm constraints on the parameter matrix of each layer. Compared to previous work, these complexity bounds have improved dependence on the network depth and, under some additional assumptions, are fully independent of the network size (both depth and width). These results are derived using some novel techniques, which may be of independent interest.

Subfields: Artificial Intelligence, Scaling & Learning Theory, Statistical 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 Scaling & Learning Theory

In Statistical Learning Theory

Citations in the corpus

Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “With the success of deep networks, there is a renewed interest in understanding capacity of the neural networks under different norm constraints or network architectures [22, 5, 44, 26].”
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.”
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.”
Stronger generalization bounds for deep nets via a compression approach (2018, background): “A recent work, Golowich et al. [2017] showed that many such depth dependencies can be improved.”
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, background): “Neyshabur et al. (2015b) proved a bound based on product of Frobenius norms of the layer weights times a 2 d factor and Golowich et al. (2017) was able to improve the factor to √ d .”
An analytic theory of generalization dynamics and transfer learning in deep linear networks (2018, background): “…al., 2016): many existing 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…”
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, background): “√ Theorem 7 in Golowich et al. [7] also gives a Ω( s 1 s 2 c ) lower bound, c is the number of outputs of the network, for the composition of 1-Lipschitz loss function and neural networks with bounded spectral norm, or ∞ -Schatten norm.”
Benign overfitting in linear regression (2019, background): “…have suggested viewing neural networks as ﬁnite-dimensional approximations to inﬁnite dimensional objects [28, 16, 2], and there are generalization bounds— although not for the overﬁtting regime—that are applicable to inﬁnite width deep networks with parameter norm constraints [3, 4, 32, 5, 22].”
Learning Imbalanced Datasets with Label-Distribution-Aware Margin Loss (2019, background): “There is a large body of recent work on measuring the complexity of neural networks (see [4, 13, 57] and references therein), and our discussion below is orthogonal to the precise choices.”
Generalization bounds for deep convolutional neural networks (2019, background): “…generalization of deep learning models (see Neyshabur et al., 2015; Zhang et al., 2016; Dziugaite and Roy, 2017; Bartlett et al., 2017; Neyshabur et al., 2017; 2018; Arora et al., 2018; Golowich et al., 2018; Neyshabur et al., 2019; Wei and Ma, 2019a; Cao and Gu, 2019; Daniely and Granot, 2019).”
Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks (2019, background): “This is the subject of a few interesting recent papers [5,7–9,13,24,34,50].”
Rademacher Complexity for Adversarially Robust Generalization (2018, result): “In particular, it has been shown that when properly normalized by the margin, using Rademacher complexity or PAC-Bayesian analysis, one can obtain generalization bounds that tend to match the experimental results (Bartlett et al., 2017; Neyshabur et al., 2017; Arora et al., 2018; Golowich et al., 20”
The Pitfalls of Simplicity Bias in Neural Networks (2020, background): “[21] Noah Golowich, Alexander Rakhlin, and Ohad Shamir.”
Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience (2019, background): “l dependence on depth. In particular, these bounds scale either with the product of the spectral norms of the weight matrices (Neyshabur et al., 2018; Bartlett et al., 2017) or their Frobenius norms (Golowich et al., 2018). In practice, the weight matrices have a spectral norm that is as large as 2 ”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, background): “…NTKs. Complexity Bounds Recently, researchers have studied norm-based generalization based (Bartlett et al., 2017; Neyshabur et al., 2015; Golowich et al., 2017), tighter compression-based bounds (Arora et al., 2018), and PAC-Bayes bounds (Dziugaite & Roy, 2017; Neyshabur et al., 2017)…”
Causally motivated shortcut removal using auxiliary labels (2021, methodology): “Extensions of our theoretical analysis to more complex neural networks are possible (e.g., through approaches studied in Golowich et al. [2018]).”