CROSS-ITERATION BATCH NORMALIZATION
Year: 2019

Abstract:
A well-known issue of Batch Normalization is its significantly reduced effectiveness in the case of small mini-batch sizes. When a mini-batch contains few examples, the statistics upon which the normalization is defined cannot be reliably estimated from it during a training iteration. To address this problem, we present Cross-Iteration Batch Normalization (CBN), in which examples from multiple recent iterations are jointly utilized to enhance estimation quality. A challenge of computing statistics over multiple iterations is that the network activations from different iterations are not comparable to each other due to changes in network weights. We thus compensate for the network weight changes via a proposed technique based on Taylor polynomials, so that the statistics can be accurately estimated and batch normalization can be effectively applied. On object detection and image classification with small mini-batch sizes, CBN is found to outperform the original batch normalization and a direct calculation of statistics over previous iterations without the proposed compensation technique.

heading: 1 INTRODUCTION
text: Batch Normalization (BN) (Ioffe & Szegedy, 2015) has played a significant role in the success of deep neural networks. It was introduced to address the issue of internal covariate shift, where the distribution of network activations changes during training iterations due to the updates of network parameters. This shift is commonly believed to be disruptive to network training, and BN alleviates this problem through normalization of the network activations by their mean and variance, computed over the examples within the mini-batch at each iteration. With this normalization, network training can be performed at much higher learning rates and with less sensitivity to weight initialization.
In BN, it is assumed that the distribution statistics for the examples within each mini-batch reflect the statistics over the full training set. While this assumption is generally valid for large batch sizes, it breaks down in the small batch size regime (Peng et al., 2018; Wu & He, 2018; Ioffe, 2017), where noisy statistics computed from small sets of examples can lead to a dramatic drop in performance. This problem hinders the application of BN to memory-consuming tasks such as object detection (Ren et al., 2015; Dai et al., 2017), semantic segmentation (Long et al., 2015; Chen et al., 2017) and action recognition (Wang et al., 2018b), where batch sizes are limited due to memory constraints.
Towards improving estimation of statistics in the small batch size regime, alternative normalizers have been proposed. Several of them, including Layer Normalization (LN) (Ba et al., 2016), Instance Normalization (IN) (Ulyanov et al., 2016), and Group Normalization (GN) (Wu & He, 2018), compute the mean and variance over the channel dimension, independent of batch size. Different channel-wise normalization techniques, however, tend to be suitable for different tasks, depending on the set of channels involved. On the other hand, synchronized BN (SyncBN) (Peng et al., 2018) yields consistent improvements by processing larger batch sizes across multiple GPUs. These gains in performance come at the cost of additional overhead needed for synchronization across the devices.
A seldom explored direction for estimating better statistics is to compute them over the examples from multiple recent training iterations, instead of from only the current iteration as done in previous techniques. This can substantially enlarge the pool of data from which the mean and variance are obtained. However, there exists an obvious drawback to this approach, in that the activation values from different iterations are not comparable to each other due to the changes in network weights. As shown in Figure 1, directly calculating the statistics over multiple iterations, which we refer to as Naive CBN, results in lower accuracy.
In this paper, we present a method that compensates for the network weight changes among iterations, so that examples from preceding iterations can be effectively used to improve batch normalization. Our method, called Cross-Iteration Batch Normalization (CBN), is motivated by the observation that network weights change gradually, instead of abruptly, between consecutive training iterations, thanks to the iterative nature of Stochastic Gradient Descent (SGD). As a result, the mean and variance of examples from recent iterations can be well approximated for the current network weights via a low-order Taylor polynomial, defined on gradients of the statistics with respect to the network weights. The compensated means and variances from multiple recent iterations are averaged with those of the current iteration to produce better estimates of the statistics.
In the small batch size regime, CBN leads to appreciable performance improvements over the original BN, as exhibited in Figure 1. The superiority of our proposed approach is further demonstrated through more extensive experiments on ImageNet classification and object detection on COCO. These gains are obtained with negligible overhead, as the statistics from previous iterations have already been computed and Taylor polynomials are simple to evaluate. With this work, it is shown that cues for batch normalization can successfully be extracted along the time dimension, opening a new direction for investigation.

