Abstract | ||
---|---|---|
This paper deals with the problem of identifying a connection between the Vapnik-Chervonenkis (VC) Entropy, a notion of complexity introduced by Vapnik in his seminal work, and the Rademacher Complexity, a more powerful notion of complexity, which has been in the limelight of several works in the recent Machine Learning literature. In order to establish this connection, we refine some previously known relationships and derive a new result. Our proposal allows computing an admissible range for the Rademacher Complexity, given a value of the VC-Entropy, and vice versa, therefore opening new appealing research perspectives in the field of assessing the complexity of an hypothesis space. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1109/IJCNN.2013.6706943 | Neural Networks |
Keywords | Field | DocType |
computational complexity,learning (artificial intelligence),Rademacher complexity,VC-entropy,Vapnik-Chervonenkis entropy,machine learning | Quantum complexity theory,PH,Average-case complexity,Structural complexity theory,Computer science,Rademacher complexity,Complexity index,Descriptive complexity theory,Artificial intelligence,Worst-case complexity,Machine learning | Conference |
ISSN | ISBN | Citations |
2161-4393 | 978-1-4673-6128-6 | 0 |
PageRank | References | Authors |
0.34 | 12 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Davide Anguita | 1 | 1001 | 70.58 |
Alessandro Ghio | 2 | 667 | 35.71 |
Luca Oneto | 3 | 830 | 63.22 |
Sandro Ridella | 4 | 677 | 140.62 |