Cumulative Step-size Adaptation on Linear Functions: Technical Report

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 population size. This work provides a theoretical foundation for understanding CSA-ES behavior and its stability.

What Problem Does This Paper Address?

Evolution Strategies (ESs) are powerful optimization algorithms, but their performance heavily relies on effective step-size adaptation. The Cumulative Step-size Adaptation (CSA) mechanism, used in algorithms like CMA-ES, aims to improve this by considering a "cumulative path" of past steps. However, a deep theoretical understanding of how CSA-ES behaves, especially on simple but fundamental function classes like linear functions, has been lacking. This paper addresses this gap by providing a rigorous mathematical analysis of the CSA-ES on linear functions, investigating its convergence properties and the impact of its key parameter, the cumulation factor.

Methods

The authors employ a combination of theoretical analysis and Markov chain theory. They model the CSA-ES as a Markov chain and analyze the behavior of the step-size logarithm. Key techniques include:

  • Markov Chain Analysis: The CSA-ES process is framed as a Markov chain, allowing for the application of stability theorems and laws of large numbers.
  • Lyapunov Functions: Foster-Lyapunov drift conditions are used to prove positive Harris recurrence of the underlying Markov chains.
  • Order Statistics: Properties of order statistics from normal distributions are utilized to analyze the behavior of the cumulative path and step-size updates.
  • Asymptotic Analysis: The paper derives limits and convergence rates for the step-size as the number of iterations goes to infinity.
  • Analysis of Cumulation Parameter: The impact of the cumulation parameter 'c' is explicitly studied, both in the case of no cumulation (c=1) and with cumulation (0 < c < 1).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis using synthetic linear functions.

Key Insights and Ideas

  • Geometric Divergence is the Norm: For linear functions, the step-size of the CSA-ES (with population size $\lambda \ge 3$) generally diverges geometrically, which is a desirable property for escaping local optima and ensuring progress.
  • Cumulation Stabilizes: The cumulation parameter 'c' plays a crucial role in stabilizing the step-size. As 'c' decreases (more cumulation), the variance of the step-size increment decreases, leading to more stable behavior.
  • Linear Functions as a Testbed: Analyzing CSA-ES on linear functions provides fundamental insights into its behavior that can generalize to more complex functions. It allows for rigorous proofs of convergence and divergence rates.
  • The Role of Population Size: The behavior of the step-size is shown to depend on the population size $\lambda$. For $\lambda \ge 3$, geometric divergence is observed, while for $\lambda=1$ or $\lambda=2$ (without cumulation), it behaves more like a random walk.

Key Results

  • Theorem 3: For $\lambda \ge 3$, the step-size of the (1, $\lambda$)-CSA-ES without cumulation ($c=1$) diverges geometrically almost surely and in expectation at a rate of $\frac{1}{2d_0 n}(E(N_{\lambda: \lambda}^2) - 1)$, where $d_0$ is a damping parameter, $n$ is the search space dimension, and $N_{\lambda: \lambda}^2$ is related to the squared order statistic of normal random variables.
  • Impact of Cumulation: With cumulation ($0 < c < 1$), the step-size also diverges geometrically for $\lambda \ge 3$ and for $\lambda=2$. The rate of divergence is shown to be $\frac{1}{2d_0 n}(2(1-c)E(N_{1:\lambda}^2) + c(E(N_{\lambda:\lambda}^2) - 1))$.
  • Variance Analysis (Theorem 4): The paper derives an expression for the variance of the step-size increment, showing that it decreases with cumulation (smaller 'c') and increases with the dimension 'n'. This suggests that cumulation enhances stability.

Limitations and Future Work

  • Linear Functions: The analysis is strictly limited to linear functions. While this provides a foundational understanding, the behavior on non-linear, complex objective functions might differ.
  • Future Research: The authors suggest that studying the behavior of $(X_t)_{t \in \mathbb{N}}$ (the parent points) with cumulation would require analyzing a double Markov chain, which is left for future research. This would provide a more complete picture of the CSA-ES's performance on optimization problems.

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 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: Technical Report}},
  booktitle = {HAL},
  year = {2012},
}

Loading related content...

Figure