Batch normalization

Last updated December 26, 2024

The reasons behind the effectiveness of batch normalization remain under discussion. It was believed that it can mitigate the problem of internal covariate shift, where parameter initialization and changes in the distribution of the inputs of each layer affect the learning rate of the network.^[1] Recently, some scholars have argued that batch normalization does not reduce internal covariate shift, but rather smooths the objective function, which in turn improves the performance.^[2] However, at initialization, batch normalization in fact induces severe gradient explosion in deep networks, which is only alleviated by skip connections in residual networks.^[3] Others maintain that batch normalization achieves length-direction decoupling, and thereby accelerates neural networks.^[4]

Internal covariate shift

Each layer of a neural network has inputs with a corresponding distribution, which is affected during the training process by the randomness in the parameter initialization and the randomness in the input data. The effect of these sources of randomness on the distribution of the inputs to internal layers during training is described as internal covariate shift. Although a clear-cut precise definition seems to be missing, the phenomenon observed in experiments is the change on means and variances of the inputs to internal layers during training.

Batch normalization was initially proposed to mitigate internal covariate shift.^[1] During the training stage of networks, as the parameters of the preceding layers change, the distribution of inputs to the current layer changes accordingly, such that the current layer needs to constantly readjust to new distributions. This problem is especially severe for deep networks, because small changes in shallower hidden layers will be amplified as they propagate within the network, resulting in significant shift in deeper hidden layers. Therefore, the method of batch normalization is proposed to reduce these unwanted shifts to speed up training and to produce more reliable models.

Besides reducing internal covariate shift, batch normalization is believed to introduce many other benefits. With this additional operation, the network can use higher learning rate without vanishing or exploding gradients. Furthermore, batch normalization seems to have a regularizing effect such that the network improves its generalization properties, and it is thus unnecessary to use dropout to mitigate overfitting. It has also been observed that the network becomes more robust to different initialization schemes and learning rates while using batch normalization.

Procedures

Transformation

In a neural network, batch normalization is achieved through a normalization step that fixes the means and variances of each layer's inputs. Ideally, the normalization would be conducted over the entire training set, but to use this step jointly with stochastic optimization methods, it is impractical to use the global information. Thus, normalization is restrained to each mini-batch in the training process.

Let us use B to denote a mini-batch of size m of the entire training set. The empirical mean and variance of B could thus be denoted as

$\mu _{B}={\frac {1}{m}}\sum _{i=1}^{m}x_{i}$ and $\sigma _{B}^{2}={\frac {1}{m}}\sum _{i=1}^{m}(x_{i}-\mu _{B})^{2}$ .

For a layer of the network with d-dimensional input, $x=(x^{(1)},...,x^{(d)})$ , each dimension of its input is then normalized (i.e. re-centered and re-scaled) separately,

${\hat {x}}_{i}^{(k)}={\frac {x_{i}^{(k)}-\mu _{B}^{(k)}}{\sqrt {\left(\sigma _{B}^{(k)}\right)^{2}+\epsilon }}}$ , where $k\in [1,d]$ and $i\in [1,m]$ ; $\mu _{B}^{(k)}$ and $\sigma _{B}^{(k)}$ are the per-dimension mean and standard deviation, respectively.

$\epsilon$ is added in the denominator for numerical stability and is an arbitrarily small constant. The resulting normalized activation ${\hat {x}}^{(k)}$ have zero mean and unit variance, if $\epsilon$ is not taken into account. To restore the representation power of the network, a transformation step then follows as

$y_{i}^{(k)}=\gamma ^{(k)}{\hat {x}}_{i}^{(k)}+\beta ^{(k)}$ ,

where the parameters $\gamma ^{(k)}$ and $\beta ^{(k)}$ are subsequently learned in the optimization process.

Formally, the operation that implements batch normalization is a transform $BN_{\gamma ^{(k)},\beta ^{(k)}}:x_{1...m}^{(k)}\rightarrow y_{1...m}^{(k)}$ called the Batch Normalizing transform. The output of the BN transform $y^{(k)}=BN_{\gamma ^{(k)},\beta ^{(k)}}(x^{(k)})$ is then passed to other network layers, while the normalized output ${\hat {x}}_{i}^{(k)}$ remains internal to the current layer.

Backpropagation

The described BN transform is a differentiable operation, and the gradient of the loss l with respect to the different parameters can be computed directly with the chain rule.

Specifically, ${\frac {\partial l}{\partial y_{i}^{(k)}}}$ depends on the choice of activation function, and the gradient against other parameters could be expressed as a function of ${\frac {\partial l}{\partial y_{i}^{(k)}}}$ :

