No-Regret Algorithms for Unconstrained Online Convex Optimization
Venue
Advances in Neural Information Processing Systems (NIPS) (2012)
Publication Year
2012
Authors
Matthew Streeter, H. Brendan McMahan
BibTeX
Abstract
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.
