Variational Inference for Gaussian Process Models with Linear Complexity
Large-scale Gaussian process inference has long faced practical challenges due to time and space complexity that is superlinear in dataset size. While sparse variational Gaussian process models are capable of learning from large-scale data, standard strategies for sparsifying the model can prevent the approximation of complex functions. In this work, we propose a novel variational Gaussian process model that decouples the representation of mean and covariance functions in reproducing kernel Hilbert space. We show that this new parametrization generalizes previous models. Furthermore, it yields a variational inference problem that can be solved by stochastic gradient ascent with time and space complexity that is only linear in the number of mean function parameters, regardless of the choice of kernels, likelihoods, and inducing points. This strategy makes the adoption of largescale expressive Gaussian process models possible. We run several experiments on regression tasks and show that this decoupled approach greatly outperforms previous sparse variational Gaussian process inference procedures.
Summary:  The paper employs an alternative view of Titsias's sparse variational inference technique for Gaussian process regression, treating the mean function and covariance function as linear operators in RKHS. By decoupling the basis functions that each of these functions uses, the variational lower bound can now be computed in a O(NMa + NMb^2) complexity, linear in N, and linear in Ma (number of mean parameters) and quadratic in Mb (number of covariance parameters). Previous approaches have O(NM^2) complexity. This means one now can use much bigger Ma compared to Mb without significantly increasing the complexity. The catch is, however, the posterior prediction is no longer **calibrated** and as good, i.e. smaller Mb results in larger predictive variances. The method is compared against existing approaches on several regression datasets, showing lower predictive errors and achieving higher variational lower bounds. 
Details: 
The catch is that the predictive variance is large if Mb is small resulting in a poor predictive performance if measured using the log-likelihood. This can be seen in figure 1, and is mentioned in the text but has not been fully experimented (as the paper only uses the squared error metric which does not use the predictive variances).
Unless I have missed it, the basis locations are not optimised but selected using several initial mini-batches. Would there be any problems if we optimise locations of the inducing points/bases as in Titsias's approach? 
The inducing points/inputs are grounded on some physical locations and can be plotted. Can we visualise the subspace parameterisation? For example, grounding some bases and plotting the samples generated from the corresponding GPs? 
And why is there a kink/sudden change in the traces for all methods in the middle of Figure 1? The learning curves for SVI are still going down after 2000 iterations -- does this use SNGD for the q(u)'s parameters? I think recent works on SVI for GP models (Hensman et al 2014, Bonilla et al 2014, 2015) all use SGD for the mean and Cholesky parameters. This seems to work well in practice, and avoid the need to deal with natural gradients or select a separate learning rate. It would be better to compare to these variants of SVI.
Extensions to non-Gaussian likelihoods seem non-trivial as computing the expected log likelihood would decouple the variational parameters.