Resource-Aware Parameterizations of EDA

Sylvain Gelly, Olivier Teytaud, Christian Gagné

Resource-Aware Parameterizations of EDA

Introduction

In many industrial applications, such as crash testing, fluid dynamics, and chemical design, optimization involves evaluating "black-box" functions that are extremely expensive in terms of time or capital. In these scenarios, standard evolutionary algorithms often fail because they require thousands or millions of evaluations. The paper "Resource-Aware Parameterizations of EDA" addresses this by bridging statistical learning theory and evolutionary computation, providing theoretical, non-asymptotic bounds for Estimation of Distribution Algorithms (EDAs) specifically designed for "frugal" optimization tasks.

Theoretical Foundation: VC-Dimension in Optimization

The authors apply Vapnik-Chervonenkis (VC) theory—a cornerstone of statistical machine learning—to the field of optimization. By treating the selection of the next search space as a learning problem, they derive a theorem linking the required population size to the VC-dimension of the distribution family (e.g., ellipsoids), the selection rate, and the number of iterations.

This theoretical framework demonstrates that if ellipsoids are used to model the search space (which possess a quadratic VC-dimension), the required population size must scale quadratically with the dimension and linearly with the number of optima. This allows practitioners to optimize algorithm parameters a priori for ultra-low-budget tasks, moving beyond the limitations of asymptotic convergence analysis.

Methodology: EDAs as Generalized Surrogate Models

A key conceptual contribution of the paper is the formalization of EDAs as a natural extension of Surrogate Models (SMs). In this view, SMs represent the limit case of an EDA where the selection rate is zero. This unification allows for the explicit mathematical treatment of diversification, explaining why EDAs can avoid the premature local convergence that often plagues standard Surrogate Models.

To validate this theory, the authors modified standard EDAs for extreme resource constraints:

  • Quasi-random sequences: Niedereiter sequences were used instead of pure random generation to ensure superior uniform coverage of the search space.
  • Advanced Learners: The study compared various machine learning models, finding that Support Vector Machines (specifically Sequential Minimal Optimization, or SMO) vastly outperformed Multi-layer Perceptrons (MLPs). SVMs are explicitly designed to generalize well from the tiny sample sizes typical of frugal optimization.

Empirical Results

The algorithms were evaluated on 14 continuous benchmark functions from the CEC 2005 special session. The experiments were conducted under extreme "Design of Experiments" constraints, with maximum budgets of only 16 or 64 function evaluations.

Table 1: Performance comparison of various optimization algorithms on CEC 2005 benchmarks. The SMSMO variant (EDA with SMO-SVM) shows strong performance across multiple functions.

In 2D spaces with a budget of 64 evaluations, EDAs outperformed the industry-standard L-BFGS-B on 9 out of 14 functions, dominating the most challenging multimodal problems. In higher-dimensional tests (10D with 16 evaluations), the EDA using SMO-SVM remained remarkably efficient.

Table 2: Results for higher-dimensional problem instances, demonstrating the stability and efficiency of EDA-based approaches compared to traditional baselines.

Across all tests, EDAs proved to be the most stable algorithms. While CMA-ES is highly effective in standard contexts, it struggled under these strict evaluation limits. Conversely, algorithms relying on local models, such as Coin-DFO, were heavily outperformed, highlighting the necessity of building global models when data points are scarce.

Conclusion and Future Work

This research provides a robust theoretical and empirical case for using resource-aware EDAs in expensive black-box optimization. By leveraging VC-theory, the authors offer a path toward mathematical guarantees for finite-resource tasks. Future work will focus on relaxing the restrictive assumptions in the current proofs and exploring the use of covariance-based mutations to further enhance the approximation of optima neighborhoods.

Summary updated

Abstract

This paper presents a framework for the theoretical analysis of Estimation of Distribution Algorithms (EDA). Using this framework, derived from the VC-theory, we propose non-asymptotic bounds which depend on: 1) the population size, 2) the selection rate, 3) the families of distributions used for the modelling, 4) the dimension, and 5) the number of iterations. To validate these results, optimization algorithms are applied to a context where bounds on resources are crucial, namely Design of Experiments, that is a black-box optimization with very few fitness-values evaluations.
BibTeX
@inproceedings{gelly2006resource,
  author = {Sylvain Gelly and Olivier Teytaud and Christian Gagné},
  title = {{Resource-Aware Parameterizations of EDA}},
  booktitle = {IEEE CEC},
  year = {2006},
  doi = {10.1109/cec.2006.1688620},
}
Figure