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 this paper, we study the global system operator—the operator that maps noise vectors to output—and obtain estimates on its spectrum. These results lead to 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, providing the first explicit geometric parameter of the data that can be used to bound estimation errors. Our results hold for arbitrary sub-Gaussian distributions of noise terms, and we evaluate the approach on synthetic and real-world benchmarks.
Introduction
In time-series forecasting, the relationship between inputs and outputs is rarely static. Whether tracking electricity demand across seasons or predicting volatile stock prices, the underlying parameters often drift over time. This is formally modeled as dynamic linear regression. While the Kalman Filter is the standard tool for managing such drift, its optimal performance requires precise knowledge of the process noise variance ($\sigma^2$) and observation noise variance ($\eta^2$).
Estimating these variances from finite data is a significant challenge. Traditional methods like Maximum Likelihood Estimation (MLE) are often non-convex "black boxes" that lack finite-sample guarantees. A recent paper from researchers at the Technion, presented at NeurIPS 2022, introduces the Spectrum Thresholding Variance Estimator (STVE), providing a mathematically rigorous foundation for learning these parameters with explicit convergence rates.
Problem Formulation
In dynamic regression, the regressor $\beta$ evolves at each time step. The system is defined by:
- State Equation: $X_{t+1} = X_t + h_t$, where $h_t$ is process noise with variance $\sigma^2$.
- Observation Equation: $Y_t = \langle X_t, u_t \rangle + z_t$, where $z_t$ is observation noise with variance $\eta^2$.
The objective is to estimate $\sigma^2$ and $\eta^2$ from the observed outputs $Y_t$ and inputs $u_t$. Unlike previous work that focused on asymptotic behavior, this research addresses the fundamental question: How much data is needed for a reliable estimate, and which data characteristics influence the learning rate?
The Spectrum Thresholding Variance Estimator (STVE)
The STVE approach treats the observation history as a single high-dimensional system. The authors identify a deep connection between the system's structure and the discrete Laplacian operator, allowing them to utilize well-known spectral properties to understand the system.
A key challenge is that raw data often has a peaked spectrum, which can lead to unstable estimation. STVE employs spectrum flattening via a Moore-Penrose pseudo-inverse. By creating two versions of this flattened operator—one full and one truncated (thresholded)—the algorithm generates a system of linear equations that separates the process noise from the observation noise.
Theoretical Guarantees and Empirical Results
The paper establishes several key theoretical and practical results:
- Finite Sample Complexity: The authors prove that the estimation error for both variances scales as $O(1/\sqrt{T})$. This provides a clear guarantee: quadrupling the sample size halves the error.
- Geometric Data Parameters: The convergence rate is shown to depend on the "shape" of the spectrum of the observation operator. This identifies the first explicit geometric parameter of the data that dictates estimation error.
- Robustness to Noise Distributions: While standard Kalman Filter theory often assumes Gaussian noise, STVE is proven to work for any sub-Gaussian distribution, making it highly applicable to real-world data with outliers or non-standard distributions.
Empirically, STVE was evaluated on synthetic data and the GEFCom 2012 Electricity Consumption dataset. On the real-world task of predicting electricity load based on temperature, STVE performed competitively with MLE. Notably, while MLE requires complex numerical optimization, STVE is a direct spectral calculation, offering greater reliability in non-stationary environments.
Conclusion
STVE provides the first variance estimator for dynamic regression with finite sample complexity guarantees. By connecting system dynamics to spectral theory, it offers a principled way to tune Kalman Filters. Future research will explore extending these bounds to more complex state transition matrices beyond the identity and to optimize the computational efficiency of the spectral decompositions for large-scale applications.
Summary updated