Quantifying the Computational Advantage of Forward Orthogonal Deviations

Quantifying the Computational Advantage of Forward Orthogonal Deviations

Introduction

In a seminal paper, Arellano1991 introduced a now well-known one-step generalized method of moments (GMM) panel data estimator. The estimator relies on first-differencing the observations --- the first-difference (FD) transformation --- and then applying GMM. Bover1995 suggested another transformation could be used. They showed that, under suitable conditions, GMM is invariant to how the data are transformed, and they introduced the forward orthogonal deviations (FOD) transformation to the panel data literature. Moreover, Bover1995 noted there is a computational advantage to using the FOD transformation when the number of columns in the instrument matrix is large. However, to date, there appears to be no published evidence illustrating how much of a computational advantage is conferred by using the FOD transformation.

The purpose of this paper is to fill that gap. I show how the computational complexity --- the amount of computational worked required --- of the FD and FOD transformations increase with the length of the time series ($T$) and the number of individuals ($N$). The results reveal that, even when lim$(T/N) = 0$,\footnote{In this case, one-step GMM, based on all available instruments, has no asymptotic bias Alvarez2003.} computational complexity is affected much more by the size of $T$ than by the size of $N$. Furthermore, the FD transformation's computational complexity increases with $T$ at a much faster rate than the rate of increase in the FOD transformation's computational complexity. Consequently, when $T$ is not small, the FOD transformation is computationally faster --- orders of magnitude faster --- than the FD transformation. A practical implication of this finding is that computationally intensive work, such as Monte Carlo simulations, can be performed much faster by relying on the FOD rather than the FD transformation.

The computational complexity of the FD and FOD transformations

In order to compare the computational complexity of the FD and FOD transformations, a simple case was considered --- the first-order autoregressive (AR(1)) panel data model. The model is

with $y_{i0}$ taken to be the first available observation. If the $v_{it}$s are uncorrelated, then, for instruments, one might use $z_{i1}=y_{i0}$, $\boldsymbol{z}_{i2}^{\prime }=\left( z_{i1},y_{i1}\right) $, $\boldsymbol{z}_{i3}^{\prime }=\left( \boldsymbol{z} _{i2}^{\prime },y_{i2}\right) $, and so on up to $\boldsymbol{z} _{i,T-1}^{\prime }=( \boldsymbol{z}_{i,T-2}^{\prime },y_{i,T-2}) $ . For this choice of instruments, one-step GMM based on the FOD transformation is numerically equivalent to one-step GMM based on the FD transformation (see, e.g., Hayakawa and Nagata, 2016).

However, although numerically the same, the two transformations are not computationally the same. To see this, consider first one-step GMM estimation of the AR(1) panel data model using the FD transformation. The first-difference transformation matrix is

The one-step GMM estimator based on this transformation can be written as follows: Let $\boldsymbol{y}_{i}=\left( y_{i1},\ldots ,y_{iT}\right) ^{\prime }$, $\boldsymbol{y}_{i,-1}=\left( y_{i0},\ldots ,y_{i,T-1}\right) ^{\prime }$, $\boldsymbol{\tilde{y}}_{i}=\boldsymbol{Dy} _{i}$, and $\boldsymbol{\tilde{y}}_{i,-1}=\boldsymbol{Dy}_{i,-1}$ ($ i=1,\ldots ,N$). Also, let $\boldsymbol{Z}_{i}$ denote a block-diagonal matrix with the vector $\boldsymbol{z}_{it}^{\prime }$ in its $t$th diagonal block ($t=1,\ldots ,T-1$, $ i=1,\ldots ,N$). Moreover, let $\boldsymbol{\tilde{s}}=\sum_{i}\boldsymbol{Z} _{i}^{\prime } \boldsymbol{\tilde{y}}_{i}$, $\boldsymbol{\tilde{s}}_{-1}=\sum_{i} \boldsymbol{Z}_{i}^{\prime } \boldsymbol{\tilde{y}}_{i,-1}$, $\boldsymbol{G}=\boldsymbol{D}\boldsymbol{D}^{\prime}$, and $\boldsymbol{A}_{N}=\sum_{i}\boldsymbol{Z}_{i}^{\prime }\boldsymbol{G}\boldsymbol{Z}_{i}$. Finally, set $\boldsymbol{\tilde{a}}=\boldsymbol{\tilde{s}}_{-1}^{\prime }\boldsymbol{A}_{N}^{-1}$. Then the one-step FD GMM estimator is given by

Arellano1991.

For large $T$, the formula in ((ref)) is computationally expensive. A measure of computational cost or work is computational complexity, which is the number of floating point operations or flops required.\footnote{A flop consists of an addition, subtraction, multiplication, or division.} The conclusion from counting up the number of flops required to compute $\widehat{\delta}_{D}$ is provided in Lemma (ref).

