  The goal of nonparametric regression is to recover an underlying regression
function from noisy observations, under the assumption that the regression
function belongs to a pre-specified infinite dimensional function space. In the
online setting, when the observations come in a stream, it is generally
computationally infeasible to refit the whole model repeatedly. There are as of
yet no methods that are both computationally efficient and statistically
rate-optimal. In this paper, we propose an estimator for online nonparametric
regression. Notably, our estimator is an empirical risk minimizer (ERM) in a
deterministic linear space, which is quite different from existing methods
using random features and functional stochastic gradient. Our theoretical
analysis shows that this estimator obtains rate-optimal generalization error
when the regression function is known to live in a reproducing kernel Hilbert
space. We also show, theoretically and empirically, that the computational
expense of our estimator is much lower than other rate-optimal estimators
proposed for this online setting.
