TL,DR: It appears that, contrary to oft-repeated advice, leave-one-out cross validation (LOO-CV) -- that is, $K$-fold CV with $K$ (the number of folds) equal to $N$ (the number of training observations) -- yields estimates of the generalization error that are the least variable for any $K$, not the most variable, assuming a certain stability condition on either the model/algorithm, the dataset, or both (I'm not sure which is correct as I don't really understand this stability condition).

  • Can someone clearly explain what exactly this stability condition is?
  • Is it true that linear regression is one such "stable" algorithm, implying that in that context, LOO-CV is strictly the best choice of CV as far as bias and variance of the estimates of generalization error are concerned?

The conventional wisdom is that the choice of $K$ in $K$-fold CV follows a bias-variance tradeoff, such lower values of $K$ (approaching 2) lead to estimates of the generalization error that have more pessimistic bias, but lower variance, while higher values of $K$ (approaching $N$) lead to estimates that are less biased, but with greater variance. The conventional explanation for this phenomenon of variance increasing with $K$ is given perhaps most prominently in The Elements of Statistical Learning (Section 7.10.1):

With K=N, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

The implication being that the $N$ validation errors are more highly correlated so that their sum is more variable. This line of reasoning has been repeated in many answers on this site (e.g., here, here, here, here, here, here, and here) as well as on various blogs and etc. But a detailed analysis is virtually never given, instead only an intuition or brief sketch of what an analysis might look like.

One can however find contradictory statements, usually citing a certain "stability" condition that I don't really understand. For example, this contradictory answer quotes a couple paragraphs from a 2015 paper which says, among other things, "For models/modeling procedures with low instability, LOO often has the smallest variability" (emphasis added). This paper (section 5.2) seems to agree that LOO represents the least variable choice of $K$ as long as the model/algorithm is "stable." Taking even another stance on the issue, there is also this paper (Corollary 2), which says "The variance of $k$ fold cross validation [...] does not depend on $k$," again citing a certain "stability" condition.

The explanation about why LOO might be the most variable $K$-fold CV is intuitive enough, but there is a counter-intuition. The final CV estimate of the mean squared error (MSE) is the mean of the MSE estimates in each fold. So as $K$ increases up to $N$, the CV estimate is the mean of an increasing number of random variables. And we know that the variance of a mean decreases with the number of variables being averaged over. So in order for LOO to be the most variable $K$-fold CV, it would have to be true that the increase in variance due to the increased correlation among the MSE estimates outweighs the decrease in variance due to the greater number of folds being averaged over. And it is not at all obvious that this is true.

Having become thoroughly confused thinking about all this, I decided to run a little simulation for the linear regression case. I simulated 10,000 datasets with $N$=50 and 3 uncorrelated predictors, each time estimating the generalization error using $K$-fold CV with $K$=2, 5, 10, or 50=$N$. The R code is here. Here are the resulting means and variances of the CV estimates across all 10,000 datasets (in MSE units):

         k = 2 k = 5 k = 10 k = n = 50
mean     1.187 1.108  1.094      1.087
variance 0.094 0.058  0.053      0.051

These results show the expected pattern that higher values of $K$ lead to a less pessimistic bias, but also appear to confirm that the variance of the CV estimates is lowest, not highest, in the LOO case.

