Data-driven Optimal Filtering for Linear Systems with Unknown Noise Covariances
Authors: Shahriar Talebi
Amirhossein Taghvaei
Mehran Mesbahi
Venue: NeurIPS 2023 poster (2023)
Keywords: Optimal filtering
data-driven control
stochastic optimization
learning

Abstract: This paper examines learning the optimal filtering policy, known as the Kalman gain, for a linear system with unknown noise covariance matrices using noisy output data. The learning problem is formulated as a stochastic policy optimiza- tion problem, aiming to minimize the output prediction error. This formulation provides a direct bridge between data-driven optimal control and, its dual, op- timal filtering. Our contributions are twofold. Firstly, we conduct a thorough convergence analysis of the stochastic gradient descent algorithm, adopted for the filtering problem, accounting for biased gradients and stability constraints. Secondly, we carefully leverage a combination of tools from linear system theory and high-dimensional statistics to derive bias-variance error bounds that scale logarithmically with problem dimension, and, in contrast to subspace methods, the length of output trajectories only affects the bias term.

Data-driven Optimal Filtering for Linear Systems with Unknown Noise Covariances
Shahriar Talebi
Amirhossein Taghvaei! Mehran Mesbahi
University of Washington, Seattle, WA, 98105
Harvard University, Cambridge, MA, 02138
talebi@seas harvard. edu amirtagdus.com edu mesbahi@ux: edu
Abstract
This paper examines learning the optimal filtering policy, known as the Kalman gain, for a linear system with unknown noise covariance matrices using noisy output data. The learning problem is formulated stochastic policy optimiza- tion problem, aiming to minimize the output prediction error. This formulation provides direct bridge between data-driven optimal control and, its dual, op- timal filtering. Our contributions are twofold. Firstly. we conduct a thorough convergence analysis of the stochastic gradient descent algorithm,, adopted for the filtering problem, accounting for biased gradients and stability constraints. Secondly, carefully leverage combination of tools from linear system theory and high-dimensional statistics to derive bias-variance error bounds that scale logarithmically with problem dimension, and, in contrast subspace methods, the length of output trajectories only affects the bias term.
Introduction
The duality of control and estimation plays a crucial role in system theory, linking two distinct synthesis problems [ 2 5 6) This duality is effective bridge between two distinet disciplines, facilitating development of theoretical and computational techniques in one domain and then adopting them for in the other. For example, the stability proof of the Kalman filter relies on the stabilizing characteristic of the optimal feedback gain in the dual Linear Quadratic Regulator (LQR) optimal control problem 7 Ch. 9]. In this paper, we leverage this duality to learn optimal filtering policies using recent advances in data-driven algorithms for optimal control.
We consider the estimation problem for system with known linear dynamic and observation model, but unknown process and mcasurement noise covariances. Our objective is to learn the optimal stcady- state Kalman gain using training dataset comprising independent realizations of the observation signal. This problem has a rich history in system theory, often explored within the context of adaptive 12 [3]. A comprehensive summary of four solution approaches
Kalman filtering g 9
10
to this problem can be found the classical reference
[ These approaches include Bayesian 16] Maximum likelihood [17 18]. covariance matching [12], and innovation
inference [14 15.
correlation methods g 10]. While Bayesian and maximum likelihood approaches are computationally
intensive, and covariance matching introduces biases in practice, the innovation correlation-basee approaches have gained popularity and have been the subject of recent research
[19] 20 21.. For an
excellent survey on this topic, refer to the article (22). However, it is important to note that these approaches often lack non-asymptotic guarantees and heavily depend on statistical assumptions about the underlying model.
In the realm of optimal control, significant progress has been made in the development of data-driven synthesis methods. Notably, recent advances have focused on the adoption of first-order methods for state-feedback LQR problems (23 24). The direct optimization of policies from gradient-dominant
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

perspective has first proven in [25] to be remarkably effective with global convergence despite non-convex optimization landscape. It has been demonstrated that despite the non-convex nature of the cost function, when expressed directly in terms of the policy, first-order methods exhibit global convergence to the optimal policy. Building upon this line of work, the use of first-order methods for policy optimization has been explored in variants of the LQR problem. These include Output-feedback Linear Quadratic Regulators (OLQR) (26), model-free setup [27], risk-constrained setup (28) Linear Quadratic Gaussian (LQG) [29]. and most recently, Riemannian constrained LQR 30 These investigations have expanded the scope of data-driven optimal control, demonstrating the
versatility and applicability of first-order methods for wide range of synthesis problems.
The objective of this paper is to provide fresh insights into the classical estimation problem by leveraging the duality between control and estimation and incorporating recent advances in data- driven optimal control. Specifically, building on the fundamental connection between the optimal mean-squared error estimation problem and the LQR problem (Prop.[). we reformulate determining the optimal Kalman gain as a problem of synthesizing an optimal policy for the adjoint system, under conditions that differ from those explored in the existing literature (see (10) and Remark B}. Upon utilizing this relationship, we propose a Stochastic Gradient Descent (SGD) algorithm for learning the optimal Kalman gain, accompanied by novel non-asymptotic error guarantees in presence of biased gradient and stability constraint. Our approach opens up promising avenues for addressing the estimation problem with robust and efficient dataenriven techniques. The following is an informal statement of our main results (combination of Thm. and Thm. D and missing proofs appear in the supplementary materials.
Theorem 3 (Informal). Suppose the system is observable and both dynamic and measurement noise are bounded. Then, with high probability, direct policy updates using stochastic gradient descent with small stepsize converges linearly and globally (from any initaal stabilizing policy) to the optimal steady-state Kalman gain.
More recently, the problem of learning the Kalman gain has been considered from a system iden- tification perspective, for completely unknown linear systems [I 32 subspace system identification methods are used to obtain error bounds for learning the Markov parameters of the model over time horizon and establish logarithmic regret guarantee for output prediction error. Due to the inherent difficulty of learning a completely unknown stochastic system from partial observations, subspace methods assume marginal stability of the unknown system, and lead to sub-optimal sample complexity bounds that grow with the number of Markov parameters, instead of the number of unknowns (35 pp. 14]. Alternatively, [34] considers minimizing the output prediction error and introduces a model-free policy gradient approach, under the same stability assumptions, that achieves sublinear convergence rate. This paper provides a middle ground between completely known and completely unknown systems, for a learning scenario that not only has relevant practical implications, but also utilizes the duality relationship LQR to establish linear convergence rates even for unstable systems as long as they are observable. See the Appendix A for the discussion
B3
34). In [32 and [33),
of additional related works 36 37
2 Background and Problem Formulation
Herein, first we propose the model setup in detail and discuss the Kalman filter as the estimation strategy. Consider the discrete-time filtering problem given by the stochastic difference equations,
(I) where ztt)) R" is the state of the system, y(t) E T is the observation signal, and {E(t) hez and hez are the uncorrelated zero-mean random vectors, that represent the process and measure- ment noise respectively, with the following covariances,
x(t + 1) = (at)) + E(t), and y(t) = Hz(()) + w(t,,
E ((())(())] Q E m= E (+)(((()) R R m
for some positive (semi- )deniitee matrices Q R. z O. Let mn and Po z 0 denote the mean and covariance of the initial condition Zi-
In the filtering setup, the state xx()) is hidden, and the objective to estimate given the history of the observation signal (tt)) = (v(0), v())..... ..... y(t - 1)}. The best linear mean-squared ervor (MSE)
2

---

