Real-Time Recurrent Learning: Training Dynamics

Learning online the parameters of a Recurrent Neural Network (RNN) holds the promise of offering better sample complexity when compared to offline algorithms such as Backpropagation Through Time. We benefit from the stable parametrization of the Linear Recurrent Unit, to study the training dynamics of the Real Time Recurrent Learning (RTRL) algorithm in the class of linear RNNs. We show empirically and justify theoretically that RTRL benefits from highly stochastic online updates. From the insights we develop in the linear setting, we then study it’s implications in highly sparse Continuous Time Recurrent Neural Networks were we observe similar results. Overall, our findings allow us to offer a possible explanation for the phenomena observed by other researchers when training highly sparse RNNs with RTRL.

1 Online vs Offline

Let’s start by introducing the notation we’ll use throughout this post. We define the transition function as $f \colon \Theta \times \mathcal{S} \times \mathcal{X} \to \mathcal{S}$, where $\Theta$ denotes a finite dimensional vector space where the parameters live, $\mathcal{S}$ denotes the same for the hidden states and $\mathcal{X}$ as well for the inputs to the RNN. A single sequence of inputs will be defined as $\mathbf{x}_{1:T} \coloneqq (x_1, x_2, \cdots, x_T)$ where $T$ denotes the end of the sequence. For when needed we define $f_{\theta} \coloneqq f(\theta, \cdot, \cdot)$ and to further declutter notation given a fixed input $x_t$ we define $f_{t} \coloneqq (\cdot, \cdot, x_t)$. For a fixed parameter $\theta$, given an initial condition $h_0$, the sequence of hidden states produced by the network can be recursively defined as:

Under this formalism an RNN can be considered a non-autonomous discrete dynamical system.

In what follows we focus on gradient-based learning where the objective is to minimize at each time step $t$, a cost function $\mathcal{L}_t \colon \Theta \to \mathbb{R}$ that measures the network's performance on a given task, as a function of the parameters $\theta$. Note that $t$ can be unbounded, but in this post we focus on the case where $t\leq T$. This allows us to define a cumulative loss function:

that will measure the overall performance of the network.

In the Sparse Jacobians post, we introduced two different algorithms to compute the gradient $\mathrm{d}_{\theta}\mathcal{L}$. Backpropagation Through Time (BPTT) and Real Time Recurrent Learning (RTRL). Both algorithms are equivalent, in the sense that they compute the same gradient $\mathrm{d}_{\theta}{\mathcal{L}}$, the difference however relies on how this gradient is computed. BPTT computes the cumulative loss gradient in two passes, a first forward pass where the inputs $x_t$ are processed, and a second backward pass where the gradients are computed. In contrast RTRL allows for comuting both in just a single pass, however this comes at a significant computational and memory cost as explained in the Sparse Jacobians post. More specifically RTRL computes each $\mathrm{d}_{\theta}\mathcal{L}_t$ explicitly as the network runs, whereas BPTT will only compute them implicitly. To better illustrate this difference we can derive the gradient equations for both methods:

after the exchange of summations in BPTT we are not computing $\mathrm{d}_{\theta}\mathcal{L}$ by adding each $\mathrm{d}_{\theta}{\mathcal{L}_t}$, but rather different terms. RTRL computes $\mathrm{d}_{\theta}\mathcal{L}$ by adding each $\mathrm{d}_{\theta}\mathcal{L}_t$ explicitly as we process the inputs.

Being able to obtain the gradient of the instantenous loss $\mathrm{d}_{\theta}\mathcal{L}_t$ as we process the inputs $x_t$ is the core feature of RTRL. It allows the update of the parameters $\theta$ in an online fashion, without having to neither accumulate the gradients nor wait until the sequence has been fully processed. This is what we refer as the online training setting, where numerous updates of the parameters $\theta$ are performed as we process the inputs, in contrast to the offline training setting in which only one update of the parameters its performed at the end. Throughout the rest of this post to remove unnecessary wording we will refer to RTRL with online updates as the online algorithm, and to BPTT as the offline algorithm. A single online update of the parameters while processing an input will be refered as an in-sequence update, to better emphasize its nature.

To make the difference more clear between both training settings, we can make explicit the dependence of the parameters $\theta$ on $t$. In the offline setting we are not performing any update as we run the network, therefore we have $\theta_t = \theta_1$ for $1 \leq t \leq T$, whereas in the online setting in general we have $\theta_i \neq \theta_j$ for $1\leq i < j \leq T$. We remark that this change of parameters as the network runs only happens while training, and when doing inference on a new input sequence the parameters are fixed for both methods¹.

Online updates of the network parameters can exhibit different training dynamics when compared to their counterpart. This difference arises by noting that while in the offline setting:

in online setting we have:

