Generalization Bounds for Dependent Data

Everything you have ever been told about what a backtest proves rests on one assumption that market data does not satisfy. Hoeffding's inequality, the VC bound, cross-validation error bars, the whole apparatus of Uniform Convergence of Empirical Risk — each derivation opens with "let the observations be independent and identically distributed". Tuesday's market is not independent of Monday's. Volatility clusters, order flow persists, regimes last for months, and if you built your features from overlapping windows then consecutive rows literally share most of their raw ingredients.

So the honest question is not whether the bounds break. They do not. It is that the sample size inside them shrinks, often by a factor of five or ten, and every conclusion you drew from the original row count has to be re-drawn from the smaller one.

The analogy: the survey that called the same houses

A polling firm reports 1,000 responses and a margin of error of three points. Then you learn how it was collected: they dialled 250 households and interviewed all four residents of each. Nobody lied, nobody was double-counted, the fieldwork was clean. But housemates vote alike. The number on the box is 1,000; the number of genuinely independent opinions is nearer 250, and the honest margin of error is twice as wide as advertised.

Dependent data is that survey. Your dataset has exactly as many rows as it has rows. What it does not have is that many independent facts.

Where the standard bound spends its sample size

Take a loss that lives between 0 and 1 — classification error is the easy case, since every row scores either 0 or 1. Write $\hat{R}$ for the error rate you measured on your data and $R$ for the error rate you will actually suffer in future. For independent rows, Hoeffding's inequality says that with probability at least $1-\delta$,

$$\lvert \hat{R} - R \rvert \;\le\; \sqrt{\frac{\ln(2/\delta)}{2n}}$$

In plain English: the gap between the score on your data and the score in real life shrinks like one over the square root of the number of observations, and $\delta$ is the small chance you are willing to be wrong about that. The symbol $n$ is doing all the work, and the derivation earns it by assuming each row brings news nobody else brought.

When rows are correlated, the right substitution is the effective sample size — the number of independent rows that would have carried the same information:

$$n_{\text{eff}} \;=\; \frac{n}{1 + 2\sum_{k \ge 1} \rho_k}$$

In plain English: divide your row count by how long the series remembers itself. Here $\rho_k$ is the correlation between two observations $k$ steps apart, so the sum in the denominator is a memory length. If the series forgets instantly every $\rho_k$ is zero, the denominator is 1, and you get your rows back.

Worked example 1: overlapping windows

You are testing whether a signal predicts the direction of the next five days. You have five years of daily data, so $n = 1{,}250$ rows, and each row is a five-day forward window that starts one day after the previous one. Your signal calls the direction right 54 percent of the time.

Consecutive rows share four of their five days. Working through the correlation sum for overlapping windows of length $h$ gives a denominator of exactly $h$, so

$$n_{\text{eff}} \;=\; \frac{1{,}250}{5} \;=\; 250$$

In plain English: sampling a five-day return every day rather than every five days gave you five times the rows and none of the extra information.

Now compute the bound both ways at $\delta = 0.05$, where $\ln(2/0.05) = \ln 40 = 3.689$.

• Pretending the rows are independent. $\sqrt{3.689 / (2 \times 1{,}250)} = \sqrt{0.001476} = 0.038$. Your hit rate is $54\% \pm 3.8$ points, a range of 50.2 to 57.8. It clears the coin-flip line, so you write it up.
• Using the effective count. $\sqrt{3.689 / (2 \times 250)} = \sqrt{0.007378} = 0.086$. Your hit rate is $54\% \pm 8.6$ points, a range of 45.4 to 62.6. It contains 50. You have not shown anything.

Same data, same signal, same arithmetic. The only thing that changed is whether you counted rows or counted independent facts.

Putting a number on "eventually forgets"

Effective sample size is the practitioner's version. Learning theory needs something that works for any model class, not just for an average, and the standard tool is a mixing coefficient. Write $\beta(a)$ for how far the joint behaviour of "everything up to today" and "everything from $a$ days later" is from what it would be if the two halves were unrelated.

In plain English: $\beta(a)$ is how much today still tells you about a day $a$ steps away. A market with short memory has $\beta(a)$ collapsing quickly as $a$ grows; a market stuck in a regime has $\beta(a)$ near its maximum for a long time. Series where $\beta(a) \to 0$ are called beta-mixing, and essentially every bound for dependent data assumes it.

