Parameter Setting for Multicore CMA-ES with Large Populations

Nacim Belkhir, Johann Dréo, Pierre Savéant, Marc SchoenauerArtificial Evolution 2015 · DOI

TL;DR

This paper investigates how to optimize the performance of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) when using a large number of parallel processing cores. They propose and validate a new strategy for CMA-ES, called Self-CMA-ES, which adaptively tunes its internal parameters, showing significant improvements in efficiency and speed compared to default CMA-ES settings, especially in distributed computing environments.

What Problem Does This Paper Address?

Modern computing relies heavily on parallel processing to speed up complex tasks. Evolutionary Algorithms (EAs), like CMA-ES, are powerful tools for optimization but can be computationally intensive. While CMA-ES can be parallelized by distributing fitness evaluations across multiple cores, its default parameter settings are often not optimal for large populations, which are necessary to effectively utilize many cores. This leads to suboptimal performance and wasted computational resources. The paper addresses the challenge of finding effective parameter settings for CMA-ES in a distributed setting, specifically when the population size is large and directly mapped to the number of available cores, aiming to minimize the time it takes to find a solution (wall-clock time-to-solution).

Methods

The core of the paper revolves around two main approaches to parameter setting for CMA-ES:

  • Off-line Tuning: This involves using an external optimization algorithm (like SMAC) to find the best fixed parameter values before the main optimization run. This is computationally expensive as it requires running the target algorithm many times.
  • On-line Tuning (Self-CMA-ES): This is the novel approach proposed and investigated. Self-CMA-ES is a variant of CMA-ES that adaptively tunes its internal parameters (specifically, those controlling the covariance matrix adaptation: $c_c, c_1, c_\mu$) during the optimization process. It uses an auxiliary CMA-ES instance to estimate the best parameter configuration at each step, based on the likelihood of generating the current best solutions. This approach aims to reduce the computational overhead and avoid the need for extensive off-line tuning.

The paper also explores the impact of the population size ($\lambda$) and the initial step-size ($\sigma_0$) on performance, proposing new strategies for their selection in the context of large populations.

Datasets

The experiments were conducted using the Black-Box Optimization Benchmark (BBOB) suite. This benchmark includes 24 functions with varying characteristics (e.g., separability, conditioning, multi-modality) and across different dimensions (2, 3, 5, 10, 20, 40). The paper specifically mentions using the noiseless versions of these functions.

Key Insights and Ideas

  • Self-CMA-ES is a strong contender: The adaptive nature of Self-CMA-ES makes it a robust and often superior alternative to default CMA-ES, especially in distributed settings with large populations. It achieves comparable or better performance with significantly less tuning effort.
  • Large populations require different strategies: The default CMA-ES parameter settings, particularly the population size ($\mu$), are not suitable for large $\lambda$. The paper suggests a new strategy of $\mu \approx \ln(\lambda)$ which performs better than the default $\mu \approx 4 + 3\ln(n)$ and the strategy $\mu \approx \lambda/2$ proposed in prior work.
  • Initial step-size matters for large populations: The initial step-size ($\sigma_0$) needs to be adjusted for larger population sizes. The paper finds that a value smaller than the one used in [17] but larger than the default is optimal.
  • On-line tuning is efficient: While off-line tuning can find optimal parameters, the computational cost is prohibitive. Self-CMA-ES offers a practical way to achieve good performance without this burden.
  • Diminishing returns with many cores: The study suggests that simply adding more cores beyond a certain point (e.g., 500 cores) doesn't necessarily lead to proportional speedups, indicating a need for further research into strategies for massive parallelism.

Key Results

  • Self-CMA-ES outperforms default CMA-ES: Across various dimensions and functions in the BBOB benchmark, Self-CMA-ES consistently showed better performance, especially as the dimension increased.
  • New $\mu$ strategy is effective: The proposed strategy of $\mu \approx \ln(\lambda)$ yielded better results than default settings for both CMA-ES and Self-CMA-ES.
  • VWCT metric: The paper introduces the Virtual Wall Clock Time (VWCT) metric, which accounts for core usage and provides a more relevant measure of performance in distributed environments than raw function evaluations.
  • Performance gains with dimension: The advantage of Self-CMA-ES over CMA-ES generally increased with the dimensionality of the problem. For example, in 40D, Self-CMA-ES performed significantly better.
  • Tuned CMA-ES vs. Self-CMA-ES: While a heavily tuned CMA-ES (using SMAC for extensive off-line tuning) could sometimes outperform Self-CMA-ES, the difference was often not significant, and the tuning process was orders of magnitude more computationally expensive.

Limitations and Future Work

  • Separable functions: Self-CMA-ES showed some weaknesses on separable functions in higher dimensions (40D), where it sometimes failed to reach the target value. Further investigation is needed to understand and address this.
  • Low/moderate conditioning: For functions with low or moderate conditioning, Self-CMA-ES showed slightly worse results than CMA-ES, though still competitive.
  • Hybridization: The authors suggest combining their approach with other strategies (e.g., those from [3] and [21]) to further improve performance, especially for very large numbers of cores.
  • Step-size adaptation: Further research is recommended to refine the adaptation mechanism of the step-size $\sigma$.
  • Detecting poor adaptation: Developing methods to detect situations where Self-CMA-ES's adaptation mechanism performs poorly and switching back to default parameters could guarantee robustness.
  • Portfolio of strategies: Considering a portfolio of strategies, including CMSA-ES, might be beneficial for maximizing expected performance, particularly in large dimensions and population sizes.

Summary updated

BibTeX
@inproceedings{belkhir2015parameter,
  author = {Nacim Belkhir and Johann Dréo and Pierre Savéant and Marc Schoenauer},
  title = {{Parameter Setting for Multicore CMA-ES with Large Populations}},
  booktitle = {Artificial Evolution},
  year = {2015},
  doi = {10.1007/978-3-319-31471-6\_9},
}
Figure