Adversarial Delays in Online Strongly-Convex Optimization
arXiv:1605.06201
Abstract
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 d_t rounds and delivered before the game ends, at iteration t+d_t-1. Specifically for \algo{online-gradient-descent} algorithm we show it has a simple regret bound of \Oh{\sum_{t=1}^T \log (1+ \frac{d_t}{t})}. 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 \Oh{\log T} when there are no delays (i.e. d_t = 1) and regret bound of \Oh{τ\log T} for constant delays d_t = τ.
arXiv commentWe discovered mistakes in the proof of proof of Theorem 3.1. The overall is no longer correct, although the claim is still true
References in corpus (8)
- HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- Slow Learners are Fast
- Online Learning under Delayed Feedback
- AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
- On Lower and Upper Bounds for Smooth and Strongly Convex Optimization Problems
- Decentralized Consensus Algorithm with Delayed and Stochastic Gradients