LEARNING REPRESENTATIONS FOR BINARY- CLASSIFICATION WITHOUT BACKPROPAGATION
Year: 2020

Abstract:
The family of feedback alignment (FA) algorithms aims to provide a more biologically motivated alternative to backpropagation (BP), by substituting the computations that are unrealistic to be implemented in physical brains. While FA algorithms have been shown to work well in practice, there is a lack of rigorous theory proofing their learning capabilities. Here we introduce the first feedback alignment algorithm with provable learning guarantees. In contrast to existing work, we do not require any assumption about the size or depth of the network except that it has a single output neuron, i.e., such as for binary classification tasks. We show that our FA algorithm can deliver its theoretical promises in practice, surpassing the learning performance of existing FA methods and matching backpropagation in binary classification tasks. Finally, we demonstrate the limits of our FA variant when the number of output neurons grows beyond a certain quantity.

heading: 1 INTRODUCTION
text: A key factor enabling the successes of Deep Learning is the backpropagation of error (BP) algorithm (Rumelhart et al., 1986). Since it has been introduced, BP has sparked several discussions on whether physical brains are realizing BP-like learning or not (Grossberg, 1987; Crick, 1989). Today, most researchers consent that two distinct characteristics of BP render the idea of a BP based learning in brains as implausible: 1) The usage of symmetric forward and backward connections and 2) the strict separation of activity and error propagation (Bartunov et al., 2018). These two objections have lead researchers to search for more biologically motivated alternatives to BP.
The three most influential families of BP alternatives distilled so far are Contrastive Hebbian Learing (CHL) (Movellan, 1991), target-propagation (TP) (LeCun, 1986; Hinton, 2007; Bengio, 2014) and feedback Alignment (FA) (Lillicrap et al., 2016).
The idea of CHL is to propagate the target activities, instead of the errors, backward through the network. For this reason, a temporal dimension is added to the neuron activities. Each neuron then adapts its parameters based on the temporal differences of its ”forward” and ”backward” activity. The two significant critic points of CHL are the requirement for symmetric ”forward-backward” connections and the use of alternating ”forward” and ”backward” phases (Baldi & Pineda, 1991; Bartunov et al., 2018).
TP shares the idea with Contrastive Hebbian Learning of propagating target activities instead of errors. However, rather than keeping symmetric forward and backward paths, the reciprocal propagation of the activities are realized through learned connections. Consequently, each layer has assigned two objectives: Learning the inverse of the layer’s forward function and minimizing the difference to the back-projected target activity. Variants of TP differ in how exactly the target activity is projected backward (LeCun, 1986; Bengio, 2014; Bartunov et al., 2018). Theoretical guarantees of TP rely on the assumption that each reciprocal connection implements the perfect inverse of the corresponding forward function. This issue of an imperfect inverse was also found to be the ”bottleneck” of TP in practice (Bartunov et al., 2018). When the output of a layer has a significant lower dimension than its input, reconstructing the input from the output becomes challenging, resulting in poor learning performance.
Feedback alignment algorithms eliminate the weight sharing implausibility of BP by replacing the symmetric weights in the error backpropagation path by random matrices. The second objection, i.e., separate activity and error channels, is attenuated by Direct Feedback Alignment (Nøkland, 2016) which drastically reduces the number of channels carrying an error signal. While feedback alignment algorithms work well on small and medium-sized benchmarks, a recent study identified that they are unable to provide learning on more challenging datasets like ImageNet (Bartunov et al., 2018). Another criticism of FA algorithms is the lack of rigorous mathematical justification and convergence guarantees of the performed computations.
In this work, we investigate feed-forward networks where the weights of all, expect the first, layers are constrained to positive values. We prove that this constraint does not invalidate the universal approximation capabilities of neural networks. Next, we show that, in combination with monotonic activation functions, all layers from the second layer on realize monotonically increasing functions. The backpropagation of a scalar error signal through these layers only affects the magnitude of the error signal but does not change its sign. Consequently, we prove that algorithms that bypass the error backpropagation steps, such as Direct Feedback Alignment, can compute the sign of the true gradient with respect to the weights of our constraint networks without the need for backpropagation. Finally, we show that our algorithm, which we call monotone Direct Feedback Alignment, can deliver its theoretical promises in practice, by surpassing the learning performance of existing feedback alignment algorithms in binary classification task, i.e., when the error signal is scalar, and provide decent performance even when the error signal is not scalar.
We make the following key contributions:
• First FA algorithm that has provable learning capabilities for non-linear networks of arbitrary depth
• Experimental evaluation showing that our FA algorithm outperforms the learning performance of existing FA algorithms and match backpropagation in binary classification tasks
• We make an efficient TensorFlow implementation of all tested algorithms publicly available1

