On a reasonably sized data file, I do a random split and get the validation and test sets (80/20 let's say). I perform a (repeated) k-fold CV on the validation portion of the data and adjust all the parameters needed and finally come up with my best model. Then I try this model on the test set (20%) I never used before and find out that it performs pretty well. Now how do I know that I wasn't just lucky in my selection (though randomised) of the test portion I set aside in the first place? Is there a procedure (similar to k-fold CV we used for the validation portion) that compensates for this effect?
When learning a model, the aim is to be able to generalize well to the distribution which the data came from, and using a testing set is kind of a proxy for that, because we do not have access to this distribution.
Generalizing well essentially means that you were able to learn factors that are intrinsic properties of that distribution, and so you are able to perform well on any data sampled from that distribution. How do we know what are these intrinsic properties? We do not, and must make assumptions based on the data we can observe. So when you see something that is common to all the data samples you have access to, the assumption is that this must be a parameter of the distribution.
When your model trained on the validation set performs well, it means it has learned some parameters intrinsic to that set, but when it also performs well on the test set, it must mean that whatever it learned (that led to good performance) are also present in the test set. So in the absence of more data samples from that distribution, you can assume that these common parameters are properties of the distribution.
However if you really wanted to guard against a lucky split, you could repeat this training-testing process multiple times on different random splits and see whether the values of the parameters it learns are more or less the same. If yes, then you can be certain that there was no random luck involved. But it's likely excessive. It's possible to have an unlucky test set, consisting only of outliers for example, but if the model performs well on both seen and unseen data, then it must mean that the split led to a test set that is representative of the same distribution that the validation set came from.
Is there a procedure (similar to k-fold CV we used for the validation portion) that compensates for this effect?
As @jxd1011 already pointed out, you can do (repeated) cross validation also at that upper level of measuring generalization performance.
However, I thought it worth while to point out that search terms for this approach ("inner" cross validation for model optimization + "outer" cross validation for final estimate of generalization error) is known as nested or double cross validation.
At high level, if the data is large enough, 20% of the testing data, can be representative to the population.
In addition, there are other re-sample methods available. For example, repeated cross validation will repeat the process many times and reduce the chance of getting a skewed training or testing data.
Please check this post for details.