Difference Target Propagation

Introduction

Recently, deep neural networks have achieved great success in hard AI tasks , mostly relying on back-propagation as the main way of performing credit assignment over the different sets of parameters associated with each layer of a deep net. Back-propagation exploits the chain rule of derivatives in order to convert a loss gradient on the activations over layer $l$ (or time $t$, for recurrent nets) into a loss gradient on the activations over layer $l-1$ (respectively, time $t-1$). However, as we consider deeper networks– e.g., consider the recent best ImageNet competition entrants with 19 or 22 layers – longer-term dependencies, or stronger non-linearities, the composition of many non-linear operations becomes more strongly non-linear. To make this concrete, consider the composition of many hyperbolic tangent units. In general, this means that derivatives obtained by back-propagation are becoming either very small (most of the time) or very large (in a few places). In the extreme (very deep computations), one would get discrete functions, whose derivatives are 0 almost everywhere, and infinite where the function changes discretely. Clearly, back-propagation would fail in that regime. In addition, from the point of view of low-energy hardware implementation, the ability to train deep networks whose units only communicate via bits would also be interesting.

This limitation of back-propagation to working with precise derivatives and smooth networks is the main machine learning motivation for this paper’s exploration into an alternative principle for credit assignment in deep networks. Another motivation arises from the lack of biological plausibility of back-propagation, for the following reasons: (1) the back-propagation computation is purely linear, whereas biological neurons interleave linear and non-linear operations, (2) if the feedback paths were used to propagate credit assignment by back-propagation, they would need precise knowledge of the derivatives of the non-linearities at the operating point used in the corresponding feedforward computation, (3) similarly, these feedback paths would have to use exact symmetric weights (with the same connectivity, transposed) of the feedforward connections, (4) real neurons communicate by (possibly stochastic) binary values (spikes), (5) the computation would have to be precisely clocked to alternate between feedforward and back-propagation phases, and (6) it is not clear where the output targets would come from.

The main idea of target propagation is to associate with each feedforward unit’s activation value a target value rather than a loss gradient. The target value is meant to be close to the activation value while being likely to have provided a smaller loss (if that value had been obtained in the feedforward phase). In the limit where the target is very close to the feedforward value, target propagation should behave like back-propagation. This link was nicely made in , which introduced the idea of target propagation and connected it to back-propagation via a Lagrange multipliers formulation (where the constraints require the output of one layer to equal the input of the next layer). A similar idea was recently proposed where the constraints are relaxed into penalties, yielding a different (iterative) way to optimize deep networks . Once a good target is computed, a layer-local training criterion can be defined to update each layer separately, e.g., via the delta-rule (gradient descent update with respect to the cross-entropy loss).

By its nature, target propagation can in principle handle stronger (and even discrete) non-linearities, and it deals with biological plausibility issues (1), (2), (3) and (4) described above. Extensions of the precise scheme proposed here could handle (5) and (6) as well, but this is left for future work.

In this paper, we describe how the general idea of target propagation by using auto-encoders to assign targets to each layer (as introduced in an earlier technical report ) can be employed for supervised training of deep neural networks (section 2.1 and 2.2). We continue by introducing a linear correction for the imperfectness of the auto-encoders (2.3) leading to robust training in practice. Furthermore, we show how the same principles can be applied to replace back-propagation in the training of auto-encoders (section 2.4). In section 3 we provide several experimental results on rather deep neural networks as well as discrete and stochastic networks and auto-encoders. The results show that the proposed form of target propagation is comparable to back-propagation with RMSprop - a very popular setting to train deep networks nowadays- and achieves state of the art for training stochastic neural nets on MNIST.

Target Propagation

Although many variants of the general principle of target propagation can be devised, this paper focuses on a specific approach, which is based on the ideas presented in an earlier technical report and is described in the following.

Let us consider an ordinary (supervised) deep network learning process, where the training data is drawn from an unknown data distribution $p(\mathbf{x},\mathbf{y})$. The network structure is defined by

