  We propose an efficient online approximate Bayesian inference algorithm for
estimating the parameters of a nonlinear function from a potentially
non-stationary data stream. The method is based on the extended Kalman filter
(EKF), but uses a novel low-rank plus diagonal decomposition of the posterior
precision matrix, which gives a cost per step which is linear in the number of
model parameters. In contrast to methods based on stochastic variational
inference, our method is fully deterministic, and does not require step-size
tuning. We show experimentally that this results in much faster (more sample
efficient) learning, which results in more rapid adaptation to changing
distributions, and faster accumulation of reward when used as part of a
contextual bandit algorithm.
