Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers the problem of training recurrent neural networks (RNNs) using an online bilevel optimization (OBLO). This allows to consider the problem as a meta-learning-like problem with streaming data, and obtain a new family of RNNs, dubbed as meta-RNN. The OBLO formulation is derived leading to two optimization problems that are solved interleaved. The first and inner stage is an inference step for the network (i.e., a forward pass) computes the hidden state out of the current network. Three versions are proposed to solve it based on stochastic gradient methods: SGD, SHB, and SNAG. Then, the convergence of these methods for this inner optimization task is analyzed theoretically to show the training stability in this inner optimization task. The second optimization aims to update the meta-RNN weights and hyperparameters. Last, the method is compared to several other RNN methods on four tasks: adding task, sequential MNIST and its permuted version, and HAR-2 (time series for activity recognition).

main_review: The idea of looking at meta-learning with OBLO as an RNN is novel to me. The idea seems interesting. The paper cites a long list of papers. While doing an extensive review of related work is welcomed, it is always nice to explain how the current work differentiates from each one of these. In some cases, one may find that some of these works may not need to be cited or their detailed summary relegated to the supplementary material while using the space for the own technical aspects of this work.

The submission seems mostly technically sound. There are a few details that are unclear or seem missing. I would appreciate if the authors can respond to my questions below on these and other matters. The theoretical part of the paper is welcomed, however it is common to refer to the gradients of the weight updates (2 stage) for training stability of RNNs. Moreover, the main paper does not discuss the details of solving the network parameters stage. Another welcomed aspect is the extensive comparison against other methods in the experimental section. On the other hand, the authors forgot to discuss how to apply the model after trained to new (e.g., test) sequences, like those in the test sets in the experimental section. Regarding your deep-RNN limitation, you may find some inspiration in [1]. 

The paper seems nicely written and well organized. In general, the work is simple to understand. However, there some clarity details missing in the text that could improve the readability and reproducibility of this work. It is slightly confusing to go from RNN to meta-learning and back to meta-RNN in the introduction. Also, its motivation could be improved as well (what problem are we solving?). Referring to the parameters of the network with $\theta$ as the hyperparameters (for meta-learning) was confusing. There are some details described above that are missing (e.g., applying trained model to new sequences, solving the other optimization task, theorem assumptions met).

The methods presented in this work are relevant to the NeurIPS community. However, the potential value of this work seems small in my opinion. The missing details and the several limitations of this work are behind my score. I would be happy to reconsider my score if the authors could address my concerns.

