Question number 1: What happens if the validation metrics plateau?
A plateau in the validation metrics means that additional variables, parameters or parameter tweaks (depending on what you are tracking in validation) are not improving performance but not degrading it either. They are providing no additional information.
Should I relax my regularization parameters a bit because I am underfitting? (as to allow for a U shape in the validation metrics graph? U for logloss inverse U for AUC etc.)
That would be a reasonable option to explore to ensure your restrictions are not too harsh. However, since you would only know this after exposing the validation set then you will no longer be testing independent of model tuning, it will be a validation set for your model limits. This would mean that if you want independent validation of your final model you will need to have a further independent test set.
What if it still is stuck in the same value?.
A typical response is Ockham's razor, keep the simplest version that gives the required level of performance.
In that case what happens if I keep training without reaching an outrageous gap?
By Outrageous I assume you mean that the difference is negligible for all practical purposes? This would be practical significance rather than statistical significance, and would require you to define what an 'outrageous gap' or minimally practical difference would be. Then apply Ockham's razor same as if the plateau is completely flat.
Question number 2: We generally want our training and validation metrics to hold relatively the same values, is that correct?
That is the ideal, it provides some confidence that the model is stable transferring from the training scenario to an independent implementation.
However, what happens if for some reason the validation set and the training set are not representive of each other 100%?
They never will be 100%, even if it is one data collection subsequently split into two sets. Based on stochastic sampling you would expect there to be some differences between the two sets. Ideally you want the differences to be unbiased. Statistics is not about conclusions but risk assessment and management, the difference you encounter between the training and validation sets gives you a first measure of risk associated with deploying your model in new data.
More specifically can there be some cases where the model is trained correctly (thus higher training metrics) and not overfit (i am not talking about huge gaps), while these cases are missing in the validation set (thus the validation metrics plateau)?
Overfitting is always with respect to samples not included in the training. The value of CV during training is we can internally assess the risk of overfitting by holding out a sub set of samples on multiple iterations, to get a first estimate of overfitting. But what is overfitting? Over fitting is using irrelevant noise in the model that boosts training performance because it explains noise that is specific to that set of data making it appear to describe it better. The danger is that in new data it will be irrelevant and so will provide random and unpredictable deviations from the true value. If the test data simply does not show a sub-group of variation that was present in the training set you will indeed see a plateau in the regions associated with that unrepresented variation. The data may be irrelevant to your test data but may still be relevant to other sets of data. It may say more about the suitability of your test set than you model. The main concern with overfitting is that it really has fitted to noise and you see a drop in performance since the noise is not reproducible in any new data.
I am asking because In real world, sometimes it is hard to gather huge amounts of data, thus some cases might not be well-represented. So even by performing k-fold validation n times, I may still be depending on the luck of the split; enough cases in the training set and enough of them in the test set. By keeping a very close gap in this situation I am running the risk of underfitting my model, is that correct?
That is correct, that is the fine line we try to walk in developing models of the real world. It should be noted that training a model and testing it once rarely warrants releasing it on the real world. It is all about risk evaluation. If you have a huge training set and validation set and independent test set* in a low risk situation you may be able to persuade stakeholders to use your model in the real world. It is typical however to have to incrementally demonstrate value in different settings, and anytime the model is to be deployed in a new setting it should be validated for that setting. There may be times when validation fails and the model needs updated to account for new variation.
If my way of thinking is not flawed, would a good solution be to allow for slightly higher metrics in the training set?
Depends on whether someone is doing leave one out CV which is unbiased but inaccurate or K-folds CV (as you indicate your are) which is biased towards optimistic but tends to be a more accurate estimate of performance. If using K-folds you should assume there will be some drop in performance, your hope is that it will be within the bounds of statistical and practical acceptability.
*Note: I recognise that people use validation and test set interchangably, with some preferring to use one or the other to refer to hyperparamater tuning set and the other to a final test of the model where no tweaking is allowed. In this case I am using 'validation' for the hyperparameter tweaking set.