therefore, except for the first time step, in the online setting we are no longer computing the real Jacobian $\mathrm{d}_{\theta}h_t$ but a biased one, that will a priori better reflect the influence of the most recently used parameters $\{\theta_t, \theta_{t-1}, \theta_{t-2}, \dots \}$ in comparison to the initial ones $\{\theta_1, \theta_2\, \dots\}$. If we use gradient descent, this bias will imply that we are no longer following the precise negative gradient direction. The difference at each step is nevertheless $\mathcal{O}(\eta_t)$, so one can mitigate this bias by reducing the learning rate. The bias of the $\mathrm{d}_{\theta}h_t$ when using online updates, was indeed noted by the original authors of RTRL [1]:

While the resulting algorithm is no longer guaranteed to follow the gradient of total error, the practical differences are often slight, with the two versions becoming more nearly identical as the learning rate is made smaller.

By making $\eta_t$ small we are potentially aligning more closely to BPTT training dynamics. Even in this small learning rate regime formally analyzing the online algorithm becomes substantially challenging since standard stochastic gradient descent theory does not apply directly, and to this date we could only find one work where they proved local converge of RTRL when the network parameters start within a radius close enough to a local minima [2].

Local converge itself will not really tell us much about the qualitative differences on the training dynamics when the network has just been initialized with random parameters. It is the purpose of this post to try elucidate the qualitative differences, if any, that arise when using RTRL with online updates in comparison to BPTT. To the best of our knowledge no prior work has been done in this regard, and even though numerous studies have been done in either improving, or analyzing the performance of RTRL in different scenarios, as well as reducing its computational cost, we could not find any prior work in trying to uncover the qualitative differences that could potentially arise.

2 Teacher Student Analysis

2.1 Online EVGP

As argued in [3] if there is any hope of understanding Recurrent Neural Networks we first need to understand them in the special case where we remove the non-linearities. Albeit in principle this simplifies the analysis, removing the non-linearities however makes the online algorithm more prone to the exploding-vanishing gradient problem [4], when compared to the offline one. To see this, lets first define $J_t \coloneqq \mathrm{d}_{\theta}h_t\left(\theta_{t}\right)$, $D_t \coloneqq \frac{\delta f_t}{\delta h}\left(h_{t-1}\right)$, and $I_t \coloneqq \frac{\delta f_t}{\delta \theta}\left(\theta_{t}\right)$. Equation 3 can then be rewritten as:

unrolling the recurrence and starting with $J_0 = \mathbf{0}$, we can see that:

In the class of linear RNNs² and when using the offline algorithm the state-transition Jacobian becomes constant $D_t = W$, therefore by computing $J_t$ we are also computing $W^{t-1}$. This becomes an issue if the spectral radius³ $\rho(W)$ is strictly bigger than $1$ since the gradients are computed using $J_t$ and therefore as $t$ grows we enter the exploding gradient regime. This can be partially mitigated by ensuring that at initilization the randomly sampled $W$ satisfies the condition $\rho(W) \leq 1$, however an update of the weights could easily break this inequality.

Even though this is a big concern in both algorithms, note that in the online setting the state-transition Jacobian $D_t$ is not constant anymore, since we are updating $W$ at every time step $t$. With no non-linearity regulating the matrix products in $J_t$, a single bad in-sequence update could already set the RNN in the unstable regime. Therefore even in the linear setting, studying the dynamics of the online algorithm becomes more difficult. Recall that reducing the learning rate to smaller values in order to control the perturbation of an in-sequence update is ideally not what we are aiming for, since as mentioned before this will lead to training dynamics similar to BPPT. To further make progress in our study, we are going to take advantage of the Linear Recurrent Unit, recently introduced by [5].

2.2 Linear Recurrent Unit

Let $W \in \mathbb{R}^{k\times k}$ be the connectivity matrix of a linear RNN, $U \in \mathbb{R}^{k \times k}$ the input matrix, and $C\in \mathbb{R}^{d\times k}$ the readout matrix. Given $h_0$, and a sequence $\mathbf{x}$ the output $y_t$ is computed as:

this in fact is equivalent to computing the convolution:

note that diagonalizable matrices are dense in $\mathbb{R}^{k\times k}$ [6], therefore under a small perturbation of $W$ we can decompose it as $W = P \Lambda P^{-1}$, where $\Lambda = \text{diag}(\lambda_1, ..., \lambda_k) \in \mathbb{C}^{k \times k}$, and $P \in \mathbb{C}^{k \times k}$ is an invertible matrix. Left multiplying equation 5 by $P^{-1}$ on both sides, and letting $\tilde{C} \coloneqq CP$, $\tilde{B} \coloneqq P^{-1}B$, we obtain:

If the purpose of our study is to first understand the training dynamics of RTRL in the class of linear RNNs, we might as well train linear RNNs where instead of learning $\theta=(W, U, C)$, we learn $\theta=(\Lambda, \tilde{B}, \tilde{C})$⁴ and work with complex matrices. Expressiveness will not be lost in this parametrization, but it still does not ensure stable training dynamics and the EVGP remains a concern in both online and offline training settings.

