Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes.
Lunjia HuRuihan WuTianhong LiLiwei WangPublished in: COLT (2017)
Keyphrases
- upper bound
- teaching dimension
- vc dimension
- concept classes
- concept class
- vapnik chervonenkis dimension
- lower bound
- sample complexity
- target function
- decision lists
- worst case
- generalization error
- lower and upper bounds
- dnf formulas
- upper and lower bounds
- sample size
- linear functions
- objective function
- pac learning
- learning machines
- pairwise
- monotone dnf
- monotone dnf formulas
- agnostic learning
- learning theory
- special case
- computational complexity