heading: 2 BACKPROPAGATION AND FEEDBACK ALIGNMENT
text: We consider the feed-forward neural network
hl(hl−1) := { f(Wlhl−1 + bl) if l < L Wlhl−1 + bl if l = L
h0 := x Wl ∈ Rnl×nl−1 , bl ∈ Rnl
(1)
where f is the non-linear activation function, x the input and hL the output of the network. For classification tasks, hL is usually transformed into a probability distribution with discrete support by a sigmoid or softmax function.
During training, the parametersWl, bl, l = 1, . . . L are adjusted to minimize a loss functionL(y, hL) on samples of a giving training distribution p(y, x). This is usually done by performing gradient descent
θl ← θl − α dL dθ , α ∈ R+ (2)
with respect to the parameters θl ∈ {Wl, bl}, 1 ≤ l ≤ n of the network.
1https://github.com/mlech26l/iclr_paper_mdfa
a) BP b) FA c) DFA d) mDFA y y y y

heading: 2.1 BACKPROPAGATION
text: Backpropagation (Rumelhart et al., 1986) is the primary method to compute the gradients needed by the updates in equation (2) by iteratively applying the chain-rule
dL dθl = (dhl dθl )T dL dhl
(3)
dL dhl = (dhl+1 dhl )T dL dhl+1
(4)
dhl+1 dhl = Wl+1diag(f ′(Wl+1hl + bl+1)). (5)
A graphical representation of how information first flow forward and then backward in BP through each layer is shown in Figure (1) a.
Two major concerns argue against the idea that biological neural networks are implementing BPbased learning. I) The weight matrix Wl of the forward path is reused in the backward path in the form of WTl (weight sharing), and II) the strict separation of activity carrying forward and error carrying backward connections (reciprocal error transport).

