Convergence Analysis and Implicit Regularization of Feedback Alignment for Deep Linear Networks
Authors: Manuela Girotti
Ioannis Mitliagkas
Gauthier Gidel
Venue: ICLR 2022 Submitted (2022)
Keywords: feedback alignement
optimization
convergence guarantees
implicit regularization

Abstract: We theoretically analyze the Feedback Alignment (FA) algorithm, an efficient alternative to backpropagation for training neural networks. We provide convergence guarantees with rates for deep linear networks for both continuous and discrete dynamics. Additionally, we study incremental learning phenomena for shallow linear networks. Interestingly, certain specific initializations imply that negligible components are learned {before} the principal ones, thus potentially negatively affecting the effectiveness of such a learning algorithm; a phenomenon we classify as implicit anti-regularization. We also provide initialization schemes where the components of the problem are approximately learned by decreasing order of importance, thus providing a form of implicit regularization.

Under review as a conference paper at ICLR 2022
CONVERGENCE ANALYSIS AND IMPLICIT REGULARIZATION OF FEEDBACK ALIGNMENT FOR DEEP LINEAR NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We theoretically analyze the Feedback Alignment (FA) algorithm, efficient al- ternative to backpropagation for training neural networks. We provide convergence guarantees with rates for deep linear networks for both continuous and discrete dynamics. Additionally, we study incremental learning phenomena for shallow linear networks. Interestingly, certain specific initializations imply that negligible components are learned before the principal ones, thus potentially negatively af- fecting the effectiveness of such a learning algorithm; a phenomenon we classify as implicit anti-regularization. We also provide initialization schemes where the components of the problem are approximately learned by decreasing order of importance, thus providing form of implicit regularization.
INTRODUCTION
In order train a Machine Learning (ML) architecture in the context of supervised learning, is consolidated practice to resort to the Gradient Descent (GD) algorithm and its variants (e.g. stochastic GD) and to calculate the gradient of the loss function via backpropagation (Rumelhart et al., 1986). However, 1987): the update of each neuron during the learning phase relics on the downstream weights (which therefore "transported" along the backward pass). This implies that 1) the synaptic weights the same, up to transposition, for both the forward (inference) and backward (learning) pass and 2) each neuron has precise knowledge of all of its forward synapses. It is known that such model does not accurately reflect the behaviour of a human brain, thus it is biologically implausible (Crick, 1989). Feedback Alignment (FA), originally proposed by Lillicrap (Lillicrap al., 2016), has been an attempt to mitigate this discrepancy between the neuroscience side and the engineering side of AI and tackle the weight transport problem systematic way. The simple, yet powerful idea is to replace the transposed weight matrices in the backpropagation algorithm with arbitrary, fixed matrices: via this strategy, each neuron during training receives random projection of the error vector.
of its limitations is the so-called weight transport problem (Grossberg,
In order to illustrate the algorithm and for the purpose our study, us consider a fully-connected L-layer neural network (NN): given the input, x ho E Rdd, the predicted label ý E RR is computed as
a₂ Wihi-1 h oaz), i (1...,, := [L].
being a (potentially) nonlinear function applied entry-wise to the vector ag, and finally ý - f(a)) for some output nonlinear function f. We consider a regression task with loss function being the standard Mean Square Error (MSE). The backpropagation strategy for GD prescribes the following
updates for each layer the network: given a step size v) >> and the error vector e = -ar, = 3g
ac
ÿ where y is the true label, we have
oW, 1,
T-1 SW;
- and da (W (441)aat))oo Le [L-1] (GD)
where @ denotes the Hadamard product. The FA recipe prescribes the following:
Feedback Alignment:
(GD) use
da = (Mşdar-1) o o'a)), e 1].
(2)
where {Mr) are collection of arbitrarily chosen matrices, which do not evolve during training.

---

Under review as a conference paper at ICLR 2022
Related and previous work. Inspired by Lillicrap et al. (2016) and shortly after its publication, Nøkland (2016) proposed two new algorithms called Direct and Inverse FA. In particular, Direct FA reduces to the FA algorithm in the case of 2-layer NN or multi-layer linear NN; the difference between these two algorithms in the general multi-layer nonlinear NN resides in injecting the error vector directly into the update of each hidden layer of the network: da, (Mąe) @ o (ae), f E [1,-- 1]. Such a modification of the FA algorithm can be interpreted as a noisy version of layer-wise training (Gilmer al., 2017).
Since its first formulation, there has been an extensive numerical analysis on testing whether FA and Direct FA algorithms can be successfully applied to ML problems. in particular in the presence of complex datasets and deep architectures (Bartunov et al., 2018: Moskovitz et al., 2018: Launay et al., 2019). We mention the recent survey paper Launay et al. (2020) where the focus on Direct FA and it is shown that the algorithm performs well in modern deep architectures (Transformers and Graph NN, among others) applied to problems like neural view synthesis or natural language processing. Furthermore, more on the applied (biologically-ins) -inspirred))) side, there have been recent pushes in furthering the idea of FA: spike-train level direct feedback alignment (Lee et al., 2020), memory- -efnooreefffiientt direct feedback alignment (Chu et al., 2020) and direct random target projection (Frenkel et al., 2021) to mention a few examples.
On the other hand, rigorous theoretical results are scarce. Preliminary asymptotic results can be found in the original papers by Lillicrap et al. (2016) and Nøkland (2016). More recently, Refinetti al. (2020) presented the derivation of system of differential equations that governs the Direct FA dynamics for 2-layer non-linear NN in the regime where the input dimension goes to infinity. There no explicit formula for the solution of the system, but via a careful local analysis it possible to identify two separate phases of learning (alignment and memorization) and a "degeneracy breaking" effect: at the end of the FA training, the selected solution maximizes the overlap between the second weight matrix W2 and the FA matrix M. Such an "alignment" dynamics is also evident in our analysis (Section 2). Convergence guarantees for deep networks are still missing from the literature and one of the goals of this paper is indeed to provide rigorous proofs of convergence, together with convergence rates.
Our analysis is in similar vein as some recent works on implicit regularization in linear neural networks Saxe et al. (2018); Gidel et al. (2019); Arora et al. (2018). Even though our setting is very similar, analysis is different: because of the feedback alignment matrices, the autonomous differential equation obtained significantly differ and lead to different dynamics. Moreover our focus is slightly different from Saxe al. (2018), Gidel et al. (2019); Arora et al. (2018) which are fully dedicated to implicit regularization of GD while we also aim at proving the convergence of FA.
Our contributions. We aim to provide a theoretical understanding of how and when FA works. We focus two aspects: 1) proving convergence of the algorithm and 2) analyzing implicit regularization phenomena. We will extensively study the case of deep linear NNs. Despite being sometimes regarded as too simplistic, the study of linear networks is a crucial starting point for systematic analysis of the FA algorithm: it will allow us to rigorously analyze a tractable model and it will give us insights and intuition on the general nonlinear setting (Section 7).
Our main results are the following.
We prove convergence of the FA continuous dynamics, with rates, for L-layer NNs with I > 2 (Sections 2 and 3). Such results hold for any input dimension and number of neurons: the network is not necessarily overparametrized.
We prove that, for certain initialization schemes, the continuous FA dynamics sequen- tially learn the solutions of reduced-rank regression problem. but in backward fashion: smaller components first, dominant components later (Section 4). Additionally, we provide guidelines for an initialization scheme that avoids such phenomena.
Finally (Section 5), we analyze the corresponding discrete FA dynamics and we prove convergence to the true labels with linear convergence rates.
We assumed some conditions the data and on the model in order to render the exposition and the reading more clear. However, some of the "strong" assumptions that will appear in the paper can be easily relaxed (see Section 2).
2

---

