How to think about prediction error that is not convex in hyperparameter, or over the course of training
The underlying true performance is likely convex or at least likely only has one minimum, but you don't know the true underlying performance, you only get a stochastic sample with a tiny sample size because you apply cross validation. The performance is a random variable where you are interested in the expected value, but you only get k samples where k is the number of folds. I think if you would increas k your curve would look more smooth. That said, even if your hypothesis counts in general, for this specific set there might be some weird data points that make random settings perform worse than expected still.

The problem with your suggested approach is that you are treating this noise as signal. If you have a normally distributed random variable, you sample 1000 times from it and take the max value, this will be much higher than the true expected value. An alternative explanation could be that it is not noise, but that you are actually overfitting. Then your approach makes more sense, and if the samples surrounding it during training are also relatively low then this is actually a good strategy, it is called early stopping, a different form of regularization and commonly used in Neural Networks.

EDIT: I think you are right that I didn't explain that analogy very well, we are trying to optimize a function g(x) where x is our hyperparameters and g(x) is a random variable function, let's say it had a true underlying value f(x) and additive noise $\epsilon$. If $\epsilon$ is Gaussian distributed with a high variance compared to the underlying value, if we take the max without looking at anything else we could take one that had lucky noise. I think what we are seeing in your graph is relatively high variance due to low sample size of your data (which means small validation sets in your folds) whih will lead to non-convex behaviour. That said, your explanation of early on seeing lower validation losses does imply overfitting which early stopping can help with.