Title: POP-NORM: A THEORETICALLY JUSTIFIED AND MORE ACCELERATED NORMALIZATION APPROACH

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.

1. INTRODUCTION:

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 approachremoving the mean of inputs and dividing by the scaled l 2 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.

2. THEORETICAL PREMISES:

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 {x i } n i=1 , the empirical risk as the average of all the samples loss is typically treated as the optimizing objective, i.e.,

EQUATION

where f i (w; x i ) is the loss incurred by the parameter vector w with respect to the i-th sample or mini-batch. Noth that sometimes F (w; {x i } n i=1 ) and f i (w; x i ) may be abbreviated as F (w) and f i (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

w k+1 ← w k -α k+1 ∇f i k (w k ; x i k )

(2) where at the k-th iteration x i k is randomly chosen from the full sets {x i } n i=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 (w 1 ) -∇F (w 2 ) ≤ L w 1 -w 2 .

(3)

An important equality directly induced from Eq. ( 3) is

EQUATION

)

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 (w k ) in Eq. ( 1) is bounded (i.e., ∇F (w k ) ≤ M ≤ ∞), SGD algorithm is applied to optimize F (w k ).

(1) If the leaning rate satisfies

∞ k=1 α k = ∞ and ∞ k=1 α 2 k < ∞, and then K k=0 α k+1 E[ ∇F (w k ) 2 ] K k=0 α k+1 ≤ E[F (w 0 )] -F inf K k=0 α k+1 + L 2 K k=0 α 2 k+1 E[ ∇f i k (w k ) 2 ] K k=0 α k+1 K→∞ ----→ 0,

(5) where F inf = min w F (w) . Then, ∇F (w K ) K→∞ ----→ 0 in probability .

(2) If the leaning rate satisfies1 α k ≥ L and

EQUATION

where

EQUATION

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[∇f i k (w k )] 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)]-F inf K k=0 α k+1 in Eq. (5) (or E[F (w0)]-F inf 1 2 K k=0 α k+1

in Eq. ( 6)) faster to diminish.

However, when the learning rate α k becomes large, the term 6) ) may also become large and the condition 1 α k+1 ≥ L may not be met. Hence reducing the gradient variance V[∇f i k (w k )] 1 and 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.