Under review as a conference paper at ICLR 2022
2 WARM-UP: SHALLOW NETWORKS
In this section, we consider a 2-layer linear NN with vector output ğ W,W E R and input vector a: E Rd such that (æ. 3) DD for some distribution D. Define En.. := ax E Rdddd that we assume to be positive definite, and Ezy == Elyx' E Roxd, then the following result holds:
Proposition 1. For any distribution D, the FA dynamics that dictates the learning process is
W1 = M (Ezg W
W₂ (Ezy W2W1E WT.
where the dot refers to the time derivative.
Note that this result particularly holds for empirical distributions corresponding to finite datasets.
In this work, we will assume that the two matrices Eg.. Ery can be simultaneously decomposed as Σ. A V and Exy = U UAaVV. where the latter corresponds the singular value decomposition (SVD) of Ezy This assumption holds in many situations, as discussed in details by Gidel et al. (2019). Moreover, perturbation analysis similar as the one done Gidel al. (2019, Theorem 1) could be performed in the general case in order to handle the non-commutative case. Next, we introduce the change of variables Wi = RW, V and W2 UW2 for some arbitrary left-orthogonal matrix R, and we choose the FA matrix M to be decomposable in a similar fashion: M = RDU for some matrix D with positive diagonal entries D,, 0 and zero entries otherwise. In particular, this implies that M is full rank, therefore guaranteeing convergence to a global minimum of the dynamics. The equations for the FA flow will then become
W1 D (Any W2W1A
W2 = (Awy W2W111 W...
(4)
Moreover, by the change of variable Wi WiA 1/2 W == A W2. D' := DA 1/2 where
A 1/2 is the coordinate-win wise square root of Ages we get after some simple calculations that
W = D' (A Any 1/2 w.W?).
W
1/2 A A 1/2 w:W;) W
(5)
Therefore, by considering A/ A by A 1/2 may equivalently assume Ege
Ia
(isotropic features), without any loss of generality.
It is now crucial observe that if W E Rhxd W Roxh are diagonal matrices, then the dynamics decouples into is independent equations with h: = minfd, h, o}. In particular, let 0j = (Wi),, s and
02 (W))s; and assume that time each i = I,..., k we obtain the following scalar system:
the matrices Wi(0) and W2(0) are diagonal. Then, for
0 d' (X* 0581)
0 (X* 0,66) 0%
where A = (Azy)as and Dis- Note that for i > one could define diagonal coefficients for the matrices W/ or W3, but their derivative will be 0, thus non-trivial dynamics only occur for i [k:].
2.1 THE SCALAR DYNAMICS
We now our attention to analyzing nonlinear system of the form (6) for the scalar functions 8, 02 E C'(RR) (R) (we suppressed the indices).
Theorem 2. For any FA constant E Ry0, and V 0u E IR initial value with initialization scheme
(0) Oo and
02(0)
(7)
2d
CC 0 such that the product 0g (1, (1) of the solution of the system (6) converges exponentially
the signal X in a monotonic fashion: (0 (t)))())))))))(()))( - >l Ce - (ax) as t - +o0. Moreover the first layer gets "aligned" with the feedback matrix such that (t) - 2/2d.
Note that we used slight abuse of notation: depending on the matrix is multiplied to -12 corresponds the diagonal matrix either of size d x d or with the diagonal enefficients [A |/
la, 1 < rank (ank(Azx).
3

---

Under review as a conference paper at ICLR 2022
(a) FA trajectories in the phase space (0,, 0z) for d = 22 The dotted hy- perbola correspond to the solution set 0,02= X.
(b) FA (continuous lines) and GD (dotted lines). with initial conditions
(c) FA dynamies with i.dd ini-
tial conditions (0, (0), 0z(0)) ~
(7): 0o u(| 5, 5)) and d 2.
u(l (1)-5,5))x(([33
and d 2.
Figure I: Numerical simulations of the solution (z)()) (t) of the FA dynamics with true signal À = 3 (left and middle) and X 10 (right), with different initializations.
The proof can be found in Appendix A.2: along with the proof, it appears that the FA weights drive the learning of the forward weights for the first layers the point that their limit is "aligned" the value of the FA constants (in a nonlinear fashion). Similarly, this holds for the deep network case (Section and Appendix B.2). One can also observe that components with large FA constant d are learned faster (see (35)-(36) in Appendix A.2), boosting the alignment.
From Theorem 2 clear that the choice of the FA constant will force the optimization to select one particular pair of solutions (0, (t), (t)) among the infinitely many possible solutions (the equation 0,0,- = Å a 1-dimensional manifold on the R2 -l''pl.ne). However, all of these solutions represent global minima (those are the only stationary points of FA), and therefore via the FA dynamics, we can find the global minima of the loss function.
We can easily notice that vero-initialization does guarantee convergence for FA, unlike in the case of GD dynamics (Figure 1b). Furthermore, we want to highlight the ideological novelty of the proposed initialization scheme (7): unlike considering all weight matrices independent players the beginning of the optimization process and initializing them at random, we are imposing that once the weight matrix W1 of the first layers is initialized, the initial value of the weight matrix W2 of the second layer is deterministic, and it depends directly from the first layer.
More generally, it is easy (though lengthy) prove that the product of the solutions (0 (1), (2())) of the system (6) always converges to the signal A, regardless of the initialization scheme considered. Some intuitions can be built from the phase diagram in Fig la where one can see that the trajectories of the dynamics lie on parabolas with equation 2d0₂ = of + 2dK while the solution set is represented by the hyperbola 0, f2 = X. The difficulties in the analysis arise when the initialization correspond to parabola that intersect the solution set more than once. Moreover, the non-mon non-mononicyty of the quantity 00 (t) - >| can be seen on this diagram as the result of some trajectories getting close to the bottom left part of the hyperbola but eventually converging to the top right one.
Theorem 3. For any FA constant d E Rso and for any initial values 0₂ (0) and 02(0), the system (6) admits a unique solution (0, (t), (2)) such that (t), 02(t) are bounded for all times 2 0 and Oz (z(() (t) + X as +o0. The convergence rate is exponential for any pair of initial values (0), (0)) except for a set of (Lebesgue) measure zero in IR?.
For the proof, see Appendix A.3. The main consequence of Theorem that even by initializing all layers randomly and independently (as it is common practice), the FA dynamics still converges to the true signal. However, we want to stress that the initialization scheme (7) is more suitable for ML applications: for arbitrary initial conditions, the product of the solutions 0g (t)0, (t) may not be monotonic (compare with Theorem 2). Thus it may trigger inefficient early stopping practices (see Figure lc). Furthermore, for randomly and independently sampled pair of initial conditions, may observe a highly undesirable "reversed" incremental learning phenomenon (Section 4), which is avoided if (7) is put into place.
Relaxing some assumptions. Considering the the assumption that the weight matrices Wi, W share the left/right singular vectors with Exy is not strictly needed: with more work, the more general case can be analyzed via perturbation analysis, along the same lines in Gidel al. (2019) (Assumption 1). Furthermore, even though the initialization of the matrices Wi, W₂ are diagonal
4

---

Under review as a conference paper at ICLR 2022
Saxe al. (2018) argues that the diagonal solutions provide good approximations to the full solutions when (O).,, (2) are full matrices, initialized with small random weights.
DEEP NETWORKS
In this section we extend the results of Section 2 deep linear NNs: given distribution of input-output pairs (x, y) ~ D. the predicted output vector is now ÿ = W.... W2W, W, æ with weight matrices W E Rhexhe-1 (ho d, h o) and note Σ, E ax E Raxd and
Eay- Elyæ' E Roxd
Proposition 4. For any distribution D, the FA equations of motion are
Wi = Mr(E2y - WI=ly ) W(he-1
(he-11
ÉE [4],
(8)
for some FA weight matrices (Me)ee()) with Mr and with Mi:d We... W1.
Notice that the legitimate FA update would be W. M (1 Weey--in:i [1:L] Ems) W W... since we are requiring the FA matrices to be full rank, we can redefine the FA matrices M, M (E...-)) 1)- We now perform a similar change of variables as in Section 2: We R2 W. with Ro V. R2 U and (Rt) (Re) arbitrary left-orthogonal matrices. We additionally assume that the FA matrices Mt have the following prescribed form M, D2 (with D; matrix with zero entries except for entries on the diagonal, which are positive). Then, the system becomes
[1:C-1]: however
We = Di(Azy zy WII (16-1)
EE
Considering the change of variable W == WAA 1/2 WL == A D == D 1/2
Aay = 1/2 A and assuming as in $2 that (0) are diagonal, the system decouples:
0 = dx( 02 01)000001111100000.0011111 ... 0i
EE [L),
(10)
and for each entry i l,...,k, with l min hy.... ....... p.....,,h-uu hL-1,, o}, the analysis reduces studying system of scalar functions (Bi....,0) 81))
Theorem 5. For any set of FA constants {dehee[--1) de E B2 and for any Oo E E, there exists an initialization scheme of the form
(0) 0o.
0z(0) = C,0 e
(11)
where Ct E RR depends on [di...., d such that the system of differential equations (10) has unique solution (t), ( (t)), which converges exponentially the signal X 400 in monotone fashion.
As in the 2-layer case, the proposed initialization scheme is characterized by the fact that only the first layer initialized at random, while all the other layers depend deterministically along the same lines as Theorem 3, it is also possible to prove convergence to the true signal for any initialization set (0) (EEL)- However, some desirable properties of the dynamics (monotonicity, exponential convergence) may be lost. For the proofs and the explicit construction of the initialization scheme (11) see Appendix B.2.
it. Note that,
IMPLICIT REGULARIZATION PHENOMENA
In this section, we analyze the phenomenon of hierarchical learning (or implicit regularization) for FA, described in Gidel et al. (2019) and Gissin et al. (2019) in the case of GD: along the optimization path, features of the model are learned learned before the dynamics starts to learn the next feature. For FA, we may observe similar behavior as GD, however, in certain settings the dynamics seems to favor the learning of secondary component prior than the learning of principal components, i.c. signals X's with small magnitude are learned earlier than those of big magnitude. This phenomenon is potentially highly problematic since smaller singular values ' are normally tied to noisy measurements and do not represent
sequential way, so that one feature fully
5

---

Under review as a conference paper at ICLR 2022
give meaningful information the structure of the data. Privileging negligible features goes against the standard principles of reasoned data analysis (Principal Component Analysis, for example). We will see that the occurrence of this behavior depends on particular initializations of the algorithm and can be therefore successfully avoided.
Theorem 6 (Informal). Let X1 ... > X be the principal components of Agy- There exists initialization schemes such that the component x is incrementally learned at time T. Moreover, there exists two different initialization schemes such that
Anti- Satt-Regularzzaaion44....11 Ti >...>> Te and Regularization($4.)) Ti <... Ts (12)
To illustrate such phenomenon and rigorously describe it, consider the 2-layer case in the SVD- setting as in Section 2: v i =1:=.... -..... k, the system (6) can be equivalently rewritten as
......,,,
0 1 ((0)) + 2d - -2dx),
(1(0)) 0%.
(13)
and -2(1)= 23 01 + K3, with K* - (2 2 (01 (0))² E R and d, X >> 0 (for simplicity we assumed d' = d, A i). Depending the value of K* (i.e. the initial condition of the i-th system), the cubic polynomial on the right-hand-side of (13) may have between and 3 distinct real roots. The value of the discriminant A = 4d (8d( (K+)a 27))) will dictate which regime fall into.
We will be considering the case where A > 0 and the case K 0 (i.e. the initialization scheme (7)), which is a special instance of the case A < 0. The case A = 0 can be equally analyzed, but will not be considered in this paper, as has zero probability of occurring. 2 The sequential learning phenomenon becomes evident when we perform a double scaling limit of the time variable t + öt and the initial condition 83 + f6,, 6)). 5 - +oc, as will be clear below. Note that the rescaling is uniform across the components Proof of Theorem 7 and lengthier discussion can be found in Appendix C.
4.1 CASE A > O: BACKWARD LEARNING
If K < -2) intuition that by initializing 6j at a value that very close to r and applying the time scaling I -+ 8t, 8 >> (i.e. we are "ooaa-forwarding" the solution 0, (8t)), we can clearly identify the time threshold T after which the signal is fully learned. More formally,
O, the cubic polynomial in (13) has real, distinct root ri r < rg. The
Theorem 7. V 1, ......k. k. if (0) r + (6 0), then the solution (ôt) converges step function:
0f (51) + r uUTT + a anll (--T + +rllTST
as 5 - t00,
(14)
where (0E is the indicator function on the set A.
T
at E (r2.r))
(15)
(r3 r3) rt)
Furthermore, T is increasing function of Xi: for X > X2 ...>> X and fixed FA constant d, we have T > T >..> Thb
Similar conclusions hold when 0 (0) = rá -5 Therefore, as the value of X increases, the value 7 increases as well: negligible features of the data are learned sooner than the dominant ones.
On the other hand, Theorem shows that such a backward incremental learning does not happen with high probability: indeed, we are requiring all the parameters K' (which depends the initialization) to be sufficiently negative and the probability of sampling initial conditions that will yield anti- regularization depends on the value of the signals X (i.e., it is data-dependent): the bigger the value X1, the smaller the probability. Nevertheless, we will see in the next subsection how such a phenomenon can be safely bypassed and we discuss some properties that suggest that the initialization scheme (7) can guarantee the correct sequential learning of features as GD exhibits.
"The claim is correct if we sample the initial conditions 0, (0). (0) independently and generically: for example, from uniform distribution 2(([-R, R, R)) 24( R,, Rl), for some R e Ry0-

