Abstract
We consider the problem of prediction with expert advice when the losses of the experts have low-dimensional structure: they are restricted to an unknown d-dimensional subspace. We devise algorithms with regret bounds that are independent of the number of experts and depend only on the rank d. For the stochastic model we show a tight bound of Θp√ dTq, and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of Opd√ Tq and a lower bound of Ωp√ dTq.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1096-1114 |
| Number of pages | 19 |
| Journal | Journal of Machine Learning Research |
| Volume | 49 |
| Issue number | June |
| State | Published - Jun 6 2016 |
| Event | 29th Conference on Learning Theory, COLT 2016 - New York, United States Duration: Jun 23 2016 → Jun 26 2016 |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence
Fingerprint Dive into the research topics of 'Online learning with low rank experts'. Together they form a unique fingerprint.
Cite this
Hazan, E., Koren, T., Livni, R., & Mansour, Y. (2016). Online learning with low rank experts. Journal of Machine Learning Research, 49(June), 1096-1114.