Lower Bounds for Agnostic Learning via Approximate Rank.
Adam R. KlivansAlexander A. SherstovPublished in: Comput. Complex. (2010)
Keyphrases
- agnostic learning
- lower bound
- concept class
- upper bound
- uniform distribution
- learning theory
- concept classes
- noise tolerant
- membership queries
- pac learning
- complexity analysis
- vc dimension
- np hard
- lower and upper bounds
- objective function
- concept learning
- dnf formulas
- optimal solution
- sample complexity
- decision lists
- boosting algorithms
- kernel methods
- binary classification problems
- worst case
- target function
- statistical queries