Title: SEMI-IMPLICIT BACK PROPAGATION

Abstract: Neural network has attracted great attention for a long time and many researchers are devoted to improve the effectiveness of neural network training algorithms. Though stochastic gradient descent (SGD) and other explicit gradient-based methods are widely adopted, there are still many challenges such as gradient vanishing and small step sizes, which leads to slow convergence and instability of SGD algorithms. Motivated by error back propagation (BP) and proximal methods, we propose a semi-implicit back propagation method for neural network training. Similar to BP, the difference on the neurons are propagated in a backward fashion and the parameters are updated with proximal mapping. The implicit update for both hidden neurons and parameters allows to choose large step size in the training algorithm. Finally, we also show that any fixed point of convergent sequences produced by this algorithm is a stationary point of the objective loss function. The experiments on both MNIST and CIFAR-10 demonstrate that the proposed semi-implicit BP algorithm leads to better performance in terms of both loss decreasing and training/validation accuracy, compared to SGD and a similar algorithm ProxBP.

1. INTRODUCTION:

Along with the rapid development of computer hardware, neural network methods have achieved enormous success in divers application fields, such as computer vision (Krizhevsky et al., 2012) , speech recognition (Hinton et al., 2012; Sainath et al., 2013) , nature language process (Collobert et al., 2011) and so on. The key ingredient of neuron network methods amounts to solve a highly non-convex optimization problem. The most basic and popular algorithm is stochastic gradient descent (SGD) (Robbins & Monro, 1951) , especially in the form of "error" back propagation (BP) (Rumelhart et al., 1986 ) that leads to high efficiency for training deep neural networks. Since then many variants of gradient based methods have been proposed, such as Adagrad (Duchi et al., 2011) , Nesterov momentum (Sutskever et al., 2013) , Adam (Kingma & Ba, 2014) and AMSGrad (Reddi et al., 2019) . Recently extensive research are also dedicated to develop second-order algorithms, for example Newton method (Orr & Müller, 2003) and L-BFGS (Le et al., 2011) .

It is well known that the convergence of explicit gradient descent type approaches require sufficiently small step size. For example, for a loss function with Lipschitz continuous gradient, the stepsize should be in the range of (0, 2/L) for L being the Lipschitz constant, which is in general extremely big for real datasets. Another difficulties in gradient descent approaches is to propagate the "error" deeply due to nonlinear activation functions, which is commonly known as gradient vanishing. To overcome these problems, implicit updates are more attractive. In (Frerix et al., 2018) , proximal back propagation, namely ProxBP, was proposed to utilize the proximal method for the weight updating. Alternative approach is to reformulate the training problem as a sequence of constrained optimization by introducing the constraints on weights and hidden neurons at each layer. Block coordinate descent methods (Carreira-Perpinan & Wang, 2014; Zhang & Brand, 2017) were proposed and analyzed to solve this constrained formulation with square loss functions. Along this line, the Alternating direction method of multipliers (ADMM) (Taylor et al., 2016; Zhang et al., 2016) were also proposed with extra dual variables updating.

Motivated by proposing implicit weight updates to overcome small step sizes and vanishing gradient problems in SGD, we propose a semi-implicit scheme, which has similar form as "error" back propagation through neurons, while the parameters are updated through optimization at each layer. It can be shown that any fixed point of the sequence generated by the scheme is a stationary point of the objective loss function. In contrast to explicit gradient descent methods, the proposed method allows to choose large step sizes and leads to a better training performance per epoch. The performance is also stable with respect to the choice of stepsizes. Compared to the implicit method ProxBP, the proposed scheme only updates the neurons after the activation and the error is updated in a more implicit way, for which better training and validation performances are achieved in the experiments on both MNIST and CIFAR-10.

2. NOTATIONS:

Given input-output data pairs (X, Y ), we consider a N -layer feed-forward fullly connected neural network as shown in Figure 1 . Here, the parameters from the i-th layer to the (i + 1)-th layer are the

