Stopping criteria for optimisation

[sambitmishra98]

I am trying to use Knowledge Gradient acquisition function to tweak and run a Navier Stokes solver. My cost function (simulation wall-time) has an error which is typically around 1%. My goal is to minimise the cost function untill I am fairly certain that the theoretical best candidate in the domain and the best candidate generated after X iterations are within 1% relative difference of each other.

Whenever I use Bayesian Optimisation to get good candidates, I run into the following uncertainties and questions:

1. Different random seeds converge to different best candidates after 100 iterations. Although the candidates have similar costs, I am not sure if the model generated from dataset from one seed is better than that of the other.
2. Probably since the cost is noisy, I am unable to replicate the results. When I am trying to use one seed to get the same set of 100 candidates, I would at least want the candidates being generated in the second round to be replicated with a deviation of maybe 1% to the first round of 100 candidates.
3. How would one know when to stop searching for better candidates? For my purpose, I want to be able to stop the simulation when I know that any candidate that is suggested beyond a certain number of iterations will not have a cost that is below 99% of the cost of the best candidate I have untill now. Is there a metric one can use to determine this?

[Balandat]

Different random seeds converge to different best candidates after 100 iterations. Although the candidates have similar costs, I am not sure if the model generated from dataset from one seed is better than that of the other.

By this do you mean the random seed of the optimization algorithm (rather than the random seed of your solver and/or initial conditions)? One reassuring thing is that the costs are similar - it may well be possible that there are multiple local minima with cost very similar to that of the global minimum. If that's the case then the fact that the optimizers between the seeds are different isn't really anything of concern. And whether a particular model is "better" than the other - that's really something you will have to assess, that's not something the algorithm can help with (all it sees is the cost function). Are there other metrics beyond the simulation wall time that are of interest?

Probably since the cost is noisy, I am unable to replicate the results. When I am trying to use one seed to get the same set of 100 candidates, I would at least want the candidates being generated in the second round to be replicated with a deviation of maybe 1% to the first round of 100 candidates.

Same point as above - if the response surface of the black box function you're optimizing here is multimodal with local minima of very similar performance, then the fact that the candidates themselves aren't replicated between rounds isn't necessarily an issue.

How would one know when to stop searching for better candidates? For my purpose, I want to be able to stop the simulation when I know that any candidate that is suggested beyond a certain number of iterations will not have a cost that is below 99% of the cost of the best candidate I have until now. Is there a metric one can use to determine this?

That's a great question. Since we have an underlying probabilistic surrogate model, we can reason about these things. Since everything is probabilistic, the model will never be certain that such candidate cannot be found. But you could work with a probability threshold, say you want this to hold with probability at least 1-alpha for small alpha. Then what we'd need to compute is P(min_x f(x) < 0.99 f*), where f* is the best observed point so far. If that is less than alpha you can stop. There are different ways to estimate this; one of them is to Monte Carlo estimate it by drawing a bunch of function samples from the model, compute the respective minimum of each, check whether it's less than 0.99 f* and then count the frequency. If your domain is low-dimensional you can also get away with sampling function values at a dense grid of points instead (but that quickly becomes infeasible as the dimension grows). The big caveat here is that this is all dependent on the model being good. If there is model mismatch, then a decision based on the (bad) model might be very wrong. Thing thing to do about this in practice is to evaluate the model quality (ideally by means of cross-validation)

cc @abbas-kazerouni, @j-wilson

[sambitmishra98]

One reassuring thing is that the costs are similar - it may well be possible that there are multiple local minima with cost very similar to that of the global minimum. If that's the case then the fact that the optimizers between the seeds are different isn't really anything of concern.

This is true. The Navier Stokes solver I am using as the blackbox to get the cost function surely seems to have multiple good solutions which are within the error bounds. Beyond a certain point (say around 200 iterations) the optimisation process gives a slightly better solution maybe after 50 more iterations. Currently the stopping criteria that I am using is that I check if the optimiser has suggested the best candidate in the last 50 iterations. If not then I stop the optimisation.

Monte Carlo estimate it by drawing a bunch of function samples from the model, compute the respective minimum of each, check whether it's less than 0.99 f* and then count the frequency. If your domain is low-dimensional you can also get away with sampling function values at a dense grid of points instead (but that quickly becomes infeasible as the dimension grows). The big caveat here is that this is all dependent on the model being good. If there is model mismatch, then a decision based on the (bad) model might be very wrong. Thing thing to do about this in practice is to evaluate the model quality (ideally by means of cross-validation)

So based on what I understood, the following is the workflow I will try to follow. Let me know if this makes sense:

1. Generate around 50 cndidates and get their costs using qKG method (mainly because it explores the space quite well).
2. Check for model accuracy. Keep using KG method untill model accuracy is high enough using LOOCV (need to figure out what high is) then use qNEI method (Because its cheap and exploits more than qKG).
3. Stop optimisation process when the relative loss in cost between two successive best sugestions is within X tolerence over Y iterations. (eg. if the optimiser suggests the best candidate so far in iteration 110 (cost 1.0) and then in iteration 125 (cost 0.95), then X=5% and Y=15. So when the absolute slope of (minimum cummilative best cost) v.s. (iteration) graph is below certain value, we stop the simulation.)

I will read up a bit more based on what you said and update my methods.

Finally, once I have a model I am confident enough to use, which acquisition function would work well enough to get the best candidate from the model? By the end of the entire process, I would have a set of candidates, the cost and variance in each cost. So I am currently using HeteroskedasticSingleTaskGP model with qNEI to get the best candidate in the end.

[Balandat]

Check for model accuracy. Keep using KG method until model accuracy is high enough using LOOCV

So KG may be exploiting the space better, but if what you're really trying to do is get a good model fit there are other options (such as the active learning type acquisition functions whose goal it is explicitly to improve the model).

Using KG earlier on since it's rather expensive and then switching to a different, cheaper acquisition function when you've collected a bunch of data makes sense though.

Stop optimisation process when the relative loss in cost between two successive best sugestions is within X tolerence over Y iterations

For this you don't really need to verify that the model fits are good since this strategy doesn't depend on the model (at least not explicitly). My suggestion above was to potentially use stopping strategy that reasons explicitly about the model and the likelihood of finding better solutions given that model. In that case it's crucial to ensure that the model fits are indeed decent otherwise such strategies can fail miserably.

Finally, once I have a model I am confident enough to use, which acquisition function would work well enough to get the best candidate from the model?

Usually you will want to get the best posterior mean from the model. The PosteriorMean "acquisition function" allows you to do that.

[sambitmishra98]

So KG may be exploiting the space better, but if what you're really trying to do is get a good model fit there are other options (such as the active learning type acquisition functions whose goal it is explicitly to improve the model).

I didn't know this part, I will look into it. I do have the need to intuitively understand the model using cheaper less accurate black-boxes and then moving on to getting an optimal candidate using a better model and acquisition function for expensive and more accurate black-boxes.

The PosteriorMean "acquisition function" allows you to do that.

Thanks, I will use that.