Abstract:

In optimization, CMA-ES is the state-of-the-art algorithm among the evolution strategies. Although it has found many applications for more than 20 years, a proof of its convergence remained an open question. Solving this problem is the goal of this thesis. More precisely, we provide theoretical guarantees of linear convergence of CMA-ES when minimizing an ellipsoidal objective function. Moreover, we prove that second-order information of a convex-quadratic function is learnt since the covariance matrix approximates the inverse Hessian matrix. To establish our results, we normalize the states of the algorithm and define a Markov chain when the objective function is scaling-invariant. The stability of this Markov chain proves then the convergence of CMA-ES. We decompose this proof in several steps. In the first two chapters, we give a methodology to prove the irreducibility and topological properties of Markov chains that we apply to the normalized Markov chain underlying CMA-ES. After the next two chapters, we obtain that this Markov chain is geometrically ergodic for ellipsoidal problems. The last chapter concludes our proof.

Abstract:

In this paper, we analyze a large class of general nonlinear state-space models on a state-space $\mathsf X$, defined by the recursion $\phi_{k+1} = F(\phi_k,\alpha(\phi_k,U_{k+1}))$, $k \in\mathbb N$, where $F,\alpha$ are some functions and $\{U_{k+1}\}_{k\in\mathbb N}$ is a sequence of i.i.d. random variables. More precisely, we extend conditions under which this class of Markov chains is irreducible, aperiodic and satisfies important continuity properties, relaxing two key assumptions from prior works. First, the state-space $\mathsf X$ is supposed to be a smooth manifold instead of an open subset of a Euclidean space. Second, we only suppose that $F$ is locally Lipschitz continuous. We demonstrate the significance of our results through their application to Markov chains underlying optimization algorithms. These schemes belong to the class of evolution strategies with covariance matrix adaptation and step-size adaptation.

Abstract:

We study ill-conditioned positive definite matrices that are disturbed by the sum of rank-one matrices of a specific form. We provide estimates for the eigenvalues and eigenvectors. When the condition number of the initial matrix tends to infinity, we bound the values of the coordinates of the eigenvectors of the perturbed matrix. Equivalently, in the coordinate system where the initial matrix is diagonal, we bound the rate of convergence of coordinates that tend to zero.

Abstract:

Scaling-invariant functions preserve the order of points when the points are scaled by the same positive scalar (usually with respect to a unique reference point). Composites of strictly monotonic functions with positively homogeneous functions are scaling-invariant with respect to zero. We prove in this paper that also the reverse is true for large classes of scaling-invariant functions. Specifically, we give necessary and sufficient conditions for scaling-invariant functions to be composites of a strictly monotonic function with a positively homogeneous function. We also study sublevel sets of scaling-invariant functions generalizing well-known properties of positively homogeneous functions.

Abstract:

In this paper we introduce modified versions of CMA-ES with the objective to help to prove convergence of CMA-ES. In order to ensure that the modifications do not alter the performances of the algorithm too much, we benchmark variants of the algorithm derived from them on problems of the bbob test suite. We observe that the main performances losses are observed on ill-conditioned problems, which is probably due to the absence of cumulation in the adaptation of the covariance matrix. However, the versions of CMA-ES presented in this paper have globally similar performances to the original CMA-ES. Data

Abstract:

In this paper, we investigate the effect of a learning rate for the mean in Evolution Strategies with recombination. We study the effect of a half-line search after the mean shift direction is established, hence the learning rate value is conditioned to the direction. We prove convergence and study convergence rates in different dimensions and for different population sizes on the sphere function with the step-size proportional to the distance to the optimum. We empirically find that a perfect half-line search increases the maximal convergence rate on the sphere function by up to about 70%, assuming the line search imposes no additional costs. The speedup becomes less pronounced with increasing dimension. The line search reduces—however does not eliminate—the dependency of the convergence rate on the step-size. The optimal step-size assumes considerably smaller values with line search, which is consistent with previous results for different learning rate settings. The step-size difference is more pronounced in larger dimension and with larger population size, thereby diminishing an important advantage of a large population.