Asymptotic Convergence in Online Learning with Unbounded Delays
By Scott Garrabrant, Nate Soares, Jessica Taylor. 2016
10 citations recorded by the source corpus.
We study the problem of predicting the results of computations that are too expensive to run, via the observation of the results of smaller computations. We model this as an online learning problem with delayed feedback, where the length of the delay is unbounded, which we study mainly in a stochastic setting. We show that in this setting, consistency is not possible in general, and that optimal forecasters might not have average regret going to zero. However, it is still possible to give algorithms that converge asymptotically to Bayes-optimal predictions, by evaluating forecasters on specific sparse independent subsequences of their predictions. We give an algorithm that does this, which converges asymptotically on good behavior, and give very weak bounds on how long it takes to converge. We then relate our results back to the problem of predicting large computations in a deterministic setting.
Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Jessica Taylor
- Tsvi Benson-Tilsen
- Scott Garrabrant
- Nate Soares
- Andrew Critch
- Tom Everitt
- Marcus Hutter
In Management Science and Operations Research
Citations in the corpus
- Logical Induction (2016, background): “Refer to Garrabrant, Soares, and Taylor (2016) for a discussion of why this is a good way to broaden the set of sequences that count as pseudorandom.”