Fully Unconstrained Online Learning

We provide an online learning algorithm that obtains regret G\|w_\|T (\|w_\|GT) + \|w_\|² + G² on G-Lipschitz convex losses for any comparison point w_ without knowing either G or \|w_\|. Importantly, this matches the optimal bound G\|w_\|T available with such knowledge (up to logarithmic factors), unless either \|w_\| or G is so large that even G\|w_\|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.