Train Feedfoward Neural Network with Layer-wise Adaptive Rate via Approximating Back-matching Propagation
Huishuai Zhang Wei Chen Tie-Yan Liu


[

Train Feedfoward Neural Network with Layer-wise Adaptive Rate 

via Approximating Back-matching Propagation













equal*


Huishuai Zhanggoo
Wei Chengoo
Tie-Yan Liugoo


gooMicorosoft Research Asia, Beijing, China

Huishuai Zhanghuzhang@microsoft.com





Machine Learning, ICML

0.3in
]









  


Stochastic gradient descent (SGD) has achieved great success in training deep neural network, where the gradient is  computed through back-propagation. However, the back-propagated values of different layers vary dramatically. This inconsistence of gradient magnitude across different layers renders optimization of deep neural network with a single learning rate problematic.  We introduce the back-matching propagation which computes the backward values on the layer's parameter and the input by matching backward values on the layer's output.  This leads to solving a bunch of least-squares problems, which requires high computational cost. We then reduce the back-matching propagation with  approximations and propose an algorithm that turns to be the regular SGD with a layer-wise adaptive learning rate strategy. This allows an easy implementation of our algorithm in current machine learning frameworks equipped with auto-differentiation. We apply our algorithm in training modern deep neural networks and achieve favorable results over SGD.




§ INTRODUCTION

Deep neural networks have been advancing the state-of-the-art performance over a number of tasks in artificial intelligence, from speech recognition <cit.>, computer vision <cit.> to natural language understanding <cit.>. These problems are typically formulated as minimizing non-convex objectives  parameterized by the neural network models. Typically the models are trained with stochastic gradient descent (SGD) or its variants and the gradient information is computed through back-propagation (BP) <cit.>. 



However, the magnitudes of gradient components often vary significantly in neural network. Recall that one coordinate of the gradient is the directional derivative along with that coordinate which represents how a change on the weight will affect the loss rather than how we should modify the weight to minimize the loss. Thus vanilla SGD with a single learning rate could be problematic for  
the optimization of deep neural network because of the inconsistent magnitude of gradient components.  In practice, extreme small learning rate alleviates this problem but leads to slow convergence. Moreover, momentum <cit.> amends this problem by accumulating velocity along the coordinate with small magnitude but consistent direction and reducing the velocity for those coordinates with large magnitudes but opposite directions. Adaptive learning rate algorithms <cit.> scale coordinates of the gradient by  reciprocals of some averages of their past magnitudes, confirming that weakening the affect of magnitudes of the gradient components could be favorable to the optimization from the other side. 












We want to solve this problem from another perspective. <cit.> suggests that the magnitude inconsistence of gradient components are mainly across layers. We can get a hint by scrutinizing the back-propagation through a fully connected layer[We omit bias terms for simplicity.] which has output  and input  and weight parameter .  The layer mapping is given by =. If δ is the back-propagated value on the output is , i.e., the partial derivatives of the loss with respect to , the back-propagation equation is given by

    δa_j = _j→^T δ, 


where _j→ is the j-th column of  (represents all the connections emanating from unit j) and δ a_j is the back-propagated value on the layer's input a_j computed through back-propagation. 
If the rows of  are initialized with unit length (roughly) to preserve the forward signal, then back-propagation through this layer would shrink the magnitude of the backward signal heavily when the number of input  is much larger than the number of output. 

We suggest a principled way to overcome the problem of magnitude inconsistence of gradient components across layers in back-propagation. Specifically, 
we compute changes δ' and  δ' a_j on the weight parameter  and on the input respectively, to match the error guiding signal δ b_k as closely as possible. This motivates us to formulate the backward pass through the fully connected layer as solving a group of least-squares problems. By hiding technical details and some assumption, we propose the back-matching propagation as follows,

   δ' a_j = (_j→^T_j→)^-1 (_j→^T  δ),  

   δ' = (^T)^-1[(δ) ^T], 

where the expectation is over the data points in a mini batch. 
A direct expalanation of (<ref>) is that we want to change the weight matrix  by δ' to produce a desired change δ on the output (or sufficiently close to) given the current input . So can we explain equation (<ref>). Then we use  δ' to update the parameter   and use δ' a_j as the error guiding signal to back-propagate to lower layers. 

For the back-matching propagation (<ref>), we need to compute (_j→^T_j→)^-1 which is easy since it is a scaler.  For the parameter update solution (<ref>), we need to compute an inverse  (^T)^-1. This requires a large number of matrix inverse operations, roughly the number of neurons, and each inverse requires flops on the cubic order of the number of neurons in one layer. This hinders it to be applied to large neural networks which typically contain tens of thousands of neurons in a single layer.
















Fortunately, we can work with the batch normalization (BN) technique <cit.> to circumvent this difficulty. With batch normalization, we regard ^T as an identity matrix approximately and remove the inverse in (<ref>). Then with some approximation, we can reduce the back-matching propagation into a layer-wise gradient adaption strategy, which can be viewed as layer-wise adaptive learning rates when applying pure SGD. As such a layer-wise gradient adaption strategy is built upon the regular BP process, it is easy to implement in current deep learning frameworks <cit.>. Moreover, this strategy also works with other popular optimization techiques (momentum, ada-algorithms, weight-decay) naturally to achieve possible higher performances in machine learning tasks. We expect this layer-wise gradient adaption strategy could accelerate the training procedure. 
Surprisingly, this strategy often improves the test accuracy by a considerable margin in practice. 




 §.§ Related Works