So it appears that linear regression is one of the "stable" cases mentioned in the papers above, where increasing $K$ is associated with decreasing rather than increasing variance in the CV estimates. But what I still don't understand is:

  • What precisely is this "stability" condition? Does it apply to models/algorithms, datasets, or both to some extent?
  • Is there an intuitive way to think about this stability?
  • What are other examples of stable and unstable models/algorithms or datasets?
  • Is it relatively safe to assume that most models/algorithms or datasets are "stable" and therefore that $K$ should generally be chosen as high as is computationally feasible?
  • 2
    $\begingroup$ +1. What exactly is "mean" in your simulation results? Mean CV estimate of the generalization error (mean across 10000 datasets)? But what should we compare it to? It would be more meaningful to show the bias, i.e. root-mean-square-deviation from the true generalization error. Also, what is "true generalization error" in this case? True generalization error of the estimate on a given N=100 dataset? Or expected value of the true generalization error (expected value over all N=100 datasets)? Or something else? $\endgroup$
    – amoeba
    Commented May 20, 2017 at 7:54
  • 3
    $\begingroup$ +1. After short glance at en.wikipedia.org/wiki/… it seems that in this context stability means that an algorithm produces similar results on training set with $N$ and $N-1$ examples. Where similar means difference w.r.t. some loss function bounded by some low value $\endgroup$ Commented May 20, 2017 at 8:00
  • 1
    $\begingroup$ Apart from that, I have recently talked about it with @DikranMarsupial (who is probably one of our main experts on cross-validation here on CV) here in the comments - he suggested to read Kohavi's 1995 paper. Dikran was also talking about stability. Unfortunately, I did not follow it up since then. $\endgroup$
    – amoeba
    Commented May 20, 2017 at 8:01
  • 2
    $\begingroup$ I don't think so, @Jake. What I wrote invalidates your "counter-intuition", but the main "intuition" (about models from different folds being highly dependent) still can hold. $\endgroup$
    – amoeba
    Commented May 26, 2017 at 17:11
  • 2
    $\begingroup$ Another simulation supporting your conclusions that the variance decreases with $K$: stats.stackexchange.com/a/357749/28666. $\endgroup$
    – amoeba
    Commented Jul 18, 2018 at 11:44

4 Answers 4


This answer follows up on my answer in Bias and variance in leave-one-out vs K-fold cross validation that discusses why LOOCV does not always lead to higher variance. Following a similar approach, I will attempt to highlight a case where LOOCV does lead to higher variance in the presence of outliers and an "unstable model".

Algorithmic stability (learning theory)

The topic of algorithmic stability is a recent one and several classic, infuential results have been proven in the past 20 years. Here are a few papers which are often cited

The best page to gain an understanding is certainly the wikipedia page which provides a excellent summary written by a presumably very knowledgeable user.

Intuitive definition of stability

Intuitively, a stable algorithm is one for which the prediction does not change much when the training data is modified slightly.

Formally, there are half a dozen versions of stability, linked together by technical conditions and hierarchies, see this graphic from here for example:

enter image description here

The objective however is simple, we want to get tight bounds on the generalization error of a specific learning algorithm, when the algorithm satisfies the stability criterion. As one would expect, the more restrictive the stability criterion, the tighter the corresponding bound will be.


