Online Strongly Convex Optimization with Unknown Delays
This work addresses the problem of delayed feedback in online learning for researchers and practitioners, offering incremental improvements by leveraging strong convexity for better theoretical performance.
The paper tackles online convex optimization with unknown delays by exploiting strong convexity to improve regret bounds, achieving O(d log T) compared to previous O(sqrt(T+D)) results, and extends this to the bandit setting with similar guarantees.
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.