Year: 2019

Abstract:
Batch Normalization (BatchNorm) has been a default module in modern deep networks due to its effectiveness for accelerating training deep neural networks. It is widely accepted that the great success of BatchNorm is owing to reduction of internal covariate shift (ICS), but recently it is demonstrated that the link between them is fairly weak. The intrinsic reason behind the effectiveness of BatchNorm is still unrevealed that limits it to be made better use. In light of this, we propose a new normalization approach, referred to as Pre-Operation Normalization (POP-Norm), which is theoretically ensured to speed up the training convergence. Not surprisingly, POP-Norm and BatchNorm are largely the same. Hence the similarities can help us to theoretically interpret the root of BatchNorm’s effectiveness. There are still some significant distinctions between the two approaches. Just the distinctions make POP-Norm achieve faster convergence rate and better performance than BatchNorm, which are validated in extensive experiments on benchmark datasets: CIFAR10, CIFAR100 and ILSVRC2012.

heading: 1 INTRODUCTION
text: The last decade has witnessed significant advances in deep neural networks (DNN), which brought substantial improvements for many real-world tasks, such as object(Szegedy et al., 2015; He et al., 2015), scene(Khan et al., 2016; Guo et al., 2017) and action recognition(Feichtenhofer et al., 2017), object detection(Ren et al., 2015; He et al., 2017b; Redmon & Farhadi, 2018) and image segmentation(Ronneberger et al., 2015; He et al., 2017a). BatchNorm (Ioffe & Szegedy, 2015) is a milestone technique in the development of DNN, and nowadays it has become a default component to construct modern deep networks. BatchNorm is widely-used in DNN due to that it is able to reduce the sensitivity to initialization, significantly raise the learning rate, substantially speed up the training process and considerably improve the performance. Actually, along with this line a variety of works, such as layer normalization (Ba et al., 2016), instance normalization (Ulyanov et al., 2016), weight normalization(Salimans & Kingma, 2016) and group normalization (Wu & He, 2018), batch renormalization, (Ioffe, 2017) were sequently proposed and also have made great success.
Nowadays, the practical success of BatchNorm is mainly attributed to reduction of internal covariate shift (ICS) by controlling the first two moments (mean and variance) of the distributions of layer inputs. Recently, this point of view is challenged by (Santurkar et al., 2018). It points out that the link between reduction of ICS and performance improvement of BatchNorm is tenuous, at best. However, the success of BatchNorm is indisputable, therefore there may exist a profound mathematical mechanism behind BatchNorm. In fact, from the perspective of loss landscape, (Santurkar et al., 2018) demonstrates BatchNorm will make the optimization landscape smoother, and then this smoothness induces a more predictive and stable behavior of the gradients.
As stated above, the original theoretical foundation of the vanilla BatchNorm is not so solid and the exact reason for its effectiveness is poorly understood, hence BatchNorm maybe not optimal in theory and we might not make better use of it. In light of this, we try to propose a theoretically justified normalization approach for accelerating training deep neural networks, so that we can continuously further algorithmic progress. To achieve this goal, we firstly demonstrate that lowering gradient Lipschitz constant and gradient variance is the key to boost the convergence rate of optimization algorithms with stochastic gradient methods. And then we construct a normalization approach – removing the mean of inputs and dividing by the scaled l2 norm of inputs before conducting the
main operation (convolution or inner-production) of a layer, which can be theoretically ensured to reduce the gradient Lipschitz constant and gradient variance.
The new normalization approach and BatchNorm are similar. Hence we utilize their similarity to interpret the effectiveness of the vanilla BatchNorm, along the line of lowering gradient Lipschitz constant and gradient variance, which is different from the view of the loss landscape (Santurkar et al., 2018). According to our theory, we can easily explain why BatchNorm with ReLU is powerful with but ineffective with Sigmoid and Tanh as activation functions, which may help us to better understand the underlying complexity of neural networks.
The main contributions of this paper are summarized as follows:
• From scratch a theoretically justified normalization approach is deduced for accelerating the convergence speed of training deep neural networks.
• We theoretically explain the root of BatchNorm’s effectiveness and the weakness from the perspective of lowering the gradient variance and gradient Lipschitz constant.
• With the help of the new normalization approach, in extensive experiments the performance for Sigmoid and Tanh achieve massive improvement, and they are even competitive to ReLU.
Our paper is organised as follows. In Section 2, we will deduce the theoretical premises to accelerate stochastic optimization. Then, built on the premise, we will propose a new normalization approach in Section 3. In Section 4, we will analyze the exact root of BatchNorm’s effectiveness. In Section 5, we will implement extensive experiments to demonstrate the superiorly of the new normalization approach. We will summarize our work and discuss further work in Section 6.

