Learning rotations with little regret

Elad Hazan, Satyen Kale, Manfred K. Warmuth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We describe online algorithms for learning a rotation from pairs of unit vectors in ℝn. We show that the expected regret of our online algorithm compared to the best fixed rotation chosen offline is O(√nL), where L is the loss of the best rotation. We also give a lower bound that proves that this expected regret bound is optimal within a constant factor. This resolves an open problem posed in COLT 2008. Our online algorithm for choosing a rotation matrix in each trial is based on the Follow-The-Perturbed-Leader paradigm. It adds a random spectral perturbation to the matrix characterizing the loss incurred so far and then chooses the best rotation matrix for that loss. We also show that any deterministic algorithm for learning rotations has Ω(T) regret in the worst case.

Original languageEnglish (US)
Title of host publicationCOLT 2010 - The 23rd Conference on Learning Theory
Pages144-154
Number of pages11
StatePublished - Dec 1 2010
Externally publishedYes
Event23rd Conference on Learning Theory, COLT 2010 - Haifa, Israel
Duration: Jun 27 2010Jun 29 2010

Publication series

NameCOLT 2010 - The 23rd Conference on Learning Theory

Other

Other23rd Conference on Learning Theory, COLT 2010
CountryIsrael
CityHaifa
Period6/27/106/29/10

All Science Journal Classification (ASJC) codes

  • Education

Fingerprint Dive into the research topics of 'Learning rotations with little regret'. Together they form a unique fingerprint.

  • Cite this

    Hazan, E., Kale, S., & Warmuth, M. K. (2010). Learning rotations with little regret. In COLT 2010 - The 23rd Conference on Learning Theory (pp. 144-154). (COLT 2010 - The 23rd Conference on Learning Theory).