No-Regret Algorithms for Unconstrained Online Convex Optimization
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.
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.
Research Areas
