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.
All Science Journal Classification (ASJC) codes
- Artificial Intelligence
- Bregman projection
- Online learning
- Regret bounds