  We present algorithms for nonparametric regression in settings where the data
are obtained sequentially. While traditional estimators select bandwidths that
depend upon the sample size, for sequential data the effective sample size is
dynamically changing. We propose a linear time algorithm that adjusts the
bandwidth for each new data point, and show that the estimator achieves the
optimal minimax rate of convergence. We also propose the use of online expert
mixing algorithms to adapt to unknown smoothness of the regression function. We
provide simulations that confirm the theoretical results, and demonstrate the
effectiveness of the methods.
