Timezone: »

 
Poster
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

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #35
in Posters Tue »
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.
Keywords: Bandit Algorithms · Online Learning · Convex Optimization · Sparsity and Compressed Sensing · Regression · Hardness of Learning and Approximations · Computational Complexity
[ Paper] 

Author Information

Shinji Ito (NEC Corporation, University of Tokyo)
Daisuke Hatano (National Institute of Informatics)
Hanna Sumita (National Institute of Informatics)
Akihiro Yabe
Takuro Fukunaga (National Institute of Informatics)
Naonori Kakimura
Ken-Ichi Kawarabayashi (National Institute of Informatics)

More from the Same Authors