${\frac {\partial l}{\partial {\hat {x}}_{i}^{(k)}}}={\frac {\partial l}{\partial y_{i}^{(k)}}}\gamma ^{(k)}$ ,

${\frac {\partial l}{\partial \gamma ^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}{\hat {x}}_{i}^{(k)}$ , ${\frac {\partial l}{\partial \beta ^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}$ ,
${\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}(x_{i}^{(k)}-\mu _{B}^{(k)})\left(-{\frac {\gamma ^{(k)}}{2}}(\sigma _{B}^{(k)^{2}}+\epsilon )^{-3/2}\right)$ , ${\frac {\partial l}{\partial \mu _{B}^{(k)}}}=\sum _{i=1}^{m}{\frac {\partial l}{\partial y_{i}^{(k)}}}{\frac {-\gamma ^{(k)}}{\sqrt {\sigma _{B}^{(k)^{2}}+\epsilon }}}+{\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}{\frac {1}{m}}\sum _{i=1}^{m}(-2)\cdot (x_{i}^{(k)}-\mu _{B}^{(k)})$ ,

and ${\frac {\partial l}{\partial x_{i}^{(k)}}}={\frac {\partial l}{\partial {\hat {x}}_{i}^{(k)}}}{\frac {1}{\sqrt {\sigma _{B}^{(k)^{2}}+\epsilon }}}+{\frac {\partial l}{\partial \sigma _{B}^{(k)^{2}}}}{\frac {2(x_{i}^{(k)}-\mu _{B}^{(k)})}{m}}+{\frac {\partial l}{\partial \mu _{B}^{(k)}}}{\frac {1}{m}}$ .

Inference

During the training stage, the normalization steps depend on the mini-batches to ensure efficient and reliable training. However, in the inference stage, this dependence is not useful any more. Instead, the normalization step in this stage is computed with the population statistics such that the output could depend on the input in a deterministic manner. The population mean, $E[x^{(k)}]$ , and variance, $\operatorname {Var} [x^{(k)}]$ , are computed as:

$E[x^{(k)}]=E_{B}[\mu _{B}^{(k)}]$ , and $\operatorname {Var} [x^{(k)}]={\frac {m}{m-1}}E_{B}[\left(\sigma _{B}^{(k)}\right)^{2}]$ .

The population statistics thus is a complete representation of the mini-batches.

The BN transform in the inference step thus becomes

$y^{(k)}=BN_{\gamma ^{(k)},\beta ^{(k)}}^{\text{inf}}(x^{(k)})=\gamma ^{(k)}{\frac {x^{(k)}-E[x^{(k)}]}{\sqrt {\operatorname {Var} [x^{(k)}]+\epsilon }}}+\beta ^{(k)}$ ,

where $y^{(k)}$ is passed on to future layers instead of $x^{(k)}$ . Since the parameters are fixed in this transformation, the batch normalization procedure is essentially applying a linear transform to the activation.

Theory

Although batch normalization has become popular due to its strong empirical performance, the working mechanism of the method is not yet well-understood. The explanation made in the original paper^[1] was that batch norm works by reducing internal covariate shift, but this has been challenged by more recent work. One experiment^[2] trained a VGG-16 network^[5] under 3 different training regimes: standard (no batch norm), batch norm, and batch norm with noise added to each layer during training. In the third model, the noise has non-zero mean and non-unit variance, i.e. it explicitly introduces covariate shift. Despite this, it showed similar accuracy to the second model, and both performed better than the first, suggesting that covariate shift is not the reason that batch norm improves performance.

Using batch normalization causes the items in a batch to no longer be iid, which can lead to difficulties in training due to lower quality gradient estimation.^[6]

Smoothness

One alternative explanation,^[2] is that the improvement with batch normalization is instead due to it producing a smoother parameter space and smoother gradients, as formalized by a smaller Lipschitz constant.

Consider two identical networks, one contains batch normalization layers and the other does not, the behaviors of these two networks are then compared. Denote the loss functions as ${\hat {L}}$ and $L$ , respectively. Let the input to both networks be $x$ , and the output be $y$ , for which $y=Wx$ , where $W$ is the layer weights. For the second network, $y$ additionally goes through a batch normalization layer. Denote the normalized activation as ${\hat {y}}$ , which has zero mean and unit variance. Let the transformed activation be $z=\gamma {\hat {y}}+\beta$ , and suppose $\gamma$ and $\beta$ are constants. Finally, denote the standard deviation over a mini-batch ${\hat {y_{j}}}\in \mathbb {R} ^{m}$ as $\sigma _{j}$ .

First, it can be shown that the gradient magnitude of a batch normalized network, $||\triangledown _{y_{i}}{\hat {L}}||$ , is bounded, with the bound expressed as

$||\triangledown _{y_{i}}{\hat {L}}||^{2}\leq {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}{\Bigg (}||\triangledown _{y_{i}}L||^{2}-{\frac {1}{m}}\langle 1,\triangledown _{y_{i}}L\rangle ^{2}-{\frac {1}{m}}\langle \triangledown _{y_{i}}L,{\hat {y}}_{j}\rangle ^{2}{\bigg )}$ .

Since the gradient magnitude represents the Lipschitzness of the loss, this relationship indicates that a batch normalized network could achieve greater Lipschitzness comparatively. Notice that the bound gets tighter when the gradient $\triangledown _{y_{i}}{\hat {L}}$ correlates with the activation ${\hat {y_{i}}}$ , which is a common phenomena. The scaling of ${\frac {\gamma ^{2}}{\sigma _{j}^{2}}}$ is also significant, since the variance is often large.

Secondly, the quadratic form of the loss Hessian with respect to activation in the gradient direction can be bounded as

$(\triangledown _{y_{j}}{\hat {L}})^{T}{\frac {\partial {\hat {L}}}{\partial y_{j}\partial y_{j}}}(\triangledown _{y_{j}}{\hat {L}})\leq {\frac {\gamma ^{2}}{\sigma ^{2}}}{\bigg (}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg )}^{T}{\bigg (}{\frac {\partial L}{\partial y_{j}\partial y_{j}}}{\bigg )}{\bigg (}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg )}-{\frac {\gamma }{m\sigma ^{2}}}\langle \triangledown _{y_{j}}L,{\hat {y_{j}}}\rangle {\bigg |}{\bigg |}{\frac {\partial {\hat {L}}}{\partial y_{j}}}{\bigg |}{\bigg |}^{2}$ .

