Depth Enables Local Entropy: Quadratic Depth Dependence in Deep Variation-Norm ReLU Regression
Not on the map. Why?
Abstract (arXiv)
We study Gaussian regression over the explicit vector-valued Parhi--Nowak deep-RBV^2 architecture with depth L, width w, layer-sum variation budget A, and output bound B. For this O(L w^2)-parameterized architecture, the known lower and upper bounds differ by one factor of depth. We construct a local packing showing that the quadratic depth dependence is intrinsic under an explicit sample-size-dependent radius condition. The packing has log-cardinality Omega(L^2 w^2 log w); its codewords lie in an O(lambda) L^2 ball and are pairwise Omega(lambda)-separated. The main ingredients are a bias-corrected bounded-coefficient approximation theorem and balanced amplification: multiplying a depth-D ReLU network by q can be implemented using one constant channel so that every coefficient grows by only q^(1/D). Translation to vector-valued RBV^2 blocks then has layer-sum cost O(D w^2 q^(1/D)). Gaussian Fano yields a radius-explicit lower bound governed by the output, testing, and representation scales. Under A=B=R, sigma proportional to R, and the stated radius condition, this gives minimax risk at least of order L^2 w^2 log(w) R^2/n. A pseudodimension-based finite-net upper bound gives O-tilde(L^2 w^2 R^2/n) for unbounded Gaussian responses. Thus the minimax risk has quadratic polynomial dependence on depth, up to logarithmic factors, and exhibits a transition to representation-limited behavior at smaller radius.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 18 of its 28 references that are in the map. First posted on arXiv 18 Aug 2026.
Builds on
18 of 28 references.
References · 18
- 2016Error bounds for approximations with deep ReLU networkscited by 574
- 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
- 2014Breaking the Curse of Dimensionality with Convex Neural Networkscited by 331
- 2017Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networkscited by 311
- 2015Norm-Based Capacity Control in Neural Networkscited by 299
- 2017Size-Independent Sample Complexity of Neural Networkscited by 290
- 2016Benefits of depth in neural networkscited by 250
- 2018Optimal approximation of continuous functions by very deep ReLU networkscited by 166
- 2018Adaptivity of deep ReLU network for learning in Besov and mixed smooth Besov spaces: optimal rate and curse of dimensionalitycited by 162
- 2019A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Casecited by 114
- 2019How do infinite width bounded norm networks look in function space?cited by 106
- 2021Sharp Bounds on the Approximation Rates, Metric Entropy, and n-widths of Shallow Neural Networkscited by 86
6 more
- 2021What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theorycited by 60
- 2021Near-Minimax Optimal Estimation With Shallow ReLU Neural Networkscited by 41
- 2023Variation Spaces for Multi-Output Neural Networks: Insights on Multi-Task Learning and Network Compressioncited by 18
- 2024Covering Numbers for Deep ReLU Networks with Applications to Function Approximation and Nonparametric Regressioncited by 11
- 2024Three Quantization Regimes for ReLU Networkscited by 5
- 2026A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernelcited by 1
Built on by
Not cited yet.