Sparse Regression with $\ell_0$ Constraints for $\alpha$-Mixing Time Series: Algorithms and Guarantees

Exact sparse methods based on $\ell_0$ constraints are increasingly used for interpretable and scalable time series modeling, where one aims to recover a small set of informative lags/factors while maintaining strong predictive performance and low computational cost. Despite their empirical success, finite-sample and computational guarantees for such methods under temporal dependence remain limited. In this paper, we study $\ell_0$-constrained least squares for time series generated by $\alpha$-mixing stationary Gaussian processes with sparse coefficients. We establish high-probability restricted strong convexity/smoothness (RSC/RSS) for the empirical quadratic loss. Leveraging these conditions, we derive nonasymptotic statistical guarantees and computational complexities for a series of exact sparse methods, including iterative hard thresholding (IHT). We apply our theoretical results to Gaussian vector autoregressive (VAR) models and obtain new guarantees. Experiments on synthetic sparse VAR models and real-world mobility time series demonstrate that exact sparse methods recover lag structure more accurately and interpretably than some classical methods, while achieving comparable prediction error with substantially lower computational cost.

Many important datasets are collected over time, such as traffic volume, energy use, sales, and ridesharing demand. To understand and predict such data, it is often useful to know which past time points are most informative. For example, today’s travel demand may depend mainly on the previous hour, the same hour yesterday, or the same hour last week. A model that uses only a small number of such past signals is easier to interpret and can be faster to fit. This paper studies methods that directly search for a small set of useful past signals when modeling time series data. We provide mathematical guarantees showing when these methods can recover the important signals reliably, even though observations collected over time are naturally dependent on one another. We also test the methods on simulated data and real ridesharing data. The results show that these sparse methods can predict about as well as common alternatives, while running faster and producing simpler models whose selected time lags better match meaningful daily and weekly patterns.