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 .
There has been remarkable progress over the past decade in establishing finite-sample, non-asymptotic bounds on recovering unknown system parameters from observed system behavior. Surprisingly, however, we show that the current state-of-the-art bounds do not accurately capture the statistical complexity of system identification, even in the most fundamental setting of estimating a discrete-time linear dynamical system (LDS) via ordinary least-squares regression (OLS). Specifically, we utilize asymptotic normality to identify classes of problem instances for which current bounds overstate the squared parameter error, in both spectral and Frobenius norm, by a factor of the state-dimension of the system. Informed by this discrepancy, we then sharpen the OLS parameter error bounds via a novel second-order decomposition of the parameter error, where crucially the lower-order term is a matrix-valued martingale that we show correctly captures the CLT scaling. From our analysis we obtain finite-sample bounds for both (i) stable systems and (ii) the many-trajectories setting that match the instance-specific optimal rates up to constant factors in Frobenius norm, and polylogarithmic state-dimension factors in spectral norm.
Yichen Zhou, Stephen Tu
Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California, USA.
This paper studies finite-sample set-membership identification for discrete-time bilinear systems under bounded symmetric log-concave disturbances. Our analysis considers trajectory-dependent regressors and allows marginally stable dynamics with polynomial mean-square state growth. We prove that the diameter of the feasible parameter set shrinks with sample complexity O(1/ε) where ε is the estimation error. Simulation supports the theory and illustrates the advantage of the proposed estimator for uncertainty quantification.
Hongyu Yi, Chenbei Lu, Jing Yu
Department of Electrical and Computer Engineering, University of Washington, Seattle, WA, USA. · Cornell University AI for Science Institute, Cornell University, Ithaca, NY, USA.
Auto-regressive models have emerged as powerful tools for sequential data, from language to video. Understanding how and why these models learn latent representations remains an open theoretical question. In this work, we demonstrate that when trained by empirical risk minimization on data from partially observed linear dynamical systems, two-layer linear auto-regressive models naturally learn to approximate Kalman filtering. In particular, we show that the learned hidden representation coincides, up to a similarity transformation, with the state estimates produced by the optimal (Kalman) filter, even though the model has no explicit knowledge of the underlying dynamics or state. The result follows from three main insights. First, we establish that the Kalman filter is well approximated by an auto-regressive model with bounded truncation error. Second, we show that despite non-convexity, the two-layer optimization landscape is benign, i.e., all stationary points are either strict saddles or global minima. Finally, as our main contributions, we provide finite-sample guarantees on prediction error, parameter estimation error, and latent state recovery. Numerical simulations support the theoretical results and demonstrate that the latent representations of auto-regressive models recover state estimates.
Yahya Sattar, Sunmook Choi, Leo Maynard-Zhang +3
Cornell · U Washington · Imperial College London +1