Finite Sample Deviation and Variance Bounds for First Order Autoregressive Processes

Rodrigo A. González, Cristian R. Rojas

TL;DR

This paper provides rigorous, non-asymptotic upper bounds on the deviation probability and variance of the least squares estimator for first-order autoregressive (AR(1)) processes. By leveraging decoupling theory, the authors deliver formulas that work for both stable and unstable systems, showing that while stable systems exhibit standard linear variance decay, unstable systems actually see their estimation variance drop exponentially as more data arrives.

What Problem Does This Paper Address?

In fields like control theory, signal processing, and econometrics, we frequently use the Least Squares (LS) method to identify the parameters of a system. For a simple AR(1) process—where the current value depends on the previous value plus some noise—we have a wealth of "asymptotic" theory. This theory tells us how the estimator behaves as the number of samples ($N$) approaches infinity.

However, in the real world, we never have infinite data. We have "finite samples." The gap in the literature is that most existing finite-sample bounds are either too conservative (meaning they over-estimate the error by a huge margin) or they fail to account for the specific stability of the system. This paper aims to provide "problem-dependent" bounds that accurately reflect how the estimator performs for specific parameter values, even when data is scarce.

Methods

The authors employ a sophisticated mathematical toolkit to tackle the dependency inherent in time-series data:

  • Decoupling Theory: This is the core innovation. Usually, the variables in an AR process are intertwined over time, making them hard to analyze. Decoupling theory allows the researchers to compare these dependent sequences to sequences of independent variables, making it possible to apply powerful concentration inequalities.
  • Chernoff’s Inequality: Used to transform the probability of a large deviation into an optimization problem involving moment-generating functions.
  • Toeplitz Matrix Analysis: The covariance of an AR(1) process has a specific "Toeplitz" structure. The authors use properties of these matrices (and their determinants) to find closed-form expressions for their bounds.
  • Szegő’s Formula: In the stable case, this classical result from spectral theory helps evaluate the integrals needed to define the variance bounds.

Datasets

The paper does not use empirical real-world datasets. Instead, it relies on synthetic data generated via Monte Carlo simulations.

  • The authors ran $5 \times 10^5$ simulations for various pole values ($a_0 = 0.5, 0.98, 1.01, 1.1$) and sample sizes ($N$ from 2 to 1000).
  • These simulations serve as the ground truth to validate that their theoretical upper bounds "track" the actual behavior of the estimator.

Key Insights and Ideas

  • Unstable Systems are "Easier" to Learn: One of the most striking insights is that unstable systems ($|a_0| > 1$) actually allow for much faster parameter identification. Because the signal grows exponentially, the signal-to-noise ratio improves rapidly, causing the estimation variance to decay exponentially ($|a_0|^{-2N}$) rather than linearly ($1/N$).
  • Stability Margins Matter: The bounds explicitly include the parameter $a_0$. This shows that as a system approaches the "edge" of stability ($a_0 \approx 1$), the estimation becomes more difficult, a phenomenon captured by the "problem-dependent" nature of their formulas.
  • Rate-Optimality: For stable systems, the authors' variance bound matches the structure of the well-known asymptotic Cramer-Rao lower bound. This suggests their finite-sample approach isn't just a loose guess—it captures the fundamental physics of the estimation process.

Key Results

  • Deviation Bounds: The paper provides a specific formula (Theorem 1 and 2) for the probability that the estimate $\hat{a}_N$ deviates from the true value $a_0$ by more than $\epsilon$.
  • Variance Bounds: For stable systems, they prove the variance is bounded by roughly $8/(N-6)$. For unstable systems, the bound includes a factor of $|a_0|^{-2N}$, confirming exponential convergence.
  • Validation: Simulation plots (Figures 1 and 2) demonstrate that the theoretical bounds qualitatively match the empirical curves. While the bounds are (by definition) higher than the actual values, they capture the "shape" of the error perfectly across different regimes.

Limitations and Future Work

  • Scalar Limitation: The current work is strictly for AR(1) processes (single-parameter scalar systems). Most real-world engineering systems are higher-order (ARX, ARMAX) or vector-valued.
  • Gaussian Assumption: The proofs rely on the noise being Gaussian. While common, many real-world signals have "heavy tails" or non-symmetric noise distributions.
  • Future Directions: The authors suggest extending these results to sub-Gaussian noise (a broader class of distributions) and applying the decoupling framework to more complex, multi-parameter system identification models.

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},
}

Loading related content...

Figure