heading: 2 RELATED WORK
text: The importance of normalization in training neural networks has been recognized for decades (LeCun et al., 1998). In general, normalization can be performed on three components: input data, hidden activations, and network parameters. Among them, input data normalization is used most commonly because of its simplicity and effectiveness (Sola & Sevilla, 1997; LeCun et al., 1998).
After the introduction of Batch Normalization (Ioffe & Szegedy, 2015), the normalization of activations has become nearly as prevalent. By normalizing hidden activations by their statistics within each mini-batch, BN effectively alleviates the vanishing gradient problem and significantly speeds up the training of deep networks. To mitigate the mini-batch size dependency of BN, a number of variants have been proposed, including Layer Normalization (LN) (Ba et al., 2016), Instance Normalization (IN) (Ulyanov et al., 2016), Group Normalization (GN) (Wu & He, 2018), and Batch Instance Normalization (BIN) (Nam & Kim, 2018). The motivation of LN is to explore more suitable statistics for sequential models, while IN performs normalization in a manner similar to BN but with statistics only for each instance. GN achieves a balance between IN and LN, by dividing features into multiple groups along the channel dimension and computing the mean and variance within each group for normalization. BIN introduces a learnable method for automatically switching between normalizing and maintaining style information, enjoying the advantages of both BN and IN on style transfer tasks. Cross-GPU Batch Normalization (CGBN or SyncBN) (Peng et al., 2018) extends BN across multiple GPUs for the purpose of increasing the effective batch size. Though providing higher accuracy, it introduces synchronization overhead to the training process. Kalman Normalization (KN) (Wang et al., 2018a) presents a Kalman filtering procedure for estimating the statistics for a network layer from the layer’s observed statistics and the computed statistics of previous layers.
Batch Renormalization (BRN) (Ioffe, 2017) is the first attempt to utilize the statistics of recent iterations for normalization. It does not compensate for the statistics from recent iterations, but rather it down-weights the importance of statistics from distant iterations. This down-weighting heuristic, however, does not make the resulting statistics “correct", as the statistics from recent iterations are not of the current network weights. BRN can be deemed as a special version of our Naive CBN baseline (without Taylor polynomial approximation), where distant iterations are down-weighted.
Recent work have also investigated the normalization of network parameters. In Weight Normalization (WN) (Salimans & Kingma, 2016), the optimization of network weights is improved through a reparameterization of weight vectors into their length and direction. Weight Standardization (WS) (Qiao et al., 2019) instead reparameterizes weights based on their first and second moments for the purpose of smoothing the loss landscape of the optimization problem. To combine the advantages of multiple normalization techniques, Switchable Normalization (SN) (Luo et al., 2018) and Sparse Switchable Normalization (SSN) (Shao et al., 2019) make use of differentiable learning to switch among different normalization methods.
The proposed CBN takes an activation normalization approach that aims to mitigate the mini-batch dependency of BN. Different from existing techniques, it provides a way to effectively aggregate statistics across multiple training iterations.

heading: 3 METHOD

heading: 3.1 REVISITING BATCH NORMALIZATION
text: The original batch normalization (BN) (Ioffe & Szegedy, 2015) whitens the activations of each layer by the statistics computed within a mini-batch. Denote θt and xt,i(θt) as the network weights and the feature response of a certain layer for the i-th example in the t-th mini-batch. With these values, BN conducts the following normalization:
x̂t,i(θt) = xt,i(θt)−µt(θt)√
σt(θt)2 + ε , (1)
where x̂t,i(θt) is the whitened activation with zero mean and unit variance, ε is a small constant added for numerical stability, and µt(θt) and σt(θt) are the mean and variance computed for all the examples from the current mini-batch, i.e.,
µt(θt) = 1 m
m
∑ i=1 xt,i(θt), (2)
σt(θt) = √ 1 m m ∑ i=1 (xt,i(θt)−µt(θt))2 = √ νt(θt)−µt(θt)2, (3)
where νt(θt) = 1m ∑ m i=1 xt,i(θt)2, and m denotes the number of examples in the current mini-batch. The whitened activation x̂t,i(θt) further undergoes a linear transform with learnable weights, to increase its expressive power:
yt,i(θt) = γ x̂t,i(θt)+β , (4)
where γ and β are the learnable parameters (initialized to γ = 1 and β = 0 in this work).
When the batch size m is small, the statistics µt(θt) and σt(θt) become noisy estimates of the training set statistics, thus degrading the effects of batch normalization. In the ImageNet classification task
for which the BN module was originally designed, a batch size of 32 is typical. However, for other tasks requiring larger models and/or higher image resolution, such as object detection, semantic segmentation and video recognition, the typical batch size may be as small as 1 or 2 due to GPU memory limitations. The original BN becomes considerably less effective in such cases.

