Subsampling Algorithms for Irregularly Spaced Autoregressive Models

Jiaqi Liu, Ziyang Wang, HaiYing Wang, Nalini RavishankerAlgorithms 2024 · DOI

TL;DR

This paper introduces novel subsampling algorithms for analyzing irregularly spaced time series data, specifically for autoregressive models. These methods significantly reduce computational costs by analyzing smaller data subsets while maintaining high estimation accuracy, offering up to a 40x speedup over full-data estimation.

What Problem Does This Paper Address?

Traditional time series analysis methods often assume data points are collected at regular intervals. However, many real-world datasets, such as high-frequency financial transactions or astronomical observations, are inherently irregularly spaced. Analyzing these irregular time series with conventional statistical models can be computationally prohibitive, especially for large datasets. Existing subsampling techniques primarily focus on independent data, leaving a gap for dependent, time-series data. This paper addresses this by developing and evaluating subsampling strategies tailored for irregularly spaced autoregressive (IS-AR) models.

Methods

The authors propose three novel subsampling algorithms for IS-AR(1) models:

  • Optimal Subsampling under A-Optimality (opt): This method uses stochastic subsampling with probabilities designed to minimize the asymptotic mean squared error. It employs Poisson sampling (sampling without replacement) and incorporates a pilot estimate to determine subsampling probabilities. A mixing strategy is used to prevent probabilities from becoming too small.
  • Information-Based Optimal Subdata Selection (iboss): This is a deterministic approach that selects data points by maximizing the determinant of the Fisher information matrix. It identifies the subset of data that provides the most information about the model parameters.
  • Sequential Thinning (thin): Another deterministic method, "thin" is designed for streaming data. It makes online decisions about including data points based on their contribution to the information matrix, without needing simultaneous access to the entire dataset.

These methods are compared against a naive uniform subsampling approach and the full-data estimation method.

Datasets

The paper does not use real-world datasets for evaluation. Instead, it relies on extensive numerical simulations with synthetically generated irregularly spaced time series data. The parameters of the IS-AR(1) model (φ and σ) and the time gaps (dⱼ) are varied to test the performance of the proposed algorithms under different scenarios.

Key Insights and Ideas

  • Subsampling for Dependent Data is Crucial: The paper highlights that specialized subsampling techniques are necessary for dependent time series data, as standard methods for independent data may not be optimal.
  • Optimality Criteria Matter: Different optimality criteria (A-optimality vs. D-optimality) lead to varying performance characteristics, influencing how well parameters are estimated. A-optimality (used by opt) seems to perform better for estimating parameters with larger variances (like σ), while D-optimality (used by iboss and thin) is better for estimating parameters like φ.
  • Deterministic Methods Excel for Specific Parameters: iboss and thin show superior performance in estimating the autoregressive parameter (φ), especially when σ is small, suggesting their D-optimality focus is beneficial here.
  • Computational Efficiency is Significant: The proposed subsampling methods offer substantial reductions in computation time, making the analysis of large, irregularly spaced time series feasible.

Key Results

  • Estimation Efficiency: All three proposed subsampling methods (opt, iboss, thin) outperform uniform subsampling in terms of Mean Squared Error (MSE) across various parameter settings.
  • Speedup: The subsampling methods achieve significant computational speedups. For large datasets, opt and iboss can reduce computation time by a factor of approximately 40 compared to full-data estimation. thin also provides substantial savings, taking less than one-tenth of the time of full-data estimation.
  • Parameter-Specific Performance: opt generally shows the best overall performance, particularly when σ or φ is large. However, iboss and thin demonstrate higher estimation efficiency for φ, especially when σ is small. Conversely, opt outperforms iboss and thin when estimating σ, particularly when σ is large.
  • Subsample Size Impact: The benefits of subsampling are more pronounced with smaller subsample sizes (r). As r approaches the full data size (m), the performance differences between the methods diminish.

Limitations and Future Work

  • IS-AR(1) Focus: The current work is limited to the IS-AR(1) model. The authors suggest extending these techniques to more complex models, such as IS-AR(p) for p > 1, where optimal subsampling is expected to be even more effective.
  • Parameter Dependence: The performance of the methods can vary depending on the specific values of the model parameters (φ and σ).
  • Future Directions: The paper paves the way for further exploration of subsampling strategies in time series analysis, particularly for more complex autoregressive models.

Summary updated

BibTeX
@article{liu2024subsampling,
  author = {Jiaqi Liu and Ziyang Wang and HaiYing Wang and Nalini Ravishanker},
  title = {{Subsampling Algorithms for Irregularly Spaced Autoregressive Models}},
  journal = {Algorithms},
  year = {2024},
  doi = {10.3390/a17110524},
}
Figure