# Pipelined Stochastic Gradient Descent with Taylor Expansion
## 2 Problem Definition and Related Work  
Instead of performing SGD for each training instance, we can organize multiple training instances into groups called mini-batches and perform SGD for each mini-batch, which is called mini-batch SGD. This can increase the training speed because the data in a mini-batch can be processed in parallel using GPUs. This mini-batch SGD is a DNN training method that is widely used at present. In this paper, SGD refers to mini-batch SGD. SGD updates the model parameters gradually by calculating the gradient of the loss function and moving to the opposite direction of the gradient as follows:  
\[W^{t+1}=W^{t}-\eta\
abla\mathcal{L}(W^{t};x^{t},y^{t}), \tag{1}\]  
where \(W\) is the weight (i.e., model parameters) of a DNN model, \(\eta\) is the learning rate, \(\mathcal{L}\) is the loss function, \(x\) is the input data, \(y\) is the target value, and \(t\) is the time index (i.e., index of a training instance or mini-batch). It is difficult to parallelize this type of SGD that performs computations sequentially and repeatedly. Therefore, the accuracies of SGD-based pipelined parallel training algorithms are lower than those of the original sequential SGD algorithm. Pipelined SGD typically groups the layers of a DNN model into as many stages as the number of computing nodes and distributes the stages to the computing nodes (Figure 1). After the forward pass of the \(t\)-th mini-batch is completed at the layers in the \(n\)-th computing node, the \((n+1)\)-th computing node proceeds with the next forward pass of the \(t\)-th mini-batch. At the same time, the \(n\)-th computing node simultaneously executes the forward pass of the \((t+1)\)-th mini-batch. Similarly, all computing nodes simultaneously perform computations for different mini-batches in the backward pass as well. Therefore, pipelined SGD is suitable for large-scale DNN training because it uses all computing nodes without idle time and reduces the burden on each computing node, in terms of memory use, by dispersing the DNN model parameters. However, when a backward pass is executed at a computing node in naive pipelined SGD, the forward pass values and the model parameters required for the backward pass computation have been changed already by a different mini-batch, causing the _weight inconsistency_ problem (i.e., the model parameters used during the forward and backward passes are different). For example, the model parameters used in the forward pass of the second mini-batch in the third computing node (denoted as \(F_{3}^{2}\) in Figure 1) and the resulting forward pass values are changed in the process of \(F_{3}^{3}\) (the forward pass of the third mini-batch), \(B_{3}^{1}\) (the backward pass of the first mini-batch), and \(F_{3}^{4}\) (the forward pass of the fourth mini-batch). Hence, an incorrect forward pass values and stale weights are used for \(B_{3}^{2}\), which is the backward pass of the second mini-batch in the third computing node, causing the delayed gradient problem in the naive pipeline parallelism. Previous works on pipelined SGD used the terms delayed gradient and weight inconsistency interchangeably. In this work, delayed gradient refers to the late-arriving gradients as in the ASGD algorithm, and weight inconsistency refers to the phenomenon that occurs in the naive pipeline parallelism, which is the cause of the delayed gradients. Various approaches have been studied to solve the delayed gradient problem in pipelined SGD and improve the accuracies. In this section, the approximation methods analyzed in [17] are briefly described. Decoupled parallel backpropagation using delayed gradient [18] executes the forward pass sequentially and uses the pipelining only for the backward pass. Though forward passes are executed correctly, since backward passes proceed simultaneously in a pipeline manner, the weight inconsistency problem persists. Also, there is a limit to improving the parallelization performance because the higher the number of computing nodes, the larger the effect of delayed gradients.