heading: 3.2 LEVERAGING STATISTICS FROM PREVIOUS ITERATIONS
text: To address the issue of BN with small mini-batches, a naive approach is to compute the mean and variance over the current and previous iterations. However, the statistics µt−τ(θt−τ) and νt−τ(θt−τ) of the (t−τ)-th iteration are computed under the network weights θt−τ , making them obsolete for the current iteration. As a consequence, directly aggregating statistics from multiple iterations produces inaccurate estimates of the mean and variance, leading to significantly worse performance.
We observe that the network weights change smoothly between consecutive iterations, due to the nature of gradient-based training. This allows us to approximate µt−τ(θt) and νt−τ(θt) from the readily available µt−τ(θt−τ) and νt−τ(θt−τ) via a Taylor polynomial, i.e.,
µt−τ(θt) = µt−τ(θt−τ)+ ∂ µt−τ(θt−τ)
∂θt−τ (θt −θt−τ)+O(||θt −θt−τ ||2), (5)
νt−τ(θt) = νt−τ(θt−τ)+ ∂νt−τ(θt−τ)
∂θt−τ (θt −θt−τ)+O(||θt −θt−τ ||2), (6)
where ∂ µt−τ(θt−τ)/∂θt−τ and ∂νt−τ(θt−τ)/∂θt−τ are gradients of the statistics with respect to the network weights, and O(||θt −θt−τ ||2) denotes higher-order terms of the Taylor polynomial, which can be omitted since the first-order term dominates when (θt −θt−τ) is small. In Eq. (5) and Eq. (6), the gradients ∂ µt−τ(θt−τ)/∂θt−τ and ∂νt−τ(θt−τ)/∂θt−τ cannot be precisely determined at a negligible cost because the statistics µ lt−τ(θt−τ) and ν lt−τ(θt−τ) for a node at the l-th network layer depend on all the network weights prior to the l-th layer, i.e., ∂ µ lt−τ(θt−τ)/∂θ rt−τ 6= 0 and ∂ν lt−τ(θt−τ)/∂θ rt−τ 6= 0 for r ≤ l, where θ rt−τ denotes the network weights at the r-th layer. Only when r = l can these gradients be derived in closed form efficiently.
Empirically, we find that as the layer index r decreases (r≤ l), the partial gradients ∂ µ l t (θt ) θ rt and ∂ν l t (θt ) θ rt rapidly diminish. These reduced effects of network weight changes at earlier layers on the activation distributions in later layers may perhaps be explained by the reduced internal covariate shift of BN. Motivated by this phenomenon, which is studied in Appendix C, we propose to truncate these partial gradients at layer l.
Thus, we further approximate Eq. (5) and Eq. (6) by
µ lt−τ(θt)≈ µ lt−τ(θt−τ)+ ∂ µ lt−τ(θt−τ)
∂θ lt−τ (θ lt −θ lt−τ), (7)
ν lt−τ(θt)≈ ν lt−τ(θt−τ)+ ∂ν lt−τ(θt−τ)
∂θ lt−τ (θ lt −θ lt−τ). (8)
A naive implementation of ∂ µ lt−τ(θt−τ)/∂θ lt−τ and ∂ν lt−τ(θt−τ)/∂θ lt−τ involves computational overhead of O(Cl ×Cl ×Cl−1×K), where Cl and Cl−1 denote the channel dimension of the l-th layer and the (l−1)-th layer, respectively, and K denotes the kernel size of θ lt−τ . Here we find that the operation can be implemented efficiently in O(Cl×Cl−1×K), thanks to the averaging over feature responses of µ and ν . See Appendix B for the details.

