Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work has four major contributions: a) authors provide the first offline algorithm that can learn non-linear dynamical systems without the mixing assumption, b) authors significantly improve upon the sample complexity of existing results for mixing systems, c) in the much harder one-pass, streaming setting authors study a SGD with Reverse Experience Replay (SGD − RER) method, and demonstrate that for mixing systems, it achieves the same sample complexity as our offline algorithm, d) authors justify the expansivity assumption by showing that for the popular ReLU link function — a non-expansive but easy to learn link function with i.i.d. samples — any method would require exponentially many samples (with respect to dimension of Xt) from the dynamical system. 

This paper is comprehensive with both solid theoretical analysis and simulations. 

main_review: Originality: authors studied the problem of learning non-linear dynamical systems from a single trajectory and analyzed offline and online algorithms to obtain near-optimal error guarantees. The results are original.

Quality: Overall the quality is good. However, compared to the theoretical analysis, the empirical experiments are bit too short. 
It would be helpful to consider multiple different data generating system, instead of just one simple case study. In addition, it would be great if authors can provide some ablation study on the impact of the hyper-parameters of the algorithm, and how they are selected in the simulation (e.g. B = 240 and u = 10). 
Also authors claimed "step sizes for GLMtron have to be chosen to be small in-order to ensure that the algorithm does not diverge", it would be helpful to add some results to help understand how the step size can influence the performance for the GLMtron in appendix, as a smaller step size usually lead to slower convergence.
Also in the theoretical analysis authors proved the convergence rate with heavy tail noise, while only studied Gaussian noise in the empirical study. It would be great to have multiple experiments with different noise.

Clarity: Overall the paper is clear. My only concern is this paper contains too much results,so a 8-page conference paper might not be the best venue compared to journal article. 

Significance: this works has both theoretical contribution, and methodological contribution.
limitations_and_societal_impact: Not observed any potential negative societal impact
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors study a very special case of "non-linear dynamical systems" where there is no hidden state and there is some expansive, component-wise "link function" \phi in the evolution X(t+1) = \phi(AX(t)) + noise. For this very special case, they show both off-line and on-line algorithms. They also show lower bounds on the sample complexity of learning systems with with non-expansive link functions (such as ReLU). 

main_review: The authors study a very special case of "non-linear dynamical systems" where there is no hidden state and there is some expansive, component-wise "link function" \phi in the evolution X(t+1) = \phi(AX(t)) + noise. For this very special case, they show both off-line and on-line algorithms. They also show lower bounds on the sample complexity of learning systems with with non-expansive link functions (such as ReLU). 

Originality:

The work seems very original. 

Quality and significance:

Removing the T_mix term in the sample complexity is a major contribution, albeit to a problem where real-world applications are "yet to be found".

Clarity:

While I have not checked the proofs in the supplementary material in detail, the main body of the text is very well written.  
limitations_and_societal_impact: None.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider non-linear dynamical systems of the form $X_{t+1} = \phi(A^* X_t) + \eta_t$, where $\eta_t$ is a noise term, $A$ is a $d \times d$ matrix and $\phi$ acts component-wise, and provide some results relating to the estimation of $A^* $ under certain assumptions. A key assumption is that $\phi$ is "expansive", which I understand to be a sort of converse Lipschitz condition. (Since 1-Lipschitzness is also assumed, this means that $\zeta |x - y| \le |\phi(x) - \phi(y)| \le |x - y|$ for some $\zeta \in (0, 1)$. I wasn't sure why this was called "expansive", because it seems to me more to be a limit on contraction than expansion per se, but this seemed understandable.) Under these conditions, they provide:

1. An algorithm that, given sub-Gaussian noise, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$ (though I have questions about this, see main review).
2. An algorithm that, given system stability and finite-fourth-moment noise, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$ (though I have questions about this too).
3. A _streaming_ algorithm that, given sub-Gaussian noise, system stability and twice-differentiable $\phi$, can recover $A^*$ with squared-norm error scaling in $O(d^2/T)$.
4. A negative result with the non-expansive ReLU function, showing a lower bound on squared-norm error in this case of $\Theta(e^{cd}/T)$, implying a need for exponentially many samples to recover $A^*$ satisfactorily.

main_review: Firstly—there are a lot of results in this paper. Some of the proofs are very involved and the authors had space only for just over one page for all four proof sketches, leaving 36 pages for the supplementary material. I congratulate the authors on their work. I suspect this could have comfortably been two papers if the authors had so wished. On the other hand, this volume made it an apparent challenge for the authors to structure the paper and highlight the key ideas in their work. For this reason, I wonder if this may even have been a stronger submission with just half its content but more thoroughly explained.

**Clarity:** The summary Table 1 was very helpful in understanding how the results fit together. The main assumptions of the paper are listed in one place, which makes for some back-and-forth reference, but I can appreciate why this structure was chosen. The notation was generally clear and I didn't find it too confusing. If the authors can find a way to make pagination/space work, a minor suggestion is to show most the auxiliary definitions in Theorems 1 and 2 in display mode (rather than inline).

I had a couple of clarifying questions about the results:

1. In Theorem 1, $R^*$ appears in the $d^2$ term, and it is proportional to $d (\sum_{t=1}^T \rho^t)^2$ (ignoring log terms). If $\rho < 1$ this would not be an issue but I believe this theorem is specifically about the case where $\rho > 1$, which if I'm not mistaken would make $R^* = O(d \rho^{2T})$ (ignoring log terms), $\rho^T$ being the dominating term in the summation (and then squared). But that makes $R^*$ exponential in $T$. Then wouldn't we have $$\log\left(1 + \tfrac{R^*}{\sigma^2}\right) = O(\log d + 2T \log \rho),$$  (ignoring log-log terms) thereby cancelling out the $T$ in the denominator of the squared error expression? Then we would have an error in $O(d^2 \log d)$ rather than $O(d^2/T)$ as claimed? I have probably missed something here and politely invite the authors to clarify.

2. The left-hand side of the main line of this theorem has $\mathbb{1}(\mathcal{W})$ in it, which if I'm not mistaken is a random variable (being the indicator of an event). This makes the left-hand side of that expression a random variable (since it is an expectation multiplied by a random variable). Then is the inequality in this theorem intended to be an almost-sure inequality? Or are the authors trying to say that with probability at least $1 - \delta$, 
$$\mathbb{E}\lVert A_m - A^* \rVert_F^2 \le \frac{C_0 d^2 \sigma^2}{\zeta^2 T \lambda_\mathrm{min}(G)}?$$
I again hope the authors can clarify.

**Significance:** Since there were so many results, the implications and significance were sometimes hard to follow. Since all of the results appear to be interrelated and highly specific, I would have appreciated a section explicitly discussing how results fit into existing knowledge and what gaps remain—preferably for all of the results of the paper in one place. I appreciate that this may necessitate even further trimming some sections to allow it to fit, but I think it would be helpful.

My impression in general is that the results are significant and likely to be built on, but I think this paper would be much stronger with a clearer discussion of what the authors envisage with respect to this.

**Quality:** I could not check any of the proofs in the supplementary material in detail, but there was nothing unsound that I could detect from my review of the main paper (except perhaps question 1 above), and a quick scroll through the section A of the supplementary material. I tend to think the nature of the assumptions makes the weaknesses of these results somewhat self-explanatory, and the authors make references to these in passing, though this is part of the discussion that I mentioned above might be useful.

**Originality:** As far as I can tell, the proof techniques aren't brand new but their applications in this setting may be somewhat new, and the cases addressed in the paper are new contributions. However, I am not sufficiently familiar with the surrounding literature to provide a confident assessment of how original this is given the prior art.

**Typos:** (not part of assessment, just for benefit of authors)
- Line 17, stray period after "via".
- Line 160–161, "for _a_ possibly unstable".
- Line 162, "in _the_ linear system".
- Line 163, "mixing _systems_" (plural).
- Theorem 1, "Assumptions _1, 3_ and 4" (missing comma).
- Theorem 2, the expression for $m$ has $R^*$ in it, I assume this was meant to be $R$?
- Line 181, Section B.1, I assume this was meant to say Section A.2.
- Also, a reference to the proof of Theorem 1 was omitted.
- Remark 2, "_Theorem_ 3" (missing capital letter).
- Line 273, missing period.
- Line 277, "SGD-ER".

_Edit, 02 Sep 2021: Raised rating from 6 to 7, as discussed in below responses/comments._
limitations_and_societal_impact: The paper is almost entirely theoretical in nature and I don't foresee any direct societal impact as a result of this work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work considers learning NLDS. Previous works can only learn mixing systems with sub-gaussian noise in the offline setting, with sample complexity depending on the mixing time. This work improves existing results in several ways, assuming the link function is expansive:
1, it's shown that the offline Quasi Newton Method achieves near-optimal convergence rate for non-mixing systems.
2, the offline Quasi Newton Method still achieves near-optimal convergence rate with heavy-tail noise, assuming mixing systems.
3, a new algorithm SGD-RER is introduced, which achieves near-optimal convergence rate in the online setting.
4, an exponential lower bound is proven for the ReLU link function, showing the expansivity assumption is necessary.
main_review: Originality: This work focuses on a classic problem: learning NLDS. Nevertheless, the settings considered in this paper are less touched in previous works, and the use of SGD-RER is novel.

Quality: Although the authors claim that the upper bounds in this work is independent of the mixing time, a new term $\lambda_{min} (\hat{G})$ is introduced which would make the upper bounds vacuous when being very small. It's unclear whether we can give a good lower bound for $\lambda_{min} (\hat{G})$, thus the result in this work isn't a $\text{strict}$ improvement over previous works. In line 164 there is no support why $\lambda_{min} (\hat{G})\ge \sigma^2$ should hold. In line 165, $\rho<1+C/T$ seems problematic.

The assertion of Theorem 2 is non-standard (and actually weaker). High-probability upper bounds of errors are preferred in common. The secondary choice is proving an upper bound for the expectation of error. However, Theorem 2 proves a high-probability bound for the expectation of errors, which might fail in the two settings above.

Clarity: The notations are heavy. Hiding ignorable variables and the parameter setting can improve the readability of theorems. The proof sketch of Section 3 is too brief compared with that of Theorem 4. More details should be included, for example, why can we use the convex proxy loss in line 127?

Significance: This work improves existing results for learning NLDS in several ways. The new algorithms/improved analyses can be useful for solving practical problems in RL and control.

Other comments: in line 163, number 'of' samples. 
In line 179, $\tau_{mix} \approx 1/(1-\rho)$.
In line 180, the probability measure should be specified for the sigma algebra.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The contributions were considered to be significant with high potential for impact. The main concern was that the paper contains, in a sense, "too much": there are many results, which made it harder for some reviewers to appreciate the level of contribution/improvement, and which raises the question of how to package the results into a coherent final version of the paper. Perhaps the authors can also consider submitting to a journal.
Decision: Accept (Spotlight)