Questions for the authors:
1. In Eq. (1), the RNN learning problem is defined as a constrained optimization problem. However, the constrain depends on $x$, which is part of the input distribution and changes with each input. It is unclear to me why this can be done. I would appreciate if the authors include the derivation that shows how they arrive to (1) from training. 
2. Could you comment whether the conditions of the Theorems 1 and 2 are met after updating the network weights for your choice of $F$? How can one make sure that the method remains stable over batches? It would be very valuable to discuss this in the main paper. 
3. How well does an LSTM perform in the HAR-2 10% and 1% of training data problem? (of similar hidden size and with a similar number of parameters.
4. How does your meta-RNN deal with problems that need to output sequences instead of a single prediction?
5. Both in training and testing(inference) time, what is the computational complexity (runtime and memory) of your method? How does it compare to training an RNN/LSTM  with SGD?

Minor:
* Please, consider removing the legend from inside the plots in Figure 4 to having it one time outside the plots. 
* Consider increasing font size in plots.

References

[1] Turek et al., Approximating Stacked and Bidirectional Recurrent Architectures with the Delayed Recurrent Neural Network, ICML 2020.
limitations_and_societal_impact: One important limitation that hasn't been addressed or mentioned by the authors is the fact that sequences can have variable length. This is very common in natural language for example. Another limitations not addressed is solving tasks that require sequential outputs.

Other limitations and societal impact have been mentioned to the best of my understanding.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposes a formulation of RNNs which allow practitioners to train RNNs using bilevel optimization algorithms. This is a novel perspective of RNNs.

The authors claim that their formulation of RNNs as an optimization process and their approach of training RNNs by solving a bilevel optimization problem prevents the problems of gradient vanishing/exploding. The authors demonstrate their methods on small datasets such as Pixel MNIST, Permutation MNIST, and HAR-2 (a dataset from phone accelerometer/gyroscope for activity recognition).

main_review: The paper provides an interesting and novel perspective of RNNs. I will first summarize the method. Let $h_t$ be an RNN’s state at time step $t$, then the standard forward propagation of RNNs would set $h_t = f(h_{t-1}, \theta)$ where $f$ is the parameterized function of the RNNs (such as an LSTM). Now, instead of enforcing the equality $h_t = f(h_{t-1}, \theta)$, this paper treats $h_t$ as a *free* parameter that should minimize the difference $|| h_t - f(h_{t-1}, \theta) || $. Under this formulation, the forward pass of an RNN can be treated as an optimization problem. This paper considers this optimization problem to be an inner loop of a bilevel optimization problem. Now, the entire RNN is supposed to minimize an objective function – for instance, predicting the correct MNIST pixel at each step. This objective function can be treated as an outer loop of the RNN’s bilevel optimization problem. This resulting bilevel optimization problem removes the recursive dependency of each $h_t$ on $h_{<t}$, and hence effectively avoids the RNN’s gradients from vanishing/exploding.

I personally find this bilevel optimization perspective of RNNs fascinating, novel, and interesting. In addition to this interesting formulation, the authors also derive an efficient analytical formula to iteratively solve their bilevel optimization problem using gradient-based updates (Equation 10-11). The authors also demonstrate that their meta-RNNs can be trained effectively to perform well on some small RNN tasks, namely Pixel-MNIST, Permuted-MNIST, and HAR-2.

While I like the perspective of this paper very much, I believe the following discussions and analysis should be included, in order for meta-RNNs to become useful:

1. Experiments on larger, more “real” situations such as large language models, should be conducted. There is also the Long-range Arena challenge, which measures how well RNNs can learn on long sequences. The authors can consider trying meta-RNNs on that challenge too.

2. Bilevel optimization is slow and finicky. The authors should compare the training time of meta-RNNs with other baselines. Table 2 does report the training time of meta-RNNs, but I cannot find any comparison of meta-RNNs’s training time and other methods. The comparison should be in controlled environments, e.g. on the same devices.

3. RNNs are no longer the state-of-the-art in sequence modeling. That title belongs to the Transformer model now. Can meta-RNNs achieve the same performance with Transformer? What are the pros and cons in comparison?

Overall, despite the novel perspective that this paper describes, I wish the authors had added larger and more “real” experiments to attest to the strengths of their model and method. Therefore, I am not certain whether this paper should be accepted or rejected.

limitations_and_societal_impact: Interesting novel perspective. Little to no practical impact for the present.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper formulates the problem of RNN training as a bilevel optimization problem in which the outer optimization is over the RNN parameters and the inner optimization is over the RNN activations. The authors prove upper bounds on the hidden feature distance of similar inputs. Moreover, the authors prove bounds on the inner optimization rate to guarantee training stability. Finally, the authors empirically find that their RNN formulation requires fewer parameters, less training data and converges faster than competing RNN formulations on benchmark problems.
main_review: **Originality**
This paper appears similar to prior works that view RNN hidden states as equilibrium points of a dynamical system (as noted by the authors in section 2). In this paper, the dynamical system over hidden states is itself an optimization. However, this contribution does not seem particularly novel since in prior work like iRNN, the dynamics of hidden states can also be viewed as an optimization (in which equilibrium points represent local minima of the lower-level optimization problem).

**Quality**
The theoretical claims appear correct and provide some justification for using meta-RNN, although it is not clear whether the results are specific to meta-RNN or whether similar results could be shown for standard RNNs.

The authors compare meta-RNN to several baselines. Unfortunately, the experimental results do not convincingly show that meta-RNN requires fewer parameters and less training data than baselines. Firstly, in Figure 5, meta-RNN-dense appears to require a similar number of parameters as baselines. Meta-RNN-sparse requires fewer parameters, but this does not appear to be a fair comparison with other dense methods such as regular RNN. A fair comparison would compare meta-RNN-sparse with sparse versions of baselines.

Moreover, the claim that meta-RNN requires less training data than baselines is not well supported by Figure 4. It appears that meta-RNN performs better than baselines in general for both the 1% and 10% training data settings on HAR-2. There doesn't appear to be evidence that meta-RNN is better than baselines *particularly* when training data is limited. This is partly because training curves for the full HAR-2 training data sets are not presented.

Finally, the datasets appear relatively simple. Conducting experiments on more challenging datasets would significantly improve this work.

In summary, the experiments could be further improved as follows:
1) Compare with sparse versions of baselines
2) Show that meta-RNN performs relatively better than baselines in regimes with low training data (vs. high training data)
3) Conduct experiments on more challenging datasets.


