Online Regression with Partial Information: Generalization and Linear Projection

Shinji Ito, Daisuke Hatano, Hanna Sumita, Akihiro Yabe, Takuro Fukunaga, Naonori Kakimura, Ken-Ichi Kawarabayashi
Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, PMLR 84:1599-1607, 2018.

Abstract

We investigate an online regression problem in which the learner makes predictions sequentially while only the limited information on features is observable. In this paper, we propose a general setting for the limitation of the available information, where the observed information is determined by a function chosen from a given set of observation functions. Our problem setting is a generalization of the online sparse linear regression problem, which has been actively studied. For our general problem, we present an algorithm by combining multi-armed bandit algorithms and online learning methods. This algorithm admits a sublinear regret bound when the number of observation functions is constant. We also show that the dependency on the number of observation functions is inevitable unless additional assumptions are adopted. To mitigate this inefficiency, we focus on a special case of practical importance, in which the observed information is expressed through linear combinations of the original features. We propose efficient algorithms for this special case. Finally, we also demonstrate the efficiency of the proposed algorithms by simulation studies using both artificial and real data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v84-ito18a, title = {Online Regression with Partial Information: Generalization and Linear Projection}, author = {Ito, Shinji and Hatano, Daisuke and Sumita, Hanna and Yabe, Akihiro and Fukunaga, Takuro and Kakimura, Naonori and Kawarabayashi, Ken-Ichi}, booktitle = {Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics}, pages = {1599--1607}, year = {2018}, editor = {Storkey, Amos and Perez-Cruz, Fernando}, volume = {84}, series = {Proceedings of Machine Learning Research}, month = {09--11 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v84/ito18a/ito18a.pdf}, url = {https://proceedings.mlr.press/v84/ito18a.html}, abstract = {We investigate an online regression problem in which the learner makes predictions sequentially while only the limited information on features is observable. In this paper, we propose a general setting for the limitation of the available information, where the observed information is determined by a function chosen from a given set of observation functions. Our problem setting is a generalization of the online sparse linear regression problem, which has been actively studied. For our general problem, we present an algorithm by combining multi-armed bandit algorithms and online learning methods. This algorithm admits a sublinear regret bound when the number of observation functions is constant. We also show that the dependency on the number of observation functions is inevitable unless additional assumptions are adopted. To mitigate this inefficiency, we focus on a special case of practical importance, in which the observed information is expressed through linear combinations of the original features. We propose efficient algorithms for this special case. Finally, we also demonstrate the efficiency of the proposed algorithms by simulation studies using both artificial and real data.} }
Endnote
%0 Conference Paper %T Online Regression with Partial Information: Generalization and Linear Projection %A Shinji Ito %A Daisuke Hatano %A Hanna Sumita %A Akihiro Yabe %A Takuro Fukunaga %A Naonori Kakimura %A Ken-Ichi Kawarabayashi %B Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2018 %E Amos Storkey %E Fernando Perez-Cruz %F pmlr-v84-ito18a %I PMLR %P 1599--1607 %U https://proceedings.mlr.press/v84/ito18a.html %V 84 %X We investigate an online regression problem in which the learner makes predictions sequentially while only the limited information on features is observable. In this paper, we propose a general setting for the limitation of the available information, where the observed information is determined by a function chosen from a given set of observation functions. Our problem setting is a generalization of the online sparse linear regression problem, which has been actively studied. For our general problem, we present an algorithm by combining multi-armed bandit algorithms and online learning methods. This algorithm admits a sublinear regret bound when the number of observation functions is constant. We also show that the dependency on the number of observation functions is inevitable unless additional assumptions are adopted. To mitigate this inefficiency, we focus on a special case of practical importance, in which the observed information is expressed through linear combinations of the original features. We propose efficient algorithms for this special case. Finally, we also demonstrate the efficiency of the proposed algorithms by simulation studies using both artificial and real data.
APA
Ito, S., Hatano, D., Sumita, H., Yabe, A., Fukunaga, T., Kakimura, N. & Kawarabayashi, K.. (2018). Online Regression with Partial Information: Generalization and Linear Projection. Proceedings of the Twenty-First International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 84:1599-1607 Available from https://proceedings.mlr.press/v84/ito18a.html.

Related Material