heading: 2 THEORETICAL PREMISES
text: In this section, we will theoretically deduce that reduction of gradient Lipschitz constant and gradient variance plays a vitally important role in convergence when applying stochastic gradient descent(SGD) algorithms for machine learning tasks.
In a machine learning task, given a set of samples {xi}ni=1 , the empirical risk as the average of all the samples loss is typically treated as the optimizing objective, i.e.,
F (w) = F (w; {xi}ni=1) = 1
n n∑ i=1 fi(w;xi), (1)
where fi(w;xi) is the loss incurred by the parameter vector w with respect to the i-th sample or mini-batch. Noth that sometimes F (w; {xi}ni=1) and fi(w;xi) may be abbreviated as F (w) and fi(w).
In large-scale machine learning tasks, such as deep learning, we usually choose SGD to minimize the empirical risk in Eq. (1) since its computational cost is cheap. Applying SGD, the parameter update at k-th iteration is wk+1 ← wk − αk+1∇fik(wk;xik) (2) where at the k-th iteration xik is randomly chosen from the full sets {xi}ni=1, and αk+1 is the learning rate.
Convergence guarantee of most gradient-based algorithms including SGD is built upon the assumption of Lipschitz-continuous objective gradients, which is state as follow.
The function F (w) is continuously differentiable and the gradient function of F (w), namely ∇F (w), is Lipschitz continuous with gradient Lipschitz constant L > 0, i.e.,
‖∇F (w1)−∇F (w2)‖ ≤ L‖w1 − w2‖. (3)
An important equality directly induced from Eq. (3) is
F (w2) ≤ F (w1) + 〈∇F (w1), w2 − w1〉+ L
2 ‖w2 − w1‖2. (4)
The proof for it can be found in (Nesterov, 2004; Bottou et al., 2016).
Under the assumption in Eq. (4), we provide convergence analysis in the following for the general objective function Eq. (1) when applying SGD, no matter whether it is convex or not.
Theorem 1 Suppose the assumption in Eq. (4) is satisfied and the gradient of F (wk) in Eq. (1) is bounded (i.e., ∇F (wk) ≤M ≤ ∞), SGD algorithm is applied to optimize F (wk). (1) If the leaning rate satisfies ∑∞ k=1 αk =∞ and ∑∞ k=1 α
2 k <∞, and then∑K
k=0 αk+1E[‖∇F (wk)‖2]∑K k=0 αk+1 ≤ E[F (w0)]− Finf∑K k=0 αk+1 + L 2
∑K k=0 α
2 k+1E[‖∇fik(wk)‖2]∑K k=0 αk+1 K→∞−−−−→ 0,
(5) where Finf = minw F (w) . Then, ‖∇F (wK)‖ K→∞−−−−→ 0 in probability .
(2) If the leaning rate satisfies 1αk ≥ L and ∑∞ k=1 αk =∞, we have∑K
k=0 αk+1E[‖∇F (wk)‖2]∑K k=0 αk+1 ≤ E[F (w0)]− Finf 1 2 ∑K k=0 αk+1 +
∑K k=0 αk+1V[∇fik(wk)]∑K
k=0 αk+1 , (6)
where V[∇fik(wk)] = E[‖∇fik(wk) − E[∇fik(wk)]‖2] that is the gradient variance of fik(wk). When K →∞,
inf k
( E[‖∇F (wk)‖2] ) ≤ sup
k (V[∇fik(wk)]) . (7)
According to the first conclusion of Theorem 1, when the learning rate satisfies ∑∞ k=1 αk =∞ and∑∞
k=1 α 2 k < ∞, we know that SGD algorithm will guarantee the empirical risk function in Eq. (1) converges to a stationary point in probability. The conditions in the second conclusion of Theorem 1 is easier to be met. In this case we should make the the gradient variance V[∇fik(wk)] as smallest as possible to ensure the empirical risk function in Eq. (1) can converge to a good point.
Theorem 1 also implies that increasing learning rate will directly speed up convergence. Since larger αk will make the term
E[F (w0)]−Finf∑K k=0 αk+1 in Eq. (5) (or E[F (w0)]−Finf1 2 ∑K k=0 αk+1 in Eq. (6)) faster to diminish.
However, when the learning rate αk becomes large, the term L2 ∑K k=1 α 2 kE[‖∇fik(wk)‖2] in Eq.
(5) (or ∑K k=0 αk+1V[∇fik(wk)] in Eq. (6) ) may also become large and the condition 1 αk+1
≥ L may not be met. Hence reducing the gradient variance V[∇fik(wk)] 1and the value of Lipschitz constant L is the key to increase the learning rate and accelerate the convergence. It is worth noting that the conclusion that gradient variance reduction is beneficial to accelerate convergence has been demonstrated in (Johnson & Zhang, 2013) when the objective function is convex.
Therefore, if an normalization approach is effective to make Eq. (1) converge to a good point and accelerate the convergence process, it needs to reduce gradient variance V[∇fik(wk)] and gradient Lipschitz constant L.

