Statistical Query Lower Bounds for List-Decodable Linear Regression.
Ilias DiakonikolasDaniel KaneAnkit PensiaThanasis PittasAlistair StewartPublished in: NeurIPS (2021)
Keyphrases
- linear regression
- lower bound
- statistical queries
- upper bound
- concept class
- least squares
- regression problems
- np hard
- worst case
- uniform distribution
- concept classes
- learning theory
- objective function
- vc dimension
- optimal solution
- linear models
- concept learning
- boolean functions
- pac learning
- membership queries
- regression trees
- sample complexity
- noisy data
- learning tasks
- semi supervised
- target function
- data sets