Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem

Alexandre Chotard; Anne Auger; Nikolaus Hansen

Source-linked AI summary

Markov Chain Analysis of Cumulative Step-size Adaptation on a Linear Constrained Problem

Alexandre Chotard, Anne Auger, Nikolaus Hansen

arXiv:1510.04409v1Oct 15, 2015math.OC

TL;DR

The paper asks how a resampling-based (1, λ)-ES behaves on a linear constrained problem under constant and cumulative step-size adaptation. It models each setting with Markov chains and proves stability in the constant-step-size and c = 1 CSA cases. These results establish constant-speed divergence for fixed step-size and geometric divergence or convergence for CSA, while the full c < 1 case remains difficult.

Problem
Earlier analyses of this constrained (1, λ)-ES relied on simplified models, while the exact behavior and stability properties remained to be established rigorously.
Method
The paper models normalized constraint distance, and for CSA also the evolution path, as continuous-state Markov chains whose stability is analyzed mathematically.
Results
The Markov chains are stable for constant step-size and CSA with c = 1; the algorithm then diverges at constant speed or changes geometrically at rate r, with the sign of r determining divergence or convergence.
Takeaways & Limitations
The analysis provides a rigorous framework for estimating divergence rates and supports fast-converging Monte Carlo simulations for studying parameter influence.
Takeaways & Limitations
The full CSA analysis for c < 1 remains difficult because the evolution path and normalized distance must be controlled together.

Abstract

from arXiv · show

This paper analyzes a (1, $λ$)-Evolution Strategy, a randomized comparison-based adaptive search algorithm, optimizing a linear function with a linear constraint. The algorithm uses resampling to handle the constraint. Two cases are investigated: first the case where the step-size is constant, and second the case where the step-size is adapted using cumulative step-size adaptation. We exhibit for each case a Markov chain describing the behaviour of the algorithm. Stability of the chain implies, by applying a law of large numbers, either convergence or divergence of the algorithm. Divergence is the desired behaviour. In the constant step-size case, we show stability of the Markov chain and prove the divergence of the algorithm. In the cumulative step-size adaptation case, we prove stability of the Markov chain in the simplified case where the cumulation parameter equals 1, and discuss steps to obtain similar results for the full (default) algorithm where the cumulation parameter is smaller than 1. The stability of the Markov chain allows us to deduce geometric divergence or convergence , depending on the dimension, constraint angle, population size and damping parameter, at a rate that we estimate. Our results complement previous studies where stability was assumed.

1 Introduction

The paper rigorously analyzes a constrained (1, λ)-ES using Markov chains, addressing limitations in earlier simplified models and focusing on cumulative step-size adaptation.

Motivation: The study examines a (1, λ)-ES optimizing a linear function under a linear constraint handled by resampling.The linear objective represents divergence away from an optimum, while the constraint represents proximity to a boundary.
Motivation: Earlier studies found that adaptive step-size mechanisms fail to diverge unless internal algorithm parameters satisfy requirements, but relied on simplified models.This paper instead analyzes the algorithm without those simplifications.
Method: The analysis represents the algorithm through a Markov chain pairing the evolution path with distance to the constraint normalized by the step-size.Its stability properties support rigorous deductions about geometric divergence and parameter effects.
Results: For constant step-size, the paper proves a stationary distribution for normalized constraint distance and constant-speed divergence.For CSA with cumulation parameter c = 1, the logarithmic step-size change converges to a parameter-dependent constant r.
Scope: The paper extends a conference version with new c = 1 path-length-control analysis, discussion of c < 1, new figures, and convergence of the progress rate in Theorem 1.The paper is organized around problem definition, preliminary distributions, constant step-size analysis, CSA analysis, and discussion.

2 Problem statement and algorithm definition

The algorithm samples Gaussian candidates, resamples infeasible points, selects the best feasible candidate, and updates the search point and adaptation parameters on a linear constrained problem.

Algorithm: At each iteration, the (1, λ)-ES generates λ candidates from a multivariate normal distribution centered at the current vector.Infeasible candidates are resampled until feasible.
Algorithm: The selected candidate is the feasible solution with the best objective value, and the current vector is updated to that solution.The selected step is the feasible step associated with the maximizing candidate.
Algorithm: The step-size and other internal parameters are then adapted according to a rule determined by selected steps, initialization, and algorithm parameters.The specific adaptation rules are defined later in the paper.
Problem: The objective and constraint are linear, with unit gradient norms and constraint angle θ ∈ (0, π/2).The feasible region is defined by g(x) > 0, with g(x) = −[x]1 cos θ − [x]2 sin θ.
Problem: Only the first two coordinates are affected by resampling and objective-based selection; coordinates 3 through n remain standard normal.This follows from the chosen coordinate system and coordinate independence.
Problem: The normalized signed distance δt = −Xt.n/σt measures the current vector’s distance to the constraint relative to the step-size.The initialization X0 = −n and σ0 = 1 gives δ0 = 1.

3 Preliminary results and definitions

The preliminary analysis characterizes feasible and selected steps through distributions depending on normalized constraint distance, enabling finite-sample representations for later Markov-chain analysis.

