Data-driven Optimal Filtering for Linear Systems with Unknown Noise Covariances

Summary

The paper builds on the duality between estimation and control, in order to develop an online data-driven method for MSE-optimal filtering of linear systems with linear observations. Process and observation noise covariances are considered unknown, but stochastic states are assumed to be bounded. The paper proposes using SGD in the space of steady-state stabilizing gains, claims asymptotic convergence to the optimal gain, and provides an asymptotic probabilistic bound on the deviation from optimal error.

Strengths

Although the use of online optimization for controlling linear-quadratic settings is not new (e.g. [r1]), exploiting the duality between control and filtering problems is novel and interesting in this context. The concentration and error bounds are not trivial and useful, as concentration bound is non-asymptotic in the series length T. Proof of SGD convergence and error bounds are novel as well, even if derived under very strong assumptions. [r1] Cohen A. et al., "Online Linear Quadratic Control", 2018

Weaknesses

Overall, I believe the authors did their best that the paper will be well-organized and clear (as it can be for a rather technical manuscript). The explanations and given outlines before each section are indeed helpful. However, it is still very hard to follow the assumptions and constant definitions, and some of the conclusions. Writing becomes very laconic at some crucial points (e.g. Thm. 2, Remark 7). Particularly, Thm.2 and it's proof are not clear hence it is hard to get convinced in their soundness. Furthermore, In the introduction it is stated that convergence is guaranteed from every initial policy, but according to Theorem 2 the policy cannot enter (or start in) a class of policies where gradient is smaller than some constant. I didn't find any discussion about when trajectories enter this region. My impression is that this is a good paper, and I might be missing something. I will be willing to raise my score when given a more detailed proof and this clarification.

Questions

I ask for a more detailed proof for Thm. 2 (see above). In addition, a summary of all assumptions, results and notations can be very useful. Minor typos: l. 249 't' should be replaced by $\gamma$. l. 276 I think i should go between 1 and T-1. l. 309 quite.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The online method uses a surrogate loss using the observations, this is a reasonable choice due to lack of ground-truth states and the observability, which is a strong assumption. The paper should discuss the implications of using this loss with more general (i.e. non observable) systems.

Summary

This submission examines the learning of the Kalman filter gain for linear systems with unknown covariance matrices using noisy output data. Similar to learning the linear quadratic regulators for unknown linear systems, the learning problem here is posed as a stochastic policy optimization problem which minimizes the expected output prediction error. Bridging together the learning of kalman gain and the optimal control gain, the paper provides an interesting convergence analysis of stochastic gradient descent for the policy optimization problem, and bias-variance error bounds of the learning problem by employing a set of tools from linear systems and stochastic geometry.

Strengths

+) The learning of the Kalman gain as a stochastic policy optimization problem which is amendable to results and studies of learning linear quadratic regulators in the literature; +) the dual of learning the Kalman gain and the optimal control gain in the data-driven setting; +) biased gradients and stability constraints are strategically handled when learning the Kalman gain, along with the bias-variance error bounds.

Weaknesses

-) The setup is not very practical as the system matrices are assumed perfectlt known but only the covariance matrices are unknown; even in e.g., the stated application aircraft wign dynamics where only approximate models are known, one would assume imperfect knowledge of both the system matrices and covariance matrices; or identifying them via data-driven method first. -) For the learning problem described in lines 106-108, it is unclear whether the problem is well-posed in the sense that given these information (data), wheher one is able to learn the steady -state Kalman gain L_\infinity, or at least how large the horizon T shall be such that one will be able to have a unique L_\infty? -) In (1), are uncorrelated random vectors enough for deriving the optimal Kalman filter without mutually independent random noise vectors? Also in the formulation of (5), what are random quantities and do we have any condition expectations or not?

Questions

It would be great if the results can be compared with more related works on learning the Kalman filter under different settings; Zheng, Y. et al. Sample complexity of linear quadratic gaussian (LQG) control for output feedback systems. In Learning for dynamics and control (pp. 559-570). PMLR. Zhang, X. et al. Learning the Kalman filter with fine-grained sample complexity. arXiv preprint arXiv:2301.12624. In the behavioral theory literature, results are available for learning the Kalman filter for unknown linear systems by using data, although seemingly in addition to the noisy output data and also the pure state data, in e.g., Liu, W. et al. Learning Robust Data-based LQG Controllers from Noisy Data. arXiv preprint arXiv:2305.01417.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

