A Deep Connection Between the Vapnik-Chervonenkis Entropy and the Rademacher Complexity

作者：Anguita Davide^*; Ghio Alessandro; Oneto Luca; Ridella Sandro

来源：IEEE Transactions on Neural Networks and Learning Systems, 2014, 25(12): 2202-2211.

DOI：10.1109/TNNLS.2014.2307359

• Complexity measures
• Rademacher complexity
• statistical learning theory
• Vapnik-Chervonenkis (VC) entropy

In this paper, we derive a deep connection between the Vapnik-Chervonenkis (VC) entropy and the Rademacher complexity. For this purpose, we first refine some previously known relationships between the two notions of complexity and then derive new results, which allow computing an admissible range for the Rademacher complexity, given a value of the VC-entropy, and vice versa. The approach adopted in this paper is new and relies on the careful analysis of the combinatorial nature of the problem. The obtained results improve the state of the art on this research topic.

• 出版日期2014-12