heading: 3 THE PROPOSED APPROACH
text: In this section, we will present a new normalization approach of which each step will be theoretically proved to be beneficial to reduce the gradient variance V[∇fik(wk)] and the gradient Lipschitz constant L simultaneously, therefore the new approach will accelerate the convergence of training and improve the performance.
1It is known E[‖∇fik (wk)‖ 2] = V[∇fik (wk)] + (E[‖∇fik (wk)‖]) 2, decreasing V[∇fik (wk)] will also lower E[‖∇fik (wk)‖ 2].
When applying mini-batch SGD, at the k-th iteration the empirical risk loss with respect to the weight/bias of the l-th fully-connected layer of DNN can be expressed as 2,
F(m)(w (l) k ) =
1
m m∑ i=1 fik(w (l) k ;xik) = 1 m m∑ i=1 g (( x (l−1) ik )t w (l) k + b (l) k ) = G(m) (( X (l−1) (m)k )t wlk +B (l) (m)k ) (8)
where m is the size of mini-batch, and X(l−1)(m)k = [x (l−1) 1k ;x (l−1) 2k ; ...;x (l−1) mk ] and B (l) (m)k = [b (l) 1k , b (l) 2k , ..., b (l) mk ]. x (l−1) ik is randomly choose from the entire train set {x(l−1)ik } n i=1 with equal probability, hence F (w(l)k ) = 1 n ∑n i=1 fik(w (l) k ;x (l−1) ik
) is the expectation of F(m)(wlk)( E[F(m)(wlk)] = F (wlk)), where n is the total number of train set. Note that Eq. (8) also implies that F (wlk) = G ( (X l−1k ) twlk +B l k ) where X l−1k = [x l−1 1k ;xl−12k ; ...;x l−1 nk ] and Blk = [b l 1k , bl2k , ..., b l nk
]. For clarity, henceforth we will omit the layer index.
We construct a new normalization approach, referred to as Pre-Operation Normalization (POPNorm), of which one main characteristic is putting the normalization technique before operation. For a layer fed with a d-dimensional input xik = (x [1] ik , x [2] ik ..., x [d] ik
) , we ideally normalize each dimension with the global estimation of entire samples, i.e.,
x̄ [j] ik = x [j] ik − η[j] · 1
n n∑ i=1 x [j] ik , (Mean Removal) (9)
x̂ [j] ik
= x̄
[j] ik ρ[j] · √
1 n ∑n i=1 ( x̄ [j] ik )2 = x̄ [j] ik ρ[j]√ n ‖x[j]k ‖2 , (Division by sclaed l2 Norm) (10)
where 0 ≤ η[j] ≤ 2, ρ[j] √
1 n ∑n i=1 ( x̄ [j] ik )2 ≥ 1 and x[j]k = (x [j] 1k , x [j] 2k , ..., x [j] nk).
The normalization approach consists of two parts – mean removal and division by l2 norm. The both steps are actually not interdependent and can individually take effects for decreasing gradient variance and gradient Lipschitz constant. We will theoretically demonstrate it in the following.
Theorem 2 (Justification of Mean Removal in Eq.(9)) Eq. (9) is adopted to handle each input xik of the model in Eq. (8). Suppose assumption in Eq. (3) is satisfied and the gradient and Hessian function of g(z) and G(z) in Eq. (8) is bounded , i.e., ‖∇g(z)‖2 ≤ M1 < ∞ and ‖∇2G(z)‖2 ≤ M2 <∞ , we have (1) the upper bound of the gradient variance V[∇fik(wk; x̄ik)] will be lower than that of V[∇fik(wk;xik)]. (2) the upper bound of the minimal gradient Lipschitz constant of F (wk; {x̄ik}ni=1) will be lower than that of F (wk; {xik}ni=1);
Theorem 3 (Justification of Division by l2 Norm in Eq.(10)) Eq. (10) is adopted to handle each input x̂ik from Eq. (9). Suppose assumption in Eq. (3) is satisfied and the gradient and Hessian function of g(z) and G(z) in Eq. (8) is bounded , i.e., ‖∇g(z)‖2 ≤ M1 < ∞ and ‖∇2G(z)‖2 ≤ M2 <∞ , we have (1) the upper bound of the gradient variance V[∇fik(wk; x̂ik)] will be lower than that of V[∇fik(wk; x̄ik)] ; (2) the upper bound of the minimal gradient Lipschitz constant of F (wk; {x̂ik}ni=1) will be lower than that of F (wk; {x̄ik}ni=1);
(3) if F (wk) is locally convex and maxj((ρ
[j])2)
(minj(ρ[j])2) ≤
maxj (∑n
i=1(x̄ [j] ik
)2 )
minj (∑n
i=1(x̄ [j] ik
)2 ) , the lower bound of conditional
number of ∇2F (wk; {x̂ik}ni=1) will be lower than that of∇2F (wk; {x̄ik}ni=1) in the local space. 2 A convolution layer can be also reformulated to be a matrix form , hence the analysis for convolution layers is similar, but it is still somewhat complicated and we discuss it in the appendix.
Due to the limited space, the proofs of Theorem 2 and Theorem 3 are provided in the appendix. The computation of 1n ∑n i=1 xik and 1 n ∑n i=1 x̄ 2 ik
in Eq.(9 - 10) over the entire training set is impractical when adopting SGD. Therefore, just like the vanilla BatchNorm, each mini-batch produces 1 m ∑n i=1 xik and 1 m ∑n i=1 x̄ 2 ik
as the estimates instead. This implementation will also make all the inputs fully participate in the gradient back-propagation. The vanilla BatchNorm introduces the scale and shift parameter to be learned to restore the presentation power of the network. To make POP-Norm more like the vanilla BatchNorm, we factorize η[j] and ρ[j] into a fixed parameter and a parameter to be learned. In practice POP-Norm is presented as follows:
x̄ [j] ik = x [j] ik − 1 m m∑ i=1 x [j] ik + β[j], (Mean Removal) (11)
x̂ [j] ik
= γ[j]
κ ·
x̄ [j] ik√
1 m ∑m i=1 ( x̄ [j] ik )2 , (Division by scaled l2 Norm) (12) where β[j] and γ[j] are the shift parameter and the scale parameter to be learned, and κ (≥ 1) is a
hyperparameter. If |β[j]| < 1m ∑m i=1 x [j] ik and |γ[j]| < κ √ 1 m ∑m i=1 ( x̄ [j] ik )2 are satisfied, Theorem 2
and Theorem 3 will still hold.
Remark 1. Although the main steps of POP-Norm in Eq.(11 - 12) are similar to the vanilla BatchNorm, they are still slight different, as shown in Figure 1. For BatchNorm, x̂[j]ik =
γ[j] ( x [j] ik − µ[j] + β[j] ) / √ 1 m ∑m i=1 ( x [j] ik − µ[j] )2 where µ = 1m∑mi=1 x[j]ik , while for POP-Norm, x̂[j]ik = γ[j] ( x [j] ik − µ[j] + β[j] ) / √ 1 m ∑m i=1 ( x [j] ik − µ[j] + β[j]
)2. Besides, there are other two significant differences between the proposed POP-Norm and the vanilla BatchNorm – placing normalization before the main operation(convolution and inner-production) and adding a new scale parameter κ. Actually, we deliberately make POP-Norm more like the the vanilla BatchNorm. POP-Norm has other forms, for example, mean removal in Eq.(11) can be x̄[j]ik = x [j] ik − 1+β [j] m ∑m i=1 x [j] ik
, and the l2 norm to divide can be substituted by the other norm, such as l1 norm and l∞ nrom. Mean removal and division by l2 norm of POP-Norm are actually not interdependent and can individually take effects for decreasing gradient variance and gradient Lipschitz constant, and their order can be also exchanged. From the proof of Theorem 2 and Theorem 3, we also know the division by l2 norm will lowering the upper bound of V[∇fik(wk)] and L more substantially than mean removal. Additionally, the theoretical analysis and construction of POP-Norm are generalized, and we can also apply them to construct a new normalization approach to compete with instance normalization (Ulyanov et al., 2016) and group normalization (Wu & He, 2018).
Remark 2. Adding a new parameter κ and setting κ ≥ 1 is more beneficial to decrease the gradient variance and the gradient variance V[∇fik(wk)] and the gradient Lipschitz constant L. When looking into the proof of Theorem 2 and Theorem 3, we can conclude the upper bound of V[∇fik(wk)] and L will be proportional to 1κ2 , which means the larger κ will be quickly smaller V[∇fik(wk)] and L so that speeds up the convergence. However, κ can not be too large, otherwise the value after the operation will be much small, and then it may harm the representation capability of the layer,
since the non-linear activation function will mainly work in the linear regime. Moreover, when κ is too large that will directly make gradient variance much small, and then it is difficult for train loss to escape the trap of early local minimums. In our practices, when κ is moderately large, it will substantially improve the performance, which is demonstrated in the experimental section. Not strictly speaking, adding κ is just make f(w) change to f(wκ ). It seems the optimization trajectory will be the same if we magnify the initial value ofw by an exact factor κ and scale the corresponding learning rate . However, we do not exactly change the initial value and the learning rate, and the optimum is not unique. On the contrary, the number of local minimums of a deep neural network is much large and they scatter throughout all the space. Therefore, adding κ is more likely to help w in the network quickly converge to a local minimum near the initial value according to Theorem 3 rather than along with a far trajectory converge to the original local minimum.
Remark 3. As proved in Theorem 3, adopting the POP-Norm will be conducive to reduction of the condition number of∇2F (wk) if F (wk) is locally convex. Smaller condition number will make the training algorithm avoid the danger of running into a sudden change of the loss such as a flat region or a steep slope, which also enable us to adopt a larger learning rate. In other words, the smaller condition number will make the landscape or convergence trajectory of the loss is more smooth and substantially speed up the training process.

