On the complexity of approximating the VC dimension.
Elchanan MosselChristopher UmansPublished in: J. Comput. Syst. Sci. (2002)
Keyphrases
- vc dimension
- vapnik chervonenkis dimension
- vapnik chervonenkis
- worst case
- upper bound
- sample complexity
- lower bound
- statistical learning theory
- concept classes
- sample size
- function classes
- query complexity
- covering numbers
- pac learnability
- generalization bounds
- distribution free
- uniform convergence
- empirical risk minimization
- inductive inference
- computational complexity
- learning machines
- special case
- mind change complexity