Bayesian Distributed Stochastic Gradient Descent
We introduce Bayesian distributed stochastic gradient descent (BDSGD), a highthroughput algorithm for training deep neural networks on parallel computing clusters. This algorithm uses amortized inference in a deep generative model to perform joint posterior predictive inference of mini-batch gradient computation times in a compute cluster specific manner. Specifically, our algorithm mitigates the straggler effect in synchronous, gradient-based optimization by choosing an optimal cutoff beyond which mini-batch gradient messages from slow workers are ignored. The principle novel contribution and finding of this work goes beyond this by demonstrating that using the predicted run-times from a generative model of cluster worker performance improves over the static-cutoff prior art, leading to higher gradient computation throughput on large compute clusters. In our experiments we show that eagerly discarding the mini-batch gradient computations of stragglers not only increases throughput but sometimes also increases the overall rate of convergence as a function of wall-clock time by virtue of eliminating idleness.
========================================Update after authors' rebuttal======================================== I am generally happy with the authors' rebuttal, but would like to add a response to the reply, "For our purposes, we find that batch-size and objective function gain to be correlated in the literature, assuming strong convexity and Lipschitz-continuity ... ". These are rather strong assumptions that are not necessarily true, especially for deep neural networks. Furthermore, finding this optimal m (after taking the product with time-to-m) is non-linearly dependent on the local convexity and Lipschitzness, i.e. you really should be optimizing for objective function gain!  To be clear, the paper remains interesting irrespective of this, but I do think it would be a good direction for future research to properly understand the difference between optimizing throughput versus optimizing objective function gain. ================================================================================   This paper describes a method to improve on Chen et al, by automatically learning and deciding on the number of workers to wait for in distributed synchronous SGD, so as maximize "throughput" and avoid the straggler effect. This is done by using deep linear dynamical models to estimate worker run-times. The number of workers to wait for is then dynamically determined via model inference and maximizing the expected throughput at the next iteration. Experiments conducted show that the method can provide improvements over the static cutoff of Chen et al, and over a baseline dynamic Elfving cutoff.   This work improves over Chen et al by introducing a dynamic cutoff in a principled manner, further improving the state-of-the-art for synchronous SGD. In spite of the seemingly heavy machinery, the experiments show that a dynamic estimation works better than the static cut-off. This work could generate discussion in the systems-ML community, further the debate between asynchronous and synchronous distributed methods.  I have a number of questions / suggestions:  - The technique targets maximization of "throughput", which does not take into account the improvement in the objective function. What we're really interested in is the "rate of objective improvement", or roughly speaking, \Delta(c) / \tilde{x}_{(c)}, where \Delta(c) is the decrease in the objective function using gradients from c workers. Despite the claims (line 112-113) that optimizing throughput "handles tradeoff between iteration speedup and learning signal reduction", I do not see how it addresses the optimization problem / gradient variance. To make this more concrete, consider the optimization of a convex problem. At the start, we would expect all stochastic gradients to be generally in agreement, in which case, it might be best to use few workers, since \Delta may not change much with larger c. As we approach the opt, stochastic noise dominates, and \Delta increases quickly with larger c, so we would want to use as many workers as possible while still mitigating for stragglers.  - In the experiments, comparison between methods is often made in terms of time to reach X iterations. However, the real measure should be time to reach a loss or accuracy target. (After all, the entire point of cutoff methods is to trade-off between the statistical efficiency of synchronous methods and the throughput of asynchronous methods to achieve the best wall-clock time to accuracy, and not the best wall-clock time to target number of iterations.)  - As mentioned above, a lot of work goes into estimating the dynamic cutoff point. How much computation time does this take relative to the gradient computation?  - How does the cutoff point change over the course of the optimization? If it stabilises quickly, can we switch to a static method, or at least reduce the frequency at which the cutoff is changed?  - How would the proposed method compare with a naive approach of constructing an empirical CDF (a la Figure 2) and using that to determine cutoff?