estimate of zzf) is defined according to
*(t) argmin aEC(())
E || =|
(2)
where [()(t)) denotes the space of all linear functions of the history of the observation signal (t).
the model parameters (A, H, Q. R) are known, the optimal MSE estimate #(l) can be recursively computed by the Kalman filter algorithm (2:
a(t+ 1) AF(() + (v)) Hz(()), a(0) = Ma.
(3a)
P(t AP(t) A(()))
P(0) = Po.
(3b)
where 8(1) HP(())++++RR R. L(t) == AP(I) is the Kalman gain, and P(t) =- [8((((t)-
((t))(x(t)
=[t))]] (0((=((()<((TTTT)
is the error covariance matrix.
Assumption The pair (A, H) is detectable, and the pair (A, Qb) is stabilizable, where Q is the unique positive semidefinite square root of Q.
Under this assumption, the error covariance P(I) converges steady-state value Pas, resulting in unique steady-state Kalman gain Lxx AP HT (HP HT + R) 12)-1pp (39 40. It is common to evaluate the steady-state Kalman gain T offline and use it, instead of (t), to update the estimate in real-time. Furthermore, establish that Kalman filter provides the best linear estimate of the states given the observations for minimizing the MSE criterion
note that the assumption of uncorrelated random vectors is sufficient to
2 Theorem 2].
2.1 Learning problem
Now, we describe our learning setup: 1) The system matrices A and H are known, but the process and the measurement noise covariances, Q and R, are not available. 2) We have access to oracle that generates independent realizations of the observation signal for given length T: {u(()) However, ground-truth measurements of the state xt)) is not available.
Remark Our proposed learning setup arises in various important engineering applications where merely approximate or reduced-order linear models are available due to difficulty in analytically capturing the effect of complex dynamics or disturbances, hence represented by noise with unknown covariance matrices. Additionally, the system identification procedure often occurs through the application of physical principles and collection of data from experiments in controlled environment (e.g., in wind tunnel). However, identifying the noise covariance matrices strongly depends on the operating environment which might be significantly different than the experimental setup. Therefore, it is common engineering practice to use the learned system matrices and tune the Kalman gain to this procedure for gust load alleviation in wings and [42] for estimation in chemical reactor models. We also emphasize that this learning setup has a rich history in adaptive filtering with numerous references with a recent survey on this topic (22). As part of our future research, we will carry-oul a robustness analysis, similar to its LQR dual counterpart performance.
improve the estimation error. We refer to 41 for the application
43 to study the effect the error in system matrices on the learning
Inspired by the structure of the Kalman filter, our goal is to learn the steady-state Kalman gain Loc from the data described in the learning setup:
Given: independent random realizations of (T(O) with the parameters A, H
Learn: steady-state Kalman gain T
For that, we formulate the learning problem as a stochastic optimization described next.
2.2
Stochastic optimization formulation
Define ăz (T') be the estimate given by the Kalman filter at time T realized by the constant gain L. Rolling out the update law 3a for = 0 to f = T - 1, and replacing L(t) with L, leads to the following expression for the estimate क (T) as function of L.
(T) = AT - ETD -/ Ly((),
(4)
3

---

where As := AH. Note that evaluating this estimate does not require knowledge of Q or R. However, is not possible to directly aim to learn the gain L by minimizing the MSE (2) because the ground-truth measurement of the state a(T)) is not available. Instead, we propose to minimize the MSE in predicting the observation (T) as a surrogate objective function!
ming J == E [Ilx(T) Dr (2))l2)
(5)
where (T) == (T). Note that while the objective function involves finite time horizon T, goal is to learn the steady-state Kalman gain 20
The justification for using the surrogate objective function in 55) instead of MSE error 2 lies in the detectability assumption | Detectability implies that all unobservable states are stable; other words, their impact on the output signal vanishes depending their stability time constant.
Numerically, the optimization problem (5) falls into the category of stochastic optimization and can be solved by algorithmss such as Stochastic Gradient Descent (SGD). Such an algorithm would need access independent realizations of the observation signal which are available. Theoretically however, it is not yet clear if this optimization problem is well-posed and admits a unique minimizer. This is the subject of following section where certain properties of the objective function, such as its gradient dominance and smoothness, are established. These theoretical results are then used to analyze first-order optimization algorithms and provide stability guarantees the estimation policy iterates. The results are based on the duality relationship between estimation and control that is presented next.
3 Estimation-Conti Duality Relationship
The stochastic optimization problem 3 is related to an LQR problem through the application of the classical duality relationship between estimation and control [45] Ch.7.5). In order to do so, we introduce the adjoint system (dual to (I) according to:
z(t) AT=(t 1)
=(T)
(6)
where zt) E IR" is the adjoint state and U(T) := (u()),... u(T)) E RTT are the control variables (dual to the observation signal ((()). The adjoint state is initialized at x(T)
E IR" and simulated backward in time starting with t = T 1. We introduce an LQR cost for the adjoint system:
JI (a, UT) = (o)) + Et= (==(==((((())) + u (1)
and formalize relationship between linear estimation policies for the system ① and linear control policies for the adjoint system (6). A linear estimation policy takes the observation history Vr E 1=T and outputs an estimate & c (T)) ;= C(Fr) where L R=T + 1²n is linear map. The adjoint of this linear map, denoted by L R" R TT is used to define control policy for the adjoint system (6) which takes the initial condition a E I2" and outputs the control signal Ugt = (a); i.e.
..0)......10 v( - 1)} م (T)
and [u(1), (T)) a.
The duality relationship between optimal MSE estimation and LQR control is summarized in the following proposition. The proof is presented in the supplementary material.
Proposition 1. Consider the estimation problem for the system ( and the LQR problem 7 subject
to the adjoint dynamics (6. For any linear estimation policy â (c( = L(YT), and for any a E R", we have the identity
E [IaTx(T) -T J (a, (g))),
where (T) L (a). In particular, for a Kalman filter with constant gain L, the output prediction error
E [Ilx(T) (T))) = Em J (Hr (T)) + tr [R]
(9)
where UL (T) = (TTT(11), gain LT, and H.- E TR." the i-th row of the m X n matrix for i 1, m.
(T)( i.e., the feedback control policy with constant
'The expectation in (5) is taken over all the random variables; consisting of the initial state xe. dynamic noise {()), and measurement noise w(t) for fort= = 0.... ,T. A conditional expectation is not necessary as the estimate is constrained to be measurable with respect to the history of observation.

---

Remark 2.
The duality is also true in the continuous- time setting where the estimation problem is related a continuous-time LQR. Recent extensions to the nonlinear setting appears in [46] with comprehensive study in [47] This duality is distinct from the maximum likelihood approach which involves an optimal control problem over the original dynamics instead of the adjoint system [5]
3.1 Duality in stcady-state regime
Using the duality relationship 9 the MSE in prediction 5 is expressed as:
J [.] = tr (XT(L))TH) + tr [R),
where = + + A/ (AT)) Define the set of Schur stabilizing gains
S (L e R=xm ((Ar) <
For any L E S, in the steady-state, state, the mean mean-squared prediction error assumes the form,
limr- (L) tr (Z) H] ir [R],
where (L) == limm- +oo (L) and coincides with the unique solution X of the discrete Lya- punov equation X = Ar,X AT, +Q+ LRLT (existence of unique solution follows from p(Ar, < 1). Given the steady-state limit, formally analyze the following constrained optimization problem:
min ((L) H(,) S.L. X(L) = (L)) A + Q LRLT. LES
(10)
Remark 3. Note that the latter problem is technically the dual of the optimal LQR problem as formulated in [23] by relating A ++ AT, -H + BT, L ++ KT, and HTH ++ Σ. However, the main difference here is that the product H H may not be positive definite, for example, due rank deficiency in H specially when m < n (whereas X(E) > 0 appears in all of the bounds in [25] 23)). Thus, general, the cost function [L) is not necessarily coercive L. which can drastically effect the optimization landscape. For the same reason, in contrast to the LQR case 25 23 the gradient dominant property of J (T.) not clear the filtering setup. the next section, we show that such issues can be avoided as long the pair (A, H) is observable. Also, the learning problem posed here distinct from its LQR counterpart (see Table
3.2 Optimization landscape
The first result is concerned with the behaviour of the objective function at the boundary of the optimization domain. It is known 48 that the set of Schur stabilizing gains S is regular open, contractible, and unbounded when m 2 2 and the boundary aS coincides with the set (L E Raxm;
p(A- LH) = 1}. For simplicity of presentation, we consider a slightly stronger assumption: Assumption 2. The pair (A, H) ) observable, and the noise covariances Q > 0 and R. 0.
Lemma 1. The function J()) S TR. is real-analytic and coercive with compact sublevel sets; i.e.,
L + 0S || + each implies J(L) - 00,
and S. = {L E R= J(L) S a} is compact and contained in S for any finite >> 0.
The next result establishes the gradient dominance property of the objective function. While this result is known in the LQR setting ([25) 23),, the extension to the estimation setup is not trivial as HT H. which takes the role of the covariance matrix of the initial state in LQR, may not be positive definite (instead, we only assume (A, If) is observable). This, apparently minor issue, hinders establishing the gradient dominated property globally. However, we recover this property on every sublevel sets of J which is sufficient for the subsequent convergence analysis.
Lemma 2. Consider the constrained optimization problem (10 T0een,,,
The explicit formula for the gradient of is: VJ(L) = =2Y(L) (-LR+ ALX(L)HTT) where Y(L) =Y is the unique solution of Y = ATY Ar. HTH.
The global minimizer I," = arg minses J(L) satisfies I,* A (R+ HX with X being the unique solution of X = A1-X X" AT, +Q + L'R
5

---

The function J(): So - R. for any non-empty sublevel set Sa. for some > 0, satisfies the following inequalities; for all S.:
G[ J(L') 02 L (VJ(L)
(11a)
Ca L' S -
(1lb)
[VJ(L) VJ(L') E P.
(11c)
for positive constants C1, 02, and & that are only function of and independent of L.
Note that the expression for the gradient is consistent with Proposition duality relationship explained in Remark
23 after applying
Remark 4. The proposition above implies that J(.) has the Polyak-Lojasiewiiie (PL) property (aka gra- dient dominance) on every Sa; i.e., for any L Sa we have (()) S cyta) (VJ(L), vJ(()). The inequality (aa)) is more general as it characterizes the dominance gap in terms of the iterate error from the optimality. This is useful in obtaining the iterate convergence results in the next section. Also, the Lipschitz. bound resembles its "dual" counterpart in [23] Lemma 7.9], however, it is not implied as simple consequence of duality because HT H may not be positive definite.
SGD for Learning the Kalman Gain
In order emphasize the estimation time horizon T for various measurement sequences, Drr == {t(t)) to denote the measurement time-span. Note that, any choice of L E S corresponds to filtering strategy that outputs the following prediction,
(T) = H.A.mo + Σ HAT---Lyy(
We denote the squared-nowe norm of the estimation error for this filtering strategy as,
=(L,)rr (1))
where (L( = y(T) - -9L (T). We also define the truncated objective function as
(L) = (L,))r)
where the expectation is taken over all possible random measurement sequences, and note that, the steady-state limit, we obtain limy- Jr JL).
The SGD algorithm aims solve this optimization problem by replacing the gradient, in the Gradient Descent (GD) update, with an unbiased estimate of the gradient in terms of samples from the measurement sequence. In particular, with access oracle that produces independent realization of the measurement sequence, say M random independent measurements sequences ( J the gradient can be approximated follows: denote the approximated cost value
Jr( = M En e (L, 3%+),
then the approximate gradient with batch-size M is V = 1 EM VLE(L, This forms
an unbiased estimate of the gradient of the "truncated objective", i.e., VJ. (T.) = VJ.(
Next, for implementation purposes, we compute the gradient estimate explicitly in terms of the measurement sequence and the filtering policy L.
Lemma 3. Given and a sequence of measurements y = {y(t))T=o) we have,
(LE(L,)) -2- (
T-
Finally, using this approximate gradient, the so-called SGD update proceeds as.
L La me V V (r()),
for is Z, where 7) >> the step-size. Numerical results of the application of this algorithm appears in Appendix G

---

Table 1: Differences between SGD algorithms for optimal LQR and optimal estimation problems
Problem
Parameters
Constraints
Gradient Oracle
cost value
and R
A and H
stability S
model
biased
LQR 25
known
known
unknown
yes
J(L rA)A]
yes
A U (S
Estimation (this work)
unknown
unknown
known yes
(V 3
yes
y output data
Vanila SGD
*
*
* no
Ve( )
no
y data dist.
Remark 5. Computing this approximate gradient only requires the knowledge of the system matrices A and H, and does not require the noise covariance information Q and R. Simulation results for the SGD algorithm are provided in the supplementary material.
Although the convergence of the SGD algorithm expected to follow similar the GD algorithm under the gradient dominance condition and Lipschitz property, the analysis becomes complicated due the possibility of the iterated gain L3 leaving the sub-level sets, is expected that a convergence guarantee would hold under high- gigh-rrbbbbiltyy due to concentration of the gradient estimate around the true gradient. The complete analysis in this direction is provided in the subsequent sections.
We first provide sample complexity and convergence guarantees for SGD with a biased estima- tion of gradient for locally Lipschitz objective functions and in presence of stability constraint S. Subsequently, we study the stochastic problem of estimating the gradient for the estimation prob- lem. Distinct features of our approach as compared with similar formulations in the literature highlighted in Table !
We now provide road map to navigate the technical results that concludes with Theorem B Section 4.1 is concerned with the convergence analysis of the SGD algorithm under an assumption for the biased gradient oracle, summarized in Theorem I which concludes the linear convergence of the iterates for sufficiently small stepsize. Section 4.2 is concerned with the bias-variance error analysis of the gradient estimate, summarized in Theorem Pheeremmprovviii providing the sufficient values for the batch-size and trajectory length that guarantees the desired bound on the gradient oracle required in Theorem Finally, combining the results from Theorem I and Theorem 2 concludes main result
in Theorem 3
4.1 SGD with biased gradient and stability constraint
First, we characterize the "robustness" of policy at which we aim to estimate the gradient. This is formalized in the following lemma which is a consequence 30 Lemma IV.1].
Lemma 4. Consider any L E S and let Z be the unique solution of 2 = A,, ZA,, + +Afor any A > 0. Then, L + A E S for any A E Æaxm satisfying 0 < || < / X(Z)
Second, we provide a uniform lowerbound for the stepsize of gradient descent for an approximated direction "close" to the true gradient direction.
Lemma 5 (Uniform Lower Bound on Stepsize). Let Lg Sq for some a 2 a* J(L"), and choose any finite 8 2 a. Consider any direction E such that ||E -JJ(()) S >/[v)((Lo)l for some 7 E [0, 1), then we have [Lo nE)= S 3 for any n7 satisfying:
1-2 1 osns ( 1)2 ((B) Ela)[a arl
ca(a)
3
20(33)
Remark 6. Note that for the case of exact gradient direction, i.c. when E = (Lo), we have = 0 and choosing 3 = implies the known uniform bound of 7) S शाक for feasible stepsizes as expected. Also, by this choice of 8, this guarantees that the next iterate remains in sublevel set S,, This lemma generalizes this uniform bound for general directions and (potentially) larger sublevel set.
7

---

The next proposition provides a decay guarantee for one iteration of gradient descent with an approximate direction which will be used later for convergence SGD with biased gradient estimate.
Proposition (Linear Decay in Cost Value). Suppose Lo E So for some a > and a direction E + is given such that J(.)ll S ([.) r for some 7 < 1. Let (1-9)/(++ 1()) Then, L1 = To i remains in the same sublevel set, ie., In E Sax Furthermore, we obtain the following linear decay of the cost value:
((L)-J(A) (1- (|0-0(0000-0)))10100 J(L")
Next, we guarantee that SGD algorithm with this biased estimation of gradient obtains a linear convergence rate outside a small set C- around optimality defined as
C = ( E ||VJ]L)) S so/T),
for some T E (0, 1) and arbitrarily small so > 0. First, we assume access to the following oracle that provides a biased estimation of the true gradient.
Assumption Suppose, for some a > 0, we have access biased estimate of the gradient V J(L) such that, there exists constants 8, 80 > 0 implying [VL - VJ(LI) S J[)V + 80 for all I. Sa |Cr.
Theorem 1 (Convergence). Suppose Assumption 3 holds with small enough and such that 8 S 7/2 and Sa CC2/2 is non-empty for some 7 E (0,1), Then, SGD algorithm starting from any Lo E S, CCuf2 with fixed stepsize îj []+1)=[(a] generates sequence of policies {LR} that are stable (i.e. each Lg Sa) and cost values decay linearly before entering C2/22 i.e,
(1-a)
cI J(Lx) J(L')( -()0)) 21/2 (J(L)) -(L'))-((LL))
for each l 2 O uuless L, E 22 for some j S k.
Remark 7. By combining Theorem and the PL property the cost in (1la), we immediately obtain 1/2, then in order to guarantee
sample complexity for our algorithm; e.g., choose
the cost (Lx) ((L)) < E, suffices to have a small enough bias term so S (o1 and variance
coefficient for the oracle, and run the SGD algorithm for ln(2)/ In(1 I8((a) )) steps.
4.2 Observation model for the estimation problem
Herein, first we show that the estimation error and its differential can be characterized as "simple norm" of the concatenated noise (Proposition (3. This norm is induced by metric that encapsulates the system dynamics which is explained below. Before proceeding to the results of this section, we assume that both the process and measurement noise are bounded:
Assumption 4. Assume that (almost surely) || [|{())] S Kg and [|((()] S Kus for all t. Also, for simplicity, suppose the initial state has mean, i.e., Mgg 0n.
For two vectors E, v E (T+1)), we define
(G, T) = tr ( A[HTHAL))
where AG = (49, A
AF) Also, define ML[E] = (Mo
M ... Mr(
with (F = 0, [F] FH and M++1 [F] = Ei A F AT for T -1 Proposition 3. The estimation error ELL,Yr) takes the following form
c(L,Jr) | 11a_.
where Th غ - (I L)ø with E" (E(T - 1)T E(O) =())T) and W (W(T- - T)T w(OT OT,)
Furthermore, its differential aets on small enough E E Roxm as,
de(,, vrr (L) -2 (T 8 () (X,N111 where X2 = T. and [B] = MM + (.
8

---

Now, we want to bound the error in the estimated gradient (L) by considering the concentration error (on length trajectories) and truncation error separately as follows:
(L)
[V) = -++(()) IVJ+(L) VJIIII
recalling that Jz( = E [=(L,)/))] by definition.
Next, we aim to provide the analysis of concentration error trajectories of length 7 with probability bounds. However, for any pair of real (T x - M and N, by Cauchy Schwartz inequality we obtain that |tr [M S || I| M I [T]] This bound becomes loose (in terms of dimension 7) the condition number of N increases
Nonetheless, we are able to provide concentration error bounds that "scale well with respect to the length 7" that hinges upon the following idea: from von Neumann Trace Inequality 44 Theorem 8.7.6] one obtains,
|tr [MN] S E. (.MM), & |
(12)
where || = tr VNTN = - (N) is the nuclear norm with or (N) denoting the i-th largest singular value of N. Additionally, the same inequality holds for non-square matrices of appropriate dimension which is tight in terms of dimension.
Proposition (Concentration Error Bound). Consider M independent length T trajectories ()+)
and suppose Assumption holds. Let (T(. = M E Ve(L, then any 8 > 0,
-Ms2/2
P (L) V-)( S 2n exp
17 + 2218/3
where Vr. = 4x |1111/11 (p(Ar))) with Kr. Kig + ||]||riw
We can also show how the truncation error decays linearly as T grows, with constants that are independent of the system dimension
Proposition 5 (Truncation Error Bound). Under Assumption 4 the truncation error is bounded:
[V - (JI( S 92 vp(At) T+1
where PL= 10
|| p(AL)]²
Remark 8. Notice how the trajectory length T determines the bias in the estimated gradient. However, the concentration error bound is independent of T and only depends on the noise bounds proportionate to Kigz Kig and the stability margin of A proportionate to C2/
%
Finally, by combining the truncation bound in Proposition with concentration bounds in Proposi- tion 4 we can provide probabilistic bounds on the "estimated cost" J, (Z. and the "estimated gradient" Jrr L.). Its precise statement is deferred to the supplementary materials (Theorem)
4.3 Sample complexity of SGD for Kalman Gain
Note that the open-loop system may be unstable. Often in learning literature, it is assumed that the closed-loop system can be contractible ( (ie.,, the spectral norm |r.r.] < 1) which is quite convenient for analysis, however, it is not reasonable system theoretic assumption. Herein, we emphasize that only require the close-loop system to be Schur stable, meaning that p(Az) 1; yet, it is very well possible that the system is not contractible. Handling systems that are merely stable requires more involved system theoretic tools that are established in the following lemma.
Lemma 6 (Uniform Bounds for Stable Systems). Suppose L. E S, then there exit a constants C₁ > 0 such that
| & CL vp(AL) Yk 2
Furthermore, consider S., for some Pa E 1) such that [[]] < D.,, C₁ S Ca. and p(Ar,) S Pa for all L E S,-
O, then there exist constants D.. > 0, C. and
"The reason is that the first equality is sharp whenever M is in the "direction" of N. while the second inequality is sharp whenever condition number of M close to

---

The following result provides sample complexity bounds for this stochastic oracle to provide a biased estimation of the gradient that satisfies our oracle model of SGD analysis in Assumption B
Theorem 2. Under the premise of Proposition f consider Sa for some and choose any 8, 80 >
O and T E (0, 1). Suppose the trajectory length T 2 In (Nav (aa/min(n,, m)/so) In (1/ (Pa) and the
batch size M 4 min(n, m) ln(2n/6) (s su)², where %a 10(kg Da | |
and V 5 | [1 (Ki Da //11 VPals. Then, with probability no less than 1 6,
Assumption 3 holds.
Proof. First, note that for any L S., by Lemma 6 we have that 7.. S Tox and VT. S Va- Then, note that the lower bound on T implies that "a v minn (n, /) T+1 I 80- The claim then follows by applying Theorem 5 and noting that for any L & C, the gradient is lowerbound as [VJ(L]] > 50/T.
Theorem 3. Consider the linear system (1) under Assumptions@andda Suppose the SGD algorithm is
implemented with initial stabilizing gain Lo, the step-size vj == se(a(ha)) for k itenations, a batch-size
of M, and data- lenghh T. Then, VE > 0 and with probability larger than 1 8, ((L)) - J(=)) SE
if
T T2 ((n())
M 2 0 In( In(ln(-)). and k (lm(()))
(13)
Proof of Theorem 3 Recall that according to Remark | in order to obtain E error the cost value we require hs 2 ((n((1/)) of SGD algorithm using gradient estimates with small enough bias
term 80 I Veilate and variance coefficient s 1 Now, we can guarantee Assumption holds for such 8p and s (with probability at least 1 - 5) by invoking Theorem 2 In fact, it suffices to ensure that the length of data trajectories T and the batch size M are large enough; specifically, T 2 O(Im(1/50)) = ([Im(1/s) and by using union bound for bounding the failure probability M 2 ((In(1/8) ((n()//) /=)) = (1m(1/)) ln((n()/E))/E).
5 Conclusions, Broader Impact, and Limitations
In this work, we considered the problem of learning the optimal (steady-state) Kalman gain for linear systems with unknown process and measurement noise covariances. Our approach builds on the duality between optimal control and estimation, resulting in a direct stochastic Policy Optimization (PO) algorithm for learning the optimal filter gain. We also provided convergence guarantees and finite sample complexity with bias and variance error bounds that scale well with problem parameters. In particular, the variance is independent of the length of data trajectories and scales logarithmically with problem dimension, and bias term decreases exponentially with the length.
This work contributes generic optimization algorithm and introduces a filtering strategy for estimat- ing dynamical system states. While theoretical, raises privacy concerns similar the model-based Kalman filter. Limitations include the need for prior knowledge of system parameters; nonetheless, parameter uncertainties can be treated practically as process and measurement noise. Finally, sample complexities depend on the stability margin v A())), inherent to the system generating the data.
Finally, a direction for future research is to study how to adapt the proposed algorithm and error analysis for the setting when single long trajectory is available opposed to several independent trajectories of finite length. Another interesting direction is to carry out a robustness analysis, similar to its LQR dual counterpart, study the effect of the error in system parameters on the policy learning accuracy. Of course, the ultimate research goal is to use the recently introduced duality in nonlinear filtering [7 as bridge bring tools from learning to nonlinear filtering.
Acknowledgments and Disclosure of Funding
The research of A. Taghvaei has been supported by NSF grant EPCN-2318977, S. Talebi and M. Mesbahi have been supported by NSF grant ECCS-2149493 and AFOSR grant FA9550-20-1-005: The authors are also grateful for constructive feedback from the reviewers.
10

---

References
[1] R. E. Kalman, "On the general theory of control systems," in Proceedings First International Conference on Automatic Control, Moscow, USSR, pp. 481-492, 1960.
[2] R. E. Kalman, "A new approach to linear filtering and prediction problems," ASME. Journal of Basic Engineering, vol. 82, pp. 35-45, 03 1960.
[3] J. Pearson, "On the duality between estimation and control," SIAM Journal Control, vol. no. 4, pp. 500, 1966.
[4] R. Mortensen, "Maximum-likeline Theory and Applications, vol. 2, no. 6, pp. 386-394, 1968.
recursive nonlinear filtering," Journal of Optimization
[5] A. Bensoussan, Estimation and control of dynamical systems, vol. 48. Springer, 2018.
[6] W. H. Fleming and S. K. Mitter, "Optimal control and nonlinear filtering for nondegenerate diffusion processes," " Stochastics: An International Journal of Probability and Stochastic Processes, vol. 8, no. 1. pp. 63-77, 1982.
[7] J. Xiong, An Introduction to Stochastic Filtering Theory, vol. 18. OUP Oxford, 2008.
[8] R. Mehra, "On the identification of variances and adaptive Kalman filtering," IEEE Transactions on Automatic Control, vol. 15, no. 2, pp. 175-184, 1970.
[9] R. Mehra, "Approaches to adaptive filtering." IEEE Transactions on Automatic Control, vol. 17, no. 5, pp. 693-698, 1972.
[10] B. Carew and Belanger, "Identification of optimum filter steady-state gain for systems with unknown noise covariances," IEEE Transactions on Automatic Control, vol. 18, no. 6, pp. 582-587, 1973.
[11] R. Belanger, "Estimation of noise covariance matrices for a linear time-varying stochastic process," Automatica, vol. 10, no. 3, pp. 267-275, 1974.
[12] K. Myers and B. Tapley, "Adaptive sequential estimation with unknown noise statistics," JEEE Transactions Automatic Control, vol. 21, pp. 520-523, 1976.
[13] K. Tajima, "Estimation of steady-state Kalman filter gain," IEEE Transactions Automatic Control, vol. 23, no. 5, pp. 944-945, 1978.
[14] D. Magill, "Optimal adaptive estimation sampled stochastic processes," JEEE Transactions on Automatic Control, vol. 10, no. 4, pp. 434-439, 1965.
[15] C. G. Hilhorn and D. G. Lainiotis, "Optimal estimation in the presence of unknown parameters," IEEE Transactions on Systems Science and Cyhernetics, vol. 5, no. 1, pp. 38 38-43, 1969.
[16] Matisko and V. Havlena, "Noise covariances estimation for Kalman filter tuning." IPAC Proceedings Volumes, vol. 43, no. 10, pp. 31-36, 2010.
[17] R. Kashyap. "Maximum likelihood identification of stochastic linear systems," IEEE Transac- fions on Automatic Control, vol. 15,
pp. 25-34, 1970.
[18] R. H. Shumway and D. S. Stoffer, "An approach to time series smoothing and forecasting using the EM algorithm,"" Journal of Time Series Analysis, vol. 3, no. 4, pp. 253-264, 1982.
[19] B. J. Odelson, M. R. Rajamani, and B. Rawlings, "A new autocovariance least-squares method for estimating noise covariances," Automatica, vol. 42, no. pp. 303-308, 2006.
[20] B. M. Åkesson, J. B. Jørgensen, N. K. Poulsen, and S. B. Jørgensen, "A generalized autoco- variance least-squares method for Kalman filter tuning," Journal of Process Control, vol. 18, no. 7-8, pp. 769_779, 2008
[21] Duník, M. Simandl, and O. Straka, "Methods for estimating state and measurement noise covariance matrices: Aspects and comparison," IFAC Proceedings Volumes, vol. 42, no. 10, 372-3777 2009.
[22] L. Zhang, D. Sidoti, A. Bienkowski, K. R. Pattipati, Y. Bar- Shalom, and D. L. Kleinman, "On the identification of noise covariances and adaptive Kalman filtering: A new look at 50 ycar-old problem," " IEEE Access, vol. 8, pp. 59362-59338 59388, 2020.
[23] Bu, A. Meshahi, M. Fazel, and M. Mesbahi, "I.QR through the lens of first order methods: Discrete-tin time case," arXiv preprint arXiv:1907.08920 2019.

---

[24] J. Bu, A. Mesbahi, and M. Mesbahi, "Policy gradient- algorithms for continuous-time linear quadratic control," arXiv preprint arXiv:2006.091755 2020.
[25] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi, "Global convergence of policy gradient methods for the linear quadratic regulator:" in Proceedings of the 35th International Conference on Machine Learning, vol. 80, pp. 1467-1476, PMLR, 2018.
[26] I. Fatkhullin and B. Polyak, "Optimizing static linear feedback: Gradient method," SIAM Journal on Control and Optimization, vol. 59, no. 5, pp. 3887-3911, 2021.
[27] H. Mohammadi, M. Soltanolkotabi, and M. R. Jovanovic, "On the linear convergence of random search for discrete-time LQR," IEEE Control Systems Letters, vol. 5, no. 3, pp. 989-994, 2021.
[28] F. Zhao, K. You, and T. Başar, "Global convergence of policy gradient primal-dus methods for risk visk-constrained L.QRs," arXiv preprint arXiv:2 104.04901, 2021.
[29] Y. Tang, Y. Zheng, and N. Li, "Analysis of the optimization landscape of linear quadratic gaussian (LQG) control," in Proceedings of the 3rd Conference on Learning for Dynamics and Control, vol. 144, pp. 599-610, PMLR, June 2021.
[30] S. Talebi and M. Mesbahi, "Policy optimization over submanifolds for constrained feedback syn- thesis," IEEE Transactions on Automatic Control (to appear), arXiv preprint arXiv:2201. 11157, 2022.
[31] S. Lale, K. Azizzadeneshelii B. Hassibi, and A. Anandkumar, "Logarithmic regret bound in partially observable linear dynamical systems," Advances in Neural Information Processing Systems, vol. 33, pp. 20876-20888, 2020.
[32] A. Tsiamis and G. J. Pappas, "Finite sample analysis of stochastic system identification," " in 2019 IEEE 58th Conference on Decision and Control (CDC), pp- 3648-3654 IEEE, 2019.
[33] A. Tsiamis and G. Pappas, "Online learning of the Kalman filter with logarithmic regret," IEEE Transactions on Automatic Control, vol. 68, no. 5, pp. 2774-2789, 2023.
[34] J. Umenberger, M. Simchowitz, J. Perdomo, K. Zhang, and R. Tedrake, "Globally convergent policy search for output estimation," in Advances in Neural Information Processing Systems (S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, eds.), vol. 35, pp. 22778- 22790, Curran Associates, Inc., 2022.
[35] A. Tsiamis, I. Ziemann, N. Matni, and G. J. Pappas, "Statistical learning theory for control: A finite sample perspective," arXiv preprint arXiv:2209.05423, 2022.
[36] Y. Zheng, L. Furieri, M. Kamgarpour, and N. Li, "Sample complexity of linear quadratic gaussian (LQG) control for output feedback systems," in Proceedings of the 3rd Conference on Learning for Dynamics and Control (A. Jadbabaie, J. Lygeros, G. J. Pappas, P. A.Paariioo, B. Recht, J. Tomlin, and M. N. Zeilinger, eds.), vol. 144 of Proceedings of Machine Learning Research, pp. 559-570, PMLR, 07 - 08 June 2021.
[37] X. Zhang, B. Hu, and T. Başar, "Learning the Kalman filter with fine-grained sample complexity." in 2023 American Control Conference (ACC), pp. 4559-4554, 2023.
[38] W. Liu, J. Sun, G. Wang, F. Bullo, and J. Chen, "Learning robust data-based LQG controllers from noisy data," " arXiv preprint arXiv:2305.00 011471, 2023.
[39] H. Kwakernaak and R. Sivan, Linear Optimal Control Systems, vol. 1072. Wiley- filyy-interscience, 1969.
[40] Lewis, Optimal Estimation with an Introduction to Stochastic Control Theory. New York, Wiley-Interscieene,, 1986.
[41] K. A. Hinson, K. A. Morgansen, and E. Livne, "Autocovariance least squares noise covariance estimation for a gust load alleviation test-bed," in AIAA SCITECH 2022 Forum, p. 0617, 2022.
[42] B. Odelson, A. Lutz, and J. B. Rawlings, "TTh autocovariance least-squares method for estimating covariances: Application to model-based control of chemical reactors," JEEE Trans- actions on Control Systems Technology, vol. 14, no. 3, pp. 532-540, 2006.
[43] M. Safonov and W. Wang, "Singular value properties of LQ regulators." IEEE Transactions on Automatic Control, vol. 37, no. 8, pp. 1210-1211, 1992.
[44] C. Chen and A. Holohan, "Stability robustness of linear quadratic regulators," International Journal of Robust and Nonlinear Control, vol. 26, 9, pp. 1817-1824, 2016.
12

---

[45] K. J. Aström, Introduction to Stochastic Control Theory. Courier Corporation, 2012.
[46] J.-W. Kim, P. G. Mehta, and S. P. Meyn, "What is the lagrangian for nonlinear filtering?." in
2019 IEEE 58th Conference on Decision and Control (CDC), pp- 1607-1614, IEEE, 2019.
[47] J. W. Kim, "Duality for nonlinear filtering," arXiv preprini
2022.
[48] J. Bu, A. Mesbahi, and M. Mesbahi, "On topological and metrical properties of stabilizing feedback gains: The MIMO case," arXiv preprint (rXiv:/904.027377 2019.
[49] R. A. Horn and C. R. Johnson, Matrix Analysis. Cambridge University Press, 2012.
[50] H. Mohammadi, A. Zare, M. Soltanolkotabi, and M. R. Jovanović, "Convergence and sample complexity of gradient methods for the model-free linear-quadratic regulator problem," IEEE Trunsactions Automatic Control, vol. 67, no. 5, pp. 2435-2450, 2021.
[51] A. Beck, First-Order Methods in Optimization. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017.
[52] A. Cohen, A. Hasidim, T. Koren, N. Lazic, Y. Mansour, and K. Talwar, "Online linear quadratic control," in Proceedings of the 35th International Conference on Machine Learning (J. Dy and A. Krause, eds.), vol. 80 of Proceedings of Machine Learning Research, pp. 1029-1038, PMLR, 10-15 Jul 2018.
[53] N. J. Higham, Functions of Matrices: Theory and Computation. SIAM, 2008
[54] A. Tropp, "An introduction matrix concentration inequalities," Foundations and Trends@
in Machine Learning, vol. 8, no. 1-2, pp. 1-230, 2015.
[55] S. Talebi, A. Taghvaci, and M. Mesbahi, "SGD for Filtering," Oct. 2023. Available on GitHub htapps////gttuub..cc///hhaaaaara
13

---

Contents
Introduction
2
Background and Problem Formulation
2.1
Learning problem
2.2
Stochastic optimization formulation
3
Estimation-Control Duality Relationship
3.1
Duality in steady state regime
3.2
Optimization landscape
SGD for Learning the Kalman Gain
SGD with biased gradient and stability constraint
4.2
Observation model for the estimation problem
4.3
Sample complexity SGD for Kalman Gain
5
Conclusions, Broader Impact, and Limitations
10
Discussion of additional related works
15
Summary of Assumptions
15
Proof of the duality relationship: Proposition] 1
16
Proofs for the results for the analysis of the optimization landscape
17
D.I
Preliminary lemma
17
D.2
Proof of Lemmall
17
D.3
Derivation the gradient formula in Lemma
18
D.4
Proof of existence of global minimizer Lemma
19
D.5
Proof of gradient dominance property in Lemmal
19
D.6
Proof of Lipschitz property in Lemma
21
D.7
Gradient Flow (GF)...
22
D.8
Gradient Descent (GD)
23
Proofs for the analysis of the constrained SGD algorithm
24
E.
Proof of lemma])
3
Derivation of stochastic gradient formula
24
Proof of Lemma
Robustness of the policy with respect perturbation
24
Proof of Lemma
5
Uniform lower-bound on stepsize
24
Proof of Proposition 2
Linear decay in cost value
25
E.5
Proof of Theorem
Convergence of SGD algorithm
26
Proofs of the result for observation model and sample complexity
27
Preliminary lemmas and their proofs
27
14

---

F2
Proof of Proposition 3] The Observation model
30
Proof of Proposition
Concentration bounds
30
Proof of the Proposition
Truncation error bound
33
F5
Complete version of Theorem
Sample complexity bounds for the stochastic oracle
34
F6
Additional concentration bound results
35
Numerical Results
37
H
Nomenclature
37
Appendix A
Discussion of additional related works
After the initial submission of this manuscript, we encountered the following related works, and we will now briefly discuss their connections and differences in relation to work: [36] establishes an end-to-end sample complexity bound on learning a robust LQG controller (which is different than our filtering problem). As the system parameters also unknown, this work only considers the open-loop stable systems. Additionally, it establishes a nice trade-off between optimality and robustness characterized by suboptimality performance bound result of the robust LQQ design. While our filtering design is based on the knowledge of system parameters, we do not consider the open-loop stability assumption; and the robust synthesis is included as one of the main future directions of this work. Furthermore, the complexity bounds in [36] depends on the length of trajectory, whereas ours does not. Also, their suboptimality bound scale as O(1/VN) in the number of trajectories, whereas ours scales as O11/N). Next, [37] similarly considers the problem of learning the steady-state Kalman gain but in a different setup: The model is assumed to be completely unknown. However, the algorithm requires access to a simulator that provides noisy measurement of the MSE [[[] {t) [[?] which requires generation of ground-true truth state trajectories (() (see Assumption 3.2 therein). The proposed approaches are different: zeroth-order global optimization (theirs) vs first-order stochastic gradient descent (ours). The analysis reports O) sample complexity on optimal policy error which aligns with our result. However, it is difficult to provide more detailed comparison as explicit dependence the error terms on problem dimension is not provided. Finally, [38] considers the problem of simultaneously learning the optimal Kalman filter and linear feedback control policy in the LQG setup. Their approach involves solving Semidefinite Programmings (SDP) using paput-state-outpee trajectories. Their result, for the the when trajectories involve noise, relies on the assumption that the magnitude of the noise can be made arbitrary small. This is in contrast our setup where only assume bound the noise level and do not require access to state trajectories.
Appendix B Summary of Assumptions
Herein, we provide a summary of all assumptions considered in our work and their relation to our results.
Note that if the given pair (A, H) of system parameters is not detectable, then the estimation problem not well veleep simply because there may not exist any stabilizing policy Lo- Therefore, we consider the minimum required assumption for well-posedness of the problem follows:
Assumption The pair (A, H) is detectable, and the pair (A, Q+) is stabilizable, where Q à is the unique positive semidefinite square root of Q.
indeed possible to work with the weaker conditions compared with Assumption D and obtain similar results presented here-by incorporating more system theoretic tools. However, in order to improve the clarity of the learning problem with less system theoretic technicalities, work with the following stronger assumption in lieu of Assumption] T
Assumption 2. The pair (A, H) is observable, and the noise covariances Q > 0 and R > 0.
It is clear that Assumption 2 implics Assumption D
15

---

Next, in order to provide an independent analysis of the SGD algorithm for locally Lipschitz functions in presence of gradient bias, we consider the following assumption on the gradient oracle.
Assumption Suppose, for some a > 0, we have access to a biased estimate of the gradiens V (IL) such that, there exists constants 5, So > 0 implying [V - F S { + 50 fo all L E S. CG.
Next, in order to utilize the complexity analysis of SGD algorithm provided in Theorem I we need to build an oracle that satisfies Assumption 3 This is oracle is built in Section 4.2, building on the following assumptions on the process and observation noise.
Assumption 4. Assume that (almost surely) ||zoll, [|E())] S Kg and [[((t]] S Now for all t. Also, for simplicity, suppose the initial state has zero mean, L..., mg = O,,
Then, based on this assumption,
provides lowerbounds on the trajectory length and the batch-size in order for the oracle to satisfy Assumption Finally, the combined version of our results is presented in Theorem 3
Appendix C Proof of the duality relationship: Proposition |
By pairing the original state dynamics ① and its dual 6 =(t 1)Ta(t + 1) =(() xx()) =0t + T)TE(() u(t 1)(++))THa()
Summing this relationship from / to / T 1 yields,
T-1 1
z (T) (()) +
Σ + ()T(()))())) + u(t + 1)T Hx()).
t=
Upon subtracting the estimate a (T using the adjoint relationship
T Σ
1(1+1))((0=a445)) = (T)
(14)
and =(T) = a, lead to a a'x(T)-a
z(0)T=(0)
+ z(t 1)TE(t) - u(t 1)T
Squaring both sides and taking the expectation concludes the duality result in (8). Consider the adjoint system (6 with the linear feedback law u(t) = LT)(t). Then,
z(t) (AI) a, for t= 0, I.....T. Therefore, as function of a. u(t) LT These relationships are used to identify the control policy
(15)
(a) (u M(T) (LT LTa). This control policy corresponds to estimation policy by the adjoint relationship 14
T-1
a a dT)((T)= d'A - - Ly((t, Va E R..
t=
This relationship holds for all a E R". Therefore,
T-1
Tc(T)
*
A Af-+-1 Ly((t) Σ 1=0
which coincides with the Kalman filter estimate with constant gain L given by the formula (4) (with mo = 0). Therefore, the adjoint relationship (14) relates the control policy with constant gain LT to the Kalman filter with constant gain L. The result (9) follows from the identity
E [[lv(T) - Uz
ΣE E [ (1) + [R)
and the application of the first result
9 with H..
16

---

Appendix D Proofs for the results for the analysis of the optimization
landscape
D.1 Preliminary lemma
The following lemmas are direct consequence of duality and useful for our subsequent analysis. Lemma 7. The of Schur stabilizing gains S is regular open, contractible, and unhounded when m 2 2 and the boundary as coincides with the set {L E R==xm p(A LH) = 1}. Furthermore, (.) is real analytic on S.
The proof then follows identical to 23 Lemmas 3.5 and 3.6] by noting that the spectrum of matrix is identical to the spectrum of its transpose. D
Proof. Consider the duality described in Remark 3
Next, we present the proof of Lemma that provides sufficient conditions to recover the coercive property of ((.) which resembles Lemma 3.7 in 23 (but extended for the time-varying parameters). The proof is removed on the account of space and appears in the extended version of this work. Remark This approach recovers the claimed coercivity also in the control setting with weaker assumptions. In particular, using this result, one can replace the positive definite condition on the covariance of the initial condition in 23 i.e., Σ > 0, with just the controllability of (A, E1/2).
D.2 Proof of Lemma
Proof. Consider any L E S and note that the right eigenvectors of A and Ar. that are annihilated by H are identical. Thus, by to observability of (A H). Therefore, there exists a positive integer no S n such that (AI)"=-IHT)
(PBH) test, observability of (A, H) is equivalent
H (L) = (HT ATTT full-rank, implying that H7, (L) (I) is positive definite. Now, recall that for any such stabilizing gain L, we compute
J(L)
(RL)
no
(An) motth (Q LRL (RLT)(AT)) notth HTH
(AL))ol not nO + LRLT)(AT) not HT (L) (L)
tr [X (L.HTT
no (n.) (T.)
where we used the cyclic property of trace and the inequality follows because for any PSD matrices Pl, P2 2 0 have
tr [.P = tr P 20.
(16)
Also, Xno (L) is well defined because Ar, is Schur stable if and only if (At) is. Moreover, Xno (L) coincides with the unique solution to the following Lyapunov equation
Xno (L) (Az)"o Xno Xom (L) no + Q LRLT.
Next, R 2 0.
J(L) 2 AHH HL) (L)) (nn(L))
2 A(HT (L) (L))tr
Σ (AL) ((AA) not
2 (L) (L)) [(AT) not (Al) not]
2 (L) (L)) x(Q)
Σ Snot
(17)
0=
17

---

where the last inequality follows by the fact that
tr Mo (M) = II(A)) 1|? 2 [I(A)) not llop z (((AL)matt p(AL) 2m
with llop denoting the operator norm induced by 2-norm. Now, by Lemma 7 and continuity of
the spectral radius, as L - aS we observe that p(AL. - 1. But then, the obtained lowerbound implies that J (Lx) + oc. On the other hand, as Q 0, R > are both time-independent, by using similar technique we also provide the following lowerbound
J(L) 2tr (Q + LRIT)
(AL) not HT. (L) (A))
2 HH (L)H (L)) + LRL
XHT (L) (L))tr [RLLT]
AHH (L) (L)) X(R)
where || denotes the Frobenius norm. Therefore, by equivalency of norms finite dimensional
spaces, || || - oo implies that J( ) + oo which concludes that J(.) is coercive on S. Finally, argue that (T.) oc, therefore the sublevel sets S C S
note that for any T. E S, by (17) whenever a is finite. The compactness of S is then a direct consequence of the coercive property and continuity of (.) (Lemma
D.3 Derivation of the gradient formula in Lemma 2
Next, aim to compute the gradient of J in more general format. We do the derivation for time-varying R and Q with specialization to time-invariant setting at the end. For any admissible A, have
(L+)) - (AL)' (Q+ + (R,LT) (Q, (0)
t=1
Σ (Ar)' (ARLL LRAT) (AT)* +(IA))),
where the is hiding the following term
Σ (HA))=
Therefore, by linearity and cyclic permutation property of trace, we get that
J(L + A) J(L) =tr
AH
2 (AA) (Q: + LR,LT) (AL)* H (AL)
8 2RL (AT)* HTH((L)) + +o(|A|)).
tr
1=0
Finally, by considering the Euclidean metric on real matrices induced by the inner product (Q,P) tr (QTP), obtain the gradient of J as follows
VJ(L= -22 Σ (AL) HT (AL)* LR.
1=0
+2
(AT)*
HTH (AL) (Q, (AI)))(A)) HT,
18

---

whenever the series are convergent! And, by switching the order of the sums it simplifies to VJ(L) (AL) H (At)* LRa
(AT)* HTH H (A Ar. (A1) (Q++ LR(LT) (AT) H
+
km tmnk
= - 2
(AD) HTH (AL)* LR, + Σ
(AT)) HTH
(AL)' (AL)
t=
1=0
A
Σ
(AL)* (Qu+++1 - L (AT)* H
L
For the case of time- indeeendeennd Q and R. this reduces to
VJ(L) = = - Az
(Az)* (Q L.IT) H Σ
k==
[- (
where Y()) = the unique solution of
Y AL H
D.4 Proof of existence of global minimizer in Lemma
The domain S is non-empty whenever (A, ()) is observable. Thus, by continuity of L - JLL. there exists some finite minimizer is an interior point and thus must satisfy the first-order optimality condition (J(LL) = 0. Therefore, by coercivity, it stabilizing and unique which satisfies
0 such that the sublevel set S,, non-empty and compact. Therefore, the
L" = AX H (R + HX* H
with X* being the unique solution of
X = A A - Q L'R(L(L"))
(18)
As expected, the global minimizer L equal to the stcady-state Kalman gain, but explicitly dependent on the noise covariances Q and R.
D.5
Proof of gradient dominance property in Lemma 2
Note that X X(L) satisfies
X= A +Q+ LRLT.
(19)
Then, by combining (18) and (19), and some algebraic manipulation, we recover part of the gradient information, i.e., (-LR + Ar. ,, the gap of cost matrices by arriving at the following identity
X-X X" AI, X-
= (L - LT)T -L-L")(RI. HXA[)
- - - -1)R( - (I-
(20)
( ( - - -XX)) + a(T (T)
1
L L')T
where the upperbound is valid for any choice of a O. Now, R 0, choose X(R)/2. As
X 2- 0, it further upperbounds
X A XX-X")A],
1 X(R)
(-LR + -
X(R)
(L -L)T
2
19

---

Now, let X and X be, respectively, the unique solution of the following Lyapunov equations
x= A1- + (-I. ( RLT + HXAA),
x= A,-AAA,, + (1--))(L - LT)T.
Then by comparison, conclude that
2
X X(R) X
X X 3
A(R)
Recall that by the fact in (16),
J(L) - J(L') = tr - X & X(R)
2 tr ( H
A(R)
2 ir [ (21)
Let Y > 0 be the unique solution of
y= AT, Ar, + H1H1,
then, by cyclic permutation property
{HTH = tr (-LR- (-RI +
s X(Y") tr [r(u)[--RR +
(Y(())
X(Y') (J(L),VJ(M)
(22)
(Y)()))))
where the last equality follows by the obtained formula for the gradient V J(.). Similarly, we obtain that
tr {HTH tr L1)
(23)
Notice that the mapping L - YIE) is continuous on S Sa. and also by observability of (A, H), Y(z) > for any LES. To see this, let Hno (L) > be as defined in Lemma ] Then,
Y(1) (AT)(HTT))A
(AL) notth (H (AL) mat4h
1= k=
Σ mot HT (T.) (Ar) nat
غ mg
HL) (L) - O.
Now, by Lemma 1 S,, is compact and therefore we claim that the following infimum is attained with some positive value Ka:
inf A(V()) = Ka > 0.
(24)
LES.
Finally, the first claimed incquality follows by combining the incqualities (21), (22) and (23), with the following choice of
2A(()) (a) A(Y*) 22g and c2(a) == A(Y A(R)2
X(Y*) 2
For the second claimed inequality, one arrive at the following identity by similar computation to (20):
X - -
AI. TTTT+
[R) - HX AL) (L- +[
(1--="""++---"XXX"" =(I - LT)T
20

---

where the second equality follows because (() > 0 and thus
L'R AL- 1. HT -Y (x O.
Recall that
J - ( [x- - x X
then by the equality in (20) and cyclic property of trace we obtain
J(L) - J(L) = tr [ZY[n],
where
2 1X)
=
Therefore, for any L Sa. we have
J(L) J(L)) 2(L))( A((L2) Jr [2] 2 A())aa || -- L 1
and thus, we complete the proof of first part by the following choice of
ca(a) A(R)ka.
D.6 Proof of Lipschitz property in Lemma 2
Next, provide the proof of locally Lipschitz property. Notice that the mappings L X(L). + (L)) and - AL are all real-analytic on the open set >> Sa. and thus so is the mapping - (L) ()) - LR+ Ar, Also, by Lemmal | S, is compact and therefore the mapping L - V(()) is (-Lipschitz continuous on Sa for some f = f(a) > 0. In the rest of the proof, attempt characterize E(o) in terms of the problem parameters. By direct computation obtain
-J(L))- - (V(22) = (2Y - (Y())) ( [-4 A XL,) - L2R + AL, (1z) HT) =2(V(u)) - [- HX(L,) + AX HT
+(2((a)) R - ((L,)
+ +2X(4))) (L2 (1X,++ + A1z(()))) -(
Therefore,
[[V ((())) S <(1((()) Y(M))l? + BIIL, Lell (31 X(ra)l? (25)
where
4 (4,) 211 (R + HX(,,) AX(,,)
8 (T4, [2) (1) llop || + HX(L,) HT llop
fa (T(2 211Y plop A llop HT llop-
On the other hand, by direct computation we obtain
Y(,,) - (Y(1.) - -((Ia))AL
-
=(12 - HT) (12TY(2)AA,, Arz + AJ H(L Li) + (11 - T2) (L,) H(L -2)
(26)
3 L - 4
where
44 = (T,,, T2) =2||HTY(LD) Azg 1lop ((L T22)lop-
Now, consider the mapping L + Z(I.) where Z(1)) = Z is the unique solution of the following Lyapunov equation:
= AT + I,
which is well-defined and continuous on S S,, Therefore, by comparison, we claim that
[|\(,)) Y(L,) 1F = 11 L2IlF ls IZz)lle.
21

---

By similar computation to that of (20), we obtain that
((m)) (12)) (X ((
=L, AL, ((,) H (I2 - L2)
(L1 (LL (
(27)
(L1 L2)R(L1 -22)
(L1 - (L)) L2)
_1 L Es (Q -22L13
where
l = (L(L)) = 211 - 1, R + A X ((1,) HT lop/ X(Q). Therefore, by comparison, we claim that
[ (I,))llr r N || L2ll r Es (
Finally, by compactness of Sa. we claim that the following supremums are attained and thus, are achieved with some finite positive values:
(a) = sup L,,L2ES,
(L))) L2) IZe,,)le
(2(a)=
sup
(g(L1, L2),
L.LLES.
(a) = sup 1.2EE
la (1(42))((4))))
Then, the claim follows by combining the bound in (25) with (26) and (27), and the following choice of
((a) = + ((a))
+ (aa
D.7 Gradient Flow (GF)
For completeness, in the next two sections, we anlayze first-order methods order to solve the minimization problem (TO), although they not part of the main paper. In this section, we consider a policy update according to the the GF dynamics:
[GF]
L, = VL,
We summarize the convergence result in the following proposition which is direct consequence of Lemma
Proposition 6. Consider any sublevel set Sa for some > O. Then, for any initial policy Lo S.. the GF updates converges to optimality and the policy iterate). In parficular, we have
linear rate of exp(-ci (a)) (in both the function value
((L.) J(L") S (xxx)("")
and
[1, - 1 a- J(1=) exp(-c1(ass).
cs(a)
Proof.
Consider a Lyapunov candidate function (L) = ((L) - J(L)). Under the GF dynamics V(I.)) = - (VJ(L..), VJ((L)) 5.
Therefore, Lg Sa for all 0. But then, by Lemma 2 we also show that
(L.) -ci(aV((L.) (2( 1I for 0.
By recalling that e1 (a) > 0 is a positive constant independent L. we conclude the following exponential stability of the GF:
V(L.) S V(Lo) (xp(-c
for any Lo Sa which, in turn, guarantecs convergence of J(L.) + J(L") at the linear rate of exp(-ci(a)), Finally, the linear convergence of the policy iterates follows directly from the second bound in Lemma
- L < es(()) V(L,) <
v(Lo)
csla) exp( (a))s)
The proof concludes by noting that (Lo) S J(L") for any such initial value Lo S..
22

---

D.8 Gradient Descent (GD)
Here, we consider the GD policy update:
[GD]
L++1 L T/ (LL)),
for k Z and a positive stepsize Tjk. Given the convergence result for the GF, establishing con- vergence for GD relies on carefully choosing the stepsize 7), and bounding the rate of change of VJ at least on each sublevel set. This achieved by the Lipschitz. bound for J.. on any sublevel set.
In what follows, we establish linear convergence of the GD update. Our convergence result only depends on the value of a for the initial sublevel set S., that contains Lo. Note that our proof technique distinct from those in [2 and [50]; nonetheless, involves similar argument using the gradient dominance property of J.
Theorem 4. Consider any sublevel set S. for some o > O. Then, any initial policy Lo E S.. the GD updates with any fixed stepsize Tis =1 (0, 1/[[a]] converges optimality at linear rate of 1 1 1-1 /22 (in both the fanction value and the policy iterate). In particular, we have
J(Lx) - J(L") la J(L")(( (a))22))))
and
aa I())
- 1' -
(1 -1- m7c (a))22)))
ca(a)
with (i(a) and cz(a) defined in Lemma
Proof. First, argue that the GD update with such step size does not leave the initial sublevel
set S, for any initial Lo E S,, In this direction, consider L(n) = Lo - V for r 2 0 where To * I. Then, by compactness of S., and continuity of the mapping 1 J(L(n)) on S 3 S., the following supremum is attained with a positive value ijo:
yo == suppn : ((L()) S a, [0,
where positivity of ?7 is a direct consequence of the striet decay of [[(())) for sufficiently small ((o)) * O. This implies that L(n) S. C for all E [0, 77o and ([L()))) = Next, by the Fundamental Theorem of Calculus and smoothness of J--) (Lemma 7). for any 17 E [0, 7u we
have that,
J(L(n)) -(Lo) Lo) ( (VJ(L(ns)) - VJ(()), L(n) Lo)ds
$ (((()) - Lolls ( [[V](I((n))) J(
((a)](((n) LollF 1'' [[L(ns) Loll 1
- -(a))lLL())) [ol==/VV((Lo)le
where || r denotes the Frobenius norm, the first inequality is a consequence of and the second one due to (11c) and the fact that L(ss) remains in S., for all E [0, 1] By the definition of L(n), it now follows that,
(((a))) 2
J(L(n)) J(Lo) 5 [
(28)
This implies J(L(n)) < J(Lo) for all 1) < 2/E(a), and thus concluding that no 2 2/E(o). This justifies that I(m) E S. for all E (0,2 Next, if we consider the GD update with any
"Note that a direct application of Descent Lemma 51 Lemma 5.7] may not be justified as one has to argue about the uniform bound for the Hessian of / over the non-convex set S,, where J is Lipsciitc only on S.. Also the proof of (50) Theorem 2].
23

---

fixed stepsize 1f E (0, 1/(((a)] and apply the bound in (28) and the gradient dominance property in Lemma we obtain
- J(L1) - J( S menl ( - ](
which by subtracting J(L") results in
- (1-
J(L))},
(c((()))/22-1) nncn /2 for 1 17 (0,1/((a)). By induction, and the fact that both (o) and the choice of 1j only depends on the value a, we conclude the convergence in the function value linear rate of 1 (170122 /2) and the constant coefficient of a J(L") 2 J(La) J(L").
To complete the proof, the linear convergence of the policy iterates follows directly from the second bound Lemma
Appendix E Proofs for the analysis of the constrained SGD algorithm
E.1
Proof of lemma 33 Derivation of stochastic gradient formula
Proof. For small enough A E Raxm
=(L+A.)) e(L.)) leT 2)|l (L)I [er A) + AlIA)))
The difference
(T + A) eT(L)) (1) + F2( + ((I
with the following terms that are linear A:
= - H Ay - (A)))
= >
-t 1)..
Therefore, combining the two identities, the definition of gradient under the inner product (A, B) = tr [ABT], and ignoring the higher order terms in yields.
(V.e(L, v). A) = 2tr [(E (A) + E2(A))e(()), which by linearity and cyclic permutation property of trace reduces to:
(Vie(L,V), A) -2r
1 Σ
+2tr
Σ
(L)
k=1
This holds for all admissible A, concluding the formula for the gradient.
E.2 Proof of Lemma 4: Robustness of the policy with respect to perturbation
Proof. Recall the stability certificate Są proposed in 30 Lemma IV.1] for choice of constant
mapping @ K - A > 0 and dual problem parameters as discussed in Remark 3 Then, we arrive at şк = X(A) X(2))) []), for which p (AT + HT(LT + T)T)) < 1 for any E [0, sk). But, the spectrum of square matrix and its transpose are identical, thus L + 7 S for any such n,. The claim then follows by noting that the operator norm of a matrix and its transpose are identical, and the resulting lowerbound as follows 8x 2 (())
E.3 Proof of Lemma Uniform lower-bound on stepsize
Proof. Without loss of generality, suppose Lo * L and E + O, and let L(n) = Lo - E. By compactness of Sy and continuity of the mapping 17 + (L(r)) on S 3 Sg. the following supremum is attained by ns:
n == sup(n (((()) < 3, n].
(29)
24

---

Note that 77 is strictly positive for 3 > a because Lo E Sa C S3 and J() is coercive (Lemmal
and its domain open (Lemma This implies that L(n) E Sg c S for all oj E [0, nsl and J(L(ns)) = B.
Next, we want show that vı is uniformly lower bounded with high probability. By the Fundamental Theorem of Calculus, for any 7) E [O, na] we have
J(L(T)) - ((Lo) - (L))) [()) Lo) = L.' (VJ(L(ns)) - VJ((o)) M(n) Lo)ds
< (1((1)) Loll= / [VJ((((ss) -VJ()))l
{((B) Loll / [[((s)) Lolleds
1 (
(30)
2
where the first inequality is consequence of Souchy-Schwartz, and the second one is due (11c)
and the fact that [(ns)) remains in S3 for all E [0, 1] by definition of n/- Note that the assumption
implies ||E|| - (7 + 1))] Thus, (30) implies that
J(L(n)) -<V))) E) 2 ((0))
SJ(L)) (VV E - (L()) - / 13 2 (18))
(31)
<J([o) + ( 1 + 1))()))())) ( 1)m]
Therefore, for 7) to be a feasible point in the supremum in (29), it suffices to satisfy:
(((o))] [[T + 1)2E(3)n) + 2(- 1)yl S 3 - a,
or equivalently,
(++ 1)((3))
Y- 1 2
7
20(B][3 al [VJ(L))
+
7+1
7 7++1
But then it suffices have
7-1 (7 + 1)+(()))) +
v
22(B3] -
<
++1
Finally, note that by Lemma 2 and (11c) we have
{(a) [V < c3(a) J(LO)-
((a) ca(a)
la - -a*).
(32)
Using this uniform bound of gradient on sublevel set S₂ and noting that y E [0, 1]. we can obtain the sufficient condition for be feasible. This completes the proof.
E.4 Proof of Proposition] 2 Linear decay in cost value
Proof. Suppose Lo * L and let L(r) = Lo EE Note that E may not be necessarily in the argue the following:
direction of decay in J (L), however,
Choose 3 in Lemma and note that ny as defined in (29) will be lower bounded as 178 2 7o- and thus 77 is feasible. Recall that L(n) E Sg S for all 17 E [0, ns). Also, for any 17 E [0, 7o] and y E [0, 1), from (31) we obtain that:
1 [ + 1) + (7 (7-1
J(L()) ((Lo) < [[V](
- <a((a)[[Loo)) J(Zz)] 1/2 (7 (1++1)(((a)r)) + (7 (7-1))
25

---

where, as y < 1, the last inequality follows by (1 for any S min 773. By the choice of fjo. then we obtain that
(7 1)2
(L(rio) - J(Lo) - -c((a)
(J(LO) - [J(L0)
J(L')
[2 1)3((a)
This implies that
- (1-
( 1)2 2(7 +
1)<((a)) (17+1)(((a))
[U(LO) J(L3)
J(L")]
E,5 Proof of Theorem 1
Convergence of SGD algorithm
Before proving this result, we first discuss that the claim of Theorem i sufficient for establishing the complexity result of Theorem 3 i.e., it suffices to guarantee convergence from every initial (stabilizing) policy to neighborhood of optimality where norm of the gradient is controlled.
As shown in Lemma 2 (and discussed in Remark 4p. the cost maintains the PL property on each sublevel set. In particular (a) implies that on each Sa, [[V][ characterizes the optimality gap (LL J(L) by:
(
[L)]
for some constant C1 (a.). This implies that if we have arrived at candidate policy La for which the gradient is small, then the optimality gap should be small (involving the constant ej (a) that is independent of Lı). This is the reason that in Theorem I it suffices to argue about the generated sequence La to have a linear decay unless entering a neighborhood of L containing policies with small enough gradients (denoted by Cr). In particular, if for some j < k, we arrive at some policy Lj E C,, then by (1la) we can conclude that:
- 2 IVJLDI
$
(i(a)
(1)722
which is directly controlled by the bias term 8o- This is the bound used also in the proof of Theorem
Finally, recall that every (stabilizing) initial policy Lo amounts to a finite value of J (Lo) and thus lies in some sublevel set S.. So, starting from such Lo. Theorem guaranttess linear decay of the optimality gap till the trajectory enters that small neighborhood. Finally, note that the radius this neighborhood C, is characterized by the bias term 8g which itself is exponentially decaying to zero in the trajectory length T.
Next, we provide the proof of this result that is essentially an induction argument using Proposition
Proof of Theorem The first step of the proof is to show that the assumption of Proposition satisfied for E = (() for all L E Sa C2/2. This is true because
[VJ(L) VJ(DII < $ VJ(III + 80
VJ([)I + 3 JVJ(L)) <J))I
where the first inequality follows from Assumption 3] the second inequality follows from L & C2f2 (i.e. soll [LL]] 2 7/2), and last step follows from the assumption s < 7/2.
The rest of the proof relies on repeated application of Proposition 2 In particular, starting from
Lo E S. CCyy2, the application of Proposition 2 implies that I, To J(L.) remains in the same sublevel set, i.e., L E S,, and we obtain the following linear decay of the cost value:
J(LI) J(L') < |1 -i (a - ())o) J(L))
Now, if L1 C,,/2 then we stop; otherwise L1 E S, C,y2 and we can repeat the above process to arrive at L2 == Ln - 1) ((L,) E S.. with a guaranteed linear decay
J(L2) J(L") = (1-))((11))222) (((1) J(L")).
26

---

Combining the last two linear decays yields
- - s -1 - J(L)).
Repeating the process generates sequence of policies Lo, 11, L2... with a combined linear decay of
J(L)) J(L') = (1)) 7)/2 (J(Lo) J(L*)),
unless some iteration arrive at policy I, such that I.g E C2 This completes the proof.
Appendix F Proofs of the result for observation model and sample complexity
F1
Preliminary lemmas and their proofs
First, we provide the proof for the complete version of Lemma 6
Lemma 6' (Uniform Bounds for Stable Systems). Suppose L S, then there exit a constants CL O such that
Il S Cr. (Vo(Ar)) k+1
whenever p(AL) > O, and otherwise v v((A)) is replaced with any arbitrarity small (0, 1). Additionally,
Cr.
| S 1- vP(AL)
1 1 1+20%p(AL))
|EH
[L ve(AA))
Furthermore, consider Sa for some 0. then there exist constants D& 0, Co and Pa E (0, 1) such that |L]| S. Da, CL S Co and p(AL) S Pa. VL E Sa.
Proof of Lemma 0 Recall the Cauchy Integral formula for matrix functions any matrix M E nxn,
53 Theorem 1.12]: for
S(M) = - f. (M)(2l-M)---
whenever f is real analytic on and inside a closed contour that encloses spectrum of M. Note that L S implying that p(Ar)= < 1. Now, fix some r (p(Ac), 1) and define [(0) re with ranging on [0, 2x). Therefore, Cauchy Integral formula applies to f(2) = z for any positive integer and the contour I' defined above. So, for matrix A,, we obtain
$f (2T A 2
2n
A
2 fr
+²t eke 10 - A) r "
implying that
k+1
/
2T
|
l1(re
1- 11)=~1((00 < k-
max [[re -
2T
0E (
Finally, the first claim follows by choosing r (p(Ar) (whenever p(Ar.) 0, otherwise (0,1) can be chosen arbitrarily small) and defining
C₁. = max 0 00
II( (0 Ar.)
which is attained and bounded.
Detinition 3.1] for an alternative notation; however, we prefer the explicit and simple form of expressing spectral radius in the bounds established in our work, which also facilitates the comparison to literature on first order methods for stabilizing policies.
*See [52
27

---

Next, by applying the first claim, we have
EiANT C1 1 vP(AA) )"
Vo(Ar)
==
implying the second bound. For the third claim, note that for i 1,2.... we obtain
& |E Σ V((A)) (-++))
|M [E]] -
|A4
|II
k=0 0
$ ||EH| CLVP(AR ((A))
(i+1) p(Ar)
(33)
But, then by recalling that Mo[E] = 0 and [| |EH|| || we have
20 209,p(Ar.)33
MM[BIl < |EH|| + |EH]]
[L
where we used the following convergent sum for any p E 10,
(2 p2-p)p²
2p²
1)+
-
(1 (1-p)² p)2
(1 p)2
1=1
This implies the third bound.
The final claim follows directly from compactness of sublevel set S. (Lemma 1 and continuity of the mappings (L, 0) + (p(Ar),)) 0) - ([V ee 1 Ar, 11 on S., x [0, 2T| whenever p(Ar. > (and otherwise considering the mapping (I,, 0) + [1 Az) || for arbitrarily small and fixed r E (0, 1)).
As mentioned in Section 4.2 a key idea behind these error bounds that scale well with respect to the length i' the following consequence of von Neumann Trace Inequality (49] Theorem 8.7.6]:
ttr [MM] s (MM), S |MIIII
with || || denoting the nuclear norm. Additionally, as direct consequence of Courant-Fisched Theorem, one can also show that nuclear norm is multtilicccaiiee More precisely,
|AB|| < |||||| |||| < ||||I
Next, we require the following lemma bound these errors.
Lemma 8. For any L E Sc. we have
H- | S 1 p(A(At)
[2Cr + (41,P((A))3
[|]]| | H
[L]
|E
[1-p(AL) ((A))
Proof of Lemma 8 For the first claim, note that AJ, H1 H Ar, is positive semi-definite,
|
tr [A]
S [ H1] ||
< ||
Σ
(AT))
T
$ HI
||
2=0
C7
< I H||
p(Ar.)
28

---

where the last inequality follows by Lemma 6
Next, we have
|Ma
M
1/2
T
1/2
M |||
T ||H|| + |FH|| (AL)
1/2
+ 1)2 p(Ar)
1=
2p(Ar.
< ||H]| + |EHI CEHICCEV (A)))
1+ P(AL
||H||
[1-p(1 11-((A))33/2
where the second inequality follows by (33) and the third one by the following convergent sum for any p (0,1): 1):
Σ (i+1) p0(0² - 1-7-3p+-3 3p+
4p²
5 (1 p)
(1 p)3
Also, by the properties of nuclear norm
H |HT = ( A
< ||A
1/2
|4
||TH||
CR
1/2
||
((A))
where the last incquality follows by Lemma 6
Finally, notice that
< Mr H...
and thus combining the last three bounds implies the second claim. This completes the proof.
The next tool we will be using is the following famous bound on random matrices which a variant of Bernstein inequality:
Lemma 9 (Matrix Bernstein Incquality (54 Corollary 6.2.1J). Let Z be a dj d2 random ma- trices such that E [2] = Z and || < K almost surely. Consider M independent copy of Z as ".. Zes, then for every 2 we have
1
M2 + 2Kt/3
PP
Σ,
Z. 2
2t
(di
(di
+ exp
exp
M
Il. |E [ZTZ] [1} the par-sample second moment. This bound can be ex- 12 pressed as the mixture of sub- sabbsaausiinn and sub-exponential tail as (d, + d2) exp -emin 5z 2K for some
where o² max E [ZZT]|]
We are now well-equipped to provide the main proofs.
29

---

F.2 Proof of Proposition 3 The Observation model
Proof. Recall that
E(L,)r)= = [Hx(T)) - HT(T) Σ (T) H.
where H. is the i-th row of H. Also, by duality, if =({) = (A1) H, is the adjoint dynamics'
closed-loop trajectory with control signal u(t) = (t) then
HTx(T) - HT) = -| 7
where
2 (=(T)T x(' 1)T
2(1)T =(0)))
7 = (m(T)* u(T 1)1 u(1)T 0%)
But 7 (I LT)z and then E, Al, H, Therefore,
e(L,)Tr) = Σ
HT -
i=1
m
t (1 (1) L)]
Then, by using the fact that > -,HI--HTH, = we obtain that
e(,))r) ir (
Thus, we can rewrite the estimation error
<( (T.,)r) = (E,E) A + ((T s L) (T& & ). - ()) A = =1771.12
Next, we can compute that for small enough
AL+E -A. Ar.
This implies that
((A]TTHHL) n. | + + AAHTHM.LEE
On the other hand,
- - (1
(T ET)
+ EII
Therefore, the second claim follows by the chain rule.
F.3 Proof of Proposition 4 Concentration bounds
We provide the proof for detailed version of Proposition 4
Proposition 4' (Concentration independent of length T). Consider length T trajectories
{)Y 10 and let (L) := ,े .M (+). Then, under Assumption for any > 0
P -[3 Jr( & a) 2 1 - 2n
-M
|1 + 2/118/3
2M
P [[IVTr(L)- - v-)(()] S 21 enexp
1/ + 22/23/3
30

---

where Ty = Kgg + M and
x2,0
Pr. =
HTH I-
[1 vp(At)]
VL k 07 + [c + (0 |
| |+
[] - --v((A))
Note that E [EE = (100 0 P. - (10) R
(m))
Proof of Proposition
R, and E {
0. Assume mo = 0 and recall that
3),, = de((, thus,
using Proposition
we can rewrite the (L) and its gradient as
Jr (L) = E [=(L, = I = tr EE A
where E [ Q
L) LT). Therefore, by definition of (T) obtain
- [E
with Zr,
MI Σソ (r.=)''(''') which can be expanded as
Σ, = + 1.) 2x( @ I.T) - Zz(7 s IT)
where
M
M
M
2 =
E 22 M 1=1
Σ J
23
E 5
M
M
and E [2 (I & L)R(I & LT). Therefore,
(r) (L) tr [(2z - E (2)) AL H[HTHA)]
Thus, by cyclic permutation property of trace and (12) we obtain
-z Al (21 [2L]) AL |
(34)
Next, we consider the symmetric random matrix AL (Z - E (Zz) AL. Note that - L s Kg almost surely and thus
2
- s nnt
Σ
||
S HL/ |LL
It then follows that
EE (L |
S [| & H
Therefore, by Lemma 9 we obtain that
M H 1
P Al (2₁- - E 2x)) ALl 2 < 2n exp
11 + 2pz H H 1t/3
Substituting with H/||TT together with (34) implies the first claim. Similarly, compute that
(V.r(L), F) = (.)( E) 22r & L)R(1 ATTTA (1 [T)))
and thus
(D)) -2r (2/(1 (T)
2tr L (I HT)
31

---

Thus, by eyclic permutation property of trace and (12) we obtain that
M (VV..(1) - VJr(L), B) S M Σ (L(F,))) - [SL(E, (7 |||
(35)
where Sz (E.)) the symmetric part of the following random matrix
-2ALE @ ET)A + 2A & L) ET) + 2 M
Next, we provide the following almost sure bounds for each term: first,
|Ar. Zal & ET)AE S ||A
@ E |I
S Kig
Σ |ALLI
Kuw
Σ IALI
C7
S Ki
||||
where the last equality follows by Lemma 6 second, similarly
| @ L) @ ATll
S (I ② L)
|I @ E)Ø1
11111111111
Σ |
C7.
2
||Z|||
||]|
vp(AL))
and finally
M, AI
(ETTell
<N
Σ ||4 |I
Σ
Cz. + (C2,((A))
SKt.
|EH]
[]
v)(Aa)
where the last inequality follows by Lemma claim that almost surely
Now, by combining the last three bounds we can
(F,)))) -
VL
||]]
|
This also implies that
2 < H HIP
E (F, || < E (F,
|
Therefore, by Lemma 9 obtain that
P
M Σ Sx(E, - (S.(0,)4)
M H
< 2n exp
E + | H || E11/33
Thus, by substituting with F| | [HH)) H|. and applying this bound (35) we obtain that
M 1 + 2v,t/3
P (1) (L), (L)) F. S ||]]]] 2 - exp
Finally, choosing E = (L) (L) proves the second claim.
32

---

F.4 Proof of the Proposition 5 Truncation error bound
We provide the proof for detailed version of Proposition Proposition 5' (Truncation Error Bound). Suppose mo = 0, then under Assumption 4 we have
|J(L) - Jr()) & p(AL) p(Ar))
and
V p((A)) T+1
(VJ(LL) VJI(L)) 92
where
Et. = [ng (Kē + [4 |ATHII.CE.
7L =2 [k2 + ( - C II
+2 ( |T HI). (CL. + 201P(A))81) CLVD(AL)**
Proof of Proposition 5 For the purpose of this proof, we denote the same matrices by ALT and ML.T [b]] in order to emphasize on length T. Recall that
E AL HT HA,TT where E3 = L)R(1 @ LT). which implies
JT( E (e(L,
Jr(L) [1
tr (PO(A))TTHHA))
On the other hand,
J(L) = lim tr
+
and thus
Jz(L) =- tr (P
+ >im
[T
(Q (Q IRLT)] [Q[TT]]]] (AD)"AL, AL. & AE]]
tox
= - tr [A] HTH]
+ lim (r [M & A4 + (A t-
Therefore, by the properties of trace and Lemma we obtain that
(J(L) - (1)) Po || tr [HTH]
+ + II
lim HL, HAL!! +oo
< |1 ||T/||
C2IHT + +1 + ||| (())))
1- p(Ax)
where the last line follows by Lemma So.
|| + (IQ1I + |||||| 1
|ITHH)-C(MAA)))
p( Al)
This, together with Assumption limply the first claim.
Next, for simplicity adopt the notation AL to interpret the limit as l - co, then similar to the proof of Proposition 4 we can compute that
(VJ(L)- JJ. (L),(),)))
21r [M (ATT)) HTH
+ tr
[ 8 AΠ (AIT++)A) [F]]
+ 2tr
[ HA
JAL HT HAL
[T AE
HTH.
2tr
33

---

Therefore, using (12) and Lemma we have the following bound
[(V[()) V.J E)
||] P
+ +IQ 1 1N
T+1
+ + LLLL | (T))((A)
1)p((A))+ I H H
+ |E + 1 HAL
(
which by Lemma 8 bounded as follows
(VJ(L) VJJ
PolI H H|| + ()p(A2)
20 4C,,,((A))77) p(Ar)=+1
+ IQQ + LRL H ||
[] -1- p(x))
+ 2 + | C1 - p(Ar.)
()p(AL)
C),(Ar))
+ 2 R |||| HT H|I
1 p((A))
Finally, choosing E = (L() V (I) together with Assumption implies
kx
(x x.111
VJr
-
CEIL | (1)(A,)
1- ((z)
(NB + I I ||]I| (Cz, + 202P(AA)))))
|ATH|| C)A(A)) p(Ar)
+
1(A(A,)
Finally, the second claim follows by the following simple facts:
(T + 1)p(AA) < vp(AL)** T+1
VT> 0,
-(())))
2 S 1ypp + for any p E (0, This completes the proof. as max tp' "mml/p
F.5 Complete version of Theorem 2 Sample complexity bounds for the stochastic oracle
The following is detailed version of Theorem
Theorem 2'. Suppose my = Op, and Assumption 4 holds for a data-set ( Define (L) = M
1 E Ve(T.,)% where vI,e(T,)))) is obtained in Lemma Consider Sa, for some >> 0 and
any 8, 80 > 0 and T E (0, 1). Suppose the trajectory length
Ja Paymin(n, min(n, m)
T> In
In
80
VPa
and the batch size
Vay min(n, m)
4
Vay ////miinnn.. m)
M 2
+
In(2n/8),
880 /T
3
3 /T
where
7a = 2 2 C2 + 22DD2) C2I
( Kig D2 D. | ||||||H (Co + +022p2/ Ca T+1
2(1i + DaVi Kw C2 + Ca + p0 3/2
H ( + Dats))
/
with Par Co and Da defined Lemma Then, with probability no less than Assumption holds.
34

---

F.6 Additional concentration bound results
Combining the truncation bound in Proposition with concentration bounds Proposition we can provide probabilistic bounds on the "estimated cost" (T.) and the "estimated gradient" (I.) The result involves the bound for the Frobenius norm of the error with probabilities independent of T.
Theorem can be viewed as simplified application of Theorem S characterize the required minimum trajectory length and minimum batch so that the approximate gradient satisfies Assumption B with a specific s and su-
Theorem 5. Suppose Assumption 4 holds. For any and L E Sa.
UL min(n, m)
4
VI. min m)
M 2 2
+
In(2n/0),
3
[J[[]]
then with probability no less than 1 - 6,
|VJr(L)
J S J[VJ(L)]|F + min(n, m) p((()) T+1
with vr, and Hr. defined Proposition f and Proposition respectively.
Proof of Theorem 5 Recall that for any LE S., for some 0 we have
[L) VJ(IIII & (V) - (+T( -Vr(() ((JT())))+I(((()))))))))) (J()I
Thus, by Proposition with replaced by 8|| [[[]][[] min(n, m) and applying Proposition to the second term, obtain that with probability at least - 6:
JJL))l
vp(AA)
[V) (J)))) s
+ FL min(n, m) [1 p(AL))2
where
-2
8 2 2n exp
man
+
8/3
[J([)]]
Noticing (V) -L)(L)) S /m)n(n,m) (L) (J) -J(()] and rearranging terms will
complete the proof.
One can also provide the analogous concentration error bounds where the probabilities are independent of the system dimension n..
Proposition 7 (Concentration independent of system dimension n). Under the same hypothesis, we have
-M
p - s) 21 1 2T exp
n27 + 2//
and
22
- vJr(D)II Ss) 21-22 2T exp
2Texp
1772 + +2 s3/33
- -Ms2/2
-Tp
k2 T + 2 T's/3
where
HH H||-
P1 1 ((AL) Ki
2Cr. -C2,p(A))8/2
| HT
11
K
[1 - ((A))]
35

---

Proof of Proposition Similar to the previous proof, we have
(LL (L) tr ((2 - E (z,)) AT..T
and thus, by (12) we obtain
- S (Z,, - -E (2..) ||
(36)
Next, we consider the symmetric random matrix (Zz - E [zl) and recall that lIE(t) - Lw((t)l S KL almost surely; thus
|| = |/r S T
then follows that
E [x]] - E |r S K
Therefore, by Lemma 9 we obtain that
M22/2
Plll (Zz- E (2))) || 2 S 27 exp
(37)
K4 + 2
Substituting t with t/ | H.TH | together with (36) implics the first claim because by Lemma *IAT 11 & ,rT'
Again, similar to (35) in the previous proof, by (12) we obtain that
M
- - S
Σ
SL(E,))) E (E,())))) HTT
X2()") - E [x2())) [[]]]]]] (38)
M
where SL(E,)) is the symmetric part of the following random matrix
25 2 ET) + 2(1 & L) ET)
So, claim that almost surely
[| 2/ @ E) |(IE + (I(I @ L)
2| K. TRETT + [[])
and thus
|E (E. < (E, S S
Therefore, by Lemma g we obtain that
M2
(F, E [F,, |2 < 2T exp
exxp
2 T3
Substituting with t/ t/||A| H AAll || implies that
M
Sr. Sz yf) - E. [S,(E, |A 2 1
M
M22/2
< 2T exp
T 2x T
because by Lemma
8 we have 1 |A S PIT.
Next, by substituting with t/ Wr E in (37) we have
-MP/2
PP 2 E. [2z] || [ |. 2 1 < 27 exp
E
E
26
36

---

because Lemma 8 implies that [ I ET.
Thus, by combining the last two
inequalities and using the union bound for (38) we obtain that
M2
(L) VJ. 2T exp
E
+ 2 Et/3
MM
+ 2T exp
1 E + 2kw b///
Finally, substituting with s|] F|] and choosing
vJr(L) (L.) proves the second claim.
Remark 10. We obtained better bound for truncation of the gradient
[VJ(L) (L)))) S (L) [] - p(A)) In(1/p(AL) T2(L) ((Ar))+1
Vp(AL)
[1- p(A)))²
which has been simplified for clarity of the presentation.
Appendix G Numerical Results
Herein, we showcase the application of the developed theory for improving the estimation policy for an LTI system. Specifically, we consider an undamped mass-spring system with known parameters (A, H) with = and m = 1. In the hindsight, we consider a variance of 0.1 for each state dynamic noise, state covariance of 0.05 and variance of 0.1 for the observation noise. Assuming a trajectory of length T' at every iteration, the approximate gradient is obtained as in Lemma B only requiring an output data sequence collected from the system (1). Then, the progress of policy updates using the SGD algorithm for different values of trajectory length T and batch size A are depicted in Figure [ where each figure shows averaage progress over 50 rounds of simulation. The figure demonstrates linear convergence outside of neighborhood of global optimum that depends on the bias term in the approximate gradient (due truncated data trajectories). The rate then drops when the policy iterates enter into this neighborhood which is expected as every update only relies on a biased gradient in contrast to the linear convergence established for deterministic GD (to the exact optimum) using true gradient.
Specifically, recall that convergence guarantee small neighborhood around the optimal value is due to the finite-length of the data trajectories. The region can be made arbitrary small by choosing larger trajectory length. In particular, to achieve error, we only require the length T (In(L/=)) see Theorem 3 Also, Fig (dd is illustrating that optimality gap at the final iteration (i.e. the radius of the small neighborhood around optimality) which is decaying linearly
function of trajectory length T < 50 until the variance error dominates beyond T = 50. It is clear that, increasing the batch size M will allow further decrease of this optimality gap beyond T 50.
The code for regenerating these results is available online at this Gitl-ub repository 55
Appendix H Nomenclature
Constant Values
Scalar value of the cost
To
Uniform constant for gradient estimate-sse see Theorem
Tr.
Constant for bounding bias of gradient estimate-see Proposition 5
5
Failure probability
7
Step-size of SGD algorithm
Positive constant smaller than one see Proposition
Kis
Scalar upperbound 2-norm of measurement noise
Kig
Scalar upperbound on 2-norm of dynamic noise
37

---

10
M - 10
[(,,) -
20
10a3
10a1
[(.))
30
80
10
10 7
10a
10-1
[[Lc] -|L-)
10
[[_
1000
1500
2000
Iteration
M
(a)
(b)
1(La] - [(LJ)
T=10 10
[Ld [[_.]
RL
T=20
KL.))
T=30 30
109
10
T= 50
10
10--
16-1
1014
250
500
150
1000
1250
1500
1750
2000
40 60 80 100
Iteration
(c)
(d)
Figure 1: Simulation result of the SGD algorithm to learn the steady-state Kalman gain for the mass-spring example. (a) The optimality gap as a function of iterations for different value of batch-size M averaged over 50 simulations; (b) The optimality gap at final iteration as function of batch-size M for all 50 simulations; (c) The optimality gap as function of iterations i for different value trajectory length T. The figure depicts the linear decay of the optimality gap, with respect to iteration k, before the iterate enters the small neighborhood of optimality where the direction of the oracle gradient is not informative anymore. The neighborhood shrinks T increases; (d) The optimality gap at final iteration as a function of trajectory length T. The gap is decaying linearly as function of trajectory length T until the variance error dominates beyond T 50.
Combined Scalar upperbound on 2-norm of noise
Va
Uniform constant for gradient estimate-see Theorem
VL
see Combined matrix variance statistics gradient estimate- see Proposition 4
Iteration step of SGD algorithm
M
Batch-size of SGD algorithm
m
Dimension of observation vector
Dimension of state vector
Variance coefficient term of oracle model see Assumption 3
so
Bias term of oracle model see Assumption 3
Length of output data trajectory
t
Time step of the system
Other symbols
||-I1
2-norm of matrix
||-
||F Frobenius-norm of a matrix
L Linear operator describing the filtering policy that maps measurements state estimation
Ct Adjoint of the operator L
38

---

p(-)
Spectral radius of matrix
Pa
Uniform upperbound of spectral radius of closed-loop system over Sa-see Lemma
C2,02,C3
C3
Uniform positive constants related to the cost function on Sa see see Lemma 2
C.
Uniform upperbound of constant coefficient
Sa see Lemma 6
Cl
Constant coefficient of upperbound in Lemma 6
Da
Uniform upperbound of 2-norm policy over S,-see Lemma
Problem Parameters
Ar.
Concatenation of closed-loop dynamics matrices-see Proposition
A
Dynamics matrix
И
Observation matrix
mo
Initial state mean vector
P
Error covariance matrix
Po
Initial state covariance matrix
Q
State noise covariance matrix
R
Output (measurement) noise covariance matrix
System Quantities
7
Combined noise vector
á
Estimation of state vector
Estimation of output vector
C
ho/h-neighborhood of the globally optimal policy I,*
Mr
Concatenated matrix regarding the differential of (L,))r) see Proposition
N
Concatenated matrix regarding the differential of c(L) see Proposition 3 Set of Schur stabilizing policies a-sublevel set contained in Trajectory of adjoint input vector Concatenated matrix regarding the differential of =LL,)rr see Proposition 3
Sa
X1
y
Trajectory of output vectors
vj
Estimation of gradient of cost function
VJ
Gradient of cost function
Output (measurement) noise vector
as
Boundary of the set of Schur stabilizing policies
e(,,)r)
Squared-norm of the estimation error vector of policy L for trajectory V
Concatenated combined noise vector
Concatenated measurement noise vector
E
Concatenated state noise vector
Jr
Estimation of the cost function on length T trajectory
g
State (dynamics) noise vector
eT(L)
Estimation error vector of policy I. for trajectory Yrr
Cost function
JT
Cost function on length T trajectory
Filtering policy matrix
u
Adjoint input vector
X Cost matrix
State vector
39

---

XT
Cost matrix on length T' trajectory
Y
Auxiliary cost matrix
y
Output (measurement) vector
Adjoint state vector
40


Reviews:
[{"review_id": "QEkFWZGC5j", "reviewer": "Reviewer_LR36", "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.\n\n\n\n", "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?\n\n", "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. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "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.\n", "weaknesses": "I don't consider these as weaknesses necessarily but here are a few things I would recommend the authors to consider:\n1. The results of remark 7 can be discussed earlier maybe within the informal theorem 1.\n2. 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.\n3.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. \n4. It would be helpful to discuss possible future directions.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "The authors would like express their gratitude to this reviewer for their insightful comments. \n\n**Q:** *The results of remark 7 can be discussed earlier maybe within the informal theorem 1.*\n\n**A:** We are going to replace Remark 7 with a formal version of Theorem 1 that includes the necessary assumptions and the complexity bounds (See Response to All). To avoid introducing symbols in the introduction, we keep the informal version of Theorem 1 the way it is and refer to its formal version for details to avoid complications.\n\n**Q:** *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.*\n\n**A:** Thanks for pointing out the notation convention. Indeed, we can rewrite the bound in Lemma 6 in terms of $(\\kappa,\\gamma)$ as opposed to spectral radius. We will point this out in our revision. However, we decided to also keep the explicit  appearance of spectral radius in the bound to facilitate comparison with the related literature where spectral radius appears in the respective bounds (Fazel et. al. 2018, Tsiamis & Pappas, 2023).\n\n**Q:** *It wasn't clear to me in the first place why singularity of $H^\\intercal H$ requires a significantly different treatment than LQR case. maybe you can clarify this earlier in the text*\n\n**A:** \nThe existing convergence results for the LQR problem rely on the positive-definiteness of the covariance of the initial state. For instance, the constant $\\mu = \\lambda_{\\min}(\\Sigma)$ appears in all bounds in (Fazel et. al. 2018). We hint to this difference on line 51 of Introduction and provide more details in Remark 2 after we introduce the dual LQR problem in Proposition 1. We will modify Remark 2 to further clarify the difference with the existing analysis.  \n\n**Q:** *It would be helpful to discuss possible future directions.*\n\n**A:** We will include the following directions for future research:\n- Single trajectory data: A direction for future research is to study how to adapt the proposed algorithm and error analysis for the setting when a single long trajectory is available as opposed to several independent trajectories of finite length. \n- In-accurate system matrices: An important research direction is to carry-out a robustness analysis, similar to its LQR dual counterpart, to study the effect of the error in system parameters on the policy learning accuracy. \n- Nonlinear setting:  The ultimate research goal is to use the recently introduced duality in nonlinear filtering (Kim. 2022) as a bridge to bring tools from RL to nonlinear filtering.  \n\n**Q:** *How essential is it to assume bounded noise for propositions 4 and 5?*\n\n**A:** We are using standard Matrix Bernstein Inequality which requires almost sure norm-bounded realization of the random matrices. It is possible to improve this using more advanced results on concentration inequalities which is part of our future research direction.  \n\n**Q:** *In figure 1a, could you explain why we see that $M=10$ case seems like the best performing , even better than $M=30$?*\n\n**A:** This was due to a mistake in our code. Please see the general response and the corrected figures in the accompanying pdf. "}, {"review_id": "M17rWh2PhQ", "reviewer": "Reviewer_aTTt", "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.", "questions": "None", "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.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\n\nquality: provides detailed theoretical results and analysis.\n\nclarity: 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:\n - 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;\n - 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);\n - maybe comparison with some existing methods on real data is preferred.\n\n2. The organization of this paper can be improved. For example,\n - numerical results can be put in main paper.\n - 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).\n\n3. Some typos:\n - Eq.(3b) $P(T)$ should be $P(t).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\nThe authors would like to express their gratitude to this reviewer for\ntheir insightful comments that helped us improve the\npresentation and empirical results of this manuscript.\n\n***Q:** The paper lacks enough empirical experiments to support their\nidea. The only two figures appear in the supplementary materials, but\nthe linear convergence outside a region near optimal, along with reasons\nwhy performances of the $M=20$ and $T=200$ case is different from other\nsettings, is not presented clearly in this paper. It is suggested that:\nthe figures can be plot in the log scale to illustrate the linear\nconvergence; also it is better to illustrate in the plot the scale of\nthe \\\"no-linear-rate\\\" small region; additional studies to demonstrate\nwhy medium hyperparameters and , yield worst/best convergence rate among\nother hyperparameters (otherwise it is likely to think that the proposed\nSGD approach is not so robust to hyperparameters); maybe comparison with\nsome existing methods on real data is preferred.*\n\n**A:** Thanks for pointing out the strange nature of the empirical\nresults which made us to look closely at the code and find a mistake in\ncomputing the exact steady-state Kalman gain (the multiplication by the\n$A$ matrix is not included in the code). The mistake produces an error\nof the order $A - I = O(\\Delta t)$ which effected the relative order for\ndifferent $M$. The corrected figures are produced in the accompanying\npdf for the figures, which illustrates the expected order of the error\ncurves and linear convergence regime (the errors are averaged over $50$\nsimulations). Finally, please note that our contributions are mostly\nmethodological and theoretical: the empirical results are provided for\nillustration purposes. Extensive numerical experiments for specific\napplications and comparison with related approaches is the subject of a\nseparate work.\n\n***Q:** The organization of this paper can be improved. For example,\nnumerical results can be put in main paper. From my view, it is more\nnatural to first characterize the bias in estimated gradient (Sec.4.2)\nand then provide convergence guarantees under such biased gradient\n(Sec.4.1). Otherwise, it may lead to confusion on the need of\nconvergence analysis under biased estimates (e.g. the appeared in Lemma\n5 & Proposition 2).*\n\n**A:** Thanks for the suggestion about the organization of the paper. We\nwill move the numerical result to the main paper by moving supporting\nlemmas to the supplementary material. We will also interchange 4.1 and\n4.2 as it fits better to the the flow of the arguments.\n\n***Q:** The main limitation of the proposed approach is that the biased\ngradient causes the convergence rate to be linear only outside a small\nregion near the true optimal value. It may not seem so preferable if the\nregion is large, thus not ensuring exact convergence to optimal value.*\n\n**A:** We like to clarify that the convergence guarantee to a region\naround the optimal value is due to the finite-length of the data. The\nregion can be made arbitrary small by choosing larger length and larger batch-size. In\nparticular, to achieve $\\varepsilon$ error, we only require the length\n$T\\geq O(\\ln(1/\\varepsilon))$ and $M\\geq O(1/\\varepsilon)$. See the formal version of Theorem 1 in\nResponse to All. Also, see the newly added Fig 1 (d) illustrating that\noptimality gap at the final iteration (i.e. the radius of the small\nneighborhood around optimality) is decaying linearly as a function of\ntrajectory length $T \\leq 50$---until the variance error dominates\nbeyond $T=50$. It is clear that, increasing batch size $M$ will allow\nfurther decrease of this optimality gap beyond $T=50$."}, {"review_id": "JjANrZRKii", "reviewer": "Reviewer_yyZM", "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. ", "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. ", "limitations": "NA", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "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;\n+) the dual of learning the Kalman gain and the optimal control gain in the data-driven setting;\n+) 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. \n-) 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?\n-) 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?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive comments, clarifications, and reference to relevant literature that will indeed improve this manuscript.\n\n**Q:** *The setup is not very practical as the system matrices are assumed perfectly known but only the covariance matrices are unknown...*\n\n**A:** Please see our response to all. \n\n**Q:** *For the learning problem described in lines 106-108, it is unclear...*\n\n**A:** Please note that lines 106-108 are not intended as precise mathematical statement of the problem, but as a formal qualitative\ndescription: given independent realizations of output data with length $T$, our goal is to learn the steady-state Kalman gain. Our result\n(formerly Remark 7, now Theorem 1) shows that in order to learn the steady-state Kalman gain up to $\\varepsilon$ accuracy, it is sufficient\nfor the time horizon to satisfy $T\\geq O(\\ln(1/\\varepsilon))$. The precise mathematical problem we intend to solve is the steady-state\noptimization problem (10).  The uniqueness of steady-state Kalman filter gain $L_\\infty$ is guaranteed under Assumption 2.\n\n**Q:** *In (1), are uncorrelated random vectors enough for deriving the optimal Kalman filter...*\n\n**A:** Yes, uncorrelated random vectors is enough to establish that Kalman filter provides the best *linear* MSE estimate of the state given the\nobservations (Thm. 2 in Kalman, 1960). The word *linear* was missing in the text, We will add this in the revision. Note that the error analysis also does not require independent noise. \n\n**Q:** *Also in the formulation of (5), what are random quantities and do we have any condition expectations or not?*\n\n**A:** The expectation in (5) is taken over all the random variables;\nconsisting of the initial state $x_0$, dynamic noise $\\xi(t)$, and\nmeasurement noise $\\omega(t)$ for $t= 0, \\cdots, T$. The conditional\nexpectation is not necessary (the estimate is constrained to be\nmeasurable with respect to the history of observation).\n\n**Q:** It would be great if the results can be compared with more related works on learning the Kalman filter under different settings; \n\n**A:** Thanks for pointing us to the relevant references that we missed\nin our literature survey. We will include these references along with\nthe summary of the following comparison in our revision.\n\n(Zheng, Y. et al. ) establishes an end-to-end sample\ncomplexity bound on learning a robust LQG controller--establishing a nice trade-off between optimality and robustness. As the system parameters are also unknown, this work only considers the *open-loop stable* systems. While our filtering design problem is based on the knowledge of system parameters, we do not require the open-loop stability\nassumption and its robustness analysis is part of our future work. Furthermore, the complexity\nbounds in (Zheng, Y. et al. ) depends on the length of trajectory and  scale as $O(1/\\sqrt{N})$ in number of trajectories whereas ours does not depend on length and scales as $O(1/N)$.\n\n(Zhang, X. et al.) considers the problem of\nlearning the steady-state Kalman gain but in a different setup: The\nmodel is assumed to be completely unknown. However, the algorithm\nrequires access to a simulator that provides noisy measurement of the\nMSE  $\\mathbb E[\\|X(t)- \\hat{X}(t)\\|^2]$ which requires generation of\nground-truth state trajectories $X(t)$ (see Assumption 3.2 in the\nreference). The proposed approaches are different: zeroth-order global\noptimization vs first-order stochastic gradient descent. Sample complexity result of our approach and their approach is similar. However, it is difficult to provide more detailed comparison as explicit dependence of the error terms on\nproblem dimension is not provided.\n\n(Liu, W. et al) considers the problem of\nsimultaneously learning the optimal Kalman filter and linear feedback\ncontrol policy in LQG setup. Their approach involves solving SDP\nproblems using input-state-output trajectories. Their result, for the\nthe case when trajectories involve noise, relies on the assumption that\nthe magnitude of the noise can be made arbitrary small. This is in\ncontrast to our setup where we only assume a bound on the noise level\nand do not require access to state trajectories."}, {"review_id": "MQGSiFrQp3", "reviewer": "Reviewer_4EhD", "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.", "questions": "I ask for a more detailed proof for Thm. 2 (see above).\n\nIn addition, a summary of all assumptions, results and notations can be very useful.\n\n\n\nMinor typos:\n\nl. 249 't' should be replaced by $\\gamma$.\n\nl. 276 I think i should go between 1 and T-1.\n\nl. 309 quite.\n", "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.\n\n", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\nProof of SGD convergence and error bounds are novel as well, even if derived under very strong assumptions.\n\n[r1] Cohen A. et al., \"Online Linear Quadratic Control\", 2018 \n\n", "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).\n\nParticularly, 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.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q**: *... However, it is still very hard to follow the assumptions...*\n\n**A**: Please see the Response to All for clarification on the technical results and the changes we made for the revision.\n\n**Q**: *...Particularly, Thm.2 and it's proof are not clear ...* \n\n**A**: We provide the following observation that clearly states the implications of Theorem 2 followed by its detailed proof:\n\n*Observation 1*. Combining Theorem 2 and the PL property (11a) results in a sample complexity for our\nalgorithm. In particular, it follows that  $J(L_k)-J(L^*)\\leq \\varepsilon$, if $s_0\\leq \\frac{\\sqrt{c_1(\\alpha) \\varepsilon}}{4}$, $s\\leq \\frac{1}{4}$, and the number of steps\n$k>\\ln(\\frac{\\varepsilon}{\\alpha})/\\ln(1-\\frac{c_1(\\alpha)}{18\\ell(\\alpha)}))$.\n\nWhile the original version of Theorem 2 is stated for any choice of $\\epsilon \\in (0,1)$, for simplicity we present its proof for the special case of $\\epsilon = 1/2$:\n\n*Proof of Theorem 2.* The first step of the proof is to show that the\nassumption of the Proposition 2 is satisfied for\n$E=\\nabla \\widehat J(L)$ for all\n$L \\in \\mathcal{S}\\_\\alpha \\setminus \\mathcal{C}\\_{\\gamma/2}$. This is\ntrue because $$\\begin{aligned}\n    \\|\\nabla \\widehat J(L) - \\nabla J(L)\\| \\leq s\\|\\nabla J(L)\\| + s_0 \\\\\n    \\leq s\\|\\nabla J(L)\\| + \\frac{\\gamma}{2} \\|\\nabla J(L)\\|\\\\\n    \\leq \\gamma \\|\\nabla J(L)\\|\n\\end{aligned}$$ where the first inequality follows from Assumption 3,\nthe second inequality follows from $L \\not \\in C_{\\gamma/2}$ (i.e.\n$s_0\\|\\nabla J(L)\\|\\geq \\gamma/2$), and the last step follows from the\nassumption $s\\leq \\gamma/2$.\\\nThe rest of the proof relies on repeated application of Proposition 2.\nIn particular, starting from\n$L_0 \\in \\mathcal{S}\\_\\alpha \\setminus \\mathcal{C}\\_{\\gamma/2}$, the\napplication of Proposition 2 implies that\n$L_1\\coloneqq L_0 - \\bar\\eta \\nabla\\widehat J(L_0)$ remains in the same\nsublevel set, i.e., $L_1 \\in \\mathcal{S}\\_{\\alpha}$, and we obtain the\nfollowing linear decay of the cost value:\n$$J(L_1) -J(L^*) \\leq \\left[1-c_1(\\alpha)\\bar\\eta{(1 - \\gamma)}/2\\right] [J(L_0)- J(L^*)].$$\nNow, if $L_1 \\in \\mathcal{C}\\_{\\gamma/2}$ then we stop; otherwise\n$L_1 \\in \\mathcal{S}\\_\\alpha \\setminus \\mathcal{C}\\_{\\gamma/2}$ and we can\nrepeat the above process to arrive at\n$$J(L_2) -J(L^*) \\leq \\left[1-c_1(\\alpha)\\bar\\eta{(1 - \\gamma)}/2\\right]^2 [J(L_0)- J(L^*)].$$\nRepeating the process generates a sequence of policies\n$L_0, L_1, L_2 ...$ with a combined linear decay of\n$$J(L_k) -J(L^*) \\leq \\left[1-c_1(\\alpha)\\bar\\eta{(1 - \\gamma)}/2\\right]^k [J(L_0)- J(L^*)],$$\nunless at some iteration $j$, we arrive at a policy $L_j$ such that\n$L_j \\in \\mathcal{C}\\_{\\gamma/2}$. This completes the proof. ◻\n\n\n\n**Q**: *...convergence is guaranteed from every initial policy, but...I might be missing something...*\n\n**A**: \nWe think the missing point here is the PL property of the cost that seems to understate the result of Theorem 2. As shown in Lemma 2 (and discussed in Remark 3), the cost maintain PL property on each sublevel set. In particular (11a) implies that on each $\\mathcal S_\\alpha$ , $\\|\\nabla J (L)\\|\\_F$ characterizes the optimality gap $J(L) - J(L^*)$ by:\n$$c_1(\\alpha) [J(L) - J(L^*)] \\leq  \\|\\nabla J(L)\\|\\_F^2$$ \nfor some constant $c_1(\\alpha)$. This implies that if we have arrived at a candidate policy $L_k$ for which the gradient is small, then the optimality gap should be small (involving the constant $c_1(\\alpha)$\nthat is independent of $L_k$).\n\nThis is the reason that in Theorem 2, it suffices to argue about the generated sequence $L_k$ to have a linear decay unless entering a small neighborhood of $L^*$ containing policies with small enough gradients (denoted by $\\mathcal{C}\\_\\tau$). In particular, if for some $j<k$, we arrive at some policy $L_j \\in \\mathcal{C}\\_\\tau$, then by (11a) we can conclude that:\n$$J(L_j)-J(L^*) \\leq \\frac{1}{c_1(\\alpha)} \\|\\nabla J(L_j)\\|\\_F^2  \\leq \\frac{s_0^2}{c_1(\\alpha) \\tau^2},$$\nwhich is directly controlled by the bias term $s_0$. This is the bound used also in the argument of Remark 7. We believe this is the missing point for causing the confusion about what happens when the trajectories enter this region.\n\nAdditionally, as stated in the introduction, every (stabilizing) initial policy $L_0$ amounts to a finite value of $J(L_0)$ and thus lies in some\nsublevel set $S_\\alpha$. So, starting from such $L_0$, Theorem 2 \nguarantees linear decay of the optimality gap till the trajectory enters\nthat small neighborhood. Finally, note that the radius of this\nneighborhood $\\mathcal{C}_\\tau$ is characterized by the bias term $s_0$\nwhich itself is exponentially decaying to zero in the trajectory length\n$T$.\n\n\n**Q:** *... a summary of all assumptions, results....*\n\n**A**: Assumption 1 sates that the linear system is detectable. This is the minimum requirement to make the estimation problem well-posed. \n\nAssumption 2 states that the linear system is observable. This stronger assumption is made in lieu\nof Assumption 1 to improve the clarity of the analysis with less system theoretic\ntechnicalities. \n\nAssumption 3 states an error bound on the gradient oracle. This is made in order to provide an independent analysis of the SGD algorithm\nfor locally Lipschitz functions in presence of gradient bias. This assumption is later verified by Thm. 3. \n\nAssumption 4 assumes bounded process and observation noise. This is made to facilitate application of matrix concentration inequalities.  \n\nFinally, we now have a complete nomenclature that is added to the supplementary materials.\n\n**Q**: *The online method uses a surrogate loss...*\n\n**A:** If the system is non-observable there is no guarantee for existence of a stabilizing policy unless the system is detectable (Assumption 1). In fact, detectability is a necessary and sufficient condition for well-posedness. While our analysis is presented for observable systems, we believe that the extension to detectable case is possible by adopting more system theoretic tools in Lemma 1."}]

Author rebuttal:
We appreciate reviewers' feedback and suggestions that have helped improve the paper. We provide a summary of the response to the main concerns here, followed by individual responses to the reviewers. 

**Presentation of the technical results:** In order to improve the presentation of the technical result, we will make the following changes to the paper: 

- Remark 7 will be replaced with the formal statement of Theorem 1. This will include the main result and the necessary assumptions: 

**Theorem 1.** *Consider the linear system (1) under Assumptions 2 and 4. Suppose the SGD algorithm is implemented  with initial stabilizing gain $L_0$, the step-size $\bar\eta \coloneqq \frac{2}{9 \ell(J(L_0))}$, for $k$ iterations,  a batch-size of $M$, and data-length $T$. Then, $\forall \varepsilon>0$ and with probability larger than $1-\delta$, $J(L_k)  - J(L^\*)\leq \varepsilon$ if $$T \geq  O(\ln(\frac{1}{\varepsilon})),\quad  M \geq  O(\frac{1}{ \varepsilon}\ln(\frac{1}{\delta}) \ln(\ln(\frac{1}{\varepsilon}))), \quad \text{and}\quad k \geq O(\ln(\frac{1}{\varepsilon})).$$*

- In the beginning of Section 4, we will give a roadmap to navigate the technical results that concludes the proof of Theorem 1: 
1. Section 4.1 is concerned with the convergence analysis of the SGD algorithm under the assumption that oracle gives a gradient estimate that satisfies $\|\nabla\widehat J(L) - \nabla J(L)\|_F \leq s \|\nabla J(L)\|_F + s_0$ whenever $\nabla J(L) \ge \frac{s_0}{\tau}$ for $s,\tau \in (0,1)$, and $s_0>0$. The main result of this section is Thm.2 which concludes the linear convergence of the iterates for sufficiently small $s_0$, i.e. 
$J(L_k)-J(L^\*)\leq \varepsilon$, if $s_0\leq O(\sqrt{\varepsilon})$ and $k>O(\ln(\frac{1}{\varepsilon}))$. 

2. Section 4.2 is concerned with the bias-variance error analysis of the gradient estimate, summarized as the main result in Thm. 3. It gives the sufficient values for the batch-size $M$ and trajectory length $T$ that provides the desired bound on the gradient estimate error required in Thm.2 with arbitrary small $s$ and $s_0$. 

3. Combining the results from Thm. 2 and Thm. 3 concludes the main result Thm. 1. A proof sketch is provided at the end of this response. 

**Explanation of the empirical result:** Thanks for pointing out the strange nature of the empirical results which made us reexamine the code and find a mistake in computing the exact steady-state Kalman gain (the multiplication by the $A$ matrix was not included in the code). The mistake produces an error of the order $A - I = O(\Delta t)$ which effected the relative order for different $M$. The corrected figures are produced in the accompanying pdf, which illustrates the expected order of the error curves and linear convergence regime. We also provide additional figures for the error at the final iteration, as a function of batch-size $M$ and time-horizon $T$. The numerical results serve to illustrate and validate the presented theoretical results. We leave extensive numerical experiments with real data on applications and empirical comparison with existing approaches for a separate work. 

**limitations of the learning setup:** We agree that the perfect knowledge of the system matrices is a strong assumption. Our perspective is to separate the two problems of  identification of system matrices and the learning of the Kalman gain. This is aligned with certain practical considerations as we explain below. The system identification procedure  occurs through the application of physical principles and collection of data from experiments in a controlled environment (e.g., in a wind tunnel). However, identifying the noise covariance matrices strongly depends on the operating environment which might be significantly different than the experimental setup. Therefore, it is common in engineering applications to use the learned system matrices and tune the Kalman gain to improve the estimation error. Please see [Ref 1] for the application of this procedure for gust load alleviation on aircraft wings and [Ref 2] for estimation in chemical reactor models.  We also emphasize that the assumed learning setup has a rich history in adaptive filtering with numerous references with a  recent survey on this topic [Ref 3]. Our plan for future research is to carry-out a robustness analysis, similar to  its LQR dual counterpart in [Ref 4, Ref 5], to study the effect of the error in system parameters on the learning accuracy. 

[Ref 1] Hinson KA, Morgansen KA, Livne E, ``Autocovariance least squares noise covariance estimation for a gust load alleviation test-bed,'' AIAA SCITECH 2022 Forum, 2021. 

[Ref 2] Odelson BJ, Lutz A, Rawlings JB. ``The autocovariance least-squares method for estimating covariances: application to model-based control of chemical reactors,'' IEEE Trans. Control Syst. Technol., 2006 

[Ref 3] L. Zhang, D. Sidoti, A. Bienkowski, K. R. Pattipati, Y. Bar-Shalom, and D. L. Kleinman,
391 ``On the identification of noise covariances and adaptive Kalman filtering: A new look at a 50
392 year-old problem,'' IEEE Access, vol. 8, pp. 59362–59388, 2020

[Ref 4] Safonov, M. G., and W. E. I. Z. H. E. N. G. Wang. ``Singular value properties of LQ regulators,'' IEEE transactions on automatic control 37.8 (1992): 1210-1211.

[Ref 5] Chen, Ci, and Anthony Holohan. ``Stability robustness of linear quadratic regulators.'' International Journal of Robust and Nonlinear Control 26.9 (2016): 1817-1824.

*Formal Proof of Theorem 1.* According to Thm.3, Assumption 3 holds at each iteration with probability at least $1-\delta$, if  $T \geq O(\ln(1/s_0))$ and $M \geq O(\ln(1/\delta)\big/ s_0^2)$. As a result, Thm.2 is valid, hence 
$J(L_k)-J(L^\*)\leq \varepsilon$, if $s< \frac{1}{4}$, $s_0\leq O(\sqrt{\varepsilon})$ and $k>O(\ln(\frac{1}{\varepsilon}))$. 
 Finally, the claim follows by combining the above bounds and using union bound for computing the failure probability of $k$ iterations.◻

 


Meta-review: The authors consider the problem of learning the optimal (Kalman) filter for a linear system with unknown noise covariance matrices, giving a convergence analysis for SGD with bias-variance error bounds logarithmic in dimension. In discussion the authors justified the practicality of the problem setup. Reviewers found the contributions technically interesting and novel. The only reviewer giving a low rating has not acknowledged the author rebuttal, and is mainly concerned with experiments; the authors have adjusted their experiments in response, and besides, the contribution is mainly theoretical. I recommend acceptance.
Decision: Accept (poster)