X W1,b1 -→ G 2 σ -→ F 2 W2,b2 -→ G 3 • • • G N -1 σ -→ F N -1 W N -1 ,b N -1 -→ F N • • • • • • • • • Figure 1: N-layer Neural Network

weight matrix W i and bias b i , and σ is a non-linear activation function, such as sigmod or ReLU. We denote the neuron vector at i-th layer before activation as G i , and the neurons after activation as

EQUATION

for i = 1, • • • , N -1.

We note that in general at the last layer, there is no non-linear activation function and F N = G N . For ease of notation, we can use an activation function σ as identity. The generic training model aims to solve the following minimization problem:

EQUATION

where θ denotes the collective parameter set {W i , b i } N -1 i=1 and L is some loss function.

3. SEMI-IMPLICIT BACK-PROPAGATION METHOD:

In the following, we first present the classic back propagation (BP) algorithm for an easier introduction of the proposed semi-implicit method.

3.1. BACK PROBATION METHOD:

The widely used BP method Rumelhart et al. (1986) is based on gradient descent algorithm:

θ k+1 = θ k -η ∂J(θ k ; X, Y ) ∂θ (3)

where η > 0 is the stepsize. The main idea of BP algorithm is to use an efficient error propagation scheme on the hidden neurons for computing the partial derivatives of the network parameters at each layer. The so-called "error" signal δ N ≡ ∂J ∂F N at the last level is propagated to the hidden neurons δ i ≡ ∂J ∂Fi using the chain rule. In fact for a square loss function, the gradient at the last layer

EQUATION

And the partial derivative to W i can be computed as

EQUATION

At k-th iteration, after a forward update of the neurons F k i by (1) using the current parameters sets

{W k i , b k i }, i = 1, • • • , N -1,

we can compute the "error" signal at each neurons sequentially from the i + 1 level to i level by (4) and the parameters W k+1 i is updated according to the gradient at the point W k i computed by (5).

3.2. SEMI-IMPLICIT UPDATES:

Compared to the BP method, we propose to update the hidden neurons and the parameters sets at each layer in an implicit way.

At the iteration k, given the current estimate

θ k : {W k i , b k i }, we first update the neuron F k i and G k i

in a feedforward fashion as BP method, by using (1

) for i = 1, • • • , N -1.

For the backward stage, we start with updating neuron F N at the the last layer using the gradient descent:

EQUATION

) For i = N -1, • • • , 1, given F k+ 1 2 i+1

, the parameters W i , b i are updated by solving the following optimization problem (once)

       W k+1 i = arg min Wi σ(W i F k i + b k i ) -F k+ 1 2 i+1 2 F + λ 2 W i -W k i 2 F b k+1 i = arg min bi σ(W k+1 i F k i + b i ) -F k+ 1 2 i+1 2 F + λ 2 b i -b k i 2 F (7)

where λ > 0 is a parameter that is corresponding to stepsize. This update of parameters is related to using an implicit gradient based on so-called proximal mapping. Taking W i as an example, the optimality in (7) gives

W k+1 i = W k i - 1 λ ∇f (W k+1 i ) where f (W i ) = σ(W i F k i +b k i )-F k+ 1 2 i+1 2 F .

Compared to a direct gradient descent step, this update is unconditionally stable for any stepsize 1/λ. We note that proximal mapping was previously proposed for training neural network as ProxBP in (Frerix et al., 2018) . However the update of the parameter sets is different as ProxBP uses G i+1 for the data fitting at each layer. The two subproblems at each layer can be solved by a nonlinear conjugate gradient method.

After the update of W k+1 i and b k+1 i , we need to update the hidden neuron F i . As classical BP, we first consider the gradient at F k i as

EQUATION

)

It can be seen that the partial derivative

∂G k i+1 ∂F k i := W k i .

Different from BP and ProxBP, we use the newly updated W k+1 i instead of W k i to compute the error:

δ k i := (W k+1 i ) T • (∂σ(G k i+1 ) δ k+1 i+1 ), F k+ 1 2 i = F k i -ηδ k i (9)