heading: 2.2 FEEDBACK ALIGNMENT ALGORITHMS
text: Feedback alignment addresses the implausibility of reusing WTl in the backward path by replacing WTl by a fixed random matrix Bl. Lillicrap et al. (2016) showed that this somewhat counterintuitive approach works remarkably well in practice. The term ”feedback alignment” originates from the observations made by Lillicrap et al. (2016) that the angle between the FA update vector and the true gradient starts to decrease, i.e., align, after a few epochs of the training algorithm. Theoretical groundwork on this alignment principle of FA relies on strong assumptions such as a linearized network with one hidden layer (Lillicrap et al., 2016).
FA avoids any weight sharing but does not address the reciprocal error transport implausibility, due to its strict separation of forward and backward pathways, as shown in Figure (1) b. Direct Feedback Alignment (DFA) (Nøkland, 2016) relaxes this issue by replacing all backward paths with a direct feed from the output layer error-gradient dLdhL . Consequently, there is only a single error signal that is distributed across the entire network, which is arguably more biologically plausible than reciprocal error connections. The resulting parameter updates of DFA are of the form
δθl :=
{ dL dhL hL θl
if l = L dL dhL Bl hl θl if l < L (6)
, where Bl ∈ RnL×nl is a random matrix. A graphical schematic of DFA is shown in Figure (1) c. Similar to FA, DFA shows a decent learning performance in mid sized classification tasks (Nøkland, 2016), but fails on more complex datasets such as ImageNet (Bartunov et al., 2018). Theory on adapting the alignment principle to DFA shows that under the strong assumptions of constant DFA update directions and a layer-wise criterion minimization, the DFA update vector will align with the true gradient (Nøkland, 2016; Gilmer et al., 2017).
Recently, Frenkel et al. (2019) proposed to combine ideas from feedback alignment and targetpropagation in their Direct Random Target Projection (DRTP) algorithm. While DRTP shows decent empirical performance, theoretical guarantees about DRTP rely on linearized networks.

heading: 2.3 SIGN-SYMMETRY ALGORITHMS
text: Liao et al. (2016) introduced the sign-symmetry algorithm, a hybrid of BP and FA. Sign-symmetry locks the signs of the feedback weight Bl to have the same signs as WTl , but random absolute value. The authors showed that this approach drastically improves learning performance compared to standard FA. Furthermore, Moskovitz et al. (2018) and Xiao et al. (2019) demonstrated that the sign-symmetry algorithm is even able to match backpropagation for training deep network architectures and large datasets such as ImageNet.
While these empirical observations suggest that the polarity of the error feedback is more important than its magnitude, the mathematical justification of sign-symmetry remains absent. Similar to FA, sign-symmetry relaxes the strict weight sharing implausibility, but still relies on an unrealistic reciprocal error transport.

heading: 3 MONOTONE DIRECT FEEDBACK ALIGNMENT
text: In this section, we first introduce a new class of feed-forward networks, where all, except the first, layers are constrained to realize monotone functions. We call such networks mono-nets and show that they are as expressive as unconstrained feed-forward networks. Next, we prove that for our mono-nets with single output tasks, e.g., binary-classification, feedback alignment algorithms provide the sign of the gradient. The sign of the gradient is interesting for learning, as it tells us if the value of a parameter should be increased or decreased in order to reduce the loss. At the end of this section, we will highlight similarities to algorithms from literature, which can provide resilient learning by only relying on the sign of the gradient.
Neural networks with monotonic constraints have been already studied in literature (You et al., 2017), however not in the context of learning algorithms. Definition 1 (mono-net). A mono-net is a feed-forward neural network with L layers h1, . . . hL, each layer l composted of nl units and the semantics
hl(hl−1) := { f(Wlhl−1 + bl) if l < L Wlhl−1 + bl if l = L
(7)
h0 := x (8) W1 ∈ Rn1×n0 , (9) Wl ∈ R nl×nl−1 + , for l > 1 (10)
bl ∈ Rnl (11) where R+ are the positive reals, i.e. R+ = {x ∈ R|x ≥ 0}, f is a non-linear monotonic increasing activation function, x the input and hL the output of the network.
The major difference between mono-nets and general feed-forward neural networks is the restriction to only positive weight values in layers from the second layer on. Combined with the monotonic increasing activation function, this means that each layer hl(hl−1), l ≥ 2 realizes a monotone increasing function. Because functional composition preserves monotonicity, the complete network up to the first layer hl ◦ hl−1 ◦ · · · ◦ h2(h1) (12) implements a monotone increasing function.
mono-nets are Universal Approximators At first glance, this restriction seems counterproductive, as it might interfere with the expressiveness of the networks. However, we proof in Theorem 1 that our mono-nets with tangent hyperbolic activation are universal approximators, meaning that we can approximate any continuous function arbitrarily close. A potential drawback of the monotonicity constraint is that we might need a larger number of units in the hidden layers to achieve the same expressiveness as a general feed-forward network, as illustrated in our proof of Theorem 1. Theorem 1 (mono-nets are Universal Approximators). Let In be the n-dimensional unit hypercube [0, 1]n and C(In) denote the set of continuous functions f : In → R. We define ‖f‖∞ as the supremum norm of f ∈ C(In) over its domain In. For any given f ∈ C(In) and ε > 0, there exist a function m : In → R of the form
m(x) := M∑ i=1 v̄i tanh(w̄i Tx+ ŵi T (−x) + b̄i) + c (13)
with v̄ ∈ R+M , w̄i ∈ R+n, ŵi ∈ R+n, b̄ ∈ RM , c ∈ R and M <∞ such that ‖m(x)− f(x)‖∞ < ε.
In essence, the set of functions m(x) of the form given in (19) is dense in C(In).
Proof. See supplementary materials 3.
mDFA provides the sign of the gradient Here, we prove that for 1-dimensional outputs DFA applied on a mono-net, which we will call simply mDFA, provides the sign of the true gradient. Note that we focus our methods on DFA instead of ”vanilla” FA, due to the superiority of DFA in terms of biological plausibility and empirical performance (Nøkland, 2016; Bartunov et al., 2018). Theorem 2 (For 1-dimensional outputs mDFA computes the sign of the gradient). Let L(y, hL) be a loss function, m(x) := hL ◦ hL−1 ◦ · · · ◦ h2 ◦ h1 ◦ h0(x) be a mono-net according to Definition 1 with parameters Θ := {Wl, bl
∣∣l = 1, . . . L}. We denote δθ the update value computed by mDFA and ∇θ as the gradient ∂L∂θ for any θ ∈ {Wl, bl} with 1 ≤ l ≤ L. If nL = 1, it follows that(
δθ ) i,j · ( ∇θ ) i,j ≥ 0, (14)
for each coordinate (i, j) of θ.
Proof. See supplementary materials.
A graphical illustration of how activities and errors propagate in mDFA is shown in Figure (1) d.
Literature on learning by relying only on the sign of the gradient Two learning concepts related to mDFA are RPROP (Riedmiller & Braun, 1993; Riedmiller, 1994) and signSGD (Bernstein et al., 2018). RPROP aims to build a more resilient alternative to gradient descent by decoupling the amplitude of the gradient from the step size of parameter updates. In essence, for each coordinate RPROP adapts the step size based on the sign of the most recent gradients computed. Riedmiller & Braun (1993) showed that their approach could stabilize the training of a neural network compared to standard gradient descent.
Performing gradient descent with taking the sign of each gradient coordinate is on an algorithmic level equivalent to the well-known steepest descent method with L∞ norm (Boyd & Vandenberghe, 2004; Bernstein et al., 2018). signSGD (Bernstein et al., 2018) studies convergence properties of the stochastic approximation of this algorithm.
What about networks with more than one output neuron? Theorem 2 applies only to networks with scalar output. As a natural consequence, one may ask whether such theoretical guarantees can be extended to more dimensional output variables. The simple answer is, unfortunately not. In the supplementary materials section A.3 we provide a counterexample showing that Theorem 2 naively extended to two output neurons does not hold anymore.
We want to note that the requirement of a neural network to have only a single output neuron is biologically unjustified. It is known that sub-circuits of biological neuronal networks can feed to multiple motor neuron groups Cook et al. (2019).
How does mDFA relate to the non-negative matrix factorization? A seemingly related concept to mDFA is the non-negative matrix factorization (NMF) algorithm. NMF decomposes an observation matrix V into a weight matrix W and a latent variable matrix H such that V ≈ WH . In contrast to other decomposition-based unsupervised learning methods, all three matrices V,W and H are restricted to non-negative entries. While NMF can model data that is inherently non-negative, such has semantic features of images and text, effectively Yuan & Oja (2005); Shahnaz et al. (2006), the method is unable to learn subtractive and non-linear structures that are present in the data Lee & Seung (1999).
Semi-non-negative matrix factorization Ding et al. (2008) relaxes the original restriction to nonnegative observations of NMF, by only constraining the weight matrix W to be non-negative. Deep semi-NMF Trigeorgis et al. (2014) further enhances the expressiveness of NMF by adding multiple layers and non-linearities between them to the decomposition.
Concerning this work, the semantics of mono-nets from the second layer on is equivalent to that of deep semi-NMF models. However, the unconstrained first layer of mono-nets provides universal approximation capabilities, enabling mono-nets to learn subtractive and non-monotonic input dependencies. Moreover, while deep NMF models are mostly trained via layer-wise learning in an unsupervised context Trigeorgis et al. (2014); Yu et al. (2018), the sole purpose of mono-nets is to investigate alternatives to backpropagation for training multi-layer classifiers.

heading: 4 EXPERIMENTS
text: So far, we have only proven the learning capabilities of mDFA. What remains unclear is whether mDFA can deliver its theoretical promises in practice. In this section, we experimentally evaluate the learning performance of mDFA on a set of empirical benchmarks. We aim to answer the following two questions:
• How well does mDFA perform compared to DFA, FA, and backpropagation in ”natural conditions,” i.e., in binary classification tasks, and
• how much does the performance of mDFA degrade in multi-class classification tasks?
Our performance measure is the achieved classification accuracy of a network trained by a particular method. First, we report the highest achieved accuracy on the training set, which tells us how well the algorithm could fit the model to the training data. Secondly, for each method, we tuned the hyperparameters on a separate validation set and selected the best performing configuration to be evaluated on the test data. The obtained test accuracy tells us how well the model generalizes to data outside the training set.
We evaluate fully-connected networks (FC) and Convolutional networks (CNNs) in form of modified all-convolutional-nets (Springenberg et al., 2015) with tangent hyperbolic, ReLU (Nair & Hinton, 2010), and the hard-tanh non-linearity. The hard-tanh function is defined as
hard-tanh(x) := min(max(x,−1), 1). (15)
Hyperparameters For all training methods, we fixed the batch size to 64, applied no regularization, no normalization, and no data augmentation. Optimizer, i.e., {”Vanilla” Gradient Descent, Adam (Kingma & Ba, 2014), Rmsprop (Tieleman & Hinton, 2012) }, learning rate, training epochs, and weight initialization method were tuned on the validation set. We tested three different weight initialization schemes; all zeros, a scaled uniform, and a normal distribution. Note that all zeros was only tested on the forward weights. Our uniform initialization followed the methodology of Nøkland (2016), i.e., scaling the bounds of the distribution inversely by the square-root of the number of incoming connections of a neuron. In order to comply with the weight constraints of mono-nets, for mDFA the lower bound of the uniform distribution was set to ε = 10−3. Moreover, for mDFA we post-processed the initial weights of the normal distribution by taking their absolute values. Input variables are scaled to [0,1]. Detailed network architectures and a brief discussion about the best performing hyperparameter configurations are listed in the supplementary materials in section B.1 and section B.3.

heading: 4.1 BINARY CLASSIFICATION
text: We created a series of binary classification benchmarks by randomly sampling two classes from the well-studied CIFAR-100 and ImageNet datasets. We then train and test a 1-vs-1 classifier on the samples of the two classes. For each dataset, we create five such ”binarized” sub-datasets and report the mean and standard deviation over these experiments. CIFAR-100 (Krizhevsky et al., 2014) poses a challenging classification dataset, consisting of 32-by-32 RGB images in 100 real-world object categories. ImageNet (Russakovsky et al., 2015) is a large-scale object classification benchmark and de-facto standard to asses new deep learning methods. Each sample is a high-resolution image representing one out of 1000 possible object classes. We pre-processed all samples by cropping and resizing each image to 224-by-224 pixels. Because ImageNet lacks a public test set, we will report the validation accuracy, i.e., as it was reported by Bartunov et al. (2018).
The results on the binarized benchmarks are shown in Table 1 for CIFAR-100 and Table 2 for ImageNet. mDFA could bring the training error to zero for fully-connected networks, and match the test/validation accuracy of backpropagation for convolutional networks.
Poor learning performance for ReLU networks One surprising characteristic in our results is that mDFA fails to provide the same level of learning performance as backpropagation for ReLU networks. Recall that Theorem 1 proves the universal approximation capabilities only for mono-net with tanh activation function. A mono-net with ReLU non-linearity restricts both, the activation and the weight values, to positive values. These constraints arguably limit the approximation capabilities of mono-net in combination with ReLU and thus explain the poor performance of mDFA for ReLU networks. We could validate our hypothesis by testing a rectifier non-linearity that also contains negative values in its image. Coincidentally, the hard-tanh function matches exactly this criterion. Therefore, the decent learning performance of mDFA for hard-tanh networks confirms our hypothesis. Note that also FA and DFA expressed an improvement in performance when switching from ReLU to hard-tanh activation. This observation suggests that feedback alignment algorithms in general benefit from symmetric activation functions.
Discrepancy between fully-connected and convolutional networks Though mDFA achieved the same training accuracy as backpropagation for fully-connected networks, the generalization ability, i.e., test and validation accuracy, slightly lacks behind BP in our binarized-CIFAR-100 benchmark. This observation aligns with the studies by Nøkland (2016); Bartunov et al. (2018). For convolutional neural networks, this effect is reversed, i.e., a decent test/validation accuracy but a higher training error than BP. We speculate that the two tested initialization schemes for the feedback weights caused this discrepancy. Both backpropagation and feedback alignment have been shown to be sensitive to the employed initialization method (Zhang et al., 2019; Bartunov et al., 2018). The restriction to positive values of the weights used in mDFA, requires a re-thinking of the initialization methods examined in the literature. However, we will leave this study open for future work.

heading: 4.2 MULTI-CLASS CLASSIFICATION
text: Here we modify the classification benchmark creation procedure used above, by randomly sampling n classes from the datasets instead of just two. Due to their compelling results in our binary classification benchmark, we restrict our evaluation to networks with tanh activation. Table 3 and Table 4 show the results on our n-class CIFAR-100 benchmark for fully-connected and CNNs respectively. The results on n-class ImageNet can be found in the supplementary materials in Table 5 and 6.
mDFA can provide learning for networks with more than one output neuron Though we do not have a complete theory on mDFA for multi-dimensional outputs, our experiments indicate that mDFA can provide learning for networks with more than one output neuron. In particular, the achieved accuracies of mDFA outperforms other feedback alignment methods for convolutional networks with ten or fewer output neurons. However, mDFA falls behind standard DFA for networks with more than ten output neurons. This observation suggests that our restriction to positive weights can be beneficial even for multi-class tasks but eventually hurts learning performance when the number of classes grows larger.
Feedback alignment algorithms, in general, tend to struggle with increasing output dimension Our results express the trend that with an increase in the number of classes, feedback alignment algorithms struggle to fit the training data. While BP can reduce the training error to almost zero independently of the output dimension, the training errors achieved by FA algorithms are significantly higher and correlate with the number of output neurons. Our observations suggest that the dimension of the error signal affects the training convergence for FA algorithms, in contrast to BP, which appears to be less affected by the dimension of the error signal. This relation potentially provides a step towards understanding why FA algorithms fail on challenging datasets as described by Bartunov et al. (2018).

heading: 5 CONCLUSION
text: Feedback alignment algorithms are promising biologically motivated alternatives to backpropagation. While existing literature provides empirical evidence that FA algorithms can work well in practice, there is still a lack of rigorous theory formalizing their learning capabilities. Here we contributed to the field of biologically motivated learning algorithms, by introducing the first feedback alignment algorithm that provable provides learning for non-linear networks of arbitrary depth and single output neuron. We showed that our FA algorithm outperforms existing FA algorithms in binary classification tasks, and even provide decent learning on multi-class problems.
Limitations We demonstrated on empirical benchmarks as well as theoretical examples that our method is limited to networks with scalar output. Indeed, uncovering the mathematical principles behind the decent learning performance of FA and DFA on multi-class tasks remains an open challenge.
Is this really useful? In terms of scientific significance, this work provided theoretical contributions toward understanding the capabilities and limits of feedback alignment algorithms. From a practical point of view, our mDFA algorithm has an advantage over backpropagation concerning training latency, as all weight updates can be computed in parallel, i.e., see Figure 1. Furthermore, we have shown that mDFA is superior to other feedback alignment algorithms in binary classification tasks. Consequently, mDFA provides an effective solution for binary classification problems with training latency constraints. Dynamic branch prediction in microprocessor pipelines poses such problem instance, where program specific binary branch outcomes, i.e., branch taken/not taken, need to be learned in real-time. Because of this real-time constraint, existing branch predictors often employ only shallow perceptron modules (Jiménez & Lin, 2002; Egan et al., 2003). mDFA could enable deeper branch predictor networks to be learned in real-time.

heading: ACKNOWLEDGMENTS
text: This research was supported in part by the Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).

heading: A APPENDIX
text: A.1 MONO-NETS ARE UNIVERSAL APPROXIMATORS
We denote σ(x) :=
1
1 + exp(−x) the sigmoid function,
tanh(x) := ex − e−x
ex + e−x
the hyperbolic tangent and
1[expr] := { 1 if expr is true 0 if expr is false
the indicator function.
From the definitions above we can derive the equalities
σ(x) = 1
2
( 1 + tanh( x 2 ) )
(16)
tanh(x) = − tanh(−x) (17) , which we will need for our proof. Lemma 1 (Universal Approximation Theorem). For any given f ∈ C(In) and ε > 0, there exist a function g : In → R of the form
g(x) := N∑ i=1 viσ(w T i x+ bi) (18)
with v ∈ RN , wi ∈ Rn, b ∈ RN and N <∞ such that
‖g(x)− f(x)‖∞ < ε.
In essence, the set of functions g(x) of the form given in (18) is dense in C(In).
Proof. See Hornik et al. (1989)
Theorem 3 (mono-nets are Universal Approximators). For any given f ∈ C(In) and ε > 0, there exist a function m : In → R of the form
m(x) := M∑ i=1 vi tanh(w T i x+ bi) + c (19)
with v ∈ R+M , wi ∈ Rn, b̄ ∈ RM , c ∈ R and M <∞ such that
‖m(x)− f(x)‖∞ < ε.
In essence, the set of functions m(x) of the form given in (19) is dense in C(In).
Proof. By Lemma 1 we know that there exist a g(x) with ‖g(x)− f(x)‖∞ < ε that has the form
g(x) = N∑ i=1 viσ(w T i x+ bi)
We will show that we can reformulate g(x) to the form in equation (19). Our basic idea is to propagate all negative weight entries into to the first layer where negative weight values are allowed.
g(x) = N∑ i=1 viσ(w T i x+ bi)
= N∑ i=1 vi 1 2 ( 1 + tanh(wTi x+ bi) ) =
N∑ i=1 vi 1 2 tanh ( n∑ j=1 wi,jxj + bi ) + 1 2 N∑ i=1 vi
= N∑ i=1 1[vi ≥ 0]vi 1 2 tanh ( n∑ j=1 wi,jxj + bi )
+ N∑ i=1 1[vi < 0]vi 1 2 tanh ( n∑ j=1 wi,jxj + bi )
+ 1
2 N∑ i=1 vi
= N∑ i=1 1[vi ≥ 0]vi 1 2 tanh ( n∑ j=1 wi,jxj + bi )
+ N∑ i=1 −1[vi < 0]vi 1 2 tanh ( − n∑ j=1 wi,jxj − bi )
+ 1
2 N∑ i=1 vi
= N∑ i=1 v̄i tanh ( wi Tx+ bi ) +
N∑ i=1 v̄′i tanh ( w̄i Tx+ b̄i ) + c
with
v̄i = 1[vi ≥ 0]vi 1
2 ≥ 0
v̄′i = −1[vi < 0]vi 1
2 ≥ 0
w̄i = −wiT
b̄i = −bi
c = 1
2 N∑ i=1 vi
Therefore, we showed that there exist a m(x) with a form as in equation (19) that satisfy
‖m(x)− f(x)‖∞ < ε.
This proof showed us how to translate any neural network with sigmoid activation function and one hidden layer of size N into a mono-net with 2N hidden units.
A.2 FOR 1-DIMENSIONAL OUTPUTS MDFA COMPUTES THE SIGN OF THE GRADIENT
Lemma 2 (The gradient of a monotone layer is non-negative). Let m : Rn0 → R with m(x) := hL ◦ hL−1 ◦ · · · ◦ h2 ◦ h1 ◦ h0(x) be a mono-net according to Definition 1. Then( dhl
dhl−1
) i,j ≥ 0, (20)
for any l, i, j with 2 ≤ l ≤ L and 1 ≤ i ≤ nl and 1 ≤ j ≤ nl−1
Proof. We have to distinguish two cases: Case 1: l = L, i.e. there is no activation function. We have ( dhl
dhl−1
) i,j = ( Wl ) i,j ≥ 0, (21)
according to the definition in Equation (10). Case 2: l < L, i.e. there is an activation function. We have ( dhl
dhl−1
) i,j = ( Wldiag(f ′(Wlhl−1 + bl)) ) i,j
(22)
= nl∑ k=1 ( Wl ) i,k ( diag(f ′(Wlhl−1 + bl)) ) k,j , (23)
where f ′ is the derivative of the activation function. Because f is a monotonic function, its derivative is non-negative everywhere. As a result we have a sum of a product of non-negative values. Ergo( dhl
dhl−1
) i,j ≥ 0 (24)
Lemma 3 (The gradient of a composition of monotone layers is non-negative). Let m : Rn0 → R with m(x) := hL ◦ hL−1 ◦ · · · ◦ h2 ◦ h1 ◦ h0(x) be a mono-net according to Definition 1. Then( dhl
dhk
) i,j ≥ 0, (25)
for any l, k, i, j with 2 ≤ l ≤ L and 1 ≤ k < l and 1 ≤ i ≤ nl and 1 ≤ j ≤ nk
Proof. By applying the chain rule we get( dhl dhk ) i,j = ( l∏ m=k+1 dhm dhm−1 ) i,j
(26)
According to Lemma 2 we have a product of non-negative values. Because a product of non-negative values is non-negative itself, we have ( dhl
dhk
) i,j ≥ 0 (27)
Theorem 4 (For 1-dimensional outputs mDFA computes the sign of the gradient). Let L(y, hL) be a loss function, m(x) := hL ◦ hL−1 ◦ · · · ◦ h2 ◦ h1 ◦ h0(x) be a mono-net according to Definition 1 with parameters Θ := {Wl, bl ∣∣l = 1, . . . L}. We denote δθ the update value computed by mDFA and ∇θ as the gradient ∂L∂θ for any θ ∈ {Wl, bl} with 1 ≤ l ≤ L. If nL = 1, it follows that(
δθ ) i,j · ( ∇θ ) i,j ≥ 0, (28)
for each coordinate (i, j) of θ.
Proof. We distinguish two cases: Case 1: l = L, i.e. θ is a parameter of the last layer. From the definition of mDFA we have
δθ := dL dhL dhL dθ . (29)
For the gradient by applying the chain rule we get
∇θ = dL dθ = dL
dhL
dhL dθ
(30)
Thus, in the last layer the mDFA update equals the gradient. Case 2: l < L, i.e θ is a parameter of a hidden layer. From the definition of mDFA we have(
δθ ) i,j := ( dL dhL B dhl dθ ) i,j
(31)
with B ∈ R+nL×nl . Next, we expand the multiplication,( δθ ) i,j = nL∑ k=1 ( dL dhL )kBk,i d(hl)i dθi,j
(32)
= d(hl)i dθi,j nL∑ k=1 ( dL dhL )kBk,i. (33)
We assumed that the output dimension is 1, i.e. nL = 1. Therefore,( δθ ) i,j = d(hl)i dθi,j ( dL dhL )1B1,i. (34)
For the gradient by applying the chain rule we get
∇θ = dL dθ = dL
dhL
dhL dθ
(35)
= dL dhL dhL dhl dhl dθ
(36)
Like above, we expand the multiplication,( ∇θ ) i,j = nL∑ k=1 ( dL dhL )k( dhL dhl )k,i d(hl)i dθi,j
(37)
= d(hl)i dθi,j nL∑ k=1 ( dL dhL )k( dhL dhl )k,i. (38)
We assumed that the output dimension is 1, i.e. nL = 1. Therefore,( ∇θ ) i,j = d(hl)i dθi,j ( dL dhL )1( dhL dhl )1,i. (39)
For Equation (28) we get by applying Lemma 3,( δθ ) i,j · ( ∇θ ) i,j = (d(hl)i dθi,j ( dL dhL )1B1,i ) · (d(hl)i dθi,j ( dL dhL )1( dhL dhl )1,i ) (40)
= (d(hl)i dθi,j ( dL dhL )1 )2 ︸ ︷︷ ︸
≥0
B1,i︸︷︷︸ ≥0 ( dhL dhl )1,i︸ ︷︷ ︸ ≥0
(41)
≥ 0. (42)
A.3 FOR k ≥ 2-DIMENSIONAL OUTPUTS MDFA UPDATES MAY NOT ALIGN WITH THE GRADIENT
Theorem 5 (For k ≥ 2-dimensional outputs mDFA updates may not align with the gradient). Let L(y, hL) be a loss function, m(x) := hL ◦ hL−1 ◦ · · · ◦ h2 ◦ h1 ◦ h0(x) be a mono-net according to Definition 1 with parameters Θ := {Wl, bl ∣∣l = 1, . . . L}. We denote δθ the update value computed by mDFA and ∇θ as the gradient ∂L∂θ for any θ ∈ {Wl, bl} with 1 ≤ l < L. If nL ≥ 2, there exists the possibility that (
δθ ) i,j · ( ∇θ ) i,j < 0, (43)
for at least one coordinate (i, j) of θ.
Proof. We construct a minimal counterexample consisting of a network with two outputs and one hidden layer of two neurons.
Let
W2 = ( 0 1 1 0 ) (44)
B2 = ( 1 0 0 1 ) (45)
∂L ∂hL = ( 1 0 0 −1 ) (46)
∂h1 ∂θ = ( 1 0 0 1 ) (47)
(48) Then we have
∇θ = dL dhL WT2 dhl dθ
(49)
= ( 1 0 0 −1 )( 0 1 1 0 )( 0 1 1 0 ) (50)
= ( −1 0 0 1 ) (51)
and
δθ = dL dhL B2 dhl dθ
(52)
= ( 1 0 0 −1 )( 1 0 0 1 )( 0 1 1 0 ) (53)
= ( 1 0 0 −1 ) (54)
(55) , which are orthogonal.

heading: B EXPERIMENT SETUP
text: B.1 NETWORK ARCHITECTURES
Dataset Fully-connected Convolutional CIFAR-100 1024,1024 (96,5,2),(96,3,2),(96,3,1) ImageNet 1024,1024,1024,1024 (96,3,2),(96,5,1),(128,3,2),
(192,3,1),(192,3,2),(384,3,1)
Network architectures, layers are separated by commas. Fully-connected column specifies the number of neurons of each layer. Convolutional column specifies the number of filters, kernel size,
and stride for each layer.
B.2 n-CLASS IMAGENET
B.3 DISCUSSION ON HYPERPARAMETERS
We observed that all FA algorithms yield a more stable convergence with ”vanilla” stochastic gradient descent, i.e., no post-processing of the FA updates, than with Adam (Kingma & Ba, 2014) or Rmsprop (Tieleman & Hinton, 2012). This may be non-surprising as these acceleration methods have been developed for gradient-based optimization, whereas FA updates roughly align with the gradients at best.
Furthermore, we observed that FA algorithms achieve a descent validation accuracy after the first few training epochs. However, in contrast to BP, these methods may require over a hundred training epochs to converge fully. This ”fast-start-slow-convergence” aligns with the observations made by Lillicrap et al. (2016).
We found that FA, DFA, and mDFA perform best when all forward weights are initialized to zero. Notable exceptions are networks with ReLU activation function which express poor performance with the all-zeros initialization scheme. This poor performance with all-zeros initialization partially explains the poor observed performance of FA and DFA for ReLU networks.
In contrast to Nøkland (2016), we observed that backward weights initialized by a normal distribution perform slightly better than the scaled uniform proposed by Nøkland (2016).
We confirmed the observation made by Bartunov et al. (2018), that feedback alignment algorithms are in general relatively sensitive to hyperparameter choice.

Review summaries:
This paper presents an approach towards extending the capabilities of feedback alignment algorithms, that in essence replace the error backpropagation weights with random matrices.  The authors propose a particular type of network where all weights are constraint to positive values except the first layers, a monotonically increasing activation function, and where a single output neuron exists (i.e., for binary classification - empirical evidence for more output neurons is presented but not theoretically supported).  This is to enforce that the backpropagation of the (scalar) error signal to affect the magnitude of the error rather than the sign, while preserving universal approximation.  The authors also provide provable learning capabilities, and several experiments that show good performance, while also pointing out limitations in case of using multiple output neurons.

This paper examines the question of learning in neural networks with random, fixed feedback weights, a technique known as “feedback alignment”. Feedback alignment was originally discovered by Lillicrap et al. (2016; Nature Communications, 7, 13276) when they were exploring potential means of solving the “weight transport problem” for neural networks. Essentially, the weight transport problem refers to the fact that the backpropagation-of-error algorithm requires feedback pathways for communicating errors that have synaptic weights that are symmetric to the feedforward pathway, which is biologically questionable. Feedback alignment is one approach to solving the weight transport problem, which as stated above, relies on the use of random, fixed weights for communicating the error backwards. It has been shown that in some cases, feedback alignment converges to weight updates that are reasonably well-aligned to the true gradient. Though initially considered a good potential solution for biologically realistic learning, feedback alignment both has not scaled up to difficult datasets and has no theoretical guarantees that it converges to the true gradient. This paper addresses both these issues.