  We introduce a scalable approach to Gaussian process inference that combines
spatio-temporal filtering with natural gradient variational inference,
resulting in a non-conjugate GP method for multivariate data that scales
linearly with respect to time. Our natural gradient approach enables
application of parallel filtering and smoothing, further reducing the temporal
span complexity to be logarithmic in the number of time steps. We derive a
sparse approximation that constructs a state-space model over a reduced set of
spatial inducing points, and show that for separable Markov kernels the full
and sparse cases exactly recover the standard variational GP, whilst exhibiting
favourable computational properties. To further improve the spatial scaling we
propose a mean-field assumption of independence between spatial locations
which, when coupled with sparsity and parallelisation, leads to an efficient
and accurate method for large spatio-temporal problems.
