Learning with little mixing
We study square loss in a realizable time-series framework with martingale
difference noise. Our main result is a fast rate excess risk bound which shows
that whenever a trajectory hypercontractivity condition holds, the risk of the
least-squares estimator on dependent data matches the iid rate order-wise after
a burn-in time. In comparison, many existing results in learning from dependent
data have rates where the effective sample size is deflated by a factor of the
mixing-time of the underlying process, even after the burn-in time.
Furthermore, our results allow the covariate process to exhibit long range
correlations which are substantially weaker than geometric ergodicity. We call
this phenomenon learning with little mixing, and present several examples for
when it occurs: bounded function classes for which the $L^2$ and
$L^{2+\epsilon}$ norms are equivalent, ergodic finite state Markov chains,
various parametric models, and a broad family of infinite dimensional
$\ell^2(\mathbb{N})$ ellipsoids. By instantiating our main result to system
identification of nonlinear dynamics with generalized linear model transitions,
we obtain a nearly minimax optimal excess risk bound after only a polynomial
burn-in time.