Convergence and Alignment of Gradient Descent with Random Backpropagation Weights
Year: 2021

Abstract:
Stochastic gradient descent with backpropagation is the workhorse of artificial neural networks. It has long been recognized that backpropagation fails to be a biologically plausible algorithm. Fundamentally, it is a non-local procedure— updating one neuron’s synaptic weights requires knowledge of synaptic weights or receptive fields of downstream neurons. This limits the use of artificial neural networks as a tool for understanding the biological principles of information processing in the brain. Lillicrap et al. (2016) propose a more biologically plausible “feedback alignment” algorithm that uses random and fixed backpropagation weights, and show promising simulations. In this paper we study the mathematical properties of the feedback alignment procedure by analyzing convergence and alignment for two-layer networks under squared error loss. In the overparameterized setting, we prove that the error converges to zero exponentially fast, and also that regularization is necessary in order for the parameters to become aligned with the random backpropagation weights. Simulations are given that are consistent with this analysis and suggest further generalizations. These results contribute to our understanding of how biologically plausible algorithms might carry out weight learning in a manner different from Hebbian learning, with performance that is comparable with the full non-local backpropagation algorithm.

text: Stochastic gradient descent with backpropagation is the workhorse of artificial neural networks. It has long been recognized that backpropagation fails to be a biologically plausible algorithm. Fundamentally, it is a non-local procedure— updating one neuron’s synaptic weights requires knowledge of synaptic weights or receptive fields of downstream neurons. This limits the use of artificial neural networks as a tool for understanding the biological principles of information processing in the brain. Lillicrap et al. (2016) propose a more biologically plausible “feedback alignment” algorithm that uses random and fixed backpropagation weights, and show promising simulations. In this paper we study the mathematical properties of the feedback alignment procedure by analyzing convergence and alignment for two-layer networks under squared error loss. In the overparameterized setting, we prove that the error converges to zero exponentially fast, and also that regularization is necessary in order for the parameters to become aligned with the random backpropagation weights. Simulations are given that are consistent with this analysis and suggest further generalizations. These results contribute to our understanding of how biologically plausible algorithms might carry out weight learning in a manner different from Hebbian learning, with performance that is comparable with the full non-local backpropagation algorithm.

heading: 1 Introduction
text: The roots of artificial neural networks draw inspiration from networks of biological neurons (Rumelhart et al., 1986a; Elman et al., 1996; Medler, 1998). Grounded in simple abstractions of membrane potentials and firing, neural networks are increasingly being employed as a computational tool for better understanding the biological principles of information processing in the brain; examples include Yildirim et al. (2019) and Yamins & DiCarlo (2016). Even when full biological fidelity is not required, it can be useful to better align the computational abstraction with neuroscience principles.
Stochastic gradient descent has been a workhorse of artificial neural networks. Conveniently, calculation of gradients can be carried out using the backpropagation algorithm, where reverse mode automatic differentiation provides a powerful way of computing the derivatives for general architectures (Rumelhart et al., 1986b). Yet it has long been recognized that backpropagation fails to be a biologically plausible algorithm. Fundamentally, it is a non-local procedure—updating the weight between a presynaptic and postsynaptic neuron requires knowledge of the weights between the postsynaptic neuron and other neurons. No known biological mechanism exists for propagating
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
information in this manner. This limits the use of artificial neural networks as a tool for understanding learning in the brain.
A wide range of approaches have been explored as a potential basis for learning and synaptic plasticity. Hebbian learning is the most fundamental procedure for adjusting weights, where repeated stimulation by a presynaptic neuron that results in the subsequent firing of the postsynapic neuron will result in an increased strength in the connection between the two cells (Hebb, 1961; Paulsen & Sejnowski, 2000). Several variants of Hebbian learning, some making connections to principal components analysis, have been proposed (Oja, 1982; Sejnowski & Tesauro, 1989; Sejnowski, 1999). In this paper, our focus is on a formulation of Lillicrap et al. (2016) based on random backpropagation weights that are fixed during the learning process, called the “feedback alignment” (FA) algorithm. Lillicrap et al. (2016) show that the model can still learn from data, and observe the interesting phenomenon that the error signals propagated with the forward weights align with those propagated with fixed random backward weights during training. Direct feedback alignment (DFA) (Nøkland, 2016) extends FA by adding skip connections to send the error signals directly to each hidden layer, allowing parallelization of weight updates. Empirical studies given by Launay et al. (2020) show that DFA can be successfully applied to train a number of modern deep learning models, including transformers. Based on DFA, Frenkel et al. (2021) proposes direct the random target projection (DRTP) algorithm that trains the network weights with a random projection of the target vector instead of the error, and shows alignment for linear networks. Related proposals, including methods based on the use of differences of neuron activities, have been made in a series of recent papers (Akrout et al., 2019; Bellec et al., 2019; Lillicrap et al., 2020). A comparison of some of these methods is made by Bartunov et al. (2018).
The use of random feedback weights, which are not directly tied to the forward weights, removes issues of non-locality. However, it is not clear under what conditions optimization of error and learning can be successful. While Lillicrap et al. (2016) give suggestive simulations and some analysis for the linear case, it has been an open problem to explain the behavior of this algorithm for training the weights of a neural network. In this paper, we study the mathematical properties of the feedback alignment procedure by analyzing convergence and alignment for two-layer networks under squared error loss. In the overparameterized setting, we prove that the error converges to zero exponentially fast. We also show, unexpectedly, that the parameters become aligned with the random backpropagation weights only when regularization is used. Simulations are given that are consistent with this analysis and suggest further generalizations. The following section gives further background and an overview of our results.

