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 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.
Cite
Text
Mcmahan and Streeter. "No-Regret Algorithms for Unconstrained Online Convex Optimization." Neural Information Processing Systems, 2012.Markdown
[Mcmahan and Streeter. "No-Regret Algorithms for Unconstrained Online Convex Optimization." Neural Information Processing Systems, 2012.](https://mlanthology.org/neurips/2012/mcmahan2012neurips-noregret/)BibTeX
@inproceedings{mcmahan2012neurips-noregret,
title = {{No-Regret Algorithms for Unconstrained Online Convex Optimization}},
author = {Mcmahan, Brendan and Streeter, Matthew},
booktitle = {Neural Information Processing Systems},
year = {2012},
pages = {2402-2410},
url = {https://mlanthology.org/neurips/2012/mcmahan2012neurips-noregret/}
}