Cumulative Step-size Adaptation on Linear Functions

Thomas Philip Rúnarsson, Xin Yao, Nikolaus Hansen

TL;DR

This paper rigorously analyzes the Cumulative Step-size Adaptation Evolution Strategy (CSA-ES) on linear functions. It proves that the step-size of the CSA-ES typically diverges geometrically, with the rate influenced by the cumulation parameter and the dimensionality of the search space. This provides crucial theoretical understanding for the behavior of this popular optimization algorithm.

What Problem Does This Paper Address?

Evolution Strategies (ESs) are powerful algorithms for continuous optimization, but their performance hinges on effective adaptation of parameters like step-size and covariance matrix. The Cumulative Step-size Adaptation (CSA) mechanism is a key component of modern ESs like CMA-ES, designed to adapt the step-size based on a "cumulative path" of past search steps. However, a deep theoretical understanding of how CSA behaves, especially in challenging scenarios, has been lacking. This paper tackles this by providing a rigorous mathematical analysis of CSA-ES on linear functions, a fundamental building block for understanding its behavior on more complex problems. Specifically, it investigates how the step-size evolves and whether it diverges, and how the "cumulation parameter" (controlling the memory of past steps) affects this behavior.

Methods

The authors employ a combination of theoretical analysis and mathematical tools to study the CSA-ES. Key methods include:

  • Markov Chain Analysis: The core of the analysis involves modeling the CSA-ES's behavior as a Markov chain. This allows for the application of powerful tools like the Law of Large Numbers (LLN) to understand the long-term behavior of the step-size.
  • Logarithmic Transformation: To analyze the multiplicative nature of step-size updates, the authors take the logarithm of the step-size. This transforms the multiplicative updates into additive ones, making them amenable to LLN.
  • Order Statistics: The analysis of the selected step's distribution involves order statistics of normal distributions, particularly for understanding the behavior of the first dimension where selection pressure is applied.
  • Variance Analysis: To understand the stability and robustness of the step-size adaptation, the paper analyzes the variance of the logarithm of the step-size increment.

The paper distinguishes between the case with cumulation (where past steps are weighted with decreasing importance) and without cumulation (where only the most recent step is considered).

Datasets

Not discussed in the paper. The analysis is theoretical and focuses on the mathematical properties of the algorithm on abstract linear functions.

Key Insights and Ideas

  • Geometric Divergence is the Norm: For most configurations (specifically, when the search space dimension $\lambda \ge 3$ or with cumulation and $\lambda \ge 2$), the step-size of the CSA-ES diverges geometrically. This means the algorithm tends to explore larger and larger steps over time, which can be beneficial for escaping local optima or navigating flat landscapes.
  • Cumulation Parameter is Crucial for Stability: The cumulation parameter ($c$) plays a significant role in stabilizing the step-size. When $c$ is small (i.e., more cumulation), the step-size variations are reduced, leading to a more stable and predictable behavior. This is in contrast to the case without cumulation ($c=1$), where the step-size can behave like a random walk for certain dimensions.
  • Dimensionality Matters: The dimensionality of the search space ($n$) influences the variance of the step-size increment. As dimensionality increases, the relative standard deviation of the step-size increment tends to decrease, especially with cumulation, suggesting that the algorithm becomes more robust in higher dimensions.
  • Linear Functions as a Foundation: Analyzing CSA-ES on linear functions is a critical first step. The paper shows that understanding this simple case provides insights into its behavior on more complex, composite functions.

Key Results

  • Theorem 1: For $\lambda \ge 3$, the CSA-ES without cumulation ($c=1$) diverges geometrically almost surely and in expectation. For $\lambda=1$ and $\lambda=2$ without cumulation, the logarithm of the step-size follows an additive unbiased random walk.
  • Theorem 2: With cumulation ($0 < c < 1$), the CSA-ES step-size diverges geometrically fast if $\lambda \ge 3$ or if $\lambda \ge 2$ and $c < 1$. The paper provides an explicit formula for the rate of divergence.
  • Theorem 3: The paper derives an expression for the variance of the logarithm of the step-size increment, showing how it depends on the cumulation parameter $c$ and the dimension $n$. It demonstrates that for appropriate choices of $c$, the relative standard deviation of the step-size increment converges to zero as the dimension increases.

Limitations and Future Work

  • Linear Functions: The analysis is strictly limited to linear functions. While this is a fundamental case, the behavior on non-linear, complex objective functions might differ. The paper mentions that analyzing the behavior of the parent point $(X_t)$ with cumulation requires studying a "double Markov chain," which is left for future research.
  • Specific CSA Variant: The paper focuses on a specific variant of CSA-ES, the (1, $\lambda$)-CSA-ES. Other ES variants or more complex selection schemes might exhibit different behaviors.
  • Future Work: The authors explicitly state that analyzing the behavior of $(X_t)$ with cumulation is a direction for future research. They also suggest extending the analysis to more general function classes.

Summary updated

Abstract

The CSA-ES is an Evolution Strategy with Cumulative Step size Adaptation, where the step size is adapted measuring the length of a so-called cumulative path. The cumulative path is a combination of the previous steps realized by the algorithm, where the importance of each step decreases with time. This article studies the CSA-ES on composites of strictly increasing functions with affine linear functions through the investigation of its underlying Markov chains. Rigorous results on the change and the variation of the step size are derived with and without cumulation. The step-size diverges geometrically fast in most cases. Furthermore, the influence of the cumulation parameter is studied.
BibTeX
@inproceedings{runarsson2012cumulative,
  author = {Thomas Philip Rúnarsson and Xin Yao and Nikolaus Hansen},
  title = {{Cumulative Step-size Adaptation on Linear Functions}},
  booktitle = {HAL},
  year = {2012},
}
Figure