Sample Size Lower Bounds in PAC Learning by Algorithmic Complexity Theory.
Bruno ApolloniClaudio GentilePublished in: Theor. Comput. Sci. (1998)
Keyphrases
- pac learning
- sample size
- complexity theory
- lower bound
- upper bound
- vc dimension
- concept class
- worst case
- theoretical basis
- concept classes
- sample complexity
- computational geometry
- model selection
- target concept
- generalization error
- random sampling
- optimal solution
- progressive sampling
- objective function
- statistical queries
- np hard
- data sets