betaFeedback

WorksComputer Science

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.

Paper details

vlnc:W_9mzkstas
Version
v1 · latest
Published
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…