A Deep Dive Into Effects of Structural Bias on CMA-ES Performance Along Affine Trajectories

Niki van Stein, Sarah L. Thomson, Anna V. Kononova

TL;DR

This paper investigates how "structural bias" – an algorithm's inherent tendency to favor certain search space regions – affects the performance of the modular Covariance Matrix Adaptation Evolution Strategy (modCMA). By analyzing over 435,000 configurations and testing them on progressively complex landscapes, the authors identify key modules influencing this bias and reveal a nuanced interplay between bias type, landscape, and optimum location.

What Problem Does This Paper Address?

The field of heuristic black-box optimization offers a vast array of algorithms, but choosing the right configuration for a specific problem is challenging due to the complexity of hyperparameters and their interactions. A critical, yet under-explored, aspect is "structural bias" (SB) – an algorithm's predisposition to favor certain search regions irrespective of the objective function's landscape. Understanding SB is crucial for designing more effective optimization heuristics. This paper aims to dissect how SB, arising from different modular components of modCMA, impacts its performance across various search landscapes, particularly as they transition from simple to complex.

Methods

The researchers employed a multi-pronged approach:

  • Extensive Configuration Sweep: They systematically tested a massive number of modCMA configurations (435,456) by varying its categorical module options.
  • Structural Bias Detection and Classification: The Deep-BIAS toolbox was used to automatically detect and classify the structural bias of each modCMA configuration into categories like "center bias," "bounds bias," and "uniform" (no bias).
  • Explainable AI (XAI) for Module Contribution: SHAP (Shapley Additive Explanations) analysis was applied to understand which specific module options within modCMA contribute most significantly to each type of structural bias. This involved training XGBoost models on configurations and their predicted SB classes.
  • Performance Evaluation on Affine Trajectories: To assess the impact of SB on performance, they created a suite of "affine-recombined" functions. These functions gradually transition from simple to more complex landscapes by blending basic BBOB functions (like SPHERE) with others of increasing ruggedness. The location of the global optimum was also varied across these functions (near bounds, near center, mixed, random).

Datasets

The study utilized:

  • BBOB Functions: A selection of standard BBOB (Black-Box Optimization Benchmark) functions (f1, f3, f15, f16, f21) were used as building blocks for creating the affine-recombined benchmark problems.
  • Affine-Recombined Functions: A novel benchmark suite was generated by creating affine combinations of BBOB functions. This allowed for a controlled transition of landscape complexity and fixed optimum locations.

Key Insights and Ideas

  • Module-Specific Bias: Certain modCMA modules have a disproportionately large influence on structural bias. Specifically, covariance adaptation, elitism, threshold convergence, and bound correction modules were found to be key drivers of SB.
  • Interplay of Bias and Landscape: The impact of structural bias is not static; it significantly interacts with the characteristics of the search landscape. For instance, a "center bias" might be detrimental in some scenarios but less so in others.
  • Optimum Location Matters: The position of the global optimum within the search space plays a crucial role in how structural bias affects performance. Algorithms with certain biases might struggle when the optimum is at the boundaries, but perform surprisingly well when it's near the center.
  • Counter-Intuitive Findings: Surprisingly, algorithms with "center bias" or "no bias" often performed better than "bounds bias" algorithms when the optimum was near the bounds. Conversely, "bounds bias" algorithms sometimes outperformed others when the optimum was centrally located.
  • "Mixed SB" is Generally Worse: Configurations exhibiting a combination of center and bounds bias ("mixed SB") tended to perform the worst across various scenarios.

Key Results

  • Prevalence of Center Bias: The majority of modCMA configurations (82%) were classified as having "center bias."
  • Module Contributions:
    • Elitism and threshold convergence (when turned on) were found to reduce center SB.
  • Bound correction "saturate" was a strong indicator of bounds SB, as expected.
  • Covariance matrix adaptation was identified as a major contributor to center SB, potentially due to the mismatch between the algorithm's hyper-ellipsoidal search distribution and the hyper-cubic search space.
  • Performance Trends:
    • For most function pairs, increasing the proportion of the simple SPHERE function (f1) generally led to improved performance.
  • When the optimum was near the center, bounds-biased and center-biased algorithms performed best.
  • When the optimum was near the bounds, center-biased and unbiased algorithms performed better.
  • The performance trend reversed for the f21 function (Gallagher's Gaussian 101-me PEAKS), where increasing f1's proportion led to decreased performance when the optimum was centrally placed, likely due to the function's unique funnel-like structure.

Limitations and Future Work

  • Dimensionality: The current analysis is limited to 2D landscapes. The authors suggest that future research should extend this analysis to higher dimensional spaces, where the interplay between SB, geometry, and landscape features may become even more complex and reveal new insights.
  • Mixed SB Class: The "mixed SB" class was identified as a new phenomenon not previously accounted for in bias detection tools. Further investigation into its causes and implications is warranted.
  • Statistical Analysis of Counter-Intuitive Results: The paper notes a curious finding where center/unbiased algorithms outperform bounds algorithms when the optimum is near the bounds. A deeper statistical analysis of these specific runs is suggested for future work.
  • Developing Robust Strategies: The ultimate goal is to use these findings to guide the development of more robust optimization strategies that are less susceptible to structural biases.

Summary updated

Abstract

To guide the design of better iterative optimisation heuristics, it is imperative to understand how inherent structural biases within algorithm components affect the performance on a wide variety of search landscapes. This study explores the impact of structural bias in the modular Covariance Matrix Adaptation Evolution Strategy (modCMA), focusing on the roles of various modulars within the algorithm. Through an extensive investigation involving \(435\,456\) configurations of modCMA, we identified key modules that significantly influence structural bias of various classes. Our analysis utilized the Deep-BIAS toolbox for structural bias detection and classification, complemented by SHAP analysis for quantifying module contributions. The performance of these configurations was tested on a sequence of affine-recombined functions, maintaining fixed optimum locations while gradually varying the landscape features. Our results demonstrate an interplay between module-induced structural bias and algorithm performance across different landscape characteristics.
BibTeX
@inproceedings{stein2024deep,
  author = {Niki van Stein and Sarah L. Thomson and Anna V. Kononova},
  title = {{A Deep Dive Into Effects of Structural Bias on CMA-ES Performance Along Affine Trajectories}},
  booktitle = {PPSN},
  year = {2024},
  url = {https://openreview.net/forum?id=RzJnEOT9y1},
}
Figure