L 2 K k=1 α 2 k E[ ∇f i k (w k ) 2 ] in Eq. (5) (or K k=0 α k+1 V[∇f i k (w k )] in Eq. (

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[∇f i k (w k )] and gradient Lipschitz constant L.

3. THE PROPOSED APPROACH:

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[∇f i k (w k )] and the gradient Lipschitz constant L simultaneously, therefore the new approach will accelerate the convergence of training and improve the performance.

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 as2 ,

F (m) (w (l) k ) = 1 m m i=1 f i k (w (l) k ; x i k ) = 1 m m i=1 g x (l-1) i k t w (l) k + b (l) k = G (m) X (l-1) (m) k t w l k + B (l) (m) k (8)

where m is the size of mini-batch, and

X (l-1) (m) k = [x (l-1) 1 k ; x (l-1) 2 k ; ...; x (l-1) m k ] and B (l) (m) k = [b (l) 1 k , b (l) 2 k , ..., b (l) m k ]. x (l-1) i k is randomly choose from the entire train set {x (l-1) i k } n

i=1 with equal probability, hence F (w

(l) k ) = 1 n n i=1 f i k (w (l) k ; x (l-1) i k ) is the expectation of F (m) (w l k )( E[F (m) (w l k )] = F (w l k ))

, where n is the total number of train set. Note that Eq. ( 8) also implies that

F (w l k ) = G (X l-1 k ) t w l k + B l k where X l-1 k = [x l-1 1 k ; x l-1 2 k ; ...; x l-1 n k ] and B l k = [b l 1 k , b l 2 k , ..., b l n k ].

For clarity, henceforth we will omit the layer index.

We construct a new normalization approach, referred to as Pre-Operation Normalization (POP-Norm), of which one main characteristic is putting the normalization technique before operation. For a layer fed with a d-dimensional input

x i k = (x [1] i k , x [2] i k ..., x [d]

i k ) , we ideally normalize each dimension with the global estimation of entire samples, i.e.,

EQUATION

where

0 ≤ η [j] ≤ 2, ρ [j] 1 n n i=1 x[j] i k 2 ≥ 1 and x [j] k = (x [j] 1 k , x [j] 2 k , ..., x [j] n k ).

The normalization approach consists of two parts -mean removal and division by l 2 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 x i k 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 ≤ M 1 < ∞ and ∇ 2 G(z) 2 ≤ M 2 < ∞ , we have (1) the upper bound of the gradient variance V[∇f i k (w k ; xi k )] will be lower than that of V[∇f i k (w k ; x i k )].

(2) the upper bound of the minimal gradient Lipschitz constant of

F (w k ; {x i k } n i=1 ) will be lower than that of F (w k ; {x i k } n i=1 );

Theorem 3 (Justification of Division by l 2 Norm in Eq.( 10)) Eq. ( 10) is adopted to handle each input xi k 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 ≤ M 1 < ∞ and ∇ 2 G(z) 2 ≤ M 2 < ∞ , we have (1) the upper bound of the gradient variance V[∇f i k (w k ; xi k )] will be lower than that of V[∇f i k (w k ; xi k )] ;

(2) the upper bound of the minimal gradient Lipschitz constant of

F (w k ; {x i k } n i=1 ) will be lower than that of F (w k ; {x i k } n i=1 ); (3) if F (w k ) is locally convex and maxj ((ρ [j] ) 2 ) (minj (ρ [j] ) 2 ) ≤ maxj n i=1 (x [j] i k ) 2 minj n i=1 (x [j] i k ) 2 , the lower bound of conditional number of ∇ 2 F (w k ; {x i k } n i=1 ) will be lower than that of ∇ 2 F (w k ; {x i k } n i=1

) in the local space. i k 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:

EQUATION

where β [j] and γ [j] are the shift parameter and the scale parameter to be learned, and

κ (≥ 1) is a hyperparameter. If |β [j] | < 1 m m i=1 x [j] i k and |γ [j] | < κ 1 m m i=1 x[j] i k 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] i k = γ [j] x [j] i k -µ [j] + β [j] / 1 m m i=1 x [j] i k -µ [j] 2 where µ = 1 m m i=1 x [j] i k , while for POP-Norm, x[j] i k = γ [j] x [j] i k -µ [j] + β [j] / 1 m m i=1 x [j] i k -µ [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] i k = x [j] i k -1+β [j] m m i=1 x [j]

i k , and the l 2 norm to divide can be substituted by the other norm, such as l 1 norm and l ∞ nrom. Mean removal and division by l 2 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 l 2 norm will lowering the upper bound of V[∇f i k (w k )] 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[∇f i k (w k )] 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[∇f i k (w k )] and L will be proportional to 1 κ 2 , which means the larger κ will be quickly smaller V[∇f i k (w k )] 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 of w 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 ∇ 2 F (w k ) if F (w k ) 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.

4. JUSTIFYING EFFECTIVENESS AND WEAKNESS OF BATCHNORM:

The vanilla BatchNorm has been a standard toolkit for modern deep networks, but the root of Batch-Norm'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. Batch-Norm and POP-norm can be expressed as:

EQUATION

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]

i k } n i=1 are symmetric about zero that can be easy to be satisfied in practice, we have

EQUATION

hence when adopting ReLU as the activation function for BatchNorm, it is equal to taking the step division by l 2 norm with respect to h(x

[j]

i k ) for POP-Norm. In other words, no matter we put normalization before or behind ReLU, division by l 2 norm will be effective. From Remark 2, we know in normalization mean removal and division by l 2 norm can take effects individually and division by l 2 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 l 2 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 l 2 norm, hence performance of BatchNorm with Sigmoid will be seriously deteriorated.

As we analyze in Remark 2, moderately increase the scale of the l 2 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.

5. EXPERIMENTS:



5.1. GENERAL SETTINGS:

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.

5.2. PARAMETER SENSITIVITY ANALYSIS:

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. 

5.3. ABLATION EXPERIMENTS:

As analyzed in Remark 1 in Section 3, mean removal and division by l 2 -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 l 2 -norm works can individually accelerate convergence mainly due to increasing learning rate, and it also implies that division by l 2 -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.

5.4. CLASSIFICATION COMPARISON:

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 POP-Norm 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. 

6. CONCLUSIONS AND DISCUSSIONS:

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.

APPENDIX A. POP-NORM FOR CONVOLUTION:

When the layer is a convolutional layer, the matrix equivalence of a sample with respect to the learning parameter w k is

EQUATION

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 x i k 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

EQUATION

x[j,q]

i k = x[j] i k ρ [j] • 1 ns n i=1 s i=1

x [j,q] i k

2:

, (Division by sclaed l 2 Norm)

B. PROOF OF THEOREM 1

