Why this matters
CMA-ES is the right method for the user who fits models on a laptop and will never use a cluster. It needs the fewest simulations of any method we have, and its population size works out to roughly 4 + 3 * ln(n) parameter sets, which is about 12 to 20 for a typical problem. That is close to the number of processors a laptop has, so it fits that machine almost exactly. The small population that makes it a poor fit for a large cluster makes it the natural choice for a small one.
It has one gap for the models PyBNF was originally built for. It does not know that a stochastic simulation gives a different answer every time.
The problem
Each generation, CMA-ES simulates a population of parameter sets, sorts them from best to worst, and uses that ordering to decide where to search next. It reads only the ordering. It never uses the objective values themselves.
With a stochastic model, each of those objective values comes from a single simulation and carries noise. When the noise is comparable to the real differences between candidates, the sort order is partly random. The method then adapts its search distribution and its step size from an ordering that does not reflect which parameter sets are actually better. Two things follow. The search is pulled in arbitrary directions, and the step size adaptation misreads the noise as a lack of progress, which usually makes the step size shrink when it should not.
The implementation is in pybnf/algorithms/optimizers/cmaes.py.
The fix
The established approach is to check whether the ordering is trustworthy and react when it is not. Each generation, re-simulate a few members of the population, see how far they move in the ranking, and use that as a measure of how much the noise is disturbing the sort. When the disturbance is large, spend more simulations per candidate, and hold the step size back rather than letting the noise drive it down. Hansen and colleagues described this in 2009 and it is the standard treatment.
Shared work with the scatter search epic
This should be built on the same component as step 3 of #660, and neither should invent its own.
Both methods are driven entirely by ranking. CMA-ES uses only the sort order of its population. Scatter search uses the gap in rank between two reference members to set its step size, and uses rank comparisons to decide whether a child beat its parent and whether a member is stuck. So both need the same underlying thing, which is a way to hold an estimate and an uncertainty for a parameter set, decide whether two of them are safely ordered, and ask for more simulations when they are not.
Suggested order. Build the shared piece as part of #660 step 3, since scatter search needs more from it, then apply it here, which should be a much smaller piece of work.
Notes
This only applies when at least one model is stochastic. Config._check_smoothing_misuse in pybnf/config.py already reads m.stochastic to answer that question, so the check exists.
The smoothing setting is not a substitute. It runs every simulation the same number of times, which multiplies the cost of the whole fit, and it cannot tell the difference between a generation where the ordering is obvious and one where it is not.
Issue #659 covers the same underlying error in the final reported answer, for every method rather than this one. It is smaller and independent, and it will show how large the effect is on real fits before we build any of this.
Why this matters
CMA-ES is the right method for the user who fits models on a laptop and will never use a cluster. It needs the fewest simulations of any method we have, and its population size works out to roughly
4 + 3 * ln(n)parameter sets, which is about 12 to 20 for a typical problem. That is close to the number of processors a laptop has, so it fits that machine almost exactly. The small population that makes it a poor fit for a large cluster makes it the natural choice for a small one.It has one gap for the models PyBNF was originally built for. It does not know that a stochastic simulation gives a different answer every time.
The problem
Each generation, CMA-ES simulates a population of parameter sets, sorts them from best to worst, and uses that ordering to decide where to search next. It reads only the ordering. It never uses the objective values themselves.
With a stochastic model, each of those objective values comes from a single simulation and carries noise. When the noise is comparable to the real differences between candidates, the sort order is partly random. The method then adapts its search distribution and its step size from an ordering that does not reflect which parameter sets are actually better. Two things follow. The search is pulled in arbitrary directions, and the step size adaptation misreads the noise as a lack of progress, which usually makes the step size shrink when it should not.
The implementation is in
pybnf/algorithms/optimizers/cmaes.py.The fix
The established approach is to check whether the ordering is trustworthy and react when it is not. Each generation, re-simulate a few members of the population, see how far they move in the ranking, and use that as a measure of how much the noise is disturbing the sort. When the disturbance is large, spend more simulations per candidate, and hold the step size back rather than letting the noise drive it down. Hansen and colleagues described this in 2009 and it is the standard treatment.
Shared work with the scatter search epic
This should be built on the same component as step 3 of #660, and neither should invent its own.
Both methods are driven entirely by ranking. CMA-ES uses only the sort order of its population. Scatter search uses the gap in rank between two reference members to set its step size, and uses rank comparisons to decide whether a child beat its parent and whether a member is stuck. So both need the same underlying thing, which is a way to hold an estimate and an uncertainty for a parameter set, decide whether two of them are safely ordered, and ask for more simulations when they are not.
Suggested order. Build the shared piece as part of #660 step 3, since scatter search needs more from it, then apply it here, which should be a much smaller piece of work.
Notes
This only applies when at least one model is stochastic.
Config._check_smoothing_misuseinpybnf/config.pyalready readsm.stochasticto answer that question, so the check exists.The
smoothingsetting is not a substitute. It runs every simulation the same number of times, which multiplies the cost of the whole fit, and it cannot tell the difference between a generation where the ordering is obvious and one where it is not.Issue #659 covers the same underlying error in the final reported answer, for every method rather than this one. It is smaller and independent, and it will show how large the effect is on real fits before we build any of this.