heading: 2 Problem Statement and Overview of Results
text: In this section we provide a formulation of the backpropagation algorithm to establish notation and the context for our analysis. We then formulate the feedback aligment algorithm that uses random backpropation weights. A high-level overview of our results is then presented, together with some of the intuition and proof techniques behind these results; we also contrast with what was known previously.
We mainly consider two-layer neural networks in the regression setting, specified by a family of functions f : Rd → R with input dimension d, sample size n, and p neurons in the hidden layer. For an input x ∈ Rd, the network outputs
f(x) = 1√ p p∑ r=1 βrψ(wᵀrx) = 1 √ p β ᵀ ψ(Wx), (2.1)
where W = (w1, ..., wp)ᵀ ∈ Rp×d and β = (β1, ..., βp)ᵀ ∈ Rp represent the feed-forward weights in the first and second layers, and ψ denotes an element-wise activation function. The scaling by √ p is simply for convenience in the analysis.
Given n input-response pairs {(xi, yi)}ni=1, the training objective is to minimize the squared error
L(W,β) = 12 n∑ i=1 ( yi − f(xi) )2 . (2.2)
Standard gradient descent attempts to minimize (2.2) by updating the feed-forward weights following gradient directions according to
βr(t+ 1) = βr(t)− η ∂L
∂βr (W (t), β(t))
wr(t+ 1) = wr(t)− η ∂L
∂wr (W (t), β(t)),
for each r ∈ [p], where η > 0 denotes the step size. We initialize β(0) and wr(0) as standard Gaussian vectors. We introduce the notation f(t), e(t) ∈ Rn, with fi(t) = f(xi) denoting the network output on input xi when the weights are W (t) and β(t), and ei(t) = yi − fi(t) denoting the corresponding prediction error or residual. With this notation, the gradients are expressed as
∂L ∂βr = 1√ p n∑ i=1 eiψ(wᵀrxi), ∂L ∂wr = 1√ p n∑ i=1 eiβrψ ′(wᵀrxi)xi.
Here it is seen that the the gradient of the first-layer weights ∂L∂wr involves not only the local input xi and the change in the response of the r-th neuron, but also the backpropagated error signal eiβr. The appearance of βr is, of course, due to the chain rule; but in effect it requires that the forward weights between layers are identical to the backward weights under error propagation. There is no evidence of biological mechanisms that would enable such “synaptic symmetry.”
In the feedback alignment procedure of (Lillicrap et al., 2016), when updating the weightswr, the error signal is weighted, and propagated backward, not by the second layer feedforward weights β, but rather by a random set of weights b ∈ Rp that are fixed during the course of training. Equivalently, the gradients for the first layer are replaced by the terms
∂̃L ∂wr = 1√ p n∑ i=1 eibrψ ′(wᵀrxi)xi. (2.3)
Note, however, that this update rule does not correspond to the gradient with respect to a modified loss function. The use of a random weight br when updating the first layer weights wr does not violate locality, and could conceivably be implemented by biological mechanisms; we refer to Lillicrap et al. (2016); Bartunov et al. (2018); Lillicrap et al. (2020) for further discussion. A schematic of the relationship between the two algorithms is shown in Figure 1.
We can now summarize the main results and contributions of this paper. Our first result shows that the error converges to zero when using random backpropagation weights.
• Under Gaussian initialization of the parameters, if the model is sufficiently overparameterized with p n, then the error converges to zero linearly. Moreover, the parameters satisfy ‖wr(t)− wr(0)‖ = Õ ( n√ p ) and |βr(t)− βr(0)| = Õ ( n√ p ) .
The precise assumptions and statement of this result are given in Theorem 3.2. The proof shows in the over-parameterized regime that the weights only change by a small amount. While related to
results for standard gradient descent, new methods are required because the “effective kernel” is not positive semi-definite.
We next turn to the issue of alignment of the second layer parameters β with the random backpropagation weights b. Such alignment was first observed in the original simulations of Lillicrap et al. (2016). With h ∈ Rp denoting the hidden layer of the two-layer network, the term δBP(h) := ∂L∂h = 1√ pβ ∑n i=1 ei represents how the error signals ei are sent backward to update the feed-forward weights. With the use of random backpropagation weights, the error is instead propagated backward as δFA(h) = 1√pb ∑n i=1 ei.
Lillicrap et al. (2016) notice a decreasing angle between δBP(h) and δFA(h) during training, which is a sufficient condition to ensure that the algorithm converges. In the case of k-way classification, the last layer has k nodes, β and b are p × k matrices, and each error term ei is a k-vector. In the regression setting, k = 1 so the angle between δBP(h) and δFA(h) is the same as the angle between β and b. Intuitively, the possibility for alignment is seen in the fact that while the updates for W use the error weighted by the random weights b, the updates for β indirectly involveW , allowing for the possibility that dependence on b will be introduced into β.
Our first result shows that, in fact, alignment will not occur in the over-parameterized setting. (So, while the error may still converge, “feedback alignment” may be a bit of a misnomer for the algorithm.)
• The cosine of the angle between the p-dimensional vectors δFA and δBP satisfies cos∠(δFA, δBP(t)) = cos∠(b, β(t)) = O ( n√ p ) .
However, we show that regularizing the parameters will cause δBP to align with δFA and therefore the parameters β to align with b. Since β(0) and b are high dimensional Gaussian vectors, they are nearly orthogonal with high probability. The effect of regularization can be seen as shrinking the component of β(0) in the parameters over time. Our next result establishes this precisely in the linear case.
• Supposing that ψ(u) = u, then introducing a ridge penalty λ(t)‖β‖2 where λ(t) = λ for t ≤ T and λ(t) = 0 for t > T on β causes the parameters to align, with cos∠(b, β(t)) ≥ c > 0 for sufficiently large t.
The technical conditions are given in Theorem 4.6. Our simulations are consistent with this result, and also show alignment with a constant regularization λ(t) ≡ λ, for both linear and nonlinear activation functions. Finally, we complement this result by showing that convergence is preserved with regularization, for general activation functions. This is presented in Theorem 4.2.