Proof 1 (1) At the k-th iteration, we have

EQUATION

)

We know w k+1 = w k -α k+1 ∇f i k (w k ) in Eq. ( 2), so Eq. ( 20) can be formulated as

EQUATION

)

Since at each iteration the sample or mini-batch is randomly chose from the full set, ∇f i k (w k ) is an unbias estimate of ∇F (w), i.e., E[∇f i k (w)] = ∇F (w). Hence taking expectation on the k-th sample or mini-batch, we have

EQUATION

Rearranging terms yields

EQUATION

Taking the total expectation and summing over 0 to K, we obtain

EQUATION

)

Dividing both sides of Eq. ( 24) with K k=0 α k+1 and combining F inf ≤ F (w k ), we have

EQUATION

)

Since ∇F (w) is bounded, ∇f i k (w) will be bounded, and then E[ ∇f i k (w k ) 2 ] should be also bounded. It is known

∞ k=1 α k = ∞ and ∞ k=1 α 2 k < ∞

, so when K tends to infinity, we abtain

EQUATION

)

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 (w k ) 2 ] > , otherwise when K → ∞, K k=0 α k+1 E[ ∇F (w k ) 2 ] K k=0 α k+1

→ ∞ that contradicts Eq. ( 26). Therefore almost everywhere

EQUATION

)

And then for any ζ > 0,

P[ ∇F (w k ) ] > ζ] = P[ ∇F (w k ) 2 ] > ζ 2 ] ≤ E[ ∇F (w k ) 2 ] ζ 2 K→∞ ----→ 0 (28)

where the inequality holds due to Markov's Inequality, which means ∇F (w K ) K→∞ ----→ 0 in probability.

(2) Since 1 α k ≥ L and Eq. ( 22) holds, we have

EQUATION

)

It is known E[ ∇f i k (w k ) 2 ] = E[ ∇f i k (w k )-F (w) 2 ]+ F (w) 2 = V[ ∇f i k (w k ) ]+ F (w) 2

, so Eq. ( 29) can be reformulated as:

EQUATION

Taking the total expectation and summing over 0 to K, we have

EQUATION

Dividing both sides of Eq. ( 31) with 1 2 K k=0 α k+1 and combining F inf ≤ F (w k ), we have

EQUATION

It is known

∞ k=1 α k = ∞, hence when K → ∞ , we have E[F (w0)]-F inf 1 2 K k=0 α k+1 → 0. We know E[ ∇F (w k ) 2 ] ≥ inf k E[ ∇F (w k ) 2 ] and V[ ∇f i k (w k ) ] ≤ sup k (V[ ∇f i k (w k ) ]

), and then we obtain

EQUATION

and finally we arrive at the desired result.

C. PROOF OF THEOREM 2:

Proof 2 (1). From Eq. (8), we know

EQUATION

hence

EQUATION

where the second inequality holds due to the fact AB 2 ≤ A 2 B 2 , and the third inequality follows ∇g(z) 2 ≤ M 1 < ∞.

Similarly, we conclude that

EQUATION

Recalling Eq. ( 9), we have

EQUATION

From 0 ≤ η [j] ≤ 2 in Eq. ( 9), we know 0 ≤ η [j] (2 -η [j] ) ≤ 1, and then

1 - (E[ x i k ]) 2 E[ x i k 2 ] ≤ E[ xi k 2 ] E[ x i k 2 ] ≤ 1 (38)

Hence we arrive the conclusion that mean removal in Eq. ( 9) will make the upper bound of of gradient variance

V[∇f i k (w k ; xi k )] is lower than that of V[∇f i k (w k ; x i k )].

(2). If Eq. (3) holds, the following inequality can be obtained due to Lagrange Mean Theorem, i.e.,

EQUATION

)

where L inf is the minimal gradient Lipschitz constant .

Following Eq. ( 8), we know

F (w k ; {x i k } n i=1 ) = G (X t k w k + B k )

, and then the Hessian function of

EQUATION

And then we obtain

EQUATION

)

where d is the dimension of each sample x i k and H

