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." Annual Conference on Computational Learning Theory, 2010. doi:10.1007/s10994-016-5548-xMarkdown
[Hazan et al. "Learning Rotations with Little Regret." Annual Conference on Computational Learning Theory, 2010.](https://mlanthology.org/colt/2010/hazan2010colt-learning/) doi:10.1007/s10994-016-5548-xBibTeX
@inproceedings{hazan2010colt-learning,
title = {{Learning Rotations with Little Regret}},
author = {Hazan, Elad and Kale, Satyen and Warmuth, Manfred K.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2010},
pages = {144-154},
doi = {10.1007/s10994-016-5548-x},
url = {https://mlanthology.org/colt/2010/hazan2010colt-learning/}
}