How to think about prediction error that is not convex in hyperparameter, or over the course of training

Question

Take the following case of a hyperparameter and prediction error:

Imagine that the hyperparameter is a L2 penalty or a dropout rate -- something that we think that should have a single sweet spot -- too high and you're underfit and too low and you're overfit.

I keep getting nonconvex plots like the one above when doing cross-validation.

I guess this just points to a lot of noise during training -- I've got a lot of variables for a modest sample size, and I need to regularize heavily to get a good model. But still I'm a little bit unsure whether this sort of thing might point to a bug in some aspect of my implementation.

Has anyone come across this sort of thing before? And did you just shrug off the nonconvexity and go with the model that minimized the prediction error?

If so, that begs the question: why not just compute a prediction error at each update during training, saving any set of weights that minimizes prediction error -- even if the model is nowhere near converged. Basically letting the noise work in your favor. This seems appealing, because sometimes I get really low prediction errors early on, only to have them evaporate as the loss function declines.

This seems horribly unprincipled, but I ask myself "why should I care if it is"? And "is it unprincipled anyway?"

Answer 1

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.