Approximate Description Length, Covering Numbers, and VC Dimension
Not on the map. Why?
Abstract (arXiv)
Recently, Daniely and Granot [arXiv:1910.05697] introduced a new notion of complexity called Approximate Description Length (ADL). They used it to derive novel generalization bounds for neural networks, that despite substantial work, were out of reach for more classical techniques such as discretization, Covering Numbers and Rademacher Complexity. In this paper we explore how ADL relates to classical notions of function complexity such as Covering Numbers and VC Dimension. We find that for functions whose range is the reals, ADL is essentially equivalent to these classical complexity measures. However, this equivalence breaks for functions with high dimensional range.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 5 of its 15 references that are in the map. First posted on arXiv 26 Sep 2022.
Builds on
5 of 15 references.
References · 5
- 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
- 2018Stronger generalization bounds for deep nets via a compression approachcited by 306
- 2015Norm-Based Capacity Control in Neural Networkscited by 299
- 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
- 2019Generalization Bounds for Neural Networks via Approximate Description Lengthcited by 15
Built on by
Not cited yet.