Bergmeir 2018 - Theorem 1 Validity of K-Fold CV for Autoregressive Models

Summary

Theorem 1 of Bergmeir, Hyndman & Koo says that for a stationary, ergodic, correctly specified nonlinear AR($p$) model with a consistent leave-one-out estimator and martingale-difference errors, the leave-one-out CV estimate of mean squared prediction error, computed by deleting whole rows of the lag-embedded matrix, converges in probability to the true prediction error on an independent copy of the process. The same holds for K-fold CV. Serially uncorrelated errors are the load-bearing condition. A misspecified, underfitting model breaks it; an overfitting but flexible model does not.

Overview

The theorem formalises the heuristic of Bergmeir 2018 - Lag-Embedded K-Fold CV vs h-Block CV: if the residuals of the embedded regression are white, its rows behave like independent regression cases, and ordinary CV works. The authors use leave-one-out “without loss of generality” because “generalisation to the K-fold CV is straightforward” (p. 4). The proof is in Bergmeir 2018 - Proof of Theorem 1 and Lemma 1.

Main Content

Setup (§3, pp. 4-5)

Let $y_1,\dots ,y_n$ be observations from a stationary process where each $y_t$ has distribution $P$ on $\mathbb{R}$.

Nonlinear regression form of the AR( $p$) model (§3, eq. (3), p. 4)

$$y_t=g({\mathbf{x}}_t,\theta )+{\epsilon }_t,{\mathbf{x}}_t=(y_{t-1},y_{t-2},\dots ,y_{t-p}{)}^{\prime },$$

where $g(\cdot )$ is continuous and differentiable in $\theta$ for all ${\mathbf{x}}_t$, and ${\epsilon }_t$ is a regression error.

Estimator. $\hat{\theta }=\arg {\min }_{\theta \in \Theta }Q(\theta )$ with

$$Q(\theta )=\sum _{t=p+1}^n(y_t-g({\mathbf{x}}_t,\theta ){)}^2.$$

Prediction error PE (§3, p. 5)

Let $\{{\tilde{y}}_t{\}}_{t=1}^m$ be another process with the same distribution as the sample $\{y_t{\}}_{t=1}^n$, for example the future, with ${\tilde{\mathbf{x}}}_t=({\tilde{y}}_{t-1},\dots ,{\tilde{y}}_{t-p})$. Then

$$\mathrm{PE}=E\{\tilde{y}-g(\tilde{\mathbf{x}},\hat{\theta }){\}}^2,$$

where $\hat{\theta }$ solves the estimating equations

$$q(\hat{\theta })=\sum _{t=p+1}^n\frac{\partial }{\partial \theta }g({\tilde{\mathbf{x}}}_t,\hat{\theta })({\tilde{y}}_t-g({\tilde{\mathbf{x}}}_t,\hat{\theta }))=\sum _{t=p+1}^n\frac{\partial }{\partial \theta }g({\tilde{\mathbf{x}}}_t,\hat{\theta }){\tilde{\epsilon }}_t(\hat{\theta })=0,$$

with ${\tilde{\epsilon }}_t(\theta )={\tilde{y}}_t-g({\tilde{\mathbf{x}}}_t,\theta )$. By construction ${\tilde{\epsilon }}_t$ has the same distribution as ${\epsilon }_t$.

Leave-one-out CV estimator $\widehat{\mathrm{PE}}$ (§3, p. 5)

The training sample is $\{({\mathbf{x}}_j,y_j):j=p+1,\dots ,n,j\ne t\}$ and the test sample is $\{({\mathbf{x}}_t,y_t)\}$. The entire row of matrix (2) for $t$ is left out. Then

$$\widehat{\mathrm{PE}}=\frac{1}{n-p}\sum _{t=p+1}^n\{y_t-g({\mathbf{x}}_t,{\hat{\theta }}_{-t}){\}}^2,$$

where ${\hat{\theta }}_{-t}$ solves

$$q({\hat{\theta }}_{-t})=\sum _{\begin{array}{c}j=p+1\\ j\ne t\end{array}}^n\frac{\partial }{\partial \theta }g({\mathbf{x}}_j,{\hat{\theta }}_{-t})(y_j-g({\mathbf{x}}_j,{\hat{\theta }}_{-t}))=\sum _{\begin{array}{c}j=p+1\\ j\ne t\end{array}}^n\frac{\partial }{\partial \theta }g({\mathbf{x}}_j,{\hat{\theta }}_{-t}){\epsilon }_j({\hat{\theta }}_{-t})=0,$$

obtained by differentiating $Q_{-t}(\theta )={\sum }_{j=p+1,j\ne t}^n(y_j-g({\mathbf{x}}_j,\theta ){)}^2$.

Goal: $\widehat{\mathrm{PE}}$ should approximate PE closely.

Assumptions (§3, pp. 5-6)

Assumption A1: stationary nonlinear AR( $p$) process

