bootstrapping vs. "repeated cross validation"

Question

For a research project, I conducted the following methodology. The dataset was of size $N$.

$B$ times, I:

1. took a random $N/2$ rows and trained my model, which finds the optimal size $M$ of a system of resources

2. took the other half of the rows, the other $N/2$, and simulated the system assuming the size of the system was $M$. This led to a performance metric I will denote $E$.

I then reported the mean and confidence interval of $E$ across all $B$ iterations.

My questions are:

1. Is this bootstrapping without replacement or "repeated 2-fold cross validation"?
2. If the answer is both, what exactly is the difference between bootstrapping without replacement and "repeated cross validation"?

My methodology is summarized in this wikipedia, but strangely it is not called bootstrapping, but I thought this was bootstrapping, hence my confusion: http://en.wikipedia.org/wiki/Cross-validation_%28statistics%29#Repeated_random_sub-sampling_validation

Answer 1

Q. 1. Is this bootstrapping without replacement or "repeated 2-fold cross validation"?

Q. 2. If the answer is both, what exactly is the difference between bootstrapping without replacement and "repeated cross validation"?

It is neither. But the differences between sampling methods are subtle.

1. It is not classic bootstrap because your $B$ training samples are not drawn with replacement. (For the record: classic bootstrap also imposes the condition that a sample consists of exactly $N$ draws with replacement.)

2. It is not "bootstrap without replacement" because you hold the size of the training sets fixed at $N/2$. (In classic bootstrap the number of unique observations in a training sample is random with expected value $0.632N$ for sufficiently large $N$. More on that here.)

3. It is not repeated 2-fold cross-validation (CV) because CV imposes a constraint on the validation sets, $\{ V_i \}_{i=1}^B$, namely that $V_i \cap V_{i+1} = \emptyset$ for odd $i$. (See also this answer.)

So what is it then?

4. The wikipedia reference you provided is correct. It is rightly called "repeated random subsampling (validation)". Sometimes also, "Monte Carlo subsampling" (with fixed subset size). The difference with the related repeated CV method, is simply that it relaxes the disjointness condition on the validation sets. In repeated random subsampling each set drawn is independent of the others.

Answer 2

Bootstrapping always means that from your set of n samples you draw n samples with replacement. This means you will almost certainly have duplicates in your data set.

In n-fold cross validation you cleanly separate your data in n approximately equally large subsets, which do not overlap. What you are doing is indeed "repeated 2-fold cross-validation".

I don't think there is a consensus yet which methology is better and it probably depends on your application. However, I would suggest using 10-fold cross validation instead of two-fold. If you are still in a range where your model fit improves with additional training samples, then using just half the data will give estimates that are too pessimistic.