Artificial Constraints and Lipschitz Hints for Unconstrained Online Learning

We provide algorithms that guarantee regret RT(u)≤ tilde O(G|u|3 + G(|u|+1)√T) or RT(u)≤ tilde O(G|u|3T1/3 + GT1/3+ G|u|√T) for online convex optimization with G-Lipschitz losses for any comparison point u without prior knowledge of either G or |u|. Previous algorithms dispense with the O(|u|3) term at the expense of knowledge of one or both of these parameters, while a lower bound shows that some additional penalty term over G|u|√T is necessary. Previous penalties were exponential while our bounds are polynomial in all quantities. Further, given a known bound |u|≤ D, our same techniques allow us to design algorithms that adapt optimally to the unknown value of |u| without requiring knowledge of G.