Venue: NeurIPS 2022 Conference

Reviews:

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: The paper deals with stabilization of an unknown LTI system from an trajectory of the system, thus learning and stabilization of the system must be done simultaneously. This is a timely problem and an current active research area. In the paper, the states/modes of the system are divided into stable/unstable, and only the unstable modes are identified and controlled.
strengths_and_weaknesses: Strengths: The paper well written, it deals with a timely problem, and as far as I know the main results are novel and improves on the state of the art.

Weakness: 
1) There are several assumptions on the systems that restricts the applicability. Assumptions 4.1, 4.2, 4.3, seem rather harmless, however, the assumption on the eigenvalues |\lambda_1|^2 | |\lambda_k|<|\lambda_{k+1} restricts the applicability. Especially if |\lambda_1| is large. 

2) The algorithm uses k, so one need to know the number of unstable modes. 

3) In the key results, only dependence in k and n is stated but it is noted that the constant depends on other parameters as well. It seems to me difficult (and strange) to find a sequence of systems where all hidden parameters are constant (even for the ones listed). Here I think it is important to state exactly which parameters the assumptions on the parameters. In particular, when the number of states and unstable modes changes, the parameters need to be well defined and cannot, e.g., depend on the size of the system.

I did not read the supplementary material.
questions: Can the weaknesses above (1 and 2) be addressed? By including a larger "k" in the algorithm compared to the number of unstable modes it may be possible to overcome or weaken these two limitations.

Can you state the theorems so that is clear what the assumptions are on the system parameters? Are all these parameters independent of the number of states?
limitations: Not applicable. This is basic science. I see no potential negative societal impact related to this work.
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: The paper provides an algorithm for stabilizing a noiseless LTI system on a single trajectory with sample complexity scaling in the number of unstable modes of the dynamics matrix rather than the state-dimension.
strengths_and_weaknesses: Strengths:
- At it's core, this is an important problem.  LTI systems are one of the most important primitive in control and exponential state blow-up in the state dimension is a critical problem in all existing work in this area as far as I know.  
- Writing is generally quite clear and well organized. The assumptions are presented clearly in section 4 and for the most part are reasonable (see weaknesses).  Breakdown of the algorithm and exposition into stages also is very nice for clarity.
- Work seems technically correct and strong.

Weaknesses:
- While the algorithm is empirically justified in the presence of noise in App. H, no provable results for the noised case significantly weaken the result.  As mentioned in the paper, many existing methods first need a stabilizing controller.  This will need to be found in the presence of noise, which for some applications even needs to be adversarial.
- It appears that the instability index $k$ needs to be known for the algorithm, which probably is not reasonable in general.
- The algorithm outputs a $\tau$-hop stabilizing controller, which may not be suitable for certain downstream control tasks.
- Assumption 4.1 seems reasonable but may actually be difficult to deal with without handling noise.  Many physical systems do have repeated eigenvalues and small perturbations to the system parameters would require some form of noise tolerance.  Ideally, robustness in the $H_{\infty}$ sense would be involved as these perturbations depend on the state.


While there are limitations, I think this is result still would be a worthwhile addition to the conference.
questions: Noise definitely makes the analysis more challenging/messy, but is there a path to prove similar results for the noise setting?

Can the results easily be generalized to unknown $k$?
limitations: Limitation of known $k$ could be addressed directly.
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: The paper studies the problem of stabilization from data in the case of linear control systems, in the noiseless setting. A new algorithm is proposed, where instead of identifying the whole state space, it is sufficient to identify only the unstable part. Under certain assumptions, this is sufficient for designing a stabilizing control, requiring fewer samples than the case when everything is identified. The paper provides some sample complexity bounds with high probability, where the randomness comes from the initial condition. If some special conditions are satisfied, then the complexity is linear with k, i.e. the total number of unstable eigenvalues, and depends logarithmically on n, i.e. the dimension of the state space. 

​
strengths_and_weaknesses: As mentioned in the summary, if certain special conditions hold, then the complexity is linear with k, i.e. the total number of unstable eigenvalues, and depends logarithmically on n, i.e. the dimension of the state space.
This is a novel and interesting result that was not established before. Hence, the benefit of this algorithm is that we can stabilize the system much faster compared to the standard algorithm, where we identify the whole state space.
It would be interesting to compare the results of this paper to the paper by Talebi, Alemzadeh, Rahimi, Mesbahi, "Online Regulation of Unstable Linear Systems from a Single Trajectory", CDC 2020, where a similar topic is explored, under similar assumptions.
​
The main weakness  of the paper is that it relies on several restrictive assumptions that should be explained upfront and in more detail. More intuition should be provided; for example it would help to provide a discussion on what types of systems satisfy these assumptions. Also it should be explained whether the algorithm still works or fails in the absence of these assumptions.
The most crucial assumption is that all unstable modes are directly driven/controllable by the input matrix B (Assumption 4.3 along with k=input dimension m). In other words, it is assumed that we have a lot of inputs and all of them directly affect any possible unstable mode. This assumption is quite restrictive since it rules out the possibility of underactuated systems, systems with network structure or systems with integrator-like structure, which in general are hard to control, see the paper by Tsiamis, Ziemann, Morari, Matni, Pappas "Learning to control linear systems can be hard", 2022.
The material of Section C does not explicitly address the case when we might have k larger than the number of inputs (m less than k)-see also questions. 
There are three more assumptions that are somewhat restrictive yet crucial for obtaining the result. i) There should be no noise in the system, ii) The initial condition should be non-zero, iii) the stable eigenvalues cannot be arbitrary; they should be small enough to cancel the effect of the unstable ones (in the cross-term entries of matrix M tau). The paper provides technical reasons why we need them, but it would be nice to also see some discussion whether they are necessary or not. For example, having stochastic noise might affect sample complexity in a dramatic way; in deterministic systems it is always possible to identify everything with zero error and finite samples while this is not possible in the case of stochastic systems. The assumption of the stable part cancelling the unstable one seems artificial, would the algorithm work if it was removed? 

