Depth Separation in Norm-Bounded Infinite-Width Neural Networks
Not on the map. Why?
Abstract (arXiv)
We study depth separation in infinite-width neural networks, where complexity is controlled by the overall squared ℓ2-norm of the weights (sum of squares of all weights in the network). Whereas previous depth separation results focused on separation in terms of width, such results do not give insight into whether depth determines if it is possible to learn a network that generalizes well even when the network width is unbounded. Here, we study separation in terms of the sample complexity required for learnability. Specifically, we show that there are functions that are learnable with sample complexity polynomial in the input dimension by norm-controlled depth-3 ReLU networks, yet are not learnable with sub-exponential sample complexity by norm-controlled depth-2 ReLU networks (with any value for the norm). We also show that a similar statement in the reverse direction is not possible: any function learnable with polynomial sample complexity by a norm-controlled depth-2 ReLU network with infinite width is also learnable with polynomial sample complexity by a norm-controlled depth-3 ReLU network.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 37 of its 49 references that are in the map. First posted on arXiv 13 Feb 2024.
Builds on
37 of 49 references.
References · 37
- 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
- 2016Understanding deep learning requires rethinking generalizationcited by 1,657
- 2016Error bounds for approximations with deep ReLU networkscited by 567
- 2018On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transportcited by 422
- 2014In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learningcited by 339
- 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 329
- 2017The Expressive Power of Neural Networks: A View from the Widthcited by 318
- 2015Norm-Based Capacity Control in Neural Networkscited by 299
- 2017Size-Independent Sample Complexity of Neural Networkscited by 289
- 2020Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Losscited by 267
- 2016Understanding Deep Neural Networks with Rectified Linear Unitscited by 253
- 2016Benefits of depth in neural networkscited by 248
25 more
- 2019Mean-field theory of two-layers neural networks: dimension-free bounds and kernel limitcited by 187
- 2015The Power of Depth for Feedforward Neural Networkscited by 181
- 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 165
- 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 113
- 2019How do infinite width bounded norm networks look in function space?cited by 105
- 2018On the Power of Over-parametrization in Neural Networks with Quadratic Activationcited by 102
- 2020Neural Networks are Convex Regularizers: Exact Polynomial-time Convex Optimization Formulations for Two-layer Networkscited by 96
- 2022On the Implicit Bias in Deep-Learning Algorithmscited by 84
- 2016Why Deep Neural Networks for Function Approximation?cited by 82
- 2018Small ReLU networks are powerful memorizers: a tight analysis of memorization capacitycited by 76
- 2016Depth-Width Tradeoffs in Approximating Natural Functions with Neural Networkscited by 58
- 2017Depth Separation for Neural Networkscited by 46
- 2017Geometry of Optimization and Implicit Regularization in Deep Learningcited by 39
- 2022Implicit Bias of Large Depth Networks: a Notion of Rank for Nonlinear Functionscited by 38
- 2017The power of deeper networks for expressing natural functionscited by 35
- 2019Depth Separations in Neural Networks: What is Actually Being Separated?cited by 27
- 2021Depth separation beyond radial functionscited by 18
- 2022Ridges, Neural Networks, and the Radon Transformcited by 18
- 2020Neural Networks with Small Weights and Depth-Separation Barrierscited by 17
- 2023Penalising the biases in norm regularisation enforces sparsitycited by 17
- 2023Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compressioncited by 17
- 2023Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoffcited by 17
- 2019Generalization Bounds for Neural Networks via Approximate Description Lengthcited by 15
- 2020Better Depth-Width Trade-offs for Neural Networks through the lens of Dynamical Systemscited by 9
- 2014N-sphere chord length distributioncited by 1
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.