[j,j] k are the j-th diagonal element of (X k X 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 ∇ 2 G(z) 2 ≤ M 2 , and the last inequality is due to the fact A 2 ≤ d max j (A [j,j] ) where A ∈ R d×d is positive definite and A [j,j] is the j-th diagonal element.

Similarly, we can derive that

EQUATION

where

H[j,j] k is j-th diagonal element of ( Xk Xt k ) in which Xk is constructed by following X k in Eq. (8).

According to the definition of Xk in Eq. ( 9), H[j,j] k can be reformulated as

EQUATION

From 0 ≤ η [j] ≤ 2 in Eq. ( 9), we know 0 ≤ η [j] (2 -η [j] ) ≤ 1, and then

1 - n i=1 x [j] i k 2 ≤ H[j,j] k H [j,j] k ≤ 1 (44)

Therefore the upper bound of the gradient Lipschitz constant L inf of F (w k ; {x i k } n i=1 ) is lower that of F (w k ; {x i k } n i=1 ).

D. PROOF OF THEOREM 3:

Proof 3 (1)Similar to Eq.(34 -35), it can be also concluded that

EQUATION

According to Eq.( 10), we have

E[ xi k 2 ] = d j=1 E x[j] i k 2 = d j=1 E     x[j] i k ρ [j] • 1 n n i=1 x[j] i k 2 2     = 1 (ρ [j] ) 2 n n i=1

x(j)

i k 2 E[ xi k 2 ]

(46)

Hence,

E[ xi k 2 ] E[ xi k 2 ] = 1 (ρ [j] ) 2 1 1 n n i=1 x(j) i k 2 ≤ 1 (47)

where the inequality holds since (ρ [j] ) 2 n n i=1

x(j)

i k 2 ≥ 1.

Therefore the upper bound of the gradient variance V[∇f i k (w k ; xi k )] will be lowered than that of

V[∇f i k (w k ; xi k )].

(2). Similar to Eq. (35 -40), we conclude

EQUATION

where Ĥ[j,j] k is j-th diagonal element of ( Xk Xt k ) in which Xk is constructed by following X k in Eq. (8).

According to Eq.( 10), we have

EQUATION

)

where the inequality holds since (ρ [j] ) 2 n n i=1

x(j)

i k 2 ≥ 1.

Hence the upper bound of the minimal gradient Lipschitz constant of F (w k ; {x i k } n i=1 ) will be further lowered than that of F (w k ; {x i k } n i=1 ). (3). If F (w k ; {x i k } n i=1 ) is locally strongly convex, the condition num G (z) is also strong convex, and then λ min (G(z))

EQUATION

where λ max (•) is the maximal eigenvalue and λ min (•) is the minimal eigenvalue.

the local space the condition number of ∇ 2 F (c) (w k ; 

{x i k } n i=1 ) is cond(∇ 2 F (w k ; {x i k } n i=1 )) = ∇ 2 F (w k ; {x i k } n i=1 ) 2 ∇ 2 F (w k ; {x i k } n i=1 ) -1 2 = Xk ∇ 2 G Xt k w k + B k Xt k 2 Xk ∇ 2 G Xt k w k + B k Xt k -1 2 = ∇ 2 G Xt k w k + B k Xt k Xk 2 ∇ 2 G Xt k w k + B k -1 ( Xt k Xk ) -

Recalling Eq. ( 10), we obtain

EQUATION

It is known maxj ((ρ [j] ) 2 ) (minj (ρ [j] ) 2 ) ≤ (55)

Finally we arrive the conclusion that the lower bound of conditional number of ∇ 2 F (w k ; {x i k } n i=1 ) will be lowered than that of ∇ 2 F (w k ; {x i k } n i=1 ) in the local space.

:

