The Sample Complexity of Pattern Classification with Neural Networks: The Size of the Weights is More Important than the Size of the Network

By Peter L. Bartlett. 1998

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistical Learning Theory

Citations in the corpus

Reconciling modern machine-learning practice and the classical bias–variance trade-off (2018, background): “Related ideas have been considered in the context of margins theory (7, 9, 10), where a larger function class H may permit the discovery of a classifier with a larger margin.”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “Statistical learning theory: Statistical properties of neural networks have been studied since 1990’s [3, 8, 7].”
AdaNet: Adaptive Structural Learning of Artificial Neural Networks (2016, background): “Common activation functions include the Rectiﬁed Linear Unit (ReLU) ϕ k ( x ) = max { 0 , x } and the sigmoid function ϕ k ( x ) = 1 1+ e − x (see e.g. [Goodfellow et al., 2016]), although our work will allow for any 1-Lipschitz activation function.”
Sorting out Lipschitz function approximation (2018, methodology): “The Lipschitz constant of neural networks has been connected theoretically and empirically to generalization performance (Bartlett, 1998; Bartlett et al., 2017; Neyshabur et al., 2017; 2018; Sokolić et al., 2017).”
Regularisation of neural networks by enforcing Lipschitz continuity (2018, background): “Several papers have shown that the generalisation gap of a neural network is dependent on the magnitude of the weights (Bartlett et al., 2017; Neyshabur, 2017; Bartlett, 1998).”
Rademacher and Gaussian Complexities: Risk Bounds and Structural Results (2003, background): “…a number of results bounding error in terms of a sample average of a margin error plus a penalty term involving the complexity of the real-valued class (such as covering numbers and fat-shattering dimensions; see Bartlett, 1998, Mason et al., 2000, Schapire et al., 1998, Shawe-Taylor et al., 1998).”
A Model of Inductive Bias Learning (2000, methodology): “If each example can be classified with a “large margin” then naive parameter counting can be improved upon (Bartlett, 1998).”
Exploring Generalization in Deep Learning (2017, background): “In a similar spirit, Bartlett [2] and later Neyshabur et al. [19] suggested different norms of network parameters to measure the capacity of neural networks.”
A mean field view of the landscape of two-layer neural networks (2018, neutral): “R(ρ ∗ )≤ inf θ∈RN×D RN (θ) +C D/β, [22]”
Toward Deeper Understanding of Neural Networks: The Power of Initialization and a Dual View on Expressivity (2016, positive): “As for question (ii), both classical [10, 9, 3] and more recent [40, 22] results from statistical learning theory show that as the number of examples grows in comparison to the size of the network the empirical loss must be close to the population loss.”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, methodology): “…claim, this cannot be explained by applying generalization analysis techniques, like VC dimen-sion and Rademacher complexity, to classiﬁcation loss (although it does not rule out a margins analysis—see, for example, (Bartlett, 1998); their experiments involve the un-bounded cross-entropy loss).”
Size-Independent Sample Complexity of Neural Networks (2017, background): “Scale-sensitive bounds, which rely on the magnitude of the network parameters, can alleviate the dependence on the width (see Bartlett [1998], Anthony and Bartlett [2009]).”
Empirical margin distributions and bounding the generalization error of combined classifiers (2002, methodology): “Bartlett (1998) obtained a bound similar to the first inequality of Theorem 13 for a more special class H and with larger constants.”
Robustness and generalization (2010, methodology): “We need the following standard definition (e.g., Bartlett 1998) of the distance of a point to a classification rule.”
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].”
An introduction to domain adaptation and transfer learning (2018, background): “Equation 7) [12,13,148,51].”