Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: This paper shows that randomly initialized RNNs can display a type of chaos called Li-Yorke chaos and the number of linear regions they have remains exponential with depth (unlike in feedforward nets).
strengths_and_weaknesses: Strengths: 

The work seems technically sound, although I have to admit I did not go through the proofs very carefully.

Weaknesses:

Please see questions and limitations below.
questions: In experiments reported in Figure 3, do the authors use a standard RNN or an RNN with a clip operation as the one used for the proofs?
limitations: RNNs are not a very commonly used architecture in machine learning any more, so I doubt that these results will be of much interest to the NeurIPS audience. This paper in addition studies a peculiar type of RNN with a clip operation after the nonlinearity that calls into question even more the relevance of these findings for even standard RNN architectures that used to be used by the machine learning community.

It wasn’t really clear to me what the implications of Li-Yorke chaos or exponential number of linear regions are in practical terms beyond things like instability and exploding gradients etc. The results are in general very far removed from the interests and concerns of the overwhelming proportion of machine learning practitioners today. I believe a more specialized venue on dynamical systems may be more appropriate for this work. 

Finally in Fig 4, having a Jacobian norm greater than 1 seems like a very weak proxy for what the paper is primarily concerned with, i.e. Li-York chaos.
review_title: null

final_score: rating: 9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors establish non-asymptotic probability bounds that a random (randomly initialized) recurrent neural network is chaotic.
The analysis is performed as follows

1. Hidden state $x_t$ is scalar, and the state space is compact interval $x_t \in [a,b] \subset \mathbb{R}$

2. ReLU is used as the activation function, though the analysis only requires continuity rather than differentiability

3. Using the specific definition of chaos due to Li and Yorke for interval maps, the authors need to bound the probability that the RNN $f$ has period three fixed points, i.e. $f^3(x^*) = x^*$

4. The probability of such an event is then expressed in terms of the number of neurons $k$, the variance parameter $\sigma^2$ of a Gaussian distribution from which the 'weight matrix' is sampled.
strengths_and_weaknesses: The submission offers a novel, rigorous analysis that quantifies how commonly is chaos found in RNNs with finitely many neurons.
Unlike the mean-field approaches, $\lim{k \to \infty}$ isn't necessary.

This allows to establish chaos more rigorously than the use of Lyapunov exponents usually allows for.

Overall, I believe this to be an extremely interesting study, with excellent presentation.

I would like to offer some comments, presented in chronological order, that might help improve the manuscript further:

1. I found Figure 2 somewhat hard to understand, at least initially. It might be worthwhile displaying the equation for the tent map in the figure. The graph added little intuition, partly because nodes and edges aren't explained. It might also help to mention that the FNN graph is simply 'unrolled'. Perhaps it would also help to indicate where the small Gaussian perturbation is supplied? What overall effect on the dynamics do stochastic perturbations to $b_i$'s have? 

2. Li-Yorke chaos is introduced, but never contrasted with other definitions e.g. one due to Devaney. This could also give an avenue to explicit all the consequences of LY chaos for interval maps, such as sensitive dependence on initial conditions/exploding gradients.

Section 2.1
Most of the cited references analyze their respective problems using ergodic theory. The juxtaposition with LY chaos is entirely warranted, but the phrasing of the sentence gives the impression that non-reliance on LY is somehow 'bad'.

Paragraph 'RNNs transitions in Higher Dimensions':
Invoking LY chaos is warranted for interval maps. For higher dimensional systems period-3 fixed points do not provide sufficient nor necessary conditions for chaos. Similarly, requiring the existence of a scrambled set as in Definition 2.1, can produce dynamics that do not have the sensitive dependence on initial conditions. 
I believe this should be acknowledged. In a similar vein, paragraph 'Techniques' (lines 143-159) gives an impression that the analysis is more general than the mean-field one, rather than that it lies at the "opposite end of the spectrum". I believe it should be stated more clearly in the sections of the submission that technical arguments apply only to RNNs with a scalar hidden state $x_t$.
questions: > small perturbations do not break expressivity
I am not overwhelmingly familiar with symbolic dynamics, but if the activation were smooth, then the persistence should be guaranteed due to hyperbolicity. I wonder if the authors could offer some comments on the hyperbolicity and robustness.

Lines 190-193:
Could the authors comment further on cases when chaos is unobservable?

Figure 5 and accompanying code:
It appears the figure is produced by calculating the input-output Jacobian of the 2 layer NN specified in the paragraphs 'RNNs transitions in Higher Dimensions'. I would argue that evaluating either input-output Jacobian of the iterated map or its Lyapunov exponent would provide a more convincing evidence for chaos.
On a related note, I do believe that use of the function `complexe_modulo` is erroneous-- stability of the system should depend only on the real part of the eigenvalues.
limitations: N/A
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the behavior of a specific class of RNNs at initialization using dynamical systems theory. Its main result shows that chaos can arise in RNNs even in the absence of external input and this behavior holds independently of the width. This result explains the scrambling phenomenon observed experimentally. It also shed light on the expressive power of RNNs, in terms of the number of linear regions formed by the nonlinear activations.
strengths_and_weaknesses: Strengths
- Provide first understanding of RNNs via the lens of Li-Yorke chaos
- Overall well written

Weaknesses
- Analysis is limited to scalar inputs and RNNs with ReLU activation (tanh activation is often used in practice)
- There are no results connecting the behavior of input data to the chaotic behavior of (input-driven) RNNs, which are highly relevant in practice
questions: - Is it possible to clarify the connection between Li-Yorke chaos and exploding gradients slightly more precisely?
- Will similar chaotic behavior be observed for other variants of RNNs (say with different activations and depth)?
- For the experiments with MNIST, how does the Pr[period 3] depends on the width of RNN? Would be good to demonstrate some results along this line
limitations: In the checklist, it was mentioned that limitations are described, but I could not find any such discussions in the main paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper explores how randomly initialized RNNs exhibit "Li-Yorke chaos" with a certain probability and which leads to exploding gradients and other undesirable phenomena. By using the fact that functions containing a period three point it exhibits chaos, some probabilistic bounds on the emergence of chaos in RNNs are derived. Finally, the theoretical results are evaluated with two toy examples.
strengths_and_weaknesses: Strengths:
- Stunning maths
- Interesting little experiments with code attached

Weaknesses:
- Short conclusion, no immediately apparent benefit other than a new name for the phenomenon.

Suspected Errors:
- Figure 1: A legend would be helpful -  what is the blue line? Typo in caption: "adabehind" 
- Figure 2: Unclear how spikes in the plots correspond to linear regions
- Lemma 4.2.: Some y's should be x's?
- Line 156 end: something missing here


questions: - Is the resulting chaos actually desirable or should it be avoided when possible?
- If it should be avoided, what alternative initialization procedure could be used?
- What would be the theoretical bounds for the Probabilities given in Figure 3?
limitations: Not applicable IMO
review_title: null

Meta-review: metareview: This submission is borderline.  Reviewer EXTU praises its theoretical contribution and highly recommends acceptance.  Reviewers niom and YhQb are more tepid but still support acceptance in light of the sound theoretical analysis.  Reviewer j5Sz acknowledges that the analysis is sound, but believes the models to which it pertains (RNNs, with certain unconventional features) are of little interest to the community, and therefore argues for rejection.  While I agree with j5Sz that the paper may not be of immediate interest to many practitioners, I believe the theory it delivers is worthy on its own, and may lead to further theoretical developments that will apply to more contemporary neural networks.  I thus recommend acceptance.
confidence: Less certain
Decision: Accept