Finite Sample Analysis Of Dynamic Regression Parameter Learning

Mark Kozdoba, Edward Moroshko, Shie Mannor, Koby Crammer

Introduction

Dynamic linear regression is a cornerstone of time-series forecasting, used to model systems where the relationship between inputs and outputs evolves over time. While tools like the Kalman Filter provide an optimal way to track these changes given known noise parameters, estimating those parameters—specifically the process noise variance ($\sigma^2$) and observation noise variance ($\eta^2$)—has historically lacked rigorous finite-sample guarantees. Most existing methods rely on asymptotic results, leaving practitioners in the dark about how much data is actually required for reliable estimation.

In this work, we present the first finite-sample analysis for dynamic regression parameter learning. We introduce the Spectrum Thresholding Variance Estimator (STVE) and prove that its estimation error decays at a rate of $1/\sqrt{T}$, where $T$ is the number of observations.

The Challenge of Non-Stationarity

In a dynamic linear regression model, the state $X_t$ evolves as a random walk, and observations $Y_t$ are linear projections:

  1. State evolution: $X_{t+1} = X_t + h_t$, where $h_t$ is process noise with variance $\sigma^2$.
  2. Observation: $Y_t = \langle X_t, u_t \rangle + z_t$, where $z_t$ is observation noise with variance $\eta^2$.

The difficulty arises because the observation vectors $u_t$ change over time, making the system non-stationary. Traditional Maximum Likelihood Estimation (MLE) lacks explicit convergence rates in this setting. Our approach overcomes this by analyzing the "global system operator" that maps the sequence of noise terms to the sequence of observations.

The STVE Approach: Spectral Analysis

The core innovation of STVE is treating the entire observation sequence as a single operator equation. We discovered a fundamental link between this system operator and the discrete Laplacian operator. By performing a Singular Value Decomposition (SVD) on the system operator, we can analyze the spectral properties of the data.

Spectral decay of the system operator and the thresholding point $p=T/4$.

As shown in the figure above, the spectrum of the operator typically exhibits a sharp decay. STVE leverages this by "flattening" the spectrum using a pseudo-inverse and then truncating it at a specific threshold $p$ (e.g., $p=T/4$). This truncation allows us to separate the signal from the noise components effectively. By comparing the energy of the signal across different spectral bands, we derive linear equations that can be solved to estimate $\sigma^2$ and $\eta^2$ simultaneously.

Theoretical Guarantees and Empirical Results

Our main theoretical result establishes that for any sub-Gaussian noise distribution, the estimation error for both variances is bounded by $O(B/\sqrt{T})$. Here, $B$ is a geometric parameter determined by the diversity of the input sequence $u_t$. This provides the first explicit link between data geometry and convergence rates in dynamic regression.

We validated STVE on both synthetic and real-world datasets:

  • Synthetic Benchmarks: Simulations confirmed the predicted $1/\sqrt{T}$ convergence rate across various noise levels.
  • Electricity Consumption: Using data from the Global Energy Forecasting Competition, we demonstrated that STVE performs comparably to MLE while offering superior robustness to missing data. Both adaptive methods significantly outperformed stationary regression models, highlighting the importance of tracking state drift.

Conclusion

By shifting the perspective from time-domain filtering to spectral-domain operator analysis, we provide the first finite-sample guarantees for learning noise parameters in dynamic regression. While currently focused on random walk dynamics, this spectral framework offers a promising path toward understanding more complex and non-linear dynamical systems in finite time.

Summary updated

Abstract

We consider the dynamic linear regression problem, where the predictor vector may vary with time. This problem can be modeled as a linear dynamical system, with non-constant observation operator, where the parameters that need to be learned are the variance of both the process noise and the observation noise. While variance estimation for dynamic regression is a natural problem, with a variety of applications, existing approaches to this problem either lack guarantees altogether, or only have asymptotic guarantees without explicit rates. In particular, existing literature does not provide any clues to the following fundamental question: In terms of data characteristics, what does the convergence rate depend on? In this paper we study the global system operator -- the operator that maps the noise vectors to the output. We obtain estimates on its spectrum, and as a result derive the first known variance estimators with finite sample complexity guarantees. The proposed bounds depend on the shape of a certain spectrum related to the system operator, and thus provide the first known explicit geometric parameter of the data that can be used to bound estimation errors. In addition, the results hold for arbitrary sub Gaussian distributions of noise terms. We evaluate the approach on synthetic and real-world benchmarks.
BibTeX
@inproceedings{kozdoba2022finite,
  author = {Mark Kozdoba and Edward Moroshko and Shie Mannor and Koby Crammer},
  title = {{Finite Sample Analysis Of Dynamic Regression Parameter Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=tJBYkwVDv5},
}
Figure