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