The sequence $\{y_t{\}}_{t=1}^n$ is represented by the nonlinear AR($p$) process (3). The process is stationary and ergodic.

Role: A1 fixes the model CV is applied to and “ensures that no misspecification is considered in our setup” (p. 6). The paper adds: “Note that (3) is a standard AR(p) process and our setup covers common applications of CV for dependent data” (p. 6). That is, the linear AR($p$) model is the special case $g({\mathbf{x}}_t,\theta )={\varphi }_0+{\sum }_{i=1}^p{\varphi }_i{y}_{t-i}$, and the authors present the nonlinear form as covering the usual uses of CV on dependent data. Under regularity conditions (Mokkadem 1988), $\{y_t\}$ is strong mixing:

• (a) $|P(A\cap B)-P(A)P(B)|\le \alpha (k)P(A)$ for all $A\in {\mathcal{F}}_t$, $B\in {\mathcal{F}}_{t+k}$, any $t,k$;
• (b) ${\sum }_{k\ge 1}\alpha (k)<\infty$.

Assumption A2: consistency of nonlinear least squares

${\hat{\theta }}_{-t}$ is a consistent estimator of $\theta$.

By stationarity, the conditions for consistency of $\hat{\theta }$ and ${\hat{\theta }}_{-t}$ are equivalent. One sufficient set (following Andrews 1987):

• (i) the parameter space $\Theta$ is a compact subset of ${\mathbb{R}}^k$;
• (ii) $g(\cdot ,\theta )$ is continuous and differentiable in $\theta$ for all $(y_t,{\mathbf{x}}_t)$;
• (iii) $\frac{1}{n-p-1}{Q}_{-t}(\theta )\stackrel{p}{\to }Q(\theta )$ uniformly in $\theta$, where $Q(\theta )$ is a nonstochastic function with a unique minimum at $\theta ={\theta }_0$.

Assumption A3: errors are a martingale difference sequence (MDS)

The disturbances $\{{\epsilon }_t\}$ satisfy:

• (i) $\{{\epsilon }_t,{\mathcal{F}}_t\}$ is a martingale difference sequence, where ${\mathcal{F}}_t$ is the sigma field generated by $\{{\epsilon }_s,y_s;s\le t\}$. I.i.d. errors are an MDS.
• (ii) $\mathrm{var}({\epsilon }_t\mid {\mathbf{x}}_t)={\sigma }^2$ and $E|{\epsilon }_t{|}^{4+\delta }<K$ for some $K<\infty$ and $\delta >0$.
• (iii) $\{{\epsilon }_t\}$ has an absolutely continuous distribution with respect to Lebesgue measure. This holds for the usual error distributions, including the normal.

Role: “A3.(i) ensures that errors are serially uncorrelated, which will be the key component for the success of the cross-validation” (p. 6).

Strength: A2 and A3 “are not strong assumptions but rather are standard ones, e.g., when Machine Learning methods are used for prediction” (p. 6).

Counterexample to A3: “errors with discrete values, say ${\epsilon }_t\in \{-1,1\}$ do not satisfy A3” (p. 6).

The theorem

Theorem 1 (§3, eq. (4), p. 6)

Suppose that Assumptions A1-A3 hold. Then

$$\widehat{\mathrm{PE}}\stackrel{p}{\to }\mathrm{PE}.$$

The same conclusion holds for K-fold CV over rows of the embedded matrix (the paper treats the extension as straightforward, p. 4).

Proof sketch (full version in Bergmeir 2018 - Proof of Theorem 1 and Lemma 1):

1. Following Burman & Nolan (1992), write PE and $\widehat{\mathrm{PE}}$ each as a variance term, a squared-bias term and a noise term $\int {\epsilon }^2$.
2. The bias and noise terms agree asymptotically.
3. The variance term of PE equals a diagonal sum $\frac{1}{n-p}\sum {\tilde{\epsilon }}_j^2$ plus an off-diagonal double sum ${\sum }_{j\ne t}{\tilde{\epsilon }}_j{\tilde{\epsilon }}_t$.
4. Because whole rows are left out and the errors are an MDS, the off-diagonal sum is a martingale whose normalised fourth moment vanishes (Lemma 1). So it converges to zero in probability, and the diagonal sum matches $\widehat{\mathrm{PE}}$‘s variance term.

When the assumptions fail (pp. 6-7)

The CV method “makes use of features of residuals”, so “residuals should emulate error terms for the success of this type of CV” (p. 6).

