Gradient-free training of recurrent neural networks

Authors: Erik Lien Bolager, Ana Cukarska, Iryna Burak, Zahra Monfared, Felix Dietrich
Primary area: learning on time series and dynamical systems
Keywords: recurrent neural networks, koopman operator, random feature networks

Abstract:
Recurrent neural networks are a successful neural architecture for many time-dependent problems, including time series analysis, forecasting, and modeling of dynamical systems. Training such networks with backpropagation through time is a notoriously difficult problem because their loss gradients tend to explode or vanish. In this contribution, we introduce a computational approach to construct all weights and biases of a recurrent neural network without using gradient-based methods. The approach is based on a combination of random feature networks and Koopman operator theory for dynamical systems. The hidden parameters of a single recurrent block are sampled at random, while the outer weights are constructed using extended dynamic mode decomposition. This approach alleviates all problems with backpropagation commonly related to recurrent networks. The connection to Koopman operator theory also allows us to start using results in this area to analyze recurrent neural networks. In computational experiments on time series, forecasting for chaotic dynamical systems, and control problems, as well as on weather data, we observe that the training time and forecasting accuracy of the recurrent neural networks we construct are improved when compared to commonly used gradient-based methods.

Decision: reject
Reviewer scores: 5, 5, 6, 8

Reviews and discussion:
<thread>
creation date:
1730669534018

thread_type:
official_review

<thread_object>
creator: reviewer_bq2a

<content>
summary:
The MS explores an alternative method for fitting recurrent neural networks, based on Koopman operator theory.  A single-layer neural network with *random weights* is used to map the state (and possibly a control input) to a higher-dimensional space, in which the dynamics are assumed to be linear.  Since the state is assumed fully observed, the low-D state at consecutive time steps can be mapped to the high-D state, and the state matrix fit with the normal equations (and similarly for the input matrix when there is a control input).  The map back to the low-dimensional state and the output matrix can be found likewise.  The intuition from Koopman operator theory is that there exists a set, possibly infinite-dimensional, of measurement functions that evolve linearly in time.  The authors shows that this method yields computationally cheap and highly accurate models of simple nonlinear systems.

strengths:
The proposed approach fits simple nonlinear systems with high accuracy and very little computational time compared with using BPTT in RNNs.  This makes the approach a very appealing alternative for modeling and controlling such systems.  To my knowledge, the approach is novel (but see below), and open up a new perpective on random networks.

weaknesses:
From the point of view of implementation, the manuscript's random RNNs are a fairly minor variation on echo-state networks.  Indeed, there is a large literature on ESNs and reservoir computing, and I am surprised that this variation has not previously been explored.  Can the authors confirm this?

The introduction of Koopman operator theory does provide a nice intuition about why a linear dynamical system should exist in a higher-dimensional space.  But it seems that the trade-off it enables---linearity for higher dimension---limits the scope of application of this approach: As the authors note, the matrix inversion operation (in the normal equations) is expensive, and it is cubic precisely the dimension of the (large) measurement space.

My understanding of the theory is that, in general, not only is this space infinite-dimensional, but also there is no way to bound the number of required dimensions.  That is, M could be arbitrarily large.  Perhaps this is addressed in the proof in Appendix B, which I did not read closely.  Can the authors provide more insight here?

Finally, I found the paper somewhat hard to read.  This could be my fault, but there seem to be notational issues.  For example, near l. 139 the authors write h_t = F(h_{t-1}), and then later in the same paragraph, h_t' = F(h_t).  Is the idea that, in the first instance, h_t is the model state; where in the second instance, h_t is the *true* state (and therefore F(h_t) need not be equal to h_{t+1})?

questions:
The authors compare against ESNs on some problems and LSTM on others.  Is there any reason for these choices?

Can the authors provide more intuition about the weight initialization, i.e., Eq. 4 and the equation for the distribution p_H?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692364375

thread_type:
official_review

<thread_object>
creator: reviewer_vqoq

