Variational Orthogonal Features

Sparse stochastic variational inference allows Gaussian process models to be applied to large datasets. The per iteration computational cost of inference with this method is O(tildeNM2+M3), where tildeN is the number of points in a minibatch and M is the number of `inducing features', which determine the expressiveness of the variational family. Several recent works have shown that for certain priors, features can be defined that remove the O(M3) cost of computing a minibatch estimate of an evidence lower bound (ELBO). This represents a significant computational savings when Mgg tildeN. We present a construction of features for any stationary prior kernel that allow for computation of an unbiased estimator to the ELBO using T Monte Carlo samples in O(tildeNT+M2T) and in O(tildeNT+MT) with an additional approximation. We analyze the impact of this additional approximation on inference quality.