Find a witness or shatter: the landscape of computable PAC learning.
Valentino Delle RoseAlexander KozachinskiyCristóbal RojasTomasz SteiferPublished in: COLT (2023)
Keyphrases
- pac learning
- uniform distribution
- computational learning theory
- learning theory
- sample complexity
- sample size
- learning problems
- target concept
- membership queries
- decision lists
- vc dimension
- statistical queries
- memory based learning
- instance space
- agnostic learning
- data sets
- concept classes
- boolean functions
- theoretical analysis
- upper bound
- learning algorithm
- concept class
- noise tolerant
- dnf formulas
- machine learning