Recently [5] took the previous approach one step further, and propose parametrizing the elements of $\Lambda$ as:

where it is the vectors $\mathbf{\nu} \in \mathbb{R}^{k}$ and $\mathbf{\theta} \in \mathbb{R}^{k}$ that will be learned during training. It is easy to see that under this parametrization starting with $\nu_j \geq 0$ for all $j$ guarantees $\rho(\Lambda) < 1$ at initialization. However post-update stability cannot be guaranteed since a $\nu_j$ can become negative. To address this, they introduced an additional positive non-linearity leaving the final parametrization as:

and now stability is ensured post-update. For learning long-range sequences where $\lambda_j \to 1$, the authors still noted a explosion in the forward pass. To see why⁵, assume a one dimensional network $\lambda \in \mathbb{C}$, and let $\tilde{B}=1$. Then under white-noise input $x_t$ we can see that:

therefore as $\lambda \to 1$ the forward pass explodes since the contribution from $x_j$ takes longer to decay. In order to address this issue they propose to normalize $\tilde{B}x_{t}$ by an element-wise factor $\gamma$ defined at initialization as $\gamma \coloneqq\sqrt{1 - \left|\lambda\right|^{2}}$.

Given the preceding normalization and the exponential parametrization of $\lambda$ (7) the Linear Recurrent Unit (LRU) is formally defined by [5] as:

where $\theta = (\lambda, B, C, D, \gamma)$. The LRU plays a significant role for our next studies as in-sequence updates will no longer break the stability of the linear RNNs. Furthermore as shown by [7], the diagonal nature of the connectivity matrix in the LRU allows for drastically reducing the computational and memory requirements induced by RTRL. This is due to the fact that complex neurons in the LRU do not affect each other and therefore tracking the sensitivities requires only $\mathcal{O}(|\theta|)$ storage, while updating the Jacobian $\mathrm{d}_{\theta}h_t$ gets reduced from a matrix multiplication to a dot product. For more details about the properties of the LRU and its online training algorithm the reader is encouraged to check the excellent work done by [5] and [7].

Having introduced the LRU and its benefits when used in combination with the RTRL algorithm, in the next section we will start studying its dynamics empirically in a teacher-student setting.

2.3 Sample Complexity Study

Our investigation begins with the question: Does the substantially higher update frequency of RTRL compared to BPTT provide any benefits in a Linear System Identification (LSI) task? Specifically, we aim to determine whether it results in improved performance or faster convergence.

Following [8], we will work under a teacher-student setting where the teacher is formally defined as:

with $h_t \in \mathbb{R}^n$, $x_t \in \mathbb{R}$ drawn i.i.d. from $\mathcal{N}(0,1)$, $A \in \mathbb{R}^{n \times n}$, $B \in \mathbb{R}^{n \times 1}$, $C \in \mathbb{R}^{1 \times n}$ and $D \in \mathbb{R}^{1 \times 1}$. The difficulty of the task its determined by the spectral radius of $A$, since given an input $x_{t-j}$ its contribution to $y_t$ is modulated by $\rho(A)^{j}$ as can be seen from equation 6. Thus bigger values of $\rho(A)$ will force the student to remember inputs from further back in time. Since this $\rho(A)$ is a parameter we want to control in our experiments, after sampling $A_{i,j} \overset{\mathrm{iid}}{\sim} \mathcal{N}(0, 1/n)$, we complex diagonalize it⁶, and then we apply the following transformation [8] to its spectrum:

note that this transformation ensures that $\nu_{\min} \leq |\lambda_i| \leq \nu_{\max}$. In case $A$ contained complex eigenvalues they must come in conjugate pairs. By using $\exp(\cdot)$ in the transformation and noting that $\exp(i\theta) ^{*} = \exp(-i\theta)$, the resulting matrix after the transformation is also real.

Controling $\nu_{min}$ and $\nu_{max}$ in the teacher is not enough for our purposes as we also need to control the spectrum of the student. The student will be a LRU, where its spectrum is controled by sampling $\lambda$ using lemma 3.2 from [5]:

Let $u_1, u_2$ be independent uniform random variables on the interval $[0, 1]$. Let $0 \leq r_{\text{min}} \leq r_{\text{max}} \leq 1$. Compute $\nu = -\frac{1}{2} \log \left( u_1\rho + r_{\text{min}}^2 \right)$, where $\rho = r_{\text{max}}^2 - r_{\text{min}}^2$ and $\theta = 2 \pi u_2$. Then $\exp(-\nu + i \theta)$ is uniformly distributed on the ring in $\mathbb{C}$ between circles of radii $r_{\text{min}}$ and $r_{\text{max}}$.

