Stop hopeless starts early in a multi-start fit instead of running every one to completion

[wshlavacek]

What happens now

The gradient optimizers (gntr, lbfgs, trf, ms) and the local searches (powell, sim) run several searches at the same time, each from a different starting point, and keep the best result. The number of concurrent searches comes from population_size for the gradient methods and from n_starts for powell and sim. The orchestration is in pybnf/algorithms/optimizers/concurrent_multistart.py.

Every one of those searches runs until it meets its own stopping rule. Nothing ever stops a search early because other searches are doing better.

Why this wastes a cluster

Fitting a model with many parameters usually means most starting points land in a poor region and stay there. On a laptop with eight concurrent searches that is tolerable. On a cluster with two hundred, it is not. Most of those two hundred searches are clearly going nowhere within the first handful of iterations, and they then spend the rest of their iteration budget confirming it. Each of those iterations costs a full simulation with sensitivities, which is the most expensive thing PyBNF does.

So a large allocation is spent mostly on proving that bad starting points are bad.

Suggested approach

Run all the starts for a short budget of iterations. Rank them by the objective value they have reached. Keep the better half and give the survivors a longer budget. Repeat until one or a few remain.

The total cost stays about the same, but far more of it is spent on the searches that are actually improving. It also means a user can afford many more starting points for the same money, which is the thing that most improves the chance of finding the best fit.

This idea is standard practice in hyperparameter tuning, where it is usually called successive halving, and it transfers directly.

Why this fits what we already have

• The orchestrator already routes each finished simulation to the search that owns it, tracks each search's iteration count, and knows how to retire one. ConcurrentMultiStartOptimizer.got_result already handles a search finishing and decrementing the active count. Stopping a search early is a policy decision on top of machinery that exists.
• Every search's current objective value is already available on its runner object as runner.fval.
• Issue Report each start's final objective value at the end of a multi-start fit #658 asks for the same per-search objective values to be reported at the end of a run, as a way for a user to see whether enough starting points were tried. This proposal consumes the same numbers while the run is still going. Doing Report each start's final objective value at the end of a multi-start fit #658 first is a sensible order, since it puts the data in reach and gives a way to see the effect of any pruning afterwards.

Care needed

A search that looks bad early is not always bad. A starting point in a long shallow valley can trail the field for many iterations and then overtake everything. Cutting too aggressively will throw those away.

Some ways to keep that in check:

• Use a gentle schedule and give the first round enough iterations that a slow start has a fair chance.
• Keep the discarded searches in the archive with their final values rather than deleting them, so the report asked for in Report each start's final objective value at the end of a multi-start fit #658 still shows the whole picture and a user can see what was cut.
• Make it optional and off by default, so existing runs are unchanged.

Some measurement of how often a pruned search would have won, on real models, would be worth having before this is turned on by default.

Not in scope

This is about which searches keep running. It does not change how any individual search takes its steps.