Lower bounds on the performance of polynomial-time algorithms for sparse linear regression.

Yuchen Zhang Martin J. Wainwright Michael I. Jordan

Published in: CoRR (2014)

Keyphrases

linear regression
lower bound
worst case
computational complexity
least squares
regression methods
linear models
learning algorithm
upper bound
theoretical guarantees
generalized linear models
sparse regression
regression problems