For the experiments the hidden size of the teacher is fixed to 10 and for the student 64. We will gradually increase $[r_{\min}, 1)$ and $[\nu_{\min}, 1)$ for the student and the teacher respectively. We choose a sequence size of $T=300$ to ensure that the input sequence is longer than the characteristic timescale we want to learn⁷. For every value $\nu_{\min}$, we train the student LRU with BPTT and RTRL under the same conditions with the same budget of samples, which varies from $\{1000, 5000, 20000, 500000\}$. We work under the purest version of SGD with batch size $1$. The loss $\mathcal{L}$ is the mean squared error over the prediction and the target sequence. To be fair with both algorithms and since gradient descent optimization is highly dependent on the learning rate, we sweep over 15 learning rates starting from $0.01$ and decreasing logarithmically. For the optimization algorithm we use Adam [9] with its default hyperparameters in combination with cosine annealing without warm restarts⁸. When the best evaluation loss is found at one of the extremes of the allocated learning rates, we manually finetune it until the best learning rate does not live in the extremes. We repeat everything for $4$ different seeds. The grid search is done using Ray Tune [10], and we use the framework introduced in the Sparse Jacobians post for implementing RTRL, where we conducted unit tests in all the optimization algorithms to ensure their correctness. Details of all the hyperparameters that we sweep over can be found in table 1.

Intuitively to correctly explore the parameter space $\Theta$ for learning long-range dependencies, we want the $\mathrm{d}_{\theta}h_t$ to not be biased. This is ensured in BPPT, as there are no in-sequence updates. However for RTRL this term does not actually reflect the influence of the parameters at the beginning of the sequence. Since $\theta_0$ has had an influence in $h_{t-k}$ and $h_{t-k}$ in turn influences $h_t$ as well, if the loss $\mathcal{L}$ at time step $t$ is highly dependent in the state of $h_{t-k}$, we should take into account the $\theta_0$ that leads $h_0$ to $h_{t-k}$ as well.

By allowing online updates we are not really tracking the real influence over all time steps. For tasks with short-time scale as measured by the spectral radius of the teacher, we should expect that the significantly higher number of updates of RTRL help converging faster towards a smaller loss. This advantage however should be lost as we give more sample budget both BPTT and RTRL, and the spectral radius of the teacher increases as well.

Results of the empirical sample complexity experiment for LSI can be seen in figure 1. The results align with our intuition as the performance of RTRL outperforms BPPT only on small values of $\nu_{\min}$ and when the budget of samples is small. Eventually the differences vanish and BPTT catches up in performance. For bigger values of $\nu_{\min}$, RTRL does not present any advantage and when the budget is increased towards $50000$ performs an order of magnitude worse than BPTT.

3 Benefits of Noisy In-Sequence Updates

Recall that in the previous experiment we used Adam with its default hyperparameters as our optimizer. Lets take a closer look at the update function defined by Adam⁹:

Adam defines three¹⁰ hyperparameters $\beta_1$, $\beta_2$ and $\eta$ that are left for the experimenter to tune. Intuitively $\beta_1$ controls the exponential moving average of the gradients, since as $\beta_1 \to 1$ greater smoothing is performing and more weight is given to the average gradient $m_t$. One will expect that for learning a long-range task, if we are performing in-sequence updates, we want to give more importance to the average gradient $m_t$, the intuition for this is that since in the online setting the parameters now define a in-sequence trajectory $\theta_{1:T}$, the update directions from the instantaneous loss gradients $\mathrm{d}_{\theta}{\mathcal{L}_t}$ do not necessarily need to be aligned¹¹. This leads the trajectory to fluctuate significantly, which we control using $\beta_1$ with Adam. The interpretation that $\beta_1$ controls these fluctuations of the gradients, can be easily checked by tracking the updates $\mathcal{U}(\beta_1, \eta, \mathrm{d}_{\lambda}\mathcal{L}_t)$¹² given by Adam to the eigenvalues, as we do in Figure 2.

Whether reducing this fluctuations is beneficial for RTRL, as we presuppose, is what we discuss next.

Contrary to our intuition the closer $\beta_1 \to 0$ the better RTRL performs, even in the harder task of our previous experiment where $\nu_{\min} = 0.99$. In figure 3, we can see a sweep over different values of $\beta_1$, where for each $\beta_1$, we follow a similar grid search procedure as in the previous study, ensuring that for every $\beta_1$ we find the best configuration, ensuring a fair comparison. The best mean performance its achieved with $\beta_1 = 0.0$ i.e no smoothing at all over the in-sequence gradients, and even more surprising, it is achieved with the maximum initial learning rate $\eta$ when compared to best performant learning rates in the other $\beta_1$ scenarios.

In order to get more insights we start by analyzing the backward sensitivity of the system, which we define as:

where the norm is the spectral norm i.e the largest singular value. Intuitively this term measures how sensitive the final hidden state $h_T$ is to a perturbation of a hidden state in a distant past $t$. For tasks with long-range dependencies we want this term to increase during training in case it is small at time steps the task cares about.

