Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers systems identification in vectorized auto-regressive model with stochastic noise. The paper focuses on the practicality of system identification with nearly optimal computation and sample complexity instead of using offline-style methods such as OLS. The authors propose a new SI algorithm based on SGD that uses reverse experience replay to address the challenges due to the inherent correlation between samples. Performance bounds on the accuracy of estimating the transition matrix as well as prediction error are given, both of which nearly matching the lower bounds. Numerical simulations show that SGD-RER is competitive to OLS, which enjoying a smaller time complexity. 
main_review: Originality:
- The idea of reversing replay buffer to mitigate correlation is interesting, novel, and practical.
- It is unclear to me why the SDG approach in [25] is insufficient. The partial observable LDS considered in [25] is a more general version of the auto-regressive model considered here. Also, another work by Hazan et al. 2017 uses online projected gradient descent, which also handles correlations in LDS via a standard online convex optimization argument. Could you discuss the differences between your work and these papers?

Quality:
- Strong theoretical guarantees are provided for both estimation and prediction errors. The leading term in error bound is independent of mixing time, which improves over prior work.
- Recent results on linear system identification and prediction that use OLS completely remove dependency on mixing time. While the leading term in error bound is nearly independent of mixing time, I wonder if it is also possible to remove the dependency of SGD stepsize on mixing time as well. Could you explain the challenges involved in removing this dependency?
- The experiments section can be improved. It would be interesting to see whether the SGD-RER is robust to the choice of step size. 

Clarity:
- The paper is organized well and easy to follow.

Significance:
- The paper is well-motivated and increases the practicality of linear system identification.

Additional references:
- Hazan, Elad, Karan Singh, and Cyril Zhang. "Learning linear dynamical systems via spectral filtering." Advances in Neural Information Processing Systems 30 (2017): 6702-6712.
- Tsiamis, Anastasios, and George J. Pappas. "Finite sample analysis of stochastic system identification." 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.
- Rashidiejad, Paria, Jiantao Jiao, and Stuart Russell. "SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory." 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. 2020.
- Lee, Holden. "Improved rates for identification of partially observed linear dynamical systems." arXiv preprint arXiv:2011.10006 (2020).
- Tsiamis, Anastasios, and George J. Pappas. "Linear systems can be hard to learn." arXiv preprint arXiv:2104.01120 (2021).

-----
After the response:

I thank the authors for responding to my questions. The discussion on the dependency of the bounds on mixing time is interesting and would be good to include it in the paper. I am happy with the answers and stick to my score in favor of accepting this paper.
limitations_and_societal_impact: Yes, the authors have discussed the limitations of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an SGD-style algorithm for linear dynamical system identification. The authors claim that the proposed algorithm is the first of its kind to have near-optimal error rates. The key idea behind the algorithm is to run SGD in reverse on streaming segments of the data. 
main_review: Online (linear) dynamical system identification is an important problem in machine learning. The paper motivates this well and clearly describes the new approach that is designed to tackle previous challenges.

What is missing in my opinion is a more thorough comparison (both theoretically and empirically) with other online algorithms that use the Sherman-Morrison-Woodbury (SMW) formula. The authors say that the application of such algorithms is limited. In what way is it really limited? Can you give a side-by-side comparison of the error rates? Also, you say that they do not apply to practically important settings like generalized non-linear dynamical systems. As far as the current paper goes, you do not show that SGD-RER can be applied to this case (you only briefly mention the work of Jain et al. (2021) on this matter). It would have also been nice to include a SMW-style online algorithm in the experiments. 

The other weakness of the proposed algorithm, in my opinion, is the fact that it introduces extra parameters such as the buffer size and gap, which both need be set as a function of the horizon. Sometimes the horizon is not known. Can the new approach easily be adapted to this case?

Finally, in line 243, you claim the rate in the lower bound in Thm 3 matches that of Theorem 1. However, in Thm 1, I see 1/sqrt{T} rate, whereas Thm 3 has a 1/T rate. What am I missing here? 

limitations_and_societal_impact: NA
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors consider a rather special case of a linear dynamical system, where there is no hidden state and the transition matrix is "externally stable" (less than 1 in the operator norm), process noise is sub-gaussian, and the stationary distribution has bounded fourth moment. In this case, they suggest running the SGD "backwards" in small buffers, which they call "reverse experience replay". This leads to the independence of the observations, and the unbiased nature of the SGD updates. 
main_review: Originality:

This is original, as far as I can tell. The only issue could be the concurrent submission of id 1136 on the use of related algorithms for the identification of non-linear systems (under even stricter assumptions).  

Quality:

The algorithm is practical and readily implementable. The analysis is quite sophisticated.

Clarity:

The paper is a joy to read.

The significance:

I imagine that this could become influential. 
limitations_and_societal_impact: None.
review_title: null

Meta-review: This paper considers the system identification problem in a vector autoregressive process using a single-pass SGD type algorithm with reverse experience replay. The analysis is interesting, and compared to existing work, it has improved the dependence on the mixing time and dimension. Although it has not completely resolved the dependence on the mixing time, I agree with the reviewers that it is already an interesting contribution and a concrete step towards a better understanding of system identifications in linear systems. I am happy to recommend acceptance. 
Decision: Accept (Poster)