Streaming Linear System Identification with Reverse Experience Replay
Authors: Suhas S Kowshik
Dheeraj Mysore Nagaraj
Prateek Jain
Praneeth Netrapalli
Venue: NeurIPS 2021 Poster (2021)
Keywords: Linear System Identification
Streaming Algorithms
Experience Replay

Abstract: We consider the problem of estimating a linear time-invariant (LTI) dynamical system from a single trajectory via streaming algorithms, which is encountered in several applications including reinforcement learning (RL) and time-series analysis. 
While the LTI system estimation problem is well-studied in the {\em offline} setting, the practically important streaming/online setting has received little attention. Standard streaming methods like stochastic gradient descent (SGD) are unlikely to work since streaming points can be highly correlated. 
In this work, we propose a novel streaming algorithm, SGD with Reverse Experience Replay (SGD-RER), that is inspired by the experience replay (ER)  technique popular in the RL literature. SGD-RER divides data into small buffers and runs SGD backwards on the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error. Thus, we provide the first -- to the best of our knowledge -- optimal SGD-style algorithm for the classical problem of linear system identification with a first order oracle. 
Furthermore, SGD-RER can be applied to more general settings like sparse LTI identification with known sparsity pattern, and  non-linear dynamical systems. Our work demonstrates that the knowledge of data dependency structure can aid us in designing statistically and computationally efficient algorithms which can ``decorrelate'' streaming samples. 

Streaming Linear System Identification with Reverse Experience Replay
Prateek Jain Google Al Research Lab, Bengaluru, India 560016
Suhas Kowshik Department of EECS MIT, Cambridge, MA 02139 suhasklmit.com
prajain@google.coom
Dheeraj Nagaraj Department of EECS MIT, Cambridge, MA 02139 dheeraj @mit edu
Praneeth Netrapalli Google AI Research Lab, Bengaluru, India 560016 pnetrapalli@google com
Abstract
We consider the problem of estimating linear time-invariant (LTI) dynamical system from single trajectory via streaming algorithms, which is encountered in several applications including reinforcement learning (RL) and time-series analysis. While the LTI system estimation problem is well-studied in the offfine setting, the practically important streaming/online setting has received little attention. Standard streaming methods like stochastic gradient descent (SGD) are unlikely to work since streaming points can highly correlated. In this work, we propose a novel streaming algorithm, SGD with Reverse Experience Replay (SGD- RER), that is inspired by the experience replay (ER) technique popular the RL literature. SGD RER divides data into small buffers and runs SGD backwards the data stored in the individual buffers. We show that this algorithm exactly deconstructs the dependency structure and obtains information theoretically optimal guarantees for both parameter error and prediction error. Thus, we provide the first to the best of our knowledge optimal SGD-style algorithm for the classical problem linear system identification with a first order oracle. Furthermore, SGD RER can be applied to more general settings like sparse LTI identification with known sparsity pattern, and non-linear dynamical systems. Our work demonstrates that the knowledge of data dependency structure can aid us in designing statistically and computationally efficient algorithms which can "decorrelate" streaming samples.
1 Introduction
this paper, we study the problem learning linear-time invariant (LTI) systems, where the goal is to estimate the matrix A E Rddd from the given samples (Xo.... XT.....X) that obey:
X = A" tr, X, ER
i.i.d. Yr
14,
where μ is an unbiased noise distribution. The problem is central in control theory and reinforcement learning (RL) literature (1 It is also equivalent estimating Vector Autoregressive (VAR) model popular in the time-series analysis literature finding gene regulatory information network
3 where it has been used in several applications like
Despite a long line of classical literature for the problem, most of the existing results focus on the offline setting, where all the samples (Xo.... XT) are available apriori. In this setting, ordinary
35th Conference on Neural Information Processing Systems (NeurIPS 2021).

---

least squares (OLS) method that estimates A as, À = mig TT-
|| 112 is known
to be nearly optimal 5 However, such offline solutions do not apply to the streaming setting where A needs to be estimated online that has applications in several domains like RI., large-scale forecasting systems, recommendation systems g
In this paper, we study the above mentioned problem of learning LTI systems via first order gradient oracle with streaming data. The goal is design an estimator that provides accurate estimation while ensuring nearly optimal time complexity and space complexity that is nearly independent of T'. Note that due to specific form arising in linear regression, the optimal solution to OLS can be estimated in online fashion using Sherman- Mortunn---r--o---- -ooddbury formula. But such solution is limited and does not apply to practically important settings like generalized non-linear dynamical system or when A' is high- ligh-dimensional and has special structure like low-rank or sparsity (9 10]
So, in this work, focus designing Stochastic Gradient Descent (SGD) style methods that can work directly with first order gradient oracle, and hence is more widely applicable to the settings mentioned above. In fact, after the first appearance of this manuscript, the algorithm (SGD RER) and the techniques introduced in this paper were used to obtain near-optimal guarantees for learning certain classes of non-linear dynamical systems | as well as in Q-learning tabular MDPs in RL [2]. We note that prior to MI. even optimal offline algorithms were unknown for such non-linear systems.
SGD is a popular method for general streaming settings, and has been shown to be optimal for problems like streaming linear regression [33. However, when the data has temporal dependencies, as in the estimation of linear dynamical systems, such a naive implementation of SGID may not perform well as observed in [14 15]. In fact, for linear system identification, our experiments suggest that SGD suffers from a non-zero bias (Section 6). In order to address temporal dependencies in data, practitioners use heuristic called experience replay, which maintains buffer of points, and samples points randomly from the buffer. However, for linear system identification, experience replay does not seem to provide an accurate unbiased estimator for reasonable buffer sizes (see Section 6).
In this work, we propose reverse experience replay for linear system identification. Our method maintains small buffer of points, but instead of random ordering, replay the points in reverse order. We show that this algorithm exactly unravels the temporal correlations to obtain a consistent estimator for A Similar to the standard linear regression problem with i.i.d samples,
can break the error in two parts: a) bias: that depends on the initial error |A4- - 1.. b) variance: the steady state error due noise 77. We show that our proposed method, under fairly standard assumptions and with a small buffer size, is able to decrease the bias at fast rate, while the variance error is nearly optimal (see Theorem D. matching the information theoretic lower bounds [5] Theorem 2.3]. To the best of our knowledge, we provide first non-trivial analysis for a purely streaming SGD-style algorithm with optimal computation complexity and nearly bounded space complexity that is dependent logaritbmically on T. We note here that the idea of reverse experience replay was independently discovered in experimental reinforcement learning by [16] based on reverse replay observed in Hippocampal place cells 17 in Neurobiology. We also refer to [18] for more on this connection.
In addition to the transition matrix estimation error |A - A" ||. we also provide analysis of prediction error, i.e., E||AX A x|]]] (see Theorem 2). Here again, we bound the bias and the variance part of the error separately. We further derive new lower bounds for prediction error (see Theorem 4 and show that our algorithm is minimax optimal, under standard assumptions on the model. As mentioned earlier, our method work with general first order oracles, hence applies to more general problems like sparse LTI estimation with known sparsity structure and unlike online OLS methods, SGD RER has nearly optimal time complexity. Finally, we also provide empirical validation of our method on simulated data, and demonstrate that the proposed method is indeed able to provide error rate similar to the OLS method while methods like SGD and standard experience replay, lead to biased estimates.
Related Work. Due to applications in RL, recently LTI system identification has been widely studied. In particular, [19 studied the problem in offline setting under the "stability" condition, i.e., the spectral radius (p(A*) of A" is a constant bounded away from 1. The sequence of papers
( G 20, 21 provide optimal analyses of the offline OLS estimator beyond assumptions of stability. That is, they show that OLS recovers A near optimally even the process defined by ① is stable
but does not mix within time T (when p(A') is 1 - O(1/T)) or is unstable (when p(AA) is larger

---

than 1). Further [5 22 provide information theoretic lower bounds for the LTI system identification
problem. [T] 23 24 consider the problem of identifying non-linear dynamical systems of the form X++1 = 6 X + T) where @ is one dimensional link function which acts co-ordinate wise. In this setting, however, there no closed for expressions for the estimator of A* [23 24 give offline algorithms whose error guarantees are worse off by factors of mixing time whereas 11 obtains near
optimal offline and streaming algorithms for this setting. In fact, [ uses SGD - RER which was first introduced in this work in order to obtain the streaming algorithm.
LTI identification problem has been studied in time series forecasting literature as well. For example, 25 obtains asymptotic consistency results for system identification problem and [26] 27 consider the problem of finite time recovery. Both consider certain parameterized predictor for a linear system with empirical risk minimization for the parameter and analyzes the deviation from population risk. Similarly, 28 also studies generalization error guarantees. In contrast, our work is able to provide precise bias and variance (similar to generalization error) of the estimator in the streaming setting, and show that the asymptotic error is minimax optimal.
29 studied SISO systems with observations (Ir, Mr) E R and a hidden state for which is high dimensional, thus their model and applications are significantly different than the LTI system we study. For the SISO system, [29] analyzes SGD to provide error bounds contain (a large) polynomial in the hidden state dimension. Here, the hidden state has an evolution similar to Equation T whereas "i....,,) ZT are drawn i.i.d from some distribution.
System identification has been studied in the context of partially observed LTT systems as well. Recent works [9 30 34
focus on identifying a certain Hankel-like matrix of the system. These are not directly comparable to the fully observed setting in this work since the model parameters identifiable only upto similarity transformation in the partially observed setting.
Recently, there has been exciting line of work in the related domain of online control (see 335 and references therein). The state equation studied in these papers also contain an additive term of Bu, for some unknown matrix B and control signal it and the noise 17 is either stochastic (as in (35]) or adversarial (as in (6)38). The goal is to output control signals u, after observing X1, X1...., Xy, such that the cost Σ, cr (X,, u,) is minimized for some sequence of convex costs 0z. We focus on the LTI system identification(or estimation) problem while the goal of the above mentioned line of work is design online controller.
We also note here another line of works [32 39
focused on online prediction of both fully observed and partially observed LTI systems, and the similar problem of time series forecasting by regret minimization 128 45). In particular, the main goal there is to design online prediction algorithms minimizing regret against a certain class (for instance, against Kalman filter with knowledge of the system parameters in the case of partially observed LTI systems). The situation considered in work is different in atleast two aspects: 1) we focus significantly parameter recovery or system identification and 2) our notion of prediction is prediction at stationarity which can be thought of as one-step regret (compared to T'sttep regret for instance in 39 40)).
Finally, 99] considers offline sparse linear regression with & penalty where the feature vector is derived from an auto regressive model. Similarly, [14] considers the problem of linear regression where the feature vectors come from a Markov chain. This line of work different from ours in that we try to estimate the parameters of the Markov process itself.
Paper Organization. We provide the problem definition and introduce the notations in the next section. We then present our algorithm and the key intuition behind it in Section We then present our main result in Section 4 and provide a proof sketch in Section 5 Finally, we present simulation results in Section
2 Problem Setting and Notation
In this section, we first introduce the data generation model, the required assumptions and then provide the precision problem definition. Throughout the paper, we use || to denote the operator norm of A unless otherwise specified. || denotes the Frobenius norm of A. (A) denotes
the i-th largest singular value of A, i.e., (A) = ai (A). s(A) == m (max(A)/oa (A)/amin (A) denotes the condition number of A. p(A) denotes the spectral radius of A. For two symmetrie matrices
3

---

A, B E Raxd we say A 3 Bf B - A is positive semidefinite (psd). For notational simplicity, we use C' to denote constant, and it's value can be different in different equations.
Linear Dynamical System/VA (()(()) model. Given an initial (possibly random) data point Xo which independent of the noise sequence, we generate the (X....., from the VAR model as:
x A Th, 0 O
where A Rdxd be the transition matrix. Let 77....,, Tr Ed be an i.dd noise sequence with O mean and finite second moment with probability measure p. We will denote this model by VAR(A", We also make the following assumptions about A", μ4, and Xu: Assumption 1. External Stability. ||A*|| <1
Assumption 2. Gaussian Noise. μ has co-variance E and all x E R., (x, is Ca E.x) sub-Gaussian. Further, Σ is full rank. Also, let μ4 := E [11~~1'] be the fourth moment of the noise.
Assumption 3. Stationarity. Xo n, the stationary distribution corresponding to (A ,1). Let
M4 E |
Due to Assumption 1 we can show that the law of the iterate XT from the VAR model defined above converges to stationary distribution π as T oo for arbitrary choice of Xo and has mixing time of the order Tmix O
(-- ). For simplicity, we will absorb C₁ into other constants. Finally, we will use (Zo..... Zr) ~ VAR(A", (1) to mean that Zu.... Zr is stationary
sequence corresponding to VAR(A", n)). We also note that the covariance matrix under stationarity, G Ex=, X.x E. A"*=(A"))=
Remark. is indeed possible to replace Assumption | with the weaker condition on the spectral radius of A p(A*)= < 1. While our results still hold in this case, the bound might have additional condition number factors. See Section A. for more details.
Remark. The full rank assumption E is needed for polynomial sample complexity
46
Problem Statement. Let (Xo, ..... XT) be sampled from VAR(A", (4) model for a fixed horizon T. Then, the goal is design and analyze online algorithm that uses only first order gradient oracle to estimate the system matrix A". That is, at each time-step т, we obtain gradient for the transition (X,, X Xx+1) and output estimate A,. The goal is ensure that each A, has small estimation eтror wrt A naturally, we would expect better estimation eπrоr with increasing J. We quantify estimation error using the following two loss functions:
Parameter error: Lop A p)) = ||A A+ll
Prediction error at stationarity: Cpedd (A; A", () = Ex || AX,
Note that the problem is equivalent to linear regression problems, but with dependent samples, making it significantly more challenging. Whenever Assumption hoolds, stationary distribution exists, so the prediction enror Lpee meaningful. Furthermore: Lereed ppred (A")
Tr [AA A (A GG] where G = XXx,XX..
3 Algorithm
As mentioned in related works, the standard OLS estimator that minimizes the empirical loss is known be nearly optimal in the offline setting :
T-1 Σ
AoIs = arg min
|AX, - 2
(3)
A
T=0
Note that for least squares loss, one can indeed maintain covariance matrix and residual vector to compute the OLS solution online. But such a solution does not work if we have access to only gradients and breaks down even for generalized linear models, whereas as the techniques introduced in this work has been extended to non-linear systems [[].

---

Buffer
in-buffer order
Gap
Gap
Buffer
Gap
Buffer
Gap
Figure 1:
Data Processing Order SGD RER. A cell represents data point. Time goes from left to right, buffers are also considered from left to right. Within each buffer, the data is processed in the reverse order. Gaps ensure that data successive buffers are approximately independent.
On the other hand, using standard SGD we can obtain update to A efficiently by using gradient the current point. That is, assuming Ag = we get the following SGD update (for all r 2 0):
Ar+1 = A,
-
where is the stepsize. While SGD is known to be an optimal estimator in certain streaming problems with i.i.d. data, for the VAR(A", ,1) problem the standard SGD does not apply, as samples (X,, x1+1 and (X++1, x+) are highly correlated. To see why this is the case, let us unroll the recursion for two steps and using Equation (
A A' (Ao A1 2
+ Xy Xxx
27 -1-27X1 x7
Note that the last term does not have mean because X₁ depends on 7o by Equation in the case when Ao A", this means that IEA, * A" in general. In fact, in Section 6 we show empirically that SGD with constant step-size converges to a significantly larger error than OLS, even when T is very large. This shows that we cannot naively treat this problem regressions. This is consistent with the results in 14 which show a similar behavior for constant step-size SGD with dependent data. Now, one use techniques like data drop that drops large fraction of points (either explicitly or during the mathematical analysis) from the stream to obtain nearly independent samples [14] 477, but such methods waste lot of samples and have significantly suboptimal error rate than OLS.
Even
collection of dl linear
So. the goal is to design streaming method for the problem of learning dynamical systems that at each time-step t provides an accurate estimate of A", while also ensuring small space+time complexity, We now present novel algorithm that addresses the above mentioned problem.
3.1 SGD with Reverse Experience Replay
We now discuss novel algorithm called SGD with Reverse Experience Replay (SGD RER) that addresses the problem of learning stationary auto-regressive models (or linear dynamical systems) in the streaming setting. Our method is inspired by the experience replay technique [48), used extensively in RL to break temporal correlations between dependent data. We make the following crucial observation. Suppose in Equation 4 instead of processing the samples in the order (X,, (XI.X2) X2) >
(2,Xx) (XT-2, XT-1) .... (X1, X2). Then,
(XT 1, XT), we process it in the reverse order. That is: (XT-1,X7)
A2 A =AAo (loo-)((1 (T 24 - (T -- 27 2
(1-
(5)
Now, observe that (Xr-2, X1--) are independent of 1/--1- Therefore the problematic last term, 211r--1 - XT 22)-2)) now has expectation 0. So the updates for reverse order SGD would be unbiased. This, however, requires us to know all the data points beforehand which is infeasible in the streaming setting. We alleviate this issue by designing SGD RER, which is the online variant of the above algorithm. SGD RER uses a buffer of large enough size to store values of consecutive data points and then performs reverse SGD in each of these buffers and then discards this buffer. Experience replay methods also use such (small) buffers of data, but typically samples point randomly from the buffer instead of the reverse order that propose. We refer to Figure an illustration of the proposed data processing order.
We present pseudocode of SGD RER in Algorithm 1
Note that the algorithm forms non- overlapping buffers of size S B + u. Here B is the actual size of the buffer while samples are used to interleave between two buffers that the buffers are almost independent of each other. Now
5

---

Algorithm 1: SGD RER
Input
:Streaming data { horizon T, buffer size B, buffer gap u, bound R. tail average
start:
Estimate Ag,t, for all a <ts N 1; ( +u
begin
Step-size: 7 8RB Total buffer size: <- B + Number of buffers: N + T/S Ag 0/ /Mnitiialization"/ for t t to N do Form buffer Buf (X)-1 ..11 where, X X(1-1).54
If Bi, s.t., || > R. then return Au, =0
for to B do
A A!- 2- (A 1- x s-1-i - (x
x
10
end
Aj A
Ift > a, then Au,t t 1 t-a 1
A/- 17-1
12
13
end
14 end
within a buffer, we perform the usual SGD but with samples read in reverse order. Formally, suppose we index our buffers by 0, 1,2, and let S = B + u be the total samples (including those that were dropped) the buffers. Let denote the total number
buffers in horizon Within
each buffer i, we index the samples as X where i = 0, 1,2, .... S - 1. That is X Xis+i is the i-th sample buffer Similarly of 1hS+1- Further let X =\t ((ss (1-1)- Similarly we set n²=; = 1)= Then, the algorithm performs the recursion stated in Line of Algorithm that the recursion can also written as,
Note
A+1 A = (4 A²) 2
+ 2ym 2"1"
(6)
for S N and sis
with Ab A'p and 18= Ap-
We then ignore the iterates corresponding to first buffers as part of the burn-in period, and output average of the remaining iterates a) at each step as that step's estimator (see Line 2 of Algorithm 1). That is, we have the tail-averaged iterate:
A-1==11 ---=1-
Áot 1 - r=a+1
Σ
A
We output the new iterate Au,t only at the end of each buffer t. At intermediate steps, S tB, we output Aa.t-1- Also, note that the tail average can be computed in small space and time complexity, by using running sum of the tail iterates. The update for each point is rank-one, so can be computed in time linear in number of parameters (O(d)). In the next section, we show that despite using small buffer size = B + u (that depends logarithmically on 2'), and by throwing of any problem paratiter-fraction of points u in each buffer, we
away small constant-independed are still able to provide error bound similar to that of OLS.
Main Results
We now state our main results with leading order terms. For simplicity, we only state the results for the tail average AN but similar result holds for any A., when = ((dBx(G) log" T). We 2
refer to Section for complete statements. Recall the problem setting, and the covariance matrix G : Ex=,XX XXT. Before stating the results, we choose the parameters B, R, and u as follows, which can be estimated using upper bounds on ||A"
1. < (T)y We use this to bound the norm of covariates in the next item.
22; R C(a) Tr(E) To 1- O(drmix log T) s.t. P ||++1| < R. TTTTT 2 T See
lemma in appendix.

---

3. 2 2
log
(mmi log T): B = 10u
A'
For all the results below, suppose that Assumptions I and holdd the stream of samples X; is sampled from VAR(A", 14) model described Section and that Rt B, a and u are chosen as above. Further we hide some mild conditions on N and T.
Theorem (Informal version of Theorem
S
Let the step size Y < min Brrii 8BR for some
constant depending only on C.. Then, with probability least T:00. have:
(d log T)x SCV To (G)
Log A ,) sSy
+ Lowwr Order Terms
Theorem (Informal version of Theorem 6 Consider the setting of Theorem 7 but where the step size 7 = min I BR. for some constant 2n
< Then, the following holds:
(CCmolAy Ni . m)
Tr(E) S C - d(TrE)
Lowwr Order Terms
T
where "lower order" is with respect to 4.
See Section Section F.3 for a detailed proof of the parameter error bound and see Section Section G.2 for detailed proof of the prediction error bound.
We now make the following observations:
(1) The dominant term in our bound on Lop (Theorem T matches the information theoretically optimal bound (up logarithmic factors) for the VARTA", pu) estimation problem [5] as long as || < 1 т for & E (0, 1/2). Note that despite working with dependent data, leading term in our error bound is nearly independent of mixing time Tmix In contrast, most of the existing streaming/SGD style methods for dependent data have strong dependence on Tiiix (14)
(2) SGD for linear regression with independent data 13 49), but with similar problem setting incurs
error O TT(2)) for Fpedd- So our bound for SGD RER matches the independent data setting bound in the minimax
(3) The space complexity our method is O Bd + d²) where B = (Tmix log 7) is independent of d and only logarithmically dependent T.
(4) Sparse matrices with known support: Suppose A is known to be sparse and we know the support (say by running L1 regularized OLS on a small set of samples). Let sy denote the sparsity of row j of A*. Then the SGD - RER algorithm can be modified to run row by row such that operates only on the support of row j. That is the covariates can be projected onto the support of each row. Then it can be shown that the prediction error is bounded O (Σi= o3 /T) where of is the j-th diagonal entry of Σ. Note that SGD RER requires only O( operations per iteration while applying online version of standard OLS would require (dd) operations. In the simple case of Σ 0²1, I, we note that G Z o²1 and hence the bound for Cpred
becomes O [sppp(1")]
We refer to Section O for a sketch of this extension.
Next, show that error bounds nearly information theoretically optimal. For the lower bound on Lop we directly use [5] Theorem 2.3].
Theorem 3. Let p < 1 and E 10,1 Let p. be the distribution O2). For any estimator À F, there exists an matrix A E IRdxd where A = for some orthogonal matrix O such that |omax and we have that with probability least 8:
A - A = (d (og(1/5))(1 -
(8)
T
Notice that in the setting of Theorem we have G G= - o (A = T-pl.. Therefore, Omin (G) 1-n² 1-p- The bound in Theorem matches the above minimax bound up to
o²
logarithmic factors.
Next we consider the prediction loss. We fix dimension d and horizon T and consider the class of VAR models M such that Assumptions and hold such that Tr(E(u)) B E R be fixed. Let
7

---

FF be the class of all estimators for parameter A given data (Zo...., Zr). We want to lower bound the minimax error:
(aminmax(M) == inf sup ((IZ))VAR((A ui Freed (f (J Zr)); A", ,1) Lpred (A"; A", ,1). fEF (A" JAJM
Theorem 4. For some universal constant e, have:
1 Lminmax 2 cB(d - min (
where 3 = Tr(E(n))
Note that the theorem shows that our algorithm is minimax optimal with respect to the prediction loss at stationarity, firedd See Section for a detailed proof the above lower bound.
Idea Behind Proofs
In this section, we provide an overview of the key techniques to prove our results. As observed in the discussion following Equation (5). when the data processed in the reverse order within a buffer, behaves similar to SGD for linear regression with i.i.d. data. Due to the gaps of size u, we can take the buffers to be approximately independent. Therefore, we analyze the algorithm as follows:
1. Analyze reverse order within a buffer using the property noted in Equation (5).
2. Treat different buffers to be i.i.d. due gap and present an i.i.d data type analysis.
To execute the proposed proof strategy, we introduce the following technical notions:
Coupled Process. For the real data points (X²), the points in different buffers are weakly dependent. In order to make the analysis straight forward, we introduce the fictitious coupled process X, such that X X, 2 1 for large enough a, for every data point X, used by SGD RER. We have the additional property that the successive buffers are actually independent for this coupled process. We refer to Definition 1 in the appendix for the construction of the coupled process X,.
Suppose SGD - RER with the coupled process X, instead of X, obtain the coupled iterates ÁÇ. We then show that Á A/. Thus it suffices analyze the coupled iterates Aς. We refer to Sections [ [ the details.
Bias Variance Decomposition. We consider the standard bias variance decomposition with individual buffers as the basic unit as opposed to individual data points. We D for the details. We decompose the error in the iterates into 1
refer to Section
the bias part (AtT
(Ao A Ha,B-1 and the variance part 27 E/ E5= n n X AT J+i. -I i6 where the matrices H H8,B-1 -T 2
(A--1 - _A*)
B-1
the independent 'contraction' matrices associated with each buffer This result in the geometric decay of the initial distance between (Au -*)). The variance part is due to the inherent noise present in the data. In Section F.I we first establish the exponential decay of the 'bias'. We then consider the second moment of the variance term. Observe that the distinct terms in the expression for (A'
are uncorrelated either due to reverse order
within a buffer noted in Equation (5) or due independence between the data in distinct buffers (due to coupling). This allows us to split the second moment into diagonal terms with non-zero mean and cross terms with zero mean. Diagonal terms are analyzed via recursive argument in Claim I and the following discussion in order to remove dependence on mixing time factors. The analysis for parameter recovery (the result of Theorem [ similar but we bound the relevant exponential moments using sub-Gaussianity of the noise sequence 7): to obtain high-probability bounds which when combined with standard e-net arguments give us guarantees for the operator norm error Lop-
Averaged Iterates. We then combine the bias and variance bounds obtained for individual iterates Section F.] to analyze the tail averaged output. Using techniques standard the analysis of SGD for linear regression, we finally show that this averaging leads error rates of the order d' We refer to Sections B (for parameter recover) and (for prediction error) for the detailed results.

---

Full-Avg: error buffer RandBiMod A
Tail-Avg: enror buffer c, RandBiMod
10
10
SGD
10
10
SGD EI
-Abeet - A'll
SGD-ER
SGD RER
SGD-RER
SGD RER
SGI-RER SGD-ER
3
SGIDED
10
SGD
SGD
OLS
102
103
10a
105 10a
103
10*
10
Buffer index
Buffer index
Figure Gaussian VAR(A* μ)): Parameter error for tail averaged and full average iterates of SGD - RER and baselines. SGD RER and OLS incur similar parameter error, while error incurred by SGD and SGD ER saturate significantly higher level, indicating non-zero bias. The parameters used are = 0.9, d = 5, T 10", B 100, u = 10. R is estimated and y = 1/2RR.
Picking the Step Sizes and Conditioning, Due to the auto-regressive nature of the data generation, the iterates can grow to be of the size O(1 1-p)) The step sizes need to be set small enough so that the X| < 1 in order for the SGD - RER iterations to not diverge to infinity. In the statement of the event where ||xX, are all bounded by sufficiently large number R for every r in order to ensure this property. The relevant events where the norm is bounded are defined in Section B Conditioning
Theorem we condition
these events results in previously zero terms to be not zero mean. Routine calculations using triangle inequality and Cauchy-Sehie Schwarz inequality ensure that the means still of the order yiz for any fixed constant
0. Furthermore, actually require Xx S 1 to show exponential contraction Hě n- matrices
step sizes such that due to the Grammian G as described next.
Probabilistic Results. We establish some properties of H5 random matrices in Section L. Specifically we refer to Lemmas 28 that IT H (1 Bo (G))* with high probability.
86, B- which are products of dependent
30 and 31 which establish
Experiments
In this section, we compare performance of our SGD - RER method on synthetic data against the performance standard baselines OLS and SGD, along with SGD -ER method that applies standard experience replay technique, but where points from a buffer are sampled randomly.
Synthetic data: We sample data from VAR(A", 14) with Xo 0, J (O, o²T) and A E Rddd generated from the "RandBiMod" distribution. That is, A UAU with random orthogonal U, and A is diagonal with [d/2] entries on diagonal being and the remaining diagonal entries are set to p/3. We set
5, p == 0.9 and ² 1. We fix horizon T 10" and set the buffer size as B = 100 and u = 10. To estimate R from the data, we use the first |2 log T| = 32 samples and set R as the sum of the norms of these samples. We let the stepsize be ZØ which aggressive compared to our theorems. We start the SGD RER and other S-i-eike algorithms from the second buffer onward.
For tail averaging, as described in algorithm I we ignore the first [log T' 16 buffers, and maintain running tail average at the end of each of the subsequent buffers. In figure we plot the parameter errors
AlogT, A and |oo, A versus the buffer index t as the algorithm runs for horizon T. For OLS, we include samples in the first buffer as well (which were used for estimating Rt. Clearly, SGD - RER has very similar performance that of OLS whereas SGD ER and SGD seem to display residual bias for the chosen step-size (which is logarithmic in the horizon T) and buffer lengths. We also observe similar behavior when we choose A pl.

---

7 Conclusion
In this paper, studied the problem of linear system identification in streaming setting and provided an efficient algorithm (SGD RER). We proved that SGD RER achieves nearly minimax optimal error rate, both in terms of parameter error as well as prediction error. Furthermore, using experiments, we validated that standard SGD as well as SGD with experience replay can have large bias error. Our algorithm and analysis demonstrates that the knowledge of dependency structure can aid us in designing accurate algorithms for dependent data.
This work opens up myriad of open questions about learning from dependent data in general and Markov processes in particular. Our work currently assumes a specific Markovian dependency structure extending the intuition and techniques handle more general data dependencies is an interesting open question. Further, our work does not address the question of recovering sparse system matrix with unknown sparsity pattern. So online learning of such linear dynamical systems with (unknown) sparsity pattern or low-rank structure is an exciting question with applications to domains like bioinformatics. Moreover, even in our linear setting, extending SGD RER to the situation of partially observed states with or without control inputs would be another direction to pursue. Finally, it would interesting to understand how the techniques introduced in this work perform in practical RI. settings where learning with data from Markov processes is essential.
Acknowledgments and Disclosure of Funding
D.N. was supported in part by NSF grant
S.S.K was supported in part by Teaching Assistantship (TA) from EECS, MIT. Part of this work was done when S.S.K was visiting Microsoft Research Lab India Pyt Ltd during summer 2020.
10

---

References
[1] Panqanamala Ramana Kumar and Pravin Varaiya. Stochastic systems: Estimation, identification. and adaptive control. SIAM, 2015.
[2] Behçet Açıkmeşe, John Carson, and Lars Blackmore. Lossless convexification of nonconvex control bound and pointing constraints of the soft landing optimal control problem. IEEE Transactions on Control Systems Technology. 21(6):2104-2133 2013.
[3] James Douglas Hamilton. Time series analysis. Princeton university press, 2020.
[4] André Fujita, João R Sato, Humberto M Garay-Malpartida, Rui Yamaguchi, Satoru Miyano, Mari C Sogayar, and Carlos Ferreira. Modeling gene expression regulatory networks with the sparse vector autoregressive model. BMC Systems Biology, 1:39, 2007.
[5] Max Simchowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. arXiv preprint 2018.
[6] Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In International Conference on Machine Learning, pages 5610-5618 8. PMLR, 2019.
[7] Christoph Hanck, Martin Arnold, Alexander Gerber, and Martin Schmelzer. Introduction to econometrics with University of Duisburg-Essen, 2019.
[8] Yin Zheng, Bangsheng Tang, Wenkui Ding, and Hanning Zhou. A neural autoregressive approach to collaborative filtering. In International Conference on Machine Learning, pages 764-773. PMLR, 2016.
[9] Sumanta Basu, George Michailidis, et al. Regularized estimation in sparse high-dimensional time series models. The Annals of Statistics, 13(4))1535--150 2015.
[10] Sumanta Basu, Xianqi Li, and George Michailidis. Low Rank and Structured Modeling of High-Dimensional Vector Autoregressions. IEEE Transactions on Signal Processing, 67()): 1207-1222, Mar 2019. ISSN 1941-0476. doi: 10.1 2018tsp..188.28777777
[11] Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj. and Praneeth Netrapalli. Near-optimal Offline and Streaming Algorithms for Learning Non-Linear Dynamical Systems. arXiv preprint arXiv:2/05. 1558, 2021.
[12] Naman Agarwal, Syomantak Chaudhuri, Prateck Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint arXiv:2 10.08440, 2021.
[13] Prateek Jain, Praneeth Netrapalli, Sham M Kakade, Rahul Kidambi, and Aaron Sidford. Parallelizing stochastic gradient descent for least squares regression: mini-batching, averaging. and model misspecification. The Journal of Machine Learning Research, 18(1):8258-822) 8299,
2017.
[14] Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms. Advances in Neural Information Processing Systems, 33, 2020.
[15] László Györf and Harro Walk. On the averaged stochastic approximation for linear regression. SIAM Journal on Control and Optimization, 34(1):31-61 1996.
[16] Egor Rotinov. Reverse Experience Replay. arXiv preprint arXiv: 2019.
[17] R Ellen Ambrose, Brad E Pfeiffer, and David Foster. Reverse replay of hippocampal place cells is uniquely modulated by changing reward. Neuron, 91(5):1124-1136, 2016.
[18] Matthew T Whelan, Tony Prescott, and Eleni Vasilaki. A robotic model of hippocampal reverse replay for reinforcement learning, arXiv preprint arXiv:2102.11914
2021. 2021.
11

---

[19] Samet Oymak and Necmiye Ozay. Non-asympiotic identification of Iti systems from a single trajectory. In 2019 American Control Conference (ACC), pages 5655-5661. IEEE, 2019.
[20] Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time identification in unstable linear systems. Automatica, 11:342-353, 2018.
[21] Yassir Jedra and Alexandre Proutiere. Finite-time Identification of Stable Linear Systems Optimality of the Least-Squares Estimator. 2020 59th IEEE Conference on Decision and Control (CDC), pages 996-1001. IEEE, 2020.
[22] Yassir Jedra and Alexandre Proutiere. Sample complexity lower bounds for linear system identification. In 2019 IEEE 58th Conference on Decision and Control (CDC), pages 2676- 2681. IEFE, 2019.
[23] Yahya Sattar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. arXiv preprint arXiv:2002.088: 085388 2020.
[24] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, pages 851-861. PMLR, 2020.
[25] TL. Lai and CZ. Wei. Asymptotic properties of general autoregressive models and strong consistency of least-squares estimates of their parameters. Journal of multivariate analysis, 13 (1):1-23, 1983.
[26] Marco C Campi and Erik Weyer. Finite sample properties of system identification methods. IFFE Transactions on Automatic Control, 1329)11329-1344 2002.
[27] Mathukumalli Vidyasagar and Rajeeva Karandikar. A learning theory approach to system identification and stochastic adaptive control. In Probabilistic and randomized methods for design under uncertainly, pages 265-302. Springer, 2006.
[28] Vitaly Kuznetsov and Mehryar Mohri. Theory and algorithms for forecasting time series. arXiv preprint 1003:v8800.0588111 2018.
[29] Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. The Journal of Machine Learning Research, 19(1):1025-1068, 2018
[30] Anastasios Tsiamis and George J Pappas. Finite sample analysis of stochastic system identification. In 2019 JEEE 58th Conference on Decision and Control (CDC), pages 3648-3654. IEEE, 2019.
[31] Tuhin Sarkar, Alexander Rakhlin, and Munther A Dahleh. Finite Time LTI System Identification. J. Mach. Learn. Res., 22:26-1, 2021.
[32] Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems. arXiv preprint arXiv:2003. 11277, 2020.
[33] Holden Lee. Improved rates for identification of partially observed linear dynamical systems. arXiv preprint arXiv:201 10000 2020.
[34] Bruce Lee and Andrew Lamperski. Non aon-ssympto closed-loop system identification using autoregressive processes and hankel model reduction. In 2020 59th IEEE Conference Decision and Control (CDC), pages 3419-3424. IEEE, 2020.
[35] Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029-1038, PMLR, 2018.
[36] Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference Machine Learning, pages 111-119. PMLR, 2019.
[37] Elad Hazan, Sham Kakade, and Karan Singh. The nonstochastic control problem. In Algorithmic Learning Theory, pages 408-421. PMLR, 2020.
12

---

[38] Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. arXiv preprint arXiv:2007.066500 2020.
[39] Udaya Ghai, Holden Lee, Karan Singh, Cyril Zhang, and Yi Zhang. No-regret prediction in marginally stable systems. In Conference Learning Theory, pages 1714-1757. PMLR, 2020.
[40] Paria Rashidinejad, Jiantao Jiao, and Stuart Russell. SLIP: Learning predict in unknown dynamical systems with long-term memory. arXiv preprint arXiv:20/0.05899, 2020.
[41] Mark Kozdoba, Jakub Marecek, Tigran Tchrakian, and Shie Mannor. On-line learning of linear dynamical systems: Exponential forgetting in kalman filters. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4098-4105, 2019.
[42] Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. Advances in Neural Information Processing Systems, 30:6702-6712, 2017.
[43] Anastasios Tsiamis, Nikolai Matni, and George Pappas. Sample complexity of kalman filtering for unknown systems. In Learning for Dynamics and Control, pages 435-444, PMLR, 2020.
[44] Anastasios Tsiamis and George Pappas. Online learning of the kalman filter with logarithmic regret. arXiv preprint arXiv:2002.0514. 2020.
[45] Vitaly Kuznetsov and Mehryar Mohri. Time series prediction and online learning. In Conference on Learning Theory, pages 1190-123. PMLR, 2016.
[46] Anastasios Tsiamis and George Pappas. Linear systems can be hard learn. arXiv preprint arXiv:2104.01 /20, 2021.
[47] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan. Ergodic Mirror Descent, SIAM Journal on Optimization, 1544)1159 2012. doi: 10. 10.1 10836043. URL http::t////oo..ogg/// 1137.011/11/1111111111
[48] Long-Ji Lin. Self-improving reactive agents based on reinforcement learning, planning and teaching. Machine learning, 8(3-4):99-3311 1992.
[49] Alexandre Défossez and Francis Bach. Averaged least-mean-square:: Bias-variance trade-off's and optimal sampling distributions. In Artificial Intelligence and Statistics, pages 205-213. PMLR, 2015.
[50] Fedor Petrov. Non-asympototic version of Gelfand's formula. MathOverflow, 2016. URL
[51] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. 2013.
[52] Roman Vershynin. High--iimensional probabilit:: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[53] Torgny Lindvall. Lectures on the coupling method. Courier Corporation, 2002.
[54] Stanislaw J Szarek. Nets of Grassmann manifold and orthogonal group. In Proceedings of research workshop on Banach space theory (Iowa City, lowa, 1981), volume 169, page 185, 1982.
[55] T Tony Cai, Zongming Ma, Yihong Wu, al. Sparse PCA: Optimal rates and adaptive estimation. The Annals of Statistics, 3166):004-3110, 2013.
13


Reviews:
[{"review_id": "vBtwqegCfTF", "reviewer": "Reviewer_EQ4W", "summary": "The paper proposes an SGD-style algorithm for linear dynamical system identification. The authors claim that the proposed algorithm is the first of its kind to have near-optimal error rates. The key idea behind the algorithm is to run SGD in reverse on streaming segments of the data. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Online (linear) dynamical system identification is an important problem in machine learning. The paper motivates this well and clearly describes the new approach that is designed to tackle previous challenges.\n\nWhat is missing in my opinion is a more thorough comparison (both theoretically and empirically) with other online algorithms that use the Sherman-Morrison-Woodbury (SMW) formula. The authors say that the application of such algorithms is limited. In what way is it really limited? Can you give a side-by-side comparison of the error rates? Also, you say that they do not apply to practically important settings like generalized non-linear dynamical systems. As far as the current paper goes, you do not show that SGD-RER can be applied to this case (you only briefly mention the work of Jain et al. (2021) on this matter). It would have also been nice to include a SMW-style online algorithm in the experiments. \n\nThe other weakness of the proposed algorithm, in my opinion, is the fact that it introduces extra parameters such as the buffer size and gap, which both need be set as a function of the horizon. Sometimes the horizon is not known. Can the new approach easily be adapted to this case?\n\nFinally, in line 243, you claim the rate in the lower bound in Thm 3 matches that of Theorem 1. However, in Thm 1, I see 1/sqrt{T} rate, whereas Thm 3 has a 1/T rate. What am I missing here? \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "qZvgjzOOzq3", "reviewer": "Reviewer_SVQN", "summary": "The authors consider a rather special case of a linear dynamical system, where there is no hidden state and the transition matrix is \"externally stable\" (less than 1 in the operator norm), process noise is sub-gaussian, and the stationary distribution has bounded fourth moment. In this case, they suggest running the SGD \"backwards\" in small buffers, which they call \"reverse experience replay\". This leads to the independence of the observations, and the unbiased nature of the SGD updates. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n\nThis is original, as far as I can tell. The only issue could be the concurrent submission of id 1136 on the use of related algorithms for the identification of non-linear systems (under even stricter assumptions).  \n\nQuality:\n\nThe algorithm is practical and readily implementable. The analysis is quite sophisticated.\n\nClarity:\n\nThe paper is a joy to read.\n\nThe significance:\n\nI imagine that this could become influential. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "WgC-wtpOzAW", "reviewer": "Reviewer_UGDX", "summary": "This paper considers systems identification in vectorized auto-regressive model with stochastic noise. The paper focuses on the practicality of system identification with nearly optimal computation and sample complexity instead of using offline-style methods such as OLS. The authors propose a new SI algorithm based on SGD that uses reverse experience replay to address the challenges due to the inherent correlation between samples. Performance bounds on the accuracy of estimating the transition matrix as well as prediction error are given, both of which nearly matching the lower bounds. Numerical simulations show that SGD-RER is competitive to OLS, which enjoying a smaller time complexity. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality:\n- The idea of reversing replay buffer to mitigate correlation is interesting, novel, and practical.\n- It is unclear to me why the SDG approach in [25] is insufficient. The partial observable LDS considered in [25] is a more general version of the auto-regressive model considered here. Also, another work by Hazan et al. 2017 uses online projected gradient descent, which also handles correlations in LDS via a standard online convex optimization argument. Could you discuss the differences between your work and these papers?\n\nQuality:\n- Strong theoretical guarantees are provided for both estimation and prediction errors. The leading term in error bound is independent of mixing time, which improves over prior work.\n- Recent results on linear system identification and prediction that use OLS completely remove dependency on mixing time. While the leading term in error bound is nearly independent of mixing time, I wonder if it is also possible to remove the dependency of SGD stepsize on mixing time as well. Could you explain the challenges involved in removing this dependency?\n- The experiments section can be improved. It would be interesting to see whether the SGD-RER is robust to the choice of step size. \n\nClarity:\n- The paper is organized well and easy to follow.\n\nSignificance:\n- The paper is well-motivated and increases the practicality of linear system identification.\n\nAdditional references:\n- Hazan, Elad, Karan Singh, and Cyril Zhang. \"Learning linear dynamical systems via spectral filtering.\" Advances in Neural Information Processing Systems 30 (2017): 6702-6712.\n- Tsiamis, Anastasios, and George J. Pappas. \"Finite sample analysis of stochastic system identification.\" 2019 IEEE 58th Conference on Decision and Control (CDC). IEEE, 2019.\n- Rashidiejad, Paria, Jiantao Jiao, and Stuart Russell. \"SLIP: Learning to Predict in Unknown Dynamical Systems with Long-Term Memory.\" 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada. 2020.\n- Lee, Holden. \"Improved rates for identification of partially observed linear dynamical systems.\" arXiv preprint arXiv:2011.10006 (2020).\n- Tsiamis, Anastasios, and George J. Pappas. \"Linear systems can be hard to learn.\" arXiv preprint arXiv:2104.01120 (2021).\n\n-----\nAfter the response:\n\nI thank the authors for responding to my questions. The discussion on the dependency of the bounds on mixing time is interesting and would be good to include it in the paper. I am happy with the answers and stick to my score in favor of accepting this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have discussed the limitations of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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