Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals.
Daniel J. HsuClayton Hendrick SanfordRocco A. ServedioEmmanouil-Vasileios Vlatakis-GkaragkounisPublished in: COLT (2022)
Keyphrases
- statistical queries
- lower bound
- noise tolerant
- agnostic learning
- learning process
- uniform distribution
- learning algorithm
- pac model
- supervised learning
- upper bound
- learning tasks
- learning problems
- concept classes
- concept class
- decision lists
- dnf formulas
- positive and unlabeled examples
- pattern languages
- concept learning
- sample size
- active learning
- objective function