<content>
summary:
The authors propose a novel way to construct recurrent neural networks. Their approach is two stepped, where they first generates hidden weights and biases according to a data-dependent distribution, and then construct read-out parameters by approximating the dimensional Koopman operator with dynamic mode decomposition.

strengths:
Training recurrent neural networks is notoriously hard. I am partial to the authors approach of fitting an RNN to a a dynamical system by a smart sampling of hidden parameters and Koopman operator based modeling. Particularly, I am drawn to the use of Koopman operator in the context of RNNs. 

The paper is very well written and is a nice read, and the results comparing their gradient-free approach to trained models are impressive.

weaknesses:
It is unclear how much the Koopman operator and EDMD components contributed to model performance. Since the hidden weights initialisation schema is an application of previous work (Bolager et al. (2023)), I see the Koopman related work as the main conceptual innovation. However, based on the presented results it is hard to disentangle where improvements come from and I am not fully convinced of the added value of EDMD. I suggest the authors include two additional experiments: a. setting hidden weights randomly and learning read-out with EDMD and b. setting hidden weights based on Bolager et al. (2023) and learning read-out without EDMD. 

I am also not keen on the name and think it over-promises. Being able to train general recurrent neural networks without gradient descent or BPTT is an extremely ambitious goal, which this paper does not fulfils. As the authors explain in the (very much appreciated) limitation section, their approach does not immediately extend to RNN tasks relating to computer vision or NLP, thus the paper results are mostly regard dimensional dynamical system. I still believe their results are impressive, but the language, and specifically the title, needs to be toned down.

questions:
The impact of exploding and vanishing gradients is not made clear in this manuscript. I understand their model outperforms LSTMs and other, gradient based models based on numerical values. Could the authors make the impact of EVGP more apparent?

Can the authors include more real-world datasets? As of now, all but 1 result is simulated, and additional examples would significantly strengthen the manuscript.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721523227

thread_type:
official_review

<thread_object>
creator: reviewer_jk3b

<content>
summary:
This paper presents an alternative strategy to backpropagation through time (BPTT) by using a combination of Koopman operator theory and random feature networks instead of gradient-based techniques. This novel method avoids vanishing and exploding gradient problems, and outperforms BPTT in terms of training time and accuracy in a series of empirical comparisons, including time series, forecasting, control, and weather problems.

strengths:
1. Proof seems to be sound and theoretically correct given the assumptions stated by the authors, however i am not an very well versed with koopman operator theory and thus have provided a lower confidence score.
2. Their method (called sampled RNN) takes significantly less time to train than alternative state-of-the-art models such as ESNs, shPLRNNs, and LSTMs. Predictions from this model capture patterns in toy experiments as well as real-world data (like weather forecasting), and outperform current models (especially on problems with long horizons).

weaknesses:
1. There is little motivation for the problem in the introduction, and the paper jumps right into formalisms. 
2. The weights and biases need to be sampled from a data-dependent probability distribution, however it's unclear how feasible this is?
3. This method does not converge for controlled systems.

questions:
1. “For completeness we have added sigma_hx as an arbitrary activation function. We choose to set sigma_hx as the identity function to let us solve for the last linear layer… other activation functions such as the logit are possible as well”. However this is not shown in the paper. Can the authors provide clarification on the effect of non-linear activations here?
2. In the weather task, the sampled RNN has a similar MSE to shPLRNNs and LSTMs for 1-day forecasting, but higher than both alternative models for week-long forecasting. However, MSE is higher than ESNs for the Rosseler system task. Can the authors provide some clarification on this?
4. Can the authors provide clarifications/results on how performance for chaotic systems might change based on how many samples are drawn for the sampled RNN (and the influence on dimensionality of the hidden layer)? 
5. The authors state: “The complexity of solving this system depends cubically on the minimum number of neurons and the number of data points (respectively, time steps). This means if both the network and the number of data points grow together, the computational time and memory demands for training grow too quickly. For BPTT, the memory requirements are mostly because many gradients must be stored for one update pass”. — can the authors provide a comparison of # of neurons vs # of time steps?
6. Can the authors provide details on how they infer the “data-dependent probability distribution” (especially for the weather data)? 
5. Additionally, can the authors expand on how weights and biases are sampled from the specific, data-dependent probability distribution (again for weather data) and how other parameters are computed using a sequence of linear equations?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731495914354

