Timezone: »

No-Regret Algorithms for Unconstrained Online Convex Optimization
Matthew Streeter · Brendan McMahan

Wed Dec 05 07:00 PM -- 12:00 AM (PST) @ Harrah’s Special Events Center 2nd Floor

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 an algorithm that, without such prior knowledge, offers 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 algorithm's guarantees are optimal in this setting up to constant factors.

Author Information

Matthew Streeter (Duolingo)
Brendan McMahan (Google Research)

More from the Same Authors