Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

We establish non-asymptotic sample complexity bounds for the least-squares estimation of vector autoregressive models for exponentially stable systems with heavy-tailed noise based on a single observed trajectory. By assuming i.i.d. noise, bounded noise covariance, and persistent excitation, we show that the estimation error is $\tilde{\mathcal{O}}(r^{1\mathrm{/}2}{T}^{-1\mathrm{/}2+1\mathrm{/}p})$ under bounded $p$th moment for $p>2$, where $T$ is the number of samples, $r$ is the noise dimension, and $\tilde{\mathcal{O}}(\cdot )$ hides logarithmic terms. We also introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions and showcase this by deriving error bounds for sub-exponential and sub-Gaussian noise distributions. Finally, we specialize our analysis to autoregressive models with exogenous inputs and show that the dimension factor of the error bound is independent of the model order.