PAC Learning of Halfspaces with Malicious Noise in Nearly Linear Time.
Jie ShenPublished in: AISTATS (2023)
Keyphrases
- pac learning
- agnostic learning
- noise tolerant
- statistical queries
- concept classes
- sample complexity
- attribute noise
- uniform distribution
- pac model
- target concept
- membership queries
- decision lists
- concept class
- computational learning theory
- vc dimension
- sample size
- dnf formulas
- term dnf
- learning theory
- low degree
- learning problems
- exact learning
- upper bound
- worst case
- mistake bound
- learning algorithm
- active learning
- lower bound
- theoretical analysis
- target function
- noisy data
- special case
- upper and lower bounds
- boolean functions
- supervised learning
- label noise
- efficient learning
- equivalence queries
- generalization error
- machine learning