heading: 4 JUSTIFYING EFFECTIVENESS AND WEAKNESS OF BATCHNORM
text: The vanilla BatchNorm has been a standard toolkit for modern deep networks, but the root of BatchNorm’s effectiveness is still vague. The motivation of BatchNorm built on ICS is somewhat heuristic. Actually, in (Santurkar et al., 2018) it demonstrates the link between the performance gain and reduction of ICS is fairly weak, which means the success of BatchNorm may be not owing to ICS. (Santurkar et al., 2018) owes faster training with BatchNorm to the improvement of loss landscape. In this section, we will analyze not only BatchNorm’s effectiveness but also its weakness from the perspective of lowering the gradient variance and gradient Lipschitz constant above.
BatchNorm and POP-Norm are similar, but there are still some significant distinctions between BatchNorm and POPNorm. One of them is putting the normalization before the main operation (convolution and inner-production) for POPNorm. As analyzed in the above subsection, each step of POP-Norm has been theoretically justified. Therefore, we can analyze the influence of differences between BatchNorm and POPNorm to verify the effectiveness and weakness of BatchNorm.
BatchNorm is placed behind the operation of convolution or inner-production and before the nonlinear activation function which is displayed in Figure 1, hence BatchNorm actually takes effect on the operation of the next layer. For simplicity, we omit the shift and scale parameter here. BatchNorm and POP-norm can be expressed as:
x̄ [j] ik = x [j] ik − 1 n n∑ i=1 x [j] ik
(13)
x̂ [j] ik
= x̄ [j] ik√
1 n ∑n i=1 ( x̄ [j] ik )2 (14) x̃
[j] ik = h(x̂ [j] ik ) (15)
where h(·) is a activation function. Due to nonlinearity of the activation function, the benefits of normalization will be impaired. When it is ReLU, the damage will be not so serious. Suppose all samples {x̄[j]ik } n i=1 are symmetric about zero that can be easy to be satisfied in practice, we have
x̃ [j] ik = h ( x̄ [j] ik / √√√√ 1 n n∑ i=1 ( x̄ [j] ik )2) = h(x̄[j]ik )/ √√√√ 2 n n∑ i=1 h2 ( x̄ [j] ik ) , (16)
hence when adopting ReLU as the activation function for BatchNorm, it is equal to taking the step division by l2 norm with respect to h(x̄ [j] ik
) for POP-Norm. In other words, no matter we put normalization before or behind ReLU, division by l2 norm will be effective. From Remark 2, we know
in normalization mean removal and division by l2 norm can take effects individually and division by l2 norm plays a major role and can still substantially reduce the gradient variance and gradient Lipschitz constant. Therefore, the effectivness of BatchNorm with ReLU will be still guaranteed. On the contrary, when the activation function is Tanh, it will damage division by l2 norm and reserve mean removal, but the performance of BatchNorm with Tanh will be still undermined. When the activation function is Sigmoid, it will destroy both of mean removal and division by l2 norm, hence performance of BatchNorm with Sigmoid will be seriously deteriorated.
As we analyze in Remark 2, moderately increase the scale of the l2 norm will be beneficial to decrease the gradient variance and gradient Lipschitz constant. It is known most of activation functions will shrink the value of inputs, and then the value of normalization will become relatively larger, hence from this perspective of view, activation function may be beneficial, but the deterioration brought by distortion of activation functions may be still dominated for BatchNorm with Sigmoid, but BatchNorm with ReLU will be benefited from the declined value of inputs.

heading: 5 EXPERIMENTS

