Find a witness or shatter: the landscape of computable PAC learning.
Valentino Delle RoseAlexander KozachinskiyCristóbal RojasTomasz SteiferPublished in: CoRR (2023)
Keyphrases
- pac learning
- uniform distribution
- computational learning theory
- learning theory
- sample size
- learning problems
- sample complexity
- target concept
- concept classes
- membership queries
- vc dimension
- agnostic learning
- learning algorithm
- special case
- statistical queries
- boolean functions
- data sets
- labeled data
- small number
- semi supervised
- multi class
- concept class
- upper bound
- support vector machine
- instance space
- decision lists
- machine learning