Appendix A.1 provides the flop counts that verify Lemma (ref).

Lemma (ref) shows that, even when $T$ is much smaller than $N$, it can be much more important than $N$ in determining the amount of computational work --- and hence time --- it takes to obtain an estimate via the formula in ((ref)). A substantial contribution to the amount of work required is the computation of $\boldsymbol{A}_{N}$ and then inverting it. Appendix A.1 shows that the number of flops required to calculate $\boldsymbol{A}_{N}$ is on the order of O($NT^{5}$). Moreover, the work required to invert $\boldsymbol{A}_{N}$ increases even faster with $T$. Standard matrix inversion methods require on the order of another O($T^{6}$) flops to compute $\boldsymbol{A}_{N}^{-1}$.

On the other hand, the FOD transformation does not require inverting $\boldsymbol{A}_{N}$. This fact makes it more efficient computationally when $T$ is not small.

To see how much more efficient the FOD transformation is, consider again the AR(1) model in ((ref)), and set $\boldsymbol{\ddot{y}}_{i}=\boldsymbol{Fy}_{i}$ and $\boldsymbol{\ddot{y}}_{i,-1}=\boldsymbol{Fy}_{i,-1}$, where $\boldsymbol{F}$ is the FOD transformation matrix given by

(see Arellano and Bover, 1995). Also, let $\ddot{y}_{it}$ and $\ddot{y}_{i,t-1}$ denote the $t$th entries in $\boldsymbol{\ddot{y}}_{i}$ and $\boldsymbol{\ddot{y}}_{i,-1}$. Then the FOD version of the one-step GMM estimator is

where $\boldsymbol{\ddot{s}}_{t}=\sum_{i}\boldsymbol{z}_{it}\ddot{y}_{it}$, $\boldsymbol{\ddot{s}}_{t-1}=\sum_{i} \boldsymbol{z}_{it}\ddot{y}_{i,t-1}$, $\boldsymbol{\ddot{a}}_{t}=\boldsymbol{\ddot{s}}_{t-1}^{ \prime } \boldsymbol{S}_{t}^{-1}$, and $\boldsymbol{S}_{t}=\sum_{i}\boldsymbol{z}_{it} \boldsymbol{z}_{it}^{\prime }$ (see, e.g., Alvarez and Arellano, 2003).

The formula in ((ref)) replaces computing and then inverting one large matrix --- the matrix $\boldsymbol{A}_{N}$ --- with computing and inverting several smaller matrices --- the matrices $\boldsymbol{S}_{t}$ ($t=1,\ldots ,T-1$). The computational savings of this alternative approach are summarized in Lemma (ref).

The flop counts are provided in Appendix A.2.

Lemmas (ref) and (ref) show that the computational complexity of one-step GMM based on both the FOD and FD transformations increases much faster with $T$ than with $N$. But the number of flops increase with $T$ at a much slower rate for the FOD transformation. This finding indicates that, for large $T$, computing time will be orders of magnitude faster for the FOD transformation than for the FD transformation. This conjecture is explored in the next section.

An illustration

In order to illustrate the reductions in computing time from using the FOD transformation rather than differencing, some experiments were conducted. For all of the experiments, observations on $y_{it}$ were generated according to the AR(1) model

with $y_{i,-50}=0$. The value for $\delta $ was fixed at $0.5$ for all experiments. The error components $\eta _{i}$ and $v_{it}$ were generated independently as standard normal random variables. The processes were started with $t=-50$ so that, for each $i$, the process was essentially stationary by time $t=0$. As for the sample sizes, $T$ was set to either five, 10, 15, 20, 25, 30, 35, 40, 45, or 50 whereas $N$ was either 100, 200, 300, 400, or 500. After a sample was generated, start-up observations were discarded so that estimation was based on the $T+1$ observations $y_{i0},\ldots ,y_{iT}$ for each $i$ ($i=1,\ldots ,N$). Finally, one-step GMM estimates were calculated both with the FD formula in ((ref)) and the FOD formula in ( (ref)). The estimates obtained from the two formulas were identical but how long it took to compute them differed.\footnote{All computations were performed using GAUSS. To calculate elapsed times for the FOD and FD algorithms, the GAUSS command hsec was used to calculate the number of hundredths of a second since midnight before and after calculations were executed.}

Figure 1 plots ratios of computing times as $N$ increases holding $T$ fixed. In Figure 1, I plot the time required to calculate GMM estimates for 100 independent samples of size $T=5$ and $N=X$ ( $X=100$, 200, 300, 400, and 500) over the time required to calculate that many one-step GMM estimates for $T=5$ and $N=100$, first using the FD formula in ((ref)) and then using the FOD formula in ((ref)). The solid line shows how computing time increases with $N$, holding $T$ constant, using differencing, while the dashed line shows how it increases with $N$ using forward orthogonal deviations.