By this formula, the difference can be propagated from the level N to 1. At the last level i = 1, we only need to update W k+1 1 and b k+1 1 as F 1 = X. The overall semi-implicit back propagation method is summarized in Algorithm 1. For large scale training problem, the back propagation is used in the form of stochastic gradient descent (SGD) using a small set of samples. The proposed semi-implicit method can be easily extended to stochastic version by replacing (X, Y ) by a batch set (X mini , Y mini ) at each iteration in Algorithm 1.

Algorithm 1 Semi-implicit back propagation:

Input: Current parameters θ k = {W k i , b k i } // Forward pass F 1 = X for i = 1 to N -1 do G k i+1 = W k i F k i + b i F k i+1 = σ(G k i+1

) end for // Update on the hidden neurons and the parameters Update on

F k N for i = N -1 to 2 do Implicit update on W k i , b k i

Error propagation and update on

F k i → F k+ 1 2 i end for Implicit update on W k 1 , b k 1 Output: New parameters θ k+1 = {W k+1 i , b k+1 i } 3.3 FIXED POINTS OF SEMI-IMPLICIT METHOD

The follow proposition indicates that any fixed point of the iteration is a stationary point of the objective energy function.

Proposition 1 Assume that L and the activation functions σ are continuously differentiable. If

θ k k→∞ -→ θ * for θ * = {W * i , b * i }, then θ * is a stationary point of the energy function J(θ; X, Y ).

Proof Due to the forward update,

{W k i , b k i } k→∞ -→ {W * i , b * i } infers that {F k i , G k i } k→∞ -→ {F * i , G * i } where G * i = W * i F * i-1 + b * i and G * i = σ(F * i ) for i = 1, • • • , N .

At the last layer, the neuron F N is updated with gradient descent:

EQUATION

)

Take a limit, we have

EQUATION

)

Now we show

EQUATION

)

for i = N, • • • , 2 using mathematical induction. The first equation is shown for i = N . By the optimality of equation 7, we have

EQUATION

It is easy to see that the limit of F

EQUATION

With mathematical induction we obtain that ∂J ∂θ * = 0.

4. NUMERICAL EXPERIMENTS:

In this section, we will compare the performance of BP, ProxBP Frerix et al. (2018) and the proposed semi-implicit BP using MNIST and CIFAT-10 datasets. All the experiments are performed on MATLAB with a 12-core CPU and the same network setting and initializations are used for a fair comparison. We use softmax cross-entropy for the loss function L and ReLU for the activation function, as usually chosen in classification problems. For the linear CG used in ProxBP and nonlinear CG in semi-implicit BP, the iterations number is set as 5. Finally the weights and bias are initialized by normal distribution with average 0 and standard deviation 0.01.

In MNIST experiments, the training set contains 55000 samples and the rest are included in the validation set. For CIFAR-10, a set of 45000 samples is used as training set and the rest as validation set. The training process are performed 5 times, and Table 1 shows the average training and validation accuracy achieved by SGD, Semi-implicit BP with different learning rates η (for SGD) and 1/λ for semi-implicit BP on MNIST. It can be seen that after 2 epoch, semi-implicit BP method already achieves high accuracy as high as 99% and the performance is very stable with respect to different stepsize choices, while SGD fails for some choices of stepsize η. For ProxBP, we present the results with η = 1 as the best performance is achieved with this set of parameters. The highest accuracies are marked in bold in each column, and we can see that semi-implicit BP achieves the highest training and test accuracy than BP and ProxBP.

In Figure 2 and 3, we show the performance of the three methods per epoch for MNIST and CIFAR-10. For the CIFAR-10 experiment, we train a 3072 × 2000 × 500 × 10 neural network and the rest settings are the same as MNIST dataset experiments. For both datasets, we choose the step size η = 0.1 for semi-implicit BP and ProxBP, while a smaller one to guarantee SGD achieves a best better performance. The evolution of training loss and training accuracy shows that the performance of ProxBP is not as good as SGD for MNIST while it is better than SGD on CIFAR-10. For both experiments, the performance of semi-implicit BP method leads to the fastest convergence. The improvement on the validation accuracy also demonstrates that the proposed semi-implicit BP method also generalize well in a comparison to the other two methods. 

