Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes

Rodrigo A. González, Cristian R. Rojas

Abstract

In this paper, we study finite-sample properties of the least squares estimator in first order autoregressive processes. By leveraging a result from decoupling theory, we derive upper bounds on the probability that the estimate deviates by at least a positive $\varepsilon$ from its true value. Our results consider both stable and unstable processes. Afterwards, we obtain problem-dependent non-asymptotic bounds on the variance of this estimator, valid for sample sizes greater than or equal to seven. Via simulations we analyze the conservatism of our bounds, and show that they reliably capture the true behavior of the quantities of interest.

Introduction

In fields like control theory, signal processing, and econometrics, the Least Squares (LS) method is a standard tool for identifying system parameters. For a simple first-order autoregressive (AR(1)) process, asymptotic theory provides a clear picture of estimator behavior as the sample size $N$ approaches infinity. However, real-world applications often operate with finite data, where asymptotic guarantees may not hold. This research addresses the gap by providing rigorous, non-asymptotic upper bounds on the deviation probability and variance of the LS estimator for both stable and unstable AR(1) systems.

Methodology

The core challenge in analyzing time-series data is the inherent dependency between variables over time. To overcome this, the authors utilize Decoupling Theory, which allows for the comparison of dependent sequences to sequences of independent variables. This framework enables the application of powerful concentration inequalities, such as Chernoff’s Inequality, to transform deviation probabilities into manageable optimization problems. Additionally, the specific "Toeplitz" structure of AR(1) covariance matrices and Szegő’s Formula are employed to derive closed-form expressions for variance bounds in the stable regime.

Deviation and Variance Analysis

The paper provides specific formulas (Theorems 1 and 2) for the probability that the estimate $\hat{a}_N$ deviates from the true value $a_0$ by more than $\epsilon$. These bounds are "problem-dependent," meaning they explicitly incorporate the parameter $a_0$, capturing how estimation difficulty increases as a system approaches the edge of stability ($a_0 \approx 1$).

Empirical deviation probability vs. theoretical upper bounds for various stability parameters.

A key insight of this work is the distinction between stable ($|a_0| < 1$) and unstable ($|a_0| > 1$) systems. While stable systems exhibit standard linear variance decay ($1/N$), unstable systems allow for much faster parameter identification. In the unstable case, the signal grows exponentially, improving the signal-to-noise ratio rapidly and causing the estimation variance to decay exponentially ($|a_0|^{-2N}$).

Variance of the LS estimator for stable (left) and unstable (right) AR(1) processes.

Key Results and Validation

Through Monte Carlo simulations ($5 \times 10^5$ runs), the authors validated that their theoretical upper bounds effectively "track" the empirical behavior of the estimator.

  • Stable Systems: The variance bound matches the structure of the asymptotic Cramer-Rao lower bound, proving the finite-sample approach captures the fundamental physics of the process.
  • Unstable Systems: Simulations confirm the predicted exponential convergence, showing that unstable systems are, paradoxically, "easier" to learn with limited data.
  • Qualitative Accuracy: While the bounds are inherently conservative (higher than actual values), they perfectly capture the "shape" of the error across different regimes and sample sizes.

Conclusion and Future Work

This work provides a robust framework for understanding LS estimator performance without relying on infinite-sample assumptions. While currently limited to scalar AR(1) processes with Gaussian noise, the decoupling framework offers a path forward for analyzing more complex, multi-parameter systems (like ARX or ARMAX models) and broader noise distributions, such as sub-Gaussian noise.

Summary updated

Abstract

In this paper, we study finite-sample properties of the least squares estimator in first order autoregressive processes. By leveraging a result from decoupling theory, we derive upper bounds on the probability that the estimate deviates by at least a positive $\varepsilon$ from its true value. Our results consider both stable and unstable processes. Afterwards, we obtain problem-dependent non-asymptotic bounds on the variance of this estimator, valid for sample sizes greater than or equal to seven. Via simulations we analyze the conservatism of our bounds, and show that they reliably capture the true behavior of the quantities of interest.
BibTeX
@inproceedings{gonzalez2020finite,
  author = {Rodrigo A. González and Cristian R. Rojas},
  title = {{Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2020},
  doi = {10.1109/icassp40776.2020.9053095},
}
Figure