heading: 5.1 GENERAL SETTINGS
text: In the experiments, we first modify each layer in Figure 1(a) to Figure 1(b) for widely-used VGGnets (Karen Simonyan, 2016) and ResNets (He et al., 2016) with POP-Norm, and all other network architecture and parameters were exactly the same with the standard VGG-nets and ResNets, and then we evaluate the standard VGG-nets and ResNets and the new ones on benchmark datasets: CIFRR10, CIFAR100 and ILSVRC2012. It is worth noting that we just want to evaluate the performance and effectiveness of the proposed POPNorm, compared with BatchNorm, rather than pursue the highest accuracy on benchmark datasets, hence we do not adopt much deep networks and complicated tricks.
For the experiments on the datasets CIFAR10 and CIFAR100, the batch size is set as 128. We use a weight of 0.0005 and SGD with a momentum of 0.9. To simplify the tuning process and compare fairly, we identically start with a learning rate of 0.1, divided by 10 at 16k and 24k iterations, and finally terminate at 30k iterations. For the experiments on ILSVRC2012, standard SGD with weight decay of 0.0001 and momentum of 0.9 is adopted. the number of samples in a batch size is set as 256 uniformly distributed on 8 GPUs. The learning rate starts from 0.05 and is divided by 10 at 250k and 450k and 550k iterations, and finally terminate at 600k iterations. The images are first simply resized to 256× 256, and then randomly cropped to 224× 224. No other data augmentation except simple horizontal image flipping is employed.

heading: 5.2 PARAMETER SENSITIVITY ANALYSIS
text: We add a scaling factor κ to magnify the value of normalization for POP-Norm. κ of POP-Norm will greatly influence the effectiveness of POP-Norm. In this subsection, we will evaluate the performance of VGG16 Embedding POP-Norm with different values of scaling factor κ from the candidate set of {1, 4, 16}. As shown in Figure 2(a-c), when κ is moderately large (κ = 4), it is not only beneficial to speed up the training but also help train loss to finally converge to a smaller value. However, if we further increase κ to 16, although the relative convergence speed is accelerated, the training loss is more like to converge to a larger local minimum. The reason for it is just what we analyzed in Remark 2 of Section 3. Overlarge κ will make activation functions (Tanh and Sigmoid), work in the linear regime, which will further harm the representative ability of neural networks, so that it is difficult for training loss to find a better local minimum. Overlarge κwill directly lead to small gradient variance, which will make train loss hard to escape the trap of an early local minimum. κ in POP-Norm will be uniformly set to 4 in the following experiments for better performance.
POP-Norm speed up the convergence through reducing gradient Lipschitz constant (increasing learning rate) and lowering gradient variance. We fix the learning rate in the experiments in this subsection, hence it also experimentally validates reduction of gradient variance is conducive to faster training convergence.

heading: 5.3 ABLATION EXPERIMENTS
text: As analyzed in Remark 1 in Section 3, mean removal and division by l2-norm of POP-Norm can work individually, in this section we will evaluate their performance of VGG16 on CIFAR100 individually and collectively. To better access their performance, we also add VGG with no normalization and BatchNorm as anchors. We set the initial learning rate 0.00005 and 0.005 for no normalization and POP-norm only with mean removal since a higher learning rate will make training diverge. Specifically, when the activation function is Sigmoid, no matter what value the initial learning rate is, no normalization, POP-norm only with mean removal and POP-norm only with division cannot make loss decrease. This phenomenon for no normalization was also reported in (Ioffe & Szegedy, 2015). We guess this may be owing to gradient vanishing, and the mean removal and division together can relief it but each individual component can not. We will explore the exact reason in the future.
As shown in Figure 3, comparing with no normalization, mean removal and division by l2-norm works can individually accelerate convergence mainly due to increasing learning rate, and it also implies that division by l2-norm is more influential than mean removal in POP-Norm, which can validate our analysis in Section 3. Moreover, when adopting ReLU as activation function, the performance of BatchNorm is close to POP-Norm only with division. And when adopting Tanh and Sigmoid, the convergence rate of BatchNorm is much slower than POP-Norm. These phenomenons just follow the analysis in Section 4.

heading: 5.4 CLASSIFICATION COMPARISON
text: In this subsection, we will access the classification performance of BatchNorm and POP-Norm on widely-used CIFAR10, CIFAR100 and ILSVRC2012. The results are reported in Table 1-2.
As displayed in Table 1, the classification accuracy for POP-Norm is consistently higher ( average more than 3%) than BatchNorm. Specifically, when the activation functions are Sigmoid and Tanh,
the improvement of POP-Norm is more obvious, gaining about 8% and 4% respectively, which demonstrates the effectiveness of POP-Norm. It is worth noting that with the help of the proposed POPNorm the performance of the networks with Sigmoid and Tanh is fairly close to the networks with ReLU, which also validates the power of the proposed approach.
Comparing to BatchNorm with ReLU, the performance for BatchNorm with Sigmoid and Tanh is heavily discounted. The reason for it is what we analyzed in Section 4. When the activation function is ReLU, placing BatchNorm behind convolution and inner-production and before activation functions will less influence the performance of normalization, but when adopting Sigmoid or Tanh, this position will have a great impact for the performance of normalization. Therefore, from another aspect, it verifies the importance of putting normalization before convolution and inner-production.
We also implement classification experiments on ILSVRC2012. As shown in Tabel 2, POP-Norm achieves about 0.8% higher classification accuracy than BatchNorm, which demonstrates POPNorm is also effective in large-scale datasets. Due to the limited time, we did not utilize deeper networks to evaluate BatchNorm and POP-Norm. We will report more results of deeper networks in future.

heading: 6 CONCLUSIONS AND DISCUSSIONS
text: In this paper we try to propose a theoretically justified and effective normalization approach. To achieve this goal, we first deduce that lowing gradient variance and gradient Lipschitz constant is the key to speed up the convergence when adopting SGD. And then we present a new normalization approach, of which each step is theoretically proven to be beneficial to reduce gradient variance and gradient Lipschitz constant. POP-Norm and BatchNorm are largely the same, which just help us to explain the effectiveness of BatchNorm. Besides the form of POP-Norm is slightly different from BatchNorm, there are two other differences between the two normalization methods. One difference is that the proposed method place the normalization ahead of the main operation of a layer rather than behind it. Another is that the proposed method adds a scaling factor to increase the value of normalization. Just the differences make our normalization approach more powerful, which is then validated by extensive experiments on benchmark datasets. Moreover, POP-Norm can have other forms that are much different from BatchNorm, and the principle of POP-Norm can be also applied to instance normalization and group normalization.

