Nearly-tight VC-dimension bounds for piecewise linear neural networks

By Nick Harvey, Christopher Liaw, Abbas Mehrabian. 2017

190 citations recorded by the source corpus.

How researchers see this paper

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

In Scaling & Learning Theory

Citations in the corpus

Deep Learning Scaling is Predictable, Empirically (2017, background): “…on the VC dimension of particular deep neural network models, including showing that recurrent neural network models have the same effective capacity if the optimization scheme is well-tuned and training runs long enough (Harvey et al. (2017); Dziugaite and Roy (2017); Collins et al. (2017)).”
mixup: Beyond Empirical Risk Minimization (2017, background): “Here, the size of a learning machine is measured in terms of its number of parameters or, relatedly, its VC-complexity (Harvey et al., 2017).”
Deep Neural Networks for Estimation and Inference: Application to Causal Effects and Other Semiparametric Estimands (2018, positive): “One contribution of our proof is to use a scale sensitive localization theory (Koltchinskii and Panchenko (2000), Bartlett, Bousquet, and Mendelson (2005), Koltchinskii (2006, 2011), Liang, Rakhlin, and Sridharan (2015)) with such scale insensitive measures for deep neural networks for general smoot”
Exploring Generalization in Deep Learning (2017, background): “In particular, Bartlett [3] and Harvey et al. [10], following Bartlett et al. [5], give the following tight (up to logarithmic factors) bound on the VC dimension and hence capacity of feedforward networks with ReLU activations: VC-dim = ˜ O ( d ∗ dim ( w )) (1) In the over-parametrized settings,…”
A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks (2017, background): “…of fully connected feedforward neural networks with ReLU activation with d layers and h units per layer is ˜Θ( d 2 h 2 ) (Harvey et al. [5]), yielding a generalization guarantee of the form: where here and throughout this section we ignore logarithmic factors that depend on - the…”
Batch Policy Learning under Constraints (2019, background): “For example, Bartlett et al. (2017) bounded the pseudo-dimension of piece-wise linear deep neural networks (e.g., with ReLU activations) as O(WL logW ), where W is the number of weights, and L is the number of layers.”
Towards Understanding the Role of Over-Parametrization in Generalization of Neural Networks (2018, background): “…set S = { x i } mi =1 and γ > 0 , Rademacher complexity of the composition of loss function γ over the class F W deﬁned in equations (4) and (5) is bounded as follows: # Reference Measure (1) Harvey et al. [9] ˜Θ( dh ) (2) Bartlett and Mendelson The proof is given in the supplementary Section B.”
Learning Fast Algorithms for Linear Transforms Using Butterfly Factorizations (2019, background): “In fact, neural networks comprising layers of BP and BPBP matrices still have VC dimension that is almost linear in the number of parameters (Appendix B), similar to networks with fully-connected layers (Bartlett et al., 1999; Harvey et al., 2017) and LDR (Thomas et al.”
Uniform convergence may be unable to explain generalization in deep learning (2019, background): “Such a requirement is satisfied even by standard parameter-count-based VC-dimension bounds, like O(dh/√m) for depth d, width h ReLU networks [13].”
Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach (2018, background): “Attempts have been made at adapting classical measures such as VC-dimension (Harvey et al., 2017) or margin/norm bounds (Neyshabur et al., 2018; Bartlett et al., 2017), but such approaches have yielded bounds that are vacuous by orders of magnitudes.”
Why ResNet Works? Residuals Generalize (2019, background): “[22] prove upper and lower bounds on the VC-dimension of the hypothesis space of deep neural networks with the activation function of ReLU.”
A systematic review on overfitting control in shallow and deep neural networks (2021, background): “The VC-dimension of a feed-forward neural network with ReLU activation function satisfies (Harvey et al. 2017) where W is the number of weights, and L is the number of layers.”
The Expressive Power of Neural Networks: A View from the Width (2017, methodology): “Neural networks 1989 [7] Nick Harvey, Chris liaw, Abbas Mehrabian.”
SPECTRALLY-NORMALIZED MARGIN BOUNDS FOR NEURAL NETWORKS (2018, background): “The VC-dimension of fully connected feedforward neural networks with ReLU activation with d layers and h units per layer is Θ̃(d2h2) (Harvey et al. (2017)), yielding a generalization guarantee of the form: L0(fw) ≤ L̂0(fw) + Õ (√ d2h2 m ) (5) where here and throughout this section we ignore…”
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).”
Deep learning generalizes because the parameter-function map is biased towards simple functions (2018, unknown): “(Kawaguchi et al. (2017); Arora et al.”
Information-Theoretic Local Minima Characterization and Regularization (2019, methodology): “Similar to Langford & Caruana (2002), Harvey et al. (2017) and Neyshabur et al. (2017), we apply the PAC-Bayes Theorem (McAllester, 2003) to derive a generalization bound for our metric.”