# Using Gaussian Processes to learn a function online

I would like to approximate a function $$f:\mathbb{R} \to \mathbb{R}_+$$ based on a set of samples. I obtain these samples online (i.e. sequentially in time). That is, at time $$t$$ I receive $$(x_t, f(x_t))$$ and I would like to update my approximation of $$f$$.

• Can you please point me to papers / resources describing Gaussian Processes for estimating a function online?
• In addition, can you point me to resources to do this online?

This is pretty straightforward to do with Bayesian learning since it corresponds to sequentially updating the posterior over $$f$$ as more and more data comes in. Bayesian optimization uses this a lot so that's one application to look at for this kind of thing.
Now when we get a new observation $$(x_{n+1}, f(x_{n+1}))$$ we will update our understanding of $$f_*$$ by adding this to $$\f_n$$ to get $$\f_{n+1}$$ and augmenting $$K_n$$ into $$K_{n+1}$$ so now for a new point $$(x_*, f_*)$$ we have $$\hat f_{n+1}(x) = \mu + k_*(x)^T(K_{n+1} + \alpha I_{n+1})^{-1}(\f_{n+1}- \mu\one_{n+1})$$ and the process continues. We've moved from conditioning on $$n$$ things to conditioning on $$n+1$$ things.
We can also save some time with these inverses by using $$K_n^{-1}$$ in the computation of $$K_{n+1}^{-1}$$ so we can compute them recursively. I'll drop the $$\alpha I$$ from this part for cleaner notation but it can be added back in with no issue. We can treat $$K_{n+1}$$ as a 2x2 block matrix so we can use the formula for such a matrix's inverse. Precomputing $$v_n = K_n^{-1}k_*$$ and the inverse of the relevant (1x1) Schur compliment $$S_n := (k_{**} - k_*^Tv_n)^{-1}$$, we have $$K_{n+1}^{-1} = \begin{bmatrix} K_n & k_* \\ k_*^T & k_{**}\end{bmatrix}^{-1} = \begin{bmatrix}K_n^{-1} + S_n v_nv_n^T & -S_n v_n \\ -S_nv_n^T & S_n\end{bmatrix} .$$ Given $$K_n^{-1}$$ and $$k_*$$, computing $$v_n$$ is $$\mathcal O(n^2)$$ and once we have that $$S_n$$ is $$\mathcal O(n)$$. $$K_n^{-1} + S_nv_nv_n^T$$ is additionally $$\mathcal O(n^2)$$ so overall getting $$K_{n+1}^{-1}$$ from $$K_n^{-1}$$ is $$\mathcal O(n^2)$$. This is better than the best known times for explictly inverting $$K_{n+1}^{-1}$$ from scratch.