heading: A. POP-NORM FOR CONVOLUTION
text: When the layer is a convolutional layer, the matrix equivalence of a sample with respect to the learning parameter wk is
xik =  0 0 ... 0 x [1,1] ik
... 0 ... 0 x [d,1] ik
0 0 ... x [1,1] ik
x [1,2] ik
... 0 ... x [d,1] ik
x [d,2] ik
... ... ... ... ... ... ... ... ... ...
x [1,1] ik
x [1,2] ik ... x [1,r−1] ik
x [1,r] ik
... x [d,1] ik
... x [d,r−1] ik
x [d,r] ik
x [1,2] ik
x [1,3] ik ... x [1,r] ik
x [1,r+1] ik ... x [1,2] ik
... x [d,r] ik
x [d,r+1] ik
... ... ... ... ... ... ... ... ... ...
x [1,s−1] ik x [1,s] ik ... 0 0 ... x [1,s−1] ik ... 0 0
x [1,s] ik
0 ... 0 0 ... x [d,s] ik
... 0 0
 ,
(17)
where the number of channels is d, the number of spatial dimensions is s, the size of kernel is r. To make the expression legible, we present the matrix equivalence of input with one-dimensional spatial locations. Actually, when s = 1 and r = 1, the convolution layer is degraded to a fully-connected layer.
Theorem 2 and Theorem 3 require each row vector of xik in a convolutional should be considered as a atom that is like a sample in a fully-connected layer, so POP-Norm for a convolution layer is
x̄ [j,q] ik = x [j] ik − η[j] · 1
ns n∑ i=1 s∑ q=1 x [j,q] ik , (Mean Removal) (18)
x̂ [j,q] ik
= x̄
[j] ik ρ[j] · √
1 ns ∑n i=1 ∑s i=1 ( x̄ [j,q] ik )2 , (Division by sclaed l2 Norm) (19)

heading: B. PROOF OF THEOREM 1
text: Proof 1 (1) At the k-th iteration, we have
F (wk+1) ≤ F (wk) + 〈∇F (wk), wk+1 − wk〉+ L
2 ‖wk+1 − wk‖2. (20)
We know wk+1 = wk − αk+1∇fik(wk) in Eq. (2), so Eq. (20) can be formulated as
F (wk+1) ≤ F (wk)− αk+1 〈∇F (wk),∇fik(wk)〉+ Lα2k+1
2 ‖∇fik(wk)‖2. (21)
Since at each iteration the sample or mini-batch is randomly chose from the full set, ∇fik(wk) is an unbias estimate of ∇F (w), i.e., E[∇fik(w)] = ∇F (w). Hence taking expectation on the k-th sample or mini-batch, we have
E[F (wk+1)] ≤ F (wk)− αk+1‖∇F (w)‖2 + Lα2k+1
2 E[‖∇fik(wk)‖2]. (22)
Rearranging terms yields
αk+1‖∇F (w)‖2 ≤ F (wk)− E[F (wk+1)] + Lα2k+1
2 E[‖∇fik(wk)‖2], (23)
Taking the total expectation and summing over 0 to K, we obtain K∑ k=0 αk+1E[‖∇F (wk)‖2] ≤ E[F (w0)]− E[F (WK+1)] + L 2 K∑ k=0 α2k+1E[‖∇fik(wk)‖2]. (24)
Dividing both sides of Eq. (24) with ∑K k=0 αk+1 and combining Finf ≤ F (wk), we have∑K
k=0 αk+1E[‖∇F (wk)‖2]∑K k=0 αk+1 ≤ E[F (w0)]− Finf∑K k=0 αk+1 + L 2
∑K k=0 α
2 k+1E[‖∇fik(wk)‖2]∑K k=0 αk+1 . (25)
Since ∇F (w) is bounded, ∇fik(w) will be bounded, and then E[‖∇fik(wk)‖2] should be also bounded. It is known ∑∞ k=1 αk =∞ and ∑∞ k=1 α
2 k <∞, so when K tends to infinity, we abtain∑K
k=0 αk+1E[‖∇F (wk)‖2]∑K k=0 αk+1 K→∞−−−−→ 0. (26)
It is known that ∑∞ k=1 αk = ∞, hence for any > 0, there should exists a number N ∈ N, so only sparse numbers k > N satisfies that E[‖∇F (wk)‖2] > , otherwise when K → ∞,∑K k=0 αk+1E[‖∇F (wk)‖
2]∑K k=0 αk+1 →∞ that contradicts Eq. (26). Therefore almost everywhere
E[‖∇F (wk)‖2] K→∞−−−−→ 0. (27)
And then for any ζ > 0,
P[‖∇F (wk)‖] > ζ] = P[‖∇F (wk)‖2] > ζ2] ≤ E[‖∇F (wk)‖2]
ζ2 K→∞−−−−→ 0 (28)
where the inequality holds due to Markov’s Inequality, which means ‖∇F (wK)‖ K→∞−−−−→ 0 in probability.
(2) Since 1αk ≥ L and Eq. (22) holds, we have
E[F (wk+1)] ≤ F (wk)− αk+1‖∇F (w)‖2 + αk+1
2 E[‖∇fik(wk)‖2]. (29)

