Online Strongly Convex Optimization with Unknown Delays
  We investigate the problem of online convex optimization with unknown delays,
in which the feedback of a decision arrives with an arbitrary delay. Previous
studies have presented a delayed variant of online gradient descent (OGD), and
achieved the regret bound of $O(\sqrt{T+D})$ by only utilizing the convexity
condition, where $D$ is the sum of delays over $T$ rounds. In this paper, we
further exploit the strong convexity to improve the regret bound. Specifically,
we first extend the delayed variant of OGD for strongly convex functions, and
establish a better regret bound of $O(d\log T)$, where $d$ is the maximum
delay. The essential idea is to let the learning rate decay with the total
number of received feedback linearly. Furthermore, we consider the more
challenging bandit setting, and obtain similar theoretical guarantees by
incorporating the classical multi-point gradient estimator into our extended
method. To the best of our knowledge, this is the first work that solves online
strongly convex optimization under the general delayed setting.