The scaling of ${\frac {\gamma ^{2}}{\sigma _{j}^{2}}}$ indicates that the loss Hessian is resilient to the mini-batch variance, whereas the second term on the right hand side suggests that it becomes smoother when the Hessian and the inner product are non-negative. If the loss is locally convex, then the Hessian is positive semi-definite, while the inner product is positive if ${\hat {g_{j}}}$ is in the direction towards the minimum of the loss. It could thus be concluded from this inequality that the gradient generally becomes more predictive with the batch normalization layer.

It then follows to translate the bounds related to the loss with respect to the normalized activation to a bound on the loss with respect to the network weights:

${\hat {g_{j}}}\leq {\frac {\gamma ^{2}}{\sigma _{j}^{2}}}(g_{j}^{2}-m\mu _{g_{j}}^{2}-\lambda ^{2}\langle \triangledown _{y_{j}}L,{\hat {y}}_{j}\rangle ^{2})$ , where $g_{j}=max_{||X||\leq \lambda }||\triangledown _{W}L||^{2}$ and ${\hat {g}}_{j}=max_{||X||\leq \lambda }||\triangledown _{W}{\hat {L}}||^{2}$ .

In addition to the smoother landscape, it is further shown that batch normalization could result in a better initialization with the following inequality:

$||W_{0}-{\hat {W}}^{*}||^{2}\leq ||W_{0}-W^{*}||^{2}-{\frac {1}{||W^{*}||^{2}}}(||W^{*}||^{2}-\langle W^{*},W_{0}\rangle )^{2}$ , where $W^{*}$ and ${\hat {W}}^{*}$ are the local optimal weights for the two networks, respectively.

Some scholars argue that the above analysis cannot fully capture the performance of batch normalization, because the proof only concerns the largest eigenvalue, or equivalently, one direction in the landscape at all points. It is suggested that the complete eigenspectrum needs to be taken into account to make a conclusive analysis.^[4]

^[2]

Measure

Since it is hypothesized that batch normalization layers could reduce internal covariate shift, an experiment^{[ citation needed ]} is set up to measure quantitatively how much covariate shift is reduced. First, the notion of internal covariate shift needs to be defined mathematically. Specifically, to quantify the adjustment that a layer's parameters make in response to updates in previous layers, the correlation between the gradients of the loss before and after all previous layers are updated is measured, since gradients could capture the shifts from the first-order training method. If the shift introduced by the changes in previous layers is small, then the correlation between the gradients would be close to 1.

