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 O(r1/2T−1/2+1/p) under bounded pth moment for p>2, where T is the number of samples, r is the noise dimension, and O(⋅) 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.
Figures & tables
Figure 1: Intuition behind empirical covariance decomposition using k blocking when k=3 .
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Figure 2: Log log plot of relative parameter estimate error for an ARX Model with OLS estimator of sample sizes T=[100,200,500,103,104,4×104,105,106,5×106] . The fitted slope for the 99 th, 95 th, and 90 th percentiles are shown in dashed lines, and the reference gray line has slope −1/2 .
Department of Electrical and Computer Engineering, University of Washington, Seattle, WA, USA. · Cornell University AI for Science Institute, Cornell University, Ithaca, NY, USA.