  Standard sparse pseudo-input approximations to the Gaussian process (GP)
cannot handle complex functions well. Sparse spectrum alternatives attempt to
answer this but are known to over-fit. We suggest the use of variational
inference for the sparse spectrum approximation to avoid both issues. We model
the covariance function with a finite Fourier series approximation and treat it
as a random variable. The random covariance function has a posterior, on which
a variational distribution is placed. The variational distribution transforms
the random covariance function to fit the data. We study the properties of our
approximate inference, compare it to alternative ones, and extend it to the
distributed and stochastic domains. Our approximation captures complex
functions better than standard approaches and avoids over-fitting.