5. CONCLUSION:

We proposed a novel optimization scheme in order to overcome the difficulties of small stepsize and vanishing gradient in training neural networks. The computation of new scheme is in the spirit of error back propagation, with an implicit updates on the parameters sets and semi-implicit updates on the hidden neurons. The experiments on both MNIST and CIFAR-10 show that the proposed semi-implicit back propagation has better performance per epoch compared to SGD and ProxBP. It is demonstrated in the experiment that larger step sizes can be adopted without losing stability and performance. It can be also seend that the proposed scheme is flexible and some regularization can be easily integrated if needed. The fixed points of the scheme are shown to be stationary points of the objective loss function and further rigorous theoretical convergence will be explored in an ongoing work.

:



Figures and Tables:

Figure 2: MNIST. Batch size 100

Semi-implicit (λ = 1, η) 0.9780 0.9801 0.9904 0.9737 0.9104 0.9710 0.9724 0.9800 0.9748 0.9338 Semi-implicit (η = 0.1, 1/λ) 0.9765 0.9752 0.9735 0.9598 0.9206 0.9736 0.9778 0.9738 0.9672 0.9394 Training and validation accuracy with different step sizes for 2 epoch.

Table content: <table><tr><td>MNIST(784 × 500 × 10)</td><td/><td colspan="3">Training/validation accuracy</td><td/></tr><tr><td>learning rates</td><td>100</td><td>10</td><td>1</td><td>0.1</td><td>0.01</td></tr><tr><td>SGD, η</td><td colspan="5">0.0985 0.1123 0.0980 0.9487 0.8885 0.1002 0.1126 0.0924 0.9492 0.8988</td></tr><tr><td>ProxBP (λ = 1, η)</td><td colspan="5">0.9239 0.9349 0.9390 0.9032 0.8415 0.9344 0.9374 0.9494 0.9244 0.8832</td></tr><tr><td>ProxBP (η = 1, 1/λ)</td><td colspan="5">0.9420 0.9444 0.9383 0.9171 0.8743 0.9486 0.9554 0.9494 0.9344 0.9064</td></tr></table>

Peer review (iclr2020):
This paper proposes an implicit update scheme for the back propagation a anlgorithm. The idea is quite simple and is based on proximal mappings that lead to implicit update. Specifically, every update in the back propagation algorithm is being replaced by an implicit update except for the intermediate parameters that receive a *semi-implicit* update. The idea is reasonable and seems to lead to good performance. This is more-or-less expected thanks to the superior performance of implicit updates in general. So, it*s good that the authors could make this work in the context of deep nets as well. Here are some more critical thoughts about the paper: 1) There is not much theoretical justification about the idea in the paper. Proposition 1 is a simple argument about the fixed point of the procedure. The argument could be made more rigorous, right now it is a bit of a sketch. Apart from Proposition 1, there is no more theory offered. The authors could appeal in the theory of implicit SGD for that, e.g., [1,2,3,4]. This theory suggests a lot of stability properties for the implicit SGD update of Equation (27). 2) Somewhat related to (1), the authors could make a more clear connection to prior work. For example, there is not mention of a very similar idea of *implicit back propagation* [5]. Also the literature in implicit SGD procedures is highly relevant. 3) Can we explain the results in Table 1 theoretically? [1] Bertsekas, *Incremental proximal methods for large scale convex optimization. Mathematical programming*, 2011 [2] Kulis and Bartlett, *Implicit online learning*, 2010 [3] Toulis and Airoldi, *Asymptotic and finite-sample properties of estimators based on stochastic gradients*, 2017 [4] Toulis, Airoldi, Rennie, *Statistical analysis of stochastic gradient methods for generalized linear models*, 2014 [5] Fagan and Iyengar, *Robust Implicit Backpropagation*, 2018