Training neural network with layer-wise adaptive learning rate has been proposed in several previous works. Specifically, <cit.> suggested using η· (1+log (1+1/δ_l_2)) as the learning rate for the layer l.  <cit.> suggested using η·_l_2/δ_l_2 as the learning rate for layer l and demonstrated that this would benefit the large-batch training.  However, the suggestion in both works mainly comes from empirical experience and do not have explanation of why the rate is set in that way. 



Our paper is related to the block-diagonal second order algorithms <cit.>. Specifically,  <cit.> proposes a weight reparametrization scheme with a diagonal rescaling step-size and show its potential advantages over batch normalization. <cit.> proposes a block diagonal Hessian-free method to train neural networks and shows fast convergence rate over first-order methods. <cit.> propose the Kronecker Factored Approximation (KFA) method to approximate the natural gradient using a block-diagonal or block-tridiagonal approximation of the Fisher matrix. These second-order algorithms
 all share a layer-wise or block-diagonal structure design, which agrees with our algorithm.  However, our layer-wise adaptive learning rate comes from the perspective of back-matching propagation and is different from the second-order approximations. 

Our paper is also related to the Riemannian algorithms <cit.>. Specifically, <cit.> proposes using ( [^T m_k])^-1 [(δ b_k) ^T] as the update for the parameter _→ k, where m_k is a backpropagated metric.  
Similarly, <cit.> advocates using  (^T + λ)^-1[(δ) ^T] as the update of the parameter. 

In comparison, the back-matching propagation comes from a different perspective that the back-propagated values should match the error guiding signal. Our layer-wise gradient adaption strategy, which is derived from back-matching propagation, is simpler than the Riemannian algorithms in terms of implementational and computational complexity. 





§ BACK-MATCHING PROPAGATION

In this section, we present how the back-matching propagation works under several popular types of layers.  Specifically, we derive the formula of the backprogated values on the layer's input and on the layer's parameters given the backpropagated value on the layer's output based on the back-matching propagation.  Moreover, we  compare the back-matching propagation to the regular BP. 

We introduce several notations here (some have been used in Introduction).  Let ℓ denote the objective (loss function). We use  and  to denote the layer's output and input respectively and use parameter  to denote the layer's parameter.  We use δ to denote the back-propagated value on the layer's output. Then we use δ a_j and δ  to denote the back-propagated values computed through BP, and use δ' a_j and δ' to denote the back-propagated values computed  through back-matching propagation. 


