Long-Context Linear System Identification
Authors: Oğuz Kaan Yüksel
Mathieu Even
Nicolas Flammarion
Venue: ICLR 2025 Poster (2025)
Keywords: autoregressive
linear
statistics
low rank
mispecification
Primary area: learning on time series and dynamical systems
TL;DR: This paper provides sample complexity for long-context linear dynamical systems.

Abstract: This paper addresses the problem of long-context linear system identification, where the state $x_t$ of the system at time $t$ depends linearly on previous states $x_s$ over a fixed context window of length $p$. We establish a sample complexity bound that matches the _i.i.d._ parametric rate, up to logarithmic factors for a broad class of systems, extending previous work that considered only first-order dependencies. Our findings reveal a ``learning-without-mixing'' phenomenon, indicating that learning long-context linear autoregressive models is not hindered by slow mixing properties potentially associated with extended context windows. Additionally, we extend these results to _(i)_ shared low-rank feature representations, where rank-regularized estimators improve rates with respect to dimensionality, and _(ii)_ misspecified context lengths in strictly stable systems, where shorter contexts offer statistical advantages.

Published as a conference paper at ICLR 2025
LONG-CONTEXS LINEAR SYSTEM IDENTIFICATION
Oguz Kaan Yüksel EPFL
Mathieu Even Inria ENS Paris, France
Nicolas Flammarion
HPFL Lausanne, Switzerland
Lausanne, Switzerland
ABSTRACT
This paper addresses the problem of long-context linear system identification, where the state 2t of a dynamical system at time depends lincarly previous states Ia over a fixed context window of length p. We establish a sample com- plexity bound that matches the i.i.d. parametric rate up to logarithmic factors for broad class of systems, extending previous works that considered only first-order dependencies. Our findings reveal a "learning- without miioouuttiiing"" phenomenon, in- dicating that learning long-context linear autoregressive models is not hindered by slow mixing properties potentially associated with extended context windows. Additionally, we extend these results to (i) shared low-rank representations, where rank-regularized estimators improve rates with respect dimensionality, and (ii) misspecified context lengths in strictly stable systems, where shorter contexts offer statistical advantages.
INTRODUCTION
System identification, which consists of estimating the parameters of dynamical system from ob- servations of its trajectories, is fundamental problem in many fields such as econometrics, robotics, aeronautics, mechanical engineering, or reinforcement learning (Ljung 1998, Gupta et al. [976] Moerland et al.] (2023). Recent theoretical advances focused on linear system identification, where observations are the form:
It = A +
for f > with initialization zo E Rd. noise & E Rd and design matrix A' E pdxdd Linear system identification (Simpkins) 1999) has been thoroughly studied, with recent interest in sharp non-asymptotic rates (Simchowitz et al. 2018 Sarkar & Rakhlin 2019 Faradonbeh et al. 2018 Jedra & Proutière 2019). The existing analyses, however, focus solely on order-1 time dependency, in which the law of 24 only depends the previous state r4-1- For order-p time dependencies, the literature on non-asymptotic rates becomes surprisingly scarce, as existing techniques do not extend p 1.
We study this more general setting, where the state I2 depends on previous states I, for 8 a context window of length p
i.c. i.e.
Apri Ee.
for & >> p. the initialization .o. Pp-1 E Rd, noise & E RRd and design matrices Ai...., A E Rdxd This classical pth-order vector autoregression model (Box et al. 20155) Brockwell & Davis, 1991 Hamilton| (020) is termed long-context linear autoregressive model. The term linear refers to the (noisy) linear relationship between iterates and long-context refers to the context length p. Recent advances in autoregressive models and architectures such as transformers (Vaswani et al. 2017 Dosovitskiy et al. 2021 El-Nouby al. 2024) highlight the importance of long-context and its impact on learning. Developing a theoretical understanding of long- long-context linear autoregressive models is necessary first step toward tackling these more complex architectures.
Motivated by empirical evidence that high figh--imensional data may share some nower-dimensionss representation (Bengio et al. 2013 Hospedales et al. 2022), several works additionally studied the

---

Published as a conference paper at ICLR 2025
problem of learning matrices A under the assumption that they are of low-rank (Alquier et al. 2020 Basu et al.) 2019), for order-1 autoregressive models. In the long-context setting. this prob- lem further motivated by the fact that if there exists lower- dimessiinni representation of the autoregressive process, this translates into shared kernels for the matrices A
Finally, key challenge in long-context autoregressive models is misspecification: the system might have an unknown context window p as Equation (2). p may be arbitrarily large and unknown by the statistician. She may then specify context length p' that can be much smaller, thus yielding the following two fundamental questions: can useful structure still be learned under misspecified context lengths? And what advantages, if any, arise from model misspecification?
Our contributions in long-conten linear systems identification are then threefold.
(i) We derive statistical rates on the recovery of matrices Aj in terms of Frobenius norm, which depends on the number of trajectories N and their length T, on the dimension d and the context length p. These rates reveal "learning- without- mixiinngttmiin""" phenomenon as they do not have a deflation in effective sample size due to the mixing time of the autoregressive process. This first contribution an attempt to fill the gap in linear system identification for long context lengths.
(ii) We study statistical guarantees for learning the matrices Ag assuming that they are all of rank at most r < d. We prove that the statistical rate reduces, and that rank-regularized estimators adapt to the low-rank structure.
(iii) We study a scenario under which the model is misspecified. Fitting a linear model with context length p' < p instead of p. we show that the first p' matrices are still learned. More importantly, the sample complexity of learning these matrices depends only on the misspecified context length, indicating that misspecification may benefit the model statistically, not just computationally.
Finally, we confirm these statistical rates through experiments that verify the scaling laws predicted by problem parameters. Due to space constraints, these experiments are provided in Section
2 RELATED WORKS
In multivariate linear regression, one observes {(x,, ye) from the model y; = A' + &,, where matrix A dgd and the sequences of noise & and inputs z; are i.i.d. The number of samples N needs to scale at least as d² for a good estimation of A with ordinary least squares estimator (Hsu et al. 2012 Wainwright 2019) in Frobenius norm ||AA - ÅIE < 1. However, in many domains, data is sequential, violating the i.i.d. assumption. such domains, classical non-i.i.d. formulations, such as vector autoregressive models or discrete-time linear dynamical systems (LDS), as seen in Equation ( are often employed. Most works used to deal with the non-i.i.d.
of the data through mixing time arguments that fall short when the spectral radius of AA* reaches 1, leading to
rates of the form || - A (dd (n(11 p))) or || 1 Odd((n( p))) for some spectral quantity 1 - related to the mixing time of the process. These rates apply to the OLS estimator (Faradonbeh al. 2018) and online settings (Hardt et al. 2018 Even 2023) alike.
Simchowitz et al. (2018); Sarkar & Rakhlin (2019) have developed excitation-basel arguments to leverage mixxngg-iime independent statistical bounds for the OLS estimator, while Hazan et al. (017)) Jain et al. (2021) respectively used spectral filtering and reverse experience replay in the online setting to obtain such bounds. The estimation of low-rank features has been studied by Basu et al. (2019); Alquier et al. (2020) via nuclear norm regularization. Finally, learning parameters of dynamical systems from N trajectories of length T has previously been considered by Tu et al. (024)) in a more general framework than Equation I
Layers of complexity can be added to the LDS described in Equation [1. Mania al. 2022 : Foster et al. 22020) considered non-linear dynamics, that write respectively as T++1 A (''((z, U4) + & and 1++11 (xx) + & where the former A is to be estimated and @ is a known non-linearity, while in the latter f* is to be estimated. Kostic et al. (2022) recently provided general framework using Koopman operators, to estimate the parameters of some general Markov chain. Giraud et al. 2015) considered varyingg systems, with arbitrary context lengths, while Bacchiocchi et al. 2024) studied autoregressive bandits. Ziemann & Tu (2022) provided a framework for learning non-parametric dynamical systems with "little mixing": their rates are not hindered by slow
2

---

Published as a conference paper at ICLR 2025
mixing after burn-in time (that may itself depend mixing properties). We refer the reader to Tsiamis et al. (2023) for a survey on recent advances on non-asymptotic system identification of LDS such as in Equation (T). Surprisingly. there does not seem to be much known about long- context LDS in Equation the counterparts of LDS in Equation with a context window p > 1.
PROBLEM SETTING
For matrix M E xdd with singular values 01....; min (d we denote its squared Frobenius norm ||M [ Eú.,) My = E., operator norm as ||M llp = maxe |oe), and nuclear norm ||M]] Ee oel- La and O2 denotes the identity and the null d d matrices, respectively. A (AI.....Ap Ap) denotes a rectangular matrix of size d x pd where each A, is d x d block.
3.1 DATA GENERATION PROCESS
Let d, p N" be the dimension of the state space and the context length, respectively. Consider the following linear autoregressive process:
Vt 00 It
A &
where 2, 0 for any < 0 and the noise & is independent of the x... E. for < t. This is particular instance of the general linear autoregressive model in Equation (2) with initial conditions Ty..... 2p-1 set to 0 and the independent noise structure. We assume sub- Gaussaanii noise:
Assumption 3.1. For all the noise & is centered and isotropic:
[[g 0, [ = = o²Ia,
and each coordinate of & is independent end 2 See--suu-aassss Gab--aassiin (Wainwright 2019 Chapter 2) for some 2 1:
Vi [d] (ll & =c00² where | = = A h-
1/2B ||a]
ki1
Let AR(A* )²) denote the law of the sequence defined in Equation 3 (Ai....,AA) for brevity. Given N independent sequences of length T pt
where A denotes
o (m) nn [M], E } where (z(")) (xf"))e lid. AR(A",
{
the goal of long-context linear system identification is to estimate the matrices A k lp).
Lastly, we assume a condition on the design matrices Ag. k E [p) that amounts to an operator norm bound, First, we define the following linear operators for any matrix E Rddxpd
Definition 3.2. Let MA TáxTd be the block-matrix with block entries of size d:
M M(aa) Ai-jo for all I<j<i<itpE$
and M Oa, otherwise.
Definition 3.3. Let T,, E TRxxxa be the block-matrix with block entries of size d d:
max 1.p)
(1.1) Ia and -!
Σ
ALL. A I<iET,
(14) L (i-++1.) for all IsiEjEP, and (5d) O.s otherwise..
MA executes predictions from the given data with A and I., generates the data from the noise. That is, letting (MA).. (L.).. Rd x R Idd be the 4th block-row of M and L., respectively, we have:
T (n)
(MA).
(n)
(Twe)e
:
(n) x
with x, for 0.
(n)
TT
ST
3

---

Published as a conference paper at ICLR 2025
Therefore, the operator norm of MA is measure of the worst-case growth of the predictions. Moreover, MA. is linked to the data-genen tata-generating operator L,:
= - MA
L. (ITa - MA-) Ira + Σ (Mai)*
We assume the following conditions on the design matrices:
Assumption 3,4. There exists a known constant D 3 such that ||MA llop & D.
Theorem 3.4 is not restrictive D is arbitrary and only needs be upper bound M llp
However, the knowledge of D is necessary, as it is used to confine the estimator in Section 3.2
As the operator MA- is derived object over the full trajectory, it is important to relate Theorem 3.4 to conditions on the design matrices At. In Theorem 3.5 below, we provide two different assump- tions on the design matrices that ensure the boundedness of the operator norm of M A with the same constant. Both conditions imply Theorem 3.4
Proposition 3.5. Theorem 3.4 holds if one of the following holds:
i
llop < D,
(ii)
1|
& vP
There is no direct assumption on L.; yet, our results depend on number of L., which is related to H2 that appears in Siimchowizz et al. (2018); /aarar & Rakhlin 2019). x related to the system stability, as explained Section 5
of k, the condition
Definition 3.6. Let R. be the condition number of L,, iee, K
m (L.)
3.2 CONSTRAINED LEAST SQUARES
natural estimator is the Ordinary Least Square (OLS), defined as any minimizer of the square loss:
ÅOLS argmin, A C(A), where ((A)
A (n)
(4)
NT
The OLS estimator has been considered in previous works (Simchowitz al. 2018
Alquier al.,
2020 Faradonbeh et al.] 2018 Sarkar & Rakhlin 2019).
albeit in the
= case.
Most of these
works provide estimation rates on AA-A"1 lolpop or LA
A- for marginally stable systems, i.c..
under the assumption that ((A) & (Alquier et al. 2020
Simchowitz al. 2018 Basu al. 2019)
and in the general case (Sarkar & Rakhlin 2019).
Instead of directly considering the OLS estimator, we consider the empirical minimizer of the square loss under restricted set of matrices A that have bounded operator norm:
Å argmin AA(AA...AA,)) {C(A) Mallop & D).
(5)
Note that the set
A(D) = (A (A Ap) ||Mallop < <D)
is bounded, closed and convex. Hence, the empirical minimizer of the square loss over A(D) can be computed with projected gradient descent (Duchi et al., 2008) the Frank-Wolfe algorithm (Jaggi 2013) as done for El constrained optimization. To avoid projecting onto the set A(D), following is possible restrict A(D) further into
Theorem 3.5
A(DY - A
Σ
1
< D2 {D) and A(D)" = A |||||
D VT
in order to ensure condition directly design matrices. Then, the empirical minimizer of the square loss over A(DY or A(D)" can again be computed via projected gradient descent or the Frank-Wolfs algorithm, with simplified projection steps.
Lastly, we briefly remark that the diameter constraint Equation 5 can be removed, i.e., A(D) replaced by A(oo), under additional assumption NT. This is explained in detail in Section
4

---

Published as a conference paper at ICLR 2025
3.3
LOW-RANK ASSUMPTION
A common assumption in multi-task and meta-learning is that high-dimensional data often shares representation in a smaller space (Bengio al. 2013 Tripuraneni al. 202T, Hospedales al.j
2022 Boursier et al.) 2022] Collins et al.] 2022, Yüksel et al.) (222) The following low-rank as-
sumptions are crucial, as they significantly improve the statistical complexity of the problem.
Assumption 3.7. For all [p], rank(AA) r.
Assumption 3.8. There exists an orthonormal matrix P E Rrxd and matrices Bi...., such that A = B P* for all k E [pp].
,..,,,, By E RRdx
The factorization A = Q* another subcase of Theorem 3.7 but is not considered as it leads to iterates that directly lie in the subspace spanned by Q* and hence Q" can be learned by treating iterates x.(") as independent. In order to benefit from the low-rank structure, we consider the following regularized estimator:
Note that Theorem 3.8 an instance of Theorem 3.7
Å E ArA [(A), where A,(D) = {A A(D) Ak [p], rank(Ap) < <r). (6)
3.4 MISSPECIFICATION
The context length of the generative autoregressive process might be unbounded, too large for an efficient estimation, or apriori unknown. In any case, practitioners still have to set context length E No for the estimator, which might differ from the true p. In this scenario, we need an additional boundedness assumption that relates the first p' matrices of the ground truth.
Assumption 3.9. There exists a constant D' such that
( (Ma- -
MM---Mi,ph Mar, L Ip & D', where Ai.y = .A....., Ay. 0a 0a)
Instead of the estimator defined in Equation (6. we consider the following misspecified estimator:
Å E argmin PegminAA4,,p// (D) C(A), where Arg (D) = (A E (,(D) Vvp < ck<p p. 0.} (7)
Theorem 3.9 is a strong assumption as it requires that L,, is well-behaved regardless of the sequence length T. Consequently, the misspecification results to smaller class of systems that still includes strictly stable systems as discussed in Section
stringent than other results and apply
4 LONG-CONTEXT LINEAR SYSTEM IDENTIFICATION
In this section, we present statistical rates for the recovery of the design matrices in terms of Frobe- nius norm. Since the matrices A lie dd the number of variables pd?. In the i.i.d. setting, the rates of the form || A = ((NT) are expected. The following theorem extends this rate for long-cor cong-context linear dynamical system identification:
Theorem 4.1. Let Theorems
3. and 3.4 hold. Then, for any 0 < K < e there exists constant
C()) such that the estimator A in Equation
( verifies with probability 6:
A A 1
C())D2
N(T -)) p.
pd
The constant (8)) depends mildly on the Ga--Gaaaiiantty constant as described in Section C.5 and sketch of proof is provided in Section A The rate is numerically verified in Figure iin in Section Theorem 4. exhibits several interesting features.
First, it shows that despite the temporal dependencies in the data, learning still occurs pace reminiscent of the i.idd setting, with a logarithmic term adjustment. This implies that the number of samples required to leam the system is approximately the same in the i.i.d. setting, except for the logarithmic factor. Therefore, even though the data sequential and only i.i.d. at the sequence level, the number of iterates N(T represents the effective data size.
5

---

Published as a conference paper at ICLR 2025
Second, the rate in Equation exhibits linear dependency the context length p instead of quadratic dependency. This is only due to the number of parameters to be estimated, which is pdf instead of d' and not a deflation in T by a factor of p. which implies the context length does not affect the effective sample size. The additive factor T - is due to the fact that first iterates do not depend on the full context length, and thus are not as informative as the later iterates. More detailed discussions of Theorem 4.1 in comparison with previous work, can be found in Section 5
Low-rank setting. Next, extend the results to the low-rank setting:
Theorem 4.2. Let Theorems 3.1 3.4 and 3.7 hold. Then, for any < e there exists constant (() such that the estimator A in Equation (6 verifies with probability 1 5:
prd
Å A')
< C(
N(T -p) polylog(n, p,,
The improved statistical rate depends on rd instead of d², Note, however, that this estimator cannot be computed in polynomial time, since the underlying optimization problem involves a non-convex constraint on the rank of all Ag. Several heuristics exist to approximate this estimator. One approach is the Burer-Monteiro factorization (Burer & Monteiro 2003 2004), which involves parameterizing A₁ as A₁ = BgCr with Bg E R and C& E ıि This method relaxes the constraint to a convex set but results in non-convex function. Another approach is wurd-thresholding algorithms, which use projected (stochastic) gradient descent on the non-convex constraint set (Blumensath Davies 2009 Foucart & Subramanian 2019)..
Perhaps the most intuitive approach is to use nuclear norm regularization, which a convex relax- ation of the rank constraint:
Å E argmin (Ax(A) A E A(D)), where (x(A) = L(A) ||| group
and || | group Ei_ || the group-nuclear norm. We leave the analysis of the nuclear
norm estimator for future work.
While the low-rank estimator cannot be computed easily, substituting the constraint Vk: rankkakkkaaa (As) S with rank(A) & r' enables a closed-form solution for the optimization problem (Bunea et al. 2011). However, the latter constraint effectively includes the former only when r' pr, which would lead to suboptimal dependencies the context length. These constraints are equivalent only all Aş matrices project onto the same space: i.c., Aş- = Q for some Q dd and Bg E BR
Misspecification. Lastly, we study linear long-context autoregressive prediction models under misspecified context lengths and show that partial learning still occurs for misspecified models: Theorem 4.3. Let Theorems
3.7 and 3.9 hold. Then, for any 0 < 5 < e-1, there exists a constant C()) such that the estimator A in Equation 7 verifies with probability 1 ō:
3./
3.4
polylog(H, p', N,T). A - 12 1| < CD))DP(D' + 1)² N(T p)
p'dr
For d, we recover Theorem 4.1 (full-rank setting) for misspecified context windows. The main improvement in that case of Theorem 4.3 over Theorem | is the dependency on p' instead of p. In practice, p can be much larger than p' and even on the order of T. In such a setting, learning all matrices Až becomes impossible if N is not large enough and one does not take advantage of the length of the sequences. One can instead misspecify the student with a context length of p' < such that NT > p'd so that the first p' matrices still learned.
Lastly, we briefly remark that Theorem 4.1 provides a rate for the case where p < p'. The latter case can be seen under well-specified setting by rewriting the ground truth model as A" = (A)...., A Od,..., Oa) where the last -p indices are padded with null matrices. Learning in such a case is then answered by Theorem 4.1 with a worsened rate that depends on p'.
DISCUSSION
We now discuss the rates obtained in Section and compare them with previous results obtained for linear dynamical systems. In particular, we comment the "learning hoaming-without without- mixinnt""iixin"" phenomenon, introduced by (Simchowitz et al. (2018) for the first-order linear dynamical systems.

---

Published as a conference paper at ICLR 2025
Adaptation of first-order techniques (p 1) to the long-context setting. Here, we explain why techniques developed in the = setting. in particular those of (Simchowitz et al. 2018 Sarkar & Rakhlin 2019). do not work for the p > 1 setting and why, even if adapted, they would fail to achieve the desired sharp dependency on p-
Observe that the multi-step dynamics can be cast 1-step dynamic using block companion ma- (n).T
trices. Let x/") (x) (a("). " E RTd =(") (O..... 0, ()) TTT E Rdd and let
A E Redxed be the companion matrix associated to A
0a
0a
A
0gd
0a
la
A
A Ap11
A5
- reducing the problem to the p case by increasing the dimension from d to pd. First, brute-force adapting previous results to this case (e.g. Basu et al., 2019 Simchowitz et al. 2018 Sarkar & Rakhlin 2019) is not possible since these works assume that the noise covariance of the additive noise added at each step (E,") here) is the identity matrix, or at least is positive definite. In our case, the noise covariance is the pd pd block-diagonal matrix, with p - 1 blocks equal to O2 and the last one to La. The covariance matrix is thus non-invertible, preventing the use of previous works.
We have the relation X (n)
Ax
In addition, arguments based on system excitation (e.g. Basu et al. 2019; Simchowitz et al. 2018) are bound incur an additional dependence on p. on top of the factors expected due to the dimen- sionality of the problem. In particular, as seen in the small-ball martingales argument by SSicchowiz al. (2018. Section 2.3), evaluating quantities like II(A xx I|a for the (ki, v. 4)-block mar- tingale small-ball assumption requires k > p as p represents the minimum number of steps for noise to propagate in every direction. Consequently, these analyses lead to a suboptimal p dependency.
Moreover, adapting the techniques developed in the p 1 setting (Sarkar & Rakhlin (019) which relies on explicit factorization of the OLS estimator is challenging. In the p >> I case, the higher- order dynamics complicate the factorization, and the data matrix takes a Toeplitz form, which is more difficult to handle.
We be- and discussing the factors that influence the mixing time Tanix- We then introduce the concept of "learning-witheee without without-mixing" as exemplified by [Simehowitz et al. (2118) and show that our bounds exhibit similar properties.
We explain why our rates exhibit gin by defining "Jeaming-witthmmxiin"
Bhaaning-without-miin
Let Tmix be the mixing time of the Markov chain (x((0) ):z0- In the i.i.d. setting (for which Tmix 1), the OLS estimator obtains the optimal rate AOTs - A 1 = O(pd² /NT), since pd? is the dimension of the inputs. With non-i..d. but Markovian data, naive strategy would be to emulate i..dd-ness and take only a sample every Tmix steps of the trajectory to compute the OLS estimator, thus having data that are approximately i.idd while dividing the number of samples by Tmix. This naive fearming-with wiith-mixing" estimator would yield || the mixing time appears as cost of non-i.i. -ness and Ô hides the logarithmic terms in problem parameters d, N.
A I| O /NT). where
In our case, two components contribute to the mixing time, Tmix- The first component is related to the stability or the excitability of the system and scales as 1/(1 - p), where p || llop < 1. When p < 1, this component has no impact, while p tends to 1, the system less stable and the Markov chain mixes more slowly. The second component is directly related to the context length
of the process. Regardless of the factor 1/(1 - p) above, the mixing time of our Markov chain
larger than p. since noise is added only in the last block in the recursion x- (n) A x*x(") + = ++1
starting from a given state, p iterations at least are needed to eventually forget this given state. The naive learning-with-miinegg with-mixing benchmark rate is thus À A & max (1/ (1 - p) .)) pd? /NT..
In contrast, a rate of convergence that exhibits "learning-withee www.wwwwtwwwheeeeeeee is a rate of the form A A I| & Cpd? /NT where C & Tmixx Such rate means that the matrix A is learned without

---

Published as a conference paper at ICLR 2025
paying the cost of non-i.i.d.ness. For instance, in the p case, the rate of (Sinchowizz et al. 2018) does not worsen as p tends to l-in fact, - actually improves their rates.
The bound presented in Theorem 4.1 takes the form (LD"pd/(N[C) - p))). Importantly the dependencies the underlying Markov chain are only through D and In which do not have direct dependency on the mixing time. The dependency on is merely an operator norm upper bound and does not diverge the mixing time grows to Similarly, In is logarithmic in T for systems of interest, as we discuss below.
System stability and We now explain the behavior of x defined in Theorem 3.6 Theorem C.11 we have that miin (L.) 3 D4T and, thus, it is sufficient to upper bound
First, by
<(T) = sup ||4 (.j
(+.f)
(6.5)
lop 2 sup
IE
|L,lle
- VdT
(10)
Vd
VdT
JJE
to control K. Equation 10
implies that if the noise at step i contributes to step j. as measured by
T. (1-1) polynomial rate in (j i), then grows most polynomially in T. For such K, the
resulting dependency on of order and mild. Instead, it exponential (j - i). then In grows linearly in T' and the dependency on cancels out in the rate.
We use the quantity C(T) to define strictly stable, marginally stable and explosive systems: Definition 5.1. An LDS as defined in Equation 3 called
strictly stable if
p < 1, C(T) = O(p²) for some
marginally stable if
k E N, explosive if C(T) O(p²) for some p> 1.
S(T) = O(Th)
for some
Theorem 5.1 similar the notions of strictly stable. marginally stable and explosive systems
considered in Simchowitz et al. 2018 be the spectral radius of 1" and
Sarkar & Rakhlin 2019) for 11 Let p(A*) = (Aa be the Jordan normal form of A Then,
VAV
||L
( lop = (AT)²~ 1lop = ||V -iii-v--lll llop < lop A || Vo
Note that [|Vllop and ||V llop are constants. For upper bounding || llop- consider the Jordan blocks (A&) of A, associated with the eigenvalues d of A', Then, ||A x sup ||
llo and
max (j (--.n-1)
(Aah +NN 1lop
Σ
N
ji-1
Nm
m=0
op
(j-in-13
E
P(A
where n is the block size for the Jordan block Ag. Note here that n does not scale with T.
In particular, for strictly stable systems Simchowitz et al. (2018): Sarkar & Rakhlin 2019 with < 1, <(T) = =.p"). For marginally stable systems of Sarkar & Rakhlin (019 with p < + 7 with some constant > 0. p(A < e" and ((T) OTT)) for some fixed i that depends on the largest Jordan block of A*. For explosive systems of Sarkar Rakhlin (2019) with p > 1, C(T) Opp)). Thus, Theorem 5.1 provides a general categorization of the systems based on the growth of ((T) in p > case. Furthermore, our analysis yields sharp rates for strictly stable and marginally stable systems previously considered only in the p setting.
Search space diameter D. Our analysis is based on the assumption that the diameter of search space is bounded and, hence, not directly applicable to the OLS estimator in Equation (4) However, Theorem CC.7 in Section [.. extends the results of Theorems [. to 4.3 to minimizers without constraint the diameter of the search space. This extension does not change the rates
but requires the additional assumption that NT 2(p dr) In the case of Theorem 4.1 this
We use the convention that d, for Theorem 4.1
8

---

Published as a conference paper at ICLR 2025
corresponds to result for the OLS estimator, but necessitating number of samples quadratic in context length. Below, we comment on why the diameter restrictions is required when NT < dr
As mentioned earlier in comparison with (Simchowitz et al. 2018 Sarkar & Rakhlin 2019). the simple OLS factorization in the = case does not generalize to the p > I and the data matrix has Toeplitz structure that is more difficult to control. In order deal with these issues, explained in the sketch of proof in Section A we rely on techniques from empirical process theory. These techniques are applied
quantify the probability of the event in Equation (33), which hold for any empirical risk minimizer of the square loss. This leads us to the study of the concentration of the martingales defined in Equation (15) around their predictable variation, which key step in our analysis. A uniform concentration is possible only if there is a uniform lower bound on the variations of the martingales, which can be achieved using set of well-behaved matrices || MA- ||ll||//////// MA - M llp- In order to translate these conditions on the design matrices without additional dimensional dependencies, we introduce the operator norm constraint.
Lastly, it is possible to extend our analysis to unconstrained OLS by establishing a general coarse upper bound on the operator norm || [MAllop < K. This allows us to consider uniform lower bounds to matrices A with ||M < K, which lead to a rate for the OLS estimator in a similar manner.
Upper bound on D'. The misspecification result Theorem 4.3 requires the additional assump- tion given in Theorem 3.9 In Theorem C.6 we show that good upper bound D' is possible when D < 1, i.e., the system is strictly stable, by using the bound |.Lllopp < 1/(1 - D). How- ever, misspecification results not, priori, applicable marginally stable systems, which limits the practical applicability of our results. We leave the investigation of misspecification results for marginally stable systems for future work.
Practical implications. The rates obtained in Section 4 holds true if the empirical risk minimizer Å is replaced by any estimate Á that verifies
((Ā) < C(A").
(11)
The training error for the ground truth A concentrates around add with rate of OLI/VNT), which is identical to that in the i.i.d. setting. Hence, any algorithm that optimizes the training error below the threshold add achieve the rates in Section 4
Moreover, in Section D we show that the rates extend to approximate minimizers, i.e., any estimate À that verifies
p' dr NT
((A) ((Ā) + Cer, where Cer Ô
(12)
where étr is the surplus training eтror of the estimate À over the empirical risk minimizer Å.
Estimates satisfying equations [1] 12) are computationally tractable in practice. This implies that practitioners can determine the required number of samples, or N and T, for estimating the system parameters up a fixed precision by using the rates in Section
CONCLUSION
In this work, extend non-asymptotic linear system identification theory and derive upper bounds on the sample complexity of learning long-comte context linear autoregressive models. Our bounds im- prove upon the existing arguments specific first-order systems by employing a uniform concen- tration argument over prediction differences. We further establish improved statistical rates when learning under low-rank assumption. Finally, we show that even with long or unbounded gen- erative contexts, misspecification still allows the estimation of the matrices with reduced sample complexity and for stable systems.
While this work makes significant progress for non-asymptotic linear system identification theory, several technical questions remain open for further investigation. Can the OLS operator norm be coarsely controlled to derive rates for unconstrained OLS in the NT 2(pdr) regime? Is it possible to find efficient algorithms that would benefit from low-rank assumptions? Lastly, can misspecification be beneficial for marginally stable systems?

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This project was supported by the Swiss National Science Foundation (grant number 212111). This work was partially funded by an unrestricted gift from Google.
REFERENCES
Pierre Alquier, Karine Bertin, Paul Doukhan, and Rémy Garnier. High-dimensional VAR with low-rank transition. Statistics and Computing, 30(4):1139-1153: March 2020. doi: 10.1007/
sl1222-20-099929- UtL/ttts:///bb.or////00
Francesco Bacchiocchi, Gianmarco Genalti, Davide Maran, Marco Mussi, Marcello Restelli, Nicola Gatti, and Alberto Maria Metelli. Autoregressive bandits. In Sanjoy Dasgupta, Stephan Mandt, and Yingzhen Li (eds.), International Conference on Artificial Intelligence and Statistics, 2-4 May 2024, Palau de Congressos, Valencia, Spain, volume 238 of Proceedings of Machine Learning Research, pp. 937-945. PMLR, 2024. htRp::tpp:t http:::::/pprceeeee ngs mlr press/v238/ bacchiocchi244 html
Sumanta Basu, Xianqi Li, and George Michailidis. Low rank and structured modeling of high- dimensional vector autoregressions. IEEE Trans. Signal Process. 6775):200--122,, 2019, doi: 02.1009/TSP.2018288887778 / 20cp://0..00077S8221188888881
Yoshua Bengio, Aaron Courville, and Pascal Vincent. Representation learning: A review and new perspectives. IEEE Trans. Pattern Anal. Mach. Intell., 35(8):1798-1828, aug 2013. ISSN 0162- 8828. doi: 10.1 109/TPAMM..013.500.. URL /tttpp:://do...rg/11..111 50
2013.
Thomas Blumensath and Mike E. Davies. Iterative hard thresholding for compressed sensing. Ap- plied and Computational Harmonic Analysis, 27(3):265-22 274, 2009. ISSN 1063-5203. doi:
http:///oii.org/100 10. act. 04 04.002. 002. URL https: www..w www.eciieeeee rect. com/
Etienne Boursier, Mikhail Konobeev, and Nicolas Flammarion. Trace norm regularization for multi- task learning with scarce data. In Po-Ling Loh and Maxim Raginsky (eds.), Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learn- ing Research, pp. 1303-1327. PMLR, 2022. URL v178 1117//burra http:/buursrree20 html
.ww.mmmrpp...... prls.p
George EP Box, Gwilym M Jenkins, Gregory C Reinsel, and Greta M Ljung, Time Series Analysis: Forecasting and Control. John Wiley & Sons, 2015.
Peter J Brockwell and Richard A Davis. Time Series: Theory and Methods. Springer Science & Business Media, 1991.
Florentina Bunea, Yiyuan She, and Marten H. Wegkamp. Optimal selection of reduced rank esti-
mators of high-dimensional matrices. The Annals of Statistics, 1309, 2011. ISSN 00905364, 21688966. httpttp: http:tpp//ww...tttoror////////// wttpo//.rr/taaaaeee//5333/33
Samuel Burer and Renato D.C. Monteiro. A nonlinear programming algorithm for solving semidef- inite programs via low-rank factorization. Mathematicall Programming, 95(2):3293357, February 2003. ISSN 1436-4646. doi: 10. 10.10077/10107-000-003333 /tt.ttpp//dd....iiiioooo
htLtttt://dx http::::///xx.d...o/////
1007/s10107-000 0352-8 8
Samuel Burer and Renato D.C. Monteiro. Local minima and convergence in low-rank semidef- inite programming. Mathematical Programming. 103(3):427444, December 2004. ISSN
1436-4646. doi: 00007//10107-004-055644 910107-004-0564-1
URL http::/dx.ddi.... org.lorrg1000 10.
Emmanuel J. Candès and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57
(4):2342-28) 22599929999,.0. 201
doi: 10.1 109/TTT22011.1111 1..111771.
10

---

Published as a conference paper at ICLR 2025
Liam Collins, Aryan Mokhtari, Sewoong Oh, and Sanjay Shakkottai. MAML and ANIL prov- ably learn representations. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepes- vari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Confer- ence on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp- 4238 4310. PMLR, 17-23 Jul 2022. URL https:/tt://tttt https:://proceedii ngs. ml. wtt.ing........smr.... www..prees/vvl2. collins22a.hth
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image is worth 16x 16 words: Transformers for image recognition at scale. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
http:://ppppeeeviieee net/ forum?
id-YicbE dNTTy
John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. Efficient projections onto the 11-ball for learning in high dimensions. In Proceedings of the 25th International Conference on Machine Learning, ICML '08, pp. 272-279, New York, NY, USA, 2008. Association for Computing Machinery. ISBN 9781605582054, doi: 10.1145/1390156.1 13919901116111999111 URL https:
7/doi. 10. 111111191115.... 110.5.5..331111 1390191
Kacha Dzhaparidze and JH Van Zanten. On bemstein-type inequalities for martingales. Stochastic processes and their applications, 93(1):109-117, 2000.
Alaaeldin El-Nouby, Michal Klein, Shuangfei Zhai, Miguel Ángel Bautista, Vaishaal Shankar, Alexander T. Toshev, Joshua M. Susskind, and Armand Joulin. Scalable pre-training of large autoregressive image models. In Forty-first International Conference on Machine Learning, ICMI. 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL. https:// openreview http:/iwwwwwwweeeeeeeeeeeeeeeeee forett/oormmiim wtt.:uummicccc90--0e0
Mathieu Even. Stochastic gradient descent under markovian sampling schemes. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (eds.), International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 9412-9439. PMLR, 2023. httt::
ngs. ml prwss
/ v2.0 even2.33 html
Mohamad Kazem Shirani Faradonbeh, Ambuj Tewari, and George Michailidis. Finite time ideni-- fication in unstable linear systems. Autom,, 96:342 353, 2018. doi: AUTOOATITTOAIICCA. 8018,07.008 http::ttts////ct http://o.o......../oo/....
aut auttmmaiiaa 2018 07.008
Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Ben- jamin Recht, Claire Tomlin, and Melanie Zeilinger (eds.), Proceedings of the 2nd Conference on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pp. 851- PMLR, 10-11 Jun 2020. URL https: http:://pooceedeeeee mlr press/v120/ Foster20a, html
Simon Foucart and Srinivas Subramanian. Iterative hard thresholding for low-rank recovery from rank-one projections. Linear Algebra and its Applications, 572:1 2019, ISSN 0024-3795. doi: https://doi.org/10.. 1010/////.00001/..../. 2019........000....0.. URL https: /tap::://www... www.wseeiinccddr....... com/ http:///nnn/rrrtceee////////2///
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp- 100-118, 1975.
Christophe Giraud, François Roueff, and Andres Sanchez-Perez. Aggregation of predictors for nonstationary sub-linear processes and online adaptive forecasting of time varying autoregressive processes. The Annals of Statistics, 43(6):2412-243 2015. ISSN 00905364. URL hhtt:
//www. jstor .aw.r.rrg/seee wwwggg/taaleeee htt.ol////338888
N. K. Gupta, R. K. Mehra, and W. E. Hall. Application of optimal input synthesis to aircraft param- eter identification. Journal of Dynamic Systems, Measurement, and Control, 9892):339-145. June 1976. ISSN 1528-9028. doi: 10.1115/1.3427000 URL http:/ /x dei wwwpoo.oo.........o T.3427000
11

---

Published as a conference paper at ICLR 2025
James D Hamilton. Time Series Analysis. Princeton University Press, 2020.
D. L. Hanson and F. T. Wright. A bound on tail probabilities for quadratic forms in independent ran- dom variables. The Annals of Mathematical Statistics, 12(9):107--1088 1971. ISSN 00034851. URL http::/tp///
jstor. wtt/ httg//salle//// 2240253
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical sys- tems. J. Mach. Learn. Res., 19:29:1-29:44, 2018. URL https::/ jmlr org/papers/
v19/16-463 html
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchanl Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Ar- ray programming with NumPy. Nature, 585(7825)357-362, September 2020. doi: 10. 1038/ 020 2649-2
s41 141186-020-2649-2. URL
Elad Hazan, Karan Singh, and Cyril Zhang. Learning linear dynamical systems via spectral filtering. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus. S. V. N. Vishwanathan, and Roman Garnett (eds.). Advances in Neural Information Processing Systems 30: Annual Conference on Neural Infor- mation Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp- 6702 6712, 2017. 16 165a59f7cf 3b5cc4 35553997703044449449333333333333 39333399666366666 Abstrattt html
URL atttps://pzoceeeinggs new.oeeeedings...uis............ http:///www..a......ooooo///////
T. Hospedales, A. Antoniou, P. Micaelli, and A. Storkey. Meta-learning in neural networks: A survey. IEEE Transactions on Pattern Analysis; Machine Intelligence, 44(09):5149-516) sep 2022. ISSN 1939-3539. doi: 10. 11A.1//TAAM22221.007999900
Daniel Hsu, Sham M. Kakade, and Tong Zhang. Random design analysis of ridge regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.). Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp- 9.1-9.24, Edinburgh, Scotland, 25-27 Jun 2012. PMLR. URL https: /ttp::://rrcceeee ngs.
mlr. wwtppperr/sssseee html
Martin Jaggi. Revisiting Wolfe: Projection-free free sparse convex optimization. In Sanjoy Das- gupta and David McAllester (eds.), Proceedings of the 30th International Conference on Ma- chine Learning, volume 28 Proceedings of Machine Learning Research, pp. 02.427-335 Atlanta, Georgia, USA, 17-19 Jun 2013. PMLR. URL ceetps::/proceeddinee www.eeeeedinnmm........m.m. mir wwt.s..rr.e.see/ jaggil3.htme html
Prateek Jain, Suhas S. Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli. Streaming lin- ear system identification with reverse experience replay. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan (eds.). Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Infor- mation Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 30140- 30152, 2021. URL https://proceed.ngg htwp://wwweedin..........ee.e.ee neurips. cc/ pttpppppee/22///aaaa... cdccae/eosaaaaaaaaacceeeeeeooo
html
Yassir Jedra and Alexandre Proutière. Sample complexity lower bounds for linear system identi- fication. In 58th IEEE Conference on Decision and Control, CDC 2019, Nice, France, Decem- ber 11-13, 2019, pp. 2676-2681, IEEE, 2019. doi: 10.100/CDC40022229999999999 https: //ooi /10. wTT.///CC4002/000 2019. 9029303
URL
Vladimir Kostic, Pietro Novelli, Andreas Maurer, Carlo Ciliberto, Lorenzo Rosasco, and Massimil- iano Pontil. Learning dynamical systems via koopman operator regression in reproducing kernel hilbert spaces. In Sanmi Koyejo. S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural In- formation Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28. De- cember 9, 2022, 2022. URL ht /ttp:///epeepaaaaaa....aaeaeaaap
ni wwwpcpppppppppppeeeeeeeeeec...ee forr__fiiee fwwef/ /ft.ess/pppeee/222//
h
12

---

Published as a conference paper at ICLR 2025
Lennart Ljung. System Identification, pp. 163-173. Birkhäuser Boston, Boston, MA, 1998. ISBN 978- 978-1-4612-1768-3 doi:
8.11. URL https:: doi. org/10.
1007/978-1-4612-779
11.
Horia Mania, Michael I. Jordan, and Benjamin Recht. Active learning for nonlinear system identification with guarantees. J. Mach. Learn. Res., 23:32:1-32:30, 2022. URL https:
//jmlr. /r/0 807 html
Thomas M. Moerland, Joost Broekens, Aske Plaat, and Catholijn M. Jonker. Model-based inforcement learning: A survey. Found. Trends Mach. Learn. 16(1):1-118, 2023.
doi:
10.1561/2200000086, URLhttps: /tts:////ooooooo org/ 10. 1211/22000020666565 23100000
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019. URL http:://pppeer..arrrps....../// 9015 hasl--yyorrhhhee -nmmhrrrttmmmmtt..ammmmmmm ve htgp:///eeeigggperoooooorreeeeee
library.
pdf
Mark Rudelson and Roman Vershynin. Hanson Hanson-Wright inequality and sub-gaussian concentration.
Electronic Communications in Probability, 18(none):1 9,, 2013. doi: 10.1214/ECRy18- 2-2855.
URL htttpss::///to owoo:i.org/o0.. 1214/ECC v18 2865
Tuhin Sarkar and Alexander Rakhlin. Near optimal finite time identification of arbitrary linear dynamical systems. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 56105561060 -6180 PMLR, 09-15 Jun 2019. URL https: Rttt: h/tpt:::///roccednnga mlr. wte.s/ v97 wtt.aaaaaaaraaaa h
Max Simchowitz, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. Learning without mixing: Towards a sharp analysis of linear system identification. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 439-473. PMLR, 06-09 mlr www..mmr....ss....mmmmmmmmmmm..m / vv5 www.shwwwwwit....mmmmmm........e tz 8a html
Jul 2018. URL https: httphhttp///p/oooo http:://rooceedeee
Alex Simpkins. System identification: Theory for the user, 2nd edition (ijung, 1; 1999). IEEE Robotics and Automation Magazine, 19(2):95-96, 1999. doi: 10.1 1090/RA.20122.222227....
Nilesh Tripuraneni. Chi Jin, and Michael Jordan. Provable meta-learning of linear representa- tions. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Con- ference on Machine Learning, volume 139 of Proceedings of Machine Learming Research, pp. 10434-10443. PMLR, 18-24 Jul 2021. URL htttps:/pproeeddnggs http://rccceennngm.m.e....e... P139/t=ipuramenn2l.. html
Anastasios Tsiamis, Ingvar Ziemann, Nikolai Matni, and George J Pappas. Statistical learning theory for control: Unite-sample perspective. IEEE Control Systems Magazine, 43(6):67-97, 20223.
Stephen Tu, Roy Frostig, and Mahdi Soltanolkotabi. Learning from many trajectories. J. Mach. Learn. Res., 25:216:1-2166 109, 2024. URL
23 1145. html
Guido Van Rossum and Fred L. Drake. Python Reference Manual. CreateSpace, Scotts Valley, CA, 2009, ISBN 1441412697.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5998 6008,6008,00000 URL /ttp:////////////eeeeeeeoooo.e. 9tteee222457/eeee111101 TTT5e7/554aaaaeToooo333a3aaaess3 http://ppppppppppppp//////////aa
13

---

Published as a conference paper at ICLR 2025
Martin J. Wainwright. High--Dmensional Statisties: A Non--symptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019. doi: 10.1017/
9781108627771.
T. Wright. A Bound Tail Probabilities for Quadratic Forms in Independent Random Vari- ables Whose Distributions are not Necessarily Symmetric. The Anmals of Probability, 166):006 1070, 1973. doi: 10. 1771966617 URL 1176996815
1214///pp.//
Oguz Kaan Yüksel, Etienne Boursier, and Nicolas Flammarion. First-order ANIL provably learns representations despite overparametrisation. In The Twelfih International Conference on Learning Representations, 2024. htths:::: wttp:///eppeeee.e////m//m net/ wtte///ooommmnmn/eeee
BEW
Ingvar M. Ziemann and Stephen Tu. Learning with little mixing. In Sanmi Koyejo, S. Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurlPS 2022. New Orleans, LA, USA, November 28 December 9, https////aaaaiiiles///////////// 00057000..cSaaa000333077f7fofer0
2022, 2022. URL /tppa///////////raoooooooooa/aaa
14

---

Published as a conference paper at ICLR 2025
ORGANIZATION OF THE APPENDIX
The appendix is organized follows,
In Section
we provide a sketch of proof for Theorem
In Section
we provide preliminary tools needed for our analyses: Hanson- Wright and Hanson-Wright Freedman inqqualities, supremum of uub-Gaussian processes, covering numbers and proof
Theorem
In Section
prove Theorems 4.1 to 4.3 jointly under Theorem C.4
In Section
we show that the rates extend to approximate empirical minimizers.
In Section provide numerical experiments to verify theoretical findings.
A SKETCH OF PROOF
We provide a sketch of proof for Theorem 4.1 The proofs of Theorems 4.2 and 4.3 are similar and can be found in Section C In the following, A a shorthand for MA MA and E' R N is the matrix that collects the noise concatenated over time, as explained in Theorem C.1
The empirical risk minimizer Å satisfies the following optimality condition:
((A) & L(A'), written differently, |AA Ir (E"
(13)
due to the well-specifted setting, i.e., A' A(D.. The condition in Equation (3) is of interest as
AA A(D), E [|A a² NIIA A L. 112-
E [Tr (E
This inequality hints that if for of matrices DD) A(D), there is uniform result
E YAA A'(D) |A |
2TH (ET [))
(14)
with high probability as seen from their means, then the empirical risk minimizer Å belongs to set A(D) (DD with the same high probability by simple Bayesian argument. Hence, the proof of Theorem is reduced to proving Equation (14) for a suitable set of matrices.
Fix A A'DD and study the martingale series defined through the differences sequences
(A - x(') (((m)
(15)
where the series is first ordered in i, then in f, and finally in n. The sum of the differences is then
YA
Σ
Σ (A A") x(! (("))
Tr (ETTE
ni
and the quadratic predictable variation of the series is
WA = Σ E (E.")
[ Σ A) A)
= -
The condition that is asked in Equation [14 is then that the sum of the differences YA is large compared to the quadratic predictable variation WA, E (AA A'(D) WA & 20
In order to prove probabilistic statements on E, we use Freedman's 's inequality (Freedman, 1975 Dzhaparidze & Van Zanten 2001) which gives control on YA and W for particular A:
P(YA rY W rw) exp (-r 72/2
(16)
rw Rry
and ry,rw, > 0 are arbitrary constants. As the noise is sub- Gaussian, it possible to upper bound WR with WA:
where W WA En
Σ
(m)
Σ n,C
(A A+) 12
sup
nit.
whh
YA : W < C In (2dNT) WA.
15

---

Published as a conference paper at ICLR 2025
Further, assume that there uniform upper and lower bounds on YA and WA. respectively:
30 < ag < ay such that A E AD) YA & au and ar & WA & SWA
(17)
Let = C1 In 2dNT and set to be the smallest integer that verifies ex' aL 2 270 Then,
P P(WA & YA) & (WX < YA) < U (W & a 2 3 c² az)
Each of the terms in the union can be controlled by the Freedman's inequality in Equation (66) with choices of ry = age k-1 /2y00 rw = =aze and It = 20ya":
P(WA & 2
exp
807204
1=1
(18)
07
+ In [In ( [Cg02 in (2dNT) ou
+ +11
< exp
C2or (In 2dNT)²
0
the probability of the event {W < 2o largely con- trolled with the lower bound a', as the ratio / only matters logarithmically. This is crucial as the og and differ with the condition number which can scale with T.
As can be seen from Equation 18
Therefore, possible control the event with a union bound over an e-net of A')).. In particular, az needs to be uniformly bounded below as follows:
ag e In WW (D)) In(dNNT))
This is achieved by Hanson- Wright inequality (Hanson & Wright 1971 which allows us to derive the needed uniform lower and upper bounds in Equation [17)
YA & c o
W WA > o2otmmin
miin NL.)>NIAAII
with high probability as long as A'(D) is composed of matrices that satisfy
where e~ polysqrt(p. c² In
> In (n.(('((
Here, we pick up the dependency on scales with k. This is needed bound the worst-case errors while transitioning from point-wise bounds on the e-net (N)()D)) to the whole set A' (D)..
Finally, since there uniform bound on | & 2D implied by Theorem 3.4
setting
A'(D) = A D2 pdr pdr N polylog(x,p.d.NNTT)
for some constant C(²) is sufficient to deduce Å A(D) A'(D) with probability 1- The proof
of Theorem 4.1 is then complete as A/ = ||M MA 11 > (T p) - -
B PRELIMINARY TOOLS
B. HANSON-WRIGHS INEQUALITY
We use Hanson-Wright inequality (aassnn & Wrightt 1971 Wright 1973 Rudelson & Vershynin 2013) to show concentration of certain second-order terms.
Theorem B.I. (Hanson- Wriigt) Let 7 = (Zi.... 7n) R random vector with independent
components Z: which satisfy E[Z.] 0 and 7 & K. Let P be an matrix. Then, for
every r >0 0,
< exxp (-CHw min
P P PZ E Z PZ|
>))
K2|lP1lbp)
KII
The bound can be turned into a one-sided bound by dropping the constant Remark B.2. For data regime considered in this paper, K ca in Theorem B.1
16

---

Published as a conference paper at ICLR 2025
B.2 FREEDMAN'S INEQUALITY
We use an extension of Freedman's inequality (Freedman 1975) to non-bounded differences by Dzhaparidze & Van Zanten (2001) show concentration of certain second-order terms. For the sake of completeness, we provide the original Freedman's inequality. We also remark that it is possible use the original Freedman's inequality in our proofs to deal with any bounded noise, leading to improved logarithmic factors, as explained in Theorem C.27
Theorem B.3. (Freedman's inequality) Let .o,..., Yn be a real-valued martingale series that is adapted the filtration Fo...., Fn where Yo = O. Let d1,...,dy be the difference sequence induced, i.e.,
d, Yi-1 for I. Assume that d, is upper bounded by some R, i.e. |dyl & R for all i. Let Wj be the quadratic variation of the martingale series, i.e.,
W Σ ==1
Eld
F5-1l for = =:....... ,....,n. n.
Then, for any T, W > O,
r²/2
P P 2 0: 2 and Wa W) exp
W Rr
Theorem B.4. (Freedman's 's inequality for non-bounded differences) Let Yo..... Yn be a real- valued martingale series that is adapted to the filtration Fo...., Fn where Yo = 0. Let d dn be the difference sequence induced, i.e.,
di YY= fori = n..
Let W.B. be the quadratic variation of the martingale series plus error term for large differences,
1 R = DEId F,-1l + d((())22)) for = ,,..., n,
1=1
We see W. = W for ease of notation. Then, for any R, W > 0,
/²/2 W + Rr
P(kk 0: V and W < W)& & exp
We extend these theorems in Theorem B.5
compare the quadratic variation with the martingale
series itself. This useful in our proofs to show certain events necessarily implied by empirical risk minimization do not occur with high probability.
Lemma B.S. Let 7, R > 0, ou > oz > 0 be scalars and let denote the following event
E = (W. > an.) n (Yn & &ov).
where Yn and W verifies the assumptions of Theorem B.4 Then, we have the following concen- tration inequality
2ey P ({w & (Yn) Nε) & exp ( (ey + R)
aL
+ In
In
yau az
+ 1
Proof. Let G {aL, eaL, ... e., aa where k is the smallest positive integer such that
ea > 700.
Then, by union bound,
P (w. < 7Yn, < < ( ((W, <e'a e- az) NE))
< (U ((W. se'ol, d oz))
((W!l v Sdal, / da))
17

---

Published as a conference paper at ICLR 2025
By applying Theorem B.4 with e' anly -''1aa// and W c'aL, obtain
c 27 (ey - Rt)
P( <eaL, Yn e- a2/7) & exp
for each = 1....,h, k. The union bound gives
2t
Σ P (W & e'az, Yn e' az))
Σ exp
27 (er + RR)
==1
ar
exp
+ 1nnk]
20y (ey + R)
The result follows by noting that
yau
In
ap
B.3 SUPREMUM OF THE NOISE
We need the following lemma to control the supremum of the noise in our proofs.
Gaussian random variables (in the sense provided in Theorem 3.1 Then, there exists universal constant d' such that for any t O,
Lemma B.6. Let XI...., X, be i.idd mean zero and o'-sub-Gaussian
(2
PP
sup
[xJ] 2oV22n2n & exp
20'02 (-
Proof. By the sub-Gaussian property, we have a universal constant such that
,2
P(X: > < exp
22
Then, by the union bound,
(
p2
x12r <UP((, < nexp
sup
22202
L......,
Similarly, we have
,2
P
sup i== L=.....,
-X, -X,
< U,P nexp
22
The result follows by union bound with r c'o 2n
Corollary B.7. For any 0 < < e1, there exists universal constant e' such that
1 VIn2dTN vmm)
sup in
( 1bo & covz
with probability 8.
(x) are i.i.d. and sub- Gaussaan with parameter a. By Theorem B.6
Proof. Each component
P sup (x) 2oo > doo 2oo22n22N +1) < exp (-
(-2d2
20
ta
for any t > 0. Select = co 2n to obtain the desired confidence level of 6.
18

---

Published as a conference paper at ICLR 2025
B.4 COVERING NUMBERS
We use the following lemma by (Candès & Plan 2011 to control the covering numbers of the set of matrices:
Lemma B.8. (Covering number for low-rank matrices) Let Maxxna denote the set of low-rank matrices of rank T and Frobenius norm bounded by 1:
M = {M E 1 ||M = (M) & r).
Then, there exists e-nel S of M for Frobenius such that
(mitn2tl)
S
&
Corollary B.9. Let My (D) denote the following set of matrices with bounded operator norm:
My (D) = {A E Rdxpd ||Al|op & D, rank( A.) & 1.. 03
Then, there exists an e-net S of Mr (D) for operator norm such that
9p'dr In Dp'
|S| < exp
Proof. Since for any matrix M, |M < |M]L, sufficient to give covering number for the Frobenius norm. Let MDx((D) be the set of low-rank matrices of rank and Frobenius norm bounded by D:
M (D) = {MER) axd ||M & D. rank(M, < <r]
By Theorem B.8 there exists an net S of MD) for Frobenius norm such that p
9Dp'
(2d+1)r
9dr In Dp'
[S] <
<
exp
as any -ne of M gives an Dp'
e S-net of Md)
p'
Observe that the set Mr (D) is subset of
u u= (M) x P Then, (S)z gives an e-net 14 and hence of Mr (D).
B.5 PROOF THEOREM 3.5
Proof. Using Theorem C.12 have || llop & |lllp" directly leading (ii).
For (i), we have
M llop
MM where A, = Og, .a..a,,,,0. Os, n Os,..., Og
i-1 times
Then, is easy to see that
JM Am llop & ||A
19

---

Published as a conference paper at ICLR 2025
C PROOF OF THEOREMS 4.1 TO 4.3
Before proving the main theorems, we recall certain definitions from the main body of the paper: Definition C.1. For any A E RRexpd, let A Day be defined as follows
A = (MA: - MA;), As, 0s. 0.)) A; (AI, ..... AJ, 0a. 0a)
where A
Let g() E Td be the whole noise concatenated in time, i.e.,
g( (
and let E E RTTxN be the matrix that collects the noise for all sequences, i.e.,
F. = -C(1) (g.))....,gm)) {()).
Proposition C.2. With the definitions of Theurem C.I we have the following properties:
Σ (A - x (m)
<l = Tr(E" AA,L,E),
Σ - A;) | -I[MA, -
F
n1,
Definition C.3. Let Ar, (D) and Sr.p (C, D) be the search and solution set for constants C, 1:
Arg = { A E dd pd | & D. rank(A.) Er, =.+1.....5 =.. Ap=
p'dr
Sy.r (C, = A(D)
||A - & ID N(T - -r)
where 1) a constant that captures an additional factor for the misspecified setting,
ifp' p.
max 1. (. (MMA-MM;)) MA;) Lx [mp
ifp' < P,
and T is the following logarithmic term:
-1+ In p NNNN2 3
T T- (1+
Let (C, be defined as follows,
{ A Anp(D) (
|
& T p'dr
Grow (C, D) =
|
We set Ar.p' = Arp((o)) and G(C))r.p' (o), Lastly, we drop the subscript r,p' when it is clear from the context.
C.1 MAIN RESULTS
In this subsection, we state Theorem C.4 that generalizes the statements in Theorems 4.1 to We give a proof that reduces Theorem C.4 to a uniform concentration result in Theorem C.5 The proof of Theorem C.3 is deferred to Section C.5 Next, in Theorem C.6 we discuss the factor 7 that appears in our results and the conditions under which our misspecification bounds are tight. Lastly, Theorem C.7 removes the constraint on the diameter of the search set which allows to treat OLS as a special case of the main theorem.
Theorem C.4. Let Theorems 3.1 and 3.4 hold. Furthermore, let Theorem for and Theo- rem 3.9 for p' < hold. Consider the following constrained empirical risk minimizer:
-= argmin
AEA(D) L(A).
Then, for any 0 < 8 < -1, there exists a constant C(6) such that
P À E S(C(6), D)) > 8
20

---

Published as a conference paper at ICLR 2025
Proof. Let EA be the following event
ε (II & Tr AAL,E)).
By Theorem C.13
((C, C D) and thus, for any random choice of A,
((A S(C, D))) > ((4 G(C, D)) = =1 P(14-
D)))
For the choice of Å, (Ex) = by Theorem C.15 and
P A [AES(C. > >1- ((EEA(D))
By Bayes rule, we have
P (
> - 1 1P(1EE E ((C.) G(C, ( PP (( A(D) A(D)
> 11-P A(D) ((D))
Then, the proof is complete by applying Theorem
C.5 to the right-hand side.
Theorem C.5. Let all the assumptions of Theorem C.4 exists a constant C(ő) such that
hold. Then, for any 8 < there
IP (3A A(D) \ G(C()), D): |IA < 2T/TT(E' AAL,E)) <d.
(19)
Remark C.6. For strictly stable systems with || < 1 and [Ma; lap < 1, the factor is controlled by Theorem C.10 However, for marginally stable systems or explosive systems, there is no a prior good upper bound on TT, implying that the misspecification results only applies to strictly stable systems without any further assumptions.
Corollary C.7. Let all the assumptions of Theorem following condition:
C.4 hold and suppose that NT verifies the
NT' > C( Tp dr
(20)
where 0 < 8 <<< <- is a constant and C(6) is given by Theorem C.4
Then, the OLS estimator
ÅOLS argmin ((o()))) L(A),
satisfies the same concentration result in Theorem C.4
P AOLS S(C(8), > 1-5.
Proof. Assume that D is sufficiently large such that
A(D) C(C(()) D) ie., the interior of A(D) contains S(C(6), D). We have the following relation:
A(xc) = (A' = a A E A(D) a
Then, by Theorem C.5 we have
P PBAA A(oo) D) [ < 2r AAL,E))
= P (3a > 1E R. A(D) \ S(C(6), AAAL & Tr AaAL,E))
= P -PA E A(D) S(C()), D) | Fl < TT( AAT. E5,
as Va > 1, we have the following:
LL, < 21 Tr(ET A)L.E) = |A < 21 Tr(E" A))L,E). Thus, the result complete by applying the same argument in Theorem C.4 where A(D) is replaced by A(co).
We only need to provide such that A(D) c S(C(6).)) For any AE S(C(8), D), we have dfr
A
p'll 2 & p'I ||A & C(
N(T v')
from Theorem C
Therefore, we need to find D such that
p2
D2 C(6)D2
N(T - p¹)
which equivalent the condition in Equation 20
21

---

Published as a conference paper at ICLR 2025
C.2 TECHNICAL LEMMAS
In this subsection, we present simple technical results on L,, MA and A that are used in the proof of Theorem C.4
Lemma C.8. L. and MA. satisfy the following relations:
L. = MA +1, MA- (L. (L.-1)-, (I= -A-)
Proof. The first relation follows from direct computation. For the second, note that L, is invertible since it a lower triangular matrix with non-zere diagonals. Lastly.
L I + M L.
+ MA M2 L.
M++MA - M2. + ... - T-
(I - (
where we have used the fact that M Oтd-
Lemma C.9. Assume that || llop < 1. Then, the operator norm and minimum singular value of L. are bounded as follows,
< O (I.w).
+ MA-
|M
1lop
Proof. By Weyl's inequality for singular values the identity I., MA T.+ from Theorem C.8.
|L < [M + |M L. olop < 1 + || |lop Lx
| olop || JM L. olop > ||MA olop L. lopp.
This implies the desired incqualities for | llop. For the lower bound on minimal singular value, use Theorem C.8
1
miin (L.) Jmin ((I - (T--)-)--) || MA 1lop 1 |M lop
Corollary C.10. Assume that |M llop < and [|Ma , llop < Then, we have
1 E - |I A 1lop
Proof. Applying Theorem C.9
|| llop +
MM
11 á MA- Ma;, lop
|L.
lop <
2
llop
1-
||
|lap
Lemma C.11. Assume that || & D. Then, the operator norm and minimum singular value of Lu are bounded as follows,
DT
LLp <
& Jmin (L.)
D-I"
D+1
Proof. By Weyl's inequality for singular values on the identity I. = I MA + MT-1 from Theorem C.8
T-
T-1 D
DT
LLllop < 11p
+
Σ
M
llop <
<
D-1
t=0
22

---

Published as a conference paper at ICLR 2025
For the lower bound on minimal singular value, use Theorem C.8
1
1
muin (L,) = Omin ((I-MA-) 1 MA lop >
1
+
llop
D+1
Lemma C.12. For any A E Rdxxd
|| op & |MMlo Vv'llAllop lop
1
- A Al < | A
A
||
<
p Al
T
Proof. Let u (u,,..,,uy ur) E Rd be an arbitrary vector with | = 1. Then, setting u-a = 0 for any a >
T
T
Ma 2
Σ l (Ma
Σ
u
i=1
1=1
A -1-0
Ag llop 1/
1=1
A op
p ||
12
p'1| || 10p.
The left-hand side of the first inequality follows by picking u1T = 0 and U1:p' as the maximal singular vector of A.p with unit length. The second inequality follows by simple computation. O
Corollary C.13. For any A E A(D).
D2
A 22
||A A-AA
T
A
op
Proof. By definition of A(D),
D2 || A
>
T p 1A
T p' A
oop
and the result follows by Theorem C.12
Proposition C.14. The empirical risk minimizer Å, i.e..
À E argmin AEA(D) L(A),
(21)
implies L(A) < ((A)), which can be rewrillen follows:
A A L1. El < 2TH LT (1- (
) L.E)
Proof. By Theorem C.8
NTC(A)
[MM 1) L.b11 [1(MA MA.) L. 1] 11 E1?
[[(MA -MA3) L. (MAS, - -M L. - L3
[MM - MMas) L.E| + +I[(MA,,
- -M..) L, - 1 E
+2T LE "MA;)' [[MMA) - -MA.) L. - -1_ E)
=I(MA- - MAa)) L.Ei + +1[MM,, -1) L.
=
+T (F.L.. (Ma - -MA)) (MAz - -1) T
23

---

Published as a conference paper at ICLR 2025
Then, have
NT ( = -1(MA - MA;)) T., Fl,F
(22)
+ 2
L.
MAy)) (0))(MM)))) (MAg. -1) I FB )
which implies the desired result for any A that satisfies ((A) & ((A))).
Corollary C.15. Observe that for p' = p. Theorem C. 1.14 reads
A T. < 2T (E' A FT.
For p' < P. one can write the following relaxed condition for any A.
| I, F1 &
(T - (MMM;,)) T.m Tr A F))
2 Ina (MA* -MAY) L.
Tr Tr(E"AALLA AL.
op
2 1+ |[ (MA- - MA;) I:x
Tr A 1T,
2n Tr (E' A FL.FF
C.3 LOWER AND UPPER ISOMETRIES
In Theorem C.16 we present uniform bounds on A. Fl and Tr(ET A.T.F) in terms of ||AA|[F F. In order to establish these bounds, we first start with point-wise bounds in Theorems C.19 and C.20 that rely on Hanson-Wrin Wright inequality for bounding the deviation of quadratic forms. Then, use Theorems
C.2nnsCC.TTuc t.2T C.23 with discretization argument establish uniform isometries.
Finally, with Theorem C.17 we have a uniform control over the range of both | E| and
Tr(E" AAL,E).
Theorem C.16. Ler > be small and fixed. Then, there exists a constant < C(0) = (ln(116)
such that the following holds uniformly for all A E A(D) \ (C(C, D) and C > C(6):
|AALL
8 mmin AII
Tr(ET ALL.E) < Lo CTD'drN
with probability at least 5
Proof. Let 11, E (0,1) be arbitrary. By Theorems 1 81 82. the following holds:
C.19 and C.20
with probability at least
E| > o² (1 Enn) m (L.) 2 A :. Tt(E Tr(ETAAL.E) AAL.E) & 22 L. CCNTTp/drN AAIIF
(23)
for any arbitrary V1, U2 E 1) and A E A(D) ((C,, D) where
81 exp (-CmnnC2ri''ppp dpdrrr Let B(C, D) be the normalized A(D) \, (G(C,
82 exp (-OnnCuzi'
B(C, D) = A
A A \ (
|| F
Then, since the conditions are homogeneous, Equation 23 holds for any E B(C, D) with prob- ability 1 - 51 6z.
Let (D) be e-net over the set B(C, D). Hence, with probability at least
1 - 6g 1 (NG(D)) 5z),
24

---

Published as a conference paper at ICLR 2025
the condition Equation
23
holds AA E Nc(D). Moreover, by Theorems C.21 to C.23
we have
1 0² (1 ev) min (L, (L.) o3
||
P'NTT plp dNT
2
Th(E AxL.E) < e
AA E B(C, D) with probability least 1 - 60 83 where
83 exp (-C#w min ( (us, vz) dNT)
Recall that
| > (T A| T P:
for any A E (CC, D) due to the normalization.
Setting
42 12 = 2c and such that
T p' T
I V p'd'
CTp dNT
6
2 211
min
(cond(La)
and we have the following:
1
o² mina (L.)
2 0² (1 - Evi) min (L.) P d2 (1
o²
CyRTp/dNN AA F +o
< Lo COPTYONNIAAll
AA E D) with probability 1 6 dz.
By homogeneity, this implies that VA E A(D) \ G(C, D), with probability at least 1 - 80 63.
o²
| T F
miin (T,,) (
AA F) & T lo / CCPTT//rNNAAlll
Lastly, we need ensure that 8, + 63 & 8. First, 63 & 8/2 can be achieved with the choice of
In 372
(5(5) = max 1.
= O (In(1/8))
CHwdNT
Moreover, the c-net size is bounded follows:
[NG(D) < exp (9
by Theorem B Then,
50 (Nc(D)) (81 + 52)
< exp (-16 Cnw dr + 9p'dr dr In 2
<exp
Thus, 50 8/2 be achieved with the choice of
16c4
9 D' + 2/2/
C C(5) 5CHW1)²
(24)
p/dr
Note that 7 1 and the latter term is (In(11))). For the first term, crudely upper bound In z by using I > In + 1 for any x > 0:
of PNNT2
In
In
+ In (I.) + 2n + (32g(//2)) < 0(n(11)))
T T-
Therefore, the definition in Equation
24 verifies C(a) = O(l()1)))))))))
25

---

Published as a conference paper at ICLR 2025
Corollary C.17. For any small 8 O. there exists constant C()) = (In(1/6)) such that the following holds uniformly for all E A(D) ((C()), D) and C (
o²
inf AEA(D)G(C.
A El min (L, (La.)(i))))'''>>''t
Tr(E' ALL.E) o Lo ( CC
sup AEA())CC..
Proof. Plug in the results from Theorem C.16 and use the definition of A(D) \ ((C(6), to lower and upper bound || | I|F
Definition C.18. For applying Theorem B.1 our setup, consider the following objects:
E (5
{(N))² ERNTA
A diag( E RNd x W
where diag(P) puts the diagonal blocks of a larger diagonal matrix.
Lemma C.19. For any A E A.A. ((C) and E (0, 1), with probability least
1 exexp (-CHwCrPiTpdde
we have the following
IALLL > 0² (1- mmin (L.) Al.
Proof. First, observe that
A. min (
Applying Theorem B.1 with P A and 2
HEAAAAEE -E
-CHW min 12 A
< exp
I A
Observe that ET A = Tr(E TH(E (TAAE)
A and E E Ir ÉE AXDx))
EE
E E
o² A = N
Furthermore, || N A
NIATAAI2 and D
A A olop = | 11@p Plugging these into the bound,
P (IA O
> CO 1T) &
|
exp
-CHw min VNN
.N A
| 11pp
Then, using | < |A 1 and // < <1,
(-CRwee
A
(IIAAE o² -1- (11-VV)NNAAA1 > exeepp exp
The result follows from the definition of set A A\g(()))) ((())
Lemma C.20. For any E A\ (((()) and v E (0, 1), with probability at least
1 1 cxcxp (-CHw Cv C2 (-CuwCu???Tp''r) rp'd
we have the following
Tr(ET A. & 202
CuPTp'dr C AAlF
26

---

Published as a conference paper at ICLR 2025
Proof. First, by the properties of trace and Frobenius norm, we have
Tr(E" AAL,E) |L.. Tr(E" AAE)
Applying Theorem B.1 with P ÂΛ and r = co AAlle,
1 A E - EIE A
dr |
A A
A olop ))
& exp -CHw min
/CC V Ci dr
Noting B[E Â E] and rewriting.
P A) EdouN
exp (-ORw min v Cnj vy CapTp/drN
AAalle
})
A
The result follows from the definition of set A ((C).
Lemma C.21. For any O, with probability at least
eex (-CHw min {u. v² JdNT).
we have the following
| dNT & cdv.
Proof. Applying Theorem B.1 with P= L=TN, -.
PÉTÉ-EEÈT e ( & exp (- (op-CmwwdNT)
The result follows by the fact EL EJ d'dNT.
Lemma C.22. For any A,, Ag A
| L, E
L. - -'||A - 2 L. 1 1
Proof. By the properties of Frobenius norm and Theorem C.12
|| F (| - AA, + A I,, El
Al 11 +2] A. - AA
2 A L, +
AA, I. 2 1
<
2/ ||
11g
The results readily follows by reordering terms.
Lemma C.23. For any A,, A2 E A. Tr(E L., & TH(E L,E + V A
Proof. By the properties of trace and Theorem C.I2
Tr(ET LA
Tr (ET (AA, DA, AA,)LE
TI (ET AA, L, + Tr (E (A - LA)
"I (ET LA, <
+
AA, Ilpp llop || bil?
Tr (ET
A - L+ E ?
27

---

Published as a conference paper at ICLR 2025
C.4 CONCENTRATION INEQUALITIES
In Theorem C.24 we show that the quantities of interest that show up in Equation 19) are related martingale series and its predictable quadratic variation. This allow us use Theorem [3.5 in Theorem C.26 to quantify the probability of the event in Equation (99) for finite sets of A.
Remark C.24. Fix A E A(D). Consider the martingale differences sequences
di
A7) -(A-A)) x;") (5()))
where the series is first ordered in i, then in t, and finally in n. Let Y be the sum of the martingale differences, i.e.,
Y= Σ d
1,
Let W. be the quadratic variation of the series plus an error term as in Theorem B.4 i.e.
A Σ E (1))
(
2
Σ
(2
(1))
2
n,t,i
Then, we have the following computations:
YA Σ (AA - A3) (1) [ Tr TT AAL.E)
WA W 0² Σ 44-
A7) x;)xx(111 ||
o2 IALLELE
Proposition C.25. Let 0 8 c- and R be constants. Then, with probability at least 1 - 6,
we have
WA A(D), C' <(IDANT + mn
! WA W
(25)
where C² 1 Ac and d' is the universal constant in Theorem B.6
Proof. By Theorem B.7 there exists constant d' suuch that
(Vin2dTN + In 1
sup || 1o & <dov2
V
Therefore, for any A E A(D), we have
W WA + Σ d (d(o))
Endgs
[I22dT + In 1
1 ((A- - Azr )² 2
< WA + 202
Σ1
(122/TN+ + E ((A- A3))
1
(()));)0 x² 2
& WA + 462
n.t.s
(M22TN + + +m 1) WA + 4
WA.
Then, by rearranging terms, we have
1 462 (I220TN+ > WR.
28

---

Published as a conference paper at ICLR 2025
Theorem C.26. Let S S A(D) be finite set and let E(S) be the following event
2 at }
E(S) = inf WA
sup
YA & av auj.
AES
AES
where O,1,, ou > are two constants. Then, for any 7/ and < d d<<< <e
P P( WA
< A NE(())
aL
+ In In (2'aw) a2
+ +1)) + 8,
expp
exp
2 (n' + R)
where y' = C'ey
2d2dTN + In
and C' is the universal constant Theorem C.25
Proof.
For any A, let &a be the following event:
ΣΛ = { W > aVAn <aut.
Then, by union bound, have
IP ((3A E : w < ?Ya} NE(S)) < Σ P((WA < NE(S))
AES
Σ (( < 7Yaa) NEA)
Aes
For any A E S.
PP (W & 7YA < exp
aL
+ In
In
you
+1
2ey (e> + Rt)
ar
by Theorem B.5 which implies that
((3A w & 7Ya) nE(S)) < [8| exp
aL
+ In
In
you
+11
2ey (er (227
R)
at
Finally, let be the event in Equation 25 Then,
P( WA & N
< ((EA ES: WA & 7Yaa P(())
1
P
3A E S <
In2dNT + In j YA NE(S))ES +
P ((3AE S: & c'y
[n2dNT + in 8 !) Ya( nE(S) +8.
1
C.5
PROOF OF THEOREM C.5
Recall that Theorem 244 shows that
YA = Tr (F. AAT.F). WA = =A=
Therefore, need show that for any 0<6 -1 there exists a constant C(o) such that
P (3AA A(D) ((C(()) D) WA < 20 < 8.
By Theorem C.17 there exists a constant
(6/4) (1nn(1))) such that for all C > (6/44)
d WA
inf AEA(D):GCC.))
>
Omin (T.,) CDD2
(26)
YA 0² LL op &D
sup AEA(D)CCC..)
29

---

Published as a conference paper at ICLR 2025
with probability 1 5/4. In addition, by Theorem C.21 with probability least 1 5/4, we have
In 6
| < (1 + c2644)) dNT, where v(6/4)= max {
max
(27)
CHwdNT
In the following, we work conditionally on these events.
Let S be c-net A(D) A(D))G(C, D). By Theorems C.22 and C.23 for any A A(D) there exists A' E such that
WA 2 W - (66/4)e YA Ya c2
where c1(6/4), (2/4/) are given as follows:
(6/44) = (1 + =
(6 0
We set as follows:
min (V ci(0/4) (02
D
In partieular, is small such that for any A E A(D) \ D),
E E S: WA & 2WA + 20l,
YN > YA 40
(28)
Assume that A E A(D) \ G(CC D) verifies
WA & 20 AYA.
Then, by Equation 28 there exists A' E S such that
WA & 4WA < 802 1602ny 4WA 160
Therefore, we have
PP ((3A e A(D) D) WA & 20² NE) < (P e S: WA 1602n\A) nE).
where & is the event that both Equation (26) and Equation 27 hold.
By Theorem C.26 there exists a universal constant C" such that
(13A E WA < 160 1602n/ n1 NE)
& y/ou ar
[S]ex (- ar + +In In
+ +1)) +
(29)
(-
12
with the following choices:
7 16a2n, R ==ye=''r (12ddT++n
+ +nn
0
00 mmin (L, (DD'
ay 0² LL (D
By union bound, Equation 29 implies that
P (JAE A(D) \ G(C, D) WA < 20 <
[S] exp
aT 4,
+ In
In
+1 +1)
+
35
(30)
By Theorem C.12
we have
A A Alop
llap ||M A-
A A A'llop-
30

---

Published as a conference paper at ICLR 2025
Therefore, e-net covering of Mry (D) defined in Theorem B.9 is also e-net over A(D) after a shift by A and we have
Dyl
|n|S| < 9p' dr in
Finally, we have to show that the right-hand side of Equation (3) is upper bounded by 8. That is, need to prove
a1 4y
2 In
In
Y au az
+1) + 9p' dr In Dp + In 3
(31)
for suitable choice of C. Note that Equation (31) is homogeneous in addition, the left-hand side does not depend on whereas the right-hand side is decreasing in Therefore, for simplicity, we can set and 1) 1.
By Theorem
C.11 we have
min (L.)
D+1
2D
and
Crpldr dr 2 ((CC((+np''NNT)) (1 ln p'dr)
>
32
For choice that verifies
c=0 ((1+)1))))
(32)
have the following lower bound for az!
Inp'dTT (1 km) (1+ pl p'ár)
22 ( ((1
aL 41
(33)
The condition Equation
31 is satisfied if the following three conditions are individually satisfied:
1)
ii)
2
In
In
12
az
Dy'
(ii)
>
9p'
dr In
42/2
aL
(iii)
as the left-hand side of Equation
is increasing in C, while the right-hand side is decreasing in C, can pick the maximum that satisfies all three conditions.
331
Condition (i). By Theorem C.I1
we have
L.llop > (D + 1)op > (D 1)0min (L,) > 1.
and
2D 2D loper 0 (V(VT
a1
a2
As > In + 1 for any x > O, we have
Y
You O In
Ias + In 1 In
In
In
+ 1
aL
aL
The lower bound in Equation
33
is sufficient to satisfy this condition.
31

---

Published as a conference paper at ICLR 2025
Condition (ii.
We have that
Dp'
(1(6/4) 462(6/4)
In
& In Dp' max
aL
aL
D
D61(6/4) 462(6/4)
< In Dp' max
aL
ar
D
=0 In Dipp'NT-i NT las I In !)
The lower bound in Equation 33 is sufficient to satisfy this condition.
Condition (iii). This condition readily verified by Equation (3
Remark C.27. The choice of C Equation (32) and T, which appears in the bounds, have third- order logarithmic dependencies on 8 and the problem parameters, respectively. This arises because the ervor bounded above by second-orde terms in ô and problem parameters. An additional logarithmic factor appears due the discretization of the problem. Thus, assuming bounded noise, i.e. sup || <l & B for some > O, one can replace the thirl-order logarithmic dependencies with first-order counterparts, along with dependency on B.
D APPROXIMATE EMPIRICAL RISK MINIMIZATION
In this section, we extend the results of Section C to approximate empirical risk minimizers Ā as in Equation (12). We begin with trivial extensions of Theorem and Theorem C.15 to approximate minimizers.
Proposition D.I. Let Å be estimate that provides an cu-approximation to the loss of ((A))):
[(Ā) & ((AA) + Cr.
In particular, can choose À as ep-approximate empirical risk minimizer, i.e.,
Ā E E ((A) & ((() 6tr
where Å is the empirical risk minimizer defined in Equation 21
Then, À satisfies
| L < 2T (ET ET (E (MMM L.E) + NTeu.
Proof. The proof follows from Equation 22
Corollary D.2. Observe that for p' p. Theorem D. reads
| T. F 2T (F F...) NT
For p' p. one write the following relaxed condition for any Ā:
I. < Tr (ET AL..E) + NT
Proof. The proof follows from Theorem C.15
We divide the analysis into two cases: 21y Tr (FT FT > NT and 27 A & NT In the first case, we can directly apply the results of Section C to approximate minimizers after noting that Theorem C.15 implies that
|AALLEE|E (2n) Tr (ET AgL.E).
This is equivalent doubling the constant y) in the main theorem and does change our results.
32

---

Published as a conference paper at ICLR 2025
In the second case, have the following:
AAL 2
Recall the lower isometry proven in Equation (26):
o²
inf AEA(D)
AAL
O mmia(L)) 8
ctr is such that
2NT & T "
then the approximate minimizer Å is guaranteed to be in the set G(C, D) with high probability. By Theorem C.13 D) C S(C, D), and thus, we have the desired result À E D).
E EXPERIMENTS
All experiments in this section are implemented with Python 3 (Van Rossum & Drake 20099 under PSF license and PyTorch (Paszke et al., 2019) under BSD-3-Clause license. In addition. we use NumPy (Harris et al. 2020) under BSD license.
For all the experiments, A is generated as follows. First, orthogonal matrices of shape x d are sampled. These are then scaled down by a p where is arbitrarily set to 0.5. In cases where A needs to be initialized, we use the same recipe for the student model with p' instead of p and set 1. For experiments with low-rank ground truth, we set arbitrary d singular values following SVD decomposition. Each experiment in this section has been run over 3 independent seeds and the average is plotted. As the variance is small and the plots usually overlap, we opt plot it for visual clarity.
4.3 provide rates on estimation error for empirical minimizers. In the following. we study these rates empirically for various values of p', p, d, N, and r where r = d for full- rank experiments or r for low-rank experiments and p' = p except it is stated otherwise. We use two quantities, / = NT, the number of total tokens, 7 = pdr, the number of parameters to estimate, to summarize information in the plots. For Theorems 4.1 and 4.3 is computed with the OLS estimator and for Theorem 4.2, Å is learned with gradient descent with learning rate on the group-norm regularized loss Equation ( The parameter and learning rate a are tuned by a grid search.
Theorems
Figure [ plots the estimation error for d E 10, 15), p E 15) E {1, 10) and T (T,5, 10, 25, 50) x pdr/N. The upper bound in Theorem 4.1 scales with the ratio 8/7 up to logarithmic terms as empirically verified by Figure [ In Figure 2 we verify that there is no individual trend to p and d, which implies that the error depends only γ. Furthermore, show the trend in N can be accounted for by incorporating the logarithmic term into 3 to obtain 3= 3 + /N).
Figure plotss the estimation error for different degrees of misspecification where the context length is fixed to 15. The curves for various p' E {5, 10, 15} overlap, which verify the rate 7/8 p' /NTT predicted by Theorem 4.3 holds.
Figure Figure repeats the same plots for low-rank experiments where d = 15, r = 5 are fixed and N and T are varied as before. Good estimation of is not straightforward as has to be appropri- ately tuned. Yet, we see that the group nuclerr norm regularized estimators found with gradient
descent after tuning on regularization problem E {10-1, 10-2, 10-3, 1001,100 10-5, 5-105,0055 10066111 1,0-6,10-7
and learning rate a E { [10-1, 10- 20-2,,00 10-3) obtain improved estimation errors than non- non-regularized OLS estimator. Particularly, the sample efficiency benefits of the group-nuclear
regularization are amplified in the low-data regime. We leave the analysis of group-nuclear norm regularization as future work.
33

---

Published as a conference paper at ICLR 2025
N
N ==
N 10
10
50
8/7
Figure I: Scaling of estimation error with respect to the ratio 3/7 NT /pd with the OLS estima- for. The black dashed line marks the reference value 7/3.
10
1010
01/
8/7
Figure 2: Scaling of estimation error for different values of d and N with the OLS estimator. Recall that [ NT, pd? and 3 B/ Im/1m11111111111 + VN). The black dashed lines mark the reference values corresponding to 7/3 and 7/3.
#'=5
// 10
+ / //=1 15
109
11 A
30
50
8/7
Figure 3: Scaling of estimation with respect the ratio B/7 NT/p for different p/
5, 10, 15 with the OLS estimator. The black dashed line marks the reference value 7/3.
34

---

Published as a conference paper at ICLR 2025
p=5
p=
p=
==
10,
A=
15
A
A| A 1
10
10
B/7
Figure 4: Scaling of estimation error with respect to 3/7 NT
for different context windows
p 5, 10, 15 with the OLS estimator (A 0) and group-nuclear norm regularized estimators.
35


Reviews:
[{"review_id": "VOMLpWnnCy", "reviewer": "Reviewer_RGko", "summary": "The authors study the problem of identifying long-context linear systems where the state at any given time depends on a sequence of previous states over an extended context window. In contrast to traditional linear system identification that typically assumes first-order dependencies, this paper focuses on autoregressive processes of order \n$p>1$. The authors establish sample complexity bounds, demonstrating a \"learning-without-mixing\"-type of result. In particular, they show that a slow mixing does not inflate their learning rates. In addition, the authors further extend their results to the setting where the long-context linear model admits a low-rank representations. They also explore the implications of context length misspecification.", "questions": "1) In Section 5, the authors emphasize that the sample complexity bounds derived remain unaffected by mixing times, highlighting the \"learning-without-mixing\" result. Could the authors discuss more the slow mixing setting (i.e., when the system is marginally stable), would the learning rates deteriorate? \n\n2) The misspecification results in Section 4 suggest that shorter context lengths can still capture useful structure in long-context systems. Could the authors provide insights into specific applications where such misspecified models are particularly advantageous?\n\n3) I am curious about how coordinate descent minimization could be used to learn $P^\\star$ in polynomial time for this setting of long-context linear system identification and the implications of non-isotropic data when updating $P$. \n\n**Minor**: The abbreviation for Ordinary Least Squares (OLS) is used early but is only formally defined in Section 3.2.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Clarity of exposition:** The paper is well-written and well-organized and systematically introduces the problem setting, contributions, and theoretical derivations. Definitions and assumptions are clearly stated, and the logical progression through each theoretical component makes the paper easy to follow.\n\n**Intuitive and well-discussed results:** The concept of \"learning-without-mixing\" is well-motivated by the authors. This result aligns with the literature on \"learning-without-mixing\" for linear system. In particular, the authors show that for long-context linear system identification, where long contexts naturally entails a strong sample dependency, it does not necessarily inflate the bounds. Moreover, the low-rank representation learning setting and misspecification scenarios are well-explained, with clear justifications for how each condition affects the error bounds.\n\n**Theoretical contribution:** The theoretical contributions are significant, providing error bounds that extend classical linear system identification results to long-context models, and the learning rates aligns with the literature of learning-without-mixing for linear systems.", "weaknesses": "**Misspecification Results and Assumptions:** Section 3.4, particularly Assumption 3.9, imposes a constraint on the misspecified model that may be too restrictive for practical applications. The requirement that $|| (MA^\\star - MA^\\star_{1:p'})L^\\star ||_{\\text{op}} \\leq D'$ implies that misspecification must remain controlled to a certain degree. The authors could discuss the limitations of Assumption 3.9 if this assumption does not hold in practical settings or offer heuristics for relaxing this constraint.", "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": "", "extra_scores": {}}, {"review_id": "3RiAjHBCxE", "reviewer": "Reviewer_Mair", "summary": "The paper considers the linear system identification problem under a long context framework. More specifically, the paper presents:\n\n1. A main result on a theoretical guarantee of the constrained least squares estimator under mild assumptions on the design matrix and sub-gaussianity of noise. This result is shown to parallel previously existing results in the i.i.d. setting under some additional logarithmic factors.\n2. An extension of the main result to a low rank setting, showing an improved statistical rate depending on the rank constraint.\n3. A further extension of the main result to the case of misspecified context windows, suggesting partial learning occurs for misspecified models.", "questions": "Some minor questions and suggestions include:\n\n1. The first question is about the claim in line 379 that \"Importantly, the constant $C$ and the logarithmic terms are independent of the mixing related quantity $\\text{max}(1/1-\\rho,p).$ Here, $\\rho$ is the operator norm of $M_{\\textbf{A}^\\star}$\". However, as stated in line 263, the explicit constant $C(\\delta)$ depends on the diameter $D$ which is one of the constraints listed in Assumption 3.4 where it is assumed that the operator norm of $M_{\\textbf{A}^\\star}$ is less than or equal to $D$. These two statements seem to be contradictory. Can you elaborate on these dependencies?\n\n2. In Equation (14), the variable $E$ is not clearly defined in the main text although it is available in the appendix. It may be helpful to add it in the main text to prevent confusion.\n\n3. The last inequality in Equation (18) appears to be a typo.\n\n4. There are multiple typos in the appendix, and it would be helpful to do a careful revision of the text. For example, line 1184 formatting, line 1287 \"martices\", line 1378 \"rearrainging\", to name a few. \n\n5. Considering the main results depend strongly on the condition number of $L_\\star$, it would be helpful to include discussions about how this condition number typically behaves. For example, how does this condition number relate to the condition number or singular values of a matrix $A$ if $A_1^\\star = A_2^\\star = \\ldots = A$? How does it behave if $A_i^\\star$ have elements sampled i.i.d. from normal distributions? Does the condition number of $L_\\star$ also depend on $T$? \n\n6. While in Equation (8) it is stated that the result depends on polylog$(\\kappa)$, can you elaborate on whether this result depends on $\\log (\\kappa)$, or is it actually dependent on O($\\kappa$) or other polynomials of $\\kappa$? It is not immediately obvious from the proof, however, in many contexts theoretical guarantees of estimators are linearly related to logs of condition numbers. Since $\\kappa$ is already the log of the condition number, I think it makes sense to clarify this dependency.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "While the topic of linear identification is certainly not new, the theoretical results developed in this paper are novel. The authors clearly stated problem formulations, main results and motivations. Overall, the paper was well written with an enjoyable read.", "weaknesses": "There are several minor questions and suggestions regarding confusions in the main text (these are deferred to the questions section below). Experiments were minimal and only provided in the appendix.", "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": "", "extra_scores": {}}, {"review_id": "1hAOEJIYBs", "reviewer": "Reviewer_tdsH", "summary": "The article focusses on the problem of identifying the $A_k$ matrices for $k=1,\\ldots,p$ where $p$ is the context length when the data is being generated via\n\n$$ x_t=\\sum_{k=1}^p A_k^* x_{t-k}+\\xi_t $$\n\nwhere $A_1^*,\\ldots,A^*_p$ are $d\\times d$ matrices and $\\xi_t$ is i.id. noise. The article discusses three problems \n\n$(1)$ Minimizing the empirical loss function under an induced-norm bound on the $A^*$ matrices where the loss function is given by\n\n$$\\ell({\\bf A})=\\frac{1}{NT}\\sum_{n=1}^N\\sum_{t=p}^T\\left\\| x_t^{(n)}-\\sum_{k=1}^p A_k x_{t-k}^{(n)}\\right\\|.$$\n\nHere, $T$ is the length of the trajectory and $N$ trajectories are collected.\n\n$(2)$ Minimizing the empiricial loss function with induced-norm constraints on the $A_k$ with an added rank constraint on $A_k$\n\n$(3)$ The same loss function is minimized with an induced norm contraints on $A_k$ matrices and a bound that captures a context length $p'$ which is smaller than the actual context length $p.$\n\nFor all the three problems above the article provides non-asymptotic bounds on the Frobenius norm of the error of the estimates with respect to $A_k^*$  that will result from an optimal solution to the problems (1), (2) and (3). The authors provide a discussion that why standard approaches of lifting the state will face challenges, and provide reasons on why the bounds they have obtained are independent of the time taken by the Markov Chain to reach any steady state distribution. The authors further comment on stability conditions.", "questions": "(1) The authors discuss how their results do not depend on the mixing time of the Markov Chains involved. The authors can provide better intuition on how they need not consider mixing time in the non-asymptotic bounds obtained.\n\n(2) Can the authors provide more details on the simulations reported. The problems being considered do not  admit closed-form solutions and include non-convex problems and thus should be difficult to solve. How are these challenges reflected in the simulations section.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results provide non-asymptotic bounds on three problems that are well motivated; earlier works have not covered the case where the process has dependency on the past with a context length.", "weaknesses": "(1) The non-asymptotic bounds are not with respect to any specific algorithm that takes data and solves the related optimization problems. The authors indicate possible approaches for solving these problems but do not analyze any specific algorithm; however, it stands to reason that the sample complexity will depend on the approach being taken. The rank constrained problem is a particularly challenging one as its not a convex problem.  The authors assume a an optimal solution to the problems. The authors need to comment on whether advances with respect to other works are also in the same spirit or if they analyze known solutions to the optimization problems. Proper justification of the utility of the results need to be provided if the article provides analysis assuming the existence of the optimal solution.\n\n(2) The mathematics is presented in a dense manner; here the approach and the problem description can be better presented  and explained.  In the Sketch of the Proof, some of the matrices such as $E$ are not defined in the main body (its defined in the Appendix; however, the main body should be self-contained; the definitions are buried deep in the Appendix). Some suggestions are to show the matrix operations in more detail to help a reader along.", "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": "", "extra_scores": {}}, {"review_id": "9rKXP9hWal", "reviewer": "Reviewer_o3yE", "summary": "The paper provides a low rank approach for long-context linear system identification.", "questions": "How do you select the proper rank when it's not known?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper provides a low rank approach for long-context linear system identification.", "weaknesses": "It's unclear how to tune the rank when we don't know it's true value (e.g. real dataset).", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)