Adaptive Realizable Regression from Two Online Learners

We study realizable regression with a finite or countably infinite function class $\mathcal{F}$. We are given $D_n = \{(X_t, Y_t)\}_{t=1}^n$, which is assumed to be i.i.d.\ with $f^\star \in \mathcal{F}$ such that $\mathbb{E}[Y_t|X_t] = f^\star(X_t)$. The goal is to estimate $f^\star$ with $\hat{f}$ under the absolute loss $\mathbb{E}_X[|\hat{f}(X) - f^\star(X)|]$. We propose a simple reduction that runs two instances of online learning algorithms: one minimizes a learned loss and the other minimizes the error induced by learning the loss. Our main result is a prior-dependent second-order bound: for any prior $\pi$ over $\mathcal{F}$, the estimator achieves with probability at least $1 - \delta$, \begin{align*} \mathbb{E}_X[|\hat{f}(X) - f^\star(X)|] \leq C\sqrt{\frac{\mathbb{E}_X[\sigma(X)]\,\Gamma(f^\star)}{n}} + \frac{CB\,\Gamma(f^\star)}{n}\,, \end{align*} where $\sigma(X) = \mathbb{E}_Y[(Y - f^\star(X))^2 \mid X]$ is the conditional variance, $\Gamma(f^\star) = \log(1/\delta) + \log((1+\log(Bn))/\pi(f^\star))$, $C > 0$ is an absolute constant, and $B$ is an upper bound on $|Y|$ and $|f(X)|$. The bound adapts automatically to the noise level $\mathbb{E}_X[\sigma(X)]$ and range $B$ without any prior knowledge of it, achieving the fast rate $O(B\Gamma(f^\star)/n)$ when $\sigma(X) = 0$ and recovering the slow rate $O(B\sqrt{\Gamma(f^\star)/n})$ in the worst case. The dependence on $\mathcal{F}$ enters only through $\log(1/\pi(f^\star))$, enabling faster rates for structured $\mathcal{F}$ or sparse $f^\star$ and extending naturally to countably infinite classes via summable priors. For finite $\mathcal{F}$ we further show that the same algorithm produces an empirically verifiable bound that allows the learner to evaluate the quality of $\hat{f}$ from the data alone, without knowledge of $\mathbb{E}_X[\sigma(X)]$. Finally, we extend our reduction to general convex loss functions satisfying $\ell(f(x), f(x)) = 0$.