  The goal of regression is to recover an unknown underlying function that best
links a set of predictors to an outcome from noisy observations. In
non-parametric regression, one assumes that the regression function belongs to
a pre-specified infinite dimensional function space (the hypothesis space). In
the online setting, when the observations come in a stream, it is
computationally-preferable to iteratively update an estimate rather than
refitting an entire model repeatedly. Inspired by nonparametric sieve
estimation and stochastic approximation methods, we propose a sieve stochastic
gradient descent estimator (Sieve-SGD) when the hypothesis space is a Sobolev
ellipsoid. We show that Sieve-SGD has rate-optimal MSE under a set of simple
and direct conditions. We also show that the Sieve-SGD estimator can be
constructed with low time expense, and requires almost minimal memory usage
among all statistically rate-optimal estimators, under some conditions on the
distribution of the predictors.
