Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes an algorithm for learning LTI systems with zero process noise. Given an input trajectory generated from independent Gaussian input, the algorithm estimates the impulse response function, which in turn can be used to estimate system parameters up-to similarity transformation.

The key idea is the multi-scale smoothing of the impulse response: A first estimate is obtained using linear regression. Denoising of the response function estimate is then performed by low-rank approximation of Hankel matrices of different sizes, with the insight being that the size of the matrix determines which parts of the response functions are preserved under the low-rank approximation.  

The proposed algorithm achieves an error rate that scales only logarithmically with the system memory. The efficacy of the algorithm is demonstrated on a synthetic problem.
main_review: Overall, this is a well-written paper. The contribution is clear and the flow of ideas is logical. 

My main concern is that the experiments were conducted exclusively on synthetic data. While It is beneficial to have control over the parameters of the problem. It is equally important to demonstrate the efficacy of the algorithm in real-world data.

Other comments:
* L96-98 gives the impression that Frobenius norm lower bounds the operator norm whereas the opposite should be true.
* L130: It is not clear what "diagonals that are $\Theta(l)$" means. Also, do you mean skew-diagonals?
* L137: What is G? Also, it would be good to define the indicator function.
* Algorithm 1 - Line 4: $(F * u)(t)$  (use parentheses)
* L146: $\Sigma_x$ instead of $\Sigma_y$ for process noise.
limitations_and_societal_impact: I do not see a potential negative societal impact in the paper.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This work considers the problem of learning linear dynamical systems with partial observability both in terms of learning the impulse response and the system parameters upto similarity transformation (using Ho-Kalman algorithm). The main technical contribution is Algorithm 1 and Theorem 2.2 which presents the error bounds for Algorithm 1. This shows that the impulse response can be learned upto frobenius error $\sqrt{d/T}$, without any dependence on the mixing time/memory length of the dynamics. The main technical tool used in Algorithm 1 is the least squares estimation of the Hankel matrix at various scales to cover dependences from inputs at various time instants and denoising it with SVD since the true Hankel matrix is constrained to have rank d. 

The experiments illustrate the advantage of the algorithm compared to least squares regression. 
main_review: I think the algorithm and its analysis is novel on both technical and conceptual level. It solves an important problem with near optimal bounds which does not depend on the memory length by using the elegant idea of SVD to denoise the Hankel matrix estimate obtained through least squares regression. Rest of the algorithm seems to be fairly standard. 

I think this deserves to be published in NeurIPS 2021.

Some comments:

1. The improved rates only hold when there is no additional noise in the hidden dynamics of the system. (This is mentioned in the paper)
2. The parameter recovery in Theorem 2.3 has an additional factor L, which is not clearly explained. 
3. It would be great if the magnitude of $\epsilon_{\mathsf{trunc}}$ is mentioned. 
4. It would be useful to mention the computational complexity of the algorithm. 
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This work studies the estimation of linear dynamical systems with unobserved state. The authors propose a novel algorithm which relies on obtaining low-rank approximations to the Hankel matrix. They provide several results on the performance of their algorithm, including finite time bounds on the error it obtains in estimating the system’s impulse response. As compared to previous work, the main novelty of this paper is eliminating a factor of the horizon in the case where there is no process noise.
main_review: Obtaining finite-time bounds for the estimation of linear dynamical systems—in both the setting where the state is observed and the state is unobserved—has been a well-studied problem in the machine learning community over the last several years, and this works fits in that literature. A primary goal of existing works has been to obtain error bounds which do not scale with the “memory” of the system, 1/(1-\rho(A)). While achievable in the case where the state is observed, this has been a more difficult goal to reach in the case when the state is unobserved. Several existing works have addressed this—for example, [1] introduces the notion of "phase rank" to avoid the memory dependence—but it is not clear that the issue has been completely solved (phase rank could be exponential in the dimension in some cases, which is also highly undesirable). This work claims to remove the memory dependence without incurring poor dependence on other quantities, but is only able to do so in the case with 0 process noise.

Pros:
- As noted above, removing the 1/(1-\rho(A)) dependence is an important goal, and as yet has not been completely achieved in the case when the state is unobserved. As such, the problem considered here is relevant and, if solved, would be a contribution. 
- The authors do solve the problem in the case when the process noise is 0, eliminating the dependence on the memory in this setting.

Cons:
- The primary issue with this paper is that the memory dependence can only be removed in the case when there is no process noise, i.e. the results improve on the state of the art only when there is no process noise. This is a very restrictive assumption, is likely unrealistic in practice, and it is not clear how interesting this setting is to the learning theory community (existing works have all assumed non-zero process noise). 
- Even in the noiseless setting, the memory dependence is not removed for the recovery of the system parameters (i.e. A,B,C,D) but only for the recovery of the impulse response. 
- The authors restrict to the case when \rho(A) < 1 while existing works also encompass the case when \rho(A) = 1. 
- The algorithm takes as input the memory length of the system, but it is not clear how one should actually set this without knowing the system parameters. 
- More care should be taken in comparing to [1]. [1] introduces the idea of phase rank, and provides bounds that scale with the phase rank instead of 1/(1-\rho(A)) in some cases (even with non-zero process noise). No discussion of this is given—it should be clarified what precisely the bounds in [1] work out to be, and what the actual memory dependence suffered is. At minimum the authors should not claim that no existing works obtain bounds that are memory-independent and should show explicit examples where their results improve over the phase rank dependence in [1]. 

While this work does make a contribution, the restrictive assumptions noted above and the fact that [1] partially solves the problem already are, in my opinion, significant enough that it does not warrant an accept. 

[1] Max Simchowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi-parametric least squares. arXiv preprint arXiv:1902.00768, 2019.
limitations_and_societal_impact: The authors do not discuss potential societal impact. However, the work is primarily theoretical so it is difficult to determine what negative societal impacts it may have. Limitations are discussed.
review_title: null

Meta-review: The paper studies the problem of learning a partially observed linear dynamic system and provides non-asymptotic system identification guarantees that scale with the dimensionality of the system, rather than the memory length. This is definitely an interesting direction, but the reviewers identified several limitations with the results in the current paper. Most notably is the fact that the paper only concerns systems with no process noise.

I am sympathetic to the fact that making progress on a hard problem can take some time and may require making assumptions to obtain preliminary results and develop new ideas. However, it would be worthwhile to explore the consequences of the assumptions more to provide a more complete story. In the context of the present paper, as suggested by the reviewer, it would help to understand if other algorithms have a memory dependence in the no-process-noise regime and also if there are lower bounds in the more general setting. Such auxiliary results would complete the picture and make the paper much stronger. 

Thus, we recommend rejecting the paper at this time.
Decision: Reject