Almost Linear VC-Dimension Bounds for Piecewise Polynomial Networks

By Peter L. Bartlett, V. Maiorov, R. Meir. 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

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].”
On the Expressive Power of Deep Neural Networks (2016, background): “The ﬁrst major difﬁculty comes from the high dimensionality of the input.”
Exploring Generalization in Deep Learning (2017, background): “Even without making an assumption on the precision of parameters, the VC dimension of feedforward networks can be bounded in terms of the number of parameters dim(w)[1, 3, 6, 23].”
Functional Gradient Boosting based on Residual Network Perception (2018, methodology): “When the activation function is piece-wise linear, such as Relu function σ ( x ) = max { 0 , x } , reasonable bounds on these quantities are given by Bartlett et al. (1998; 2017).”
SPECTRALLY-NORMALIZED MARGIN BOUNDS FOR NEURAL NETWORKS (2018, background): “Harvey et al. (2017) provided a generalization error bound by showing that the VC dimension of d-layer networks is depth times the number parameters improving over earlier bounds by Bartlett et al. (1999).”
Understanding Generalization through Visualizations (2019, unknown): “…generalization in over-parameterized neural nets, as the complexity of networks is often large (exponential in depth (Sun et al., 2016; Neyshabur et al., 2015; Xie et al., 2015) or linear in the number of parameters (Shalev-Shwartz and Ben-David, 2014; Bartlett et al., 1998; Harvey et al., 2017)).”
Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks (2019, background): “For example, generalization error is related to various complexity measures [2, 10, 24], local properties (sharpness/flatness) of loss functions at minima [18,33], stability of optimization algorithms [16], and implicit bias of the training process [1,29,34].”
Implicit Regularization in Deep Learning (2017, background): “[22], give the following tight (up to logarithmic factors) bound on the VC dimension and hence capacity of feedforward networks with ReLU activations: VC-dim = Õ(d ∗ nparam) (3.”
Deep Network Approximation for Smooth Functions (2020, background): “, in terms of combinatorics [16], 73 topology [4], Vapnik-Chervonenkis (VC) dimension [3, 18, 9], fat-shattering dimension 74 [12, 1], information theory [17], classical approximation theory [7, 11, 2, 22, 21, 5, 23, 6], 75 etc.”
Error bounds for approximations with deep ReLU networks (2016, background): “Telgarsky 2015, 2016 provides specific examples of classification problems where deep networks are provably more efficient than shallow ones.”
Optimal approximation of continuous functions by very deep ReLU networks (2018, methodology): “More accurate upper and lower bounds involving the network depth L have been given in Bartlett et al. (1998); Sakurai (1999). The recent paper Bartlett et al.”
On the Depth of Deep Neural Networks: A Theoretical View (2015, methodology): “For example, in (Bartlett, Maiorov, and Meir 1998; Karpinski and Macintyre 1995; Goldberg and Jerrum 1995), generalization bounds for multi-layer neural networks were derived based on Vapnik-Chervonenkis (VC) dimension.”
Kaleidoscope: An Efficient, Learnable Representation For All Structured Linear Maps (2020, background): “We also show that ReLU networks with kaleidoscope weight matrices have near-linear VC dimension in the number of parameters, matching the bound for networks with unconstrained weight matrices (Bartlett et al., 1999; Harvey et al., 2017) and LDR (Thomas et al., 2018).”
Learning capability and storage capacity of two-hidden-layer feedforward networks (2003, background): “It is shown [20], [25] that there is a feedforward network with layers and a total of parameters, where every hidden neuron has sigmoid activation function and the output neuron has threshold function, .”
Large Margin Deep Neural Networks: Theory and Algorithms (2015, methodology): “For example, in [3, 9, 15], error bounds for neural networks were derived based on Vapnik-Chervonenkis (VC) dimension.”
A Theoretical Analysis of Deep Q-Learning (2019, background): “t al. (2017a); Golowich et al. (2017); Liang et al. (2017) propose various norms computed from the networks parameters and establish capacity bounds based upon these norms. In addition, Maass (1994); Bartlett et al. (1999); Schmidt-Hieber (2017); Bartlett et al. (2017b) study the VapnikChervonenkis ”
Nearly-tight VC-dimension bounds for piecewise linear neural networks (2017, methodology): “One interesting aspect of the proof is that it does not use Warren’s lemma (Warren, 1968), which is a mainstay of VC-dimension upper bounds, see Goldberg and Jerrum (1995); Bartlett et al. (1998); Anthony and Bartlett (1999).”
SSN: Learning Sparse Switchable Normalization via SparsestMax (2019, unknown): “1989; Hornik 1991) and VC dimension (Bartlett et al. 1999).”