Why leave-one-out cross validation fails to detect overfit? I have an extremely simple classification problem. My data-set looks like this:
| feature | target |
| A       | 1      |
| A       | 1      |
| B       | 0      |
| A       | 0      |
....................
| A       | 0      |
| B       | 0      |
| A       | 1      |

As you can see the feature cant take only two values (A and B) and the target is always either 0 or 1. My goal is to predict probability of target = 1 given a value of the feature.
I construct a data set such that probability of target = 1 does not depend on feature and is equal to 0.5. I have generated a data set in which feature is equal to A 1000 times and equal to B also 1000 times.
Just by chance for the feature = A 1 is observed 515 times out of 1000 and for the feature = B 1 is observed 482 times out of 1000.
I have two alternative models. The first one states that probability of target = 1 does not depend on values of the feature (this model is correct per construction). The second model states that probability of target = 1 depends on the value of the feature (this model is an overfit per construction).
Now assume that I run a standard leave-one-out cross validation to find out if the second model is an overfit or not. When I take one observation with feature = A out, the number of 1s for feature = A will fluctuate between 515 and 514 and, therefore, the predicted probability for A will be either 515 / 999 or 514 / 999, which is very close to in-sample probability (515 / 1000). So, the second model will be better than the first model not only in-sample but also out-of-sample (obtained via leave-one-out cross validation)!
So, it means that we were not able to detect an over-fit with the leave-one-out procedure and the second model, which has smaller predictive power, wins the first model, which has better predictive power.
Is it a known problem? How to deal with this? Is there a procedure that is free of errors like this?
I understand that one could run a test that checks if there is statistically significant difference between probability of 1 for different values of features but my question is about cross-validation and leave-one-out specifically. For more complex data we do not have a test, we run a cross-validation there and I want to be sure that for those more complex cases the cross-validation does not fool me like in the described simple case.
 A: The problem here is that your dataset is a bit of an outlier in the population of datasets from the stated data generating process, in that the feature is more correlated with the target than average.
If the feature and target were randomly generated with equal probabilities, then the probability that the feature matches the target is a Bernoulli trial with probability 0.5.  In this case, out of 2000 samples, there are 1033 = 515 + (1000 - 482) "successes", and I think the probability of there being 1033 or more "successes" from 2000 trials is only about 0.073.
Now the statistical distribution for the "test set" in each fold of the leave-one-out data is the same as that for the "training set", so the test data is also an unlikely sample from the true data generating mechanism, so it can't be expected to give the "right" answer.
There is nothing wrong with leave-one-out cross-validation, the problem lies with being unlucky in the sample of data you have obtained.
One thing you might want to do is to compute the Bayes factor comparing the two hypotheses, which I suspect would tell you that the evidence is not strongly in favour of either hypothesis, which is reasonable as the difference is only in 33 of the 2000 observations.
Another way of looking at this would be to use NHSTs and consider the power of the test, which would probably be rather low.  If you took either model as H0 in the test, you would be unable to reject it, which indicates that there isn't enough data to be confident of a difference in performance between the models.  Essentially you need a lot of data to be able to be "confident" that a very small effect (such as this one) is not a random artefact.
The key point is that cross-validation can provide evidence of over-fitting, it does not itself provide a reliable indicator of over-fitting.  You need to consider the uncertainties involved.
A: Your example is one of purely observation-driven modeling. And your observations indicate that there is a relationship between your feature and your target. Yes, it's a weak association. But that it is overfitting is not evident from the data you have observed! You can't very well accuse LOOCV of failing to detect overfitting that you only know is there because you know the true data generating process (DGP), i.e., you have information that is not available to the LOOCV method.
Also, "overfitting" is not a Boolean attribute. On the one hand, we never know the true DGP outside simulations, so we can never truly say there is overfitting: anything could conceivably have an influence on our outcome. On the other hand, if you believe in "tapering effect sizes", we will never be able to capture all influences, so we will always have underfitting.
Thus, it makes more sense to think of "overfitting" as a continuum. How much worse does adding a predictor make my model for future expected losses (which we again will only be able to estimate, unless we know the true DGP)? Thus, we have to think about how much signal there is in our data. In the present case, the overfitting is quite weak, and as Dikran says, it is hard to distinguish a weak effect from no effect whatsoever. And adding this feature will only have a very small effect on future predictions, so the overfitting, measured on a continuum, is small.
Per above, you are modeling purely based on the observations here. Essentially, such a model has no predilection towards a simpler model, like the one without an effect of the feature. There are various ways of including such a predilection. Essentially, we would bias our models towards simplicity, and per the bias-variance tradeoff, this may very well improve future predictions. In the terminology above, our overfitting, if present, would be weaker.

*

*We could explicitly run a Bayesian model with a prior on the impact of the feature.

*As you write, we could include elements of NHST, only accepting the more complex model if the improvement in fit is statistically significant.

*Or we would use the "one standard error rule", which is very often used in cross-validation.

A: What happens here is that you compare one model that you know to be the true one with fixed true parameters to another model that will estimate these parameters. Obviously if you fix the parameters at the true values, you will normally be better on new data than if you estimate the parameters. But with a certain probability, any model selection method will select the model with estimated parameters, so will appear to be overfitting. This is not a specific problem with LOO-CV but applies to any model selection approach. If you compare a simpler model that you know to be true with a more complex model, the more complex model can be selected with a probability that is not negligible, in which case overfitting takes place.
If you set up the problem so that underfitting cannot happen, you will overfit with a certain probability and underfit with probability zero, so on average overfitting will happen. Only if you also look at what happens in case the more complex model is true you get a fair assessment of the model selection procedure.
Note furthermore that LOO-CV is known to be asymptotically equivalent to the AIC, which even asymptotically will overfit, see https://www.jstor.org/stable/2984877 (Note that I haven't made an effort to check whether potential assumptions in that paper apply here.)
The AIC (and equivalently LOO-CV) is however asymptotically good at finding an optimal prediction rule (for which overfitting is not as bad as underfitting). Note that in the given setup, if you just try to predict the target 1 or 0, rather than predicting their probabilities, any rule will be wrong 50% of the time, so that the "overfitted" model will not be worse than the true one when it comes to point prediction.
A: Overfit meaning: you get better results on your train set then on your test set.

*

*There is no clear definition of a train / test set here


*lets assume we divide your uniformly dataset of 1000 data points into: 700 data points in the train set and 300 in the test set. becuse it is uniformly distributed, you can achieve an accuracy of ~0.5 on your train set. Now, you test your model on your test set. if the performance is about the same (we expect ~0.5 accuracy), this means there is no overfit in your model.


*regardless of the overfit question, an accuracy of ~0.5 mean that your model cannot predict very well (on any set)
