Research map / Architectures and efficiency / Attention and transformers

Long-Context Linear System Identification

ICLR 2025 · Architectures and efficiency › Attention and transformers · approach: State space and recurrent sequence models · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Derives non-asymptotic sample-complexity bounds for ordinary/constrained least squares estimation of long-context (order-p) linear autoregressive models, matching the i.i.d. parametric rate up to logs ("learning-without-mixing"), with extensions to low-rank and misspecified context length.

Problem

Estimating the matrices of a p-th order linear autoregressive (long-context linear dynamical) system from trajectories, where prior non-asymptotic rates only covered order-1 dependence and typically degraded with mixing time.

Approach

Uses a uniform concentration argument over prediction differences (martingale/Freedman-based, with operator-norm-constrained estimator) to obtain Frobenius-norm rates D^2 pd^2/(N(T-p)) that do not depend on mixing time, extend to rank-r matrices (prd rate) and to misspecified context lengths p' < p.

Key results

• Frobenius-norm error bound of order D^2 pd^2/(N(T-p)) up to polylog factors for the constrained least squares estimator, matching the i.i.d. parametric rate (learning-without-mixing).
• Low-rank setting improves the bound to order prd/(N(T-p)) for rank-r design matrices.
• Under misspecification with p' < p in strictly stable systems, the error scales with p'dr/(N(T-p)) instead of depending on the true p.

Surprising findings

• Learning does not degrade as spectral radius approaches 1, in contrast to mixing-time-based rates; the rate improves for marginally stable systems in prior p=1 work.

Limitations

• Nuclear-norm low-rank estimator analysis left for future work; the rank-constrained estimator is not polynomial-time computable.
• Misspecification results require a strong assumption on L_star regardless of T and apply mainly to strictly stable systems.
• Requires knowledge of the bound D on the operator norm of M_A and the diameter constraint, though it can be removed under an extra assumption NT large.

Experimental setup

Datasets: synthetic linear autoregressive trajectories

Metrics: squared Frobenius norm estimation error

Baselines: ordinary least squares naive learning-with-mixing estimator

Builds on: Simchowitz et al. 2018 learning without mixing Sarkar and Rakhlin non-asymptotic linear system identification Freedman inequality Hanson-Wright inequality

Closest papers by meaning

• Learning Low-dimensional Latent Dynamics from High-dimensional Observations: Non-asymptotics and Lower Bounds (ICML 2024 · similarity 0.84)
• Self-supervised contrastive learning performs non-linear system identification (ICLR 2025 · similarity 0.83)
• Understanding and Improving Length Generalization in Recurrent Models (ICML 2025 · similarity 0.83)
• Improved Scaling Laws in Linear Regression via Data Reuse (NeurIPS 2025 · similarity 0.83)
• In-context Learning of Linear Dynamical Systems with Transformers: Approximation Bounds and Depth-separation (NeurIPS 2025 · similarity 0.83)
• Identifying latent state transitions in non-linear dynamical systems (ICLR 2025 · similarity 0.83)