**Clarity**
The framing of the method in this paper as a type of meta-learning is slightly confusing since meta-learning typically refers to settings where a shared set of meta-parameters are found over several related datasets or tasks. In this paper, the shared set of meta-parameters correspond to a single task, which makes it unclear initially how this setting corresponds to meta-learning.

In general, meta-learning is a specific case of bilevel optimization in which an upper-level optimization problem is conducted over *several* different lower-level optimization problems. I believe that meta-RNN can be categorized as a type of meta-learning-  however, this needs to be further clarified by the authors.

In addition, it would help for the authors to clarify how their work conceptually differs from other RNN formulations with equilibrium hidden states. In section 3.2, the authors imply that prior works do not really solve their lower-level optimization problems- it would be ideal if the authors could be provide evidence for this.

There are also a few minor improvements that could be made:
1) If the authors wish to retain the meta-learning framing, it would help to refer to hyperparameters as meta-parameters
2) $\epsilon$ is not defined in Theorem 2
3) The authors state in section 3.1 that "Recall that the goal of RNNs is to learn discriminant representations for different data sequences, regardless of how the intermediate hidden states are defined.". This does not necessarily seem to be true: certain tasks may require similar representations for different data sequences. In general, the goal of RNNs depends on the optimization objective.

**Significance**
Currently, this contribution appears to be relatively incremental relative to prior RNN formulations that also use a dynamic update process to define hidden states. However, if experimental results and the clarity of the paper can be improved, the contributions of meta-RNN using fewer parameters, training data and training time could leave a significant impact in the research community.
limitations_and_societal_impact: The authors adequately state the limitations of the work in the conclusion. There also do not appear to be potential negative societal impacts specific to this work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The authors propose viewing RNNs as meta-learning algorithms, where the RNN parameters optimize the hidden state. By using carefully chosen functions they show that reasonable RNN cells come out, like a residual RNN. They experimentally show to perform on par or better than competing approaches in 3 toy tasks.
main_review: Pros
- Seemingly good results on toy tasks.

Cons
- The authors make the paper unnecessarily difficult to follow by trying to draw parallel to meta-learning and optimization algorithms. The fact that the proposed RNN cells are the application of an optimization algorithm on a carefully chosen function doesn't add anything to the discussion. You could probably choose the function carefully  enough to get an LSTM or any other kind of RNN in the for of a meta-RNN. It's clear the authors have carefully chosen the function (Equation 10) to get an affine transformation as it's derivative (Equation 11). 
- Theorem 2 should just be an observation. Obviously, if you have a residual connection which dominates, you're gradient won't vanish/explode. However, this again becomes harder to see if you make claims about meta-learning using the SGD optimizer.
- The paper lacks proper experiments. HAR-2, MNIST and the adding task are just toy problems that should be used to illustrate elements of the model. They can't be the only supporting experimental evidence.
limitations_and_societal_impact: N/A
review_title: null

Meta-review: Overall this paper is not well written and it is hard to understand why the main algorithm (Algorithm 1) makes sense. It is also not clear if the relationship to meta-learning is useful. The results are on toy problems only plus on PennTreebank added during the rebuttal with performance much worse than ones reported in the literature for LSTM’s (on this dataset). It is good that there is a lot of relationship to literature, but the authors should provide in clearer derivation and intuitive explanation of the algorithm and resolved the discrepancy between their performance and the ones in literature.

Mini review from AC:
Even after the discussions I still don’t understand why Algorithm 1 makes sense. Intuitively, consider a sequence such as text. Inputs (x_t’s) at different time represent different pieces of information that need to be aggregated and processed using the rnn. One part of the text talks about something and another talks about something else. Why is h_t a gradient step from h_{t-1} of a function of x_t? Since x_t have completely different meaning at different times, how is this optimising anything? Is it because of assumption at line 142 and why this then possibly works so badly on PTB? Another thing unclear in the algorithm: The innermost loop in Algorithm 1 is a deterministic computation that depends on x and theta*. How does the h_T in the upper level optimisation then depend on theta (without star)? Or is it meant to be theta* and the theta, w minimization is done using bptt? Can you please provide full self-contained details of this algorithm together with the intuitive explanation why it makes sense?

Decision: Accept (Poster)