Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression

Yuchen Zhang, Martin J. Wainwright, Michael I. Jordan
Proceedings of The 27th Conference on Learning Theory, PMLR 35:921-948, 2014.

Abstract

Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-zhang14, title = {Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression}, author = {Zhang, Yuchen and Wainwright, Martin J. and Jordan, Michael I.}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {921--948}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/zhang14.pdf}, url = {https://proceedings.mlr.press/v35/zhang14.html}, abstract = {Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.} }
Endnote
%0 Conference Paper %T Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression %A Yuchen Zhang %A Martin J. Wainwright %A Michael I. Jordan %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-zhang14 %I PMLR %P 921--948 %U https://proceedings.mlr.press/v35/zhang14.html %V 35 %X Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity.
RIS
TY - CPAPER TI - Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression AU - Yuchen Zhang AU - Martin J. Wainwright AU - Michael I. Jordan BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-zhang14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 921 EP - 948 L1 - http://proceedings.mlr.press/v35/zhang14.pdf UR - https://proceedings.mlr.press/v35/zhang14.html AB - Under a standard assumption in complexity theory (NP not in P/poly), we demonstrate a gap between the minimax prediction risk for sparse linear regression that can be achieved by polynomial-time algorithms, and that achieved by optimal algorithms. In particular, when the design matrix is ill-conditioned, the minimax prediction loss achievable by polynomial-time algorithms can be substantially greater than that of an optimal algorithm. This result is the first known gap between polynomial and optimal algorithms for sparse linear regression, and does not depend on conjectures in average-case complexity. ER -
APA
Zhang, Y., Wainwright, M.J. & Jordan, M.I.. (2014). Lower Bounds on the Performance of Polynomial-time Algorithms for Sparse Linear Regression. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:921-948 Available from https://proceedings.mlr.press/v35/zhang14.html.

Related Material