{'fraction_non_alphanumeric': 0.03571339220935178, 'fraction_numerical': 0.012434014660628956, 'mean_word_length': 4.801799840336744, 'pattern_counts': {'":': 0, '<': 4, '<?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': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Large-Scale Deep Learning Optimizations: A Comprehensive Survey

Deep learning have achieved promising results on a wide spectrum of AI applications. Larger datasets and models consistently yield better performance. However, we generally spend longer training time on more computation and communication. In this survey, we aim to provide a clear sketch about the optimizations for large-scale deep learning with regard to the model accuracy and model efficiency. We investigate algorithms that are most commonly used for optimizing, elaborate the debatable topic of generalization gap arises in large-batch training, and review the SOTA strategies in addressing the communication overhead and reducing the memory footprints.


INTRODUCTION
Nowadays, deep learning (DL) have achieved promising results on a wide spectrum of AI application domains ranging from computer vision (e.g., image classification [42,47,66], object detection and segmentation [35,41,65,85]), natural language processing (e.g., language modeling [28,117] and machine translation [108,114]), information retrieval (e.g., recommendation system [43]) and many others. The scale is the main driver behind the rise of DL [28,42,55,56,94,104]. Larger datasets and neural networks consistently yield better performance across all tasks that generally require more computation and longer training time. Therefore, recent years have witnessed a surge of interests from both academia and industry in scaling up DL with distributed training on a large cluster of devices such as TPUs and GPUs with higher computation capability and memory limit. Data parallelism has become a dominant practice for distributed training. It distributes a large batch to multiple devices, where each device holds an identical model replica, computes the gradient of a local batch and finally gathers the gradients at each iteration for synchronous parameter update. With recent optimization techniques, it is now able to train very large batches on thousands of GPU devices. However, training at such scales requires overcoming both algorithmic and systemsrelated challenges. One of the main challenges is the degradation of model accuracy with large batch size beyond a certain point (e.g., 32k). Naively increasing the batch size typically results in degradation of generalization performance and reduces computational benefits. Additionally, we can not always improve the training speed by just using more processors as the communication cost is a non-negligible overhead. Intuitively multiple processors collaboratively training one task can reduce the overall training time, but the corresponding communication cost between processors is heavy and limits the model scalibility. Worse still, models with tens of billions to trillions of parameters clearly do not fit into memory of a single device, and simply adding more devices will not help scale the training. This limitation prevents DL researchers from exploring more advanced model architectures. Existing works investigate and develop optimization techniques to overcome these problems so as to accelerate training large-scale deep neural networks (DNNs). We categorise these works into two categories, one endeavors to maintain/improve the model accuracy in the large-scale setting and the other emphasises on the model efficiency, designing algorithms that are less hungry for communication and memory. Importantly, they are not mutually exclusive but can be used collaboratively to further speed up the training.

Related Surveys
Pouyanfar et al. [79] give an overview of DL from different perspectives, including history, challenges, opportunities, algorithms, frameworks, applications, and parallel and distributed computing techniques. Wang et al. [110] provide a quick survey on large-scale distributed deep learning systems, which concisely introduces parallelisms, parameter server architectures, synchronization schemes, related applications, and platforms. While some other surveys focus on a certain scope in deep learning: communication-efficiency in large-scale parallelism systems [14,106], parallelization strategies [12] and numerical optimization algorithms [11,19,87,101]. Large-scale DL represents a distinctive setting in which the accuracy, computation, communication and memory are closely connected and mutually restricted. However, existing surveys either merely concern part of them or do not address optimizations in the context of large-scale DL. Different from the two surveys [79,110] that are mostly related to ours, we focus more on the design of the algorithm rather than the system architecture. The novelty of this paper is its emphasises on both model accuracy and model efficiency, which captures critical aspects of large-scale deep learning training by presenting a review of the state-of-the-art (SOTA) optimization techniques and illustrating the trade-off in between.

Structure of the Survey
The overall structure of this survey is presented in Figure 1. Section 2 presents the formulation of a typical neural network optimization problem for supervised learning. We roughly divide the large-scale DL optimization into two components: model accuracy and model efficiency. Section 3 introduces the gradient descent optimization family, including gradient descent variants, momentum SGD and adaptive gradient algorithms. As large batch training with data parallelism has increasing popularity in DL and meanwhile introduces challenges, Section 4 discusses problems in this setting, and reviews main SOTA optimization strategies to improve the situation. Section 5 dives into the generalization gap -a debating topic in large batch training. Section 6 introduces secondorder optimizations. Then we turn our attention to model efficiency. Section 7 investigates the communication bottleneck and Section 8 focuses on memory-efficient techniques. Finally, Section 9 concludes this article.

PRELIMINARIES
Following many machine learning applications [18,19,116], we consider a space of input-output pairs ( , ) ∈ × has a probability distribution ( , ). The conditional distribution ( | ) represents the true relationship between inputs and outputs. The discrepancy between the predicted outputˆand the real output is measured by a smooth but possibly non-convex loss function (ˆ, ). The objective is to minimize the expected risk that is, Since P is an unknown distribution, in practice, one seeks the solution of a problem that involves an estimate of the empirical risk [91] The goal of solving Eq. [3] is to obtain a solution with small generalization error, i.e., high predictive accuracy on unseen data.

GRADIENT DESCENT OPTIMIZATION ALGORITHMS
Training a DNN is an optimization process, i.e., finding the parameters in the network that minimize the loss function. Gradient descent and its variant algorithms are the most popular algorithms to optimize neural networks (NNs) [87]. In order to control the oscillation of gradient descent methods, the idea of using momentum is introduced. Moreover, adapting the learning rate w.r.t. the gradient of the previous stages is found beneficial to avoid the fluctuation. In this section, we briefly sort out the mainstream optimization algorithms, consisting of gradient descent variants (Section 3.1), momentum (Section 3.2) and adaptive gradient algorithms (Section 3.3).

Gradient Descent Variants
Gradient descent and its variants dominate the optimization algorithms of DL. The gradient descent (GD) methods aim to minimize the empirical risk of a model by repeatedly computing the gradient of a loss function on a single training sample, or a (full) batch of samples, and continuously updating the model parameters accordingly by following the gradient of the objective function in the opposite direction. There are three variants in gradient descent which differ in the number of samples used for each step (updating model parameters), resulting in different accuracy and learning time.
3.1.1 Batch Gradient Descent. Batch gradient descent, a.k.a. vanilla gradient descent, minimizes the loss function ( ) with the following form: Here is the weights of a network, is a labeled training set, | | is the number of samples in the training set, and ( , ) is the loss computed from sample ∈ and and its label . Typically is the sum of a classification loss (e.g., cross-entropy) and a regularization loss on . And then update the weights where is a learning rate (LR) which controls how large of a step to take in the opposite direction of the gradient. As we need to go through the whole training set to calculate the gradient for one update of weights, batch gradient descent can be very slow, especially for large datasets (which is very common in DL tasks). Batch gradient descent also does not allow updating model online, i.e., with new examples on-the-fly.

Stochastic Gradient Descent.
Unlike batch gradient descent (GD), which calculates the gradients using the all training samples, Stochastic Gradient Descent (SGD) performs one weights update for each training sample = − ∇ ( , ).
Therefore, SGD addresses the computational bottleneck of batch gradient descent. It is significantly faster than batch gradient descent and can be used online. The drawback is that the gradient computed from just one sample is not representative enough for the whole training set. Consequently, the variance of gradients leads to a fierce fluctuation in the loss function.

Mini-batch Stochastic Gradient Descent.
Mini-batch SGD takes both advantages of batch GD and SGD by performing weights update for each mini-batch In batch GD, the gradients are computed over the entire dataset, providing an accurate estimation of the true gradient. It takes lots of time and memory to do that. But the real handicap is the batch gradient trajectory lands in a bad spot. While in SGD, parameters are updated by adding the gradient computed on a single sample of the dataset, which is very noisy and may go off in a direction far from the batch gradient. However, the noisiness is exactly what we want in non-convex optimization, because it helps to escape from saddle points or local minima [34]. The disadvantage is its terribly inefficiency of looping over the entire dataset many times to find a good solution. The mini-batch methodology is a compromise that injects enough noise to each gradient update, while achieving a relative speedy convergence. Mini-batch SGD is found to be very effective in the case of large-scale learning [18].

Momentum
SGD has trouble navigating a long and narrow valley in the loss function surface, i.e., the direction of the gradient is almost perpendicular to the long axis of the valley. In such a situation, the system oscillates back and forth in the direction of the short axis, and only moves very slowly along the long axis of the valley.

Momentum SGD.
Momentum [80] is a strategy that helps to counteract the oscillation along the short axis meanwhile accumulate contributions along the long axis. In other words, the momentum strengthens for dimensions whose gradients point in the same directions and dampens updates for dimensions whose gradients change directions. This allows Momentum to minimize the training loss in fewer steps than full batch gradient descent [76]. Specifically, momentum SGD adds update in previous step to the current update, and determines the next update as a linear combination of the gradient and the previous update −1 : 3.2.2 Nesterov Accelerated Gradient. In Eq. [8], we know that we are going to move by at least −1 and a bit more by ∇ ( ). And in Nesterov Accelerated Gradient (NAG) [74], it looks ahead by calculating the gradient at the partially updated value of ( − −1 ) instead of using the current value: Such "look before you leap" prevents us from going too fast and results in increased responsiveness. While the optimization path taken by classical momentum SGD exhibits large oscillations along the high-curvature vertical direction, NAG is able to avoid these oscillations almost entirely [102].

Adaptive Gradient Algorithms
The methods mentioned above apply a same LR to all dimensions of the parameters. Since each dimension of parameters relates to the loss function in different ways, a per-dimension LR is more advantageous due to the more accurate and precise control on the step size. Therefore, a variety of adaptive gradient-based methods have been proposed where gradients are divided by the component-wise accumulation of previous gradients. For example, AdaGrad [32] uses the sum of the squares of all past gradients, whereas Adadelta [122], RMSProp [107] and Adam [53] use an exponentially decaying average.
3.3.1 AdaGrad. Previously, we perform updates for all parameters using a same LR, regardless of their frequency and magnitude. This may lead to a failure in capturing the knowledge of infrequently occurring updates (which are highly informative and discriminative). AdaGrad [32] alleviates this problem by performing larger updates for infrequent parameters and smaller updates for frequent parameters, which enables it to do well with sparse gradients = =1 is a diagonal matrix where each diagonal element , is the sum of the squares of all past gradient w.r.t. up to time step . And is a smoothing term to avoid division by zero. A vectorized implementation has the following form: where ⊙ is an element-wise matrix-vector multiplication. In AdaGrad, each dimension has its own dynamic LR rate which is inversely dependent to the gradient magnitude, thus larger gradients have smaller LRs and small gradients have larger LRs. This is very beneficial for training DNNs since the scale of gradients in each layer is often different by several orders of magnitude. In addition, this accumulation of gradients can be regarded as a kind of simulated annealing which reduces the LRs along the course of training. Most implementation set the LR to a default value of 0.01, eliminating the need of manual tuning. However, AdaGrad holds a main drawback with the accumulation of squares of all past gradients, which keeps growing during the course of training. As the LRs radically shrink and vanish, the algorithm no longer gain additional knowledge.
3.3.2 Adadelta. Adadelta [122] is an extension of AdaGrad [32] that seeks to tackle its monotonically decreasing LRs. Instead of accumulating the sum of all previous squared gradients, Adadelta uses an exponentially decaying average instead. The running average [ 2 ] at time step depends on the previous average and the current gradient where is a decay constant similar to that used in the momentum method. As the denominator is the root mean squared (RMS) error criterion of the gradient, we can replace it with the criterion short-hand: 5 Noticing the mismatch of units in Eq. [13], i.e., the units of the update Δ do not match the units of the parameters which it applies to Zeiler [122] rearranges second order method (i.e., Newton's method) Since Δ for the current time step in unknown, assuming the curvature is locally smooth, Δ can be approximated by computing the exponentially decaying RMS of previous Δ

RMSProp.
RMSprop [107] was developed independently around the same time with Adadelta to solve the problem of AdaGrad's drastically decreasing gradients. AdaGrad treats all past gradients equally, which is counter to our intuition that fresh gradient is more informative than the elder one. RMSProp redefines by decaying the past gradients at an exponential rate = 0.9 −1 + 0.1 2 3.3.4 Adam. Adam [53] is one of the most popular optimizers for training DNNs nowadays. It computes individual LRs for different parameters base on the estimates of first and second moments of the gradients. In particular, Adam stores an exponentially moving average of past gradients ( ) and squared gradients ( ). The former is an estimate of the first momentum (the mean) and the latter is an estimate of the second momentum (the uncentered variance) of the gradients 1 and 2 are hyper-parameters controlling the decaying rates of theses moving averages. Since the moving averages are initialed as 0's, the estimates of first and second moments are biased towards zero, especially in the beginning of training. Adam utilizes correction terms to counteract the initialization biasˆ= Then Adam applies the update rule Adam is found to be robust and well-suited to a wide range of non-convex optimization problems in the field of DL. There are several variants of Adam. AdaMax [53] is an extension to Adam that generalizes the approach to the infinite norm (max) and may result in a more effective optimization on some problems. Nesterov-accelerated Adaptive Moment Estimation (NAdam) [30] incorporates NAG into Adam. It shows better convergence speed in some cases. While these algorithms have been successfully employed in several practical applications, they may fail to converge to optimal Algorithm 1: Distributed Synchronous SGD on Node k.
Input: Dataset ,minibatch size per node, the number of nodes , optimization function SGD, init parameters = [0], · · · , [ ] for = 0, 1, · · · do ← 0; for = 1, · · · , do Sample data from ; solution even in convex setting, or even diverge in DL training. Reddi et al. [84] pinpoint the exponential moving average of past squared gradients as a reason for such failures. Recall that the introduction of the exponential average was well-motivated to tackle the key flaw of the Adagrad algorithm: it should prevent the LRs to become infinitesimally small as training progresses by limiting the reliance of the update on essentially only the past few gradients. However, this shortterm memory of the gradients can indeed cause significant convergence issues in other scenarios. To resolve this issue, the authors propose new variants of Adam -AMSGrad, which relies on long-term memory of past gradients. AMSGrad uses the maximum of past squared gradients rather than the exponential average to update the parameters. Liu et al. [64] argue that the root cause of the bad convergence problem suffered by Adam is that the adaptive LR has undesirably large variance in the early stage of model training, due to the limited amount of training samples being used. Thus, to reduce such variance, it is better to use smaller LRs in the first few epochs of training. The authors propose Rectified Adam (RAdam) to rectify the variance of the adaptive LR.
Choosing an optimizer is a crucial step when training DNNs since it is woven with the training speed and the final predictive performance. Despite the fact that adaptive optimization methods, including AdaGrad, RMSProp, AdaDelat and Adam, are becoming increasingly popular, to date, how to choose an optimal one is still theoretically elusive and intractable. Instead practitioners rely on empirical studies [113] and bench-marking [88]. Wilson et al. [113] observed that the solutions found by adaptive methods generalize worse (often significantly worse) than SGD, even when these solutions have better training performance. However, Choi et al. [25] suggest that popular adaptive gradient methods never under-perform momentum or gradient descent. They point out the comparisons among optimizers are sensitive to the hyper-parameter tuning protocols.

LARGE BATCH TRAINING
Large DNNs and large datasets have fueled the development of deep learning [28,42,55,56,94,104]. However, training large models on massive datasets is compute-intensive. For instance, training the SOTA DL models like BERT and ResNet-50 takes 3 days on 16 TPUv3 chips and 29 hours on 8 Tesla P100 gpus respectively [28,42]. An intuitive way to accelerate training is to add more computational power (e.g., more GPU nodes) and use data parallel (see Alg.1). Considering communication (i.e., synchronizing the updates at each iteration) is an issue, each GPU must be utilized as much as possible to amortize the communication cost. Therefore, large batch should be used to distribute more data to each GPU. The nontrivial growth of batch size often results in test performance degradation, as observed in [45,52,54,61]. We describe the training difficulties introduced by large batch in Section 4.1, a recipe for large batch training (i.e., linear LR scaling with a warmup strategy) in Section 4.2, other supplementary strategies such as adaptive layer-wise learning in Section 4.3 and adaptive batch size in Section 4.4, and finally discuss the extent to which we can scale up the batch size in Section 4.5.

Large Batch Training Difficulties
Although large batches are preferable to increase the parallelism by distributing the workload to multiple nodes, they may slow down convergence rate in practice [20]. Empirically, an increase in mini-batch size after a certain point (e.g. 1024) without a careful optimization scheme typically decreases the rate of convergence. The test accuracy of the converged solution becomes significantly lower than the baseline [37,45,52,61]. In addition to a degradation of the test performance, Masters and Luschi [70] provide evidence that increasing the batch size also results in a progressively smaller range of LRs that allows stable training.
Keskar et al. [52] find a drop in generalization (often denoted as generalization gap) to be as high as 5% even for smaller networks, and correlate the generalization gap with the sharpness of the loss landscape. They argue that large-batch methods tend to converge to sharp minimizers of the training and testing functions, whereas small-batch methods consistently converge to flat minimizers. Hoffer et al. [45] deny the existence of inherent generalization gap and suggest that training longer will help the algorithm to generalize better and keep the accuracy higher. Goyal et al. [37] admit that large batches cause optimization difficulties, but when these are addressed the trained networks exhibit good generalization. They tried to bridge the generalization gap with heuristics of LR scaling [37] with a warpup strategy. However, empirical study [92] shows that LR scaling heuristics with the batch size do not hold across all problems or across all batch sizes. Later You et al. [120] proposed Layer-wise Adaptive Rate Scaling (LARS) to solve the large batch optimization difficulties. Several recent works successfully scaled the batch size to large values using adaptive learning rates without degrading the performance.

Learning Rate Scaling for Large Batch
A nice property of large batch is its lower variance of the gradient. This is because when we take the gradient over more examples, the variance is obviously lower. Consequently, large batch allows us to take a larger step per iteration. Followings are two commonly used LR heuristics: linear scaling and sqrt scaling, to guide us to adapt the LR for large batches.

Linear
Scaling. [19,37,54] suggest linearly scaling up LR with batch size, i.e., when the mini-batch size is multiplied by , multiply the LR by . Intuitively, after iterations of mini-batch SGD , we have while after one iteration of large mini-batch of size | | = | | we havê If we assume ∇ ( + ) ≈ ∇ ( ) for < , then the adjustmentˆ= would yieldˆ+ 1 ≈ + . Noted that this assumption holds with the premises: (1) cannot be infinite. That is, we cannot scale up the batch size without limits; (2) cannot be too small. Because at the beginning of training, the gradients change rapidly, and thus the difference between ∇ ( ) and ∇ ( + ) is no longer negligible. Using LR warmup and linear scaling, Goyal et al. [37] trained Resnet-50 with batch B=8K without loss in accuracy.

Sqrt Scaling.
Another scaling strategy is sqrt scaling, i.e., when the mini-batch size is multiplied by , multiply the LR by √ . In SGD, the co-variance matrix of the parameters update Δ is [45] A simple way to keep this co-variance constant when we change the batch size is to choose ∝ √︁ | |. Hoffer et al. [45] find that by using "Ghost Batch Normalization" and sqrt scaling, the generalization gap can be significantly decreased. However, the largest batch size used was 4,096, which does not rule out an effect appearing at still larger batch sizes, as suggested by the work of Goyal et al. [37]. Moreover, establishing this invariant co-variance remains poorly justified, and often sqrt scaling is found to degrade model quality in practice, see [37,48,54].

Warmup.
After adjusting the LR with these strategies, the main obstacle for scaling up batch size is the instability of training with high LR, especially in the initial epochs when the gradients change dramatically. This issue can be alleviated by a properly designed warmup strategy by using less aggressive LRs in the initial epochs.
Constant warmup. Verma et al. [109] use a low "safe" constant LR for the first few epochs of training and after that return to the target LRˆ= . Goyal et al. [37] find constant warmup particularly helpful for prototyping object detection and segmentation methods [35,41,85], but not sufficient enough to solve the large batch optimization problem. In particular, a transition out of the low LR warmup phase can cause the training error to spike. This motivates them to use a more moderate warmup stragegy -gradual warmup.
Gradual warmup. Unlike constant warmup, gradual warmup avoid a sudden increase of LR by gradually arising the LR from a small to a large value. We denote the LR of the -th iteration as ( ) and the maximum LR during training as . Given a predefined time frame , the LR scheduler for the -th iterations is defined as After this warmup stage, the LR will be set by classical LR schedulers (e.g., cosine decay). A LR warmup stage is proved to be beneficial when training NNs with extremely large batch size [37,121]. Liu et al. [64] claim that the benefit of the warmup stage comes from reducing the variance for the adaptive LR in the Adam optimizer. They further propose Rectified Adam (RAdam) by introducing a term to rectify the variance of the adaptive LR. Additionally, Xiong et al. [115] find the LR warm-up stage also helps quite a lot for other optimizers.

Adaptive Layerwise Learning
Linear/Sqrt LR scaling with warmup mitigates the vulnerability to the fluctuation of gradients in the initial epoch by taking less aggressive steps, starting from a small LR which is safe enough for all layers and gradually increasing it to the target value. Hoffer et al. [45] use less aggressive sqrt scaling with "Ghost Batch Normalization" to train Alexnet with = 8 , but still the accuracy (53.93%) was much worse than baseline (57.10%). Goyal et al. [37] use LR warmup and linear scaling to train Resnet-50 with batch B=8K without loss in accuracy. While these works demonstrate the feasibility of these strategies for reducing the wall time for training large DNNs, they are not general enough if we want further enlarge the batch size. For instance, You et al. [120] applied linear scaling and warmup scheme to train Alexnet with batch normalization on Imagenet, and observed a 2.2% drop when = 8 in the test accuracy. You et al. [120] explain their method to solve this problem: To analyze the training stability with large LRs we measured the ratio between the norm of the layer weights and norm of gradients update. We observed that if this ratio is too high, the training may become unstable. On the other hand, if the ratio is too small, then weights don't change fast enough. This ratio works like a hint about how to adapt the LR for each layer. In this section, we will first introduce a general adaptive layerwise strategy motivated by this ratio, followed by two specific algorithms, LARS [120] and LAMB [121].

General Layerwise Strategy.
Suppose we use an iterative base algorithm (e.g., SGD or Adam) in the small batch setting with the following layerwise update rule where is the update made by at time step . You et al. [121] propose the following two changes to the update for large batch settings: (1) The update is normalized to unit 2 -norm. This is ensured by modifying the update to the form /∥ ∥. Such a normalization is done layer-wise, i.e., the update for each layer is ensured to be unit 2 -norm.
(2) The LR is scaled by (∥ ∥) for some function : R + → R + . Similar to the normalization, such a scaling is done layer-wise. Suppose the base algorithm is SGD, then the modification results in the following update rule for all layers ∈ [ℎ]. The normalization modification ( ) /∥ ( ) ∥ is similar to one typically used in normalized gradient descent except that it is done layer-wise. Normalization of this form provides robustness to exploding/vanishing gradients (where the gradient can be arbitrarily large/small) by essentially ignoring the size of the gradient but preserving the direction. As for the scaling step, the scaling term involving ensures that the norm of the update is of the same order as that of the parameter. When the parameters are small, we take a small step and vice versa.
There are two notable differences between this general strategy and other adaptive algorithms such as Adam or RMSProp: (1) it uses a separate LR for each layer and not for each weight. (2) the magnitude of the update is controlled w.r.t the weight norm for better control of training speed. Both LARS [120] and LAMB [121] are based on this general strategy, using momentum and Adam optimizer as the base algorithm respectively.

LARS.
The first instantiation of the general strategy is the LARS algorithm [120], which is obtained by using momentum optimizer as the base algorithm in the framework. LARS stands for Layer-wise Adaptive Rate Scaling, which was proposed for large batch learning for ResNet on ImageNet. Specifically, a local LR is defined for each layer The hyper-parameter < 1 describes the extent to which we can trust the layer to update its weights during each epoch. At the beginning of training, the numerator ∥ ∥ 2 2 above is relatively small. In contrast, the denominator ∥∇ ( ) ∥ 2 2 is probably large since when everything is wrong, the loss and gradients are large. Any steps we take are likely to be small. In this way we naturally warm up as the weights increase. As we approach 0 loss, the gradients become smaller and the local LR increases again, encouraging jumping out of the local minima to prevent over-fitting. The parameter update is Algorithm 2: SGD with LARS. Example with weight decay, momentum and polynomial LR decay. Input: base LR 0 , momentum 1, weight decay , "trust" coefficient , number of steps Init: = 0; = 0. Init weight 0 for each layer while < for each layer do ← ∇ ( ) ; //obtain a stochastic gradient for the current mini-batch where is the global LR. In this way, each layer can learn at its own pace accurately. The training for SGD with LARS are summarized in the Algorithm 2.
Several works successfully scaled the batch size to large values using LARS without degrading the performance, thereby, finishing ResNet-50 training on ImageNet in a few minutes [118][119][120]. LARS also applies to tasks such as self-supervised image representation learning and contrastive learning of visual representations [24,38].

LAMB.
LAMB is the second instantiation of the general strategy, which is obtained by using Adam as the base algorithm . The pseudo-code is provided in Algorithm 3. The adaptivity of LAMB is two-fold: (1) per dimension normalization w.r.t the square root of the second moment used in Adam and (2) layer-wise normalization obtained due to layer-wise adaptivity. By using LAMB, You et al. [121] scale the batch size of BERT pre-training to 64K without losing accuracy, thereby, reducing the BERT training time from 3 days to around 76 minutes. LAMB is also the first large batch adaptive solver that can achieve the SOTA accuracy on ImageNet training with RESNET-50. LAMB has also been adopted by many other work [57].
Despite of the popularity of LARS and LAMB, their utility as a "large batch optimizer" is challenged by [73], which argues that they are more indirect regularizers than optimizers. By sophisticated tuning, traditional, generic algorithms (e.g., Momentum or Adam) achieve strong results across batch size. They appeal to researchers that the superiority of one particular optimizer over others should be claimed with extreme caution since the fair comparisons between optimizers crucially depend on the effort spent tuning hyperparameters for each optimizer.

Adaptive Batch Size
It is a common practice to decay the LR during training. When one decays the LR, one simultaneously decays the "noise scale", i.e., the scale of random fluctuations in the SGD dynamics [97] When we decay the LR, the "noise scale" falls, enabling us to converge to the minima of the loss function. We can achieve the same reduction in noise scale at constant LR by increasing the batch size. Smith et al. [96] and Devarakonda et al. [27] empirically demonstrated the equivalence between decaying LR and increasing the batch size. Instead of decaying the LR by a factor of , they increase Algorithm 3: LAMB //obtain a stochastic gradient for the current mini-batch end the batch size by during training. This strategy reaches equivalent test accuracy after the same number of training epochs, but with fewer parameter updates, leading to greater parallelism and shorter training times. Crucially, such strategy is complementary to existing training schedules requiring no hyper-parameter tuning.

Efficient Scaling
Increasing the batch size is one of the most appealing ways to accelerate NN training on data parallel hardware. Ideally, parallel mini-batch SGD can achieve a linear speed-up of the training time w.r.t. the number of workers compared with SGD over a single worker. However, such linear scalability in practice is significantly limited by the growing demand for gradient communication as more workers are involved. Moreover, when batch very large, the stochastic gradients become very close to true gradients, so increasing the batch does not give much additional gradient information comparing to smaller batches. A series of work has conducted comprehensive experiments on the relationship between batch size and training time for NNs [92,95,123]. Shallue et al. [92] experimentally measure the effects of data parallelism training across different families of NNs, training algorithms and data sets, finding no evidence that larger batch sizes degrade out-of-sample performance. They observed three distinct scaling regimes in the relationship between batch size and training time: a "perfect scaling" regime where doubling the batch size halves the number of training steps required to reach a target out-of-sample error, followed by a regime of "diminishing returns", and finally a "maximal data parallelism" regime where further increasing the batch size does not reduce training time, even assuming idealized hardware. They also provide experimental evidence that the critical batch size depends on the model architecture, the dataset and regulation technology.

GENERALIZATION GAP
Optimization in general is an extremely difficult task, especially for training NNs. With nonconvex and high-dimensional functions, it is possible to have many local minima and saddle points. Optimization methods, such as SGD, generally converge to different regions of parameter space, highly dependent on the design of network architecture, the choice of optimizer, variable initialization, and a variety of other considerations [92]. The term generalization refers to how well a hypothesis applies even to new examples that it hasn't seen in the training set. As mentioned in Section 4.1, it is observed that while yielding similar values of training functions, models trained with large-batch methods perform worse on test data compared to small-batch methods [45,52,70,92]. Such persistent degradation in generalization performance is referred to as the generalization gap.
Identifying the origin of this gap and finding ways to close it is of significant practical importance whereas remains an open problem.
This section is structured as follows. Section 5.1 introduces the concept of sharp and flat (wide) minima; Section 5.2 addresses the relationship between sharpness/flatness of local minima and their generalization ability; Section 5.3 provides explanation for the so-called generalization gap and Section 5.4 provides a somewhat opposing account.

Sharp and Flat (Wide) Minima
When training a DL model, we are seeking for a solution that minimizes a loss function on a given training set. This solution lies in a very high dimensional space (thousands, millions or even billions of parameters to learn) called parameter space. The landscape of parameter space is showed empirically crucial to generalize well. That being said, the wider the solution's local geometry, the better the generalization [22,52,59]. Figure 2 provides an intuitive explanation. There is generally a shift of the loss function in the parameter space, flat minima is more robust to the perturbation of parameter than the sharp one and thus generalizes better.
There are various definitions for "sharpness/flatness" of the landscape. Hochreiter and Schmidhuber [44] define "flatness" as a large connected region in weight space where the error remains approximately constant. Keskar et al. [52] characterize "flatness" by the magnitude of the eigenvalues of Hessian, and propose a computational feasible -sharpness measure. Dinh et al. [29] show that flat minima in practical DL hypothesis spaces can be turned into sharp minima via re-parameterization without affecting the generalization gap. Chaudhari et al. [22] exploit the local geometric properties of the objective function and use "local entropy" as a measure of "flatness", which is invariant to the simple re-parametrization in [29]. Foret et al. [33] capture the "sharpness" at parameter by measuring how quickly the training loss can be increased by moving from to a nearby parameter value.
Empirically, optimizers like SGD, Adam, etc. implicitly converge towards wide valleys solutions. But there is no guarantee that this will always be the case. This has motivated the creation of algorithms that will actively look for flat minima such as Entropy SGD [22], Sharpness-Aware Minimization (SAM) [33] and many others.

Generalization Gap and Sharp Minima
With regards to large batch training, Keskar et al. [52] observed that naively increasing the batch size typically results in degradation of generalization performance and reduces computational benefit. They speculate that "the lack of generalization ability is due to the fact that large-batch methods tend to converge to sharp minima of the training functions". Specifically, large-batch methods are more vulnerable to sharp minima whose training function increases rapidly in a relatively small neighborhood (see Fig. 2). Such kind of high susceptibility to training functions hampers the trained model from fitting on the test data. By contrast, small-batch methods can resist the attraction of these minima and converge to a flat minima whose training function varies slowly in a relatively large neighborhood. They contribute the success of small batch methods to their noisy gradients in the computation step. On one hand, the noise expels the iterations from the trap of sharp minima. On the other hand, the noise encourages them to move towards and retain in a flatter loss landscape. However, as a larger batch size depicts a more accurate gradient, their noise is no longer sufficient enough to eject the iterations from the basin of sharp minima.
It is widely thought that small-batch SGD produces "flat" minima that generalize well, while large batches converge to "sharp" minima with poor generalization [22,44,52]. However, there are some disputes about the effects of batch size on model's generalization ability. Hoffer et al. [45] deny the existence of inherent generalization gap and show empirically that the "generalization gap" stems from the relatively small number of updates rather than the batch size, and can be completely eliminated by adapting the number of weight updates. Goyal et al. [37] hold the view that optimization difficulty is the main issue with large mini-batches, rather than the poor generalization (at least on ImageNet). Specifically, using linear scaling and warmup strategy, they show no loss of accuracy when training with large mini-batch sizes up to 8,192 images on the ImageNet dataset.

Gradient Noise Ratio
As mentioned above, how batch size affects sharpness and generalization is controversial. Smith and Le [97] show that the test accuracy peaks at an optimal batch size, if one holds the other hyper-parameters constant. They believe that the arise of peak is not controlled by the batch size itself, but the underlying scale of random fluctuations in the SGD dynamics. Consider a simple model of SGD; the estimated gradient step is ∇ ( ) = | | ∈ ∇ ( ), which can be restated as the true gradient and a gradient noise term Smith and Le [97] analogy between SGD and stochastic differential equations (SDEs) to describe the noise in the SGD dynamics. In particular, they depicted Eq. [30] as the discrete update of a stochastic differential equation (SDE) and derive an analytical expression for the stochastic "noise scale" = ( − 1) ≈ , which controls the scale of random fluctuations in the SGD dynamics. Noise drives SGD away from sharp minima, and therefore there is an optimal batch size which maximizes the test accuracy. This optimal batch size is proportional to the LR and training set size ∝ . Therefore, they attribute the so-called "generalization gap" observed in [29] as a consequence of scaling batch size above this optimal batch size. Similarly, Jastrzębski et al. [48] derive a "stochastic noise" using a different SDE. They verify experimentally that the ratio of LR to batch size, / , influences the width of the minima found by SGD, and that higher values of the ratio lead to wider minima and often better generalization. Despite the slightly difference in the form of "stochastic noise", both [48,97] indicate that gradient noise can be beneficial, especially in non-convex optimization. Also they theoretically explain the empirical finding in [37,45] that rescaling the LR with the square root of the batch size and train for more epochs, or linearly with batch size, can reach the same generalization with a large batch size.

Train longer, Generalize Better
Another observation in [52] is that large batch methods are more likely to be attracted to minima close to the initial point, whereas small batch methods are more explorative and always locate minima that are farther away, with a ratio of ∥ * − 0 ∥ 2 /∥ * − 0 ∥ in the range of 3 to 10. Hoffer et al. [45] further find that the weight distance from initialization point increases logarithmically with the number of training iterations (weight updates), ∥ − 0 ∥ ∼ . They therefore deny the existence of inherent generalization gap and believe that "generalization gap" stems from the relatively small number of updates rather than the batch size. Specifically, they "stretched" the time-frame of the optimization process, where each time period of epochs in the original regime will be transformed to epochs according to the mini-batch size used. However, such modification anneals the speedup effect of large batch training.

SECOND ORDER OPTIMIZATION
Optimizations in DL, both theoretically and empirically, are presently dominated by first-order gradient methods [2,3,15,21,26,116]. Second-order optimization methods that involve second derivatives and/or second order statistics of the data, are far less prevalent despite strong theoretical properties, due to their prohibitive computation, memory and communication costs. In this section, we setup second-order optimization basics in Section 6.1, start from the classical Newton's method in Section 6.2, and turn to some up-to-date algorithms such as the Hessian-Free Method (in Section 6.3), K-FAC (in Section 6.4) and Shampoo [40] (in Section 6.5).

Second-Order Optimization Basics
Basically, many problems in machine learning can be simply described as minimizing the loss function over variables ∈ R ∈R ( ).
When training the weights of a NN, we are trying to get as far down the error surface as possible.
In most cases, we often use SGD to update the parameter vector to solve this optimization problem Another very popular family of algorithms used in practice are the adaptive optimization algorithms (e.g., AdaGrad [32], Adadelta [122], RMSProp [107], Adam [53], etc.). These are basically algorithms that update for each individual entry in the parameter vector. Each entry has its own step size which is an adaptive update using past gradients.
And there are also momentum variants of these methods that have slightly different update rules. Potentially more powerful family of algorithms are known as the preconditioned algorithms which use some matrices called preconditioners to transform the gradient before taking a step. In general, the idea of second-order optimization is to model the objective function by the local approximation Here, is a symmetric preconditioner and is the change in parameters. In Newton's method, = , or = + . Fully optimizing ( ) w.r.t. gives * = ( ) = − −1 ∇ , then apply the update +1 = + * . (36) This family includes algorithms mentioned above such as AdaGrad [32], Adam [53], where the preconditioners are diagonal. But they can be more powerful if the metrics are not diagonal but full preconditioners, for exapmle, full AdaGrad, Natural Gradient [7] and also classical algorithms like Newton's method, Quasi-Newton methods [36,89] and so on. It is well-known in optimization that preconditioning often leads to faster convergence or better "condition number" in many different scenarios. But it comes with obvious caveats: supposing the number of parameter is , we need (1) at least quadratic space Ω( 2 ) in the dimension to store the preconditioner. (2) 3 time to invert the preconditioner to apply to the gradient vector. Generally speaking, these second-order methods are not very practical where the cost of computation and memory is formidable in the DL settings. Alternatively practitioners use the diagonal approximation or using the SGD again.
Recently, there has been considerable advancement in the development of second-order methods, seeking a balance between between full matrics and the diagonal case. These methods usually approach preconditioners of the gradient in a modular way, which is as powerful (or nearly powerful) as the full matrix case, but can be used in practical like the diagonal case in terms of storage and run-time. Inspired by the idea of the natural gradient method [8], Martens and Grosse [69] use a Kronecker-factored approximation to the Fisher matrix as its preconditioning matrix that can be applied to multi-layer perceptrons (MLPs), which was subsequently extended to other architectures, such as convolutional neural networks (CNNs) [39] and recurrent neural networks (RNNs) [75]. Kronecker-factored preconditioners based on the structure of the Hessian and quasi-Newton methods have also been developed [36,86].

Newton's Method
Recall that in GD method, the gradient of a function is defined as the vector of partial derivatives.
It means we are assuming that the error surface of the NNs locally looks and behaves like a circle. And we are ignoring all curvatures of the surface, which may lead our training to progress very slowly. To rectify this, we can use information from the second derivative of a function. The idea of Newton's method is to apply a linear transformation that turns ellipses into circles. If we apply that transformation to the gradient vector, it will be as if we were going downhill in a circular error surface. Formally, Newton's method use the Hessian matrix as preconditioner The Hessian is a function of the parameters and we need to take its inverse and multiply the gradient by that. Then we need to go some distance in that direction If it is a truly quadratic surface and we choose the LR correctly, we will arrive at the minima of the surface in a single step. However, that single step involves something complicated which is inverting that Hessian matrix. Assuming that we only have a million parameters in our NN, the Hessian matrix will have a trillion terms which is completely infeasible to invert.
Curvature Matrices. Each element in the curvature matrix specifies how the gradient in one direction changes as we move in some other direction. The off-diagonal terms in a curvature matrix correspond to "twists" in the error surface. A twist means that when you travel in one direction, the gradient in another direction changes. If we have a nice circular bulb, all those off-diagonal terms are zero. As we travel in one direction, the gradient in other directions doesn't change. But when we have an elliptical error surface, as we travel in one direction, the gradient in another direction changes. This is actually what is going wrong with GD. As GD updates one of the weights, at the same time it is updating all the other weights, causing a change in the gradient for the first weight. That means when we update it we may actually make things worse. The gradient may have actually reversed sign due to the changes in all the other weights. And so the more weights we get, the more cautious about changing each one of them we need to be, because the simultaneous changes in all the other weights can change the gradient of a weight.
How to avoid inverting a huge matrix. The intensive computation of the curvature has limited the applications of second-order optimization methods in DL settings. To address this problem, there are various ideas in the literature. One very popular line of work looks at diagonal approximations, e.g., Adagrad [32], RMSProp [107], Adadelta [122] and many others [16,17]. But these diagonal terms consist only a tiny fraction of the interactions, so we are ignoring most of the terms (nearly all of them) in the curvature matrix. And the experimental evidence indicates that there is limited or almost no improvement in practice when compared to well-tuned SGD with or without momentum (see [17,122]). The benefits of these diagonal approaches seem to lie mainly in the ease of choosing the LR, but may not provide any fundamental benefits beyond that. Another thing we could do is to approximate the curvature matrix with much lower rank matrix but capturing its main aspects. Limited-memory BFGS (L-BFGS) [89] is the most well-known example. Again there is limited/non-existent empirical success for NN optimization.
More recently, many focus are put on the trade-off between the full matrix and the diagonal case, seeking a balance between these two extreme case. Some researchers find something in between that is as powerful (or nearly powerful) as the full matrix case, but can be used in practical like the diagonal case in terms of storage and run-time. Some recent approaches for approximating a full-matrix preconditioner are K-FAC [69] and Shampoo [40]. Others incorporate automatically the Hessian operator, such as Hessian-Free method [67] and trust-region [26,116].

Hessian-Free Method
The Hessian-Free method [67] is a quasi-Newton method that uses no low-rank approximations. Named "free" because it never explicitly computes the preconditioner but instead does approximate minimization of quadratic model ( ) (see Eq. [35]). The Hessian-Free (HF) method is motivated by two observations. The first one being that it is relatively easy to compute the matrix-vector product for an arbitrary vectors , e.g., use finite differences to approximate the limit.
The second motivating observation is that linear conjugate gradient (CG) minimizes positive definite quadratic cost functions using only matrix-vector products, which is relatively easy to obtained (as shown in Eq. [40]). Conjugate gradient is a very clever method that instead of trying to go straight to the minimum like in Newton's method, it tries to minimize in one direction at a time. It starts off by taking the direction of GD and goes to the minimum in that direction that might involve re-evaluating the gradient or re-evaluating the error a few times to find the minimum in that direction. Once it is done, CG method now finds another direction and goes to the minimum in that second direction. The clever thing about the technique is that it chooses the second direction in such a way that doesn't mess up the minimization it already did in the first direction, which is called a conjugate direction. "Conjugate" means that as we go in the new direction we do not change the gradients in the previous directions. What CG achieves is that it gets to the global minimum of an -dimensional quadratic surface in only steps. More importantly, in many less than steps on a typical quadratic surface, it will have reduced the error very close to the minimum value. And that's why we use it. As doing the full steps that would be as expensive as inverting the whole matrix, we are going to do many less than steps and get quite close to the minimum. Pseudo-code for a simple variant of damped HF optimization is provided in Algorithm 4.
However, common variants of HF don't work particular well for NNs. Enhancements techniques (e.g., the Gauss-Newton approximation to the Hessian, early CG stopping, damping, etc.) are provided in [67]. More recently research has revealed that DNN learning is easier than previously thought using simple methods [103]. Carefully tuned momentum methods suffice for dealing with the curvature issues in deep and recurrent network training objectives without the need for sophisticated second-order methods. Despite SGD with or without momentum still being the most widely used and best method in most situations, the fact that HF uses 100-1000x fewer iterations than SGD supports the idea that a second order method can help a lot in principle, provided that we can make these iterations cheap enough to compute.

K-FAC
Kronecker-Factored Approximate Curvature (K-FAC) [69] is one of the natural gradient approximation methods where the preconditioner is a high-quality approximation of Fisher information matrix (FIM). We first give a brief introduction about natural gradient descent and then explained the outline of K-FAC.
Here the inverse of the FIM is applied to the gradient of loss, and the gradient preconditioned by the FIM is called the natural gradient. For the parameters of size , the size of FIM is × , and NNs used in DL tend to have a massive number of parameters (e.g., 60 million parameters in AlexNet for ImageNet classification) so the inverse of the FIM is intractable, and it limits the number of the applications of NGD to DL. In recent years, some works have proposed methods that approximate or avoid inversing the FIM.
Next, each diagonal block matrix is approximated as a Kronecker product This is called Kronecker factorization and , −1 are called Kronecker factors, representing the gradient of the output of the -th layer and the activation of the ( -1)-th layer respectively. By using the critical property of the Kronecker product of the matrices ( ⊗ ) −1 = −1 ⊗ −1 , the inverse ofˆcan be computed asˆ− The final update step of parameters in the -th layer is as follows: In most implementations, Tikhonov regularization is used to avoid ill-conditioned matrix inverses with K-FAC by adding a damping parameter to the diagonal ofˆ [39,78] (ˆ+ ) −1 = ( −1 + ) −1 ⊗ ( + ) −1 .
A standard K-FAC update step for one layer requires inverting two matrices ( −1 + ) and ( + ), which can be computed implicitly using an alternative method based on the eigendecompostion of [39,78].
In practice, practitioners avoid significant computation and communication by reducing the frequency of computing these factors and and their eigendecompositions, at the cost of introducing staled information. For example, Pauloski et al. [78] update K-FAC statistics for every 500 iterations for ResNet scaling experiments on 64 GPUs.

Distributed K-FAC.
Some studies have used K-FAC and implemented the algorithm in a distributed computing environment [75,78]. With only 35 epochs and a 16K batch size, ResNet50 can be trained to achieve 75% Top1 accuracy in ImageNet [75]. More recently, Pauloski et al. [78] scales up K-FAC for training CNNs. It mainly refers to the calculation scheme of preconditioned gradient in [39] and uses feature decomposition to replace matrix inversion.

Shampoo
Shampoo [40] is another preconditioning algorithm, which is an approximation version of full matrix AdaGrad [32]. It first approximates by treating each layer independently (block diagonal).
And it uses small matrices whose Kronecker product approximates the full AdaGrad statistics. Such two approximations make Shampoo more expressive than the diagonal preconditioning and practical to store and compute at large scale. Mathematically, the preconditioner Shampoo looking for can be written as a Kronecker product of two smaller matrices and Though it cannot solve the exact optimization problem, it has a nice limit that relaxes the upper bounds in a matrix sense: The full AdaGrad peconditioner is given on the left, bounded by a Kronecker product of two smaller matrices. The update statistic of Shampoo is given as follows: Both Shampoo and K-FAC employ a preconditioning scheme that approximates the FIM. Despite their similarity in construction, they differ in several important ways. The differences are based on choices such as the empirical FIM or FIM, moving average or sum, and the inverse component.
Another key difference is that Shampoo construction is agnostic to layer types. K-FAC relies heavily on the structure of the back-propagated gradients in a feed-forward neural network. In contrast, Shampoo is virtually oblivious to the particular model structures and only depends on standard gradient information. More recently, Anil et al. [9] extend Shampoo in a number of ways so as to make it applicable to a larger range of deep architectures.
Despite the fact that first-order methods have been dominant in the recent decade, recently second order methods, such as K-FAC and Shampoo, show some promise. They mitigate the space and run-time costs of full-matrix second-order algorithms and have been applicable to a larger range of deep architectures (see Table 1). It is interesting to see whether second order methods can outperform first order ones in the future.

COMMUNICATION
Large-scale distributed training improves the productivity of training deeper and larger models, where data parallelism is adopted so as to take full advantage of the compute capability on multiple workers. SGD is usually selected as the optimization method because of its high computation efficiency and well support by the DL tool-kits, such as TensorFlow [1], PyTorch [77] and Deep-Speed [83]. In data-parallel SGD, each worker processes a random mini-batch of its training data, and then the local updates are synchronized by making an All-Reduce step or through a centralized parameter server, which aggregates stochastic gradients from all workers, and taking a Broadcast step that transmits the updated parameter vector back to all workers. The process of gradient synchronization is repeated until an appropriate convergence criterion is met.
Increasing the number of workers and taking advantage of data parallelism help to reduce the computation time on the same size training data dramatically. However, as the scale of distributed systems grows up, gradient and parameter synchronization prolongs the communication time and hinders the perfect scalability [60,112]. Therefore, the high network communication cost becomes a significant bottleneck of distributed training. There have been many attempts to reduce the communication overhead in data-parallel SGD. One notable method is to let each worker use compressed gradients rather than raw gradients for communication. For example, quantized SGD or sparcified SGD allow each worker to use fewer bits to pass gradients by sacrificing the convergence to a mild extent. Another notable method is to reduce the frequency of communication [50,62,71,124,126]. We detail on these two communication-efficient methods in the subsequent sections.

Gradient Compression
Lin et al. [63] find that 99.9% of the gradient exchange in distributed SGD are redundant. One promising solution is gradient compression, e.g., through gradient quantization [5,58,82,90,105,112] and/or gradient sparsification [4,31,63,100]. Sparcification means transmitting only those gradients that are important (e.g., gradients with large absolute values), while quantization refers to using fewer bits to represent the original gradient. Their difference is described in Fig. 3.

Gradient Quantization.
Quantizing the gradients to low-precision values can reduce the communication bandwidth. In full-precision data-parallel SGD, each processor broadcasts its locally computed stochastic gradient vector at every iteration, whereas in quantized data-parallel SGD, each processor quantizes its stochastic gradient before broadcasting. Gradient quantization is usually done by mapping a continuous space of gradient values onto a discrete set. Take the classic Quantized Stochastic Gradient Descent (QSGD) [5] as an example, the quantization function is denoted with ( ): Fig. 3. Comparison of Quantization and Sparsification, src: [106] where ( , ) are independent random variables. Let 0 ≤ < be an integer such that /∥ ∥ 2 ∈ [ / , ( + 1)/ ]. That is, [ / , ( + 1)/ ] is the quantization interval corresponding to /∥ ∥ 2 . Then ( , ) is defined as follows Here, ( , ) = − for any ∈ [0, 1]. For gradients , quantization is used to randomly convert gradient values in each dimension to some discrete value in a predetermined discrete set. After normalized by the Euclidean norm of the gradients (| |/∥ ∥), the value of each dimension will fall on a sub-interval [0, 1], and we approximate it to one of the endpoints of the sub-interval with a certain probability each time, so that the continuous value space of the original gradient value can be replaced by a set of finite discrete values. Here ( , ) is a binary random variable which guarantees that each value is quantized in a way which preserves the value in expectation, [ ( , )] = | |/∥ ∥, and introduce minimal variance. An instance of QSGD is provided in Fig. 4. This gradient quantization method greatly reduces the amount of communication required by a single node. Instead of passing 32-bit floating-point gradients, only one 32-bit floating-point gradient with one bit for gradient sign and ( ) bits for ( , ) on each dimension are required. In addition, there is another method TernGrad [112] developed simultaneously with QSGD. Their underlying idea is essentially similar, where TernGrad can be viewed as a special case of QSGD when = 1. TernGrad randomly quantizates gradient to a ternary value vector with value of {−1, 0, 1}. Formally, with a random binary vector , gradient is ternarized as Here, • is the Hadamard product. TernGrad also adopts techniques such as layer-wise ternarizing and gradient clipping to improve convergence. Ramezani-Kebrya et al. [82] propose nonuniform quantization levels (NUQSGD) and demonstrate superior empirical results compared to QSGD. Horvath et al. [46] propose natural compression and natural dithering, where the latter is a special case of logarithmic quantization. Unlike QSGD and its variants which use stochastic rounding which has an unbiased gradient expectation, there are methods adopt biased ones. Methods performing updates only based on the sign of each coordinate of the gradient have gained popularity for training DL models [13,51,58,90,105]. Seide et al. [90] proposed SignSGD, a.k.a. 1-bit SGD, to quantize the gradients aggressively to one bit per value. In this scheme, gradient updates greater than or equal to zero are encoded using The reconstruction values are chosen to be the means of the non-negative and negative updates, respectively, in order to minimize the square quantization error. This is done column-wise over the weight matrix. In each data exchange, the two reconstruction values are transmitted along with their respective quantized column. Bernstein et al. [13] later provided convergence guarantees for a variant of SignSGD. Karimireddy et al. [51] proposed EF-SignSGD, which is an improved version of SignSGD. More recently, gradient compression with error compensation has been successfully applied to adaptive optimizer such as Adam (1-bit Adam [105]) and LAMB (1-bit LAMB [58]), further scaling up training algorithms in the distributed setting.
To recap, while the analyses of gradient quatization have largely been restricted to unbiased compression schemes [5,46,82,112], biased schemes which perform extreme compression practically perform much better often without any loss in convergence or accuracy [51,58,63,90,100,105]. 7.1.2 Gradient Sparsification. Gradient sparsification is an orthogonal approach to quatization methods, which reduces the communication bandwidth by sending only the important gradients. Since zeroing small gradients damages convergence, small gradients are accumulated over time locally until they become large enough to be transmitted. Thus, we send the large gradients immediately but eventually send all of the gradients. Strom [100] proposed threshold quantization by considering only gradient elements whose absolute values exceed a threshold. A fixed threshold is chosen in advance. Gradient updates greater than are encoded with the value 1, and those less than − with the value of 0. Updates of magnitude less than are not sent at all, reducing the volume of data sent. The reconstructed value is and − respectively, and error feedback is used as normal. However, the threshold is hard to choose in practice and, moreover, it can change over time during optimization. As a resolve, Top-k sparsification selects the top-k gradients in terms of absolute values at each iteration [6,99] (see Fig. 5 for an example). Dryden et al. [31] choose an adaptive threshold so as to keep a constant proportion of gradients each iteration. Aji and Heafield [4] sparsify gradient updates by removing the R% smallest gradients by absolute value, dubbing this Gradient Dropping. This approach is slightly different from [31] as it uses a single threshold based on absolute value, instead of dropping the positive and negative gradients separately. Concurrently, Chen et al. [23] localize selection of gradient residues and automatically tunes the compression rate depending on local activity. Lin et al. [63] further push the compression ratio by employing momentum correction, local gradient clipping, momentum factor masking, warm-up training on top of the gradient sparsification while maintaining model performance. Table 2 summarises the gradient quantization and sparsification methods. Quant. Unbiased QSGD [5], NQSGD [82], TernGrad [112], Natural [46] Biased than one batch update on local data and exchange the updated weights rather than the gradients among workers.

Reducing Communication Frequency
We consider a distributed SGD framework with worker nodes where all workers communicate with others via a central server or via direct inter-worker communication. In local SGD, each worker ∈ [ ] performs sequential mini-batch SGD updates locally, and then the local models are synchronized by averaging weights among workers. Thus, the overall update rule at the -th worker is given by where ( )+ℎ denotes the local model on worker with batch size after global synchronization and ℎ local SGD updates. Mini-batch SGD is a special case of local SGD, with = 1, that is, the local models are synchronized after every iteration. The convergence results for convex and non-convex objectives are provided in [98,125]. However, while local updates reduce the communication frequency by performing global synchronization periodically instead of at per iteration, the discrepancies between local models can result in an inferior error-convergence. A larger value of (i.e., the number of sequential local SGD updates), which means less frequent averaging, saves communication delay and reduces the run-time per iteration. But on the other hand, a larger leads to slower convergence w.r.t. the number of iterations. The trade-off in between still need more exploration.
In addtion to being communication efficient, Lin et al. [62] find local SGD also exhibits good generalization behaviour. They argue that local SGD is a way to inject and control stochastic noise to the whole training procedure, and thus proposed post-local SGD as large batch training alternative for better generalization.

MEMORY
Larger models usually require more computation and memory resources to train. The amount of memory required to train these models can be several orders of magnitude larger than the amount of memory available on a single GPU. In this section, we will see how some popular techniques successfully reduce the memory requirements of training NNs without compromising model performance. Section 8.1 introduces how mix-precision training [72] lowers the burden on memory using fewer bits to preserve the weights and gradients during training. Section 8.2 introduces two memory-efficient adaptive optimizers, Adafactor [93] and SM3 [10]. And as orthogonal to the above  [81] do not change the model optimization method or affect model convergence, but instead reduces the memory cost by removing the redundancy in data-parallel (Section 8.3).

Mix-Precision Training
Modern DL training systems use single-precision (FP32) format, which takes 32 bits of memory. However, lower-precision (FP16) takes 16 bits of memory instead. Modern accelerators like Google TPUs and NVIDIA GPUs can run operations faster in the FP16 format, as they have specialized hardware to run 16-bit computations and 16-bit dtypes can be read from memory faster. These lowerprecision provides numerous benefits. First, they require less memory, enabling the training and deployment of larger NNs. Second, they lowers the burden on memory since fewer bits are required to preserve the same number of values than the FP32 format, thereby speeding up data transfer operations. Third, they speed up the mathematical computation since low-precision calculation is less time-consuming, especially on GPUs with Tensor Core support for that precision. However, low precision training also introduces a trade-off of the number of bits used versus the statistical accuracy: the fewer bits used, the lower accuracy. Mixed precision training is a very simple and practical technique, jointly published by Baidu and Google in [72], which almost halves the memory footprint while maintaining the model accuracy. This is achieved by identifying the steps that require full precision and using FP32 for only those steps while using FP16 everywhere else. We explain the workflow of mix precision training in Figure 6. Due to the differences in representable ranges, simply converting the model to FP16 can cause gradient underflow or overflow problems. We can avoid these challenges with the following four steps: (1) Conversion into FP16. In step one, we cast the inputs from FP32 to FP16 for compute intensive operations. (2) Use FP32 to compute the loss. Because FP16 might cause underflow or overflow issues, we do loss calculation in FP32 in the backward pass and cast gradients back to FP16, which means that the weights and the gradients are still in FP16. (3) FP32 master weights. In the backward pass, gradients are small compared to the parameters. If we try to update our parameters with the gradients that are much smaller than the parameters, then we might lose those parameter updates. To compensate we will maintain the master copy of weights in FP32. This means that, to the end of the backward pass, FP16 gradients will be cast into FP32 and thereby applied to FP32 weights. In the forward pass, we will cast the weights into FP16 so that the gradient computations remain in FP16. So effectively we have a master copy of all the parameters which are weights and biases stored in FP32 but all the computational operations will see the casted version which is in FP16. (4) Loss (Gradient) scaling. The last step is to do loss scaling to avoid a gradient underflow problem. Before computing gradients from the FP32 loss, we scale a loss by multiplying it with a loss scale factor. By doing so, gradients are pushed to larger values and we can safely represent them in FP16. Later when updating the weights we can re-scale the gradients by dividing them with the same loss scale factor.
Their article [72] is not the first to propose the use of lower precision for training, but its influence is far-reaching, and many current programs are designed based on this work. Jia et al. [49] apply mixed-precision training to large-batch strategies such as LARS. Using LARS with mixed-precision training, ResNet-50 with the mini-batch size of 64K, could maintain the top-1 accuracy as 76.2%.

Memory Efficient Adaptive Optimization
Some stochastic optimization methods (e.g., RMSProp, Adam [53], Adadelta [122]), keep first and second moment estimates of the per-parameter gradients to scale the gradients which triples the required memory. As models continue to grow, the memory overhead will pose more limitation on the quality of the trained model. Motivated by these challenges, memory efficient adaptive optimization methods are proposed to retain the benefits of standard per-parameter adaptivity while significantly reduce memory overhead. For instance, Adafactor [93] was proposed as a way to reduce the memory costs of AdaGrad [32], primarily for training large language models, and SM3 [10] saves memory by sharing moments of similar magnitude. [93] is a space-efficient adaptive optimization which achieves a drastic reduction in auxiliary memory usage without hurting the performance (compared to that obtained using full accumulators). One of the key contribution is the use of factored second momentum estimation.

Adafactor. Adafactor
Consider a matrix-shaped parameter subset with second moment estimate . They want to identify a low-rank representation of as a product of two factors and , i.e., ≈ which is compatible with exponential moving averaging. This would allow us to store just the low-rank factors across iteration, cutting down a memory usage. More formally, if factorization : ↦ → ( , ), we want ( −1 + (1 − ) 2 ) = ( −1 ) + (1 − ) ( 2 ). In particular, by using techniques from non-negative matrix factorization using I-divergence, the low-rank approximation can be converted into following optimization problem: In particular, for the case of rank one factors, i.e., = 1, the solution set of the optimization problem can be characterized as the set of all pairs ( , ), whose product is equal to the expression below: The right hand side can be broken down into the vector of row sums and column sums, and the denominator is the sum of all entries. In addition to the factored second moment estimation, other key changes in Adafactor include 2 varies with time, update cliping, relative step size and no momentum.

SM3
Algorithm. Adaptive gradient methods, such as AdaGrad [32], have proved to be particularly useful in training sparse models. Crucially, however, Adagrad must maintain auxiliary sequence of accumulators (i.e., the diagonal preconditioner) (also in Eq. [10]) : and thus needs Ω( ) additional space is the number of parameters. SM3 [10] provides a memoryefficient methods with comparable convergence characteristics which refrains from maintaining the full vectors. SM3 is short for save memory by sharing moments of similar magnitude. This is because they observe that the diagonal preconditioners accumulated by AdaGrad are actually similar in rows and columns, and by sharing moments cross rows and columns, the memory requirements therefore drop from Θ( ) to merely Θ( + ).
SM3 can be viewed as a diagonal version of Shampoo (see Table 1). We refer readers about the implementation details to [10].

ZeRO
The Zero Redundancy Optimizer [81] (abbreviated as ZeRO) is a novel memory optimization technology for large-scale distributed DL. Contrary to Adafactor [93] and SM3 [10] which reduce memory consumption of adaptive optimization methods by maintaining coarser-grained statistics of model parameters and gradients, ZeRO do not change the model optimization method or affect the model convergence.
We show how ZeRO works in Fig.[7]. The first row shows the memory map while training a model in data parallel. The first row shown in blue represents the memory consumed by the parameters; the second row in orange shows the memory consumed by the gradients; and the big chunk in green shows the memory consumed by the optimizer states (e.g., this could be momentum and variance for Adam). So the key thing is that these optimizer states gradients and parameters (which we collectively call the model states) are replicated across all the different GPUs in distributed data parallel training. The way ZeRO works is by removing this redundancy across these GPUs. Since there are three different types of model states, there are three different phases of ZeRO, each of them removing the redundancy for one of these states by simply partitioning these model states across GPUs instead of replicating them.
In addition to reducing the memory from model states, ZeRO also has a bunch of more optimizations that allows reduction in memory from other components (see Table 3 Proactively manage memory w.r.t tensor lifetime Table 3. Different Memory Optimizations in ZeRO how model states are replicated across multiple GPUs in data parallel training, ZeRO removes the redundancy in activation memory by partitioning the activations across these model parallel GPUs. We can also offload these activation memories to CPU if we don't have enough memory to train extremely large models. The next optimization that ZeRO can do is to convert fragmented memory to defragmented memory on the fly during training. During training if the memory is fragmented, we might still run out of memory even though there might be enough fragmented memory that can satisfy the request if they were contiguous. In ZeRO the memory defragmentation will on the fly defragment these memory fragments so that all the memory is contiguous and you are able to satisfy these larger memory requests. So with all these different memory optimizations, ZeRO is able to train models with up to 200 billion parameters up to 10 times faster than the SOTA.

CONCLUSION
Given larger datasets and bigger models consistently yielding significant improvements in accuracy, large-scale deep learning has become an inevitable trend. As datasets increase in size and DNNs in complexity, the computational intensity, communication cost and memory demands of deep learning increase proportionally. Considerable efforts have been devoted to accelerating the training speed. In this article, we give an overview of large-scale deep learning optimization. The goal in general is two-fold: model accuracy and model efficiency. As for the model accuracy, we investigate algorithms that are most commonly used for optimizing, spanning from the gradient descent variants to the (large-batch) adaptive methods, and from first-order to second-order methods. Further, we elaborate the debatable topic of generalization gap arises in large-batch training. As for the model efficiency, we summarise the SOTA techniques in addressing the expensive cost of communication overhead and memory footprint. We hope this article can provide a clean sketch for those who are interested in training large-scale training.