After 30 black-box evaluations, how does NOMAD choose point 31?

With 30 samples in hand, NOMAD can fit a local model to propose the next evaluation. When does one Search call save work in Poll?

Suppose we have sampled a black-box function f at 30 points. The smallest value we have seen is 8.0. We have no formula or gradient, only the input points and their function values. If each evaluation is expensive, where should we take sample 31?

NOMAD solves black-box optimization problems like this using Mesh Adaptive Direct Search (MADS). MADS places a mesh over the input space and chooses trial points on that mesh. During Search, it can use previous evaluations to propose a promising point. If Search is omitted or finds no improvement, Poll explores a set of directions around the best point so far. If neither step finds an improvement, the next iteration starts on a finer mesh. Audet and Dennis on MADS

How does a quadratic model help choose a point?

Consider the samples among the first 30 that lie near the current best point. If the function falls and then rises along one direction, a quadratic model can approximate that curvature. With QUAD_MODEL_SEARCH, NOMAD fits a model to past evaluations, looks for coordinates where the predicted value is low, and projects them onto the current mesh to generate Search candidates. Comparing coordinates on the model costs no extra black-box calls. NOMAD 4 implementation paper, Section 3.3

Poll first generates nearby candidates using a set of directions and a step size. The model can help here too. Setting EVAL_QUEUE_SORT to QUADRATIC_MODEL lets the quadratic model order those candidates for evaluation. With EVAL_OPPORTUNISTIC enabled and points evaluated one at a time, an early improvement saves the calls for the remaining points. NOMAD 4 user guide

Which of A, B, and C do we actually evaluate?

Suppose the best value so far is 8.0, all candidates are feasible, and A is the only Search candidate. The iteration ends at the first improvement.

Step Reason for choosing the point Model prediction Black-box value Decision
Search · A New point proposed by the quadratic model 7.3 8.2 Keep 8.0 and proceed to Poll.
Poll · B Lower predicted value than Poll candidate C, so B goes first 7.6 7.9 Adopt B as the new center.
Poll · C Next in the evaluation queue 7.8 Unevaluated End Poll because B improved the incumbent.

The model predicted 7.3 at A, but the black box returned 8.2. Had it returned 7.3, NOMAD could have accepted A and skipped Poll for this iteration. Accepting B does not require knowing the value at C. The observed value of 7.9 at B already improves on 8.0.

Is Search worth one evaluation?

Consider a separate cost comparison. Going straight to Poll takes four black-box calls. Trying Search first costs one call. Success ends the iteration, while failure adds four Poll calls. Let p be the probability that a single Search candidate improves the observed best value under comparable conditions. The 7.3 in the table predicts the function value at A. That number alone does not tell us p.

The expected count with Search first is p × 1 + (1 − p) × 5 = 5 − 4p. This equals the four calls for Poll alone at p = 0.25. One success in four attempts saves three calls, exactly covering the extra call spent on each of the three failures. Search reduces the average calls per iteration when its success rate exceeds 25%.

Early stopping in Poll changes the calculation. Suppose Poll averages two calls both when used directly and when reached after a failed Search. Search then saves calls if 1 + 2(1 − p) < 2, so its success rate must exceed 50%. To make this comparison from evaluation logs, count Poll calls separately in the two cases. If Poll takes more calls in iterations where Search fails, using the overall Poll average will understate the cost of failure.