# Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation

arXiv: https://arxiv.org/abs/1902.00800 · HTML: https://mlsanity.com/paper/1902.00800/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2019.

## Built on by (most cited first, 16 of 16)

- [What Kinds of Functions do Deep Neural Networks Learn? Insights from Variational Spline Theory](https://mlsanity.com/paper/2105.03361/) (2021)
- [Approximation bounds for norm constrained neural networks with applications to regression and GANs](https://mlsanity.com/paper/2201.09418/) (2022)
- [A path-norm toolkit for modern networks: consequences, promises and challenges](https://mlsanity.com/paper/2310.01225/) (2023)
- [Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks](https://mlsanity.com/paper/2404.18769/) (2024)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Deep Learning as a Convex Paradigm of Computation: Minimizing Circuit Size with ResNets](https://mlsanity.com/paper/2511.20888/) (2025)
- [The Rate of Convergence of Variation-Constrained Deep Neural Networks](https://mlsanity.com/paper/2106.12068/) (2021)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [Provable Identifiability of Two-Layer ReLU Neural Networks via LASSO Regularization](https://mlsanity.com/paper/2305.04267/) (2023)
- [A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations](https://mlsanity.com/paper/2405.15006/) (2024)
- [Neural Network Layer Algebra: A Framework to Measure Capacity and Compression in Deep Learning](https://mlsanity.com/paper/2107.01081/) (2021)
- [A practical generalization metric for deep networks benchmarking](https://mlsanity.com/paper/2409.01498/) (2024)
- [Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?](https://mlsanity.com/paper/2509.26149/) (2025)
- [Deep Neural Variation Spaces: A Unifying Perspective on Depth and Complexity](https://mlsanity.com/paper/2607.05546/) (2026)
- [Variation Brownian Kernel Ladders](https://mlsanity.com/paper/2608.13882/) (2026)
- [Path Regularization: A Near-Complete and Optimal Nonasymptotic Generalization Theory for Multilayer Neural Networks and Double Descent Phenomenon](https://mlsanity.com/paper/2503.02129/) (2025)

## Abstract (arXiv)

For any ReLU network there is a representation in which the sum of the absolute values of the weights into each node is exactly 1, and the input layer variables are multiplied by a value V coinciding with the total variation of the path weights. Implications are given for Gaussian complexity, Rademacher complexity, statistical risk, and metric entropy, all of which are shown to be proportional to V. There is no dependence on the number of nodes per layer, except for the number of inputs d. For estimation with sub-Gaussian noise, the mean square generalization error bounds that can be obtained are of order V √L + log d/√n, where L is the number of layers and n is the sample size.