Statistical Query Lower Bounds for List-Decodable Linear Regression.

Ilias Diakonikolas Daniel M. Kane Ankit Pensia Thanasis Pittas Alistair Stewart

Published 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