Sharp Rates in Dependent Learning Theory: Avoiding Sample Size Deflation
  for the Square Loss
Ingvar Ziemann Stephen Tu George J. Pappas Nikolai Matni
In this work, we study statistical learning with dependent ($\beta$-mixing)
data and square loss in a hypothesis class $\mathscr{F}\subset L_{\Psi_p}$
where $\Psi_p$ is the norm $\|f\|_{\Psi_p} \triangleq \sup_{m\geq 1} m^{-1/p}
\|f\|_{L^m} $ for some $p\in [2,\infty]$. Our inquiry is motivated by the
search for a sharp noise interaction term, or variance proxy, in learning with
dependent data. Absent any realizability assumption, typical non-asymptotic
results exhibit variance proxies that are deflated \emph{multiplicatively} by
the mixing time of the underlying covariates process. We show that whenever the
topologies of $L^2$ and $\Psi_p$ are comparable on our hypothesis class
$\mathscr{F}$ -- that is, $\mathscr{F}$ is a weakly sub-Gaussian class:
$\|f\|_{\Psi_p} \lesssim \|f\|_{L^2}^\eta$ for some $\eta\in (0,1]$ -- the
empirical risk minimizer achieves a rate that only depends on the complexity of
the class and second order statistics in its leading term. Our result holds
whether the problem is realizable or not and we refer to this as a \emph{near
mixing-free rate}, since direct dependence on mixing is relegated to an
additive higher order term. We arrive at our result by combining the above
notion of a weakly sub-Gaussian class with mixed tail generic chaining. This
combination allows us to compute sharp, instance-optimal rates for a wide range
of problems. %Our approach, reliant on mixed tail generic chaining, allows us
to obtain sharp, instance-optimal rates. Examples that satisfy our framework
include sub-Gaussian linear regression, more general smoothly parameterized
function classes, finite hypothesis classes, and bounded smoothness classes.