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. 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.
The authors proposed a delay-tolerant algorithm based on asynchronous distributed online learning method.  The authors reordered the summation operation in the optimization process and achieved a more efficient asynchronous distributed optimization.  the authors also proved a bound of the regret with the unprojected online gradient descent algorithm, while the bound seems not very tight.  experiments shows the proposed algorithm performs much better than other async algorithm with many threads. There are two concerns with the results.One concern is the authors did not report the time comparison.  As we know the main contribution of the paper is to replace the sync with asynchronous updating in the distributed environment.  The overhead of sync is critical and major limitation of the distributed optimization. The authors proposed new algorithms which use async and achieve comparable performance with the sync algorithm which looks very promising, while the lack of time comparison, I can not tell how much improvement or contribution the algorithm can gain over existing algorithms.  So the contribution of the paper is heavily discounted without this report.Another concern is the authors seems to update each dimension separately, this is valuable in handling high dimensional data.  While it does not state that the algorithm can also handle the long matrix optimization.  In general the high dimensional problem is very rare, most of the cases we need to handle the big samples.  Does the algorithm have any advantage over existing methods when dimension is low while sample size is huge?  Also I suggest the authors perform more experiments to report the results in two cases.