ES Gaussian Mutation

Recall that in basic ES, we do Gaussian mutation:

$$x^{\prime }=x+\sigma z,z\sim \mathcal{N}(0,1)$$

where $\sigma$ controls the mutation strength. The distribution of the steps is Gaussian, with variance ${\sigma }^2$.

Note that it’s important that we first mutate the step size $\sigma \to {\sigma }^{\prime }$, and then mutate the solution using the new step size. This means that the new individual $⟨x^{\prime },{\sigma }^{\prime }⟩$ is evaluate in directly; the primary evaluation is that we can tell $x^{\prime }$ is good if $f(x^{\prime })$ is good, and the second evaluation is that we can tell ${\sigma }^{\prime }$ is good if it produced a good $x^{\prime }$.

We can see that with $\sigma$ wider, we get a wider exploration. At different stages of optimization, the search needs different behavior; early on, larger steps helps exploration. Later on when we get close to a good solution, smaller steps help fine-tune.

The 5 rule is a super basic basic version of this:

• If success rate is too high, $\sigma$ is too small
• If success rate is too low, $\sigma$ is too large

Case 1: Global Step Size

The simplest case uses one single $\sigma$ for all variables. The step size mutation is given as

$${\sigma }^{\prime }=\sigma \exp (\tau \mathcal{N}(0,1))$$

and the solution mutation is given as

$$x^{\prime }=x+{\sigma }^{\prime }z$$

The exponential form is used so that ${\sigma }^{\prime }$ always stays positive.

In this case, the covariance is

$$\text{Cov}(x^{\prime }-x)={\sigma }^{\prime }I$$

Every direction has the same variance.

Geometry of Gaussian Mutation

Why can’t we always just use our global step size above?

Consider a problem in a higher dimension $n$, where our our isotropic model becomes $x^{\prime }=x+\sigma z,z\sim \mathcal{N}(0,I_n)$:

• $z$ is an $n$-dimensional standard normal vector.
• $I_n$ is the identity matrix
• $\sigma >0$ is the global step size

Viewing this as a distribution, we can also say that

$$x^{\prime }\sim \mathcal{N}(x,{\sigma }^2{I}_n)$$

This is radially symmetric around $x$, with equal variance in all directions. Thus, there is no preferred search direction, with a spherical sampling cloud.

The expected step length is given as:

$$\begin{array}{rl}E[||x^{\prime }-x|{|}^2]& ={\sigma }^{2}n\\ E[||x^{\prime }-x||]& \approx \boxed{\sigma \sqrt{n}}\end{array}$$

However, remember that high-dimensional spaces behave weirdly. Most probability mass lies on a thin shell, $||z||\approx \sqrt{n}$. Thus, mutations are rarely small in high $n$.

Ill-conditioned landscapes

Considered an objective like $f(x)=x_1^2+1000x_2^2$. The level sets are ellipses, with anisotropic curvature. Curvature along $x_2$ is 1000 times steeper than along $x_1$. Thus, there’s a condition number of $\kappa =1000$.

Mutation samples are spherical, but the objective is anisotropic.

• Too large steps in steep direction ($x_2$) $⟹$ rejected moves
• Too small steps in flat direction ($x_1$) $⟹$ slow progress

Case 2: Uncorrelated Mutation

For the ill-formed landscapes, a single global $\sigma$ is too crude, as some variables need larger mutations than others. Thus, we use one step size per coordinate:

$$⟨x_1,\dots ,x_n,{\sigma }_1,\dots ,{\sigma }_n⟩$$

where each coordinate mutates its own scale:

$$x_i^{\prime }=x_i+{\sigma }_i^{\prime }{z}_i$$

with

$${\sigma }_i^{\prime }={\sigma }_i\exp ({\tau }^{\prime }Z+\tau Z_i)$$

• $Z\sim \mathcal{N}(0,1)$ (global)
• $Z_i\sim \mathcal{N}(0,1)$ (per-coordinate)
• Once again, $\exp$ guarantees positivity.

This creates an axis-aligned ellipsoid instead of a sphere.

$\tau$ and ${\tau }^{\prime }$ are learning rate parameters:

$${\tau }^{\prime }=\frac{1}{\sqrt{2n}},\tau =\frac{1}{\sqrt{2\sqrt{n}}}$$

• ${\tau }^{\prime }$ is the global adaptation strength (shared across coordinates)
• $\tau$ is the coordinate-wise adaptation strength

This dimension-dependent method controls the variance of $\log {\sigma }_i^{\prime }$, preventing unstable step-size explosions in high dimensions. Thus, adaptation speed is comparable across problem sizes, and we can ensure that self-adaptation remains stable as the dimension $n$ grows. Larger $n$ means smaller learning rates, and prevents unstable covariance, ensuring smooth adaptation of search geometry.

Here, our covariance has become

$$\text{Cov}(x^{\prime }-x)=D(\sigma {)}^2=\text{diag}({\sigma }_1^2,\dots ,{\sigma }_n^2)$$

This is still uncorrelated, because the covariance matrix is diagonal; the mutation cloud is an ellipsoid aligned with the coordinate axes. Note that we can write the update as $x^{\prime }=x+D(\sigma )z$.

Case 3: Correlated Mutation

Even multiple coordinate-wise step sizes are not enough if the important search directions are rotated relative to the coordinate axes. Thus, we want to generalize the mutation to $x^{\prime }=x+\mathcal{N}(0,{\sigma }^{2}C)$ where $C$ is a learned covariance matrix.

Specifically, we use:

$$x^{\prime }=x+BDz,z\sim N(0,I)$$

where:

• $D=\text{diag}({\sigma }_1,\dots ,{\sigma }_n)$ controls axis lengths
• $B$ is an orthogonal rotation matrix constructed from angles ${\alpha }_{ij}$

Then:

$$\text{Cov}(x^{\prime }-x)=C=B{D}^2{B}^T$$

Let’s walk through the full flow.

First, our chromosome is now $⟨x,\sigma ,\alpha ⟩$. We first mutate step sizes:

$${\sigma }_i^{\prime }={\sigma }_i\exp ({\tau }^{\prime }Z+\tau Z_i)$$

Then mutate rotation angles:

$${\alpha }_{ij}^{\prime }={\alpha }_{ij}+\beta N_{ij}(0,1)$$

$\beta$ controls rotation-angle mutation; small angle updates ensure gradual geometry change.

We often also use some constraints like ${\sigma }_i^{\prime }\ge {ϵ}_0$ and $\left|{\alpha }_{ij}^{\prime }\right|\le \pi$, which prevent collapse of mutation strength and avoid premature convergence. We also do angle wrapping to ensure numerical stability and uniqueness. We can generalize this into CMA-ES.

Correlated ES Example