The correlation between the gradients are computed for four models: a standard VGG network,^[5] a VGG network with batch normalization layers, a 25-layer deep linear network (DLN) trained with full-batch gradient descent, and a DLN network with batch normalization layers. Interestingly, it is shown that the standard VGG and DLN models both have higher correlations of gradients compared with their counterparts, indicating that the additional batch normalization layers are not reducing internal covariate shift.

Vanishing/exploding gradients

Even though batchnorm was originally introduced to alleviate gradient vanishing or explosion problems, a deep batchnorm network in fact suffers from gradient explosion at initialization time, no matter what it uses for nonlinearity. Thus the optimization landscape is very far from smooth for a randomly initialized, deep batchnorm network. More precisely, if the network has $L$ layers, then the gradient of the first layer weights has norm $>c\lambda ^{L}$ for some $\lambda >1,c>0$ depending only on the nonlinearity. For any fixed nonlinearity, $\lambda$ decreases as the batch size increases. For example, for ReLU, $\lambda$ decreases to $\pi /(\pi -1)\approx 1.467$ as the batch size tends to infinity. Practically, this means deep batchnorm networks are untrainable. This is only relieved by skip connections in the fashion of residual networks.^[3]

This gradient explosion on the surface contradicts the smoothness property explained in the previous section, but in fact they are consistent. The previous section studies the effect of inserting a single batchnorm in a network, while the gradient explosion depends on stacking batchnorms typical of modern deep neural networks.

Decoupling

Another possible reason for the success of batch normalization is that it decouples the length and direction of the weight vectors and thus facilitates better training.

By interpreting batch norm as a reparametrization of weight space, it can be shown that the length and the direction of the weights are separated and can thus be trained separately. For a particular neural network unit with input $x$ and weight vector $w$ , denote its output as $f(w)=E_{x}[\phi (x^{T}w)]$ , where $\phi$ is the activation function, and denote $S=E[xx^{T}]$ . Assume that $E[x]=0$ , and that the spectrum of the matrix $S$ is bounded as $0<\mu =\lambda _{min}(S)$ , $L=\lambda _{max}(S)<\infty$ , such that $S$ is symmetric positive definite. Adding batch normalization to this unit thus results in

$f_{BN}(w,\gamma ,\beta )=E_{x}[\phi (BN(x^{T}w))]=E_{x}{\bigg [}\phi {\bigg (}\gamma ({\frac {x^{T}w-E_{x}[x^{T}w]}{var_{x}[x^{T}w]^{1/2}}})+\beta {\bigg )}{\bigg ]}$ , by definition.

The variance term can be simplified such that $var_{x}[x^{T}w]=w^{T}Sw$ . Assume that $x$ has zero mean and $\beta$ can be omitted, then it follows that

$f_{BN}(w,\gamma )=E_{x}{\bigg [}\phi {\bigg (}\gamma {\frac {x^{T}w}{(w^{T}Sw)^{1/2}}}{\bigg )}{\bigg ]}$ , where $(w^{T}Sw)^{\frac {1}{2}}$ is the induced norm of $S$ , $||w||_{s}$ .

Hence, it could be concluded that $f_{BN}(w,\gamma )=E_{x}[\phi (x^{T}{\tilde {w}})]$ , where ${\tilde {w}}=\gamma {\frac {w}{||w||_{s}}}$ , and $\gamma$ and $w$ accounts for its length and direction separately. This property could then be used to prove the faster convergence of problems with batch normalization.

Linear convergence

Least-square problem

With the reparametrization interpretation, it could then be proved that applying batch normalization to the ordinary least squares problem achieves a linear convergence rate in gradient descent, which is faster than the regular gradient descent with only sub-linear convergence.

Denote the objective of minimizing an ordinary least squares problem as

$min_{{\tilde {w}}\in R^{d}}f_{OLS}({\tilde {w}})=min_{{\tilde {w}}\in R^{d}}(E_{x,y}[(y-x^{T}{\tilde {w}})^{2}])=min_{{\tilde {w}}\in R^{d}}(2u^{T}{\tilde {w}}+{\tilde {w}}^{T}S{\tilde {w}})$ , where $u=E[-yx]$ and $S=E[xx^{T}]$ .

Since ${\tilde {w}}=\gamma {\frac {w}{||w||_{s}}}$ , the objective thus becomes

$min_{w\in R^{d}\backslash \{0\},\gamma \in R}f_{OLS}(w,\gamma )=min_{w\in R^{d}\backslash \{0\},\gamma \in R}{\bigg (}2\gamma {\frac {u^{T}w}{||w||_{S}+\gamma ^{2}}}{\bigg )}$ , where 0 is excluded to avoid 0 in the denominator.

