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

arXiv:2610.00637v1 Announce Type: new Abstract: 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 widetilde{O}(r^{1/2}T^{-1/2+1/p}) under bounded pth moment for p > 2, where T is the number of samples, r is the noise dimension, and widetilde{O}(dot) 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.

Related

• High-Probability Guarantees for SGD under eta-Heavy-Tailed Gradient Noise
• Learning Asymptotics with Convergence-Rate Guarantees using Linear Least Squares
• Learning switched non-linear dynamical systems from a single trajectory
• Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise

Source: arXiv cs.LG | 2026-10-02