Unconstrained Robust Online Convex Optimization

This paper addresses online learning with ``corrupted'' feedback. Our learner is provided with potentially corrupted gradients gₜ instead of the ``true'' gradients gₜ. 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 Rᵈ. 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 \|u\|G (T + k) when G ₜ \|gₜ\| is known, where k is a measure of the total amount of corruption. When G is unknown we incur an extra additive penalty of (\|u\|²+G²) k.