where $\mathbf{h}_{i}$ is the state of the $i$-th hidden layer (where $\mathbf{h}_{M}$ corresponds to the output of the network and $\mathbf{h}_{0}=\mathbf{x}$) and $f_{i}$ is the $i$-th layer feed-forward mapping, defined by a non-linear activation function $s_{i}$ (e.g. the hyperbolic tangents or the sigmoid function) and the weights $W_{i}$ of the $i$-th layer. Here, for simplicity of notation, the bias term of the $i$-th layer is included in $W_{i}$. We refer to the subset of network parameters defining the mapping between the $i$-th and the $j$-th layer ($0\leq i<j\leq M$) as $\mathbf{\theta}_{W}^{i,j}=\{W_{k},k=i+1,\dots,j\}$. Using this notion, we can write $\mathbf{h}_{j}$ as a function of $\mathbf{h}_{i}$ depending on parameters $\mathbf{\theta}_{W}^{i,j}$, that is we can write $\mathbf{h}_{j}=\mathbf{h}_{j}(\mathbf{h}_{i};\mathbf{\theta}_{W}^{i,j})$.

to emphasize the dependency of the loss on the state of the $i$-th layer.

Training a network with back-propagation corresponds to propagating error signals through the network to calculate the derivatives of the global loss with respect to the parameters of each layer. Thus, the error signals indicate how the parameters of the network should be updated to decrease the expected loss. However, in very deep networks with strong non-linearities, error propagation could become useless in lower layers due to exploding or vanishing gradients, as explained above.

To avoid this problems, the basic idea of target propagation is to assign to each $\mathbf{h}_{i}(\mathbf{x};\mathbf{\theta}_{W}^{0,i})$ a nearby value $\hat{\mathbf{h}}_{i}$ which (hopefully) leads to a lower global loss, that is which has the objective to fulfill

Such a $\hat{\mathbf{h}}_{i}$ is called a target for the $i$-th layer.

Given a target $\hat{\mathbf{h}}_{i}$ we now would like to change the network parameters to make $\mathbf{h}_{i}$ move a small step towards $\hat{\mathbf{h}}_{i}$, since – if the path leading from $\mathbf{h}_{i}$ to $\hat{\mathbf{h}}_{i}$ is smooth enough – we would expect to yield a decrease of the global loss. To obtain an update direction for $W_{i}$ based on $\hat{\mathbf{h}}_{i}$ we can define a layer-local target loss $L_{i}$, for example by using the MSE

Then, $W_{i}$ can be updated locally within its layer via stochastic gradient descent, where $\hat{\mathbf{h}}_{i}$ is considered as a constant with respect to $W_{i}$. That is

where $\eta_{f_{i}}$ is a layer-specific learning rate.

Note, that in this context, derivatives can be used without difficulty, because they correspond to computations performed inside a single layer. Whereas, the problems with the severe non-linearities observed for back-propagation arise when the chain rule is applied through many layers. This motivates target propagation methods to serve as alternative credit assignment in the context of a composition of many non-linearities.

However, it is not directly clear how to compute a target that guarantees a decrease of the global loss (that is how to compute a $\hat{\mathbf{h}}_{i}$ for which equation (3) holds) or that at least leads to a decrease of the local loss $L_{i+1}$ of the next layer, that is

Proposing and validating answers to this question is the subject of the rest of this paper.

2 How to assign a proper target to each layer

Clearly, in a supervised learning setting, the top layer target should be directly driven from the gradient of the global loss

where $\hat{\eta}$ is usually a small step size. Note, that if we use the MSE as global loss and $\hat{\eta}=0.5$ we get $\hat{\mathbf{h}}_{M}=\mathbf{y}$.

But how can we define targets for the intermediate layers? In the previous technical report , it was suggested to take advantage of an “approximate inverse”. To formalize this idea, suppose that for each $f_{i}$ we have a function $g_{i}$ such that

