Delay-Tolerant Algorithms for Asynchronous Distributed Online Learning

We analyze new online gradient descent algorithms for distributed systems with large delays between gradient computations and the corresponding updates. Us-ing 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 learn-ing rate used for previous gradient steps. Experimental results show when the delays grow large (1000 updates or more), our new algorithms perform signifi-cantly better than standard adaptive gradient methods.