TY - GEN

T1 - Learning rotations with little regret

AU - Hazan, Elad

AU - Kale, Satyen

AU - Warmuth, Manfred K.

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867123611&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867123611&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84867123611

SN - 9780982252925

T3 - COLT 2010 - The 23rd Conference on Learning Theory

SP - 144

EP - 154

BT - COLT 2010 - The 23rd Conference on Learning Theory

T2 - 23rd Conference on Learning Theory, COLT 2010

Y2 - 27 June 2010 through 29 June 2010

ER -