Learning rotations with little regret

摘要

We describe online algorithms for learning a rotation from pairs of unit vectors in \(\mathbb {R}^n\). We show that the expected regret of our online algorithm compared to the best fixed rotation chosen offline over T iterations is \(\sqrt{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 \(\varOmega (T)\) regret in the worst case.