heading: 3.3 CROSS-ITERATION BATCH NORMALIZATION
text: After compensating for network weight changes, we aggregate the statistics of the k−1 most recent iterations with those of the current iteration t to obtain the statistics used in CBN:
µ̄ lt,k(θt) = 1 k
k−1 ∑ τ=0 µ lt−τ(θt), (9)
ν̄ lt,k(θt) = 1 k
k−1 ∑ τ=0 max [ ν lt−τ(θt),µ l t−τ(θt) 2], (10)
σ̄ lt,k(θt) = √ ν̄ lt,k(θt)− µ̄ lt,k(θt)2, (11)
where µ lt−τ(θt) and ν lt−τ(θt) are computed from Eq. (7) and Eq. (8). In Eq. (10), ν̄ lt,k(θt) is determined from the maximum of ν lt−τ(θt) and µ lt−τ(θt)2 in each iteration because ν lt−τ(θt)≥ µ lt−τ(θt)2 should hold for valid statistics but may be violated by Taylor polynomial approximations in Eq. (7) and Eq. (8). Finally, µ̄ lt,k(θt) and σ̄ l t,k(θt) are applied to normalize the corresponding feature responses {xlt,i(θt)}mi=1 at the current iteration:
x̂lt,i(θt) = xlt,i(θt)− µ̄ lt,k(θt)√
σ̄ lt,k(θt)2 + ε . (12)
With CBN, the effective number of examples used to compute the statistics for the current iteration is k times as large as that for the original BN. In training, the loss gradients are backpropagated to the network weights and activations at the current iteration, i.e., θ lt and xlt,i(θt). Those of the previous iterations are fixed and do not receive gradients. Hence, the computation cost of CBN in back-propagation is the same as that of BN.
Replacing the BN modules in a network by CBN leads to only minor increases in computational overhead and memory footprint. For computation, the additional overhead mainly comes from computing the partial derivatives ∂ µt−τ(θt−τ)/∂θ lt−τ and ∂νt−τ(θt−τ)/∂θ lt−τ , which is insignificant in relation to the overhead of the whole network. For memory, the module requires access to the statistics ({µ lt−τ(θt−τ)}k−1τ=1 and {ν lt−τ(θt−τ)} k−1 τ=1) and the gradients ({∂ µt−τ(θt−τ)/∂θ lt−τ} k−1 τ=1 and {∂νt−τ(θt−τ)/∂θ lt−τ}k−1τ=1) computed for the most recent k− 1 iterations, which is also minor compared to the rest of the memory consumed in processing the input examples. The additional computation and memory of CBN is reported for our experiments in Table 6.
A key hyper-parameter in the proposed CBN is the temporal window size, k, of recent iterations used for statistics estimation. A broader window enlarges the set of examples, but the example quality becomes increasingly lower for more distant iterations, since the differences in network parameters θt and θt−τ become more significant and are compensated less well using a low-order Taylor polynomial. Empirically, we found that CBN is effective with a window size up to k = 8 in a variety of settings and tasks. The only trick is that the window size should be kept small at the beginning of training, when the network weights change quickly. Thus, we introduce a burn-in period of length Tburn-in for the window size, where k = 1 and CBN degenerates to the original BN. In our experiments, the burn-in period is set to 25 epochs on ImageNet image classification and 3 epochs on COCO object detection by default. Ablations on this parameter are presented in the Appendix.
Table 1 compares CBN with other feature normalization methods. The key difference among these approaches is the axis along which the statistics are counted and the features are normalized. The previous techniques are all designed to exploit examples from the same iteration. By contrast, CBN explores the aggregation of examples along the temporal dimension. As the data utilized by CBN lies in a direction orthogonal to that of previous methods, the proposed CBN could potentially be combined with other feature normalization approaches to further enhance statistics estimation in certain challenging applications.

heading: 4 EXPERIMENTS

