论文标题
近似描述长度，覆盖数字和VC维度
Approximate Description Length, Covering Numbers, and VC Dimension
论文作者
论文摘要
最近，Daniely和Granot [Arxiv：1910.05697]引入了一个新的复杂性概念，称为近似描述长度（ADL）。他们用它来得出神经网络的新概括范围，尽管大量工作，但仍无法实现更古典的技术，例如离散化，覆盖数量和Rademacher的复杂性。在本文中，我们探讨了ADL与功能复杂性的经典概念（例如覆盖数字和VC维度）的关系。我们发现，对于范围是真实的函数，ADL基本上等同于这些经典的复杂性度量。但是，这种等效性破坏了高维范围的功能。
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.