The following notation is from the wikipedia article, which itself copies the Bousquet and Elisseef paper:

  • The training set $S = \{ z_1 = (x_1,y_1), ..., z_m = (x_m, y_m)\}$ is drawn i.i.d. from an unknown distribution D
  • The loss function $V$ of a hypothesis $f$ with respect to an example $z$ is defined as $V(f,z)$
  • We modify the training set by removing the $i$-th element: $S^{|i} = \{ z_1,...,z_{i-1}, z_{i+1},...,z_m\}$
  • Or by replacing the the $i$-th element: $S^{i} = \{ z_1,...,z_{i-1}, z_i^{'}, z_{i+1},...,z_m\}$

Formal definitions

Perhaps the strongest notion of stability that an interesting learning algorithm might be expected to obey is that of uniform stability:

Uniform stability An algorithm has uniform stability $\beta$ wth respect to the loss function $V$ if the following holds:

$$\forall S \in Z^m \ \ \forall i \in \{ 1,...,m\}, \ \ \sup | V(f_s,z) - V(f_{S^{|i},z}) |\ \ \leq \beta$$

Considered as a function of $m$, the term $\beta$ can be written as $\beta_m$. We say the algorithm is stable when $\beta_m$ decreases as $\frac{1}{m}$. A slightly weaker form of stability is:

Hypothesis stability

$$\forall i \in \{ 1,...,m\}, \ \ \mathbb{E}[\ | V(f_s,z) - V(f_{S^{|i},z}) |\ ] \ \leq \beta$$

If one point is removed, the difference in the outcome of the learning algorithm is measured by the averaged absolute difference of the losses ($L_1$ norm). Intuitively: small changes in the sample can only cause the algorithm to move to nearby hypotheses.

The advantage of these forms of stability is that they provide bounds for the bias and variance of stable algorithms. In particular, Bousquet proved these bounds for Uniform and Hypothesis stability in 2002. Since then, much work has been done to try to relax the stability conditions and generalize the bounds, for example in 2011, Kale, Kumar, Vassilvitskii argue that mean square stability provides better variance quantitative variance reduction bounds.

Some examples of stable algorithms

The following algorithms have been shown to be stable and have proven generalization bounds:

  • Regularized least square regression (with appropriate prior)
  • KNN classifier with 0-1 loss function
  • SVM with a bounded kernel and large regularization constant
  • Soft margin SVM
  • Minimum relative entropy algorithm for classification
  • A version of bagging regularizers

An experimental simulation

Repeating the experiment from the previous thread (see here), we now introduce a certain ratio of outliers in the data set. In particular:

  • 97% of the data has $[-.5,.5]$ uniform noise
  • 3% of the data with $[-20,20]$ uniform noise

As the $3$ order polynomial model is not regularized, it will be heavily influenced by the presence of a few outliers for small data sets. For larger datasets, or when there are more outliers, their effect is smaller as they tend to cancel out. See below for two models for 60 and 200 data points.

enter image description here

Performing the simulation as previously and plotting the resulting average MSE and variance of the MSE gives results very similar to Experiment 2 of the Bengio & Grandvalet 2004 paper.

Left Hand Side: no outliers. Right Hand Side: 3% outliers.

enter image description here

enter image description here

(see the linked paper for explanation of the last figure)


Quoting Yves Grandvalet's answer on the other thread:

Intuitively, [in the situation of unstable algorithms], leave-one-out CV may be blind to instabilities that exist, but may not be triggered by changing a single point in the training data, which makes it highly variable to the realization of the training set.

In practice it is quite difficult to simulate an increase in variance due to LOOCV. It requires a particular combination of instability, some outliers but not too many, and a large number of iterations. Perhaps this is expected since linear regression has been shown to be quite stable. An interesting experiment would be to repeat this for higher dimensional data and a more unstable algorithm (e.g. decision tree)

  • $\begingroup$ +1 but I'd hope this thread can eventually be closed as the duplicate of the linked one (I'd wait until the bounty period is over and the discussions subdue, and see what answer ends up being accepted). I'll comment more later. $\endgroup$
    – amoeba
    Commented Jul 21, 2018 at 8:00
  • $\begingroup$ I'm not really convinced the question is a duplicate. My question uses the variance of LOO issue primarily as a way to frame the main questions, which are about trying to get an approachable explanation of what "stability" means -- see the bullet-pointed questions at the top and bottom of the OP. Speaking of which, while this answer is useful (+1), I can't see that you attempted to answer the stability questions... you do use the term a couple of times, but you seem to do so in a way that assumes the reader already knows what it means. Not sure I can accept the answer in its current form. $\endgroup$ Commented Jul 21, 2018 at 14:32
  • 1
    $\begingroup$ @JakeWestfall When I wrote that I "hope" that this thread can eventually be closed as a duplicate, I meant that I hope that an accepted answer in that thread will eventually be great enough that it will cover the things that you asked about :) Take a look at the Bengio&Grandvalet paper, Experiment 2. They show that using linear regression and Gaussian data they get minimum variance for LOOCV (that's your result too), but if the data contain some fraction of outliers then LOOCV has higher variance than 10-fold or so. I think this hints to what the relevant "stability" is about. $\endgroup$
    – amoeba
    Commented Jul 23, 2018 at 16:36
  • 3
    $\begingroup$ I love it @XavierBourretSicotte. Thanks for doing such great work on this answer. $\endgroup$ Commented Jul 24, 2018 at 13:47
  • 1
    $\begingroup$ Yes, quoting this paper: pdfs.semanticscholar.org/bf83/…: "A stable algorithm has the property that replacing one element in its learning set does not change much its outcome. As a consequence, the empirical error, if thought as a random variable, should have a small variance. Stable algorithms can then be good candidates for their empirical error to be close to their generalization error. $\endgroup$ Commented Oct 13, 2018 at 1:28

I will give my answer in context of the paragraph you cite:

With K=N, the cross-validation estimator is approximately unbiased for the true (expected) prediction error, but can have high variance because the N "training sets" are so similar to one another.

The CV estimator of the true (expected) prediction error is based on a training set example, so here, the expectation is over training set samples, when I understand that correctly.

So, what this paragraph regarding "high variance" then says is that there is a "high" difference between expected error and the error estimated by CV (which is here, the average over folds).

This makes sense because the model is fit to a particular training set and because all training folds are so similar within leave-one-out. However, while the training folds are very similar within a CV round, the estimate probably differs by a lot if we swap training samples for CV. In k-fold CV, since we "diversify" the training folds, we have some averaging affect, and across k-folds, the estimates then vary less.

Or in other words, the leave-one-out CV estimator is basically almost like a holdout method were you don't rotate folds and base your error estimate on one validation set. Again, over training examples, there will be a high variance compared to estimates from k-fold, where you average over folds by already training somewhat diverse models within k-fold round (in other words, if you swap training sets, the estimates of the error via k-fold probably won't vary that much).


When I read some answers here on cross-validated and the internet in general, I think there seems some confusion to which estimator we are referring. I think some people refer to a model having high variance (with is ML talk for the loss having a dominating variance component) vs high variance of the k-fold CV estimator. And, another set of answers refer to variance as the sample variance regarding the folds when someone says "k-fold has high variance". So, I suggest to be specific, because the answers are different in either case.

  • $\begingroup$ When discussing variance my assumption is that we are talking about the variance of the CV estimator on training set D as defined here: stats.stackexchange.com/questions/365224/… and here: stats.stackexchange.com/questions/325123/…. Yves Grandvalet and Bengio argue in their 2004 paper that the CV estimates the expected prediction error. You can see his response here: stats.stackexchange.com/a/358138/192854 $\endgroup$ Commented Oct 13, 2018 at 1:23
  • $\begingroup$ If you are to base your answer on different definitions of variance, I think it would be helpful to add the formal definitions and formulas. Perhaps I should do so in my answers as well.. $\endgroup$ Commented Oct 13, 2018 at 1:24
  • $\begingroup$ Yes, I need to review the literature a bit and should add some formulas to the answer. The quote from the The Elements of Statistical Learning is still intuitive to me though, that LOOCV has a high variance if the model has a high variance, because it is an average over the folds. If a model has high bias, both LOOCV and any k-fold estimators should have low variance (independent of bias) because the predictions will not vary so much. But the point in the paragraph was prob. that LOOCV in comparison to k-fold for most cases $\endgroup$
    – user39663
    Commented Oct 13, 2018 at 3:28
  • $\begingroup$ The quote has been shown to be incorrect - at least as a generalization - see the multiple papers quoted in my answers $\endgroup$ Commented Oct 13, 2018 at 5:13

We've been through this before -- you're getting too mathematical about a dead horse. See Ron Kohavi's (Stanford-Univ) classic paper on CV and the bias-variance dilemma here. When you're done reading this, you won't want to perform LOOCV, and will likely be attracted to 10-fold CV and/or bootstrap-bias CV.

You also have to think about large datasets, for which LOOCV is way too computationally expensive. At present, LOOCV is not really an option in most groups' workflows/pipelines.

What precisely is this "stability" condition? Does it apply to models/algorithms, datasets, or both to some extent?

In the universe of all cost functions and in the universe of all feature sets, I would not assume there is an overall "stability" index, because it would not be inadmissible, and would be too prone to breaking down under an infinitely large set of conditions. Fundamentally, $k=n$ is appropriate when the d.f. and/or # parameters is so large that more training data are needed. Bias will also be greater for $k=n$, since more data are used, and variance would be artificially zero, since the training datasets are too similar to one another. You would also be learning more noise in the data when $k=n$.

LREG as a classifier would work when the data are linearly separable, but on average its bias would be too high, since many datasets are not linearly separable.

Is there an intuitive way to think about this stability?

Not in my view -- since there is no general rule on stability.

What are other examples of stable and unstable models/algorithms or datasets?

This is open-ended and too broad, since an infinitely large number of responses can be contrived, which would not be helpful.

Is it relatively safe to assume that most models/algorithms or datasets are "stable" and therefore that $K$ should generally be chosen as high as is computationally feasible?

No. No. Relying only on $k$ assumes that you believe the data. An example is Random Forests, for which there really is no $k$. While roughly 37% of the data will be used for testing (on average, 37% of objects are not selected when sampling with replacement), there are e.g. 5,000 different datasets (bootstraps) each of which are split into training/testing differently. Your example pulled from papers assumed that each dataset used was a true realization of the data -- which is an erroneous assumption.

Given bootstrapping, the rule of stability surrounding $k$ is admissible, since the data sample used for a straightforward CV approach involving $k$ is not a true realization of the universe of all data from which the sample was obtained.

  • $\begingroup$ Thanks for your comments, but this does not seem to answer the question. $\endgroup$ Commented Oct 7, 2017 at 15:23
  • $\begingroup$ See the appended answer to the OP. $\endgroup$
    – user32398
    Commented Oct 8, 2017 at 17:06
  • 3
    $\begingroup$ Only skimmed the article, but they really seem to make their claim about 10x being best on extremely shaky ground. I can't believe that has 7k citations. With that said, there seems good reason to believe there's much benefit to more than 10x. Will give a more thorough reading when I have a chance. $\endgroup$
    – Cliff AB
    Commented Oct 8, 2017 at 18:17

This answer focuses not on stability, but on a different related issue that I have not seen addressed in the answers/comments above.

There is "conventional wisdom" about LOOCV having higher variance, e.g. quoted from ESL in the question above. This conventional wisdom makes sense to me only if CV with different fold sizes were estimating the same thing. But if the full dataset size $n$ is fixed, then 5-fold CV is estimating MSE for models trained on $n\times4/5$ cases, while 10-fold CV is estimating MSE for models trained on $n\times9/10$ cases, and so on. These are different targets of estimation, so there's no reason to expect a simple relationship between their estimates' variances.

Instead, what would happen if we think about using CV to estimate MSE for a fixed training set size?

I modified @JakeWestfall's R code (linked in the question) to carry out 2-fold, 5-fold, 10-fold, and LOOCV with a fixed training set size. I chose to use $n_{train}=36$ to allow for integer sample sizes, so that the full dataset sizes were:

  • $n=72=36\times2/(2-1)$ for 2-fold
  • $n=45=36\times5/(5-1)$ for 5-fold
  • $n=40=36\times10/(10-1)$ for 10-fold
  • $n=37=36\times37/(37-1)$ for LOOCV

In other words, for each rep of the simulation:

  • Generate a new dataset of size $n=72$
  • Carry out 2-fold CV on this full dataset
  • Take just the first 45 cases of the full dataset, and carry out 5-fold CV (so that we have five instances of [training on 36 cases and testing on 9 cases] from among the same 45 cases each time)
  • Similarly for 10-fold on the first 40 cases of the full dataset
  • Similarly for LOOCV on the first 37 cases of the full dataset

Results from 10,000 reps:

##          k = 2 k = 5 k = 10 k = n
## mean     1.122 1.123  1.123 1.123
## variance 0.052 0.068  0.073 0.077

Unsurprisingly, the means are all the same. These are all unbiased estimators of the MSE for models with $n_{train}=36$.

But now that $n_{train}$ is fixed, the variance of $\hat{MSE}$ increases with k. This, to me, matches the intuition from ESL and others. For each rep of the simulation:

  • 2-fold CV is almost the average of 2 independent estimates of $\hat{MSE}$. (Well, not quite. It's the average of $\hat{MSE}$ over two independent $\hat f(x)$, but there is dependence between training and test sets.)
  • Meanwhile, LOOCV is almost just a single estimate of $\hat{MSE}$. (It's the average of $\hat{MSE}$ over $n$ estimates of $\hat f(x)$, but these $n$ fitted models are so correlated as to be nearly identical, unless there are major outliers.)

By this intuition, LOOCV should have higher variance than 2-fold CV; and 5- or 10-fold should be somewhere in between... if they are all trying to estimate the same thing. And indeed, the simulation supports this intuition.

Back to the OP's question, and as a contrast to @XavierBourretSicotte's answer: when $n_{train}$ is fixed, "LOOCV has higher variance" does not require instability.

Of course, this does not tell us what value of k to choose in the standard situation where $n$ is fixed and $n_{train}$ varies with k! But I hope it helps to illustrate (1) where the "LOOCV has higher variance" intuition came from, and (2) why that intuition breaks down in the standard situation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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