Timezone: »

Rates of Convergence for Sparse Variational Gaussian Process Regression
David Burt · Carl E Rasmussen · Mark van der Wilk

Thu Jun 13 03:00 PM -- 03:20 PM (PDT) @ Hall A #0
Excellent variational approximations to Gaussian process posteriors have been developed which avoid the $\mathcal{O}\left(N^3\right)$ scaling with dataset size $N$. They reduce the computational cost to $\mathcal{O}\left(NM^2\right)$, with $M\ll N$ the number of \emph{inducing variables}, which summarise the process. While the computational cost seems to be linear in $N$, the true complexity of the algorithm depends on how $M$ must increase to ensure a certain quality of approximation. We show that with high probability the KL divergence can be made arbitrarily small by growing $M$ more slowly than $N$. A particular case is that for regression with normally distributed inputs in D-dimensions with the Squared Exponential kernel, $M=\mathcal{O}(\log^D N)$ suffices. Our results show that as datasets grow, Gaussian process posteriors can be approximated cheaply, and provide a concrete rule for how to increase $M$ in continual learning scenarios.

Author Information

David Burt (University of Cambridge)
Carl E Rasmussen (Cambridge University)
Mark van der Wilk (PROWLER.io)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors