Long-Context Linear System Identification

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

$x_t=\sum_{k=1}^p A_k^* x_{t-k}+\xi_t$

where $A_1^*,\ldots,A^*_p$ are $d\times d$ matrices and $\xi_t$ is i.id. noise. The article discusses three problems

$(1)$ Minimizing the empirical loss function under an induced-norm bound on the $A^*$ matrices where the loss function is given by

$\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\|.$

Here, $T$ is the length of the trajectory and $N$ trajectories are collected.

$(2)$ Minimizing the empiricial loss function with induced-norm constraints on the $A_k$ with an added rank constraint on $A_k$

$(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.$

For 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.

The paper provides a low rank approach for long-context linear system identification.

The paper considers the linear system identification problem under a long context framework. More specifically, the paper presents:

1. 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.
2. An extension of the main result to a low rank setting, showing an improved statistical rate depending on the rank constraint.
3. A further extension of the main result to the case of misspecified context windows, suggesting partial learning occurs for misspecified models.

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 $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.

This paper addresses the problem of linear system identification within a long-context framework. Specifically, it makes the following contributions:

1. Theoretical Guarantee for the Constrained Least Squares Estimator: Under mild assumptions on the design matrix and sub-Gaussian noise, the paper establishes a theoretical guarantee for the constrained least squares estimator. This result parallels existing results in the i.i.d. setting, with an additional logarithmic factor.
2. Extension to the Low-Rank Setting: The main result is extended to a low-rank setting, demonstrating an improved statistical rate that depends on the rank constraint.
3. Misspecified Context Windows: The analysis is further extended to the case of misspecified context windows, revealing that partial learning still occurs under model misspecification.

Most of the reviewers believe that the paper makes substantial contributions, and the AC also agrees with this assessment.

Accept (Poster)