Since the objective is convex with respect to $\gamma$ , its optimal value could be calculated by setting the partial derivative of the objective against $\gamma$ to 0. The objective could be further simplified to be

$min_{w\in R^{d}\backslash \{0\}}\rho (w)=min_{w\in R^{d}\backslash \{0\}}{\bigg (}-{\frac {w^{T}uu^{T}w}{w^{T}Sw}}{\bigg )}$ .

Note that this objective is a form of the generalized Rayleigh quotient

${\tilde {\rho }}(w)={\frac {w^{T}Bw}{w^{T}Aw}}$ , where $B\in R^{d\times d}$ is a symmetric matrix and $A\in R^{d\times d}$ is a symmetric positive definite matrix.

It is proven that the gradient descent convergence rate of the generalized Rayleigh quotient is

${\frac {\lambda _{1}-\rho (w_{t+1})}{\rho (w_{t+1}-\lambda _{2})}}\leq {\bigg (}1-{\frac {\lambda _{1}-\lambda _{2}}{\lambda _{1}-\lambda _{min}}}{\bigg )}^{2t}{\frac {\lambda _{1}-\rho (w_{t})}{\rho (w_{t})-\lambda _{2}}}$ , where $\lambda _{1}$ is the largest eigenvalue of $B$ , $\lambda _{2}$ is the second largest eigenvalue of $B$ , and $\lambda _{min}$ is the smallest eigenvalue of $B$ .^[7]

In our case, $B=uu^{T}$ is a rank one matrix, and the convergence result can be simplified accordingly. Specifically, consider gradient descent steps of the form $w_{t+1}=w_{t}-\eta _{t}\triangledown \rho (w_{t})$ with step size $\eta _{t}={\frac {w_{t}^{T}Sw_{t}}{2L|\rho (w_{t})|}}$ , and starting from $\rho (w_{0})\neq 0$ , then

$\rho (w_{t})-\rho (w^{*})\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}(\rho (w_{0})-\rho (w^{*}))$ .

Learning halfspace problem

The problem of learning halfspaces refers to the training of the Perceptron, which is the simplest form of neural network. The optimization problem in this case is

$min_{{\tilde {w}}\in R^{d}}f_{LH}({\tilde {w}})=E_{y,x}[\phi (z^{T}{\tilde {w}})]$ , where $z=-yx$ and $\phi$ is an arbitrary loss function.

Suppose that $\phi$ is infinitely differentiable and has a bounded derivative. Assume that the objective function $f_{LH}$ is $\zeta$ -smooth, and that a solution $\alpha ^{*}=argmin_{\alpha }||\triangledown f(\alpha w)||^{2}$ exists and is bounded such that $-\infty <\alpha ^{*}<\infty$ . Also assume $z$ is a multivariate normal random variable. With the Gaussian assumption, it can be shown that all critical points lie on the same line, for any choice of loss function $\phi$ . Specifically, the gradient of $f_{LH}$ could be represented as

$\triangledown _{\tilde {w}}f_{LH}({\tilde {w}})=c_{1}({\tilde {w}})u+c_{2}({\tilde {w}})S{\tilde {w}}$ , where $c_{1}({\tilde {w}})=E_{z}[\phi ^{(1)}(z^{T}{\tilde {w}})]-E_{z}[\phi ^{(2)}(z^{T}{\tilde {w}})](u^{T}{\tilde {w}})$ , $c_{2}({\tilde {w}})=E_{z}[\phi ^{(2)}(z^{T}{\tilde {w}})]$ , and $\phi ^{(i)}$ is the $i$ -th derivative of $\phi$ .

By setting the gradient to 0, it thus follows that the bounded critical points ${\tilde {w}}_{*}$ can be expressed as ${\tilde {w}}_{*}=g_{*}S^{-1}u$ , where $g_{*}$ depends on ${\tilde {w}}_{*}$ and $\phi$ . Combining this global property with length-direction decoupling, it could thus be proved that this optimization problem converges linearly.

First, a variation of gradient descent with batch normalization, Gradient Descent in Normalized Parameterization (GDNP), is designed for the objective function $min_{w\in R^{d}\backslash \{0\},\gamma \in R}f_{LH}(w,\gamma )$ , such that the direction and length of the weights are updated separately. Denote the stopping criterion of GDNP as