heading: It is known E[‖∇fik(wk)‖2] = E[‖∇fik(wk)−F (w)‖2]+‖F (w)‖2 = V[‖∇fik(wk)‖]+‖F (w)‖2,
text: so Eq. (29) can be reformulated as:
αk+1 2 ‖∇F (w)‖2 ≤ F (wk)− E[F (wk+1)] + Lα2k+1 2 V[‖∇fik(wk)‖] (30)
Taking the total expectation and summing over 0 to K, we have
1
2 K∑ k=0 αk+1E[‖∇F (wk)‖2] ≤ E[F (w0)]− E[F (WK+1)] + K∑ k=0 αk+1 2 V[‖∇fik(wk)‖]. (31)
Dividing both sides of Eq. (31) with 12 ∑K k=0 αk+1 and combining Finf ≤ F (wk), we have∑K
k=0 αk+1E[‖∇F (wk)‖2]∑K k=0 αk+1 ≤ E[F (w0)]− Finf 1 2 ∑K k=0 αk+1 +
∑K k=0 αk+1V[‖∇fik(wk)‖]∑K
k=0 αk+1 , (32)
It is known ∑∞ k=1 αk = ∞, hence when K →∞ , we have
E[F (w0)]−Finf 1 2 ∑K k=0 αk+1
→ 0. We know E[‖∇F (wk)‖2] ≥ infk ( E[‖∇F (wk)‖2] ) and V[‖∇fik(wk)‖] ≤ supk (V[‖∇fik(wk)‖]), and then we obtain
inf k
( E[‖∇F (wk)‖2] ) ≤ sup
k (V[‖∇fik(wk)‖]) , (33)
and finally we arrive at the desired result.

heading: C. PROOF OF THEOREM 2
text: Proof 2 (1). From Eq. (8), we know fik(wk;xik) = g ((xik)twk + bk), and then ∇fik(wk;xik) = xik∇g ( (xik) twk + bk ) , (34)
hence V [‖∇fik(wk;xik)‖] =E [ ‖∇fik(wk;xik)‖2 ] − (E [‖∇fik(wk;xik)‖]) 2
≤E [ ‖∇fik(wk;xik)‖2 ] =E [ ‖xik∇g ( (xik) twk + bk ) ‖2 ]
≤E [ ‖xik‖2‖∇g ( (xik) twk + bk ) ‖2 ]
≤M1E[‖xik‖2],
(35)
where the second inequality holds due to the fact ‖AB‖2 ≤ ‖A‖2‖B‖2, and the third inequality follows ‖∇g(z)‖2 ≤M1 <∞. Similarly, we conclude that
V [‖∇fik(wk; x̄ik)‖] ≤M1E[‖x̄ik‖2] (36)
Recalling Eq. (9), we have
E[‖x̄ik‖2] = E  d∑ j=1 ∥∥∥x̄[j]ik ∥∥∥2  = d∑ j=1 E [∥∥∥x̄[j]ik ∥∥∥2]
= d∑ j=1 E ∥∥∥∥∥x[j]ik − η[j]n n∑ i=1 x [j] ik ∥∥∥∥∥ 2 
= d∑ j=1 E [∥∥∥x[j]ik − η[j]E [x[j]ik ]∥∥∥2]
= d∑ j=1 ( E [∥∥∥x[j]ik ∥∥∥2]− η[j](2− η[j])(E [∥∥∥x[j]ik ∥∥∥])2) =E[‖xik‖2]− d∑ j=1 η[j](2− η[j]) ( E [∥∥∥x[j]ik ∥∥∥])2 ,
(37)
From 0 ≤ η[j] ≤ 2 in Eq. (9), we know 0 ≤ η[j](2− η[j]) ≤ 1, and then
1− (E[‖xik‖]) 2 E[‖xik‖2] ≤ E[‖x̄ik‖ 2] E[‖xik‖2] ≤ 1 (38)
Hence we arrive the conclusion that mean removal in Eq. (9) will make the upper bound of of gradient variance V[∇fik(wk; x̄ik)] is lower than that of V[∇fik(wk;xik)]. (2). If Eq. (3) holds, the following inequality can be obtained due to Lagrange Mean Theorem, i.e.,
Linf = ‖∇2F (wk; {xik}ni=1) ‖2, (39)
where Linf is the minimal gradient Lipschitz constant .
Following Eq. (8), we know F (wk; {x̄ik}ni=1) = G (Xtkwk +Bk), and then the Hessian function of F (wk) is
∇2F (wk; {xik}ni=1) = Xk∇2G ( Xtkwk +Bk ) Xtk. (40)
And then we obtain
‖∇2F (wk; {xik}ni=1) ‖2 = ∥∥Xk∇2G (Xtkwk +Bk)Xtk∥∥2
= ∥∥∇2G (Xtkwk +Bk)XtkXk∥∥2 ≤ ∥∥∇2G (Xtkwk +Bk)∥∥2 ∥∥XtkXk∥∥2
= ∥∥∇2G (Xtkwk +Bk)∥∥2 ∥∥XkXtk∥∥2 ≤M2
∥∥XkXtk∥∥2 ≤M2dmax
j
( H
[j,j] k
) ,
(41)
where d is the dimension of each sample xik and H [j,j] k are the j-th diagonal element of (XkX t k); the second and fourth equalities hold due to the fact ‖AB‖2 = ‖BA‖2 ; the third inequality follows ‖AB‖2 ≤ ‖A‖2‖B‖2; the fifth inequality is owing to ‖∇2G(z)‖2 ≤ M2, and the last inequality is due to the fact ‖A‖2 ≤ dmaxj(A[j,j]) where A ∈ Rd×d is positive definite and A[j,j] is the j-th diagonal element.
Similarly, we can derive that
‖∇2F (wk; {x̄ik}ni=1) ‖2 ≤M2dmax j
( H̄
[j,j] k
) , (42)
where H̄ [j,j]k is j-th diagonal element of (X̄kX̄ t k) in which X̄k is constructed by following Xk in Eq. (8).
According to the definition of X̄k in Eq. (9), H̄ [j,j] k can be reformulated as
H̄ [j,j] k = n∑ i=1 ( x̄ [j] ik )2 = n∑ i=1 ( x [j] ik − η [j] n n∑ i=1 x [j] ik )2
= n∑ i=1 ( x [j] ik )2 − η [j](2− η[j]) n ( n∑ i=1 x [j] ik )2
=H [j,j] k − η[j](2− η[j]) n ( n∑ i=1 x [j] ik
)2 (43)
From 0 ≤ η[j] ≤ 2 in Eq. (9), we know 0 ≤ η[j](2− η[j]) ≤ 1, and then
1− ( n∑ i=1 x [j] ik )2 ≤ H̄ [j,j] k H [j,j] k ≤ 1 (44)
Therefore the upper bound of the gradient Lipschitz constant Linf of F (wk; {x̄ik}ni=1) is lower that of F (wk; {xik}ni=1).