Note that in the LRU, the state-transition Jacobian is constant $\mathrm{d}_{h_{t-1}}h_{t} = \operatorname{diag}(\lambda)$, and because the spectral norm of a diagonal matrix its equal to its spectral radius we have that $t \mapsto \left|\lambda_{\max}\right|^{T-t}$. So function 11 its completely characterized by the spectral radius of $\text{diag}(\lambda)$, which allows us to study it with just a single scalar. Therefore we track the $\max$ eigenvalue after every iteration of both RTRL and BPTT, as well as tracking the $\min$ eigenvalue and then mean of $\left|\lambda_j\right|$. We do this in a setup where the student starts with a spectrum in $[0, 1)$, so that we recover Glorot initialization [11]. The teacher will be set to the hardest difficulty where $\nu_{\min} = 0.99$, in addition to $\left|\lambda_{\max}\right|$. For both algorithms we follow the same grid search procedure as in the previous study in order to compare them in their best performing settings. Since we want to better understand the observation from figure 3, in RTRL we check for $\beta_1=0$ and $\beta_1 = 0.9$, whereas in BPTT we only check for $\beta_1=0.9$. Note that in the class of Liner RNNs, as mentioned before, the state-transition Jacobian is constant¹³ and is equal to the connectivity matrix, therefore we should expect in both settings that the spectral radius of $\text{diag}(\lambda)$ increases towards higher values, closer to where the spectral radius of the teacher is. Otherwise they could not learn the long-range dependencies.

In figure 4 we can see the evolution of the quantities just described. From the plots we note three qualitative differences when considering noisy in-sequence updates ($\beta_1 = 0.0$) in comparison to BPTT and smoother in-sequence updates ($\beta_1 = 0.9$) in RTRL:

1. The spectral radius converges faster towards its theoretical limit¹⁴.

2. The norm of the minimum eigenvalue converges faster towards 0.

3. Overall the norm of the eigenvalues of the state-transition Jacobian tend to converge faster towards higher values.

in order to better comprenhend this empirical observations, in the next subsection we will argue for a simple toy model that we believe explains the previous qualitative differences.

3.1 RTRL Toy Model

To understand the qualitative phenomena of the previous study we start by recalling the LRU parametrization¹⁵:

where $\mathbf{\nu} \in R^{n}$ and $\mathbf{\theta} \in R^{n}$. Since the quantity we are interested is the norm of $\lambda_j$, to simplify the analysis we set $\theta = \vec{0}$ as it does not contribute¹⁶ to the norm. Therefore the parametrization we study is left as:

and the in-sequence update equations¹⁷ when performing gradient descent follow:

Define $e_t \coloneqq \eta \frac{\mathrm{d} L_t}{\mathrm{d} h_t} \frac{\mathrm{d} h_t}{\mathrm{d} \lambda}$, and note that $-\frac{\mathrm{d} \lambda}{\mathrm{d} \nu} = \exp(\nu_{t} - \exp(\nu_{t}))$, hereby equation 13 becomes:

we can treat 15 as a non-autonomous discrete dynamical system, since $e_t$ will be varying at each time step $t$. Even though an oversimplification, is still worth assuming constant $e_t$, so that we can treat 15 as an autonomous dynamical system, where the analysis becomes easier. In the one-dimensional setting the direction of $e_t$ is either a positive one $(+1)$ or negative $(-1)$, so assuming $\left|e_k\right| = 1$, we can plot the dynamics of the system in a Cobweb diagram (Figure 5) together with the LRU parametrization. From the plots it is clear that:

Of course during optimization neither $e_t$ will be constant nor $|e_t| \neq 1$. The term $e_t$ will be regulated by the learning rate $\eta$, and the directions will differ during the in-sequence updates. In RTRL $e_t$ fluctuates significantly during the forward pass (Figure 2), and this fluctuation can be controlled by $\beta_1$ when using Adam.

Assuming, as previously argued, that $e_t$ fluctuates significantly, let's replace $e_t$ by a random variable $\varepsilon_t \sim \mathcal{N}(0, \sigma^{2})$. The fluctuation is now governed by $\sigma$. Consider a Markovian random walk in $\mathbb{R}$. With sufficient iterations, the larger the $\sigma$ the quicker the random walk reaches its first-passage time for a given threshold. Recalling that in RTRL we perform $T$ additional updates to $\lambda$ compared to BPTT, the previous analysis suggests that under in-sequence updates, convergence towards either 0 or 1 occurs more rapidly in the LRU, even if these updates exhibit considerable fluctuation. In fact larger fluctuations, as in the random walk, imply earlier first-passage times over values of $\nu_t$ that result in closer values of $\lambda_t$ to the two poles. We can see now that as $\beta_1 \to 0$, the effective $\sigma$ increases, leading to a faster increase in the spectral radius while training, thereby enhancing performance in the harder task where $\nu_{\min}=0.99$, which is what we see in figure 4.

