{'fraction_non_alphanumeric': 0.04049091931588872, 'fraction_numerical': 0.010387376360448576, 'mean_word_length': 4.555963977210071, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Accelerating Parallel Stochastic Gradient Descent via Non-blocking Mini-batches

SOTA decentralized SGD algorithms can overcome the bandwidth bottleneck at the parameter server by using communication collectives like Ring All-Reduce for synchronization. While the parameter updates in distributed SGD may happen asynchronously there is still a synchronization barrier to make sure that the local training epoch at every learner is complete before the learners can advance to the next epoch. The delays in waiting for the slowest learners(stragglers) remain to be a problem in the synchronization steps of these state-of-the-art decentralized frameworks. In this paper, we propose the (de)centralized Non-blocking SGD (Non-blocking SGD) which can address the straggler problem in a heterogeneous environment. The main idea of Non-blocking SGD is to split the original batch into mini-batches, then accumulate the gradients and update the model based on finished mini-batches. The Non-blocking idea can be implemented using decentralized algorithms including Ring All-reduce, D-PSGD, and MATCHA to solve the straggler problem. Moreover, using gradient accumulation to update the model also guarantees convergence and avoids gradient staleness. Run-time analysis with random straggler delays and computational efficiency/throughput of devices is also presented to show the advantage of Non-blocking SGD. Experiments on a suite of datasets and deep learning networks validate the theoretical analyses and demonstrate that Non-blocking SGD speeds up the training and fastens the convergence. Compared with the state-of-the-art decentralized asynchronous algorithms like D-PSGD and MACHA, Non-blocking SGD takes up to 2x fewer time to reach the same training loss in a heterogeneous environment.


INTRODUCTION
Stochastic gradient descent (SGD) is the backbone of most state-of-the-art machine learning algorithms. Hence, guaranteeing the convergence rate and stability of the SGD algorithm as well as speeding-up SGD are critical to machine learning training. Classical SGD was designed to be run serially at a single node; the stability and convergence rate of single node SGD are reliable and are well studied (Dekel et al., 2012;Ghadimi & Lan, 2013). However, the size of deep learning models, the magnitude of computations, and the size of datasets have increased dramatically in recent years. Running SGD at a single node can be prohibitively slow. To solve this problem, distributed implementations of SGD, which parallelize the training across multiple worker nodes are shown to be successful. Following are the major types of distributed SGD: Synchronous/Asynchronous SGD with Centralized Aggregation The most popular framework to implement distributed SGD and parallelize gradient computation is using a centralized aggregator (aka parameter server) (Dean & Barroso, 2013;Li et al., 2014;Cui et al., 2014;Dutta et al., 2016). In distributed SGD the parameter updates can be designed as either synchronous or asynchronous. During synchronization in data-parallel distributed SGD, the parameter server waits for all the nodes to finish their local training and push gradients before it updates the model parameters. In asynchronous distributed SGD, the model parameters are updated asynchronously at the parameter server when any learner pushes the gradient, thereby preventing the straggler problem. However, synchronous distributed SGD faces the challenge of straggling learners: random delays in computation and heterogeneous environments are common in distributed systems and edge devices. Waiting for the straggling slower learners can diminish the speed-up offered by parallelizing the training. Asynchronous distributed SGD is associated with gradient staleness problem: learners may return stale gradients that were evaluated at an older version of the model, which will lead to slower converge and worse final model. In addition, both synchronous and asynchronous centralized distributed SGD suffer from the communication bottleneck problem when the framework has a large number of learner nodes. Decentralized Synchronous SGD To address the issue of communication bottleneck in centralized (a)synchronous SGD, an alternate is to perform decentralized aggregation without a parameter server. Both synchronous and asynchronous methods are switched to the decentralized algorithm. The most popular decentralized synchronous distributed SGD framework is Ring All-reduce, which is implemented in NVIDIA Collective Communications Library (NCCL) and supported by TensorFlow and PyTorch. Although ring all-reduce address the communication bottleneck issue, the heterogeneous environment of nodes remains to be the problem. Decentralized Asynchronous SGD In recent years, many papers proposed decentralized asynchronous SGD with novel topology structures. Most of them utilize parameter averaging instead of gradient updates, such as decentralized parallel SGD (D-PSGD) (Lian et al., 2018). Each node only needs to average with its neighbors' model, thus reducing the communication complexity (Blot et al., 2016;Jin et al., 2016;Lian et al., 2017). Previous works in distributed optimization have extensively studied the error convergence of decentralized SGD in terms of iterations or communication rounds (Duchi et al., 2011;Jakovetic et al., 2018;Nedic & Ozdaglar, 2009;Scaman et al., 2018;Towfic et al., 2016;Yuan et al., 2016;Zeng & Yin, 2018). But all of the previous works only focus on the number of iterations required to achieve a target error. Densely-connected networks, when used appropriately, give faster error convergence. However, they incur a higher communication delay per iteration, which typically increases with the maximal node degree and lead to worse wall-clock time. Other novel asynchronous decentralized algorithms with sparse-connected network topology have slower or even uncertain convergence.

Limitation of Synchronous SGD: Heterogeneity in Multi-GPU Architectures
Both centralized and decentralized synchronous distributed SGD suffer from poor performance in heterogeneous environments. There are two reasons for heterogeneity in multi-GPU training: performance gap among GPUs and sparse data assigned to different GPUs. Both TensorFlow and Omnivore support deep learning on heterogeneous CPU+GPU architecture (Abadi et al., 2016;Hadjis et al., 2016). Performance gap is significant if same work is assigned to different generations of GPUs/CPUs. Even within GPUs with the same architecture, the gap still exists. The clock rate and memory latency display oscillations on GPUs with the same model from the same vendor. The gap is amplified when multiple GPUs are integrated on the same server. Given the same training batch on a server with 4 NVIDIA V100 GPUs, the maximum gap of execution time between GPUs is as large as 32% for a single epoch (Ma & Rusu, 2020). Sparse data, which refers to the number of nonzeros data various among batches. Since sparse linear algebra operations are sensitive to the number of non-zero data, the execution time is different in processing across batches. Previous works propose algorithms for two different batch sizes concurrently to use in a heterogeneous CPU+GPU architecture to maximize utilization and reduce staleness for both resources (Ma & Rusu, 2020;Masters & Luschi, 2018). However, these algorithms can not handle sparse data issues and performance gaps between GPUs with the same model. Manually assigning batch size is also inconvenient.

Main Contribution
In this paper, we propose the (de)centralized Non-blocking Synchronous parallel SGD (Non-blocking SGD) which can address stragglers caused by heterogeneous environments. In (de)centralized Non-blocking SGD framework, the original batch will be split into mini-batches locally at the learners and the model is updated based on only completed minibatches (for which gradient is available). The decentralized Non-block SGD with a sparse connection topology can solve all the challenges listed above: stragglers (by minimizing the delays in waiting for the slowest learner), gradient staleness (by doing synchronous updates instead of asynchronous updates), and slower convergence (by only allowing once local update). More specifically, the main contribution of this paper is as follows: • Non-blocking to deal with Stragglers: Most popular distributed (a)synchronous SGD algorithms suffers from stragglers. We propose a novel non-blocking idea that can solve the straggler problem and implement it on both centralized and decentralized frameworks. Decentralized Non-blocking algorithms utilize Ring Allreduce, D-PSGD, and MATCHA as baselines and can achieve faster and more reliable convergence, fewer delays, and shorter wall-clock time.
• General performance analysis against state-of-theart algorithms: We present both complexity and efficiency analysis of the decentralized Non-block SGD and compare it with the general decentralized stateof-the-art algorithm. Expected runtime per iteration, expected runtime per epoch, and expected throughput efficiency/computational efficiency are included in the paper. We also generalize the analysis by removing several common assumptions in previous work such as bounded delays, exponential distributed service times, and independence of the staleness process. We also use convergence analysis to prove that error convergence is the same or faster than baseline algorithms.
• Extendable Non-blocking idea: We propose the general Non-blocking algorithm which is extendable to most (de)centralized state-of-the-art algorithms. Furthermore, going beyond (de)centralized SGD, the Nonblocking idea is extendable to any distributed compu-tation or consensus algorithm that requires frequent synchronizations. For instance, in federated learning systems whose edge devices have large performance gaps. The gradient accumulation in the Non-blocking idea can also help address the limited memory issue on edge devices.
• Experimental Results on Error-versus-wallclock Time Convergence: We evaluate the Non-blocking idea in a heterogeneous environment using a suite of deep learning tasks, including computer vision tasks on CIFAR-10/100. The empirical results corroborate the theoretical analyses to demonstrate the that Nonblocking idea takes ∼ 2× fewer time to reach the same training loss in heterogeneous environments.

Problem Formulation
Suppose a network has P worker nodes to implement distributed SGD. The model parameters are denoted by x where x ∈ R d . Each worker node i only has access to its own local training data distributed as D i . The purpose of distributed SGD is to train a model by minimize the objective function L(x) using P worker nodes. The problem can be defined as follows: where l(x) is the loss function defined by the learning model and E s∼Di [l i (x; s)] is the local objective function at the i-th worker.

Synchronous Centralized SGD
Synchronous centralized SGD with parameter server is parallel mini-batch SGD, where workers compute stochastic gradients of the local objectives in parallel and use the averaged gradient to update model parameters after each iteration. The update rule is written as: where x k is the parameters at the k-th iteration, g i (x k ; ξ i ) denotes the gradient descent, η is the learning rate, and ξ i is the randomly sampled mini-batches from the local data distribution. The convergence analysis has been presented in (Dekel et al., 2012;Bottou et al., 2018).

Asynchronous Centralized SGD
The asynchronous decentralized SGD allows learner nodes to push gradients to the parameter server once they finish training and the parameter server updates the model parameters without waiting for the slower learners. The update rule can be written as: where x k is the model parameters at the parameter server after the k-th update, x i is the parameters at the i-th learner node, η is the learning rate, and ξ i is the randomly sampled mini-batches from the local data distribution. After the parameter server finishes the update, the learner node which pushes the gradient will pull the new model from the parameter server and start a new iteration.

Synchronous Decentralized SGD
Synchronous Decentralized SGD such as ring all-reduce averages parameters of all learner nodes after each iteration.
Each node gathers the model parameters from other nodes and performs the update locally. The update rule can be written as: where x i k+1 denotes the parameters of the i-th learner node after the local update and x k+1 denotes the parameters after ring all-reduce parameter averaging.

Asynchronous Decentralized SGD(D-PSGD)
In recent years, many papers proposed decentralized asynchronous distributed SGD with novel topology structures. (Nedic & Ozdaglar, 2009;Duchi et al., 2011) In D-PSGD (also referred to as consensus-based distributed SGD) (Lian et al., 2017), nodes perform one local update and average their models only with neighboring nodes. The update rule is given as: where W ∈ R P * P and W ij is the (i, j)-th element of the mixing matrix W which presents the adjacency of node i and j. W ij is non-zero if and only if node i and node j are connected. One can design a sparse mixing topology to reduce the communication complexity. Although D-PSGD has been extensively studied in the last decade and many new algorithms are proposed based on it (Scaman et al., 2018;Wang et al., 2019), it remains open how to analyze the case when workers perform more than one local update.
Since nodes only average their models with neighbors, it's slower for two non-adjacent nodes to finally converge to the same model. In addition, since D-PSGD and other stateof-the-art variants need to stop and communicate after all

General Non-blocking Algorithm
In this section, we introduce the Non-blocking SGD algorithm. Since the stragglers' problem is caused by the performance gap between different GPUs in heterogeneous environments, allowing GPUs with different computational performance to process different amount of data before synchronization steps can reduce the proportion of waiting time and address the stragglers issue. The general non-blocking algorithm is presented in Algorithm 1. Following Algorithm 1, the Non-blocking idea can be applied to almost all the parallel SGD frameworks.

Non-blocking D-PSGD Algorithm
Implementation Detail: Figure 1 briefly illustrates the Non-blocking algorithm using D-PSGD as the baseline. We can easily see that by applying Non-blocking SGD with mini-batches on different workers, the proportion of time waiting for stragglers reduces dramatically. The pseudocode of Non-blocking D-PSGD is shown in algorithm 2.
We briefly describe the implementation detail of the Nonblocking D-PSGD algorithm below: • Sample data: Split original dataset into P subsets equally. Each local worker chooses a subset for training. In the same epoch, training subsets should be different among workers. Sample ξ k,i from local train-Algorithm 1 General Non-blocking algorithm 1: Initialization:initialize local models {x i 0 } P i=1 with the same initialization, learning rate η, batch size B, and the total number of iterations K. Split the original dataset into P equal-sized subsets ξ 1 , . . . , ξ P . Assign subset ξ i to i-th worker. Shuffle local subset after each epoch. 3 2: for k=0, 1, 2, ... K-1 ≤ K do • Adjust learning rate: Set the initial learning rate and adjust the learning rate according to the number of finished mini-batches. The purpose of adjusting learning rate is to assign larger learning rate to learner which has processed more mini-batches in the same iteration. n k,i is the amount of trained mini-batches before synchronization in iteration k and node i. η k,i = η * n k,i N .
• Compute gradients: Compute and accumulate all the gradients of the mini-batches Algorithm 2 Non-blocking D-PSGD algorithm 1: Initialization: initialize local models {x i 0 } P i=1 with the same initialization, learning rate η, batch size B, weight matrix W , and the total number of iterations K. Split the original dataset into P equal-sized subsets ξ 1 , . . . , ξ P . Assign subset ξ i to i-th worker. Shuffle local subset after each epoch. 3 2: for k=0, 1, 2, ... K-1 ≤ K do 3: Randomly sample ξ k,i from local subset in the i-th worker and divide the sample batch ξ k,i into N minibatches ξ k,i,1 , ..., ξ k,i,N . Compute the neighborhood weighted average by fetching optimization variables from neighbors 2 : Update the local model using accumulated gradient Shuffle local subset by the end of epoch 3 15: end for 16: Output: The average of all workers 1 Since stragglers train fewer mini-batches under the same batch time, unfinished mini-batches will be abandoned by the stragglers.
• Averaging: Differs in different baseline algorithms. In Non-blocking D-PSGD, randomly select a neighbor worker and average the local model with the neighbor model until all the neighbors are included, i.e., Algorithm 3 Non-blocking Synchronous Centralized algorithm 1: Initialization: initialize local models {x i 0 } P i=1 and the model in parameter server x ps 0 with the same initialization, learning rate η, batch size B, weight matrix W , and the total number of iterations K. Split the original dataset into P equal-sized subsets ξ 1 , . . . , ξ P . Assign subset ξ i to i-th worker. Shuffle local subset after each epoch. 2: for k=0, 1, 2, ... K-1 ≤ K do 3: Randomly sample ξ k,i from local subset in the i-th worker and divide the sample batch ξ k,i into N minibatches ξ k,i,1 , ..., ξ k,i,N . Update the parameter server by fetching gradient from workers: • Shuffling: Since stragglers will abandon unfinished mini-batches, shuffling the data guarantee all the data be well-trained. Without shuffling, the performance of the model will be worse. In Figure 2 we illustrate the importance of shuffling. The dataset cannot be fully trained without shuffling.
Note that the Non-blocking idea can also be implemented on synchronous centralized SGD. In algorithm 3 we present the pseudo-code of Non-blocking synchronous centralized D-PSGD.

THEORETICAL PERFORMANCE ANALYSIS
In this section, we analyze the complexity and efficiency of the Non-blocking SGD and compare it with the majority of state-of-the-art decentralized SGD algorithms which have synchronization steps. Both D-PSGD and MATCHA are included in the comparisons. In the following subsection, different analyses will be included: in the first part, we discuss the theoretical run-time per iteration. In the second part, we discuss the expected computational efficiency/throughput efficiency. In the third part, we discuss the expected run-time per epoch. All the following runtime analyses consider exponential random straggler delays same as previous works (Dutta et al., 2018;Lee et al., 2017;Mitliagkas et al., 2016;Hannah & Yin, 2017).

Definition and Notations
• D denotes the dataset size • B denotes the batch size, b denotes the mini-batch size • X 1:P denotes the first order statistic of P i.i.d. random variable X 1 , X 2 , ..., X P .
• X K:P denotes the K th statistic of P i.i.d. random variables X 1 , X 2 , ..., X P • Y denotes a random variable and Y = P i=1 1 X i:P • X k,i:P denotes the i th order statistic of P in k th iteration. i.i.d. random variable X 1 , X 2 , ..., X P • λ denotes the exponential distribution parameter. We assume the wall clock time of each learner to process a single mini-batch be i.i.d. exponential random variables X 1 , ..., X i , .., X P ∼ exp(λ) • For epoch level analysis, a (pseudo) epoch for Nonblocking SGD is the time to complete D/(P * B) iterations. Note that the amount of data processed in an epoch of Non-blocking SGD may be less than D as some (slow) learners are abandoning mini-batches in each iteration.

Theoretical Run-time Analysis
Lemma 1 The expected run-time per iteration for Nonblock SGD is, To proof of Lemma 1, We assume that the P learners have an i.i.d. computation times. When all the learners start together, and we wait for the first learner among P i.i.d. random variables to finish, the expected computation time for that iteration is E[X 1:P ]. As for a total number of J iterations, the expected run-time is given by JE[X 1:P ]. The run-time of fully-synchronous SGD is The run-time of asynchronous SGD is E[T ] = E[X 1:P ], which is the same as Non-blocking synchronous SGD (Dutta et al., 2018).
Then, we compare the theoretical wall clock runtime of the Non-blocking decentralized SGD and D-PSGD/MATCHA to illustrate the speed-up offered by our algorithm. Theorem 1.Let the wall clock time of each learner to process a single mini-batch be i.i.d. random variables X 1 , X 2 , ..., X P . For the Non-blocking algorithm, the original batch will be split into N mini-batches for each learner.
Then the ratio of the expected run-times per iteration for Non-blocking decentralized SGD and D-PSGD/MATCHA is Theorem 2.Let the wall clock time of each learner to process a single mini-batch be i.i.d. exponential random variables X 1 , ..., X i , .., X P ∼ exp(λ). X 1 is the time of the fastest learner. For the Non-blocking algorithm, the original batch will be split into N mini-batches for each learner. The expected run-time per iteration for Non-blocking synchronous SGD and D-PSGD/MATCHA is, The full proof is provided in Appendix A. The ratio of wall-clock run-time per epoch for Non-blocking SGD and D-PSGD is the same as the ratio of the expected run times per iteration in Theorem 1. The wall-clock runtime per epoch is When the run-time of each worker is under exponential distribution assumption, the run-time per epoch of Nonblocking SGD and D-PSGD/MATCHA are: We assume that in the last batch of an epoch, each worker will be assigned B amount of data as the original batch size.

Expected Computational Efficiency Analysis
Theorem 3.Throughput of Non-blocking SGD is Proof: The throughput of the distributed deep learning system is summing up the throughput of all the learners. The throughput of learner i is B X i:P . We assume that during an iteration, each worker processes the data at a constant speed within an iteration. We then have the following: Corollary 1 The total amount of data being trained in each iteration is, We assume the amount of data to be a fractional value. Theorem 4.Throughput of D-PSGD/MATCHA is T hroughput DP SGD = P * B X P :P (17) Theorem 5. The ratio of the throughput for Non-blocking SGD and D-PSGD/MATCHA is P i=1 B X i:P P * B * X P :P == Y * X P :P P (18)

ERROR CONVERGENCE ANALYSIS
To prove the Error Convergence of Non-blocking idea, two demonstrations are included in the following. In the first part, we will prove that the accumulated gradient of minibatches is equal to the gradient of a large batch. In the second part, we will demonstrate that the average model after being updated on the accumulated gradient has no difference from the original convergence.

Gradient Accumulation
The gradient accumulation and the local update based on the accumulated gradient are: η denotes the learning rate set for the original large batch, N denotes the number of mini-batches, n k,i denotes the number of finished mini-batches and x k,i denotes the local model in k-th iteration and i-th node. Randomly sample ξ k,i from local data ξ i and divide the sample batch ξ k,i into N mini-batches ξ k,i,1 , ..., ξ k,i,j , ..., ξ k,i,N . When n k,i = N , Equation 20 is: The gradient on a large batch is: we can prove that the update based on an accumulated gradient of multiple mini-batches is equal to the update based on a gradient of a joint dataset of all finished mini-batches. There is only one local update before synchronization. This is the precondition for the convergence analysis in the next step.

Convergence rate analysis
As for centralized synchronous distributed SGD algorithms, they gather all gradients on the parameter server(PS) and update the model on PS. Since the Non-blocking idea doesn't allow multiple local updates, the convergence of Non-blocking centralized SGD is guaranteed. As for decentralized algorithms, we will prove the convergence analysis based on Non-blocking DPSGD. Note that this convergence analysis is a general one and can also be applied to Nonblocking MATCHA. The analysis is centered around the following assumptions: Assumption 1: Each worker's local objective function F i (x)is differentiable and its gradient is L-Lipschitz:||∇F i (x) − ∇F i (y)|| ≤ L||x − y||, ∀i ∈ {1, 2, ..., P } Assumption 2: The deviation of averaged local objectives' gradients are bounded by a non-negative constant: 1 The variance of stochastic gradients E{||g i (x (k) ; ξ (k) ) − ∇F i (x (k) )||} at any worker node is bounded for ξ from the distribution D i . This implies there exist constants σ, ψ such that ∀x i ∈ {x 1 , ..., Larger batch size in local worker will lead to tighter bound. In this case, we assume ψ=0.  Assumption 4: Stochastic gradients at each worker node are unbiased estimates of the true gradient of the local objectives: , 2, . . . , P }. F k denotes the sigma algebra generated by noise in the stochastic gradients in iteration k.

Theorem 6: (Convergence of Non-blocking D-PSGD):
Our convergence analysis is under Assumptions of 1 to 4. In Nonblocking DPSGD, the learning rate is adjusted according to the finished mini-batches. Assume the learning rates in different workers are 1 2 { 1 2L+ρ √ K/n } 3 ≤ η 1 L, η 2 L, . . . , η P L ≤ 1 2L+ρ √ K/n 3 and the fastest worker is at most one time faster than the slowest one. Then we have the following convergence rate for Nonblocking DPSGD: Note that to simplify the formula we set When iteration K sufficient large enough, we can simplify the convergence rate of Nonblocking DPSGD to: This suggest that the convergence rate for Nonblocking D-PSGD is bounded byO( 1 K + 1 √ P K ). In addition, when iteration K is large enough, the convergence rate can be dominated by 1 √ P K and achieve linear speedup O( 1 √ P K ).

Experimental Setting
Datasets and models: The performance of all algorithms is evaluated in multiple deep learning tasks including image classification on CIFAR-10 and CIFAR-100 (Krizhevsky et al., 2009). All training datasets are evenly partitioned over a network of workers (each client has all classes and the number of samples per classes are the same across all the clients).
Compared algorithms: We implement the proposed Nonblocking SGD on the state-of-the-art algorithms D-PSGD and MATCHA with a communication budget c b = 0.5. MATCHA allows the system designer to set a flexible communication budget c b , which represents the average frequency of communication over the links in the network. When c b = 1, MATCHA reduces to vanilla decentralized SGD. When we set c b < 1 , MATCHA carefully reduces the communication frequency of each link, depending upon its importance in maintaining the overall connectivity of the graph. In addition, MATCHA assign probability to connections between workers so they may become active in some iterations. By using this disjoint links, MATCHA reduces the communication but maintains the degree. The Non-blocking D-PSGD (Algorithm 2) and Non-blocking MATCHA are compared with their baseline.
Machines/Clusters: All the implementations are compiled with PyTorch and OpenMPI within mpi4py. We conduct experiments on a HPC cluster with 100Gbit/s infini-band network. In all of our experiments, we use rtx8000 GPU as a node. To simulate the heterogeneous environment, we randomly slow down some of the nodes. The slowdown nodes and the rate of the slowdown are different in each iteration to simulate the real-world situation. The slowest node takes twice as long as the fastest node to finish a single batch. The slowdown is implemented using the sleep function.
Implementations: All algorithms are trained for a sufficiently long time until convergence or onset of over-fitting. The learning rate is fine-tuned for the D-PSGD baseline and then used for all other algorithms. Learning rate decay is adjusted according to the number of finished mini-batches in the experiment. We set the initial learning rate as 0.8 and it decays by 10 after 100 and 150 epochs. The batch size per worker node is 64. The batch size of baseline and the mini-batch size of Non-blocking algorithm are the same.

Result Analysis
The base topology of D-PSGD and MATCHA is shown in Figure 1(a). In Figure 3 we present the comparison of performance on the CIFAR-10 dataset and in Figure 4 we present the performance on CIFAR-100 dataset.
End-to-end performance: We first validate that, under certain network configurations, Non-blocking D-PSGD and Non-blocking MATCHA converge in similar numer of epochs, to a solution that is of similar quality as centralized SGD in a heterogeneous environment. Table 1, Figure 3 (a, d), and 4 (a, d) illustrate that the final test accuracy of Non-blocking algorithms is similar (or even better) than the two baselines, D-PSGD and MATCHA.

Dataset
Algorithms . In a heterogeneous environment where the fastest learner runs two times faster than the slowest straggler, the Non-blocking SGD takes up to 2x fewer times to reach the same final training loss.

Conclusion
This paper proposes a Non-blocking stochastic gradient descent algorithm (Non-blocking SGD) to deal with the stragglers' problem. The algorithm is robust in heterogeneous environments by allowing GPUs to process different amounts of data in a single batch and minimizing the delays in waiting for the slowest learner. The Non-blocking algorithm is extendable to most of the-state-of-the-art baselines and any other distributed computation algorithm that requires frequent synchronizations. It is also theoretically justified to have the same convergence rate as its baseline and can achieve linear speedup w.r.t. E[X P :P ] E[X 1:P ] . Experiments using different baselines validate the proposed algorithm.

EXPONENTIAL DISTRIBUTION ASSUMPTION
Proof of Theorem 2.2 The wall clock time of each learner to process a single mini-batch be i.i.d. exponential random variables X 1 , X 2 , ., X i , .., X P ∼ exp(λ). The expected maximum number of P learners under exponential distribution is E(T Sync ) = max {X 1 , X 2 , ..., X P }.