would have the consequence that (under some smoothness assumptions on $f$ and $g$) minimizing the distance between $\mathbf{h}_{i-1}$ and $\hat{\mathbf{h}}_{i-1}$ should also minimize the loss $L_{i}$ of the $i$-th layer. This idea is illustrated in the left of Figure 1. Indeed, if the feed-back mappings were the perfect inverses of the feed-forward mappings ($g_{i}=f_{i}^{-1}$), one gets

But choosing $g$ to be the perfect inverse of $f$ may need heavy computation and instability, since there is no guarantee that $f^{-1}_{i}$ applied to a target would yield a value that is in the domain of $f_{i-1}$. An alternative approach is to learn an approximate inverse $g_{i}$, making the $f_{i}$ / $g_{i}$ pair look like an auto-encoder. This suggests parametrizing $g_{i}$ as follows:

where $\bar{s}_{i}$ is a non-linearity associated with the decoder and $\mathbf{V}_{i}$ the matrix of feed-back weights of the $i$-th layer. With such a parametrization, it is unlikely that the auto-encoder will achieve zero reconstruction error. The decoder could be trained via an additional auto-encoder-like loss at each layer

Changing $\mathbf{V}_{i}$ based on this loss, makes $g$ closer to $f_{i}^{-1}$. By doing so, it also makes $f_{i}(\hat{\mathbf{h}}_{i-1})=f_{i}(g_{i}(\hat{\mathbf{h}}_{i}))$ closer to $\hat{\mathbf{h}}_{i}$, and is thus also contributing to the decrease of $L_{i}(\hat{\mathbf{h}}_{i},f_{i}(\hat{\mathbf{h}}_{i-1}))$. But we do not want to estimate an inverse mapping only for the concrete values we see in training but for a region around the these values to facilitate the computation of $g_{i}(\hat{\mathbf{h}_{i}})$ for $\hat{\mathbf{h}_{i}}$ which have never been seen before. For this reason, the loss is modified by noise injection

which makes $f_{i}$ and $g_{i}$ approximate inverses not just at $\mathbf{h}_{i-1}$ but also in its neighborhood.

As mentioned above, a required property of target propagation is, that the layer-wise parameter updates, each improving a layer-wise loss, also lead to an improvement of the global loss. The following theorem shows that, for the case that $g_{i}$ is a perfect inverse of $f_{i}$ and $f_{i}$ having a certain structure, the update direction of target propagation does not deviate more then 90 degrees from the gradient direction (estimated by back-propagation), which always leads to a decrease of the global loss.

Assume that $g_{i}=f_{i}^{-1},i=1,...,M$, and $f_{i}$ satisfies $\mathbf{h}_{i}=f_{i}(\mathbf{h}_{i-1})=W_{i}s_{i}(\mathbf{h}_{i-1})$ This is another way to obtain a non-linear deep network structure. where $s_{i}$ can be any differentiable monotonically increasing element-wise function. Let $\delta W_{i}^{tp}$ and $\delta W_{i}^{bp}$ be the target propagation update and the back-propagation update in $i$-th layer, respectively. If $\hat{\eta}$ in Equation (7) is sufficiently small, then the angle $\alpha$ between $\delta W_{i}^{tp}$ and $\delta W_{i}^{bp}$ is bounded by

Here $\lambda_{max}$ and $\lambda_{min}$ are the largest and smallest singular values of $(J_{f_{M}}\dots J_{f_{i+1}})^{T}$, where $J_{f_{k}}$ is the Jacobian matrix of $f_{k}$ and $\Delta_{1}(\hat{\eta})$ and $\Delta_{2}(\hat{\eta})$ are close to 0 if $\hat{\eta}$ is sufficiently small.

3 Difference target propagation

From our experience, the imperfection of the inverse function leads to severe optimization problems when assigning targets based on equation (9). This brought us to propose the following linearly corrected formula for target propagation which we refer to as “difference target propagation”

Note, that if $g_{i}$ is the inverse of $f_{i}$, difference target propagation becomes equivalent to vanilla target propagation as defined in equation (9). The resulting complete training procedure for optimization by difference target propagation is given in Algorithm 1.

