Unconstrained Robust Online Convex Optimization

This paper addresses online learning with corrupted'' feedback. Our learner is provided with potentially corrupted gradients $\tilde g_t$ instead of the true’’ gradients $g_t$. We make no assumptions about how the corruptions arise: they could be the result of outliers, mislabeled data, or even malicious interference. We focus on the difficult ``unconstrained’’ setting in which our algorithm must maintain low regret with respect to any comparison point $u\in {\mathbb{R}}^d$. The unconstrained setting is significantly more challenging as existing algorithms suffer extremely high regret even with very tiny amounts of corruption (which is not true in the case of a bounded domain). Our algorithms guarantee regret $\mathrm{\parallel }u\mathrm{\parallel }G(\sqrt{T}+k)$ when $G\ge {\max }_t\mathrm{\parallel }{g}_t\mathrm{\parallel }$ is known, where $k$ is a measure of the total amount of corruption. When $G$ is unknown we incur an extra additive penalty of $(\mathrm{\parallel }u{\mathrm{\parallel }}^2+G^2)k$.