Online learning with low rank experts

Elad Hazan, Tomer Koren, Roi Livni, Yishay Mansour

Research output: Contribution to journalConference articlepeer-review

4 Scopus citations

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 languageEnglish (US)
Pages (from-to)1096-1114
Number of pages19
JournalJournal of Machine Learning Research
Volume49
Issue numberJune
StatePublished - Jun 6 2016
Event29th Conference on Learning Theory, COLT 2016 - New York, United States
Duration: Jun 23 2016Jun 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