heading: 3 Convergence with Random Backpropagation Weights
text: Due to the replacement of backward weights with the random backpropagation weights, there is no guarantee a priori that the algorithm will reduce the squared error loss L. Lillicrap et al. (2020) study the convergence on two-layer linear networks in a continuous time setting. Through the analysis of a system of differential equations on the network parameters, convergence to the true linear target function is shown, in the population setting of arbitrarily large training data. Among recent studies of over-parametrized networks under backpropagation, the neural tangent kernel (NTK) is heavily utilized to describe the evolution of the network during training (Jacot et al., 2018; Chen & Xu, 2020). For any neural network f(x, θ) with parameter θ, the NTK is defined as
Kf (x, y) = 〈∂f(x, θ)
∂θ , ∂f(y, θ) ∂θ
〉 .
Given a dataset {(xi, yi)}ni=1, we can also consider its corresponding Gram matrix K = (Kf (xi, xj))n×n. Jacot et al. (2018) show that in the infinite width limit, Kf converges to a constant at initialization and does not drift away from initialization throughout training. In the overparameterized setting, if the Gram matrix K is positive definite, then K will remain close to its initialization during training, resulting in linear convergence of the squared error loss (Du et al., 2018, 2019; Gao & Lafferty, 2020). For the two-layer network f(x, θ) defined in (2.1) with θ = (β,W ),
the kernel Kf can be written in two parts, Gf and Hf , which correspond to β and W respectively:
Kf (x, y) = Gf (x, y) +Hf (x, y) := 〈∂f(x, θ)
∂β , ∂f(y, θ) ∂β
〉 + p∑ r=1 〈∂f(x, θ) ∂wr , ∂f(y, θ) ∂wr 〉 .
Under the feedback alignment scheme with random backward weights b, Gf remains the same as
for standard backpropagation, while one of the gradient terms ∂f∂wr in Hf changes to ∂̃f(x,θ) ∂wr = 1√ pbrψ ′(wᵀrx)x, with Hf replaced by Hf = ∑p r=1 〈 ∂̃f(x,θ) ∂wr , ∂f(y,θ)∂wr 〉 . As a result, Hf is no longer positive semi-definite and close to 0 at initialization if the network is over-parameterized. However, if G = (Gf (xi, xj))n×n is positive definite and H = (Hf (xi, xj))n×n remains small during training, we are still able to show that the loss L will converge to zero exponentially fast.
Assumption 3.1. Define the matrix G ∈ Rn×n with entries Gi,j = Ew∼N(0,Ip)ψ(w ᵀxi)ψ(wᵀxj). Then we assume that the minimum eigenvalue satisfies λmin(G) ≥ γ, where γ is a positive constant.
Theorem 3.2. Let W (0), β(0) and b have i.i.d. standard Gaussian entries. Assume (1) Assumption 3.1 holds, (2) ψ is smooth, ψ, ψ′ and ψ′′ are bounded and (3) |yi| and ‖xi‖ are bounded for all i ∈ [n]. Then there exists positive constants c1, c2, C1 and C2, such that for any δ ∈ (0, 1), if p ≥ max ( C1 n2 δγ2 , C2 n4 log p γ4 ) , then with probability at least 1− δ we have that
‖e(t+ 1)‖ ≤ (1− ηγ4 )‖e(t)‖ (3.1)
and
‖wr(t)− wr(0)‖ ≤ c1 n √
log p γ √ p , |βr(t)− βr(0)| ≤ c2 n γ √ p
(3.2)
for all r ∈ [p] and t > 0.
We note that the matrix G in Assumption 3.1 is the expectation of G with respect to the random initialization, and is thus close to G due to concentration. To justify the assumption, we provide the following proposition, which states that Assumption 3.1 holds when the inputs xi are drawn independently from a Gaussian distribution. The proofs of Theorem 3.2 and Proposition 3.3 are deferred to ??.
Proposition 3.3. Suppose x1, ..., xn i.i.d.∼ N(0, Id/d) and the activation function ψ is sigmoid or tanh. If d = Ω(n), then Assumption 3.1 holds with high probability.