In the following, we explain why this linear corrected formula stabilizes the optimization process. In order to achieve stable optimization by target propagation, $\mathbf{h}_{i-1}$ should approach $\hat{\mathbf{h}}_{i-1}$ as $\mathbf{h}_{i}$ approaches $\hat{\mathbf{h}}_{i}$. Otherwise, the parameters in lower layers continue to be updated even when an optimum of the global loss is reached already by the upper layers, which then could lead the global loss to increase again. Thus, the condition

greatly improves the stability of the optimization. This holds for vanilla target propagation if $g_{i}=f_{i}^{-1}$, because

Although the condition is not guaranteed to hold for vanilla target propagation if $g_{i}\neq f_{i}^{-1}$, for difference target propagation it holds by construction, since

Furthermore, under weak conditions on $f$ and $g$ and if the difference between $\mathbf{h}_{i}$ and $\hat{\mathbf{h}}_{i}$ is small, we can show for difference target propagation that if the input of the $i$-th layer becomes $\hat{\mathbf{h}}_{i-1}$ (i.e. the $i-1$-th layer reaches its target) the output of the $i$-th layer also gets closer to $\hat{\mathbf{h}}_{i}$. This means that the requirement on targets specified by equation (6) is met for difference target propagation, as shown in the following theorem

Let the target for layer $i-1$ be given by Equation (15), i.e. $\hat{\mathbf{h}}_{i-1}=\mathbf{h}_{i-1}+g_{i}(\hat{\mathbf{h}}_{i})-g_{i}(\mathbf{h}_{i})$. If $\hat{\mathbf{h}}_{i}-\mathbf{h}_{i}$ is sufficiently small, $f_{i}$ and $g_{i}$ are differentiable, and the corresponding Jacobian matrices $J_{f_{i}}$ and $J_{g_{i}}$ satisfy that the largest eigenvalue of $(I-J_{f_{i}}J_{g_{i}})^{T}(I-J_{f_{i}}J_{g_{i}})$ is less than $1$, then we have

The third condition in the above theorem is easily satisfied in practice, because $g_{i}$ is learned to be the inverse of $f_{i}$ and makes $g_{i}\circ f_{i}$ close to the identity mapping, so that $(I-J_{f_{i}}J_{g_{i}})$ becomes close to the zero matrix which means that the largest eigenvalue of $(I-J_{f_{i}}J_{g_{i}})^{T}(I-J_{f_{i}}J_{g_{i}})$ is also close to $0$.

4 Training an auto-encoder with difference target propagation

Auto-encoders are interesting for learning representations and serve as building blocks for deep neural networks . In addition, as we have seen, training auto-encoders is part of the target propagation approach presented here, where they model the feedback paths used to propagate the targets.

In the following, we show how a regularized auto-encoder can be trained using difference target propagation instead of back-propagation. Like in the work on denoising auto-encoders and generative stochastic networks , we consider the denoising auto-encoder like a stochastic network with noise injected in input and hidden units, trained to minimize a reconstruction loss. This is, the hidden units are given by the encoder as

where $sig$ is the element-wise sigmoid function, $\mathbf{W}$ the weight matrix and $\mathbf{b}$ the bias vector of the input units. The reconstruction is given by the decoder

with $\mathbf{c}$ being the bias vector of the hidden units. And the reconstruction loss is

where a regularization term can be added to obtain a contractive mapping. In order to train this network without back-propagation (that is, without using the chain rule), we can use difference target propagation as follows (see Figure 1 (right) for an illustration): at first, the target of $\mathbf{z}$ is just $\mathbf{x}$, so we can train the reconstruction mapping $g$ based on the loss $L_{g}=||g(\mathbf{h})-\mathbf{x}||^{2}_{2}$ in which $\mathbf{h}$ is considered as a constant. Then, we compute the target $\hat{\mathbf{h}}$ of the hidden units following difference target propagation where we make use of the fact that $f$ is an approximate inverse of $g$. That is,