The message of the figure is clear. Because the number of computations required to compute a GMM estimate increases linearly in $N$, regardless of whether differencing or the FOD transformation is used, so too does computing time. For example, in Figure 1, when $N$ is doubled from 100 to 200, computing time approximately doubles, regardless of whether estimates are computed using the differencing or the FOD transformation. When $N$ triples from 100 to 300, computing time approximately triples, and so on.

Figure 2 plots ratios of computing times as $T$ changes, with $N$ held fixed at 100. Specifically, it gives the time required to calculate GMM estimates for 100 independent samples of size $N=100$ and $T=X$ ($X=5$, 10, 15, 20, 25, 30, 35, 40, 45, and 50) over the time required to compute that many estimates for $N=100$ and $T=5$. As in Figure 1, the solid curve shows how computing time increases for the FD transformation, but now as $T$ increases with $N$ held fixed. The dashed curve shows how computing time increases as $T$ increases using the FOD transformation.

Figure 2 shows that computing time does not increase linearly with $T$. Instead, when the FD transformation is used, computing time increases much faster than linearly. For example, if the differencing formula in ((ref)) is used to calculate one-step GMM estimates, then, for $N=100$, it takes about 5.5 times longer to calculate an estimate, on average, when $T=10$ than when $T=5$. Thus, doubling $T$ increases computing time by 5.5 times. When $T$ increases from 5 to 15, a three-fold increase in $T$, it takes about 36 times longer to calculate an estimate. Finally, if we increase $T$ ten-fold, from 5 to 50, it takes approximately $16,038$ times longer to compute GMM estimates if differencing is used (see Figure 2).

When we use the FOD formula in ((ref)) to calculate GMM estimates, the relative increase in computing time is much less dramatic, but it is still not linear in $T$. In Figure 2, I also plotted the ratios of computing times required to calculate GMM estimates using the FOD formula in ((ref)). For the FOD transformation, how relative computing time increases with $T$ is indicated by the dashed line in the figure. The line hugs the horizontal axis in Figure 2 because the increase in computing time with $T$ is of a much smaller order of magnitude when the FOD transformation is used than when the FD transformation is used. Specifically, for $N=100$, the computing time given $T=10$ is 2.2 times what it is when $T=5$. Thus, doubling $T$ leads to a bit more than double the computing time. However, a ten-fold increase in computing time --- when $T$ is increased from 5 to 50 --- leads to computing time taking about 24 times longer to compute an estimate when the FOD transformation is used.

Although the computational complexity of the FOD transformation is not linear in $T$, it increases at a much slower rate in $T$ than is the case when differencing is used. Consequently, as $T$ increases, using the FOD formula for calculating GMM estimates leads to significant reductions in computing time relative to using the differencing formula for computing GMM estimates. Table 1 shows how large these reductions can be.

Table 1 reports time ratios. The ratios in Table 1 are the time required to compute estimates using the FD transformation over the time required to compute those same estimates using the FOD transformation for different values of $T$ and $N$. For small $T$, the computations based on first differences are faster. For example, for $T=5$, it takes about half the time to calculate an estimate using the FD formula in ((ref)) rather than the FOD formula in ( (ref)). However, because computational complexity increases in $T$ at a slower rate when the FOD transformation is used rather than differencing, the FOD method is faster --- indeed, much faster --- than differencing for larger values of $T$. For $T$ as small as 10, the FOD transformation is faster, and, for $T=50$, computations based on the FOD transformation are two orders of magnitude faster --- specifically, over 300 times faster --- than computations exploiting the FD transformation.

Table 1: Time to compute FD GMM estimates over time to compute FOD GMM estimates.

Note: Each estimate is based on 100 samples.

Summary and concluding remarks

This paper showed that the computational complexity of one-step GMM estimation based on the FD transformation increases with $N$ linearly but it increases with $T$ dramatically --- at the rate $T^{6}$ increases. On the other hand, when the FOD transformation is used, computational complexity still increases with $N$ linearly, but it increases with $T$ at the rate $T^{4}$ increases. Simulation evidence provided in Section (ref) showed that the reductions in computing time from use of the FOD instead of the FD transformation are dramatic when $T$ is not small.

The fact that estimates can be computed so much faster with the FOD transformation implies that Monte Carlo simulations, and other computationally intensive procedures, can be conducted in a fraction of the time if the FOD transformation is used rather than the FD transformation. Consequently, Monte Carlo studies using large values of $T$ and complicated models that may be prohibitively costly for GMM estimation based on the FD transformation may be feasible for GMM based on the FOD transformation.