The noise level in linear regression with dependent data

We derive upper bounds for random design linear regression with dependent (β-mixing) data absent any realizability assumptions. In contrast to the strictly realizable martingale noise regime, no sharp instance-optimal non-asymptotics are available in the literature. Up to constant factors, our analysis correctly recovers the variance term predicted by the Central Limit Theorem-the noise level of the problem-and thus exhibits graceful degradation as we introduce misspecification. Past a burn-in, our result is sharp in the moderate deviations regime, and in particular does not inflate the leading order term by mixing time factors. 1 A distribution PX,Y is (linearly) realizable if the regression function x → E[Y | X = x] is linear.