# Nonparametric nonlinear regression with prediction uncertainty (besides Gaussian Processes)

What are state-of-the-art alternatives to Gaussian Processes (GP) for nonparametric nonlinear regression with prediction uncertainty, when the size of the training set starts becoming prohibitive for vanilla GPs, but it is still not very large?

Details of my problem are:

• input space is low-dimensional ($\mathcal{X} \subseteq \mathbb{R}^d$, with $2\le d \le 20$)
• output is real-valued ($\mathcal{Y} \subseteq \mathbb{R}$)
• training points are $10^3 \lesssim N \lesssim 10^4$, about a order of magnitude larger than what you could deal with standard GPs (without approximations)
• the function $f: \mathcal{X} \rightarrow \mathcal{Y}$ to approximate is a black-box; we can assume continuity and a relative degree of smoothness (e.g., I would use a Matérn covariance matrix with $\nu = \frac{5}{2}$ for a GP)
• for each queried point, the approximation needs to return mean and variance (or analogous measure of uncertainty) of the prediction
• I need the method to be retrainable relatively fast (of the order of seconds) when one or a few new training points are added to the training set

Any suggestion is welcome (a pointer/mention to a method and why you think it'd work is enough). Thank you!

• What about sparse GPs? With good placement of the inducing points and if there is a sparse relationship between inputs and outputs, $10^4$ training points would be a piece of cake on a Xeon workstation. Commented Aug 5, 2016 at 15:12
• Thanks @DeltaIV. I think that the key point in your answer is "with good placement of the inducing points". Finding good inducing points ($f$ is black-box) seems like a hard problem. Which kind of approximation would you recommend? (e.g., FITC?) Does it work well in practice? Commented Aug 5, 2016 at 15:25
• Of course you learn their position from data. No, FITC is inferior to VFE. Have a look here: arxiv.org/pdf/1606.04820v1.pdf. Dimensionality & size of the training data set are similar to yours. Commented Aug 5, 2016 at 15:31
• Do you strictly need nonparametric and nonlinear regression methods? I don't know about your application, but in computational mechanics & fluid dynamics (classic cases where $f$ is a black box), methods similar to orthogonal polynomial regression work remarkably well, i.e., compressed sensing Polynomial Chaos/Stochastic Collocation methods. Otherwise you could try MARS or GAMs (GAMs are additive, though). Commented Aug 5, 2016 at 15:37
• Finally, I've never used them, but random forests and extreme gradient boosting are both popular nonparametric nonlinear regression methods for high dimensional problems with large training sets. Commented Aug 5, 2016 at 15:41

A Matérn covariance matrix with $ν=5/2$ is almost converging to a Squared Exponential kernel.
• I had a look at Chapter 6.4.1. How is this different/faster than GPs? I understand that for training I could probably just minimize the loss via LBFGS (and perhaps there are even smarter methods). This is in my understanding why RBFs are faster to fit than GPs (the bottleneck for GPs is matrix inversion). But to compute the predictive uncertainty I need to condition on the observed points -- won't this require an inversion of a $M$-by-$M$ matrix? ($M$ number of training points) Commented Aug 25, 2016 at 14:14