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$, align* E_X[|f(X) - f^\star(X)|] \leq CE_X[\sigma(X)] \Gamma(f^\star)n + CB \Gamma(f^\star)n , 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$.