Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning
Venue
Advances in Neural Information Processing Systems (NIPS) (2014)
Publication Year
2014
Authors
H. Brendan McMahan, Matthew Streeter
BibTeX
Abstract
We analyze new online gradient descent algorithms for distributed systems with
large delays between gradient computations and the corresponding updates. Using
insights from adaptive gradient methods, we develop algorithms that adapt not only
to the sequence of gradients, but also to the precise update delays that occur. We
first give an impractical algorithm that achieves a regret bound that precisely
quantifies the impact of the delays. We then analyze AdaptiveRevision, an algorithm
that is efficiently implementable and achieves comparable guarantees. The key
algorithmic technique is appropriately and efficiently revising the learning rate
used for previous gradient steps. Experimental results show when the delays grow
large (1000 updates or more), our new algorithms perform significantly better than
standard adaptive gradient methods.