$h(w_{t},\gamma _{t})=E_{z}[\phi '(z^{T}{\tilde {w}}_{t})](u^{T}w_{t})-E_{z}[\phi ''(z^{T}{\tilde {w}}_{t})](u^{T}w_{t})^{2}$ .

Let the step size be

$s_{t}=s(w_{t},\gamma _{t})=-{\frac {||w_{t}||_{S}^{3}}{Lg_{t}h(w_{t},\gamma _{t})}}$ .

For each step, if $h(w_{t},\gamma _{t})\neq 0$ , then update the direction as

$w_{t+1}=w_{t}-s_{t}\triangledown _{w}f(w_{t},\gamma _{t})$ .

Then update the length according to

$\gamma _{t}=Bisection(T_{s},f,w_{t})$ , where $Bisection()$ is the classical bisection algorithm, and $T_{s}$ is the total iterations ran in the bisection step.

Denote the total number of iterations as $T_{d}$ , then the final output of GDNP is

${\tilde {w}}_{T_{d}}=\gamma _{T_{d}}{\frac {w_{T_{d}}}{||w_{T_{d}}||_{S}}}$ .

The GDNP algorithm thus slightly modifies the batch normalization step for the ease of mathematical analysis.

It can be shown that in GDNP, the partial derivative of $f_{LH}$ against the length component converges to zero at a linear rate, such that

$(\partial _{\gamma }f_{LH}(w_{t},a_{t}^{(T_{s})})^{2}\leq {\frac {2^{-T_{s}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}$ , where $a_{t}^{(0)}$ and $b_{t}^{0}$ are the two starting points of the bisection algorithm on the left and on the right, correspondingly.

Further, for each iteration, the norm of the gradient of $f_{LH}$ with respect to $w$ converges linearly, such that

$||w_{t}||_{S}^{2}||\triangledown f_{LH}(w_{t},g_{t})||_{S^{-1}}^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}\Phi ^{2}\gamma _{t}^{2}(\rho (w_{0})-\rho ^{*})$ .

Combining these two inequalities, a bound could thus be obtained for the gradient with respect to ${\tilde {w}}_{T_{d}}$ :

$||\triangledown _{\tilde {w}}f({\tilde {w}}_{T_{d}})||^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2T_{d}}\Phi ^{2}(\rho (w_{0})-\rho ^{*})+{\frac {2^{-T_{s}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}$ , such that the algorithm is guaranteed to converge linearly.

Although the proof stands on the assumption of Gaussian input, it is also shown in experiments that GDNP could accelerate optimization without this constraint.

Neural networks

Consider a multilayer perceptron (MLP) with one hidden layer and $m$ hidden units with mapping from input $x\in R^{d}$ to a scalar output described as

$F_{x}({\tilde {W}},\Theta )=\sum _{i=1}^{m}\theta _{i}\phi (x^{T}{\tilde {w}}^{(i)})$ , where ${\tilde {w}}^{(i)}$ and $\theta _{i}$ are the input and output weights of unit $i$ correspondingly, and $\phi$ is the activation function and is assumed to be a tanh function.

The input and output weights could then be optimized with

$min_{{\tilde {W}},\Theta }(f_{NN}({\tilde {W}},\Theta )=E_{y,x}[l(-yF_{x}({\tilde {W}},\Theta ))])$ , where $l$ is a loss function, ${\tilde {W}}=\{{\tilde {w}}^{(1)},...,{\tilde {w}}^{(m)}\}$ , and $\Theta =\{\theta ^{(1)},...,\theta ^{(m)}\}$ .

Consider fixed $\Theta$ and optimizing only ${\tilde {W}}$ , it can be shown that the critical points of $f_{NN}({\tilde {W}})$ of a particular hidden unit $i$ , ${\hat {w}}^{(i)}$ , all align along one line depending on incoming information into the hidden layer, such that

${\hat {w}}^{(i)}={\hat {c}}^{(i)}S^{-1}u$ , where ${\hat {c}}^{(i)}\in R$ is a scalar, $i=1,...,m$ .

This result could be proved by setting the gradient of $f_{NN}$ to zero and solving the system of equations.

Apply the GDNP algorithm to this optimization problem by alternating optimization over the different hidden units. Specifically, for each hidden unit, run GDNP to find the optimal $W$ and $\gamma$ . With the same choice of stopping criterion and stepsize, it follows that

$||\triangledown _{{\tilde {w}}^{(i)}}f({\tilde {w}}_{t}^{(i)})||_{S^{-1}}^{2}\leq {\bigg (}1-{\frac {\mu }{L}}{\bigg )}^{2t}C(\rho (w_{0})-\rho ^{*})+{\frac {2^{-T_{s}^{(i)}}\zeta |b_{t}^{(0)}-a_{t}^{(0)}|}{\mu ^{2}}}$ .

Since the parameters of each hidden unit converge linearly, the whole optimization problem has a linear rate of convergence.^[4]

Related Research Articles

<span class="mw-page-title-main">Vector field</span> Assignment of a vector to each point in a subset of Euclidean space

In vector calculus and physics, a vector field is an assignment of a vector to each point in a space, most commonly Euclidean space $. A vector field on a plane can be visualized as a collection of arrows with given magnitudes and directions, each attached to a point on the plane. Vector fields are often used to model, for example, the speed and direction of a moving fluid throughout three dimensional space, such as the wind, or the strength and direction of some force, such as the magnetic or gravitational force, as it changes from one point to another point.$

<span class="mw-page-title-main">Fokker–Planck equation</span> Partial differential equation

In statistical mechanics and information theory, the Fokker–Planck equation is a partial differential equation that describes the time evolution of the probability density function of the velocity of a particle under the influence of drag forces and random forces, as in Brownian motion. The equation can be generalized to other observables as well. The Fokker-Planck equation has multiple applications in information theory, graph theory, data science, finance, economics etc.

In continuum mechanics, the infinitesimal strain theory is a mathematical approach to the description of the deformation of a solid body in which the displacements of the material particles are assumed to be much smaller than any relevant dimension of the body; so that its geometry and the constitutive properties of the material at each point of space can be assumed to be unchanged by the deformation.

In vector calculus, Green's theorem relates a line integral around a simple closed curve $C$ to a double integral over the plane region $D$ bounded by $C$ . It is the two-dimensional special case of Stokes' theorem. In one dimension, it is equivalent to the fundamental theorem of calculus. In three dimensions, it is equivalent to the divergence theorem.

In quantum mechanics, a spherically symmetric potential is a system of which the potential only depends on the radial distance from the spherical center and a location in space. A particle in a spherically symmetric potential will behave accordingly to said potential and can therefore be used as an approximation, for example, of the electron in a hydrogen atom or of the formation of chemical bonds.

In quantum field theory, Wilson loops are gauge invariant operators arising from the parallel transport of gauge variables around closed loops. They encode all gauge information of the theory, allowing for the construction of loop representations which fully describe gauge theories in terms of these loops. In pure gauge theory they play the role of order operators for confinement, where they satisfy what is known as the area law. Originally formulated by Kenneth G. Wilson in 1974, they were used to construct links and plaquettes which are the fundamental parameters in lattice gauge theory. Wilson loops fall into the broader class of loop operators, with some other notable examples being 't Hooft loops, which are magnetic duals to Wilson loops, and Polyakov loops, which are the thermal version of Wilson loops.

In quantum mechanics, the Hellmann–Feynman theorem relates the derivative of the total energy with respect to a parameter to the expectation value of the derivative of the Hamiltonian with respect to that same parameter. According to the theorem, once the spatial distribution of the electrons has been determined by solving the Schrödinger equation, all the forces in the system can be calculated using classical electrostatics.

In fluid dynamics, Couette flow is the flow of a viscous fluid in the space between two surfaces, one of which is moving tangentially relative to the other. The relative motion of the surfaces imposes a shear stress on the fluid and induces flow. Depending on the definition of the term, there may also be an applied pressure gradient in the flow direction.

In theoretical physics, a source is an abstract concept, developed by Julian Schwinger, motivated by the physical effects of surrounding particles involved in creating or destroying another particle. So, one can perceive sources as the origin of the physical properties carried by the created or destroyed particle, and thus one can use this concept to study all quantum processes including the spacetime localized properties and the energy forms, i.e., mass and momentum, of the phenomena. The probability amplitude of the created or the decaying particle is defined by the effect of the source on a localized spacetime region such that the affected particle captures its physics depending on the tensorial and spinorial nature of the source. An example that Julian Schwinger referred to is the creation of $meson due to the mass correlations among five mesons.$

In physics and fluid mechanics, a Blasius boundary layer describes the steady two-dimensional laminar boundary layer that forms on a semi-infinite plate which is held parallel to a constant unidirectional flow. Falkner and Skan later generalized Blasius' solution to wedge flow, i.e. flows in which the plate is not parallel to the flow.

<span class="mw-page-title-main">Corner detection</span> Approach used in computer vision systems

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.

In statistics, the multivariate t-distribution is a multivariate probability distribution. It is a generalization to random vectors of the Student's t-distribution, which is a distribution applicable to univariate random variables. While the case of a random matrix could be treated within this structure, the matrix t-distribution is distinct and makes particular use of the matrix structure.

The term generalized logistic distribution is used as the name for several different families of probability distributions. For example, Johnson et al. list four forms, which are listed below.

In the following we solve the second-order differential equation called the hypergeometric differential equation using Frobenius method, named after Ferdinand Georg Frobenius. This is a method that uses the series solution for a differential equation, where we assume the solution takes the form of a series. This is usually the method we use for complicated ordinary differential equations.

Curvilinear coordinates can be formulated in tensor calculus, with important applications in physics and engineering, particularly for describing transportation of physical quantities and deformation of matter in fluid mechanics and continuum mechanics.

In machine learning, the vanishing gradient problem is encountered when training neural networks with gradient-based learning methods and backpropagation. In such methods, during each training iteration, each neural network weight receives an update proportional to the partial derivative of the loss function with respect to the current weight. The problem is that as the network depth or sequence length increases, the gradient magnitude typically is expected to decrease, slowing the training process. In the worst case, this may completely stop the neural network from further learning. As one example of this problem, traditional activation functions such as the hyperbolic tangent function have gradients in the range $[-1,1]$ , and backpropagation computes gradients using the chain rule. This has the effect of multiplying $n$ of these small numbers to compute gradients of the early layers in an $n$ -layer network, meaning that the gradient decreases exponentially with $n$ while the early layers train very slowly.

In string theory, the Ramond–Neveu–Schwarz (RNS) formalism is an approach to formulating superstrings in which the worldsheet has explicit superconformal invariance but spacetime supersymmetry is hidden, in contrast to the Green–Schwarz formalism where the latter is explicit. It was originally developed by Pierre Ramond, André Neveu and John Schwarz in the RNS model in 1971, which gives rise to type II string theories and can also give type I string theory. Heterotic string theories can also be acquired through this formalism by using a different worldsheet action. There are various ways to quantize the string within this framework including light-cone quantization, old canonical quantization, and BRST quantization. A consistent string theory is only acquired if the spectrum of states is restricted through a procedure known as a GSO projection, with this projection being automatically present in the Green–Schwarz formalism.

Nonlinear tides are generated by hydrodynamic distortions of tides. A tidal wave is said to be nonlinear when its shape deviates from a pure sinusoidal wave. In mathematical terms, the wave owes its nonlinearity due to the nonlinear advection and frictional terms in the governing equations. These become more important in shallow-water regions such as in estuaries. Nonlinear tides are studied in the fields of coastal morphodynamics, coastal engineering and physical oceanography. The nonlinearity of tides has important implications for the transport of sediment.

In machine learning, normalization is a statistical technique with various applications. There are two main forms of normalization, namely data normalization and activation normalization. Data normalization includes methods that rescale input data so that the features have the same range, mean, variance, or other statistical properties. For instance, a popular choice of feature scaling method is min-max normalization, where each feature is transformed to have the same range. This solves the problem of different features having vastly different scales, for example if one feature is measured in kilometers and another in nanometers.

References

1 2 3 4 Ioffe, Sergey; Szegedy, Christian (2015). "Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift". arXiv: 1502.03167 [cs.LG].
1 2 3 4 Santurkar, Shibani; Tsipras, Dimitris; Ilyas, Andrew; Madry, Aleksander (29 May 2018). "How Does Batch Normalization Help Optimization?". arXiv: 1805.11604 [stat.ML].
1 2 Yang, Greg; Pennington, Jeffrey; Rao, Vinay; Sohl-Dickstein, Jascha; Schoenholz, Samuel S. (2019). "A Mean Field Theory of Batch Normalization". arXiv: 1902.08129 [cs.NE].
1 2 3 Kohler, Jonas; Daneshmand, Hadi; Lucchi, Aurelien; Zhou, Ming; Neymeyr, Klaus; Hofmann, Thomas (27 May 2018). "Exponential convergence rates for Batch Normalization: The power of length-direction decoupling in non-convex optimization". arXiv: 1805.10694 [stat.ML].
1 2 Simonyan, Karen; Andrew, Zisserman (2014). "Very Deep Convolution Networks for Large Scale Image Recognition". arXiv: 1409.1556 [cs.CV].
↑ Ba, J., Kiros, J.R., & Hinton, G.E. (2016). Layer Normalization. ArXiv, abs/1607.06450.
↑ Knyazev, Neymeyr (2003). "A geometric theory for preconditioned inverse iteration III: A short and sharp convergence estimate for generalized eigenvalue problems". Linear Algebra and Its Applications. 358 (1–3): 95–114. doi: 10.1016/S0024-3795(01)00461-X .