Learning rotations with little regret

Elad Hazan, Satyen Kale, Manfred K. Warmuth

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

We describe online algorithms for learning a rotation from pairs of unit vectors in Rn. We show that the expected regret of our online algorithm compared to the best fixed rotation chosen offline over T iterations is nT. 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 is essentially an incremental gradient descent algorithm over the set of all matrices, with specially tailored projections. We also show that any deterministic algorithm for learning rotations has Ω(T) regret in the worst case.

Original languageEnglish (US)
Pages (from-to)129-148
Number of pages20
JournalMachine Learning
Volume104
Issue number1
DOIs
StatePublished - Jul 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Artificial Intelligence

Keywords

  • Bregman projection
  • Minimax
  • Online learning
  • Regret bounds
  • Rotations

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

  • Cite this