Online Learning with Adversarial Delays
Authors: Kent Quanrud, Daniel Khashabi
NeurIPS 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the performance of standard online learning algorithms when the feedback is delayed by an adversary. We show that online-gradient-descent [1] and follow-the-perturbed-leader [2] achieve regret O(D) in the delayed setting, where D is the sum of delays of each round s feedback. This bound collapses to an optimal O(T) bound in the usual setting of no delays (where D = T). Our main contribution is to show that standard algorithms for online learning already have simple regret bounds in the most general setting of delayed feedback, making adjustments to the analysis and not to the algorithms themselves. Our results help affirm and clarify the success of recent algorithms in optimization and machine learning that operate in a delayed feedback model. In Section 2, we analyze the online-gradient-descent algorithm in the delayed setting, giving upper bounds on the regret as a function of the sum of delays D. In Section 3, we analyze the follow-the-perturbed-leader in the delayed setting and derive a regret bound in terms of D. |
| Researcher Affiliation | Academia | Kent Quanrud and Daniel Khashabi Department of Computer Science University of Illinois at Urbana-Champaign Urbana, IL 61801 {quanrud2,khashab2}@illinois.edu |
| Pseudocode | No | The paper describes algorithms using mathematical notation and text, but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not describe the use of any datasets for training or public access to them. |
| Dataset Splits | No | The paper is theoretical and does not describe the use of any datasets or their splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any experimental setup details such as hyperparameters or training configurations. |