In figure 6 we confirm our analysis, where we sample a white noise sequence from $\mathcal{N}(0, \sigma^2)$ to play the role of $e_t$ and we track the evolution of $g(\nu_{t}, e_{t})$, where $\lambda_0 = 0.5$, for different values of $\sigma$. As we can appreciate from the figure, the largest value of $\sigma$ results in faster convergence towards the two poles, 0 and 1, but eventually for every value of $\sigma$ convergence to the poles should occur given enough iterations. We repeat the analysis for $10^3$ white noise sequences, each of them of length $T=10^4$, and in figure 6 we show their distribution at different time steps, for different values of $\sigma$. The higher density around 0 in the histogram at 10K can be explained by noting that:

which implies that converge happens in fewer iterations towards 0 than towards 1, biasing the distribution in this simplified RTRL toy model for the LRU.

From the previous analysis we can already start to understand the qualitative differences we observed in the LSI study between the different $\beta_1$ scenarios and BPTT. If $\beta_1 \to 0$ the $\left|\lambda_j\right|$ of the LRU should show convergence towards a bimodal distribution in 0 and 1, which in turn will increase the spectral radius. This is what we indeed observe in figure 7, when we track the trajectories of the $\left|\lambda_j\right|$ during training of the LSI task. Only one seed is displayed for making the visualization easier, nevertheless to strengthen our hypothesis about the qualitative differences between RTRL and BPTT, in figure 8 we plot the complementary cumulative distribution function ¹⁸ $\Pr(|\lambda| > x)$ (CCDF) at the end of training, now computed among the different seeds for both RTRL and BPTT.

Note that the $1 - F(x)$ displayed in figure 8 is computed at the last iteration of training, nevertheless given the big gap between BPTT in RTRL it suggests the following. For sufficiently big $N$, there exists a threshold $\alpha$ such that for all $n \geq N$:

where with $B$ we denote BPTT and with $R$ we denote RTRL. We cannot offer a proof for this, but nevertheless, we give support for this claim in figure 9, where we show CCDF for both methods while training from the first iteration until iteration 1000, the upper bound on 1 its given by the stable parametrization of the LRU. How small can this $N$ be, we believe will become relevant when we study non-linear RNN's in the next section.

Interpreting $e_t$ as $\varepsilon_t$ wast partly motivated by figure 2, where we verified, albeit in a simplistic setting, that the updates provided by Adam i.e $\mathcal{U}(\beta_1, \eta, \mathrm{d}_{\nu}\mathcal{L}_t)$, were highly stochastic in nature. The cautious reader must have noted that our definition of $e_t$ in the toy model, doest not equate exactly to our LSI experiments are being performed. To see why note that when using Adam, the actual update equations for $\nu$ follow $\nu_{t+1} = \nu_{t} + \mathcal{U} (\beta_1, \beta_2, \eta, \mathrm{d}_{\theta}\mathcal{L}_t)$ therefore:

to further strength our observations and justify our interpretation of $e_t$ we need to decompose $\mathcal{U}(\cdot)$ into the two terms, $e'_t$ and $\mathrm{d}_{\nu}\lambda$ so that:

which matches the same equation as in 15, note that in the LRU $\nu$ is a vector in $\mathbb{C}^{k}$ and $\lambda$ as well, therefore to solve for $e'_t$, we could right multiply both sides by the inverse matrix $(\mathrm{d}_{\nu}\lambda)^{-1}$. The inverse is guaranteed to exist since the matrix $\mathrm{d}_{\nu}\lambda$ is diagonal¹⁹. If our interpretation of RTRL and the influence of $\beta_1$ is a valid one, then we must see as well that when computing the element-wise $\operatorname{Var}[e']_n$ (using as observations all the time steps during an input sequence $\mathbf{x}$ given at iteration $n$) ²⁰, for different values of $\beta_1$ the variances must satisfy²¹:

Recall that $e'_t$ is a vector with elements in $\mathbb{C}$ therefore we use the following definition of variance for a complex random variable:

In figure 10 we can see these values computed using 4 different seeds where we used the same initial learning rate $\eta$. Note that they closely match our interpretation of $e_t$.

Overall the previous experiments further validate the use of our toy model for RTRL, when trying to study its dynamics. Though it may sound simple, to the best of our knowledge we have not seen any study in the literature following our approach. This might partially be because of timing, since the LRU which is a key component in our study has only been introduced recently. We conclude this section by reminding the reader that we started studying RTRL in class of linear RNNs, with the hope of giving us a better understanding of its training dynamics in the non-linear setting. In the next section we start to study RTRL in non-linear RNNs.

4 Implications In Sparse Networks