thread_type:
official_review

<thread_object>
creator: reviewer_hnnr

<content>
summary:
-  The paper proposes a training method for modeling recurrent neural networks without the use of gradient-based methods, such as backpropagation through time (BPTT), which suffers from exploding and vanishing gradients, mostly occurring in a system with chaotic dynamics. Building on concepts from random feature models, such as reservoir computing (echo-state networks), the paper proposes the random sampling of weights (W­­­ and b) in the RNN from a data-driven distribution. In addition the paper employs Koopman operator theory to find the outer weights of the RNN model, which map the current state to the next state. The Koopman operator theory maps the finite nonlinear transformation matrices (outer weights) to a linear infinite-dimensional space, where the extended dynamic mode decomposition (EDMD) method is used to find a finite-dimensional approximation of the Koopman operator. 
-  For model validation, they show some computational experiments comprising simple ODEs, such as the Van Der Pol Oscillator, chaotic dynamics (Lorenz and Rossler systems), and real-world examples involving weather data.
- Paper reports results from these computational experiments in the form of training time and error (MSE/KL Divergence). When compared to other models, such as an LSTM, ESN (echo-state network), and shPLRNN (state of the art backpropagation-based RNN), the proposed model (Sampled-RNN) achieves comparable performance, in terms of MSE and KL Divergence, and a faster training time.

strengths:
- Interesting connection to Koopman operator.
- Interesting topic of trying to circumvent gradient based training.

weaknesses:
- Sampling procedure not clearly explained. (E.g. 'As we stick to networks with one hidden layer in this paper, we ignore the multilayer sampling here and direct the reader to Bolager et al. (2023) for the full sample and construction procedure for an arbitrary number of hidden layers.')
- Paper presentation generally not clear. Hard to follow. Illustrative example: equation 1 is referred to before presented. Paper requires excessive ‘detective work’ to understand what they did and/or are talking about.
- How sampling approach differs from ESNs seems unclear, and a minor innovation at best.
- Although interesting, connection to Koopman operator theory does not seem novel.

questions:
N/A
</content>
</thread_object>

</thread>


Metareview:
metareview:
In this work, the authors propose a gradient-free approach to training recurrent neural networks in low-dimensions. The proposed approach applies EDMD for output weight training to the sampling RNN framework of Bolager et al. (2023), bypassing backpropagation, and negating the exploding-vanishing gradient problem. Reviewers agreed that the manuscript is well-written, and that the approach is sound and yields good results. 

The more negative responses pointed out that the primary contribution was the incorporation of EDMD for the training procedure. The use of sampling strongly resembles ESNs, which can also be considered "gradient-free" in the same way as the proposed method. From this viewpoint, the new contribution pertains to a difference in architecture in the final layer, which requires the EDMD approach. This is not how the method is portrayed, however, as has been pointed out by reviewers. I disagree with this as a minor issue, or easily addressed by further experiments, as the exposition should be upfront about this, and the title not so broad to compensate. It is also strange that ESNs were not compared to in all settings. The authors commented on this in the discussion period, claiming that ESNs are best for chaotic systems, but if so, why not include them? Finally, I am surprised that reviewers did not critique the baselines, as I would not consider shPLRNNs, LSTMs or ESNs to be state of the art.

I am uncomfortable with recommending the paper for acceptance as-is, and would instead suggest that the authors think more deeply about the relationships between their proposed method and other existing approaches, including ESNs and the actual state-of-the-art, perhaps including other RNN approaches inspired by Koopman operators and DMD.