Lower bounds on the performance of polynomial-time algorithms for sparse linear regression.
Yuchen ZhangMartin J. WainwrightMichael I. JordanPublished in: COLT (2014)
Keyphrases
- linear regression
- lower bound
- least squares
- worst case
- learning algorithm
- linear models
- regression methods
- computational complexity
- linear regression model
- randomized algorithm
- machine learning
- regression problems
- lower and upper bounds
- upper bound
- linear predictors
- ridge regression
- text classification
- nonlinear regression
- locally weighted
- loss bounds