Drag the rate knob below into negative territory to see the shape people assume for $\beta(a)$: high at short lags, then falling away. The steeper the fall, the shorter the market's memory, and the less you pay for dependence.

The trick that converts mixing into a bound is blocking. Cut your $n$ observations into $2\mu$ consecutive blocks of length $a$. Keep the odd-numbered blocks and throw the rest away. Any two blocks you kept are now $a$ days apart, so they are nearly independent — off by an amount governed by $\beta(a)$. Apply the ordinary independent bound to the $\mu$ survivors and pay a surcharge for the "nearly":

$$\Pr\big(\lvert \hat{R} - R \rvert \ge \varepsilon \big) \;\le\; 2\exp\!\big(-2\mu\varepsilon^2\big) \;+\; 2(\mu-1)\,\beta(a)$$

In plain English: behave as though you had $\mu$ independent observations rather than $n$, then add a penalty for the fact that they were not quite independent. The first term wants $a$ small so that $\mu$ is large; the second wants $a$ large so that the blocks are far apart. Choosing $a$ is the whole game.

Worked example 2: choosing the block length

You have $n = 2{,}000$ daily observations and a classifier whose measured error rate is 0.44. Suppose the memory of the series decays as $\beta(a) = e^{-0.35a}$, so it has effectively forgotten after about a month. Take $\delta = 0.05$ and try three block lengths. In each case the mixing surcharge $2(\mu-1)\beta(a)$ eats part of the budget, and whatever is left is fed into $2\exp(-2\mu\varepsilon^2)$ to solve for $\varepsilon$.

block length $a$	blocks kept $\mu$	mixing surcharge	budget left	resulting $\varepsilon$
10	100	$198\,e^{-3.5} = 5.98$	none	vacuous
25	40	$78\,e^{-8.75} = 0.0124$	0.0376	0.223
50	20	$38\,e^{-17.5} \approx 0.000001$	0.0500	0.304

Take the middle row step by step. With $a = 25$ you get $2\mu = 80$ blocks, so $\mu = 40$ survive. The surcharge is $2 \times 39 \times e^{-8.75} = 78 \times 0.000158 = 0.0124$. That leaves $0.05 - 0.0124 = 0.0376$ for the exponential term, so $2\exp(-80\varepsilon^2) = 0.0376$, giving $\exp(-80\varepsilon^2) = 0.0188$, then $80\varepsilon^2 = 3.973$ and $\varepsilon = 0.223$.

At $a = 10$ the blocks are too close together and the surcharge alone exceeds 1, which makes the bound say nothing at all. At $a = 50$ the blocks are gloriously independent but there are only 20 of them, so the statistical term widens. The sweet spot is in between.

Now compare with what the independent bound would have claimed for the same 2,000 rows: $\sqrt{3.689 / 4000} = 0.030$. So the naive reading is "true error is at most 0.47, comfortably better than a coin flip", and the honest reading is "true error is at most 0.66, which is worse than guessing". The classifier may well be fine. The point is that these 2,000 correlated days are not enough to prove it.

What this means in practice

Nobody on a desk computes $\beta(a)$. What they do is take the consequences seriously.

Sample overlapping targets at their horizon, or accept the penalty. If your label is a 20-day forward return, either sample every 20 days or knowingly divide your effective sample by 20 when you judge significance. See Effective Sample Size With Autocorrelated Observations.

Purge and embargo your cross-validation folds. Blocking is exactly what Combinatorial Purged Cross-Validation and Cross-Validation for Time Series implement: leave a gap between train and test so the two are far enough apart to be almost unrelated.

Widen every error bar you inherit. Standard errors from a regression package, Sharpe ratio confidence intervals, and the p-value on a factor loading all assume independence unless you asked for something else. Newey-West HAC Standard Errors is the usual fix on the statistics side.

Expect to need much more history than you thought. The bound scales with $1/\sqrt{n_{\text{eff}}}$, so recovering an error bar four times narrower needs sixteen times the independent sample — and on monthly rebalanced data, twenty years is 240 observations, not 240 thousand.