  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.
