# Gaussian Process Kernel and Ridge Regression

Can a Dual Ridge Regression produce the same prediction results as a Gaussian Process with a polynomial kernel $K(x,x')=(x^Tx'+1)^2$ in less time complexity (GP is $O(n^3)$ ) using Cholesky decomposition?

If yes what would the complexity of the Ridge Regression be with a kernel that produces the same results?

If not would an SVM model be suggested?

I want to achieve linear to the number features time complexity.

• Please don't vandalize your question. If you want, you can delete your question by clicking the gray 'delete' under the tags. – gung Apr 5 '14 at 15:41
• Actually, correct me if I'm wrong, but I don't think he can now that he's got an upvoted answer... – Nick Stauner Apr 5 '14 at 21:02
• Your question has an answer, so you don't really 'own' it any more - it contains work by other people (an answer) and you don't get to delete their effort without a very good reason. If there is an especially good reason, you should flag it instead and explain it to the moderators. – Glen_b Apr 5 '14 at 23:22

Cholesky decomposition also has a complexity of $O(n^3)$ operations, so it has the same computational scaling properties as Gaussian Process regression. If you want to reduce time complexity, you could investigate a sparse approximation of the least-squares support vector machine (LSSVM) which is equivalent to dual ridge regression, which I have found useful, see e.g.

Gavin C Cawley and Nicola LC Talbot, "Improved sparse least-squares support vector machines", Neurocomputing, volume 48, number 1, pages 1025-1031, 2002

and

Gavin C. Cawley and Nicola LC Talbot, "A greedy training algorithm for sparse least-squares support vector machines", International Conference on Artificial Neural Networks—ICANN 2002, pages 681 686, 2002

If greedy selection of representation vectors is too slow, simply picking a subset of the data at random tends to work quite well (as long as all of the training data appear in the loss function).

I am not very keen on support vector regression as the $\epsilon$-insensitive loss function doesn't have a straightforward probabilistic interpretation, which is often important in regression applications.

• use the same kernel as the covariance function of the GP, there is also a need to choose a suitable regularisation parameter for the KRR model to match the GP. – Dikran Marsupial Mar 19 '14 at 15:07
• thanks I ll give it a try with theano and python! How would somebody chose the regularisation parameter? Bayesian optimisation until it fits? – papajohn Mar 19 '14 at 15:17
• @papajohn typically through cross-validation. – Marc Claesen Mar 19 '14 at 16:51
• CV Makes sense... but my objective is to simulate the GP so how would the choice be done in that case? – papajohn Mar 19 '14 at 16:56
• I use leave-one-out cross-validation for setting the regularisation parameter of ridge regression models, which can be performed very cheaply (see dx.doi.org/10.1016/j.neunet.2007.05.005 ). However, IIRC, the regularisation parameter for ridge regression typically corresponds to a parameter of the covariance function of the GP, however the exact relationship depends on how it is coded. – Dikran Marsupial Mar 19 '14 at 17:01