Efficient leave-one-out cross-validation?

[Tal-Golan]

Is there an easy way of combing fractional RR with efficient leave-one-out cross-validation?

SKLearn has a documented implementation of LOOCV for standard RR:
https://github.com/scikit-learn/scikit-learn/blob/7e1e6d09bcc2eaeba98f7e737aac2ac782f0e5f1/sklearn/linear_model/_ridge.py#L1432

Edit: the linked code should be reviewed in light of this issue:
scikit-learn/scikit-learn#18079
(TL;DR: although the scikit-learn code mentions GCV, an algebraic form of LOOCV is implemented).

[kendrickkay]

I checked out the links you sent; thanks. I haven't fully wrapped my head around the logic for the LOOCV idea in the technical reports. It sounds like perhaps that if you get a range of ridge-regression solutions (e.g. fractions from 0 to 1 in steps of 0.01 or 0.02 or something) for a full dataset, there might be some analytic solutions for estimating/determining what the leave-one-out error would have been for each of the ridge-regression solutions? If so, then that could greatly speed up computational time with respect to actually doing the leave-one-out procedure.

[Tal-Golan]

Yes, that's exactly my understanding. This is explained in more detail here:
https://www.mit.edu/~9.520/spring07/Classes/rlsslides.pdf
(slides 14-20, slide 30 for the SVD form)

[kendrickkay]

Yeah... but I have trouble parsing it. Have you figured it out / coded it with a simple example maybe?

[Tal-Golan]

https://gist.github.com/Tal-Golan/47e0daecf77d800136125576417a7450

[kendrickkay]

Nice! Do you want to Zoom to discuss a bit? I don't quite speak Python. Also, it seems too good to be true. Is it verifiable that the solution is exactly equal to what would happen if the full LOO procedure was implemented? Are there any limitations/assumptions going on? Maybe email me (kendrickkay@gmail.com) to find a time to Zoom?

[Tal-Golan]

Sure, I'll email you. We can empirically verify the equivalence of the results with algorithmic LOOCV for different regimes (e.g., not full rank, more features than observations). I don't see explicit assumptions in Rifkin's notes.

[kendrickkay]

I did some simulations to verify the correctness. It does seem promising.

However, I noticed something. It seems that an implementation would, in theory, have to do a for-loop over each alpha value and for each target (e.g. see screenshot). This is because, technically, to achieve a nice uniform set of fractions for every target, the corresponding alpha that would achieve those fractions might in fact vary from target to target. (Of course, in practice, the variation may be small...) If that is true, then the numerically correct implementation would, ironically, be really slow in the case of many targets. That seems not very appealing. So, then, if this is all true, then ironically a "n-fold" cross-validation scheme that the user performs based on the returned coefficients by fracridge might be faster.

[Tal-Golan]

I agree that such a nested loop over targets and alphas isn't ideal, but this might still be worthwhile for usage cases in which the number of targets is not huge. Maybe the simplest solution would be to add an optional call to a function within the target loop (around line 200 in fracridge.py) that will estimate LOOCV MSE per alpha and target? This targets X alphas MSE matrix can be then stored as a FracRidgeRegressor object property.

[kendrickkay]

good idea. I've been playing around with the matlab implementation.

this is sort of cool. x-axis is log(alpha). y-axis is MSE. red is a naive LOO implementation. blue is the analytic method. black is the fracridge analytic LOO method. Notice how black follows the red and blue, but that black is more sensibly arranged on the x-axis (which is the whole point of fracridge). Notice also that fracridge finds a (slightly) better minimum.

[Tal-Golan]

Yes, this is indeed a convincing demonstration of using fracridge. One more argument in favor of including the analytic LOO is that it would reduce the common mistake of using the test set to choose the alpha.

[kendrickkay]

Other examples are more extreme, see above.

Yeah, I suppose that bad users can do bad things

[kendrickkay]

I just pushed an update to the MATLAB fracridge.m with the new feature.

here is an example (also in the documentation of the function):

[kendrickkay]

If you speak MATLAB and want to try it, I would be curious.

Otherwise, we will have to wait on @arokem if he can port the update to Python.

[kendrickkay]

(Passing the nerd sniping to @arokem )