Feasible steps: A feasible step is a standard multivariate normal vector truncated by the linear constraint.Its distribution depends on the normalized distance δt to the constraint.
Feasible steps: The probability that a sampled step is feasible is determined by δt through the normal distribution along the constraint normal.This provides the basis for describing accepted samples under resampling.
Feasible steps: The feasible-step distribution can be generated from a finite number of independent random variables using a generalized inverse and a standard normal sample.This replaces resampling, which may require an unbounded number of samples.
Feasible steps: In coordinates aligned with the constraint normal, the normal component has a truncated-normal distribution with CDF min(1, Φ(x)/Φ(δt)).The perpendicular component remains an independent standard normal variable.
Selected steps: After selection, the marginal distribution of the selected step depends only on δt and has explicitly derived coordinate densities.The first-coordinate density uses F1,δ, while the second-coordinate marginal is obtained by integration.
Selected steps: The selected step is represented as a function of δt and finitely many independent random variables, yielding an explicit density for subsequent analysis.The construction uses functions based on transformed uniform and normal samples.

4 Constant step-size case

For constant step-size, the analysis models normalized distance to the constraint as a homogeneous Markov chain and proves its stability. A law of large numbers then yields divergence of the objective sequence and an exact positive progress rate.

Divergence result: The progress rate ϕ* converges to the same strictly positive constant as the divergence rate.The rate is represented as an expectation involving the stationary measure π and mutation variables W.
Markov-chain model: The normalized distance δ_t = g(X_t)/σ is a homogeneous Markov chain central to the divergence analysis.Its transition depends on the current state and independent mutation variables.
Stability properties: The chain is irreducible, strongly aperiodic, and has compact sets and sets of the form (0, M] as small sets.These properties support the subsequent stability analysis.
Stability properties: The chain is V-geometrically ergodic, Harris-recurrent, and positive, with invariant probability measure π.A suitable drift function is V(δ) = exp(αδ) for sufficiently small α > 0.
Divergence result: The Markov-chain law of large numbers proves that [X_t]_1 diverges in probability to +∞ at constant speed.The divergence rate is expressed through an expectation under the stationary distribution π.

5 Cumulative Step size Adaptation

The paper models CSA-ES behavior with Markov chains, proving stability and geometric step-size behavior when c = 1 while identifying difficulties for c < 1.

CSA mechanism: CSA adapts the step-size through an evolution path that accumulates selected steps, with c controlling the path’s memory.The modified analysis compares squared path length with the expected squared length n of a Gaussian vector; dσ controls the magnitude of step-size changes.
Markov-chain model: For c < 1, (δt, pt) forms a time-homogeneous Markov chain, whereas c = 1 reduces the analysis to the chain δt alone.The transition depends on the current state and i.i.d. random variables.
Step-size behavior: For c = 1, the average logarithmic step-size change converges to a constant, and its sign determines geometric divergence or convergence of the step-size.A strictly positive limit implies geometric divergence, while a negative limit implies geometric convergence.
Stability: For c = 1, the δt chain is ψ-irreducible, strongly aperiodic, positive Harris, and V-geometrically ergodic with an invariant measure.The drift function is V(δ) = δ^α + δ^-α for sufficiently small α > 0.

6 Discussion

The paper rigorously establishes Markov-chain stability for constant step-size and c = 1 CSA-ES, deriving divergence or convergence behavior and supporting simulation-based rate estimates.

6 Discussion: V-geometric ergodicity of the normalized-distance Markov chain is proved for constant step-size and CSA with c = 1.This stability was previously presumed for the constant step-size analysis.
6 Discussion: Constant step-size yields divergence at a constant speed, whereas step-size adaptation yields geometric divergence or convergence.The outcome depends on problem and algorithm parameters such as dimension, constraint angle, population size, and damping.
6 Discussion: Simulations suggest geometric divergence under CSA for sufficiently small c or sufficiently large λ.As θ approaches zero, the critical scaling follows c ∝ θ2 or λ ∝ 1/θ.
6 Discussion: Repairing infeasible solutions can solve the problem for fixed λ and c across all constraint angles, unlike resampling in the cited comparison.This comparison is reported as a result from previous work.
6 Discussion: Covariance adaptation changes the effective constraint angle, potentially making the problem arbitrarily close to the unconstrained linear case.The paper presents this as one reason covariance adaptation may be useful when pure step-size adaptation can fail.
6 Discussion: The Markov-chain methodology is presented as applicable to many ES variants and complementary to earlier simplified analyses.It provides a rigorous framework for analyzing constrained ES behavior.

Appendix

The appendix develops limiting and integrability arguments for transition-density quantities using dominated convergence and related probabilistic calculations.

Appendix: The normalized density p1,δ is bounded by 2ϕ(x) and converges to ϕ(x) as δ approaches infinity.This supports convergence of the associated cumulative distribution function F1,δ to Φ.
Appendix: For large δ, expectations involving G(δ, W) converge to expressions involving the order-statistic variable Nλ:λ.The convergence follows from pointwise limits and integrable domination.
Appendix: The appendix also records finite limiting expressions for Eδ/(δα + δ^-α) at large and small δ.At large δ the limit is E1E2E3, while at small δ it is 0.
Appendix: Dominated convergence is used to show Hδ/(δα + δ^-α) converges to 0 as δ approaches infinity.The argument requires α to be sufficiently small so the dominating function is integrable.
Appendix: Dominated convergence likewise shows Hδ/(δα + δ^-α) converges to 0 as δ approaches 0.The proof restricts δ to (0, 1] and establishes integrability of an upper bound.