Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation
Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-Ichi Kawarabayashi
Abstract
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. Under these assumptions, we present polynomial-time sublinear-regret algorithms for the online sparse linear regression. In addition, thorough experiments with publicly available data demonstrate that our algorithms outperform other known algorithms.
BibTeX
@inproceedings{NIPS2017_6e5025cc,
author = {Ito, Shinji and Hatano, Daisuke and Sumita, Hanna and Yabe, Akihiro and Fukunaga, Takuro and Kakimura, Naonori and Kawarabayashi, Ken-Ichi},
booktitle = {Advances in Neural Information Processing Systems},
editor = {I. Guyon and U. Von Luxburg and S. Bengio and H. Wallach and R. Fergus and S. Vishwanathan and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Efficient Sublinear-Regret Algorithms for Online Sparse Linear Regression with Limited Observation},
url = {https://proceedings.neurips.cc/paper_files/paper/2017/file/6e5025ccc7d638ae4e724da8938450a6-Paper.pdf},
volume = {30},
year = {2017}
}