Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation

Online sparse linear regression is the task of applying linear regression analysis to examples arriving sequentially subject to a resource constraint that a limited number of features of examples can be observed. Despite its importance in many practical applications, it has been recently shown that there is no polynomial-time sublinear-regret algorithm unless NP$\subseteq$BPP, and only an exponential-time sublinear-regret algorithm has been found. In this paper, we introduce mild assumptions to solve the problem. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms. Papers published at the Neural Information Processing Systems Conference.