# Adversarial Delays in Online Strongly-Convex Optimization

arXiv: https://arxiv.org/abs/1605.06201 · HTML: https://mlsanity.com/paper/1605.06201/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 May 2016.

## Built on by (most cited first, 2 of 2)

- [Nonstochastic Bandits with Composite Anonymous Feedback](https://mlsanity.com/paper/2112.02866/) (2021)
- [Online Strongly Convex Optimization with Unknown Delays](https://mlsanity.com/paper/2103.11354/) (2021)

## Abstract (arXiv)

We consider the problem of strongly-convex online optimization in presence of adversarial delays; in a T-iteration online game, the feedback of the player's query at time t is arbitrarily delayed by an adversary for dt rounds and delivered before the game ends, at iteration t+dt-1. Specifically for algoonline-gradient-descent algorithm we show it has a simple regret bound of Ohsumt=1T log (1+ fracdtt). This gives a clear and simple bound without resorting any distributional and limiting assumptions on the delays. We further show how this result encompasses and generalizes several of the existing known results in the literature. Specifically it matches the celebrated logarithmic regret Ohlog T when there are no delays (i.e. dt = 1) and regret bound of Ohτ log T for constant delays dt = τ.