Let us briefly review the regular BP here. The BP propagates derivatives from the top layer back to the bottom one. Suppose we are dealing with a general layer which has forward mapping  = f(; ). Then the derivative of the loss ℓ with respect to a specific output component  b_k is δ b_k := -∂ℓ/∂ b_k. The  BP equations are given by





    δa_j = ∑_k, j→k ∂b_k/∂a_j δb_k 
 
    δ=  _x[ (δ(x))(x)^T,  

where x represents a data point and  the expectation is over the data points in a mini batch. 

Next we present how the back-matching propagation back-propagated through specific layers. In order to compare conveniently, for each type of layer we first provide the BP formula and then derive the formula via back-matching propagation and in the end discuss the relation between the back-matching propagation and BP.


 §.§ Fully Connected Layer

We first consider a fully connected layer, whose mapping function is given by[For simplicity we omit the bias term.]

= . 	

Suppose the backpropagated values on the output are δ.  Following backpropagation equations (<ref>) and (<ref>),  we compute the backpropagated values on the input and on the weight parameter  as follows,

 δ    a_j(x) = _j→^T δ(x), 

 δ    =  _x [δ(x) (x)^T], 

where _j→ is the j-th column of .

We next derive the formula for back-matching propagation, where we compute δ' and δ' a_j that try to match the guiding signal δ as accurately as possible, in the sense of minimizing square error, 

	   δ' ←_δ' δ- (δ') _2^2 

	   δ' ←_δ' δ- (δ')_2^2.  

Note that by writing the matching problem as two independent problems (<ref>) and (<ref>), we presume that updating  and propagating backward values δ' are independent, and such layer independence has been used in block-diagonal second-order algorithms <cit.>. Moreover, (<ref>) is separable along the rows of δ'. Hence we obtain a bunch of (total number #row()) least-squares problems

	   δ' _→k  ←_δ'_→k δ_k - δ'_→k _2^2, 

where _→ k is the k-th row of  and δ_k represents the back-propagated values at neuron k in one mini batch of data. We further assume all a_j(x) are updated independently, based on the intuition that a neuron doesn't know the other neurons' states on/off and a fair strategy is to try its best to match the guiding signal by itself. Then (<ref>) becomes a bunch (total number dim()) of least-squares problems 

	   δ' a_j ←_δa_j δ- _j→ δa_j_2^2,  

where _j→ are the weights emanating from neuron j (a column of  corresponding neuron j). We call equations (<ref>) and (<ref>) the back-matching propagation rule.
Solving the least-squares problems (<ref>) and (<ref>) gives us:

   δ' a_j(x) =(_j→^T_j→)^-1 (_j→^T  δ(x)), 

   δ' = (_x (x) (x)^T)^-1_x [δ(x) (x)^T]. 











From (<ref>) (<ref>) and (<ref>) (<ref>), we can see how the back-matching propagation is related with the regular BP:

δ'    a_j(x) = (_j→^T_j→)^-1 δa_j(x), 

δ'    = (_x (x) (x)^T)^-1 δ. 


We can see that the formulas (<ref>) (<ref>) of back-matching propagation are the corresponding BP formulas (<ref>) (<ref>) rescaled by a number or a matrix. 



 §.§ Convolutional Layer

In this section we study the back-matching propagation through a convolutional layer. The weight parameter  is an array with dimension n× m × w × h, where  n and m are the number of output features and the number of input features respectively, and w and  h are the width and height of convolutional kernels. We use b_ku_1u_2 to denote the output at location (u_1, u_2) of feature k and  a_ju_1u_2 to denote the input at location (u_1, u_2) of feature j, then the forward process is 

b_ku_1u_2 = ∑_j=1^n ∑_v_1v_2 a_j(u_1+v_1)(u_2+v_2) w_jkv_1v_2, 

and the BP is given by

δ    a_ju_1u_2 = ∑_k=1^m ∑_v_1v_2 δb_k(u_1+v_1)(u_2+v_2) w_jkv_1v_2, 

δ    w_jkv_1v_2 =  ∑_u_1u_2 δb_ku_1u_2 a_j(u_1+v_1)(u_2+v_2). 

However, this formula of the forward and backward process of convolutional layer make the derivation of back-matching propagation complex. Note that the convolution operation essentially performs dot products between the convolution kernels and local regions of the input. The forward pass of a convolution layer can be formulated as one big matrix multiply with im2col operation. In order to describe back matching process clearly, we rewrite the convolution layer forward and backward pass with im2col operation. We use _row and _col to represent the weight matrices with dimension n× (mwh) and m× (nwh), respectively, which both are stretched out from (n, m, w, h). To mimic the convolutional operation, we rearrange the input features  into a big matrix _i2c through im2col operation: each column of _i2c is composed of the elements of  that are used to compute one location in . Thus if  has dimension n× q_1× q_2, then _i2c has dimension mwh× q_1q_2. Furthermore, we stack the latter two dimensions of  into a tall vector, denoted as _col which has dimension n× q_1q_2. The forward process (<ref>) of convolutional layer can be rewritten as

_col =_row _i2c

Similarly, we can rewrite the regular BP (<ref>) and (<ref>) as


   δa_ju_1u_2(x) = _ju_1u_2 →^T δ[ju_1u_2](x),  

   δ_row = _x δ_col(x) _i2c^T(x), 

where _ju_1u_2 →  is composed of weight components that interact with input location ju_1u_2, which approximately has nwh/c elements and c is a factor related with pooling and stride, and δ[ju_1u_2] is composed of output locations that have interaction with input location ju_1u_2. With these notations, we can derive  the formula for back-matching  propagation via solving the least squares problems  (<ref>) and  (<ref>), given by







δ'    a_ju_1u_2(x)  =  _ju_1u_2 →^T δ[ju_1u_2](x)/_ju_1u_2 →^T _ju_1u_2 →,  


δ'    _row^T = (_x _i2c _i2c^T)^-1 _x δ_col(x) _i2c^T(x). 

We can see that the formulas  (<ref>) (<ref>)  of back-matching propagation are the corresponding BP formulas (<ref>) (<ref>) rescaled by a number or a matrix.  
As the convolutional layer is essentially a linear mapping, the formulas here is similar to those of the fully connected layer although they are more involved.





 §.§ Batch Normalization Layer

Batch normalization (BN) is widely used for accelerating training of feedforward neural networks. In practice, BN is usually inserted right before the activation function. We fix the affine transformation of batch normalization to be identity. Then the BN layer mapping is given by

	b_k = BN(a_k) = a_k- [a_k]/√([a_k]).

The BP formula through the BN layer  is given by <cit.>,

δa_k = δb_k/√([a_k]) + (δ[a_k] ·2(a_k-[a_k]) +δ[a_k])/m, 

where m is the mini-batch size, and δ[a_k] and δ[a_k] is the backpropagated values on quantities [a_k] and [a_k] respectively.

We next derive the formula of back-matching propagation through BN. By solving (<ref>), we have 

δ' a_k    = δb_k ·√([a_k]). 

To see how the back-matching propagation is related with BP, we ignore the latter two terms in (<ref>) when the mini-batch size is large, and have the following approximation

δ' a_k    ≈δa_k ·[a_k].











 §.§ Rectified Linear Unit (ReLU)

We use σ(·) to denote the ReLU nonlinear function. Then the ReLU mapping is given by 

	b_k = σ(a_k) =
a_k ,      if a_k ≥0

0,       if  a_k < 0.


For the formula of BP, we have

δa_k = δb_k σ'(a_k) =
δb_k ,      if a_k ≥0

0,       if  a_k < 0.


Following (<ref>), we have the formula of back-matching propagation for the ReLU layer

δ' a_k = δb_k σ'(a_k).

Therefore the formula of back-matching propagation for ReLU is the same as that of BP,

δ' a_k = δa_k. 




§ LAYER-WISE ADAPTIVE RATE VIA APPROXIMATE BACK-MATCHING PROPAGATION


The back-matching propagation involves large number of matrix inverse operations, which is computationally prohibited in training large neural networks. In this section we present how to approximate the back-matching propagation under certain assumption and end up with a layer-wise adaptive rate strategy based on the approximation of the back-matching propagation, which allows easy implementation in frameworks equipped with auto-differentiation.



 §.§ Approximate Back-matching Propagation via BP
 
We firstly look at the formula of the back-matching propagated value on the weight parameter (<ref>) and (<ref>). It is the gradient scaled by an inverse of a matrix, which is prohibited for large networks. We use batch normalization to circumvent this difficulty. 

With batch normalization, we regard _x^T as identity matrix approximately. From now on, we require each intermediate layer is bonded with a batch normalization layer except the output layer. Since BN has been widely used for accelerating the training process and improving the test accuracy, this requirement does not confine us much.  Under this requirement, the back-matching propagation for the fully connected layer (<ref>) is approximated by,

δ' = (_x (x) (x)^T)^-1 δ≈δ, 

and the back-matching propagation for the convolutional layer (<ref>) is approximated by,

δ' _row^T = (_x _i2c _i2c^T)^-1 δ_row^T ≈1/s δ_row^T, 

where s is the sharing factor for the convolutional layer.

Next we consider the formula of back-matching propagated values on the input (<ref>) and (<ref>). To further reduce the complexity and develop a layer-wise adaptive learning rate strategy, we assume that  is row homogeneous <cit.>, i.e., they represent the same level of information and are roughly of similar magnitude.  We define 

    _2,μ^2 := 1/#row()∑_i=1^#row()_i^T _i,

where _i is the i-th row of .
Then the (_j→^T_j→) in equation (<ref>) can be approximated as   (_j→^T_j→)≈^T_2,μ^2.
Under this assumption, the back-matching propagation for the fully connected layer (<ref>) is approximated by,

δ' a_j(x)    = (_j→^T_j→)^-1 δa_j(x) ≈ δa_j(x)/^T_2,μ^2 

and the back-matching propagation for the convolutional layer (<ref>) is approximated by,

δ' a_ju_1u_2(x)  
≈δa_ju_1u_2(x)/_col_2,μ^2/c,

where c is a factor related with pooling, stride and padding operations. We will see a detailed example in Section <ref>.

For BN layer, we assume the weight parameter is row homogeneous and then the back-matching propagation for the BN layer (<ref>) is approximated by,

δ' a_k ≈δa_k ·[a_k]≈_2,μ^2·δa_k. 




 §.§ Layer-wise Adaptive Rate Strategy

Based on the approximations in Section <ref> we are ready to derive a layer-wise adaptive learning rate strategy.
We note that the approximate back-matching propagation gives a scaling factor for each layer's gradient if we back-propagate starting from the top layer. We set the initial factor of the output layer is m_out=1, which indicates that we regard the derivative of the loss with respect to the output of the network as the desired changes on the output to minimize the loss. 

Then starting from the top layer, we compute a backward factor m for each layer through
 
  m_a ←m_b ·δa_j/δ' a_j,
 
 where the relations of δ a_j and δ' a_j are given by (<ref>), (<ref>), (<ref>) and (<ref>) for fully connected layer, convolutional layer, BN layer and ReLU, respectively.
If the layer has parameter  and gradient δ, then we use δ/ m_b / s as the new adaptive gradient to update , where m_b is the backward factor on the output of the layer and s is the sharing factor of the layer. Then 1/ m_b / s can be viewed as a layer-wise adaptive learning rate when using vanilla SGD. This strategy is described in Algorithm <ref>.



Our algorithm can work with momentum naturally. In practice, we use the flow in Algorithm <ref> to modify the gradient computed via BP. Then we apply the momentum update with the modified gradient. With the modified gradient given by Algorithm <ref>, we can also apply other adaptive strategy, i.e., Adam and Adagrad, without difficulty.

Weight-decay is a widely used technique to improve the generalization of the model. Note that both the weight-decay and our algorithm are modifying the gradient of the network parameter computed through BP. In practice, we first apply the weight-decay modification and then apply our algorithm on the modified gradient, which produces better result than the other way around. 



 §.§ An Example: LeNet

We use LeNet (Figure. <ref>) as an example. We modify the original LeNet<cit.> by inserting a batch normalization transformation before each activation layer (ReLU) and omitting all the bias terms. 

We next walk through the approximated back-matching propagation of the LeNet and show how each layer's weight should be changed (δ'). 
Following the procedure of Algorithm <ref>, we have the following initial value: m=1, s_fc3 = 1, s_fc2 = 1, s_fc1 = 1, s_cv2 = 25, s_cv1 = 196. Given the loss ℓ(x), we can compute the normal gradient on each weight parameter through BP, which are denoted as δ with subscript of the layer name. We start from the top layer fc3 and compute 

δ'_fc3 = δ_fc3 / m / s_fc3 = δ 
and update m ← m·δ a_j/δ' a_j = _fc3^T_2,μ^2. Since the ReLU activation does not contain parameter and does not change the backward factor m, then we move to the BN layer. Since our BN layer does not have parameter, we only have to update the backward factor 
    m ← m·δ a_j/δ' a_j  =_fc3^T_2,μ^2/_fc2_2,μ^2.

 Then we move to layer fc2 and compute 

δ'_fc2 = δ_fc2 / m / s_fc2 =_fc2_2,μ^2/_fc3^T_2,μ^2 ·δ,
 
and update the backward factor 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2)/_fc2_2,μ^2.

We continue doing this till the bottom layer.  Further details are provided in supplemental material.

















We next train LeNet with BN to classify the  CIFAR-10 dataset <cit.>. CIFAR-10 is composed of 60,000 32× 32color images in 10 classes, with 6000 images per class. There are 50,000 training images and 10,000 test images. We want to compare the training procedure and test accuracy of the classical SGD based on BP and our algorithm. There are many hyper-parameters/hyper-routines that would affect the learning curve significantly, and we try our best to make a fair comparison. In the first experiment, we use only CIFAR-10 dataset without augmentation and fix momentum to be 0.9 for both algorithm, two models start from the same initial point and pass the same mini batch of data, where the mini-batch size is 128.  Global learning rates are chosen to perform best in terms of test accuracy from a pool of five candidates[The pool for regular SGD is {0.02, 0.05, 0.1, 0.2, 0.5} and the pool for our algorithm is {0.005, 0.01, 0.02, 0.05, 0.1}.]. We choose global learning rate  η=0.1 for SGD  and η=0.02 for our algorithm. We fix the global learning rate through the training process and train for 200 epochs. A weight-decay term (0.0005) is optional for both methods. We note that the loss in the training curve does not include the weight-decay term in Figure. <ref> no matter whether the weight-decay is used. 



From Figure. <ref>, we can see that without weight decay both algorithms can drive the training loss to zero but test accuracy of the regular SGD turns worse after very few epochs (15)  and the model becomes overfitting from then on. In comparison, our algorithm achieves a much lower test error than the regular SGD and there is a considerable margin between our algorithm and the regular SGD even in the overfitting phase. 
On the other hand, with weight decay both training losses do not converge to zero any more but our algorithm achieves much lower training loss than the regular SGD. Weight decay improves the final test accuracy but does not improve the lowest test error during the training period of our algorithm. The weight obtained by our algorithm have rather large magnitude (the network does not explode as the batch normalization stabilize the forward propagation). We believe our algorithm combats overfitting differently from the weight decay and could provide another way to improve generalization in certain setting that cannot achieved by weight decay. 
























§ EXPERIMENTS

In this section, we evaluate the proposed algorithm for image classification tasks with two datasets: CIFAR-10 <cit.>, CIFAR-100 <cit.>.  CIFAR-10 has been introduced in Section <ref>. The CIFAR-100 dataset is similar to the CIFAR-10, except it has 100 classes with 600 images per class and there are 500 training images and 100 testing images per class. We train VGG networks <cit.> to classify these two datasets because they are widely used baselines for image classification tasks and they are of feedforward architecture.  We modify the VGG nets by keeping the last fully connected layers and removing the intermediate two fully connected layers and all the biases [We find this does not hurt accuracy for CIFAR dataset and shortens training time due to fewer parameters.].  We equip each intermediate layer of the VGG nets with batch normalization transformation right before the activation function and the batch normalization has no trainable parameters.

Differently from the setting in Section <ref>, here we train VGG nets by using the randomly augmented CIFAR-10 and CIFAR-100 datasets (random flip and rotation) as such big models get overfitting to the datasets rapidly. We note that  augmenting the dataset the training does not gain much benefit directly. We need to decay the learning rate to learn effectively with data augmentation.  In order to compare fairly, we apply the same learning rate scheduling strategy to all algorithms: multiplying the learning rate by a factor 0.2 every 60 epochs. 









 §.§ Baseline Algorithms

We introduce several baseline algorithms and their settings. 

The base algorithm is the regular SGD with Nesterov momentum 0.9. The learning rate is set to be η=0.1. 

The second baseline algorithm is LSALR <cit.> which uses η· (1+log (1+1/δ_l_2)) as the learning rate for the layer l. The global learning rate is set to be η=0.1, which achieves best performance comparing from a pool of candidates {0.006, 0.05, 0.1, 0.2, 1}, and is different from the suggestion (0.006) in the original paper. 

The third baseline algorithm is LARS <cit.> which uses η·_l_2/δ_l_2 as the learning rate for layer l.  In our experiment, we use the global learning rate η = 2 for LARS, which achieves best performance from a pool of {1, 2, 5, 10}. 



Noting that all these layer-wise adaptive algorithms modify the regular layer gradient computed through BP,  we equip Nesterov momentum 0.9 on them  in the experiment.  For baseline algorithms, we apply weight decay with coefficient 5e-4 if without specific description. 



 §.§ Result


We first compare the learning curves between the our algorithm and the vanilla SGD on training VGG11 with CIFAR-100. We apply Nesterov momentum 0.9 and weight decay coefficient 5e-3 for both algorithms. Similarly to Section <ref>, two algorithms start from the same initialization and pass the same batches of data.  We set the same learning rate η=0.1 for both algorithms. Both algorithms are run 300 epochs. We plot the learning curves in Figure <ref>.

From Figure <ref>, we can see that the learning curves of our algorithm and SGD have similar trend: curves jump at each learning rate decay. This is predictable as our algorithm only modifies the magnitude of the layer's gradient as a whole and does not involve any further information (second order information) and moreover we use the same hyper-parameters and the same learning rate scheduling strategy for both algorithms. Scrutinizing more closely, we can see our training loss curve is almost always lower than SGD's and our test error fluctuates heavier initially but ends with a considerably lower number.

Next we present the test result of different VGG nets for classification of CIFAR-100 in Table <ref>. For this group of experiments, we use global learning rate η=0.1 and weight decay coefficient 5e-3 for our algorithm. Our algorithm achieves higher test accuracy over its competitors on all four VGG models with margins.



We then present the test accuracy result of different VGG nets for classification of CIFAR-10 in Table <ref>. The numbers in the table are the best of five independent trials of each algorithm. We use learning rate 2e-3 and weight decay coefficient 1e-4 for this group of experiments. We use a different learning rate from the case of CIFAR-100. The reason is that for training CIFAR-10 the last layer of VGG nets has 10 output and then the backpropagated values shall be multiplied by 512/10 if following the back-matching propagation rule. 
 Such an imbalanced mapping layer makes our algorithm behave aggressively. Hence we reduce the learning rate to 2e-3 for consistent result. We can see that our algorithm achieves higher test accuracy as its competitors on almost all  VGG models with various margins.






























































§ CONCLUSION AND DISCUSSION

In this paper we present the back-matching propagation which provides a principled way of computing the backpropagated values on the weight parameter and on the input, which try to match the error guiding signal on the output as accurately as possible. To utilize the idea of back-matching propagation in training large neural networks efficiently, we make several approximations based on intuitive understanding and reduce the back-matching propagation to the regular BP with a layer-wise adaptive learning rate strategy. It it easy to implement within current machine learning frameworks that are equipped with auto-differentiation. We test our algorithm in training feedforward neural networks and achieve favorable result over SGD.


There are several future directions along with this work. In our derivation of the Algorithm <ref>, we assume that each neuron updates its values independently from others in the same layer. This is a strong assumption and may produce inaccuracy on computing the backpropagated values across layers. 
Thus one future direction is to modify the back-matching propagation by considering the co-update of neurons in the same layer, which is closely related to Riemannian algorithms <cit.> that have been introduced but not widely used because of their complexity. Moreover, applying the idea of back-matching propagation to other  architectures like residual networks  and recurrent neural networks is also under consideration.



 
30


urlstyle

[Abadi et al.(2016)Abadi, Barham, Chen, Chen, Davis, Dean, Devin,
  Ghemawat, Irving, Isard, et al.]tensorflow
Abadi, Martín, Barham, Paul, Chen, Jianmin, Chen, Zhifeng, Davis, Andy,
  Dean, Jeffrey, Devin, Matthieu, Ghemawat, Sanjay, Irving, Geoffrey, Isard,
  Michael, et al.
TensorFlow: A system for large-scale machine learning.
In OSDI, volume 16, pp.  265–283, 2016.

[Amari(1998)]amari1998natural
Amari, Shun-Ichi.
Natural gradient works efficiently in learning.
Neural computation, 100 (2):0 251–276, 1998.

[Ba et al.(2016)Ba, Kiros, and Hinton]ba2016layer
Ba, Jimmy Lei, Kiros, Jamie Ryan, and Hinton, Geoffrey E.
Layer normalization.
arXiv preprint arXiv:1607.06450, 2016.

[Bastien et al.(2012)Bastien, Lamblin, Pascanu, Bergstra, Goodfellow,
  Bergeron, Bouchard, Warde-Farley, and Bengio]theano
Bastien, Frédéric, Lamblin, Pascal, Pascanu, Razvan, Bergstra, James,
  Goodfellow, Ian, Bergeron, Arnaud, Bouchard, Nicolas, Warde-Farley, David,
  and Bengio, Yoshua.
Theano: new features and speed improvements.
arXiv preprint arXiv:1211.5590, 2012.

[Duchi et al.(2011)Duchi, Hazan, and Singer]duchi2011adaptive
Duchi, John, Hazan, Elad, and Singer, Yoram.
Adaptive subgradient methods for online learning and stochastic
  optimization.
Journal of Machine Learning Research, 120
  (Jul):0 2121–2159, 2011.

[Grosse & Martens(2016)Grosse and Martens]grosse2016kronecker
Grosse, Roger and Martens, James.
A Kronecker-factored approximate Fisher matrix for convolution
  layers.
In International Conference on Machine Learning (ICML), 2016.

[He et al.(2016)He, Zhang, Ren, and Sun]he2016deep
He, Kaiming, Zhang, Xiangyu, Ren, Shaoqing, and Sun, Jian.
Deep residual learning for image recognition.
In The IEEE Conference on Computer Vision and Pattern
  Recognition (CVPR), June 2016.

[Hinton et al.(2012)Hinton, Deng, Yu, Dahl, Mohamed, Jaitly, Senior,
  Vanhoucke, Nguyen, Sainath, et al.]hinton2012deep
Hinton, Geoffrey, Deng, Li, Yu, Dong, Dahl, George E, Mohamed, Abdel-rahman,
  Jaitly, Navdeep, Senior, Andrew, Vanhoucke, Vincent, Nguyen, Patrick,
  Sainath, Tara N, et al.
Deep neural networks for acoustic modeling in speech recognition: The
  shared views of four research groups.
IEEE Signal Processing Magazine, 290 (6):0
  82–97, 2012.

[Hochreiter & Schmidhuber(1997)Hochreiter and
  Schmidhuber]hochreiter1997long
Hochreiter, Sepp and Schmidhuber, Jürgen.
Long short-term memory.
Neural Computation, 90 (8):0 1735–1780, 1997.

[Ioffe & Szegedy(2015)Ioffe and Szegedy]ioffe2015batch
Ioffe, Sergey and Szegedy, Christian.
Batch normalization: Accelerating deep network training by reducing
  internal covariate shift.
In International Conference on Machine Learning (ICML), pp.  448–456, 2015.

[Kingma & Ba(2014)Kingma and Ba]kingma2014adam
Kingma, Diederik and Ba, Jimmy.
Adam: A method for stochastic optimization.
arXiv preprint arXiv:1412.6980, 2014.

[Krizhevsky & Hinton(2009)Krizhevsky and Hinton]cifar
Krizhevsky, Alex and Hinton, Geoffrey.
Learning multiple layers of features from tiny images.
2009.

[Lafond et al.(2017)Lafond, Vasilache, and Bottou]lafond2017diagonal
Lafond, Jean, Vasilache, Nicolas, and Bottou, Léon.
Diagonal rescaling for neural networks.
arXiv preprint arXiv:1705.09319, 2017.

[LeCun et al.(1998a)LeCun, Bottou, Bengio, and
  Haffner]lecun1998gradient
LeCun, Yann, Bottou, Léon, Bengio, Yoshua, and Haffner, Patrick.
Gradient-based learning applied to document recognition.
Proceedings of the IEEE, 860 (11):0
  2278–2324, 1998a.

[LeCun et al.(2015)LeCun, Bengio, and Hinton]lecun2015deep
LeCun, Yann, Bengio, Yoshua, and Hinton, Geoffrey.
Deep learning.
Nature, 5210 (7553):0 436, 2015.

[LeCun et al.(1998b)LeCun, Bottou, Orr, and
  Müller]lecun1998efficient
LeCun, Yann A, Bottou, Léon, Orr, Genevieve B, and Müller,
  Klaus-Robert.
Efficient backprop.
In Neural networks: Tricks of the trade. Springer,
  1998b.

[Marceau-Caron & Ollivier(2016)Marceau-Caron and
  Ollivier]marceau2016practical
Marceau-Caron, Gaétan and Ollivier, Yann.
Practical Riemannian neural networks.
arXiv preprint arXiv:1602.08007, 2016.

[Martens & Grosse(2015)Martens and Grosse]martens2015optimizing
Martens, James and Grosse, Roger.
Optimizing neural networks with Kronecker-factored approximate
  curvature.
In International Conference on Machine Learning (ICML), pp.  2408–2417, 2015.

[Nesterov(2013)]nesterov2013introductory
Nesterov, Yurii.
Introductory lectures on convex optimization: A basic course,
  volume 87.
Springer Science & Business Media, 2013.

[Ollivier(2015)]ollivier2015riemannian
Ollivier, Yann.
Riemannian metrics for neural networks I: feedforward networks.
Information and Inference: A Journal of the IMA, 40
  (2):0 108–153, 2015.

[Paszke et al.(2017)Paszke, Gross, Chintala, Chanan, Yang, DeVito, Lin,
  Desmaison, Antiga, and Lerer]pytorch
Paszke, Adam, Gross, Sam, Chintala, Soumith, Chanan, Gregory, Yang, Edward,
  DeVito, Zachary, Lin, Zeming, Desmaison, Alban, Antiga, Luca, and Lerer,
  Adam.
Automatic differentiation in PyTorch.
2017.

[Qian(1999)]qian1999momentum
Qian, Ning.
On the momentum term in gradient descent learning algorithms.
Neural networks, 120 (1):0 145–151, 1999.

[Rumelhart et al.(1986)Rumelhart, Hinton, and
  Williams]rumelhart1986learning
Rumelhart, David E, Hinton, Geoffrey E, and Williams, Ronald J.
Learning representations by back-propagating errors.
nature, 3230 (6088):0 533, 1986.

[Seide & Agarwal(2016)Seide and Agarwal]CNTK
Seide, Frank and Agarwal, Amit.
CNTK: Microsoft's open-source deep-learning toolkit.
In Proceedings of the 22nd ACM SIGKDD International Conference
  on Knowledge Discovery and Data Mining, pp.  2135–2135. ACM, 2016.

[Simonyan & Zisserman(2015)Simonyan and Zisserman]simonyan2014very
Simonyan, Karen and Zisserman, Andrew.
Very deep convolutional networks for large-scale image recognition.
In ICLR, 2015.

[Singh et al.(2015)Singh, De, Zhang, Goldstein, and
  Taylor]singh2015layer
Singh, B., De, S., Zhang, Y., Goldstein, T., and Taylor, G.
Layer-specific adaptive learning rates for deep networks.
In IEEE 14th International Conference on Machine Learning and
  Applications (ICMLA), pp.  364–368, Dec 2015.

[Sutskever et al.(2013)Sutskever, Martens, Dahl, and
  Hinton]sutskever2013importance
Sutskever, Ilya, Martens, James, Dahl, George E, and Hinton, Geoffrey E.
On the importance of initialization and momentum in deep learning.
International Conference on Machine Learning (ICML),
  28:0 1139–1147, 2013.

[Ye et al.(2017)Ye, Yang, Fermuller, and Aloimonos]ye2017importance
Ye, Chengxi, Yang, Yezhou, Fermuller, Cornelia, and Aloimonos, Yiannis.
On the importance of consistency in training deep neural networks.
arXiv preprint arXiv:1708.00631, 2017.

[You et al.(2017)You, Gitman, and Ginsburg]you2017large
You, Yang, Gitman, Igor, and Ginsburg, Boris.
Large batch training of convolutional networks.
arXiv preprint arXiv:1708.03888v3, 2017.

[Zhang et al.(2017)Zhang, Xiong, Bradbury, and Socher]zhang2017block
Zhang, Huishuai, Xiong, Caiming, Bradbury, James, and Socher, Richard.
Block-diagonal hessian-free optimization for training neural
  networks.
arXiv preprint arXiv:1712.07296, 2017.




icml2018





Supplementary Material

We walk through the approximated back-matching propagation of the LeNet and show how each layer's weight should be changed (δ') under the rule of the approximated back-matching propagation.
Following the procedure of Algorithm <ref>, we have the following initial value: m=1, s_fc3 = 1, s_fc2 = 1, s_fc1 = 1, s_cv2 = 25, s_cv1 = 196. Given the loss ℓ(x), we can compute the normal gradient on each weight parameter through BP, which are denoted as δ with subscript of the layer name. We start from the top layer fc3 and compute 

δ'_fc3 = δ_fc3 / m / s_fc3 = δ 
and update 
    m ← m·δ a_j/δ' a_j = _fc3^T_2,μ^2.

Since the ReLU activation does not contain parameter and does not change the backward factor m, then we move to the BN layer. Since our BN layer does not have parameter, we only have to update the backward factor 
    m ← m·δ a_j/δ' a_j  =_fc3^T_2,μ^2/_fc2_2,μ^2.

 Then we move to layer fc2 and compute 

δ'_fc2 = δ_fc2 / m / s_fc2 =_fc2_2,μ^2/_fc3^T_2,μ^2 ·δ,
 
and update the backward factor 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2)/_fc2_2,μ^2.
 Then after another BN layer, the backward factor becomes 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2)/(_fc2_2,μ^2 ·_fc1_2,μ^2).
 Then we move to layer fc1 and compute

