No-Regret Algorithms for Unconstrained Online Convex Optimization
  Some of the most compelling applications of online convex optimization,
including online prediction and classification, are unconstrained: the natural
feasible set is R^n. Existing algorithms fail to achieve sub-linear regret in
this setting unless constraints on the comparator point x^* are known in
advance. We present algorithms that, without such prior knowledge, offer
near-optimal regret bounds with respect to any choice of x^*. In particular,
regret with respect to x^* = 0 is constant. We then prove lower bounds showing
that our guarantees are near-optimal in this setting.
