# Learning from many trajectories

arXiv: https://arxiv.org/abs/2203.17193 · HTML: https://mlsanity.com/paper/2203.17193/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2022.

## Built on by (most cited first, 24 of 24)

- [Statistical Learning Theory for Control: A Finite Sample Perspective](https://mlsanity.com/paper/2209.05423/) (2022)
- [Learning with little mixing](https://mlsanity.com/paper/2206.08269/) (2022)
- [A Tutorial on the Non-Asymptotic Theory of System Identification](https://mlsanity.com/paper/2309.03873/) (2023)
- [Sample-Efficient Linear Representation Learning from Non-IID Non-Isotropic Data](https://mlsanity.com/paper/2308.04428/) (2023)
- [On the Performance of Empirical Risk Minimization with Smoothed Data](https://mlsanity.com/paper/2402.14987/) (2024)
- [Learning Dynamical Systems by Leveraging Data from Similar Systems](https://mlsanity.com/paper/2302.04344/) (2023)
- [Outlier-Robust Linear System Identification Under Heavy-tailed Noise](https://mlsanity.com/paper/2501.00421/) (2024)
- [Combining Federated Learning and Control: A Survey](https://mlsanity.com/paper/2407.11069/) (2024)
- [Long-Context Linear System Identification](https://mlsanity.com/paper/2410.05690/) (2024)
- [Adaptive Symmetry Discovery for Dynamical System Identification](https://mlsanity.com/paper/2608.08091/) (2026)
- [Length independent generalization bounds for deep SSM architectures via Rademacher contraction and stability constraints](https://mlsanity.com/paper/2405.20278/) (2024)
- [Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples](https://mlsanity.com/paper/2410.11227/) (2024)
- [Nonconvex Linear System Identification with Minimal State Representation](https://mlsanity.com/paper/2504.18791/) (2025)
- [A note on the smallest eigenvalue of the empirical covariance of causal Gaussian processes](https://mlsanity.com/paper/2212.09508/) (2022)
- [Finite Sample Frequency Domain Identification](https://mlsanity.com/paper/2404.01100/) (2024)
- [Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights](https://mlsanity.com/paper/2604.17578/) (2026)
- [How Much Memory Do We Need? Adaptive Memory Gate for Neural Operators](https://mlsanity.com/paper/2606.13443/) (2026)
- [Learning Dynamic Bayesian Networks from Data: Foundations, First Principles and Numerical Comparisons](https://mlsanity.com/paper/2406.17585/) (2024)
- [Stability properties of gradient flow dynamics for the symmetric low-rank matrix factorization problem](https://mlsanity.com/paper/2411.15972/) (2024)
- [Boosting-Enabled Robust System Identification of Partially Observed LTI Systems Under Heavy-Tailed Noise](https://mlsanity.com/paper/2504.18444/) (2025)
- [Frequency Response Identification of Low-Order Systems: Finite-Sample Analysis](https://mlsanity.com/paper/2508.17142/) (2025)
- [CLT-Optimal Parameter Error Bounds for Linear System Identification](https://mlsanity.com/paper/2604.21270/) (2026)
- [Nearest-Neighbor Radii under Dependent Sampling](https://mlsanity.com/paper/2605.14343/) (2026)
- [Linear RNN Scaling Laws: When Longer Sequences Beat More Sequences](https://mlsanity.com/paper/2609.27964/) (2026)

## Abstract (arXiv)

We initiate a study of supervised learning from many independent sequences ("trajectories") of non-independent covariates, reflecting tasks in sequence modeling, control, and reinforcement learning. Conceptually, our multi-trajectory setup sits between two traditional settings in statistical learning theory: learning from independent examples and learning from a single auto-correlated sequence. Our conditions for efficient learning generalize the former setting--trajectories must be non-degenerate in ways that extend standard requirements for independent examples. Notably, we do not require that trajectories be ergodic, long, nor strictly stable. For linear least-squares regression, given n-dimensional examples produced by m trajectories, each of length T, we observe a notable change in statistical efficiency as the number of trajectories increases from a few (namely m lesssim n) to many (namely m gtrsim n). Specifically, we establish that the worst-case error rate of this problem is Theta(n / m T) whenever m gtrsim n. Meanwhile, when m lesssim n, we establish a (sharp) lower bound of Omega(n2 / m2 T) on the worst-case error rate, realized by a simple, marginally unstable linear dynamical system. A key upshot is that, in domains where trajectories regularly reset, the error rate eventually behaves as if all of the examples were independent, drawn from their marginals. As a corollary of our analysis, we also improve guarantees for the linear system identification problem.