heading: 4.1 IMAGE CLASSIFICATION ON IMAGENET
text: Experimental settings. ImageNet (Russakovsky et al., 2015) is a benchmark dataset for image classification, containing 1.28M training images and 50K validation images from 1000 classes. We
follow the standard setting in (He et al., 2015) to train deep networks on the training set and report the single-crop top-1 accuracy on the validation set. Our preprocessing and augmentation strategy strictly follows the GN baseline (Wu & He, 2018). We use a weight decay of 0.0001 for all weight layers, including γ and β . We train standard ResNet-18 for 100 epochs on 4 GPUs, and decrease the learning rate by the cosine decay strategy (He et al., 2019). We use the average over 5 trials for all results. All hyper-parameters, e.g. group size of GN, are carefully tuned via cross-validation. ResNet-18 with BN is our base model. To compare with other normalization methods, we directly replace BN with IN, LN, GN, BRN, and our proposed CBN.
Comparison of feature normalization methods. We compare the performance of each normalization method with a normal batch size, 32, in Table 2. With sufficient data for reliable statistics, BN easily reaches the highest top-1 accuracy. Similar as the results in previous papers
(Wu & He, 2018), IN and LN achieve significantly worse performance than BN. GN works well on image classification, but still has a small degradation of 1.2% compared with BN. Over all the methods, our CBN is the only one that is able to achieve comparable accuracy with BN, as it converges to the procedure of BN as the batch size becomes larger.
Sensitivity to batch size. We compare the behavior of CBN, original BN (Ioffe & Szegedy, 2015), GN (Wu & He, 2018), and BRN (Ioffe, 2017) at the same number of images per GPU on ImageNet classification. For CBN, the recent iterations are utilized so as to ensure that the number of effective examples is no fewer than 16. For BRN, the settings strictly follow the original paper. We adopt a learning rate of 0.1 for the batch size of 32, and linearly scale the learning rate by N/32 for a batch size of N.
The results are shown in Table 3. For the original BN, its accuracy drops noticeably as the number of images per GPU is reduced from 32 to 2. BRN suffers a significant performance drop as well. GN maintains its accuracy by utilizing the channel dimension but not batch dimension. For CBN, its accuracy holds by exploiting the examples of recent iterations. Also, CBN outperforms GN by 0.9% on average top-1 accuracy with different batch sizes. This is reasonable, because the statistics computation of CBN introduces uncertainty caused by the stochastic batch sampling like in BN, but this uncertainty is missing in GN which results in some loss of regularization ability.

heading: 4.2 OBJECT DETECTION AND INSTANCE SEGMENTATION ON COCO
text: Experimental settings. COCO (Lin et al., 2014) is chosen as the benchmark for object detection and instance segmentation. Models are trained on the COCO 2017 train split with 118k images, and evaluated on the COCO 2017 validation split with 5k images. Following the standard protocol in (Lin et al., 2014), the object detection and instance segmentation accuracies are measured by the mean average precision (mAP) scores at different intersection-over-union (IoU) overlaps at the box and the mask levels, respectively.
Following (Wu & He, 2018), Faster R-CNN (Ren et al., 2015) and Mask R-CNN (He et al., 2017) with FPN (Lin et al., 2017) are chosen as the baselines for object detection and instance segmentation, respectively. For both, the 2fc box head is replaced by a 4conv1fc head for better use of the normalization mechanism (Wu & He, 2018). The backbone networks are ImageNet pretrained ResNet-50 (default) or ResNet-101, with specific normalization. Finetuning is performed on the COCO train set for 12 epochs on 4 GPUs by SGD, where each GPU processes 4 images (default). Note that the mean and variance statistics in CBN are computed within each GPU. The learning rate is initialized to be 0.02∗N/16 for a batch size per GPU of N, and is decayed by a factor of 10 at the 9-th and the 11-th epochs. The weight decay and momentum parameters are set to 0.0001 and 0.9, respectively. We use the average over 5 trials for all results. All hyper-parameters, e.g. group size of GN, are carefully tuned via cross-validation.
As done in (Wu & He, 2018), we experiment with two settings where the normalizers are activated only at the task-specific heads with frozen BN at the backbone (default), or the normalizers are activated at all the layers except for the early conv1 and conv2 stages in ResNet.
Normalizers at backbone and task-specific heads. We further study the effect of different normalizers on the backbone network and task-specific heads for object detection on COCO. CBN, original BN, syncBN, and GN are included in the comparison.
Table 4 presents the results. When BN is frozen in the backbone and no normalizer is applied at the head, the APbbox score is 36.9%. When the original BN is applied at the head only and at both the backbone and the head, the accuracy drops to 36.3% and 35.5%, respectively. For CBN, the accuracy is 37.7% and 37.3% at these two settings, respectively. Without any synchronization across GPUs, CBN can achieve comparable performance with syncBN and GN, showing the superiority of the proposed approach. Unfortunately, due to the accumulation of approximation error, CBN observes a 0.4% decrease in APbbox when replacing frozen BN with CBN in the backbone. Even so, CBN still outperforms the variant with unfrozen BN in backbone by 1.8%.
Instance segmentation and stronger backbones. Results of object detection (Faster R-CNN (Ren et al., 2015)) and instance segmentation (Mask R-CNN (He et al., 2017)) with ResNet-50 and ResNet-101 are presented in Table 5. We can observe that our proposed CBN achieves performance comparable to syncBN and GN with R50 and R101 as the backbone on both Faster R-CNN and Mask R-CNN, which demonstrates that CBN is robust and versatile to various deep models and tasks.

