Improved Bounds For Online Convex Optimization

Abstract

In this paper, we consider the problem of online learning with convex objectives. Most of the existing work shows that static and dynamic regrets scale logarithmically or sub-linearly with the time horizon T. On the contrary, for the strongly convex setting, it is shown that the static and dynamic regrets scale with the variation term that measures the rate at which the function changes over time. In the convex setting, we show that a simple Online Gradient Descent (OGD) algorithm with single round at each time achieves a regret that is comparable with the strongly convex setting with an additional assumption of Quadratic Growth (QG) condition. More specifically, we show that the static and dynamic regrets scale as ${\mathcal{O}}\left({{{\operatorname{Var} }_3}(T)}\right)$ and ${\mathcal{O}}\left({{{\operatorname{Var} }_1}(T)}\right) + {\mathcal{O}}\left({Va{r_2}(T)}\right)$, respectively. Here, Var<inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf>, i = 1, 2, 3 represent variation terms that capture different aspects of changes in the optimal solution over time. We use experiments to corroborate some of our theoretical findings.