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.
Summary¶
Develops unconstrained online convex optimization algorithms whose regret adapts to any comparator norm without needing the feasible-set radius in advance. The reward-doubling idea is important because it preserves near-optimal guarantees on unbounded domains, including constant regret to the zero comparator, and clarifies the lower-bound tradeoffs faced by parameter-free OCO.