fcmaes - a Python 3 gradient-free optimization library

Delayed State Update

This tutorial is about:

A new mechanism performing parallel fitness evaluation during optimization.
Analyzes its performance for hyper-parameter optimization.
Compares with hyperband optimization.

This mechanism is currently implemented for DE, CMA-ES, and MODE. There are differences between the Python and C++ implementations. The C++ variants use C++ multithreading. The Python variants use Python multiprocessing. For a real application, you need to check which option works better.

GCL-DE and CR-FM-NES use Python multiprocessing for parallel fitness evaluation even in the C++ variants, and they do not support delayed update. For parallel fitness evaluation without delayed update, configure popsize=n*workers with an integer n >= 1.

Introduction

If your objective function is expensive and does not parallelize well, as in hyperparameter optimization (see the Hyper Parameter Tutorial), parallel retry becomes less attractive. In that case it is better to focus on parallel function evaluation. This often scales much better than the objective function’s own internal parallelism.

One example is hyperparameter tuning for xgboost.XGBRegressor with cross validation, as shown in house.py. The regressor itself can use n_jobs, but if the optimizer supports parallel function evaluation it is usually better to set n_jobs=1.

There are multiple ways to do this:

Population based algorithms such as CMA-ES and GCL-DE can evaluate the whole population at once. This can be implemented as a serial loop or with a parallel evaluator. The disadvantages are:
- If the population size is smaller than, or not a multiple of, the number of available threads, the CPU cannot be fully utilized.
- If some parameter settings are more expensive to evaluate than others, some threads will sit idle until the whole population has finished.
The optimization algorithm provides an X = ask() operation that generates a sample from its internal state, and a tell(X, y) operation that updates that state. If these operations work independently of the population size, then more individuals than a single population can be evaluated in parallel. New evaluations can also be started before the population is fully evaluated.

The second option is usually better. It is harder to implement, and only population based algorithms can support it, but it uses parallel resources more effectively. In fcmaes we implemented this idea in Python for CMA-ES and Differential Evolution. There is no strong reason to use C++ here because the target use case is very expensive objective functions, so the cost of the tell(X, y) state update is negligible.

If the population size is smaller than the number of parallel evaluation processes or threads, one possible way to reduce update delay is to run multiple optimizers at the same time.

If the state update is cheap compared to function evaluation, the optimizers can run in a single-threaded loop and call ask/tell for each optimizer in sequence. Then each ask listens to its own queue, filled by a single result-pipe listener running in a separate thread. This concept is not yet implemented in fcmaes because our experiments showed that even with update delay, the results are still acceptable.

Comparison with Hyperband Optimization

The idea above is closely related to the Hyperband Algorithm with

X = ask() equivalent to get_random_hyperparameter_configuration
tell(X, y) equivalent to tellrun_then_return_val_loss

with one minor modification:

The number of optimization algorithms running in the loop decreases over time by filtering out the ones with the worst solution so far.

The two approaches become equivalent if the optimization algorithms are stateless, ask() returns arbitrary random samples, and the number of evaluators matches the number of parallel algorithm runs. Our experiments show that this gives worse results.

That approach saves memory because no algorithm state has to be stored, and it saves CPU time because no state has to be updated. But CMA-ES relies on highly efficient MKL/BLAS implementations (via Numpy), and the state update cost for Differential Evolution is negligible.

Still, the Hyperband-inspired idea is interesting: run multiple optimizer instances, let them share a pool of parallel function or loss evaluators, and remove weak instances over time so the survivors get a larger evaluation budget. This may be useful for hard hyperparameter optimization problems with many variables. If GPUs limit parallel function or loss evaluation, a clustered setup based on ray, similar to fcmaes-ray, may be worth trying.

Application to Hyperparameter Optimization

What happens if we apply delayed state update to the scenario described in the Hyper Parameter Tutorial? We again use the tutorial code house.py and the same 16 core AMD 3950X machine for the tests:

For CMA-ES the call is:

from fcmaes import cmaes

   ret = cmaes.minimize(obj_f, bounds, popsize = 16, max_evaluations = 40000,
   					workers = 16)

 from fcmaes import de

   ret = de.minimize(obj_f, bounds, popsize = 16, max_evaluations = 40000,
   					workers = 16)

