Inapproximability of VC Dimension and Littlestone's Dimension.
Pasin ManurangsiAviad RubinsteinPublished in: COLT (2017)
Keyphrases
- vc dimension
- concept classes
- vapnik chervonenkis
- vapnik chervonenkis dimension
- sample complexity
- concept class
- upper bound
- sample size
- lower bound
- covering numbers
- decision lists
- mistake bound
- inductive inference
- generalization bounds
- learning theory
- pac learning
- active learning
- efficient learning
- worst case
- generalization error
- theoretical analysis
- learning problems
- learning machines
- compression scheme
- uniform convergence
- euclidean space
- membership queries
- target function
- supervised learning
- learning models
- special case