δ'_fc1 = δ_fc1 / m / s_fc1 =(_fc2_2,μ^2 ·_fc1_2,μ^2)/(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2) ·δ,

and update the backward factor 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2)/(_fc2_2,μ^2 ·_fc1_2,μ^2).
 
After another BN layer, the backward factor becomes 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2)/(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2).
 
Then we move the convolutional layer cv2 and compute 

δ'   _cv2 = δ_cv2 / m / s_cv2 

    =(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2)/25·(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2) ·δ_cv2

and update the backward factor 
    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2·_cv2, col_2,μ^2/(196/25))/(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2).
 
After another BN layer, the backward factor becomes

    m ← m·δ a_j/δ' a_j  =(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2·_cv2, col_2,μ^2/(196/25))/(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2·_cv1, row_2,μ^2).
 
Finally, we move to the bottom convolutional layer cv1 and compute

δ'   _cv1 = δ_cv1 / m / s_cv1 

    =(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2·_cv1, row_2,μ^2)/196(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2·_cv2, col_2,μ^2/(196/25)) ·δ_cv1 

    =(_fc2_2,μ^2 ·_fc1_2,μ^2·_cv2, row_2,μ^2·_cv1, row_2,μ^2)/25(_fc3^T_2,μ^2 ·_fc2^T_2,μ^2 ·_fc1^T_2,μ^2·_cv2, col_2,μ^2) ·δ_cv1





