A direct estimation of high dimensional stationary vector autoregressions

Fang Han, Huanran Lu, Han LiuJMLR 2015

TL;DR

This paper introduces a novel linear programming approach for estimating high-dimensional vector autoregressive (VAR) models. This method offers computational advantages through parallelization and relaxes the strict sparsity assumptions often required by existing lasso-based techniques, allowing for "weakly sparse" models.

What Problem Does This Paper Address?

Vector autoregressive (VAR) models are powerful tools for analyzing multivariate time series data across various fields like finance and neuroscience. However, estimating these models in high dimensions presents significant challenges. The number of parameters in a VAR model grows rapidly with the number of time series (dimension, d) and the autoregressive order (p). When this dimensionality (dp) exceeds the number of observations (T), standard estimation methods like least squares become ill-posed. Existing approaches often rely on adding penalty terms (e.g., lasso) to enforce sparsity, assuming that many coefficients are exactly zero. This paper addresses the limitations of these methods by proposing a new approach that is computationally efficient and requires weaker assumptions on the sparsity of the model.

Methods

The core innovation of this paper is the formulation of the VAR parameter estimation problem as a linear program. Instead of directly penalizing the least squares loss, the authors exploit the temporal dependence structure of VAR models and the Yule-Walker equations to transform the problem. They introduce a new objective function that minimizes the sum of absolute values of the transition matrix elements, subject to a constraint that enforces the relationship between the estimated transition matrix and the sample autocovariance matrices. This formulation allows for efficient parallel computation by decomposing the problem into multiple subproblems. The authors also introduce a "weakly sparse" assumption, which is less restrictive than the exact sparsity required by many lasso-type estimators.

Datasets

The paper evaluates its method on both synthetic datasets and real-world equity data.

  • Synthetic Data: Transition matrices are generated with five different patterns: "band," "cluster," "hub," "random," and "scale-free." Covariance matrices are generated using both diagonal and Toeplitz forms.
  • Real Data: Daily closing prices for 91 stocks from the S&P 100 index between January 1, 2003, and January 1, 2008, are used. After filtering, 50 stocks with the highest marginal standard deviations are selected, resulting in a dataset of 1258 data points.

Key Insights and Ideas

  • Linear Programming for VAR: Reformulating VAR estimation as a linear program offers a computationally efficient alternative to penalized least squares, especially for high-dimensional problems.
  • Parallelization Advantage: The linear programming formulation naturally decomposes into independent subproblems, enabling significant speedups through parallel computing.
  • Weak Sparsity: The proposed method does not require strict sparsity (many exactly zero coefficients) and can handle "weakly sparse" models, making it more applicable to real-world scenarios where exact sparsity might not hold.
  • Spectral Norm Importance: The theoretical analysis highlights the crucial role of the spectral norm of the transition matrix (||A₁||₂) in determining estimation accuracy. A larger spectral norm implies more temporal dependence and potentially lower estimation accuracy.
  • No Irrepresentable Condition: Unlike lasso-based methods, the proposed approach does not require the "irrepresentable condition" for exact sign recovery, offering a theoretical advantage.

Key Results

The paper presents strong empirical and theoretical results:

  • Empirical Performance: Across various synthetic data settings (different matrix patterns, covariance structures, and lags), the proposed method consistently outperforms both ridge and lasso-based estimators in terms of estimation error across Frobenius, L₂, and L₁ norms. The improvement is particularly noticeable with increasing dimensionality.
  • Real Data Performance: On equity data, the proposed method achieves significantly lower prediction errors compared to lasso and ridge methods, especially when considering multiple lags.
  • Computational Efficiency: Figure 3 demonstrates that the proposed method's computation time decreases significantly with an increasing number of available cores, outperforming lasso when parallelized.
  • Theoretical Guarantees: The paper provides non-asymptotic rates of convergence for the estimator in both L₁ and Lmax norms, showing that the rates depend on the sparsity level and the spectral norm of the transition matrix. It also establishes sign recovery consistency and prediction accuracy bounds.

Limitations and Future Work

  • Stationarity Assumption: The current method is designed for stationary VAR processes. The authors acknowledge that handling unstable VAR models is an important area for future research.
  • Order Selection: While cross-validation is used for selecting the lag p and tuning parameter λ, the authors express interest in exploring whether the linear programming framework can be extended to directly determine the order of the VAR model.
  • Covariance Matrix Estimation: The paper primarily focuses on estimating transition matrices and does not delve deeply into estimating the covariance matrix (Σ) and noise covariance (Ψ). However, they suggest that their framework could be extended to these problems, potentially leveraging existing results for sparse covariance matrix estimation.

Summary updated

BibTeX
@article{han2015direct,
  author = {Fang Han and Huanran Lu and Han Liu},
  title = {{A direct estimation of high dimensional stationary vector autoregressions}},
  journal = {J. Mach. Learn. Res.},
  year = {2015},
}
Figure