• A1 violated (misspecification). “The residuals will no longer have zero serial correlation. Then, the violation of A3 follows naturally since ${\epsilon }_t$ is no longer a MDS, which renders Lemma 1 in the appendix invalid. Therefore, the CV does not work any longer” (pp. 6-7).
• A2 violated (inconsistent estimator). The paper writes: “Because A2 ensures that $\widehat{\mathrm{PE}}$ approximates PE closely through consistency of the OLS estimator of φ, its violation invalidates the proposed CV not only for the dependent setup but also even for the independent setup” (p. 7).

  Notation slip in the source (p. 7) nonlinear least squares for a generic parameter $\theta$ (A2 is titled "Consistency of the Nonlinear Least Squares", and ${\hat{\theta }}_{-t}$ solves the estimating equation $q({\hat{\theta }}_{-t})=0$). "OLS" and "φ" belong to the linear AR($p$) special case, where $\theta =\varphi$ and NLS reduces to OLS. Read the sentence as "consistency of the least-squares estimator $\hat{\theta }$ (and ${\hat{\theta }}_{-t}$)". This is the vault's reading; the paper does not comment on it.

  The sentence speaks of “the OLS estimator of φ”. The setup of §3 is

• A3 violated directly. The paper’s only explicit counterexample is discrete errors: “errors with discrete values, say ${\epsilon }_t\in \{-1,1\}$ do not satisfy A3” (p. 6), because they break A3(iii). It also implies that serially correlated errors break A3(i) (through the A1 discussion above).
  • Vault inference, not stated in the paper: errors whose conditional variance changes with ${\mathbf{x}}_t$ (conditional heteroskedasticity) break A3(ii)‘s $\mathrm{var}({\epsilon }_t\mid {\mathbf{x}}_t)={\sigma }^2$, and heavy-tailed errors without a finite $4+\delta$ moment break A3(ii)‘s moment bound. In either case the Burkholder step of Lemma 1 loses its justification as written. Whether CV actually fails in those cases is not studied in the paper. (Note that a GARCH-type error is still an MDS, so A3(i) alone would survive.)

Scope of the result (§3, p. 7)

Provided the errors are serially uncorrelated, Theorem 1 covers linear or nonlinear parametric regression. Its validity “is extended to models considered ‘nonparametric’ such as regression splines, smoothing splines, locally polynomial regression, and neural networks, which can all be represented by (3)” (p. 7).

§4.4 (p. 9) adds that results “would not change much” for support vector regression or random forests. The argument concerns the residuals, whose features (zero mean, zero correlation) are universal across model families.

Overfitting vs underfitting: the asymmetry

Reading A1 and A3 together gives the paper’s practical message (pp. 2-3):

Situation	A1 (correct spec.)	A3 (white errors)	CV status
Model equals the DGP	✓	✓	valid
Model nests the DGP (too many lags, flexible learner)	✓ (true $g$ inside the class)	✓	valid. CV can detect the overfitting
Model approximates the DGP well (e.g. AR($p$) for MA(1))	approximately	approximately	works well empirically (Exp. 2)
Model underfits (missing seasonal lag, too few lags)	✗	✗ (residual autocorrelation)	biased: CV underestimates error
Exogenous persistent regressors	outside eq. (3)	often ✗	not covered. Use time-ordered evaluation

The last row is not discussed in the paper. It is the vault’s extension, developed in Bergmeir 2018 - Conclusions, Decision Rule and Scope Limits.

Examples

Why underfitting breaks the MDS condition

Setup: the DGP is $y_t=0.7y_{t-12}+u_t$ with i.i.d. $u_t$, and the fitted model is AR(1): $y_t=\varphi y_{t-1}+e_t$.

Step 1, the fit: the best AR(1) approximation has $\varphi \approx \mathrm{corr}(y_t,y_{t-1})\approx 0$, so $e_t\approx y_t$.

Step 2, the residuals: $\mathrm{corr}(e_t,e_{t-12})\approx 0.7$. The residuals are strongly autocorrelated at lag 12 and are not an MDS, so A3(i) fails.

Step 3, the leak: a test row at time $t$ sits next to training rows at $t\pm 12$ (and others) whose errors are correlated with its own. The flexible fit partly absorbs this shared component, so the held-out error looks smaller than true out-of-sample error.

Result: CV is optimistic, as in Experiment 3 of Bergmeir 2018 - Monte Carlo Results for AR and MLP Forecasters (5-fold CV MPAE from $-43.5$ to $-95.2$). A Ljung-Box test on the pooled out-of-fold residuals at 20+ lags flags the problem.

Connections

• Cross Validation Checking: LOO-CV in the exchangeable setting; this theorem is its dependent-data analogue.
• Model Testing and Specification and Single Marketing Time Series: residual whiteness diagnostics that make A3 checkable.
• Model Selection and Overfitting: CV as a guard against overfitting. The theorem shows the guard stays valid for autoregressions.
• Spurious Regression and Nonsense Correlations: what happens with persistent exogenous regressors, which are outside eq. (3).
• Q - Exchangeability and What Replaces It When It Fails: the broader map of exchangeability failures.

See Also

• Bergmeir 2018 - Proof of Theorem 1 and Lemma 1: Appendix A.
• Bergmeir 2018 - Monte Carlo Results for AR and MLP Forecasters: empirical confirmation and the counterexample.
• Out-of-Sample Validation for Time-Series Models: what to do when the conditions fail.