Timezone: »

 
Poster
Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning
Brendan McMahan · Matthew Streeter

Mon Dec 08 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D
in Poster Session and Reception »

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.

[ PDF] 

Author Information

Brendan McMahan (Google Research)
Matthew Streeter (Duolingo)

More from the Same Authors