Recently [12] showed the advantage of imposing sparsity in the parameters of the network by proposing a biased approximation to $\mathrm{d}_{\theta}{h_t}$ which reduces the memory and computational complexity of RTRL, as explained in the Sparse Jacobians post. Their experiments conclude that training highly sparse RNNs (GRU and LSTM) with RTRL outperforms BPTT when learning a curricular copy task. Studying RTRL in RNNs with gated mechanisms to understand this phenomena. Is out of the scope of this thesis and left for future work, here instead we focus on Continuous Time Recurrent Neural Networks (CTRNN), using some of the insights derived from the previous section in Linear RNNs.

Following [13] the class of CTRNN considered here are derived from the discretization of the following continuous-time dynamical system:

where $\varphi \coloneqq \tanh$, $N$ represents the number of hidden units, $N_{\text{in}}$ the number of input channels, $W \in \mathbb{R}^{N \times N}$, and $U = [\mathbf{u}_1, \cdots, \mathbf{u}_{N_{\text{in}}}] \in \mathbb{R}^{N \times N_{\text{in}}}$. The readouts of the network are computed by:

where $N_{\text{out}}$ represents the number of output channels and $\mathbf{c}_i \in \mathbb{R}^{N}$. Similar to [13] we are interested in the training dynamics of networks where $N \gg 1$ and the dimensions of $N_{\text{in}}$, and $N_{\text{out}}$ are small. However we depart from their setup by forcing sparsity in the connectivity matrix $W$ in an attempt to understand the results from [12]. We do this by sampling a random binary matrix $M_{s}$ with $\mathrm{i.i.d}$ entries $M_{i,j}\sim \mathrm{Bernoulli}\left(1 - s\right)$, where $s$ will control the amount of sparsity imposed in the connectivity matrix. The transformation to $W$ is simply:

The first insight to understand [12] comes from the following fact. Define $W' \coloneqq M_{s} \odot W$, if the entries $W_{i,j} \overset{\mathrm{iid}}{\sim} \mathcal{N}(0, 1/N)$ then:

since $\mathbb{E}[W'] = 0$ and $E[|W'|^4] \leq C$, then²² by Bai and Yin [14], we have that:

and by reverse Fatou's Lemma:

which basically tells us that for $N\gg 1$ (as in our setting and the one in [12]), under Glorot initialization of the connectivity matrix $W$, imposing a random mask on the weights to induce sparsity, effectively decreases its spectral radius. This behavior is illustrated in Figure 11. In the regime of linear RNNs, as discussed in the previous section, RTRL should escape this small spectral radius faster than BPTT. As a result, this could potentially enhance performance when the objective is to learn long-range dependencies, which is what [12] observed in their experiments although in highly sparse gated RNN's.

To test the hypothesis that RTRL outperforms BPTT when training highly sparse CTRNN we will follow a similar approach as in the preceding section were now we substitute the LSI task, with the Romo [15] task. The task is a delayed-discrimination task, where the network is presented with two positive pulses of different amplitudes separated by a delay. Following an additional delay, the network is required to remember which of the two pulses had greater amplitude. We choose this task as it is a simple one to start studying RTRL and we can easily control the specific time steps $t$ at which the network has received its inputs and has to start recalling the largest pulse.

