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.