heading: 4.3 ABLATION STUDY
text: Effect of temporal window size k. We conduct this ablation on ImageNet image classification and COCO object detection, with each GPU processing 4 images. Figure 3 presents the results. When k = 1, only the batch from the current iteration is utilized; therefore, CBN degenerates to the original BN. The accuracy suffers due to the noisy statistics on small batch sizes. As the window size k gradually increases, more examples from recent iterations are utilized for statistics estimation, leading to greater accuracy. Accuracy saturates at k = 8 and even drops slightly. For more distant iterations, the network weights differ more substantially and the Taylor polynomial approximation becomes less accurate.
On the other hand, it is empirically observed that the original BN saturates at a batch size of 16 or 32 for numerous applications (Peng et al., 2018; Wu & He, 2018), indicating that the computed statistics become accurate. Thus, a temporal window size of k = min(d 16bs per GPUe,8) is suggested.
Effect of compensation. To study this, we compare CBN with 1) a naive baseline where statistics from recent iterations are directly aggregated without compensation via Taylor polynomial, referred to as Naive CBN; and 2) the original BN applied with the same
effective example number as CBN (i.e., its batch size per GPU is set to the product of the batch size per GPU and the temporal window size of CBN), which does not require any compensation and serves as an upper performance bound.
The experimental results are also presented in Figure 3. CBN clearly surpasses Naive CBN when the previous iterations are included. Actually, Naive CBN fails when the temporal window size grows to k = 8 as shown in Figure 3(a), demonstrating the necessity of compensating for changing network weights over iterations. Compared with the original BN upper bound, CBN achieves similar accuracy at the same effective example number. This result indicates that the compensation using a low-order Taylor polynomial by CBN is effective.
Figure 4 presents the train and test curves of CBN, Naive CBN, BN-bs4, and BN-bs16 on ImageNet, with 4 images per GPU and a temporal window size of 4 for CBN, Naive CBN, and BN-bs4, and 16 images per GPU for BN-bs16. The train curve of CBN is close to BN-bs4 at the beginning, and approaches BN-bs16 at the end. The reason is that we adopt a burn-in period to avoid the disadvantage of rapid statistics change at beginning of training. The gap between the train curve of Naive CBN and CBN shows that
Naive CBN cannot even reach a good convergence on the training set. The test curve of CBN is close to BN-bs16 at the end, while Naive CBN exhibits considerable jitter. All these phenomena indicate the effectiveness of our proposed Taylor compensation.
Additional computational overhead and memory footprint. As the inference stage of CBN is the same as BN, we only need to compare the computational overhead and memory footprint at the training time, shown in Table 6. The extra computational overhead mainly includes calculations of the statistics’ respective gradients, Taylor compensations, and averaging operations. For the extra memory, the statistics (µ and ν), their respective gradients, and the network parameters (θt−1 · · ·θt−(k−1)) of previous iterations are all stored when applying CBN.
From these results, the additional overhead of CBN is seen to be minor.