It is known E[ ∇fi k (w k )

] = V[∇fi k (w k )] + (E[ ∇fi k (w k ) ]) 2 , decreasing V[∇fi k (w k )] will also lower E[ ∇fi k (w k ) 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.

Figures and Tables:

Figure 1: (a) The structure of a standard layer with BatchNorm. (b) The structure of a layer with POP-Norm.

x2

Figure 2: Train Loss for POP-Norm embedded VGG16 with different activation functions on CIFAR100: (a) Sigmoid, (b) Tanh and (c) ReLU.

Mean test accuracy(%) and standard deviation of 10 trials for BatchNorm and POPNorm embedded

Table content: <table><tr><td colspan="3">VGG16 and ResNet20 on CIFAR10 and CIFAR100.</td><td/><td/><td/></tr><tr><td>Model</td><td>Act. Fun.</td><td colspan="2">CIFAR10 BatchNorm POP-Norm</td><td colspan="2">CIFAR100 BatchNorm POP-Norm</td></tr><tr><td/><td>Sigmoid</td><td>84.21 ± 0.46</td><td>90.69 ± 0.15</td><td>62.49 ± 0.56</td><td>70.29 ± 0.14</td></tr><tr><td>VGG16</td><td>Tanh</td><td>88.69 ± 0.15</td><td>90.63 ± 0.09</td><td>66.63 ± 0.12</td><td>70.59 ± 0.09</td></tr><tr><td/><td>ReLU</td><td>90.89 ± 0.13</td><td>92.15 ± 0.11</td><td>70.83 ± 0.25</td><td>71.38 ± 0.12</td></tr><tr><td/><td>Sigmoid</td><td>83.08 ± 0.14</td><td>89.68 ± 0.14</td><td>54.10 ± 0.37</td><td>66.91 ± 0.32</td></tr><tr><td>ResNet20</td><td>Tanh</td><td>88.08 ± 0.11</td><td>89.63 ± 0.09</td><td>62.42 ± 0.36</td><td>67.02 ± 0.10</td></tr><tr><td/><td>ReLU</td><td>90.23 ± 0.13</td><td>90.90 ± 0.12</td><td>66.70 ± 0.16</td><td>67.53 ± 0.12</td></tr></table>

Test accuracy(%) for BatchNorm and POP-Norm embedded ResNet18 on ILSVRC2012. The activa-

Table content: <table><tr><td>tion function is ReLU.</td><td/><td/><td/><td/><td/><td/></tr><tr><td>Model</td><td>top-1</td><td>BatchNorm</td><td>top-5</td><td>top-1</td><td>POP-Norm</td><td>top-5</td></tr><tr><td>ResNet18</td><td>66.81</td><td/><td>87.32</td><td>67.53</td><td/><td>87.95</td></tr></table>

The third equality follows AB 2 = BA 2 ; the forth inequality holds due to the fact AB 2 ≥ 1 d Tr(AB) ≥ λ min (A)λ max (B) if A and B are positive definitive.Similarly, we havecond(∇ 2 F (w k ; {x i k } n i=1 )) ≥ M

Table content: <table><tr><td/><td/><td/><td/><td>1</td><td>2</td></tr><tr><td/><td>≥</td><td colspan="2">λ min (G) λ max (G)</td><td>•</td><td>λ max ( Xk λ min ( Xk Xt Xt k ) k )</td></tr><tr><td/><td colspan="2">≥M</td><td colspan="2">λ max ( Xk λ min ( Xk Xt Xt k ) k )</td></tr><tr><td/><td colspan="2">≥M</td><td>max j min j</td><td>H[j,j] k k H[j,j]</td><td>,</td></tr><tr><td/><td/><td/><td/><td>(52)</td></tr><tr><td>where</td><td>H[j,j]</td><td/><td/></tr><tr><td/><td/><td/><td/><td>max j</td><td>Ĥ[j,j]</td></tr></table>

Peer review (iclr2020):
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. I must first confess that I’m not an expert in the relevant area. I’m don’t know why the reviewing system assigned this paper to me, but I will try my best to judge the value of the paper. Having said that, I don’t have enough background knowledge to evaluate the novelty of the paper. For instance, the Theorem 1 is stated as if it was originally introduced in this paper, without any citation. But I doubt that because I could easily find several results relating the convergence rate of SGD to the gradient Lipschitz constant. Are there any papers or standard textbooks to be noted? If so, please cite them properly. The theorem 2 and 3 are based on the full-dataset statistics, but because they are infeasible in practice, the authors propose to use the batch statistics. How may this affect the theory? Intuitively, one could easily imagine that the smaller batch-size would lead to higher variances for batch statistics estimators, and thus impeding the regularization effect of the normalization. Also, the theory just states that the upper bound of (Lipschitz constant, gradient variance) after normalization will be lower than the lower bound without normalization, so it is not clear how much the normalization would reduce them. If possible please state the detailed results in the main text. The differences between POP-norm and Batch-norm are, 1) whether the normalization is applied before or after the operations, and 2) minor difference in the normalization procedure, such as the additional scaling parameter kappa. The experiments provide results to demonstrate the effectiveness of 1), but not clear about 2). It would be interesting to compare POP-norm to the Batch-norm applied before the operations to see the net effect of 2). The very idea of applying Batch-norm before the convolution operation has already been demonstrated and widely used in the case of ResNet with ReLU activation functions, so if the contribution from 2) is insignificant, I think one may ask the novelty of the proposed normalization scheme. Overall, despite the lack of background knowledge, I find this paper to be borderline, but more close to the reject, because of some unclear points. I would like to hear back from the authors and other reviewers. I don’t understand why the matrix B in eq.8 gathering the biases has additional indices 1_k, …, m_k. Shouldn’t it be the repetition of b_k for m times?