抄録
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 polynomialtime sublinear-regret algorithm unless NP ⊆ 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 polynomialtime 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.
| 本文言語 | English |
|---|---|
| ページ(範囲) | 4100-4109 |
| ページ数 | 10 |
| ジャーナル | Advances in Neural Information Processing Systems |
| 巻 | 2017-December |
| 出版ステータス | Published - 2017 |
| イベント | 31st Annual Conference on Neural Information Processing Systems, NIPS 2017 - Long Beach, United States 継続期間: 2017 12月 4 → 2017 12月 9 |
ASJC Scopus subject areas
- コンピュータ ネットワークおよび通信
- 情報システム
- 信号処理
フィンガープリント
「Efficient sublinear-regret algorithms for online sparse linear regression with limited observation」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。引用スタイル
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS