Right procedure to picking the value of hyper parameters I've asked a similar question before about cross-validation here and here. I've received many useful answers and benefit from the discussions on these websites. Here I summarize my original question and my thoughts after the discussion. Then I will raise an additional question based on my updated understanding about cross-validation.
My original question was motivated by my own experience with kaggle titanic tutorial to predict the survival condition of passengers. In that competition I have a training data set ($D$) about 1000 rows with both the value of the predictors and the response variable (i.e., whether a passenger is survived or not). Then we have a test data set ($T$) about 400 rows where we only have the values of the predictors and not the response variable. The task is to make predictions on the test data set and then after submission, kaggle will tell you what is the accuracy rate of your submitted prediction.
In building the machine learning model, you often need to specify the value of "hyper parameters", e.g., the L1-penalty in the logistic regression. The way to set hyper parameters originally in my head (and I think this is also what I've been taught) is: run $K-$fold CV on $D$, then choose the hyper parameter value that gives the best CV performance, then use that chosen hyper parameter value to fit on the entire $D$ and use that to generate predictions and submit. This is how I implemented (I use XGBoost as my model, which has many hyper parameters). But I found that I submitted my prediction several times (generated by the same XGBoost models but with different hyper parameter values). Interestingly, the performance on $T$ and the CV performance have negative correlation.
Then people told me that if I pick the value of hyper parameters based on the CV score it is still overfitting, i.e., overfitting with that $K$ specific CV folders. Now I kind of convinced myself that this explanation makes sense. Here I first elaborate this explanation.
Assume we only split $D$ into a "Fit" data set $F$ that is used to fit the model and a validation set $V$ (the idea is the same as $K$ fold CV). If both $F$ and $V$ are large (e.g., infinity theoretically), then the performance of the model on $V$ is the true performance(i.e., expected accuracy of the model on an infinitely many independent test data set, which is our $V$). In this case, by definition, if model $M_1$ has better performance on $V$ than model $M_2$ (I mean same type of models but with different hyper parameter value), then $M_1$ is better than $M_2$. However, even in this case, if you let these 2 models to make predictions on $T$, which is a finite data set (for extreme case, consider $T$ only has one row), there is still no guarantees that $M_1$ will performs better than $M_2$ on $T$, due to the randomness in $T$. But in this case, as both $F$ and $V$ are large (infinity), the performance on $V$ should be a good indication of whether we have picked the "right" value of the hyper parameters. The key point here is that when $F$, $V$ and $T$ are all infinite, then the performance on $V$ is indeed the same as the performance on $T$. Hence, the performance on $V$ is the right criterion to picking value of hyper parameter. And I think this "justifies" the logic of picking value of hyper parameters based on CV performance.
A side note: even if we have $D$ being infinity size, if we don't split $D$ into $F$ and $V$, directly fit the model on entire $D$, then that will still have overfitting issues.
Now in reality, when $D$ is not that large (even if $D$ has many rows, but we could have many features at the same time, which can still render the $D$ being "small"), then after we do this $F$ and $V$ splitting to pick hyper parameters, we are still overfitting on this specific $V$. Hence, there is no guarantee that the winner on $V$ will still be the winner on $T$ even if $T$ has infinity rows (recall that when $D$, $V$ and $T$ are all infinite, then the winner on $V$ will also be the winner on $T$; if $T$ is small, then the winner on $V$ will not necessarily be the winner on $T$.)
So people suggested that we divide $D$ into 3 pieces: $F$ to fit the model; $V$ to choose hyper parameters and $T'$ to do performance assessment. So after the $V$ step, we run the model (with the winner hyper parameter in $V$ step) on $T'$ to have an idea of how this model will perform on another independent test data set, e.g., $T$. Then, we must stop tuning the hyper parameter after we saw its performance on $T'$, since if we keep on tuning the hyper parameters to get a better and better performance on $T'$, then we are still overfitting on $T'$, which is the same thing as we overfitting on $V$.
Then, based on this logic, in practice, all those data set are finite, to pick the value of the hyper parameters, you shouldn't look at their performance on $V$, as a good performance on $V$ would just mean the model is overfitting on $V$; you should't also look at their performance on $T'$, as it is also overfitting on $T'$. Then my question is: what criterion should I looking for to pick the best value of the hyper parameters so that it will generate better performance on $T$ (assuming $T$ has infinite rows) than the model with other value of the hyper parameters? We know that when $D$ is infinite, then this goal can be achieved by just split $D$ into $F$ and $V$ and looking at the performance on $V$. But now $D$ is finite.
 A: Short answer: you are assuming that cross-validation is necessary.  Once you realize that it is only a crude approximation of Bayesian optimization, you can use a better approximation, such as sequential model-based optimization with Optuna.
Choosing which hyper-parameters to use can be based on a score of a fitted model evaluated on data which were not involved in fitting (then re-fitting a new model and seeing if you get an improvement to the score).  See my sample code on Github for an example of searching for optimal hyper-parameters with explicitly Bayesian tools and methods.
You do not need to perform cross-validation, but you always need to apply the theory of validation.  Kaggle is doing one type of validation for you when you submit the predictions and they score according to the "true" labels.
If you are using machine learning to fit your model, you can also perform validation within the training loop (actually you always do, at the end of each training epoch).  In this case, to avoid confusion, it might help to call the other type of validation "testing" instead.
A: You are correct, we are only assuming that the train set and validation set are representative enough for the test set. If they are not big enough, or the split was not made on random, so they differ in distributions, they may not give you trustworthy results.
However, same is true for the data you have for training the model vs making predictions in the wild, you also have no guarantees that your data is representative enough to obtain a model that generalizes outside the data. With cross-validation, we simply assume that if we trust that the data we use for training the model is good enough, we can sub-sample it as well, and the sub-samples should be good enough taken the size of the data is not too small.
We use cross-validation because it is a simple, generally applicable procedure and there’s not many good alternatives. All the other methods make additional assumptions, so they have additional points of failure beyond the data size and random sampling.
