Statistical Query Lower Bounds for List-Decodable Linear Regression.
Ilias DiakonikolasDaniel M. KaneAnkit PensiaThanasis PittasAlistair StewartPublished in: CoRR (2021)
Keyphrases
- linear regression
- lower bound
- statistical queries
- concept class
- upper bound
- least squares
- regression problems
- concept classes
- objective function
- uniform distribution
- np hard
- learning theory
- linear models
- worst case
- vc dimension
- pac learning
- regression trees
- boolean functions
- sample complexity
- theoretical analysis
- feature space
- machine learning