Learning Rotations with Little Regret
Abstract
We describe online algorithms for learning a rotation from pairs of unit vectors in $\mathbb {R}^n$ 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}$ n T . 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)$ Ω ( T ) regret in the worst case.
Cite
Text
Hazan et al. "Learning Rotations with Little Regret." Machine Learning, 2016. doi:10.1007/S10994-016-5548-XMarkdown
[Hazan et al. "Learning Rotations with Little Regret." Machine Learning, 2016.](https://mlanthology.org/mlj/2016/hazan2016mlj-learning/) doi:10.1007/S10994-016-5548-XBibTeX
@article{hazan2016mlj-learning,
title = {{Learning Rotations with Little Regret}},
author = {Hazan, Elad and Kale, Satyen and Warmuth, Manfred K.},
journal = {Machine Learning},
year = {2016},
pages = {129-148},
doi = {10.1007/S10994-016-5548-X},
volume = {104},
url = {https://mlanthology.org/mlj/2016/hazan2016mlj-learning/}
}