​
questions: Please compare with the two papers listed above, Talebi, Alemzadeh, Rahimi, Mesbahi, "Online Regulation of Unstable Linear Systems from a Single Trajectory", CDC 2020 and Tsiamis, Ziemann, Morari, Matni, Pappas "Learning to control linear systems can be hard", 2022.
​
There should be more intuition/discussion about what types of systems satisfy Assumption 4.3 , k=m.
​
Please provide more details for the case of general matrices B (when m is less than k) and clarify Section C.  What would Assumption 4.3 look like in this setting? How would the result of Theorem 4.1 depend on the index d? To my understanding, in the worst case, we might need to unroll the state d=theta(n), not theta(k/m), times to achieve controllability and stabilize the system. I believe, this d can be as high as the controllability index of the system, which in the worst case can be linear with n, even if the number of unstable modes is as small as one (unless further assumptions are imposed).   For example, see system (14) in Tsiamis, Ziemann, Morari, Matni, Pappas "Learning to control linear systems can be hard", 2022. For that system, tilde B (projected on the unstable subspace) would be equal to zero unless d=n-1. 
​
There seems to be a problem with the invertibility of matrix D'D. In particular, if matrix A is singular, then D'D should also be singular. Probably the results still go through since a projection is considered. But the proofs of section E should be updated.
​
Could you please provide more intuition why u has this particular form in line  11 of the algorithm? Why does the input scale with the norm of x? Since x is unstable, this might lead to very large control inputs. Please clarify that in the text since this seems to be another limitation of the algorithm. The naive algorithm would work with small inputs.
​
Please provide more discussion on which assumptions seem necessary and which assumptions seem removable.  
limitations: See comment above.
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 studies the number of samples for learning to stabilize a noiseless linear control system. Under a set of assumptions, it is shown that with O(k log n) samples the system can be stabilized, where n is the state dimension and k is the instability dimension. An algorithm is presented for that purpose too.
strengths_and_weaknesses: Strengths:
The paper discusses different steps and explain them. Also, the technicalities and the assumptions are stated in a way the reader can follow.

Weaknesses:
I like to see how the authors can discuss the following items. 
- Overall, the writing is repetitive in multiple places. 
- I think connections to some relevant stabilization algorithms in the literature (mostly subject to stochasticity and/or using that) are missing.
- In the abstract, 'instability index' needs a (high level) definition, and the rates are not correctly written (the current one seems like k log k).
- The assumptions are strong. The open loop matrix is diagonalizable, does not have any unit eigenvalue and even has a significant eigen-gap (Theorem 4.1), the unstable and stable eigenspaces are assumed almost orthogonal, the dimension of the control input is exactly the same as the number of unstable eigenvalues, etc. 
- On top of the above, having an undisturbed dynamics is a very important and strong assumption. Although, the authors correctly claim that it is not consequential in terms of stability, it is important for learning the unknown matrices by letting the observations be noisy or noiseless, and also as mentioned in line 196, the stable modes all die out in undisturbed systems. Importantly, most of the assumptions here are not needed in the existing literature, and some are proven to be satisfiable through designing the control input properly, rather than being given.
- Along the same axis, for extending to stochastic systems and having high probability results, it is not clear how this work helps as the authors claim in line 120.
- Some sample presentation points to improve are as follows. In Def 3.1, I think orthonormality of the matrices is crucial and needs to be emphasized and mentioned explicitly. In line 5 of Algorithm 1, I think it should be 'ortho-normalized'. The range of i is not clear in line 11. Line 258 and invertibility needs more concrete explanation. R_1 in Assumption 4.3 is better to be referred to where defined. I could not find the 'recall' in Theorem 4.1, and it might be added to the assumptions. 

questions: See above
limitations: See above.
review_title: null

Meta-review: metareview: The paper considers an interesting and timely theoretical problem in the intersection between control and machine learning. The paper is well-written and the results are novel and provide insight into how and when the sample complexity for stabilizing an unknown LTI system can be decreased. I thus recommend that it should be accepted. Nevertheless, I believe that the assumptions imposed are strong (full state measurements, strong controllability assumptions, requirements on the initial state, and systems with at least two unstable eigenvalues and no integrator dynamics) while the adaptive control literature in the 80's solved similar stabilization problems under much less stringent assumptions. Even though the contribution is theoretical, it would be useful with a physics-based example to make ideas and assumptions more concrete and compare the proposed approach against the state-of-the-art from both classical adaptive control and modern learning-based techniques. 
confidence: Less certain
Decision: Accept