Skip to main content

Online Learning with Low Rank Experts

Author(s): Hazan, Elad; Koren, Tomer; Livni, Roi; Mansour, Yishay

To refer to this page use:
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 Θ(\sqrtdT), and extend it to a setting of an approximate d subspace. For the adversarial model we show an upper bound of O(d\sqrtT) and a lower bound of Ω(\sqrtdT).
Publication Date: 2016
Citation: Hazan, Elad, Tomer Koren, Roi Livni, and Yishay Mansour. "Online Learning with Low Rank Experts." In Conference on Learning Theory (2016): pp. 1096-1114.
ISSN: 2640-3498
Pages: 1096 - 1114
Type of Material: Conference Article
Journal/Proceeding Title: Conference on Learning Theory
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.