# A path-norm toolkit for modern networks: consequences, promises and challenges

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 53 references that are in the map.
- First posted on arXiv 2 Oct 2023.

## Builds on (most cited first, 30 of 30)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Spectrally-normalized margin bounds for neural networks](https://mlsanity.com/paper/1706.08498/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Fantastic Generalization Measures and Where to Find Them](https://mlsanity.com/paper/1912.02178/) (2019)
- [Breaking the Curse of Dimensionality with Convex Neural Networks](https://mlsanity.com/paper/1412.8690/) (2014)
- [A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks](https://mlsanity.com/paper/1707.09564/) (2017)
- [Norm-Based Capacity Control in Neural Networks](https://mlsanity.com/paper/1503.00036/) (2015)
- [Size-Independent Sample Complexity of Neural Networks](https://mlsanity.com/paper/1712.06541/) (2017)
- [Understanding Deep Neural Networks with Rectified Linear Units](https://mlsanity.com/paper/1611.01491/) (2016)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Uniform convergence may be unable to explain generalization in deep learning](https://mlsanity.com/paper/1902.04742/) (2019)
- [Sorting out Lipschitz function approximation](https://mlsanity.com/paper/1811.05381/) (2018)
- [Pruning Neural Networks at Initialization: Why are We Missing the Mark?](https://mlsanity.com/paper/2009.08576/) (2020)
- [Generalization in Deep Learning](https://mlsanity.com/paper/1710.05468/) (2017)
- [A vector-contraction inequality for Rademacher complexities](https://mlsanity.com/paper/1605.00251/) (2016)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [The Early Phase of Neural Network Training](https://mlsanity.com/paper/2002.10365/) (2020)
- [Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1709.01953/) (2017)
- [In Search of Robust Measures of Generalization](https://mlsanity.com/paper/2010.11924/) (2020)
- [Lipschitz Certificates for Layered Network Structures Driven by Averaged Activation Operators](https://mlsanity.com/paper/1903.01014/) (2019)
- [Abide by the Law and Follow the Flow: Conservation Laws for Gradient Flows](https://mlsanity.com/paper/2307.00144/) (2023)
- [Generalization bounds for deep learning](https://mlsanity.com/paper/2012.04115/) (2020)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [An Embedding of ReLU Networks and an Analysis of their Identifiability](https://mlsanity.com/paper/2107.09370/) (2021)
- [Complexity, Statistical Risk, and Metric Entropy of Deep Nets Using Total Path Variation](https://mlsanity.com/paper/1902.00800/) (2019)
- [Local Identifiability of Deep ReLU Neural Networks: the Theory](https://mlsanity.com/paper/2206.07424/) (2022)
- [Capacity Control of ReLU Neural Networks by Basis-path Norm](https://mlsanity.com/paper/1809.07122/) (2018)
- [Approximation speed of quantized vs. unquantized ReLU neural networks and beyond](https://mlsanity.com/paper/2205.11874/) (2022)
- [Norm-based Generalization Bounds for Compositionally Sparse Neural Networks](https://mlsanity.com/paper/2301.12033/) (2023)

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

- [Implicit Regularization of Sharpness-Aware Minimization for Scale-Invariant Problems](https://mlsanity.com/paper/2410.14802/) (2024)
- [How DNNs break the Curse of Dimensionality: Compositionality and Symmetry Learning](https://mlsanity.com/paper/2407.05664/) (2024)
- [Convexity in ReLU Neural Networks: beyond ICNNs?](https://mlsanity.com/paper/2501.03017/) (2025)
- [Path-conditioned training: a principled way to rescale ReLU neural networks](https://mlsanity.com/paper/2602.19799/) (2026)
- [A Rescaling-Invariant Lipschitz Bound Based on Path-Metrics for Modern ReLU Network Parameterizations](https://mlsanity.com/paper/2405.15006/) (2024)
- [Intrinsic training dynamics of deep neural networks](https://mlsanity.com/paper/2508.07370/) (2025)
- [Non-Vacuous Generalization Bounds: Can Rescaling Invariances Help?](https://mlsanity.com/paper/2509.26149/) (2025)
- [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)
- [Position: Many generalization measures for deep learning are fragile](https://mlsanity.com/paper/2510.18934/) (2025)
- [Rank and computation of the pathlifting Jacobian of a DAG ReLU network](https://mlsanity.com/paper/2609.18682/) (2026)

## Abstract (arXiv)

This work introduces the first toolkit around path-norms that fully encompasses general DAG ReLU networks with biases, skip connections and any operation based on the extraction of order statistics: max pooling, GroupSort etc. This toolkit notably allows us to establish generalization bounds for modern neural networks that are not only the most widely applicable path-norm based ones, but also recover or beat the sharpest known bounds of this type. These extended path-norms further enjoy the usual benefits of path-norms: ease of computation, invariance under the symmetries of the network, and improved sharpness on layered fully-connected networks compared to the product of operator norms, another complexity measure most commonly used. The versatility of the toolkit and its ease of implementation allow us to challenge the concrete promises of path-norm-based generalization bounds, by numerically evaluating the sharpest known bounds for ResNets on ImageNet.