heading: D. PROOF OF THEOREM 3
text: Proof 3 (1)Similar to Eq.(34 - 35), it can be also concluded that
V [∇fik(wk; x̂ik)] ≤M1E[‖x̂ik‖2] (45)
According to Eq.(10), we have
E[‖x̂ik‖2] = d∑ j=1 E [∥∥∥x̂[j]ik ∥∥∥2]
= d∑ j=1 E  ∥∥∥∥∥∥∥∥
x̄ [j] ik ρ[j] · √
1 n ∑n i=1 ( x̄ [j] ik )2 ∥∥∥∥∥∥∥∥ 2 = 1
(ρ[j])2
n ∑n i=1 ( x̄ (j) ik
)2E[‖x̄ik‖2] (46)
Hence,
E[‖x̂ik‖2] E[‖x̄ik‖2] = 1 (ρ[j])2 1
1 n ∑n i=1 ( x̄ (j) ik )2 ≤ 1 (47)
where the inequality holds since (ρ [j])2
n ∑n i=1 ( x̄ (j) ik )2 ≥ 1.
Therefore the upper bound of the gradient variance V[∇fik(wk; x̂ik)] will be lowered than that of V[∇fik(wk; x̄ik)]. (2). Similar to Eq. (35 - 40), we conclude
‖∇2F (wk; {x̂ik}ni=1) ‖2 ≤M2dmax j
( Ĥ
[j,j] k
) , (48)
where Ĥ [j,j]k is j-th diagonal element of (X̂kX̂ t k) in which X̂k is constructed by following Xk in Eq. (8).
According to Eq.(10), we have
Ĥ [j,j] k = n∑ i=1 ( x̂ [j] ik )2 = n∑ i=1  x̄[j]ik ρ[j] · √ 1 n ∑n i=1 ( x̄ [j] ik )2  2
(49)
Hence,
Ĥ [j,j] k H̄ [j,j] k = 1 (ρ[j])2 1
1 n ∑n i=1 ( x̄ (j) ik )2 ≤ 1, (50) where the inequality holds since (ρ [j])2
n ∑n i=1 ( x̄ (j) ik )2 ≥ 1.
Hence the upper bound of the minimal gradient Lipschitz constant of F (wk; {x̂ik}ni=1) will be further lowered than that of F (wk; {x̄ik}ni=1). (3). If F (wk; {x̄ik}ni=1) is locally strongly convex, the condition num G (z) is also strong convex, and then
λmin(G(z)) λmax(G(z)) > M > 0, (51)
where λmax(·) is the maximal eigenvalue and λmin(·) is the minimal eigenvalue.
the local space the condition number of∇2F(c)(wk; {x̄ik}ni=1) is
cond(∇2F (wk; {x̄ik}ni=1)) =‖∇2F (wk; {x̄ik}ni=1) ‖2‖ ( ∇2F (wk; {x̄ik}ni=1) )−1 ‖2 =‖X̄k∇2G ( X̄tkwk +Bk ) X̄tk‖2‖ ( X̄k∇2G ( X̄tkwk +Bk ) X̄tk )−1 ‖2
=‖∇2G ( X̄tkwk +Bk ) X̄tkX̄k‖2‖∇2 ( G ( X̄tkwk +Bk ))−1 (X̄tkX̄k) −1‖2
≥ λmin(G) λmax(G) · λmax(X̄kX̄ t k) λmin(X̄kX̄tk) ≥Mλmax(X̄kX̄ t k)
λmin(X̄kX̄tk)
≥M maxj
( H̄
[j,j] k ) minj ( H̄ [j,j] k
) , (52)
where H̄ [j,j]k is the j-th diagonal element of (X̄kX̄ t k); The third equality follows ‖AB‖2 = ‖BA‖2; the forth inequality holds due to the fact ‖AB‖2 ≥ 1dTr(AB) ≥ λmin(A)λmax(B) if A and B are positive definitive.
Similarly, we have
cond(∇2F (wk; {x̂ik}ni=1)) ≥M maxj
( Ĥ
[j,j] k ) minj ( Ĥ [j,j] k
) (53) Recalling Eq. (10), we obtain
Ĥ [j,j] k = n∑ i=1 ( x̂ [j] ik )2 = n∑ i=1  x̄[j]ik ρ[j] · √ 1 n ∑n i=1 ( x̄ [j] ik )2  2 = (ρ[j])2 (54)
It is known maxj((ρ [j])2)
(minj(ρ[j])2) ≤
maxj (∑n
i=1(x̄ [j] ik
)2 )
minj (∑n
i=1(x̄ [j] ik
)2 ) = maxj
( H̄
[j,j] k ) minj ( H̄ [j,j] k
) , hence we have maxj ( Ĥ [j,j] k
) minj ( Ĥ [j,j] k ) ≤ maxj ( H̄ [j,j] k ) minj ( H̄ [j,j] k
) . (55) Finally we arrive the conclusion that the lower bound of conditional number of∇2F (wk; {x̂ik}ni=1) will be lowered than that of∇2F (wk; {x̄ik}ni=1) in the local space.

Review summaries:
This paper proposes Pre-OPeration Normalization (POP-norm) as a theoretically grounded modification of batch normalization (Batch-norm). The authors provide an analysis of stochastic gradient descent (SGD) showing that the convergence can be accelerated by lowering the gradient Lipschitz constant and gradient variances. Based on this observation, the authors show that by applying POP-norm which is quite similar to the Batch-norm applied before the activation functions, the gradient Lipschitz constants and the gradient variances can be lowered.