Analysis of Surrogate-Assisted Information-Geometric Optimization Algorithms

Youhei Akimoto

Abstract

Surrogate functions are often employed to reduce the number of objective function evaluations in continuous optimization. However, their effects have seldom been investigated theoretically. This paper analyzes the effect of a surrogate function in the information-geometric optimization (IGO) framework, which includes as an algorithm instance a variant of the covariance matrix adaptation evolution strategy (CMA-ES)—a state-of-the-art solver for black-box continuous optimization. We derive a sufficient condition on the surrogate function for the parameter update in the IGO algorithms to point to a descent direction of the objective function expected over the search distribution. The condition is expressed in terms of three measures of correlation between the objective function and the surrogate function. Our result constitutes a partial justification for the use of a surrogate function in IGO algorithms.

Introduction: The Budget Problem in Black-Box Optimization

In the field of black-box optimization, researchers and engineers frequently encounter a significant "budget" constraint. For example, optimizing the aerodynamic properties of a wing using high-fidelity fluid dynamics simulations requires evaluations that are both computationally expensive and time-consuming. To mitigate these costs, surrogate models—cheap mathematical approximations such as Kriging or radial basis functions—are used to substitute for the expensive "real" objective function.

While surrogate-assisted techniques, particularly within the Covariance Matrix Adaptation Evolution Strategy (CMA-ES) framework, are widely used in practice, a rigorous theoretical understanding of their reliability has been lacking. Specifically, it has been unclear how accurate a surrogate must be to ensure the optimizer continues to move toward the global minimum rather than diverging. This research addresses this gap by establishing the mathematical conditions under which a surrogate-assisted update maintains a "descent direction."

The Information-Geometric Optimization (IGO) Framework

The study focuses on the Information-Geometric Optimization (IGO) framework. IGO provides a unified perspective on optimization by evolving a probability distribution (e.g., a Gaussian) toward regions of lower objective values, rather than simply moving a single point in the search space.

The analysis examines two primary variants of IGO:

  1. IGO-$f$ (Objective Proportional): The utility of a sample is directly proportional to its objective function value.
  2. IGO-$w$ (Ranking-Based): The utility depends only on the relative rank of samples. This variant is particularly significant as it corresponds to the standard CMA-ES.

Measuring Surrogate Quality

To quantify the fidelity of a surrogate model relative to the true objective function, the author utilizes three standard statistical correlation measures:

  • Pearson’s $r$: Captures linear correlation.
  • Spearman’s $\rho$: Measures rank correlation.
  • Kendall’s $\tau$: Evaluates how frequently the surrogate and the true function agree on the relative ordering of any two points.

Key Theoretical Findings

The 0.5 Threshold

A pivotal finding for the IGO-$f$ variant is that as long as the Pearson correlation between the surrogate and the real function exceeds 0.5, the algorithm is guaranteed to move in a descent direction. This relatively low threshold provides a strong theoretical justification for the empirical success of even moderately accurate surrogates.

The Descent Condition (Theorem 6)

The core of the paper is Theorem 6, which formalizes the descent condition. It establishes a general inequality showing that the descent direction is maintained if the "noise" introduced by the surrogate (represented by $\beta$) is less than the "signal" of the ideal update (represented by $\bar{\beta}$). This theorem proves that for a sufficiently small learning rate, expected objective improvement is guaranteed if the surrogate meets the derived correlation thresholds.

Justification for CMA-ES

By applying these results to Gaussian distributions on convex quadratic functions, the research provides a mathematical backbone for the "lq-CMA-ES," a popular surrogate-assisted variant of the algorithm.

Limitations and Future Outlook

While this work provides a foundational theoretical bridge, several areas remain for future exploration:

  • Conservative Bounds for IGO-$w$: The derived thresholds for ranking-based IGO (used in practical CMA-ES) are currently very close to 1.0. Since these algorithms often perform well with lower correlations in practice, the current theoretical bounds may be overly conservative.
  • Finite Population Estimates: The study assumes "population versions" of correlation (infinite samples). Real-world applications rely on small batch estimates, necessitating future analysis of the errors introduced by finite sampling.
  • Nonlinear Landscapes: While explicit thresholds were derived for linear and quadratic models, extending these proofs to highly non-linear or "rugged" landscapes remains a significant challenge.

This research marks a major step forward in moving surrogate-assisted optimization from an empirical practice toward a theoretically grounded engineering discipline.

Summary updated

Abstract

Abstract Surrogate functions are often employed to reduce the number of objective function evaluations in a continuous optimization. However, their effects have seldom been investigated theoretically. This paper analyzes the effect of a surrogate function in the information-geometric optimization (IGO) framework, which includes as an algorithm instance a variant of the covariance matrix adaptation evolution strategy---a state-of-the-art solver for black-box continuous optimization. We derive a sufficient condition on the surrogate function for the parameter update in the IGO algorithms to point to a descent direction of the objective function expected over the search distribution. The condition is expressed in terms of three measures of correlation between the objective function and the surrogate function. Our result constitutes a partial justification for the use of a surrogate function in IGO algorithms.
BibTeX
@inproceedings{akimoto2024analysis,
  author = {Youhei Akimoto},
  title = {{Analysis of Surrogate-Assisted Information-Geometric Optimization Algorithms}},
  booktitle = {Algorithmica},
  year = {2024},
  url = {https://openreview.net/forum?id=FYcRzGczph},
}
Figure