---

Under review as a conference paper at ICLR 2022
4.2 CASE K 0: EVIDENCE OF INCREMENTAL LEARNING
Imposing K = 0 for all i's means to recur to the initialization scheme (7): 0f (0) 0g 02(0)
2d (0)). In this case, Theorem already provides exponential convergence rates that depend on the
magnitude of the signal (t))()) (t) - - < Ce -d(x)) as & + too), suggesting that the bigger the magnitude of the signal X², the faster the convergence.
If 8 0, there exists a unique time Tj (vanishing time) such that 0f (T)))
and
8i (t) $ for t & Tj respectively, where
(r' (r'-00) 03)²
2 (rt)²
20 + rr r'v3
To 233) 3(r2)2 In (0)) + r' + (rt)²
arctan
(16)
We can interpret such vanishing time as the first milestone of the learning process. In the regime as 8 + A by....he k, we have
4T
1
TØ
+0
(17)
3(
(0))²
where 2dd", therefore for bigger A (i.e. dominant singular values) the vanishing time happens sooner: for A > > X and fixed FA constant d > 0, To < Ty <... To
5 DISCRETE DYNAMICS
5.1 FORWARD EULER DISCRETIZATION
In this section, we are interested in analyzing the discrete FA dynamics and its convergence properties. For the discrete time setting, we focus again on a 2-layer lincar NN. The standard forward Euler method yields the following discretized system:
((++1) = w/ + + -
-W," )")
(18)
(((+1) w + 17 Eiry wh w(") (wr())"
(19)
and performing again the SVD change of variables, the system becomes
w ((()) nD (Asy W w.'W(/)
(20)
W (1+1)) (( v (Any W (W!")T (0)
(21)
If we set the initial conditions ( ( as diagonal, the matrices remain diagonal for all times and the dynamic decouples. For each L,..., have
(oftt1)²= (01*)² + ndd X (x- (0()) (0(
(22)
(0(+t))* (o8))² +n (x- (o((() (0(0)
(0))))
(23)
The following result holds (the index is suppressed for simplicity).
Theorem 8. Consider the system (22)-(23). With zero initialization 0 = 000 = 0, v X, d 0 and
with constant step size small enough, the product 0 g()) converges to the true signal X with linear rates: 0 - < , for some C >0.
For the sake of clarity, we deferred the precise prescription for the magnitude of n and the linear rate q to Appendix D. where the full proof of the Theorem can be found.
7

---

Under review as a conference paper at ICLR 2022
5.2 MODIFIED FORWARD DISCRETIZATION
In addition to the standard discretization strategy, we are proposing here new discretization technique that is particularly instrumental for the FA setting, as it will allow a thorough inspection of its convergence guarantees and convergence rates for NNs of any depth. Inspired by the fact that the behaviour of the second layer strictly depend on the choices that we impose on the first layer in the continuous dynamics (Theorem 2 and initialization (7)), we slightly modify the update rule for second weight matrix W2 in the following way:
( = w + +nM Ezyy - -W w?!')
(24)
W ((+1)__ = w (h (m,(43))*
(25)
with W (++ = (w(+t)) + w The above discretization technique can be considered as a hybrid between the Euler forward method and the trapezoidal rule (Iserles, 1996), although we are still evaluating the error Σzy w (t()) at the present time t. The underlying idea is that we want to already use the information encoded in the new (t + 1)-iterate of W1 to update the second layer by averaging w( and (((++))
Performing again the SVD change of variables, and setting ( w/ as diagonal, we obtain a scalar system of the form (V i ..)
(0)
(0t) (oi)(()) (++1)) (01) (t) + ndd (x² (02) (2) (01) (9)
(26)
(0))(t+))= = (8)) (8) + 17 (X (0%) (1) (0t) (0) (09) (c+2)
(27)
A convergence result follows (suppressing the i-dependence).
Theorem 9. Consider the system (27). With zero initialization 0(00 = 6 = 0, V
the product 8 g(() linearly converges the true signal A: and with constant step size 17 3(24x)
10 00 - A 3x(1 3n (2d))
The discretization scheme easily generalizes the case of L layers for L 2 3 (we again suppress the i-index for readability):
(e++) 0((+1)= = 000)) + ndde (1:E-11 (2 ( .... .89). ".""..."))
e= L,
(28)
with d, = Also in this case, the dynamics closely mimic the continuous counterpart, reducing the system to single recurrence equation for {o("). }. By selecting a step size small enough, the sequence of products (0(") ...0!! g(9) } will converge to the signal À with exponential rate.
Theorem 10. Consider the system (28) with X, > 0 and zero initialization 010) 0, A where 7 2 and R is 1...., T.. If the constant step size satisfies nf < (d17(Sx0-))//1)) suitable positive constant depending on the FA constants
dr..1, then the product I 0 0000) .1.0)) > s Cx md17 (RA2-1)7) y,, for some
linearly converges to the true signal X: 10%) constant C₃ E R25 only dependent on
The proofs of Theorems 9 and 10 can be found in Appendix D.
6 EXPERIMENTS
In this last section, we discuss one ML application of our theoretical results. The set-up is borrowed from Gidel al. (2019) (Section 4.2), where linear autoencoder is considered.
For an autoencoder, the (true) output is equal to its input = x E Rd and we want to compare the reconstruction properties of w w)( (2 layer NN) and W (1) w w(()) (3 layer NN) computed via
8

---

Under review as a conference paper at ICLR 2022
5
FA (31)
Reconstruction error
4
FA (21)
4
Trace Norm
GD (31)
3
3
GD (21)
FA (31)
2
2
FA (21)
1
1
GD (31)
GD (21)
0
10a
10a
10
10a
10a
10a
Number of iterations
Number of iterations
Figure 2: Comparison of trace norms and reconstruction errors for linear autoencoders, For the FA experiments, plotting the average (with error bars) of 15 experiments.
FA versus GD. In this experiment, we have d o 20 and k: 5. We generate 1000 synthetic data } in the following way: each data point is given as z; = Az; + where A E Raxk a fixed matrix with entries sampled as A&r 2((0, 1)), zi ~ N' (0, A == diag {4, 1, 2 7))
and the noise E; ~ 10-3N(0, Ia). We initialize the weight matrices to a close-to-zero initial- ization w(()) ( _ anti-regularization pattern and to converge to the signal (Theorems 8, 9 and 10).
10 10011000000 "[[[, 1J): this will guarantees the FA dynamics to avoid the
We generate the FA matrices M (2-layers) and M1, M2 (3-layers) with entries M,, u([0, 1]).
Keeping the same initial conditions w and same fixed matrix A, we repeat the FA training 15 times, sampling a different set of FA matrices each time: in Figure 2, we report the average (with error
bars) of the trace norm |0(1|] || with ( w ((()) or (+) := W W w(() respectively, as well as thee average of the reconstruction errors O -AAA as a function of t the number
of iterations.
We can see that the FA learning dynamics is distinctly faster than GD, which is learning at much slower pace, as we initialized the dynamics close to one GD's local maxima. In particular, the 3-layer NN trained with GD hasn't yet started to learn at the end of the selected training period of the experiment. Notably, the FA training for the 3-layer NN hints at the presence of an implicit regularization behavior, similar to what has been observed and proved in Gidel al. (2019) for 2-layer NN. Additional technical details can be found Appendix E.
FINAL DISCUSSIONS AND INSIGHTS
In the present paper rigorously analyze biologically plausible optimization algorithm, describe its potential as well as its limitations in possible MI. applicatonns.. We provide convergence guarantees both the continuous and discrete-time settings; additionally, we thoroughly discuss implicit regularization phenomena that may arise with certain initialization schemes and that may deeply affect the optimization effectiveness. The occurrence of drastically opposite regularization by only modifying an algorithm's 's initialization showcases the critical importance of the latter for ML applications.
Although the analysis is conducted only for linear models, the results give already numerous insights on the behaviour of nonlinear architectures. The analysis of Theorem shows that, some regimes, the deeper layers behave as "a power" of the first layer: this result suggests that each layer is converging at a different speed. thus defines a hierarchy (in terms of speed convergence) between the layers of the network. Furthermore, one can notice that in the linear case FA "removes" some stationary points: unlike GD that potentially has many stationary points that are saddle points, all the stationary points of FA are global minima. Therefore, undesirable stationary points in the non-linear case. Several challenges remain, but the above pieces of intuition will be critical for the analysis in the nonlinear setting.
believe that EA will also "remove" some

---

Under review as a conference paper at ICLR 2022
Beyond this, it enticing to conduct comparison between FA and GD and illustrate the advantages of one algorithm over the other (and in which setting). All of these directions will be the central objects of study in future works.
REFERENCES
Sanjeev Arora, Nadav Cohen, Noah Golowich, and Wei Hu. A convergence analysis of gradient descent for deep linear neural networks. International Conference on Learning Representations. 2018.
Sergey Bartunov, Adam Santoro, Blake Richards, Luke Marris, Geoffrey E. Hinton, and Timo- thy Lillicrap. Assessing the scalability of biologically-motivan deep learning algorithms and architectures. In Advances in Neural Information Processing Systems, volume 31, 2018.
Tien Chu, Kamil Mykitiuk, Miron Szewczyk, Adam Wiktor, and Zhigniew Wojna. Training DNNs in O(1) memory with MEM-DFA using random matrices, arXiv:2012.11745 2020.
Francis Crick. The recent excitement about neural networks. Nature, 337, 1989.
Charlotte Frenkel, Martin Lefebvre, and David Bol. Learning without feedback: Fixed random learning signals allow for feedforward training of deep neural networks. Frontiers in Neuroscience, 15, 2021.
Gauthier Gidel, Francis Bach, and Simon Lacooste-Julinn Implicit regularization of discrete gradient dynamics in linear neural networks. arXiv: /3622, 2019.
J Gilmer, C. Raffel, S. S. Schoenholz, M. Raghu, and J. Sohl-Dickstein. Explaining the learning dynamics of direct feedback alignment. ICLR, 2017.
Daniel Gissin, Shai Shalev-Shwartz, and Amit Daniely. The implicit bias of depth: How incremental learning drives generalization. arXiv: 1909.1201, 2019.
Stephen Grossherg. Competitive learning: from interactive activation adaptive resonance. Cogn. Sci., 11, 1987.
Arieh Iserles. First Course in the Numerical Analysis of Differential Equations. Cambridge University Press, 1996.
Julien Launay, lacopo Poli, and Florent Krzakala. Principled training of neural networks with direct feedback alignment. arXiv:/906. 04554, 2019.
Julien Launay, Iacopo Poli, François Boniface, and Florent Krzakala. Direct feedback alignment scales to modern deep learning tasks and architectures. In Advances in Neural Information Processing Systems, volume 33, 2020.
J. Lec, R. Zhang, W. Zhang. Y. Liu, and P. Li. Spike- Trake level Direct Feedback Alignment: Sidestepping backpropagation for on-chip training of spiking neural nets. Front Neurosci., 2020.
Timothy P. Lillicrap, Daniel Cownden, Douglas B. Tweed, and Colin J. Akerman. Random synaptic feedback weights support error backpropagation for deep learning. Nature Communications, 2016.
Theodore H. Moskovitz, Ashok Lutair-Kumar, and L.F. Abbott. Feedback alignment in deep convolutional networks, arXiv:1812. 064888 2018.
A. Nøkland. Direct feedback alignment provides learning in deep neural networks. 160..0:600.0059 2016.
Maria Refinetti, Stéphane d' Ascoli, Ruben Ohana, and Sebastian Goldt. The dynamics of learning with feedback alignment. arXiv:2011.12422 2020.
David E. Rumelhart, Geoffrey Hinton, and Ronald Williams. Learning representations by back-propagating emors. Nature, 323, 1986.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. A mathematical theory semantic development in deep neural networks, arXiv: /8/iv///0.... /0531, 2018.
10

---

Under review as a conference paper at ICLR 2022
A CONVERGENCE OF FA FOR 2-LAYER NNS
A. PROOF OF PROPOSITION
Proof. We have that : BBlly v and D W Wja j thus
Vw, C -C E1/V VW, w; 1 = = = (y W2 W aa
(29)
(30)
= -Wo (Eay - W.W W, Mrz),
(31)
where the last line comes from the linearity of the expectation. Similarly we have,
Vw, B V Wi y ~1
(32)
(y W,W1z)ar WW]
(33)
= (Ea W2W1E W.
(34)
Now we conclude by noticing that by definition of the dynamics (2), the matrix W replaced by random matrix M.
A.2 PROOF OF THEOREM 2
Consider the following system of ODEs for the functions 01,02 02 E (R):
6 d (A 0201)
(35)
02 = (A 0201) 01
(36)
for some d, X E R2 From equation (35), substitute f () 0200) in the second equation (36) to obtain
62-22
8₂ = 2d 02. iec. 02(t) =
2d (t()) + K,
(37)
for some integration constant K E IR We then substitute such expression for (2(() back into the equation (35) in order to obtain closed form expression for 01:
0, = d 1==(A-
_ 0 - K01
(38)
2d
We now choose the initial conditions for (1) and (2))) in the following way:
00²
01 (0) = 6u
and
(₂(
(39)
2d
so that the equation for 0 becomes
0 = (2d2 0f)
(40)
We are now ready to prove Theorem 2, which we recall here for convenience:
Theorem 11. For any FA constant
IR and V 0g E R initial value with initialization scheme (39), 3C > 0 such that the product (2(1)): (t) of the solution of the system (35)-(36) converges exponentially to the signal X and in a monotonic fashion:
(0)())) A/ Ce -e ((N)))
+00.
(41)
Proof. By Picard-Lindelöf Theorem, equation (40) admits unique local solution 0, E C [[o, T)) (T > 0), for any initial condition 0g RR. The local solution can be then easily extended to a global solution on [o, +00).
The cubic polynomial on the right hand side (40) has unique real root r := 2d1: 2d - 0
(r -) (0f 0ir + r?) where the quadratic 0z 0ir + r is irreducible (indeed, its discriminant
is A 3,2 0).
11

---

Under review as a conference paper at ICLR 2022
If Ou the solution of the ODE (40) is the constant function (1 V R2o. In this case,
trivial to see that (2 = zi 2d
and (2()) (t) = X, V E Rzo.
If Oo + simply need to analyze separable ODE whose solution reads
aretan (01(()) +r rv3
In 10 (1) - rl 3
In (ff(t) + (t) + r + r2
+ Co =t
3r2
(42)
with constant of integration
2 Co
280 + r
In 8
r|
In 6 + r8 +
arctan
(43)
3r
3r
r2/3
rr33
Equation (42) transcendental and cannot solved for 01 explicitly. However, we can still analyze the behaviour of the solution.
Lemma 12. 0, (t) is monotonic: in particular, 0, < 0, 0n > r, and 01 > if00 <r
The above claims easily follows by inspecting the sign of the right hand side of (40). In particular, Lemma 12 implies that 01 (t) always bounded, for any initial condition &g E R.
As t + too, the left hand side of (42) may only diverge in the first logarithmic term (t) - r), since the term involving the arctangent always bounded and the other logarithmic term has argument that is always bounded (Proposition 12) and positive (the quadratic is irreducible).
Therefore, as +00
(t) r and
(2(1)0;(1)
(44)
2d
for any initial condition 0o R. See Figure Furthermore, we can derive from (42) the rate of convergence:
(01 r|
3r
2r
1
(0) +r
exp
+
In (t) r + r²1 + sign(r) arctan
2
2
|r|v3
=
(45)
where g(t)
Co
(I((3r2)
Vs o(1), as oc; therefore,
- (0(1)
(46)
Finally, from (2())= (t)2, we get the desired result:
(2()) 1 _
(47)
2d
for some positive constant C.
Remark 13. All the above calculations are valid also in the general case r, X E R (0}. In the case
where r < 0 (i.e. sign(d) d) * sign(A)) (A)), the solution 0 satisfies the implicit equation
2 (t) - rl 3
(t) + (t) + 2 2sign(r)
(t) +r
arctan
+ C =t
3r2
2 2/
1r|v3
(48)
and
2
1
2 sign(())
200 +r
Co =
In 10.
r|
In 10g + rl, + 2
arctan
(49)
3r
3r
2 3/
1r|v3
12

---

Under review as a conference paper at ICLR 2022
Figure 3: The plots of 01 (t). (2() and the product (2(t)01 with initial condition t ~ (5,5) À = and FA constant = (10 simulations).
To conclude the proof, we need to show that the product (2(4)r is monotonic increasing (if 8 < r) or decreasing (if 0g > r) to the limit value A. See Figure for a comparative plot of the solutions 01 (t), (t) and their product.
The monotonicity properties of 0 are described in Lemma 12). We recall here the first derivative of the functions 8 and 82 2d (t))
1 (133 09)
8
82 d B101,
(50)
2
and its the second derivative
3 0 = - 07 4
1 02 d ((1)22 +0,01
-
(0P
(51)
If Oo r, then (L) is strictly convex and strictly decreasing: by construction, 02(() is also strictly convex and decreasing. Therefore, the product (2) will be strictly convex and strictly decreasing V Rzo.
If Gu then (t) is strictly increasing and by construction the product (2(t)01 2d is increasing 1 E 12 The description of convexitylconcavity in this case is more involved and we do not pursue this direction, it necessary for our results.
Case A = O. If we assume the signal 0, we can follow the same argument as above and perform similar calculations.
Equation (40) has a simple explicit solution (assuming 0n + 0)
1
(t) = + 0
(2(t)
(52)
2d(1 + 2)
where + depends on the sign of 0n. It is easy to see that
(1) - = X
as + +00,
(53)
however the convergence rate is of the order of O(:33), therefore not exponential.
A.3 PROOF OF THEOREM 3
In the setting of Theorem 3, we considering the initial conditions of 0, and 0g independent, therefore the integration constant
1 (0) ER
== 2d
=
13

---

Under review as a conference paper at ICLR 2022
may assume any value. The cubic polynomial in the ODE for 0 has the general form
1 (0) + 2dK0 - 2dA)
0, =
(54)
and it could have 1 real root (and 2 complex conjugate roots), real roots (a simple and a double root) or real distinct roots. To discern the cases, we need to evaluate the discriminant:
A 4d (sdK² + 27X2).
(55)
Regardless of the sign of the discriminant, there exists unique global solution 01 C² for any initial condition 81 (0) E R and any constant K E R -ifcerd-Lindelff Theorem).
Case A > O. The polynomial has 3 real, distinct root r1 < r2 < T3, that may be written explicitly with the help of trigonometric functions, if needed. Note also that A implies K < 0. There are three constant solutions of the equation (54): 01 (t) = T3, t 2 0 (provided that 0g = for some j 1, 2, 3). Otherwise (Bu F ry V = 1, 3), the implicit solution of (54) is the following:
In (0 (t) - r3l
In (t) r2
In (t) rıl
+ +G
(56)
(r3 - (1's m))
(ra - (13--2) (r - mi)
- -1)((2 r))
with constant of integration
In 00 r3
In 0o r2l
In 16u -1
Co (r' 22) (r3 r1)
(57)
(T3 (22 r1)
(r3 71) (r2 - -i)
Lemma 14. (1) is monotonic:
0 <
if 0. E (21, +00),
(58)
>> 0
if 0,
(59)
In particular, from Lemma 14 we can conclude that the constant solutions 0, (4) = ri and 0, (1) = -33
attractive and 0₁ (t) ra is repulsive; the general solution (regardless of the initial value 0g R) bounded for all times.
Following similar arguments in Section A.2, can conclude that the convergence is exponentially fast:
(ra (1a-ma)ir--1124440
(t) T3
as + +00,
(60)
for E (32,73) (73, +00). A similar asymptotic expansion is valid for the quantity (01(t) r1l
when On E (-00, r1) (r1,
Using the relation (2 1. (t) K, we have
Krz S Ce (m--aall---)))
(t) (t) 2d
(61)
for some C > Notice that, being I's root of the cubic polynomial x.3 2dv 2dA, it follows that 27 Kra- X. Similar arguments hold for ri.
Case A- < 0. The polynomial has real root r E R and two complex conjugate roots. Let us assume À (therefore, * 0): the case À 0 analyzed shortly below.
Using Cardano's formula, the single root has the explicit expression
8FK3
8d
dA
x2
1 dd
p22
(62)
27
27
The setting is the similar to the one analyzed Section A.2. From monotonicity argument, it follows that the constant solution 8, (t) = r (with 6 = r) is attractive, therefore for any given initial condition to. 01 (t) is bounded for all times and it converges as / +00.
14

---

Under review as a conference paper at ICLR 2022
The implicit solution reads
In 01 (t) 2d1
In (t) -r
2 (r dA)
4 4 + dA)
3r
(2(2) (t) + +r) 4dd -
) Co 2
8(7 + - )ور arctan
(63)
with Co the constant of integration.
From (t) = 2 (t) + K. convergence follows: 02(t)01(t) + 2/ + Kr X as + to0.
Furthermore, convergence is exponentially fast
(t)())( >o s Ce
as + t00,
(64)
for some C > 0.
Case A = 0.
The vanishing of the discriminant implies that the constant of integration has
specific value
3 3 X2 K
2=-2V
2 d
Notice that the set of initial conditions (0: (0), such that 0 is a set of Lebesgue measure zero in R23.
Remark 15.
In this case, the polynomial has simple root r, and one double root ra:
3\
3A
2Vd,
Vd
(65)
K
2K
The solution of the differential equation (54) (for 0g + Ts: Ta) reads
ral In 10 (1) ral In (1)
(r's (rs-ra)(Bp) (t-r))( +Co t
(66)
ra)
with Co the constant of integration.
Lemma 16. The solution 0 (t) is monotonic: ifr, rd.
0 <
if 0n E (rs, +00)
(67)
0,
if Oo (-c0, U (ra,
(68)
and similarly is. <
0
if A (ra, (ra. +00) if 0 E (-00,
(69)
0, >
(70)
Therefore, the solution 01 (t) = r, is always attractive, while the solution (t) = ra is "one-sided"
attractive. The solution 0, (1) bounded for all times and the convergence result follows:
1 2d Krs = A t oo;
(2())
(71)
similarly, for ra. Exponential convergence holds when (1) - rs. while when (1) - ra the rate is sub-exponential.
In the special case when and X 0, the polynomial has triple root r= 0. The solution is the same as the one derived in Section A.2 in the case of X = 0 and the convergence to the signal is polynomial:
(2))))( Ct
t +00,
(72)
for some C > O.
15

---

Under review as a conference paper at ICLR 2022
Figure The plot of the product 0g (1)0) (t) with initial conditions 0o 1(1-1,2)), FA constants dj 2 and d2 2.5, (10 simulations).
B CONVERGENCE OF FA FOR L-LAYER NNs
B. PROOF OF PROPOSITION 4
We have that C BEllyy أ and ÿ
Wz .. W2W thus noting W aasi
2
W.W Wa we have,
Vw 3 Ww, yyy ~1|3
(73)
= =R[ [1+:12 (y W. W W/ W
(74)
= =W [e+11 (2a WL W W [---1]
(75)
where the last line comes from the linearity of the expectation. Now we conclude by noticing that by
definition of the FA dynamics (2), the matrices the left hand-side of (y W2 W1x) are replaced
by random matrices M, Thus we get
We Mr(E.y WILL)
W Wie-11
E [4]
(76)
where we reparametrized M, = M[+1i (see discussion in the main text).
B.2 PROOF OF THEOREM 5
We will first state Theorem 5 in more extensive form. Given the system
å (2 0z 0.,,0000.....
(77)
Ú dr.-1(A 10.....0000.-22
(78)
(79)
02 d2(A - -0)...0)00
(80)
0, d, - ..)...
(81)
where we suppressed index for simplicity, the following result holds.
Theorem 17. For any set of FA constants (de) de E Rso there exists an initialization scheme such that the system of differential equations (77)-(81) can be reduced into an equation for 81 of the form
0, = (x- R0A)
(82)
for some constant & E Rso that depends on {de}, with 7 2 The other functions depend directly 0 in power-like fashion:
Ct
0r(1) 20-1
01
l= 2, 2...,,
(83)
16

---

Under review as a conference paper at ICLR 2022
for some Ct E Ryo. Furthermore, the following convergence result holds:
0z())rr-i(t....0((()) + X as +00.
(84)
See Figure 4 for numerical simulation of 3-layer scalar network.
Proof. The proof of reducing the system of differential equations into a single equation for 81 will be constructive, following a simple iterative procedure. We start by considering the last equation (81)
and by substituting (A OL .......)=
& in the second to last equation
di
d2 0,0 = 2d1 (0P)
d2
d2 (1(2) + K2,
02
implying (2(()
(85)
d1
2d1
for some constant of integration K₂ E R, which can be set to zero if we impose 82(0) = de (0)
The same substitution strategy can be consecutively applied to the third to last equation, fourth to last equation and so on. In general, it is easy to prove by induction that V l ....., L we have
0g = -20 for some Ct- = Ce(d1, ...,,...... de) E Rx0, which implies Ce
(x(t) 2 2--1 (t) + Ke
(86)
where as before we can set the constant of integration K₁ = 0 by imposing 05(0) 2 (10)²
C. ((
Once we have derived the relations between the functions (f)()) and 81 (t), we can plug all of them into (81) to obtain a closed-form differential equation for 01:
81 d1 (A R07))
(87)
where R = I S Ryo and y = Σí 2' = 2" 1. This is a separable equation which can be solved (with tears) by using partial fraction decomposition.
The proof of convergence of the product IT (e(() to the true signal À follows similar argument as in Appendix A.2. Let r == V be the unique real root of the polynomial -R07. then the solution (1) is a constant solution, provided that 0, (0) (0<(0))=2.... are also constant functions and their product is such that
By construction, it follows that
L
Ce 2
(
II
--
-
V2 0.
(88)
E-1
Lemma 18. The general solution 0, (t) is monotonic:
8 > 0
if (0) <r
(89)
0 <
if 0, (0) >r
(90)
Therefore, 8, (t) is bounded for all times and 01 (t) + r as t + too. By construction, follows that
C2 ? X 2
II
as +00.
(91)
Exponential convergence follows from a careful analysis of the implicit solution of the separable equation (87), similar way as it has been done in Appendix A.2.
The proof of convergence of the FA algorithm for generic initialization (01 (0)....... 02 (0)), where each layer is initialized independently, follows the same guidelines as the 2-layer case (Appendix A.3).
Sketch of the proof. In the same setting as the proof above, by keeping all the constants of integration K₃ O, reduce the system of ODEs (81) to single ODE for 01 of the form
è (,( (1l::d1...,,dp
(92)
where P is polynomial of degree 7 2 - 1 in the variable 0 with coefficients depending the FA constants di...., dr, and the signal X. is still a separable equation that can be studied via a careful analysis of its discriminant.
17

---

Under review as a conference paper at ICLR 2022
C IMPLICIT REGULARIZATION PHENOMENA
C.I PROOF OF THEOREM 7 (CASE A > 0)
For readability, we are suppressing the index i from all the formulæ below. Recall the Initial Value Problem for 01 (and 02):
1 (0) + 2dK0; - 2dA)
81 = 2
(93)
(0) = Po
(94)
and (t)
1 (t) + K, where K = (0) 22 0.. By assuming that the discriminant is positive 27
A -d (8dk3 + 27 O, the cubic polynomial the right hand side of (93) has real
distinct root r1 < 12 < r3 and the solution the ODE is (see also Section A.3)
In (t) r3l
In (t)
r2l
In (t)
r1
+ Co
(95)
332
21
131
In 100 ral
In 10 r2l
In 190 ril
Co =
(96)
T32131
T32721
T31721
where we set rig = Fi- rz.
we set as initial value ou = 12 + e
- (6 > 0), then
In (r32 e- In (r21 + t
Co = T32
(97)
T32
T31
we additionally rescale the time variable as + 8t. Rewriting equation (95), we have
rs (ōt) cxp
332
8
2
+ In (r32
e0 +
132
In (r21 + 00
T22
r21
131
T32
In (01 (6t)
r22
In (01(6t) r1)
(98)
r21
T21
132 5
T21
13 01 (5t)
132 In
(1( T1
(8t) r2 = exp
+
+
P32
T31
F32
P31
P21 + c 8-8
(99)
From (98)-199), we have the following asymptotic expansions: as 5 + to0
(ôt) + r'
for > T
(100)
(61') + r3 exp {(1
(1+
F31
T32
T21
In 132
In
(101)
T21
T21
131
81 (6t) -> r2
fort < T
(102)
with T 132121"
In the case 0g = 12 - e we can follow a similar argument: as 6 + t00,
(ôt) +
for T
(103)
(6T) + ā ri exp {(+
F31
F21
T32
In
In
(104)
P32
T32
T31
(ōt) +
for t < T.
(105)
The last bit of result we need analyze if the value of the critical value
(106)
T32
monotonic as À increases. Recall the cubic polynomial on the right hand side of equation (93)
(without loss of generality, are setting 2d 1): P(x) x² +K - (x-ri)xx-12)) (r)) (T))
where À > 0 and K -3 223 < 0 depends the initial conditions of the FA system.
18

---

Under review as a conference paper at ICLR 2022
0-0.
5-10
1
6-
1-15
25
(a) Numerical simulation of (t) with -2, (b) Plot of (ot) (A 0). with initial condition 1. r3 = 2 and initial conditions 0g r2 + e with 0o 12 + e 0.0 20), FA constant = 0.5, initial 8 E {10, 20, 30).
condition K =44
Figure 5: (Anti)-implicit regularization.
The quantity T32121 can be expressed as r32721 = (r22)) = -3 K, where It is easy to see that if À < X, then |r2| < |/2 and consequently 132
< ffr À > 0.
- K >
- ~2
K
T32 i.e.
2
2
Tx
Tx
(107)
732
Ps22221
Therefore the threshold time 7 is an increasing function of X. See Figure 5b: in the d-scaling limit we see indeed that for smaller values of X, the step appears sooner.
C.2 EVIDENCE OF INCREMENTAL LEARNING IN THE CASE K =
Consider again the system (93) in the case K 0:
0 1
2 (0} 2dA)
(108)
01 (0) du
(109)
and (2(+) (t).. In this case, the solution reads (see also Section A.2)
(t) +r
In (t) r|+ 3
In (0)(t) + (t) + r2/3
arctan
+ Co =
2
rv3
(110)
1
200 +r
Co
In 100 - rl
(0g + r0 + 12)
arctan
(111)
3r
3r
72 v
r/3
with = 2dd
As the limit value of the function 0, (1) is the positive root 0, (To) (for some To > 0) if and only if 0g < 0. The value of To can be easily derived from the implicit expression (110):
To π
(r 1r-00 00))
200 +
In
arctan
(112)
23
3r2
8
rBu + 2
rv3
and in the regime as 00
4T
1
To
3r2
03
+
03
0 +
-00
(113)
It is now clear that for bigger X (i.e. dominant singular values) the crossing of the r-axis happens sooner: for A > À and fixed FA constant d > 0.
Ta < T T
(114)
19

---

Under review as a conference paper at ICLR 2022
D CONVERGENCE OF THE DISCRETE ALGORITHMS
We will report here all the proof' the convergence theorems for the discrete FA dynamics. We will first discuss convergence guarantees and convergence rates for the modified (mid-point) FA dynamics for both 2- and L-layer NNs (L 2 3), as is more straightforward. The convergence proof for the forward Euler discretization method can be found in Section D.2.
D.1 CONVERGENCE OF FA UNDER THE "MIDPOINT" DISCRETIZATION SCHEME
We recall the 2-layer system that we want to analyze. For simplicity we are suppressing all the i indices and we denoting (Ie, yt) the unknown functions in the system:
Lt+1 = 2, + nd (A - 2z9:))
(115)
Vt+1 = yt + 2 (A x1y4) (Z++1 + xz)
(116)
We begin with proving series of easy lemmas that will be instrumental for the proof of the theorem.
Lemma 19. With initial condition (Io, yo) = (0, 0), the second component of the solution of the system (115)-116) reads
z
vt 2 0.
(117)
2d
Proof. From equation (115), result:
20-1-01 md
X 3zt4i substituting in equation (116), we obtain the
(xe+1 + xx)(11+1 xtt)
2++
2
M6+1
1/t +
1/1
+
2d
2d
t
2
j+1
x
2
= yo +
Yo
(118)
2d
2d
2d
j=0
0
via a telescoping sum.
Substituting the expression of y back in equation (115), have recurrence relation for x of the form:
#++ = xz + pdd (1-
x²²
=: f(x1).
(119)
r3
where r = 2dx.
Lemma 20. With parameter
2
2
17 <
(120)
3,2
3(2d))
the function f(x) = r 7dl (1- 2 maps the interval [0, r] into itself: V a e [0,r], f(x) e [0,r].
Proof. By inspecting the function. and its derivative we can conclude that f(x) 2 E [0,r]
and f increasing on the interval 0, 3n
Notice also that f(r) r. Imposing (120) guarantees
that r < / therefore
ndd= = f(0) f(x) f(r).
Vx [0,
Lemma 21. In the same hypotheses as Lemmas 19 and 20, the sequence (ache20 bounded, positive and increasing:
0 5r and x4 S se+ls
44 2 0.
(121)
20

---

Under review as a conference paper at ICLR 2022
Proof. For t O, trivially 0 I zu 0 S By induction, assume that 0 22 S r, then by Lemma 20
0 S 1e+1 It pn (a.
x3
[(xx) S S(()
(122)
2d
Furthermore,
#1+1 = Et + (2d) - xt) 2 2t
+ 7 2
2dd - (V2d1))) = Z1.
(123)
We now prove Theorem 9 that we rewrite here for convenience:
Theorem 22. With initial conditions (2r. vo) = (0, 0), A A, and with step size 1 < the following convergence result hold:
3(2dx)
[fe \1 S 33 (1 " (2dx)3)
(2
(124)
(which is outside the range prescribed in Theorem 9) and To = O, we achieve convergence in one step: Ia = 2/2xVt>> 0.
Remark 23. Note that if (2dx)
2
Proof. By Lemma 21, 3 E R20 such that 24 t + +oo. Furthermore, by solving
f= 1
(125)
it follows that / r 2dd. Finally, have
12 r| 12-1 x
(n' 2 1)
1
r|
" (2)
+ +,²) +
2
37 p2
|1-- - rl
1
3/ , 2
Sr 1
(126)
Note that < 1
3n ,
2
1, since 1)
<
3,2
In conclusion, thanks to the arguments above and
Lemma 19, we have:
[allee - A/ =
2d
It
X
=
2d
1
1 + r.t + 120 - -l
3r2
3r
(1
1
31 2
[r
r|
S
2d
2d
2
31
31
(127)
2
For the general L-layer case, we first recall Theorem 10.
Theorem 24. Consider the following system:
(1+1)
(++2) () -000 10000...00 .(.)
0((+2) = -000 + 10 ...0
(128)
10 ...07 0, (1+2)
(1-2)
ol++1) 010 + ndd-
(2- ol 0())
(129)
(130)
0 0,000 + 1 m
(1+2) (1- 0(0) ...)()))
(131)
((++1) (19 + ndh (2 (^- 1--0f 000) ... ,(00)
(132)
21

---

Under review as a conference paper at ICLR 2022
with zero initialization 0g 0. A 1, ..... L. Assume that de 1 ,,... L 1, and the constant step size satisfies
74 di (RX0-1)5
where = 2 and & is a suitable positive constant depending on the FA constants di...., dr.-1- Then, the product TT= ( linearly converges to the true signal X:
-0....--- Cx (1 (1-ndi7 nd1i (RAT-1) $
(133)
for some constant Cy E 12 only dependent X.
Proof. We consider the last equation (132) and substitute
_ 000) o((+2) p7-)
(134)
nd1
in the second last one obtain
0 0
d2
(o)*)) 21
02
d2
0
(135)
2d1
2d,
by telescoping sum. The same substitution strategy can be consecutively applied to the third to last equation, fourth to last equation and so In general, it is easy to prove by induction that L = 2, 2,..., we have
(((+1) = +600+ +Ce [(o(ttn)001
25-1 - -(0(t)²
27-1
8 =ce =o((oo))) 2--1
(136)
for some Ce Ce(di,..... de) E Rs
Once derived the relations between the sequences (0,") Ie=2.... and { we can go back the recurrence equation (132) for o( to obtain
e((+1) 8(() + ndl [ ft {B
(137)
where A -1 C2 E E and 7 -1-11 2 24 11 1.
Lemma 25. With initial condition (1) and for d
1
+ the sequence (8(t)) is positive,
increasing and bounded by r=
Proof. The proof follows the same argument as in the 2-layer case. The odd polynomial f(x) = x
nd, (> Rix") has least one fixed points at and f(0) ,dlr > Furthermore, f(10, rl) C
[0, r]. Indeed, the function is increasing on the interval [0, Fmax] with Fmax 7 d17(RA then r < 2 Fmax implying that
ydl A = f(0)= < f(x)(( s f(r) =
Vx [0,r].
follows (by induction) that < o(t) < r V and 8 s g(t+1).
From Lemma 25 we can conclude that ((4) - and
0(9) -r| 10(- -r ndd18 ((0(-11)² rr) = ( -r| 1 --nd
(olt-1))
(0(t-11)--13 m
2-13)
2-1-5
< (0(e r| Ryr (0(1-11) -r|
-r
(7) (1
[1-nd nd,
1 1
11 (1 1-pu11 (81
(138)
22

---

Under review as a conference paper at ICLR 2022
Finally, we have the following linear rate of convergence
0 10...00--10 2 = R - s 0f - - (1
-
(139)
D.2 DISCRETIZATION UNDER THE EULER FORWARD METHOD
By discretizing the FA dynamics via the standard Euler forward method, we obtain the following recurrence relation for the iterates:
1x+1 + pll (A TeWle) 1 1/2 + 1T4 (A 2z3ba)
(140)
(141)
with initial condition 20 = yoo 0. If we use the same substitution strategy as before (A TtZ/t nd ), get
Le+11 3t
ft + It [1+11 - Iz)
Ut+1 = Yt + 1J2
Yt
+
[x++1 + +11)) - (xz+1 xz1] (re+1 x1) = y1 +
(22 - -x2) 2d
(x++1
xx2)
2d
2d
y0
20
2
2
1
Σ
(x) 2)-1)²
(142)
2d
2d
2d
j=1
i..
yt
2d 2t
St
Vt20,
(143)
where St : Ei xx-1) 2 and So 0. Notice that 0 0 S. S S.41 V by definition.
Plugging (143) back into equation (140), we get highly nonlinear recurrence relation where all the past terms of the sequence (up time t) are involved in determining the subsequent term Ft+1i
F++1 x4 + " 2dd + S.).))
(144)
We will now provide a proof of Theorem The proof is quite long and it divided into four parts for readability. We will first rewrite the statement in the following way:
Theorem 26. Consider the sequence {(T,, y)} defined recursively in (143)-(144) with zero initial- ization To y/ 0. For any d > the constant step size as
2
2
n min
(145)
3(S* + 1)2
max(2. P(x, S)
where P(x, S) = 2dA 3 + xS, S is the unique positive solution of P(x,x) = O, and R is the following compact, convex set
:: (x, E R2 1S P(x,S)
(146)
Then, the product reh linearly converges to the true signal X:
| Al < Cq'.
(147)
for some C > and 0 < q < 1.
Proof of convergence part 1. order to prove convergence of the sequence { we will first consider a more general sequence defined by the following recurrence relation
F1++
1 2dx
1 x
(148)
2
23

---

Under review as a conference paper at ICLR 2022
where {ar} is auxiliary sequence that assumne to be increasing, positive and bounded (therefore convergent: a, - axe for some aeo E Ryo).
Consider the following fixed-point problem:
x f=; with (x; =x+ 22(2
2d2 x3 + or)
(149)
with 2 0 and a E [0, az) Notice that a 2 0. we have that f(0:a) ydx > 0 and f(z;a) 7 - oo as x + +o0. Therefore, a 2 0, there exists unique fixed point la > 0 for the function f (uniqueness follows by directly inspecting the cubic polynomial f(:;a) with fixed).
From #1 f2 0 for 0, it follows that f(x; a) f(x; al); Va < a'. Furthermore, L, S Ser indeed, V 0, la is the unique zero of the cubic polynomial (a(x) -r
2dA the positive real line (Pa (0) 2dA > 0, (0) = a > and (x(x) + -oo as æ + -oo); its partial
derivative aP x 2 0, for æ 2 0. implies that as a increases the zero la shifts rightwards on R. 2a
On the other hand, from
0f dr
77 2
3 2
1+
2
0
(150)
we obtain that the function f is increasing on the interval
0,
2 3n
In order to ensure mono-
3
tonicity on the interval [0, fa), we tune the parameter 17 such that
2
a
la S
V 3r
+
3
(151)
By taking the supremum over a E [0, a on the left hand side and the infimum on the right hand side, we have
lax 5
(152)
371
such a bound is satisfied if
2
1) 5
(153)
362 0100
As will be clear in the next parts of the proof (see Remark 29), the value of la is smaller than S* therefore (145) guarantees that the above bound (153) is satisfied. This implies that
1. (x; S f(a;;a) V E [0, L0 S x'
2. f(x; maps [0, ls..] into itself V a E [0, acc)
In conclusion, have
(
Voso,yaso'
(154)
We are now ready to prove the following lemma.
Lemma 27. For 7j S 36 the sequence (148) (with zero initial condition) is positive, increasing and bounded: Vt 2 0
S xz S Ft+1 S law
(155)
Proof. The proof is by induction: for we have 0 I0 Sx1 ndd < las and assuming that It-1 < Fz, it follows that
0 < It f(z,-1i; ((z x141 S flaas i00) las
(156)
n
24

---

Under review as a conference paper at ICLR 2022
Therefore the sequence (148) converges: 2t w for some E Rso. By construction, it is clear that w = lax Indeed, given
T++1 = 24 +
2dx (2dx
17 2
x² + x(ai)
(157)
and taking the limit as oc on both sides of the equation, we obtain
w w (2dx w + wass).
(158)
L.e. w is a (positive) solution of the fixed point problem x = f(x; ano)) whose unique solution is fax..
major problem arises when we consider the case of a; = S; =i= (2, - -x,-1)² 1.1)),ia i.e. the auxiliary sequence { depends directly the primary sequence {x²). ). Clearly, 0 S at ax+1 for all times t 2 0, but the boundedness property is not straightforward.
Boundedness of' the sequence of partial sums {S.}. the recurrence relations:
Since S.+1 = Se + (I++1 - IZ.)² consider
Z441 2t + ! (2d) z x,Si)
(159)
2
S+1 = St + 1/2
(2d) - x + x.)))
(160)
4
Lemma 28. Given the convex, compact set
R : (x) R2
SSSa x, S)x,S) 0}
(161)
with P(x,5)= = 2dA - x3 + xS and
2 3(S* + 1) (a,(e, P(x, S)
2
n < min
(162)
where S is the unique positive solution to P(x, x) = O, and with initial values xo = So = 0, the
sequence {[z 8i)3 defined recursively (159)-(160) is bounded and lies in the set R.
See Figure 6 for sketch of the region R.
Proof. The set of fixed points of the system is the set of zeros of the function P(x, S),
x x + 3 P(x, S)
+
P(x, = 2dA x3 +x55 = 0,
(163)
S= 7 P(x,5t S)²
which is an algebraic curve in R², with solutions in (I, 8) E RR2
S=x² 2dA
(164)
furthermore, there exists a unique solution the unique solution to the equation 3 x² + 2dA 0 and it's explicit expression can be recovered from Cardano's 's formula (if needed).
S') E R2,0 such that P(S = 0: indeed, S* is
We will prove the theorem by induction. For f 0, trivially So mn and P(zo, So) 2dA 0.
For t = 1,
1
S = 11 < <1 yda
dA if
S
(165)
S1) 2dA
ydn (yykr) (nd2 2dA > 0.
(166)
is easy to notice that (162) is satisfied, then 17 S ax as required in (165).
Since R. is compact, the value of the polynomial P(x, S) is bounded and positive for all (x, E R:
0 < 2dA = P(ao, So) - max (r
Psx,5) < +00.
25

---

Under review as a conference paper at ICLR 2022
x²
2dA
S
R
2d
Figure The compact, convex set C IR 20
Assume that v = .....,t =
we have
S, S Nio.
Se) 2dd x2. x. 20
(167)
then,
12
Se+1 St + 4 P(rt,
x4 + " P(s,, St) St) " P(at, St) S 81 + " St) It+1,
(168)
thanks to the induction step and (162). Additionally,
1 P(z,, St) 4 P(t,, St)²
P(I+11, Se+1) P(x,, S.) + V)
(169)
for some (z, 5) belonging to the line segment connecting the point (I,, St) the point (I++1, St+1). by the Mean Value Theorem;
S(41) = P(x,, S:) + P(x,, St) (-37 +5 + 1 &P(x,, St)
4
1+ (- -33 + +5 n &P(r Si)
P(x,, Si)
2
31 z2
P(r,, Si)
1
(170)
2
Notice now that 0 ã x, 8(I+41 2+) Iz + P2 St), for some 8 [0, 1]; since (zz, St) E R by induction,
F S +1. "
max 2 (a,S)eR
P(x, S) < 5" +1.
(171)
Therefore,
31 _² 2
3n (S +1)² 20,
P(Z+11, S(+1) 2 P(a,,
> P(x,, St)
1
(172)
2
by (162). The result follows.
Proof of convergence part 2. Theorem 28 above implies that the sequence partial sums
{S, = Ei= (x; 1 converges: S, + Sxx := - 2;-1)² < +oo and we can resort to the arguments in the first part of the proof conclude that 34 - lss..
26

---

Under review as a conference paper at ICLR 2022
Remark 29. Note that Es... is the unique positive solution to the equation P(x. S20) 0 and, since the sequence {(1,, St)} C R, f. lies on the boundary of R. This implies that E _ S
Finally, the product 2t À as +00. Indeed, since Ia + Egw =: L. then, by construction Ye will also converge to some value å (because of (143)). Moreover, L is the fixed point of the recurrence equation (144);
L C+ 2
(2d 2dd - L + +LS00)
(173)
which can be alternatively written as
L C-C+ bn (A-LC)
(174)
C is fixed point if and only if CC = X, implying Telt X.
Linear rates. The last piece of results that needs to be proven is the linear rate of convergence. Consider the difference Es, It, where Eg. is the unique positive solution to P(x, Sz) = 0 and by construction de S St:
1s4t1 2++1 : It-
P(z,, St)
2d1
1 It
(Es, xz)
x/ + Ls Et +
Es.
(Ls, x²)
1
!
1
2
x,6s,
2dA
(es - Ls.))
(175)
2
=:
We will bound each term B₁ and B2 separately. The first term can be easily estimated:
Bi 2 - ! 2 (15)2 + SS
2dA
1 M
(176)
where we defined
M (S+) + S + (2d1)
(177)
(recall that ts. 2d)). In order estimate Bz, we will first prove series useful lemmas that illustrate some properties of the sequence {fs,
Lemma 30. A 2 0,
2dA
2dA
0 <
< P2.
St -
(178)
tso0
Proof. By definition of És..
S(), = 2dA
G + S. =0
(179)
i...
2dA
G S l.
0.
(180)
Using the fact that {1x}} is increasing and bounded (Eso S fs, S ls V > 0), the result follows.
Lemma 31. Vt 2 0,
E+41 - Iz S M (ls. - xz)
(181)
with M defined in (177).
27

---

Under review as a conference paper at ICLR 2022
Proof. The proof easily follows from the recurrence relation of the (increasing) sequence {xz):
11 (2d2 .. xxSi)
Jt+1 2t
(es, - xz) ? (5*) + ls + (2d))$)
(182)
=yM
Lemma 32. Vt 0,
I ss4 - ls. S Coo (I++1 - xx,)
(183)
for some constant Coc E R
Proof. Using again the definition of ls., we have
S Es = 1 S141 - Ss
(est+1 (s.)) Sit1 + Es, (Se+1 5t)
= (est.1 (s,) Si+1 + Eg. (I141 - x²)²
(184)
on the other hand,
es (es.11 - (s.) (Cs.. + Essnes + (t).)
(185)
combining (184) and (185) and using Lemma 30, we obtain
Ls, (Te+1 x22)
1s Ls..
PS., + ( Ls, + L. S141
E0 (I x2
fs
(It+1 xx)2
(186)
282
2dA
2(2dA) 1 + 2dA
So
15000
25.00
=:Coo
Collecting the results from Lemmas 31 and 32, have
B2 S (2 - xz)² < MC (ls. - =x1²
(187)
In conclusion, for 17
M7 we have
( 2α+1 I (es, Iz) (1 1- nM) + 7 (ls, 21)²
(ls, Izt) (1- nM (1-nM + m
< 2/d (1 (1- nM + n m7²
(188)
where M := 26 MMC > 0 (we used the fact that {(s,) and {xt) are bounded); we stress that the quantity nM - 7 smaller than (thus being indeed a convergence rate) for small enough.
28

---

Under review as a conference paper at ICLR 2022
E
EXPERIMENTS
E SOLUTION OF THE FA ODE SYSTEM
Figures 3, 4, 5, plotting solutions (and products of solutions) of the FA system
å = (A 0.) 0.0.).))0-11.....
(189)
0, d 0.)00.....-2.......
(190)
(191)
02 d2 - -Or...0130,
(192)
0 d1(A - 02)
(193)
in the continuous setting (t E Ryo) are obtained using the standard ODE solver ode45 on Matlab (version R2020b).
E.2 LINEAR AUTOENCODERS
We set up two linear autoencoders
ÿ W2Wia
(2-layer NN)
(194)
W3 W2 Wix
(3-layer NN
(195)
where W. E gdxd
20 and the data are synthetically generated as
2; Az; c,,
2, N(, In). e, 10 10-3N( Ia)
(196)
= 5 and A E Rdxx is a fixed matrix that we sampled with entries Aij ~ ([(0 1)).
For the experiments showed in Figure 2, matrices as ( ( w(() such that W 10 10-5 1)).
the step size 7) 0.01 and initialized the weight
The FA matrices Mr are generated as Mea ((10, 1J). We repeat the FA training for 15 times, sampling different set FA matrices each time (but same initial conditions w(() and same matrix A): in Figure we then report the average of the trace norm and the reconstruction error with error bars calculated as mean visible in the final plot). We complement these experiments with the corresponding GD training.
ra__addaddddevii iti (the factor is to make the error bars more
29


Reviews:
[{"review_id": "lZdWxgUi_oe", "reviewer": "Reviewer_6Die", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is a nice theoretical development, extending the theory of linear\nneural networks to the case of DFA. The authors first study the shallow case\nbefore extending their arguments to the deep case. Throughout, they are clear\nabout the assumptions they make (choice of initialisation, commutativity of the\nweight matrices, etc.)\n\nI found the results concerning the implicit bias interesting - it is surprising\nthat FA would exhibit this inverse learning order, and I am not aware of an\nimplicit bias that would depend on the initial conditions in such a\nqualitatively different way. This observation should be interesting beyond FA.\n\nThe numerical experiments nicely illustrate the results, and show very good\nagreement with the theory, even if some of the assumptions (e.g. on\ninitialisation) are relaxed in the experiments.\n\nThe paper is well-structured and clearly written.\n\nFurther comments / questions:\n\n- In the analysis of the discrete update equations, what exactly is the\n  motivation for the additional term $W_1^{t+1/2}$ in Eq. 25? Is this system of\n  equations simply more convenient for the analysis? If so, how does it connect\n  to the algorithm?\n\n- In your conclusion, you state that you anticipate that FA will \"remove\" some\n  stationary points from the landscape of non-linear networks. This connection\n  didn't become clear to me, could you elaborate?\n  \nSome cosmetic comments:\n\n- Could you clarify over which distribution the the average is taken in Prop. 1?\n  Is it w.r.t. the finite dataset or over the distribution $\\mathcal{D}$?\n- I would increase the fontsize of some of the plots to match the captions, in\n  particular Fig 1.\n", "summary_of_the_paper": "The authors study feedback alignment (FA, Lillicrap '14), an alternative\nalgorithm to the standard backpropagation algorithm to train neural\nnetworks. The key idea is to replace the weight matrices of the network with\nfixed, random \"feedback matrices\" when computing the weight updates while\ntraining the network. A precise understanding how such a learning rule can lead\nto learning remains an open question, and has recently attracted some interest\n(see related works)\n\nHere, the authors study the dynamics of learning with FA in (deep) linear neural\nnetworks. The dynamics of linear neural networks trained with backpropagation\nhas been studied extensively, thus providing an ideal test bed for this\nstudy. The authors derive a set of continuous-time equations governing the\ndynamics of FA for linear networks, discussing in detail their assumptions\netc. They use these equations to discover an interesting implicit bias of FA:\nfor certain initialisations, features of the data are learnt in the *inverse*\norder of importance, quantified by the singular value associated with each mode\nof the data. For other initialisations, features are learnt in the order of\nimportance, as expected. The sensitivity of this bias to the initialisation\ndoesn't appear in backprop. Finally, the authors also study linear auto-encoders\ntrained with FA, and find that not FA does not only recover (a rotation of) the\neigenvectors, but that it also speeds up training significantly. They also\nstudy the discrete-step dynamics of FA.", "summary_of_the_review": "Feedback alignment has attracted some interest in recent years after it was\nshown that it can train a range of neural networks, and some groups have started\ninvestigating the mechanism that allow the training to proceed with random\nmatrices. This work is thus timely and should be of interest to the ICLR\ncommunity. It provides several interesting contributions regarding (1) the\nmechanism behind feedback alignment algorithms and (2) the implict bias of\ndifferent learning algorithms, through an analysis of linear neural networks, a\nworkhorse in neural network theory. I therefore recommend acceptance at the\nconference.\n\nPS: I am not sure I fully understood the questionnaire below regarding the\ndifference between \"technical novelty...\" and \"empirical novelty\". Since this a\ntheory paper, I only voted on the technical novelty.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EJJ7XtF5Do", "reviewer": "Reviewer_xi3S", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It provides convergence results on deep linear neural networks for feedback alignment for both discrete and continuous cases.\nThe authors show that the feedback alignment algorithm sequentially fits the solutions of a reduced-rank regression problem, and an initialization scheme is proposed to address the problem of anti-regularization.\nThey also show that the convergence results hold for networks that are not necessarily over-parametrized.\n\nFeedback alignment method is named after one of its outstanding characteristics that the forward weights get aligned with the random backward weights. However, this paper does not seem to have even mentioned any attempts on such explorations.\nThe current results focus primarily on the linear networks, which leaves a gap between the theory and the empirical successes on networks with non-linear activation functions.\nThe definition of the loss function assumes a strong condition on infinite sample size.\nOne of the key steps of reducing the original system of ODEs into a scalar system relies on the assumption that the initialization of the weight matrix for the second layer is deterministic given the one for the first layer. However, people often initialize each layer randomly and independently before training, and the condition seems to be more artificial on deep networks.\n\nThe overall structure is clear and well-structured.", "summary_of_the_paper": "The authors prove the linear convergence rate of the feedback alignment algorithm on fully connected linear networks. They also identify the implicit anti-regularization phenomenon for certain initialization of the algorithm and further propose initialization schemes that provide a form of implicit regularization and facilitate the learning process.", "summary_of_the_review": "The paper is nicely written, and the phenomenon of anti-regularization is interesting. However, the convergence results seem to assume strong conditions that only works for specific cases.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2-1jmDTGebo", "reviewer": "Reviewer_Q9E4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper is clearly written. I checked most of the proofs and they seem correct. Moreover, some results, e.g. “backward learning”, are novel and interesting. \n\nMy major concern is the significance of the results since all of them are under spectral initialization. Specifically:\n\n1. I believe not all linear regression problems admit spectral initialization. It is only possible when $\\Sigma_{xx}$ and $\\Sigma_{xy}$ are co-diagonalizable, i.e. the decomposition the author has should have both $\\Lambda_{xx}$ and $\\Lambda_{xy}$ diagonal. The introduction of spectral initialization in Section 2 is misleading to me because it is written in a way that suggests one can do spectral initialization for any linear regression problem. The author should clarify this. \n\n2. Spectral initialization alone is too restrictive to understand the training algorithm. In practice, such a spectral initialization scheme is rarely used to train a neural network (Note: an entirely different form of spectral initialization is used in matrix completion problem), and instead one uses mostly random initialization. In my opinion, spectral initialization allows us to somehow theoretically understand phenomena that happen during practical training. In that sense, analysis for spectral initialization alone is insufficient because we don’t know whether the phenomena observed in this paper, monotonicity of the product, backward learning, etc. also happen under non-spectral initialization.\nThe author discussed the relaxation of the spectral assumption at the end of page 4. but I find it unconvincing without empirical evidence.\n\n3. Following the point above, I think the author may want to add more experiments under non-spectral initialization to illustrate how should we understand these phenomena studied for spectral initialization. For example, monotonicity of the product can only happen for scalar dynamics, is there any related notion in the non-spectral case? Can backward learning happen under non-spectral initialization? Remember that the forward learning in Saxes’14 is observed empirically when weights are randomly initialized with small scale (non-spectral).\n\nAside from the concern on significance, I think the scalar dynamics in this paper can be understood better using visual tools. For the scalar dynamics (6), one can plot: 1) all the equilibrium points lie on the hyperbola $\\theta_1\\theta_2=\\lambda$; 2) the trajectory of the dynamics is constrained on the parabola $\\theta_2=\\frac{1}{2d}\\theta_1^2+K$, where $K$ depends on initialization. This makes some statements in the paper much easier to understand. For example, the flow function in (13) has three real roots if the parabola, determined by $d,K$, intersects with the hyperbola at three points. I believe the non-monotonicity of the product can also be illustrated.\n\nReference:\nAndrew M Saxe, James L Mcclelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural network. In International Conference on Learning Representations, 2014.", "summary_of_the_paper": "This paper studies the Feedback Alignment (FA) algorithm on deep linear networks. In continuous time, FA algorithm is an alternative to Gradient Flow (GF) In particular, to compute the time derivative of the weights, FA algorithm starts with the gradient of the weights at each layer, and replace the part that depends on the weights of succeeding layers by a fixed matrix.\n\nThe FA algorithm on deep linear networks under spectral initialization is studied regarding both convergence and implicit bias, and the analysis are provided for both continuous-time and discrete-time FA algorithm. ", "summary_of_the_review": "My initial rating is \"weak reject\" because:\nStrength: \n1. clear writing\n2. detailed analysis\n3. interesting observations\n\nWeakness:\n1. Significance, need connections to initialization schemes used in practice\n2. The results are hard to interpret in general non-spectral settings\n3. little numerical example\n4. presentation can be improved by visual tools", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0QlWk6EKjb", "reviewer": "Reviewer_eeMk", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper focuses on the theoretical analysis of FA. The authors find a setting (linear networks with diagonalizable matrices) to simplify the original problem to one-dimensional dynamics, then analyze the convergence rigorously. An interesting implicit anti-regularization is also observed under certain initialization. The numerical experiment, despite the simple setting, shows some advantages of FA compared to GD.\n\nI am not familiar with the related work about FA, but my main concern is that the one-dimensional dynamics may oversimplify the original problem; and for $L > 2$, the convergence is proved only for a special initialization.\n* Compared to GD, even for linear networks, the gap between (diagonalizable) one-dimensional scalar dynamics and high-dimensional matrix dynamics is non-trivial. May we get similar results as GD (given the FA dynamics seems to be simpler than GD)?\n* I tend to think that the implicit anti-regularization phenomenon is more like an interesting math problem under the special initialization. Do we observe the behavior in numerical experiments with commonly-used initialization?\n\nAs discussed in the last section, the ultimate goal of the theoretical analysis of FA is to prove its potential advantage over GD. I am afraid the current one-dimensional analysis is still far from filling this gap.", "summary_of_the_paper": "This paper theoretically analyzes the Feedback Alignment (FA, Eqn 2) algorithm in the optimization of deep linear networks.\n* Under the assumption that the data matrices, FA matrices and initial weight matrices can be diagonalized simultaneously, the optimization can be divided into several one-dimensional problems, and the paper proves the convergence of both continuous and discrete dynamics.\n* After the diagonalization, each eigenvalue corresponds to a one-dimensional dynamics. The authors construct two types of initialization to show that the convergence for the larger eigenvalues can be either faster (implicit regularization) or slower (implicit anti-regularization) than the smaller eigenvalues.\n* Numerical comparison between FA and GD with 2- and 3-layer linear networks and random initialization. FA converges faster than GD and shares similar implicit regularization behavior.", "summary_of_the_review": "This paper proves some theoretical optimization results about FA under some special settings, but I think the one-dimensional setting may oversimplify the original problem, thus the novelty may not be significant enough.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical analysis for the Feedback Alignment (FA) algorithm, an alternative to backpropagation for training deep linear neural networks. The main drawback of the analysis is that it assumes that the initial weight matrices are diagonal, which makes the dynamics of the algorithm reduce to K independent one-dimensional dynamic. Most of the reviewers feel that this assumption is too strong. Note that in many existing papers on the implicit bias/regularization of gradient descent (GD) for optimizing deep linear networks, they do not assume the initial weight matrices are diagonal. The authors provide some additional proof in appendix B during the rebuttal to try to relax the assumption on the diagonal initialization, but it is not critical clear if the same results still hold. While this paper studies a very important problem, I suggest the authors take into account the reviewers’ comments and improve the presentation/results. In addition, a comparison with the implicit bias of GD would help better position this work, as one of the reviewers suggested.
Decision: Reject