heading: A ALGORITHM OUTLINE
text: Algorithm 1 presents an outline of our proposed Cross-Iteration Batch Normalization (CBN).
Algorithm 1: Cross-Iteration Batch Normalization(CBN) Input: Feature responses of a network node of the l-th layer at the t-th iteration {xlt,i(θt)}mi=1,
network weights {θ lt−τ}k−1τ=0, statistics {µ lt−τ(θt−τ)} k−1 τ=1 and {ν lt−τ(θt−τ)} k−1 τ=1, and gradients {∂ µt−τ(θt−τ)/∂θ lt−τ}k−1τ=1 and {∂νt−τ(θt−τ)/∂θ lt−τ} k−1 τ=1 from most recent k−1 iterations
Output: {ylt,i(θt) = CBN(xlt,i(θt))} 1 µt(θt)← 1m ∑ m i=1 xt,i(θt), νt(θt)← 1m ∑ m i=1 x 2 t,i(θt) //statistics on the current iteration 2 for τ ∈ {1, . . . ,k} do 3 µ lt−τ(θt)← µ lt−τ(θt−τ)+
∂ µ lt−τ (θt−τ ) ∂θ lt−τ (θ lt −θ lt−τ) //approximation from recent iterations
4 ν lt−τ(θt)← ν lt−τ(θt−τ)+ ∂ν lt−τ (θt−τ )
∂θ lt−τ (θ lt −θ lt−τ) //approximation from recent iterations
5 end 6 µ̄ lt,k(θt)← 1 k ∑ k−1 τ=0 µ l t−τ(θt) //averaging over recent iterations 7 ν̄ lt,k(θt)← 1 k ∑ k−1 τ=0 max [ ν lt−τ(θt),µ lt−τ(θt)2 ] //validation and averaging over recent iterations 8 σ̄ lt,k(θt) 2← ν̄ lt,k(θt)− µ̄ lt,k(θt)2 9 x̂lt,i(θt) = xlt,i(θt )−µ̄ l t,k(θt )√
σ̄ lt,k(θt ) 2+ε
//normalize
10 ylt,i(θt)← γ x̂lt,i(θt)+β //scale and shift
B EFFICIENT IMPLEMENTATION OF ∂ µ lt−τ(θt−τ)/∂θ lt−τ AND ∂ν lt−τ(θt−τ)/∂θ lt−τ
Let Cl and Cl−1 denote the channel dimension of the l-th layer and the (l−1)-th layer, respectively, and K denotes the kernel size of θ lt−τ . µ lt−τ and ν lt−τ are thus of Cl dimensions in channels, and θ lt−τ is a Cl ×Cl−1×K dimensional tensor. A naive implementation of ∂ µ lt−τ(θt−τ)/∂θ lt−τ and ∂ν lt−τ(θt−τ)/∂θ lt−τ involves computational overhead of O(Cl×Cl×Cl−1×K). Here we find that the operations of µ and ν can be implemented efficiently in O(Cl−1×K) and O(Cl ×Cl−1×K), respectively, thanks to the averaging of feature responses in µ and ν .
Here we derive the efficient implementation of ∂ µ lt−τ(θt−τ)/∂θ lt−τ . That of ∂ν lt−τ(θt−τ)/∂θ lt−τ is about the same. Let us first simplify the notations a bit. Let µ l and θ l denote µ lt−τ(θt−τ) and θ lt−τ respectively, by removing the irrelevant notations for iterations. The element-wise computation in the forward pass can be computed as
µ lj = 1 m
m
∑ i=1 xli, j, (13)
where µ lj denotes the j-th channel in µ l , and xli, j denotes the j-th channel in the i-th example. xli, j is computed as
xli, j = Cl−1
∑ n=1
K
∑ k=1 θ lj,n,k · yl−1i+offset(k),n, (14)
where n and k enumerate the input feature dimension and the convolution kernel index, respectively, offset(k) denotes the spatial offset in applying the k-th kernel, and yl−1 is the output of the (l−1)-th layer.
The element-wise calculation of ∂ µ l/∂θ l ∈RCl×Cl×Cl−1×K is as follows, taking Eq. (13) and Eq. (14) into consideration:
[ ∂ µ l
∂θ l ] j,q,p,η = ∂ µ lj ∂θ lq,p,η
= ∂ 1m ∑ m i=1 x l i, j
∂θ lq,p,η
= ∂ 1m ∑ m i=1 ∑ Cl−1 n=1 ∑ K k=1 θ lj,n,k · y l−1 i+offset(k),n
∂θ lq,p,η
=
{ 1 m ∑ m i=1 y l−1 i+offset(η),p , j = q
0 , j 6= q .
(15)
Thus, [ ∂ µ l
∂θ l ] j,q,p,η takes non-zero values only when j = q. This operation can be implemented efficiently in O(Cl−1×K). Similarly, the calculation of ∂ν l/∂θ l can be obtained in O(Cl×Cl−1×K).

heading: C ADDITIONAL EXPERIMENTS
text: CIFAR-10 is selected for the experiments in this section. It consists of 50k training images and 10k test images from 10 classes. We train the standard ResNet-18 for 160 epochs on one GPU by SGD. The momentum and weight decay parameters are set to 0.9 and 0.0001, respectively. We experiment with batch sizes of 32, 16, 8, 4, and 2 images per GPU. The learning rate is scaled linearly to different batch sizes, following the practice in (Peng et al., 2018). The initial learning rate is 0.025∗N/32 for a batch size per
iteration of N. The learning rate is divided by 10 at epochs 80 and 120. The images are of 32×32 pixels with per-image standardization in both training and inference. Random flipping is applied in training.
We report the results of BN, BRN, GN, CBN with five trials on CIFAR-10, as shown in Table 7. CBN has the smallest gap with BN-bs16 compared to BN-bs4, BRN, and GN. This result is consistent with previous experiments on ImageNet and COCO. Also the std is tiny, indicating that performance on CIFAR-10 is stable enough for some empirical studies.
On the burn-in period length Tburn-in. We further study the influence of varying the burn-in period length Tburn-in, at 4 images per GPU on both CIFAR-10 image classification (ResNet-18) and COCO object detection (Faster R-CNN with FPN and ResNet-50).
Figure 5(a) and 5(b) present the results. When the burn-in period is too short, the accuracy suffers. This is because at the beginning of training, the network weights change rapidly, causing the
compensation across iterations to be less effective. On the other hand, the accuracy is stable for a wide range of burn-in periods Tburn-in that are not too short.
On the effect of using more than one layer. The efficient implementation is no longer applicable when more than one layer of compensation is adopted. Therefore, we only conduct a two-layer experiment of ResNet-18 on CIFAR-10 in consideration of the heavy extra memory and computational overhead. CBN using two layers for compensation achieves 95.0 on CIFAR-10 (batch size=4, k=4), which is comparable to CBN using only one layer. As using more layers does not further improve performance but consumes more FLOPs, we adopt one-layer compensation on CBN in practice.
On the gradients from different layers. The key assumption in Eq. (7) and Eq. (8) is that for a node at the l-th layer, the gradient of its statistics with respect to the network weights at the l-th layer is larger than that of weights from the prior layers, i.e., || ∂ µ l t−τ (θt−τ ) ∂θ lt−τ ||F || ∂ µ lt−τ (θt−τ ) ∂θ rt−τ ||F and || ∂ν l t−τ (θt−τ ) ∂θ lt−τ ||F || ∂ν lt−τ (θt−τ ) ∂θ rt−τ ||F for r < l, where || · ||F denotes the Frobenius norm. Here we examine this assumption empirically for networks trained on CIFAR-10 image recognition.
Figure 6 presents the computed ratio of || ∂ µ l t−τ (θt−τ ) ∂θ rt−τ ||F/|| ∂ µ lt−τ (θt−τ ) ∂θ lt−τ ||F and || ∂ν l t−τ (θt−τ ) ∂θ rt−τ ||F/|| ∂ν lt−τ (θt−τ ) ∂θ lt−τ ||F for r ≤ l, at different training epochs. The results suggest that || ∂ µ l t−τ (θt−τ ) ∂θ lt−τ ||F || ∂ µ lt−τ (θt−τ ) ∂θ rt−τ ||F and || ∂ν lt−τ (θt−τ ) ∂θ lt−τ ||F || ∂ν lt−τ (θt−τ ) ∂θ rt−τ ||F hold for r < l, thus validating the approximation in Eq. (7) and Eq. (8).
We also study the gradients of non-ResNet models. || ∂ µ l t−τ (θt−τ ) ∂θ l−2t−τ ||F/|| ∂ µ lt−τ (θt−τ ) ∂θ lt−τ ||F and || ∂ν l t−τ (θt−τ ) ∂θ l−2t−τ ||F/|| ∂ν lt−τ (θt−τ ) ∂θ lt−τ ||F on VGG-16 and InceptionV3 are (0.22 and 0.46) and (0.17 and 0.38), respectively, which is similar to ResNet-18 (0.13 and 0.40), indicating that the assumption should also hold for VGG and the Inception series.

Review summaries:
Paper summary: This paper proposes a new normalization technique specially designed for settings with small mini-batch sizes (where previous methods like BatchNorm are known to suffer). The approach aggregates mean/variance statistics from previous iterations, weighted based on the Taylor expansion, to get a better estimate of population statistics. The authors evaluate their approach on ImageNet classification, and object detection and instance segmentation on the COCO dataset.

This paper proposes a novel Cross-Iteration Batch Normalization (CBN) to address the limitation of BN in the case of small mini-batch sizes. Different from existing methods, CBN exploits the statistics cross different iterations to obtain more accurate estimates of the data statistics. Specifically, the proposed CBN uses Taylor polynomials to approximate the statistics using the information of multiple recent iterations. The experiments on both image classification and object detection tasks demonstrate the effectiveness of the proposed method.