Fully Unconstrained Online Learning

We provide an online learning algorithm that obtains regret $G\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }\sqrt{T\log (\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }G\sqrt{T})}+\mathrm{\parallel }{w}_{\star }{\mathrm{\parallel }}^2+G^2$ on $G$-Lipschitz convex losses for any comparison point $w_{\star }$ without knowing either $G$ or $\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }$. Importantly, this matches the optimal bound $G\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }\sqrt{T}$ available with such knowledge (up to logarithmic factors), unless either $\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }$ or $G$ is so large that even $G\mathrm{\parallel }{w}_{\star }\mathrm{\parallel }\sqrt{T}$ is roughly linear in $T$. Thus, it matches the optimal bound in all cases in which one can achieve sublinear regret, which arguably most “interesting” scenarios.