NA

Summary

This paper focuses on learning the optimal filtering policy (Kalman gain) in a linear system with known system matrices and unknown covariance matrices of noise. The paper considers a proxy objective to avoid learning with hidden variables and characterizes a dual form of the objective, optimized subsequently using SGD. Convergence analysis and finite-time error bounds are provided.

Strengths

originality: studies a traditional Kalman filtering problem with a different setting and objective. The duality theory and the proposed method of optimizing the dual objective seem original. quality: provides detailed theoretical results and analysis. clarity: clearly formulate the setting. The whole picture from the background of Kalman filtering, problem setting, duality theory, to SGD convegence analysis is well organized and easy to follow.

Weaknesses

1. The paper lacks enough empirical experiments to support their idea. The only two figures appear in the supplementary materials, but the linear convergence outside a region near optimal, along with reasons why performances of the $M=20$ and $T=200$ case is different from other settings, is not presented clearly in this paper. It is suggested that: - the figures can be plot in the log scale to illustrate the linear convergence; also it is better to illustrate in the plot the scale of the "no-linear-rate" small region; - additional studies to demonstrate why medium hyperparameters $M=20$ and $T=200$, yield worst/best convergence rate among other hyperparameters (otherwise it is likely to think that the proposed SGD approach is not so robust to hyperparameters); - maybe comparison with some existing methods on real data is preferred. 2. The organization of this paper can be improved. For example, - numerical results can be put in main paper. - from my view, it is more natural to first characterize the bias in estimated gradient (Sec.4.2) and then provide convergence guarantees under such biased gradient (Sec.4.1). Otherwise, it may lead to confusion on the need of convergence analysis under biased estimates (e.g. the appeared $E$ in Lemma 5 & Proposition 2). 3. Some typos: - Eq.(3b) $P(T)$ should be $P(t).

Questions

None

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

The main limitation of the proposed approach is that the biased gradient causes the convergence rate to be linear only outside a small region near the true optimal value. It may not seem so preferable if the region is large, thus not ensuring exact convergence to optimal value.

Summary

This paper studies the learning of optimal steady-state Kalman filter gain for a linear dynamical system with known system matrices but unknown process and measurement noise covariances. In particular, the learning process involves minimizing the prediction error of the observed output using a dataset of independently realized observation sequences. Leveraging the duality between LQR control and Kalman filtering, the authors reformulate this learning problem as synthesizing an optimal control policy for an adjoint system and propose a stochastic gradient descent (SGD) algorithm algorithm to solve it. The authors also provide sample complexity and non-asymptotic error guarantees by conducting a convergence analysis of SGD accounting for biased gradients and stability constraints. In particular, they show that the bias-variance error bounds scale logarithmically in system dimension and that the variance term doe snot change with the horizon.

Strengths

I think this paper is well-written. The text is easy to read and and the technical details are mostly neatly presented. The analysis also makes sense although I didn't verify in detail. The results are fairly general and significant as the problem of unknown noise covariances in Kalman filtering should be practically relevant as well.

Weaknesses

I don't consider these as weaknesses necessarily but here are a few things I would recommend the authors to consider: 1. The results of remark 7 can be discussed earlier maybe within the informal theorem 1. 2. You might find it useful to adopt $(\kappa,\gamma)-$stability definition by Cohen et al. 2018 in your bounds involving $\sqrt{\rho(A_L)}$, especially in Lemma 6. 3.it wasn't clear to me in the first place why singularity of $H^TH$ requires a significantly different treatment than LQR case. maybe you can clarify this earlier in the text. 4. It would be helpful to discuss possible future directions.

Questions

I have a few questions to the authors out of curiosity. How essential is it to assume bounded noise for propositions 4 and 5? In figure 1a, could you explain why we see that M=10 case seems like the best performing , even better than M=30?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

4 excellent

Limitations

The authors already addressed some of the limitations such as the requirement for perfect knowledge of system matrices. I would also consider the bounded noise setting one of the limitations that might be improved in the future works.

Thanks for the rebuttal!

Thanks for the effort in addressing my concerns. I have read the rebuttal. I am satisfied with the response and do not have further questions.