  We consider the online sparse linear regression problem, which is the problem
of sequentially making predictions observing only a limited number of features
in each round, to minimize regret with respect to the best sparse linear
regressor, where prediction accuracy is measured by square loss. We give an
inefficient algorithm that obtains regret bounded by $\tilde{O}(\sqrt{T})$
after $T$ prediction rounds. We complement this result by showing that no
algorithm running in polynomial time per iteration can achieve regret bounded
by $O(T^{1-\delta})$ for any constant $\delta > 0$ unless $\text{NP} \subseteq
\text{BPP}$. This computational hardness result resolves an open problem
presented in COLT 2014 (Kale, 2014) and also posed by Zolghadr et al. (2013).
This hardness result holds even if the algorithm is allowed to access more
features than the best sparse linear regressor up to a logarithmic factor in
the dimension.
