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.

  • $\begingroup$ Please don't vandalize your question. If you want, you can delete your question by clicking the gray 'delete' under the tags. $\endgroup$ – gung Apr 5 '14 at 15:41
  • $\begingroup$ Actually, correct me if I'm wrong, but I don't think he can now that he's got an upvoted answer... $\endgroup$ – Nick Stauner Apr 5 '14 at 21:02
  • 1
    $\begingroup$ 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. $\endgroup$ – 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


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.

  • $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Mar 19 '14 at 15:07
  • $\begingroup$ thanks I ll give it a try with theano and python! How would somebody chose the regularisation parameter? Bayesian optimisation until it fits? $\endgroup$ – papajohn Mar 19 '14 at 15:17
  • $\begingroup$ @papajohn typically through cross-validation. $\endgroup$ – Marc Claesen Mar 19 '14 at 16:51
  • $\begingroup$ CV Makes sense... but my objective is to simulate the GP so how would the choice be done in that case? $\endgroup$ – papajohn Mar 19 '14 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Dikran Marsupial Mar 19 '14 at 17:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.