Note that only cmaes supports workers > popsize. For de you need to increase popsize accordingly.

Myths regarding Hyperparameter Optimization

There are two common myths about hyperparameter optimization (hyperparameters are the values that control a machine learning process):

Bayesian Optimization and Tree of Parzen Estimators (TPE) are hard to beat.
Usually testing a few hundred parameter sets is sufficient to find good values.

Data from our Hyper Parameter Tutorial combined with new results for delayed CMA-ES and DE (population size = 16, number of parallel threads = 32) seems to confirm these myths. If we compare mean squared error after the same number of evaluations (cross validations), we get:

Especially with fewer than 100 evaluations, TPE and Bayesian optimization are superior.
Even after 300 evaluations TPE and Bayesian still perform well.

The more accurate statement is:

If you want to evaluate no more than 300 cross validations, and you cannot execute multiple cross validations in parallel (limited GPU resources, …), then TPE or Bayesian optimization is a good choice.

Now consider what happens when we remove these limits, as we can for CPU-based regressors such as the popular xgboost.XGBRegressor. Do not be misled by the CPU utilization reported by the OS when using the XGBRegressor parameter n_jobs=32, which is the default on our 16 core / 32 thread machine:

The reported CPU utilization is similar to what we see with n_jobs=1 while running 32 XGBRegressor cross validations in parallel. But the number of validations per minute increases from about 3 to about 13 and above, as shown in the top right corner of the diagrams. Reported CPU utilization only indicates how much room the processor has left for other tasks. In this case it is fully utilized, but that does not tell us how much useful work is being done. The processor may spend a lot of time moving data between cores. CPU temperature is often a better hint here. It is usually higher when the processor is doing more real work.

For this reason, we no longer compare performance by evaluation count. We compare it by elapsed time.

Update

The mechanism described here for parallel fitness evaluation is now used in most fcmaes algorithms: MO-DE, DE, and CMA-ES, both in the C++ and Python implementations. Therefore the delayed_update parameter has been partly removed. If workers > 1, delayed update or parallel function evaluation is used.

Performance of longer runs

After 3000 sec, CMA-ES 16/32 and DE 16/32 are already clearly better.

After 12000 sec, the gap to the conventional methods increases further.

Finally, we see that with CMA-ES 16/32 it may be worth investing even more time.

Conclusion

On a modern multi-core processor, hyperparameter optimization for CPU-based regressors like XGBRegressor can be improved by running multiple cross validations in parallel instead of relying on the regressor’s internal parallelization.
In this setting, CPU utilization can be improved further by using optimizers that support delayed state update.
For longer execution times (> 1000 sec on a 16 core CPU), both Differential Evolution and CMA-ES clearly outperform TPE and Bayesian optimization when using delayed state update.
For very long runs (> 50000 sec), CMA-ES + delayed update finds the best results.

This is not limited to hyperparameter optimization. The fcmaes CMA-ES and DE variants with delayed update are worth trying whenever the following conditions hold:

Very high cost for objective function evaluation.
The objective function is CPU, not GPU based.
No intrinsic parallelization of the objective function or bad scaling.

Many simulation-based objective functions fall into this category. Still, if possible, it is often even better to run parallel optimization retries instead of parallelizing objective function evaluation. For the CTOC11 competition we chose that option, although the simulation in the objective function was quite costly.

Remarks

The CMA-ES algorithm implemented in fcmaes is the well known "active CMA" algorithm, see CMA_Evolution_Strategy
The DE variant used is special to fcmaes, it was successfully applied at the CTOC11 competition. Other DE variants may perform significantly worse.
GCL-DE, which is also implemented in fcmaes, doesn’t support delayed update yet, but can evaluate a whole population in parallel. It requires more function evaluations, but still performs better than TPE and Bayesian optimization for very long runs. See "A case learning-based differential evolution algorithm for global optimization of interplanetary trajectory design, Mingcheng Zuo, Guangming Dai, Lei Peng, Maocai Wang, Zhengquan Liu", DOI