where the last equality follows from $f(\hat{\mathbf{z}})=f(\mathbf{x})=\mathbf{h}$. As a target loss for the hidden layer, we can use $L_{f}=||f(\mathbf{x}+\epsilon)-\hat{\mathbf{h}}||^{2}_{2}$, where $\hat{\mathbf{h}}$ is considered as a constant and which can be also augmented by a regularization term to yield a contractive mapping.

Experiments

In a set of experiments we investigated target propagation for training deep feedforward deterministic neural networks, networks with discrete transmissions between units, stochastic neural networks, and auto-encoders.

For discrete stochastic networks in which some form of noise (here Gaussian) is injected, we used a decaying noise level for learning the inverse mapping, in order to stabilize learning, i.e. the standard deviation of the Gaussian is set to $\sigma(e)=\sigma_{0}/(1+e/e_{0})$ where $\sigma_{0}$ is the initial value, $e$ is the epoch number and $e_{0}$ is the half-life of this decay. This seems to help to fine-tune the feedback weights at the end of training.

In all experiments, the weights were initialized with orthogonal random matrices and the bias parameters were initially set to zero. All experiments were repeated 10 times with different random initializations. We put the code of these experiments online (https://github.com/donghyunlee/dtp).

As a primary objective, we investigated training of ordinary deep supervised networks with continuous and deterministic units on the MNIST dataset. We used a held-out validation set of 10000 samples for choosing hyper-parameters. We trained networks with 7 hidden layers each consisting of 240 units (using the hyperbolic tangent as activation function) with difference target propagation and back-propagation.

Training was based on RMSprop where hyper-parameters for the best validation error were found using random search . RMSprop is an adaptive learning rate algorithm known to lead to good results for back-propagation. Furthermore, it is suitable for updating the parameters of each layer based on the layer-wise targets obtained by target propagation. Our experiments suggested that when using a hand-selected learning rate per layer rather than the automatically set one (by RMSprop), the selected learning rates were different for each layer, which is why we decided to use an adaptive method like RMSprop.

The results are shown in Figure 2. We obtained a test error of 1.94% with target propagation and 1.86% with back propagation. The final negative log-likelihood on the training set was $4.584\times 10^{-5}$ with target propagation and $1.797\times 10^{-5}$ with back propagation. We also trained the same network with rectifier linear units and got a test error of 3.15% whereas 1.62% was obtained with back-propagation. It is well known that this nonlinearity is advantageous for back-propagation, while it seemed to be less appropriate for this implementation of target propagation.

In a second experiment we investigated training on CIFAR-10. The experimental setting was the same as for MNIST (using the hyperbolic tangent as activation function) except that the network architecture was 3072-1000-1000-1000-10. We did not use any preprocessing, except for scaling the input values to lay in , and we tuned the hyper-parameters of RMSprop using a held-out validation set of 1000 samples. We obtained mean test accuracies of 50.71% and 53.72% for target propagation and back-propagation, respectively. It was reported in , that a network with 1 hidden layer of 1000 units achieved 49.78% accuracy with back-propagation, and increasing the number of units to 10000 led to 51.53% accuracy. As the current state-of-the-art performance on the permutation invariant CIFAR-10 recognition task, reported 64.1% but when using PCA without whitening as preprocessing and zero-biased auto-encoders for unsupervised pre-training.

2 Networks with discretized transmission between units

To explore target propagation for an extremely non-linear neural network, we investigated training of discrete networks on the MNIST dataset. The network architecture was 784-500-500-10, where only the 1st hidden layer was discretized. Inspired by biological considerations and the objective of reducing the communication cost between neurons, instead of just using the step activation function, we used ordinary neural net layers but with signals being discretized when transported between the first and second layer. The network structure is depicted in the right plot of Figure 3 and the activations of the hidden layers are given by

where $sign(x)=1$ if $x>0$, and $sign(x)=0$ if $x\leq 0$. The network output is given by

The inverse mapping of the second layer and the associated loss are given by

If feed-forward mapping is discrete, back-propagated gradients become 0 and useless when they cross the discretization step. So we compare target propagation to two baselines. As a first baseline, we train the network with back-propagation and the straight-through estimator , which is biased but was found to work well, and simply ignores the derivative of the step function (which is 0 or infinite) in the back-propagation phase. As a second baseline, we train only the upper layers by back-propagation, while not changing the weight $W_{1}$ which are affected by the discretization, i.e., the lower layers do not learn.

The results on the training and test sets are shown in Figure 3. The training error for the first baseline (straight-through estimator) does not converge to zero (which can be explained by the biased gradient) but generalization performance is fairly good. The second baseline (fixed lower layer) surprisingly reached zero training error, but did not perform well on the test set. This can be explained by the fact that it cannot learn any meaningful representation at the first layer. Target propagation however did not suffer from this drawback and can be used to train discrete networks directly (training signals can pass the discrete region successfully). Though the training convergence was slower, the training error did approach zero. In addition, difference target propagation also achieved good results on the test set.

3 Stochastic networks

Another interesting model class which vanilla back-propagation cannot deal with are stochastic networks with discrete units. Recently, stochastic networks have attracted attention because they are able to learn a multi-modal conditional distribution $P(Y|X)$, which is important for structured output predictions. Training networks of stochastic binary units is also biologically motivated, since they resemble networks of spiking neurons. Here, we investigate whether one can train networks of stochastic binary units on MNIST for classification using target propagation. Following , the network architecture was 784-200-200-10 and the hidden units were stochastic binary units with the probability of turning on given by a sigmoid activation:

that is, $\mathbf{h}_{i}$ is one with probability $\mathbf{h}_{i}^{p}$.

As a baseline, we considered training based on the straight-through biased gradient estimator in which the derivative through the discrete sampling step is ignored (this method showed the best performance in .) That is

With difference target propagation the stochastic network can be trained directly, setting the targets to

where $g_{i}(\mathbf{h}_{i}^{p})=\tanh(V_{i}\mathbf{h}_{i}^{p})$ is trained by the loss

and layer-local target losses are defined as $L_{i}=||\hat{\mathbf{h}}_{i}^{p}-\mathbf{h}_{i}^{p}||^{2}_{2}$.

For evaluation, we averaged the output probabilities for a given input over 100 samples, and classified the example accordingly, following . Results are given in Table 1. We obtained a test error of 1.71% using the baseline method and 1.54% using target propagation, which is – to our knowledge – the best result for stochastic nets on MNIST reported so far. This suggests that target propagation is highly promising for training networks of binary stochastic units.

4 Auto-encoder

We trained a denoising auto-encoder with 1000 hidden units with difference target propagation as described in Section 2.4 on MNIST. As shown in Figure 4 stroke-like filters can be obtained by target propagation. After supervised fine-tuning (using back-propagation), we got a test error of 1.35$\%$. Thus, by training an auto-encoder with target propagation one can learn a good initial representation, which is as good as the one obtained by regularized auto-encoders trained by back-propagation on the reconstruction error.

Conclusion

We introduced a novel optimization method for neural networks, called target propagation, which was designed to overcome drawbacks of back-propagation and is biologically more plausible. Target propagation replaces training signals based on partial derivatives by targets which are propagated based on an auto-encoding feedback loop. Difference target propagation is a linear correction for this imperfect inverse mapping which is effective to make target propagation actually work. Our experiments show that target propagation performs comparable to back-propagation on ordinary deep networks and denoising auto-encoders. Moreover, target propagation can be directly used on networks with discretized transmission between units and reaches state of the art performance for stochastic neural networks on MNIST.

We would like to thank Junyoung Chung for providing RMSprop code, Caglar Gulcehre and Antoine Biard for general discussion and feedback, Jyri Kivinen for discussion of backprop-free auto-encoder, Mathias Berglund for explanation of his stochastic networks. We thank the developers of Theano , a Python library which allowed us to easily develop a fast and optimized code for GPU. We are also grateful for funding from NSERC, the Canada Research Chairs, Compute Canada, and CIFAR.

References

Appendix

Appendix 0.A Proof of Theorem 1

Given a training example $(\mathbf{x},\mathbf{y})$ the back-propagation update is given by

where $J_{f_{k}}=\frac{\partial\mathbf{h}_{k}}{\partial\mathbf{h}_{k-1}}=W_{i}\cdot S_{i}^{\prime}(\mathbf{h}_{k-1}),k=i+1,\dots,M$. Here $S_{i}^{\prime}(\mathbf{h}_{k-1})$ is a diagonal matrix with each diagonal element being element-wise derivatives and $J_{f_{k}}$ is the Jacobian of $f_{k}(\mathbf{h}_{k-1})$. In target propagation the target for $\mathbf{h}_{M}$ is given by $\hat{\mathbf{h}}_{M}=\mathbf{h}_{M}-\hat{\eta}\frac{\partial L}{\partial\mathbf{h}_{M}}$. If all $\mathbf{h}_{k}$’s are allocated in smooth areas and $\hat{\eta}$ is sufficiently small, we can apply a Taylor expansion to get

where $\mathbf{o}(\hat{\eta})$ is the remainder satisfying $\lim_{\hat{\eta}\rightarrow 0}\mathbf{o}(\hat{\eta})/\hat{\eta}=\mathbf{0}$. Now, for $\delta W_{i}^{tp}$ we have

We write $\frac{\partial L}{\partial\mathbf{h}_{M}}$ as l , $s_{i}(\mathbf{h}_{i-1})$ as v and $J_{f_{M}}\dots J_{f_{i+1}}$ as $J$ for short. Then the inner production of vector forms of $\delta W_{i}^{bp}$ and $\delta W_{i}^{tp}$ is

For $||vec(\delta W_{i}^{bp})||_{2}$ and $||vec(\delta W_{i}^{tp})||_{2}$ we have

where $||J^{T}||_{2}$ and $||J^{-1}||_{2}$ are matrix Euclidean norms, i.e. the largest singular value of $(J_{f_{M}}\dots J_{f_{i+1}})^{T}$, $\lambda_{max}$, and the largest singular value of $(J_{f_{M}}\dots J_{f_{i+1}})^{-1}$, $\frac{1}{\lambda_{min}}$ ($\lambda_{min}$ is the smallest singular value of $(J_{f_{M}}\dots J_{f_{i+1}})^{T}$, because $f_{k}$ is invertable, so all the smallest singular values of Jacobians are larger than $0$). Finally, if $\hat{\eta}$ is sufficiently small, the angle $\alpha$ between $vec(\delta W_{i}^{bp})$ and $vec(\delta W_{i}^{tp})$ satisfies:

where the last expression is positive if $\hat{\eta}$ is sufficiently small and $cos(\alpha)\leq 1$ is trivial.

Appendix 0.B Proof of Theorem 2

Let $\mathbf{e}=\hat{\mathbf{h}}_{i}-\mathbf{h}_{i}$. Applying Taylor’s theorem twice, we get

where the vector $\mathbf{o}(||\mathbf{e}||_{2})$ represents the remainder satisfying $\lim_{\mathbf{e}\rightarrow\mathbf{0}}\mathbf{o}(||\mathbf{e}||_{2})/||\mathbf{e}||_{2}=\mathbf{0}$. Then for $||\hat{\mathbf{h}}_{i}-f_{i}(\hat{\mathbf{h}}_{i-1})||^{2}_{2}$ we have

where $o(||\mathbf{e}||^{2}_{2})$ is the scalar value resulting from all terms depending on $\mathbf{o}(||\mathbf{e}||_{2})$ and $\lambda$ is the largest eigenvalue of $(I-J_{f_{i}}J_{g_{i}})^{T}(I-J_{f_{i}}J_{g_{i}})$. If $\mathbf{e}$ is sufficiently small to guarantee $|o(||\mathbf{e}||^{2}_{2})|<(1-\lambda)||\mathbf{e}||^{2}_{2}$, then the left of Equation (A-1) is less than $||\mathbf{e}||^{2}_{2}$ which is just $||\hat{\mathbf{h}}_{i}-\mathbf{h}_{i}||^{2}_{2}$.