Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
17,913 characters · 4 sections · 14 citation commands
A restricted eigenvalue condition for unit-root non-stationary data
Modern time series applications frequently involve the analysis of high-dimensional datasets in which the number of time series $N$ is large in relation to, and may exceed, the number of temporal observations $T$. A rather successful approach to modelling such datasets has been to impose some form of sparsity on the underlying data generating process (DGP) and to incorporate $\ell_1$-based regularization such as the lasso to reduce model complexity and/or recover the true sparsity pattern Basu2015,Medeiros2016,Masini2019. However, these approaches heavily rely on stationarity of the considered time series, thereby either excluding the presence of stochastic trends or requiring correct identification and corrections of the order of integration. As noted by Smeekes2020a, a key difficulty that hinders extensions of the theory for lasso-type estimators to high-dimensional non-stationary settings is the absence of a verifiable restricted eigenvalue condition (REC). Accordingly, we aim to fill this gap in the literature by proposing an appropriately scaled REC for unit root non-stationary time series and verifying its validity directly on the gram matrix with the use of matrix concentration inequalities. This result is then used to derive novel finite sample error-bounds for the lasso and prove its asymptotic consistency on (ultra) high-dimensional (co)integrated datasets.
The behaviour of $\ell_1$-based regularization on stationary time series data is well-researched. Basu2015 and KockCallot2015 consider lasso based estimation of high-dimensional VAR processes driven by Gaussian innovations and derive tight error bounds for the prediction and estimation error. These bounds show that the estimation error deteriorates in the dimension at a logarithmic rate, thereby validating the lasso in (ultra) high-dimensional time series settings. Medeiros2016 consider the adaptive lasso and derive both estimation and selection consistency on weakly dependent and possibly heteroskedastic time series data without imposing Gaussianity on the predictors or innovations. By replacing the assumption of Gaussianity by a set of moment restrictions, they provide a considerable generalization to previous results, albeit at the cost of error bounds that deteriorate at faster rates in the dimension. Masini2019 generalize the aforementioned results on sparse VARs estimated with the lasso by deriving error bounds under the assumption of weak sparsity, while only assuming the innovation vector to be geometrically strong ($\alpha$-)mixing and a martingale difference process. Finally, Wong2020 provide further generalizations by avoiding the assumption of a specific parametric form of the DGP and relying only on (strict) stationarity and geometrically decaying $\beta$-mixing coefficients to establish error bounds for the lasso for subweibull random vectors.
Owing to the lack of suitable restricted eigenvalue conditions, the literature on the lasso in the non-stationary setting is substantially more scarce, with current results being limited to fixed or moderate dimensional settings only. For example, in the fixed dimensional setting, Liao2015 develop a penalized estimator for a vector error-correction model (VECM) and derive its consistency and pointwise limit distribution. Lee2021 consider a two-stage adaptively weighted lasso procedure applied to (co)integrated data for which the oracle property is shown to hold. Koo2020 consider the lasso applied to predictive regressions with covariates that are integrated of order one and derive error bounds under the assumption that the gram matrix satisfies an REC. The authors correctly note that the resulting lower bound that is assumed on the restricted eigenvalue may decrease to zero as the number of integrated time series grows, thereby inflating the estimation error at an unknown rate. Accordingly, consistency is again only derived for the case of a fixed number of integrated time series. Moving on to the moderate dimensional setting, Liang2019 develop a sparse VECM estimator that is argued to be consistent in a setting where the number of stochastic trends in the data increases at a rate slightly slower than $T^{1/4}$. Smeekes2020a consider lasso-type estimation of a single-equation error-correction model and derive consistency in an asymptotic framework in which the number of integrated time series is allowed to grow at rate $T^{1/4}$. In addition, the authors show that the minimum eigenvalue of the usual non-stationary gram matrix converges to zero as the dimension increases, but can be bounded away from zero with probability converging to one when scaled up by its dimension if the latter grows no faster than rate $T^{1/2}$.
To the best of the author's knowledge, this paper is the first to develop and verify a restricted eigenvalue condition that enables theoretical analysis of $\ell_1$-regularized estimators in true high-dimensional (co)integrated datasets. Since the gram matrix based on integrated time series does not converge to a deterministic matrix, the commonly used indirect approach of imposing a restricted eigenvalue condition on the limit of the sample covariance matrix is not well-suited to high-dimensional settings. Therefore, we instead verify the condition directly on an appropriately scaled version of the gram matrix. Outside the realm of time series, a broad line of research exists that is concerned with direct verification of RE type conditions. In particular, letting $\bm X$ be a $(T \times N)$-matrix with independent rows, numerous authors have shown that $\frac{1}{T}\bm X^\prime\bm X$ satisfies the RE condition under Gaussian or sub-Gaussian tail conditions Zhou2009,Raskutti2010,Rudelson2012,Tropp2015b,Kasiviswanathan2018. To the best of my knowledge, however, no contributions that deal with dependent rows exist in the current literature, let alone the case in which the rows are strongly persistent as is the case when dealing with integrated time series.
The RE condition developed in this paper enables the theoretical analysis of methods based on $\ell_1$-regularization, which we illustrate by deriving tight error bounds for the lasso when applied to cointegrated regression. We then use these error bounds to show that consistency can be maintained even when the number of potentially relevant integrated regressors grows exponentially in the sample size. Furthermore, we conjecture that the reliance on matrix concentration inequalities in the proofs offers sufficient flexibility for prospective future theoretical developments, which we motivate by providing several suggestions for valuable extensions.
The paper proceeds as follows. Section (ref) presents the assumptions on the data, the restricted eigenvalue and the theoretical validity of the latter. Next, in Section (ref) we apply the results of the preceding section to derive error bounds and asymptotic consistency for the lasso when applied to a high-dimension (co)integrated dataset. We conclude in Section (ref).
Finally, a word on notation. For an $N$-dimensional vector $\bm x$, we define the $L_p$-norm as $\left\lVert\bm x\right\rVert_p = \left(\sum_{j=1}^N x_j^p\right)^{1/p}$. Then, for a $(T \times N)$ matrix $\bm Y$, the induced matrix norm is defined as $\left\lVert\bm Y\right\rVert_p = \sup_{\bm x \in \mathbb{R}^N \setminus \lbrace 0 \rbrace} \left\lbrace \frac{\left\lVert\bm Y\bm x\right\rVert_p}{\left\lVert\bm x\right\rVert_p}\right\rbrace$. If $\bm Y$ is square, we use $\lambda_i\left(\bm Y\right)$ to denote its $i$-th eigenvalue and adopt the ordering $\lambda_1\left(\bm Y\right) \leq \ldots \leq \lambda_N\left(\bm Y\right)$. Letting $A,B$ be two index sets, we define $\bm x_A$ as the sub-vector of $\bm x$ consisting of the elements indexed by the set $A$ and $\bm Y_{A,B}$ corresponds to the sub-matrix of $\bm Y$ that contains the rows and columns indexed by $A$ and $B$, respectively. To further simplify notation, we let $\bm Y_A = \bm Y_{A,A}$.
In this section, our main theoretical result is derived. In particular, we derive a finite-sample bound on the probability that the restricted eigenvalue of the gram matrix lies above a positive, universal constant.
Let $\bm S = (\bm s_1,\ldots,\bm s_T)^\prime$ denote a $(T\times N)$-dimensional matrix with random walks of the form $\bm s_t = \sum_{s=1}^t\bm \epsilon_s$. The restricted minimum eigenvalue is defined as
We impose the following assumption on the innovations driving the random walks.
The main theoretical result brought forward in this paper concerns the behaviour of the minimum restricted eigenvalue of $\bm S^\prime\bm S$.
A direct implication of Theorem (ref) is that $\operatorname{\mathbb{P}}\left(\kappa\left(\bm S,\frac{s\log^{3/4}N}{T},s,c_0\right) \geq \kappa_0\right) \to 1$ whenever $T\text{e}^{-s\log N} \to 0$ and $s\text{e}^{-s\log N} \to 0$. Hence, perhaps somewhat counter-intuitively, the restricted eigenvalue condition is more likely to hold when $s$ and $N$ are large. The reason underlying this behaviour is the scaling factor of $s\log^{3/4} N$ included in the restricted minimum eigenvalue. We stress, however, that this is no free lunch, as the scaling factor will inversely affect the convergence rates of $\ell_1$-regularized estimators, as will become apparent in the following section.
Suppose a researcher is interested in modelling a scalar-valued time series $y_t$ based on an $N$-dimensional vector time series $\bm x_t$ by considering the model
The vector $\bm \beta$ is assumed to be sparse, with $S_\beta = \lbrace j : \beta_j \neq 0 \rbrace$ and $\left\lvertS_\beta\right\rvert = s$. Hence, $\bm y_t$ is a unit root non-stationary time series that is cointegrated with $s$ integrated time series. We stack the innovations in the $(N+1)$ vector $\bm \epsilon_t = (\epsilon_{y,t},\bm \epsilon_{x,t}^\prime)^\prime$.
Given that $N$ may be (very) large, we consider estimating the linear model (ref) by the lasso. Define $\bm y = (y_1,\ldots,y_T)^\prime$ and $\bm X = (\bm x_1,\ldots,\bm x_T)$. Then, the lasso estimator for $\bm \beta$ is given by
Based on Theorem (ref), we are able to derive the following error bounds on the prediction and estimation errors.
The probabilistic finite-sample error bound in Theorem (ref) elucidates the dual role of the penalty parameter $\lambda_T$. Whilst a high degree of penalization results in a looser error bound, it simultaneously increases the probability with which this error bound holds. The attentive reader may note that the probability in (ref) contains the lower bound on the probability that the REC holds from Theorem (ref), minus an additional term. The latter term resembles the probability that $\lambda_T$ fails to dominate the empirical process, and is the decisive factor for determining the minimum amount of penalization required to ensure consistency. Indeed, based on Theorem (ref), the consistency of the lasso estimator can be established under a suitable choice of $\lambda_T$ and appropriate restrictions on the growth rates of $T,N$, and $s$.
Corollary (ref) makes the rate of consistency, as well as the sufficient restrictions on growth rates of $\lambda_T,T,N$ and $s$ explicit. Most noteworthy is that consistency may be attained when $N$ grows exponentially in $T$, thereby providing a first justification for the use of the lasso in ultra high-dimensional cointegrated applications. Furthermore, we note that when the number of time series that cointegrate with the dependent variable ($s$) grows at a slow polynomial rate in $T$, while the total number of candidate time series $N$ grows at any polynomial rate in $T$, then $\hat{\bm \beta}$ almost attains attains the same $T$-consistency as in the fixed-dimensional setting.
In this paper, we validate the restricted eigenvalue condition (REC) proposed by Bickel2009 in a stationary setting to unit root nonstationary data. The gram matrix is scaled by $\frac{s^2\log^{3/2}N}{T^2}$ instead of the usual $\frac{1}{T^2}$ that is familiar from the fixed-dimensional case. We apply our extended REC to derive finite-sample error bounds on the lasso when applied to high-dimensional cointegrating regressions. The bounds reveal that consistency can be attained, even under exponential growth of the number of time series. In addition, when the number of potentially relevant integrated regressors grow at any polynomial rate in $T$, while the number of regressors that cointegrate with the dependent variable grows at a slow polynomial rate, the estimator is almost $T$-consistent, as is the case in the classic fixed-dimensional setting.
A natural question that may arise concerns the validity of these results in the presence of multiple cointegrating relationships. We are optimistic that the results in this paper can serve useful when deriving the properties of system estimators such as penalized vector error correction models, and we consider this an interesting avenue for future research.