As in all of our previous experiments to compare BPTT and RTRL in their best performing settings, we follow a similar grid search as in the sample complexity study. For RTRL we set $\beta_1 = 0$ in light of the previous section and for BPTT we set $\beta_1 = 0.9$. The sparsity of the network is imposed by sampling a random binary mask as explained before were we set $s$ to 0.98. For the size of the hidden units we choose $N=256$ following [13] and also to obtain the upper bound in 23. For discretizing 20 we choose as $\mathrm{d}t = 0.3$. The evaluation loss is the mean squared error over the readouts of the network. The number of iterations for both RTRL and BPTT is set 50K. Similar to the LSI task we set the batch size to 1. In figure 12 we can see the evaluation loss curves for both methods in their best performint setting. Clearly RTRL outperforms BPTT. This partial result strengthen our hypothesis about the advantages of RTRL in highly sparse CTRNNs. In figure 13 we can also see how the spectral radius converges substantially faster to a bigger value in RTRL²³. We have run control experiments where after sampling the random sparse connectivity matrix, we scale it so that we start in both algorithms with $\rho(W') = 1$, and the result in terms of performance were almost the same, with RTRL clearly outperforming BPTT. Therefore there has to be some other qualitative phenomena explaining the gap in performance.

Note that in the non-linear regime, the spectral radius is not a good indicative anymore of how the network is learning, in the case of the LRU we studied that term since as commented before, the backward sensitivity function can be fully characterized by a single scalar. This is not true in the case of non-linear RNN's. The state-transition Jacobian of CTRNN after discretization is not constant anymore and follows:

In an attempt to understand the difference in performance between both methods we recall the following standard result in the theory of continuous-time dynamical systems. Assume we have an ODE, defined as:

where $h \in R^{N}$ and represents the hidden states of a non-linear RNN. We can differentiate equation 25 from both sides with respect to $h_0$ and after an exchange of derivatives²⁴ we get the following equation:

note that $\frac{\delta h_t}{\delta h_0}$ its closely related to the function 11 we were studying in the previous section, were instead the role of the time variable $t$ is inverted. Intuitively $\frac{\delta h_t}{\delta h_0}$ measures how sensitive is $h_t$ with respect to a perturbation to the initial condition $h_0$. Following [16] lets define as well $A(t) \coloneqq \frac{\delta h_t}{\delta h_0}$, equation 26, can be rewritten then as an ODE following:

where $A(0) = I$. Similar to [16] we are going to make the assumption that $J(t)$ is constant, although a strong assumption its going to help us understand the qualitative differences of RTRL when compared to BPTT, at least in the Romo task. The strong assumption, thus allows us to get the solution for the ODE at 27:

assuming that $J$ is diagonalizable we then get:

where $\Lambda(J)$ denotes the eigenvalues of $J$. Using the fact that the trace bounds the spectral norm, we have then:

combining this lower bound, with the results from figure 9 (where we showed empirically that early in training of a LRU, RTRL has much higher probability than BPTT of $P(\left|\lambda\right| > x)$ for bigger values of $x$), we can see that RTRL also early in training will increase the trace in 30 since:

and as $t$ grows this term will be dominated by the $\lambda_j$ with highest absolute value, which is precisely what RTRL increases from what we observed in the previous experiments. Therefore RTRL will push the lower bound in 30 to higher values, biasing as well the spectral norm of the forward sensitivity towards higher values when compared to BPTT early in training, which is needed to in order to start learning distant dependencies in a sequence [4]. Note that we have made strong assumptions in the previous derivation, which don't necessarily have to match the real experimental setting. In what follows we study what we have just argued.

In light of the previous experiments and from 23 we hypothesize that RTRL bias Highly Sparse CTRNNs to two regimes during training, the first one, suggested by 30, where the network tries to memorize as much as possible, and then learns to forget the irrelevant inputs for the task at hand. Actually we hypothesize that both BPTT and RTRL use the same strategy since the spectral radius of the network at initialization its quite small, but RTRL will enter the regime of memorizing much faster.

To study this hypothesis we follow a similar approach as in the previous section. As a reminder, we want to analyze:

For every new input sequence this function changes, therefore we are not interested in the absolute magnitudes of 32 within a sequence, we are interested in their relative values within a sequence. For example, we could be interested in comparing the value at a fixed time step $t$ but at different iterations of the training algorithm say $n_1 < n_2$. At iteration $n_1$ the $\mathrm{d}_{h_{t}}h_{T}^{n_1}$ could be much smaller in norm than $\mathrm{d}_{h_{t}}h_{T}^{n_2}$ at $n_2$. However that does not indicate that network its less sensitive to a perturbation in $h_t$ at iteration $n_1$, as it could be that the $\mathrm{d}_{h_{t}}h_{T}^{n_1}$ its the biggest value in norm within its sequence indicating the contrary. Therefore if not normalizing this quantity we cannot compare them in fair manner during training at different iterations. For this reason the actual term we track is the following one. Define $c_n \coloneqq \max_{0\leq t \leq T} \left\lVert \frac{\partial h_{T}^{n}}{\partial h_{t}}\right\rVert$ for iteration $n$ of the algorithm, the quantity we track can be defined then as:

this quantity is bounded in $[0, 1]$ therefore we could also integrate it, and track as well:

so that we can display in a simple way the evolution of the overall backward sensitivity of the algorithms. In figure 14 we can see 33 for a single seed and for only one input sequence at different number of iterations during training, already supporting our intuition about RTRL increasing norm of the backward sensitivity faster early in training. In figure 15 we can see 34, which gives even more support to the hypothesis that RTRL converges faster to a bigger value of 34, and then decreases this term faster as well compared to BPTT. We find interesting that even though their respective evaluation losses follow similar trends at the beginning of training, there exists a qualitative difference hidden in the dynamics of 34.

We conclude this short section and the post by remarking that our study although small in nature, offers an possible explanation for the results obtained in [12]. RTRL benefits from highly stochastic in-sequence updates, and it benefits even more when the network is highly sparse, as we showed experimentally and motivated theoretically. We also posit a potential negative consequence: the tendency of RTRL to push the spectral norm of the backward sensitivity towards higher values may impair its performance in denoising tasks. Gated RNNs mitigate this issue through their gating mechanisms. Future work will explore this potential phenomenon in greater detail and attempt to generalize our findings to other tasks inspired by the neuroscience literature. The research in [12] play a significant role in the development of this post as we were quite intrigued by their results in networks where we the sparsity was close to 98%