heading: 4 Alignment with Random Backpropagation Weights
text: The most prominent characteristic of the feedback alignment algorithm is the phenomenon that the error signals propagated with the forward weights align with those propagated with fixed random backward weights during training. Specifically, if we denote h ∈ Rp to be the hidden layer of the network, then we write δBP(h) := ∂L∂h to represent the error signals with respect to the hidden layer that are backpropagated with the feed-forward weights and δFA(h) as the error signals computed with fixed random backward weights. In particular, the error signals δBP(h) and δFA(h) for the two-layer network (2.1) are given by
δBP(h) = 1 √ p β n∑ i=1 ei and δFA(h) = 1 √ p b n∑ i=1 ei.
Lillicrap et al. (2016) notice a decreasing angle between δBP(h) and δFA(h) during training. We formalize this concept of alignment by the following definition.
Definition 4.1. We say a two-layer network aligns with the random weights b during training if there exists a constant c > 0 and time Tc such that cos∠(δFA, δBP(t)) = cos∠(b, β(t)) = 〈b,β(t)〉‖b‖‖β(t)‖ ≥ c for all t > Tc.

heading: 4.1 Regularized feedback alignment
text: Unfortunately, alignment between β(t) and b is not guaranteed for over-parameterized networks and the loss (2.2). In particular, we control the cosine value of the angle by inequalities (3.2) from Theorem 3.2, i.e.,∣∣∣ cos∠(b, β(t))∣∣∣ ≤ |〈 b‖b‖ , β(0)〉|+ ‖β(t)− β(0)‖‖β(0)‖ − ‖β(t)− β(0)‖ = O ( n √ p ) ,
which indicates that β(t) and b become orthogonal as the network becomes wider. Intuitively, this can be understood as resulting from the parameters staying near their initializations during training when p is large, where β(0) and b are almost orthogonal to each other. This motivates us to regularize the network parameters. We consider in this work the squared error loss with an `2 regularization term on β:
L(t,W, β) = 12 n∑ i=1 ( f(xi)− yi )2 + 12λ(t)‖β‖2, (4.1) where {λ(t)}∞t=0 is a sequence of regularization rates, which defines a series of loss functions for different training steps t. Thus, the update for wr remains the same and the update for β changes to
βr(t+ 1) = (1− λ(t))βr(t)− η √ p n∑ i=1 ei(t)ψ(wr(t)ᵀxi), for r ∈ [p].
Comparing to Algorithm 1, an extra contraction factor 1−λ(t) is added in the update of β(t), which doesn’t affect the locality of the algorithm but helps the alignment by shrinking the component of β(0) in β(t). Following Theorem 3.2, we provide an error bound for regularized feedback alignment in Theorem 4.2. Since regularization terms λ(t) make additional contributions to the error e(t) as well as to the kernel matrix G, an upper bound on ∑ t≥0 λ(t) is needed to ensure positivity of the minimal eigenvalue of G during training, in order for the error e(t) to be controlled. In particular, if there is no regularization, i.e., λ(t) = 0 for all t ≥ 0, then we recover exponential convergence for the error e(t) as in Theorem 3.2. The proof of Theorem 4.2 is also deferred to ??. Theorem 4.2. Assume all the conditions from Theorem 3.2. Assume ∑∞ t=0 λ(t) ≤ S̃λ = c̃S γ2 √ p
ηn2 √ log p for some constant c̃S . Then there exist positive constants C1 and C2, such that for any δ ∈ (0, 1), if p ≥ max ( C1 n2 δγ2 , C2 n4 log p γ4 ) , then with probability at least 1− δ, we have
‖e(t+ 1)‖ ≤ ( 1− ηγ4 − ηλ(t) ) ‖e(t)‖+ λ(t)‖y‖ (4.2)
for all t ≥ 0.

heading: 4.2 Alignment analysis for linear networks
text: In this section, we focus on the theoretical analysis of alignment for linear networks, which is equivalent to setting the activation function ψ to the identity map. The loss function can be written as
L(t,W, β) = 12 ∥∥ 1√ p XW ᵀ β − y ∥∥2 + λ(t)2 ‖β‖2, where X = (x1, . . . , xn)ᵀ; this is a form of over-parameterized ridge regression. Before presenting our results on alignment, we first provide a linear version of Theorem 4.2 that adopts slightly different conditions. Theorem 4.3. Assume (1) ‖y‖ = Θ( √ n), λmin(XXᵀ) > γ and λmax(XXᵀ) < M for some
constants M > γ > 0, and (2) ∑∞ t=0 λ(t) ≤ Sλ = cS γ √ γp η √ nM for some constant cS . Then for any δ ∈ (0, 1), if p = Ω(Md log(d/δ)γ ), the following inequality holds for all t ≥ 0 with probability at least 1− δ:
‖e(t+ 1)‖ ≤ ( 1− ηγ2 − ηλ(t) ) ‖e(t)‖+ λ(t)‖y‖. (4.3)
We remark that in the linear case, the kernel matrix G reduces to the form XW ᵀWXᵀ and its expectationG at initialization also reduces toXXᵀ. Thus, Assumption 3.1 holds ifXXᵀ is positive definite, which is equivalent to the xi’s being linearly independent. The result of Theorem 4.2 can not be directly applied to the linear case since we assume that ψ is bounded, which is true for sigmoid or tanh but not for the identity map. This results in a slightly different order for Sλ and an improved order for p.
Our results on alignment also rely on an isometric condition onX , which requires the minimum and the maximum eigenvalues of XXᵀ to be sufficiently close (cf. Definition 4.4). On the other hand, this condition is relatively mild and can be satisfied when X has random Gaussian entries with a gentle dimensional constraint, as demonstrated by Proposition 4.5. Finally, we show in Theorem 4.6 that under a simple regularization strategy where a constant regularization is adopted until a cutoff time T , regularized feedback alignment achieves alignment if X satisfies the isometric condition. Definition 4.4 ((γ, ε)-Isometry). Given positive constants γ and ε, we say X is (γ, ε)-isometric if λmin(XXᵀ) ≥ γ and λmax(XXᵀ) ≤ (1 + ε)γ. Proposition 4.5. Assume X ∈ Rn×d has independent entries drawn from N(0, 1/d). For any ε ∈ (0, 1/2) and δ ∈ (0, 1), if d = Ω( 1ε log n δ + n ε log 1 ε ), then X is (1 − ε, 4ε)-isometric with probability 1− δ. Theorem 4.6. Assume all conditions from Theorem 4.3 hold and X is (γ, ε)-isometric with a small constant ε. Let the regularization weights satisfy
λ(t) = { λ, t ≤ T, 0, t > T,
with λ = Lγ and T = bSλ/λc for some large constant L. Then for any δ ∈ (0, 1), if p = Ω(d log(d/δ)), with probability at least 1 − δ, regularized feedback alignment achieves alignment. Specifically, there exist a positive constant c = cδ and time Tc, such that cos∠(b, β(t)) ≥ c for all t > Tc.
We defer the proofs of Proposition 4.5, Theorem 4.3 and Theorem 4.6 to ??. In fact, we prove Theorem 4.6 by directly computing β(t) and the cosine of the angle. Although b doesn’t show up in the update of β, it can still propagate to β through W . Since the size of the component of b in β(t) depends on the inner-product 〈e(t), e(t′)〉 for all previous steps t′ ≤ t, the norm bound (4.3) from Theorem 4.3 is insufficient; thus, a more careful analysis of e(t) is required. We should point out that the constant c in the lower bound is independent of the sample size n, input dimension d, network width p and learning rate η. We also remark that the cutoff schedule of λ(t) is just chosen for simplicity. For other schedules such as inverse-squared decay or exponential decay, one could also obtain the same alignment result as long as the summation of λ(t) is less than Sλ.
Large sample scenario. In Theorems 4.3 and 4.6, we consider the case where the sample size n is less than the input dimension d, so that positive definiteness of XXᵀ can be established. However, both results still hold for n > d. In fact, the squared error loss L can be written as
n∑ i=1 ( f(xi)− y )2 = ∥∥ 1√ p XW ᵀ β − y ∥∥2 = ∥∥ 1√ p XW ᵀ β − ȳ ∥∥2 + ‖ȳ − y‖2, where ȳ denotes the projection of y onto the column space of X . Without loss of generality, we assume y = ȳ. As a result, y and the columns of X are all in the same d-dimensional subspace of Rn andXXᵀ is positive definite on this subspace, as long asX has full column rank. Consequently, we can either work on this subspace of Rn or project all the vectors onto Rd, and the isometric condition is revised to only consider the d nonzero eigenvalues of XXᵀ.

heading: 5 Simulations
text: Our experiments apply the feedback alignment algorithm to two-layer networks, using a range of networks with different widths and activations. The numerical results suggest that regularization is essential in achieving alignment, in both regression and classification tasks, for linear and nonlinear models. We implement the feedback alignment procedure in PyTorch as an extension of the autograd module for backpropagation, and the training is done on V100 GPUs from internal clusters.
Feedback alignment on synthetic data. We first train two-layer networks on synthetic data, where each network f shares the architecture shown in (2.1) and the data are generated by another network f0 that has the same architecture but with random Gaussian weights. We present the experiments for both linear and nonlinear networks, where the activation functions are chosen to be Rectified Linear Unit (ReLU) and hyperbolic tangent (Tanh) for nonlinear case. We set training sample sample size to n = 50 and the input dimension d = 150, but vary the hidden layer width p = 100 × 2k with k ∈ [7]. During training, we take step size η = 10−4 for linear networks and η = 10−3, 10−2 for ReLU and Tanh networks, respectively.
In Figs. 2a to 2c, we show how alignment depends on regularization and the degree of overparameterization as measured by the hidden layer width p. Alignment is measured by the cosine of the angle between the forward weights β and backward weights b. We train the networks until the loss function converges; this procedure is repeated 50 times for each p and λ. For all three types of networks, as p increases, alignment vanishes if there is no regularization, and grows with the level of regularization λ for the same network. We complement the alignment plots with the corresponding loss curves, where the training loss converges slower with larger regularization. These numerical results are consistent with our theoretical statements. Due to the regularization, the loss converges to a positive number that is of the same order as λ.
We remark that using dropout as a form of regularization can also help the alignment between forward and backward weights (Wager et al., 2013). However, our numerical results suggest that dropout regularization fails to keep the alignment away from zero for networks with large hidden layer width. No theoretical result is available that explains the underlying mechanism.
Feedback alignment on the MNIST dataset. The MNIST dataset is available under the Creative Commons Attribution-Share Alike 3.0 license (Deng, 2012). It consists of 60,000 training images and 10,000 test images of dimension 28 by 28. We reshape them into vectors of length d = 784 and
normalize them by their mean and standard deviation. The network structure is 784-1000-10 with ReLU activation at the hidden layer and with softmax normalization at output layer. During training, we choose the batch size to be 600 and the step size η = 10−2. The training procedure uses 300 epochs in total. We repeat the training 10 times for each choice of λ.
Fig. 3 shows the performance of feedback alignment with regularization λ = 0, 0.1, 0.3. Since the output of the network is not one-dimensional but 10-dimensional, the alignment is now measured by cos∠(δBP(h), δFA(h)), where δBP(h) is the error signal propagated to the hidden neurons h through forward weights β, and δFA(h) the error weighted by the random backward weights b. We observe that both alignment and convergence are improved by adding regularization to the training, and increasing the regularization level λ can further facilitate alignment, with a small gain in test accuracy.

heading: 6 Discussion
text: In this paper we have analyzed the feedback alignment algorithm of Lillicrap et al. (2016), showing convergence of the algorithm. The convergence is subtle, as the algorithm does not directly minimize the target loss function; rather, the error is transferred to the hidden neurons through random weights that do not change during the course of learning. The supplement to Lillicrap et al. (2016) presents interesting insights on the dynamics of the algorithm, such as how the feedback weights act as pseudoinverse of the forward weights. After giving an analysis of convergence in the linear case, the authors state that “a general proof must be radically different from those used to demonstrate convergence for backprop” (Supplementary note 16), observing that the algorithm does not minimize any loss function. Our proof of convergence in the general nonlinear case leverages techniques from the use of neural tangent kernel analysis in the over-parameterized setting, but requires more care because the kernel is not positive semi-definite at initialization. In particular, as a sum of two terms G and H , the matrix G is concentrated around its postive-definite mean, while H is not generally postive-semidefinite. However, we show that the entries of both matrices remain close to their initial values, due to over-parameterization, and analyze the error term in a Taylor expansion, which establishes convergence.
In analyzing alignment, we unexpectedly found that regularization is essential; without it, the alignment may not persist as the network becomes wider, as our simulations clearly show. Our analysis in the linear case proceeds by essentially showing that
β(t) = (1− ηλ)t−1β(0) + η√ p W (0)Xᵀα1(t− 1) + ( η √ p ) bα2(t− 1)
and controlling α1 while showing that α2 remains sufficiently large; the regularization kills off the first term. Although we see no obstacle, in principle, to carrying out this proof strategy in the nonlinear case, the calculations are more complex. While convergence requires analysis of the norm of the error, alignment requires understanding the direction of the error. But our simulations strongly suggest this result will go through.
In terms of future research, a technical direction is to extend our results to multilayer networks. It would be interesting to explore local methods to update the backward weights b, rather than fixing them, perhaps using a Hebbian update rule in combination with the forward weights W . More generally, it is important to study other biologically plausible learning rules that can be implemented in deep learning frameworks at scale and without loss of performance. The results presented here offer support for this as a fruitful line of research. Biologically plausible computational learning contributes to, and shares societal impact with, a large body of fundamental research that aims to understand the basis for cognition in animals, including humans.

heading: Acknowledgments
text: Research supported in part by NSF grant CCF-1839308.

Review summaries:
This paper builds upon the work of Lillicrap et al 2016 of attempting to find biologically plausible methods for implementing backpropagation. They thoroughly describe the issues with non-local information and why there are limits to using backprop-based learning to understand more about biological neural systems.  They describe the algorithm of feedback alignment using random back-propagated weights.  The authors go on to confirm some of the results of the Lillicrap paper, and find a surprising and novel result that regularization is required to produce convergence in over-parameterized settings. The experimental section of the paper shows some work on a more standard ML benchmark task of MNIST classification.  They show the results that regularization is required to get good performance on the task. 

This paper studies the convergence of Feedback Alignment, and proves that in the over-parameterized setting the error converges to zero exponentially fast. This is made possible by taking inspirations from recent work on the NTK, albeit with specific challenges as some quantities are not obviously positive semi-definite. Furthermore, it makes the somewhat surprising finding that regularization helps alignment, proving this in linear networks, and confirming this finding in simulations on Gaussian data and MNIST.

The paper provides a theoretical analysis of the feedback alignment algorithm (FA), a biologically plausible approximation to backpropagation. The authors consider a two-layered network, and derive training error bounds and error alignment for a variety of cases, using the neural tangent kernel method. The results show that FA-trained network can achieve zero training error for infinitely wide networks, and have some (strictly positive) degree of alignment between backprop and FA error vectors when proper regularization is used.

This paper gives a theoretical analysis of feedback alignment (FA), an algorithm to train neural networks by approximating the gradient of the loss function using random matrices. More precisely, the weights of the network that is being trained are replaced with random matrices in the back-propagation step.  The authors study two-layer neural networks in the over-parametrised regime, where the number of samples n is much larger than the number of neurons in the hidden layer, n, and provide two results:  1. A proof of linear convergence of the loss to 0. This proof follows the proofs    of Du et al. (2018), Gao & Lafferty (2020) for standard backprop. The added    difficulty of analysing DFA in this setting is that the effective kernel of    the network is not a priori positive semi-definite.  2. An analysis of the alignment between the second-layer weights of the network    and the feedback matrix used in the feedback alignment algorithm, which    highlights the important role of regularisation and finds that (the role of)     alignment is more complex than previously thought.