Linear convergence of evolution strategies with covariance matrix adaptation

Convergence linéaire de stratégies d'évolution à matrices de covariances adaptatives En tant que méthode à l’état de l’art parmis les stratégies d’évolution, CMA-ES un algorithme d’optimisation sans dérivées avec de nombreuses applications, mais dont la convergence est restée un problème ouvert depuis plus de 20 ans. Le but de cette thèse est d’apporter des garanties théoriques de convergence de CMA-ES. Ainsi, nous prouvons que CMA-ES approche le minimum de fonctions ellipsoïdes avec une erreur géometrique, et nous vérifions la conjecture de la matrice de covariance dans CMA-ES qui estime l’inverse de la Hessienne d’une fonction convexe-quadratique.Notre démonstration s’appuie sur l’analyse de processus stochastiques et est établie en plusieurs étapes.En effet, nous définissons un processus par la normalisation des variables de CMA-ES. Cette approche aréussi à analyser des ES avec adaptation du pas : en normalisant la variable de moyenne (translaté parl’optimum) par le pas, cela forme une chaîne de Markov lorsque la fonction objective est invariante parchangement d’échelle. Sous des hypothèses supplémentaires, cette chaîne est géometriquement ergodique, ce qui permet de prouver la convergence de l’algorithme. Pour CMA-ES, nous devons inclure la matrice de covariance. Nous introduisons d’abord une fonction de normalisation R sur l’espace des matrices définies positives, et la normalisation de la moyenne par le pas et la fonction R appliquée à la matrice de covariance, nous espérons obtenir un processus stationaire. Avec une matrice de covariance normalisée et des chemins d’évolution normalisés, ce processus est une chaîne de Markov pour des fonctions objectives invariantes par changement d’échelle. La preuve de sa convergence vers une probabilité stationnaire est la clé de notre démonstration et occupera les chapitres 2 et 4.Tout d’abord, nous donnons dans le chapitre 1 une méthode pour établir l’irréductibilité, l’apériodicitéet des propriétés topologiques de chaînes de Markov homogènes, à valeurs dans des variétés et avecdes mises à jour non lisses. Ceci est la généralisation d’une analyse de modèles d’espace d’état non-linéaires qui n’incluaient que des espaces d’états euclidiens et des fonctions de mise à jour continuementdifférentiables. En s’appuyant sur des résultats de l’analyse non-lisse et de la théorie de la mesure sur desvariétés topologique, nous avons pu étendre ce travail.Ces résultats préliminaires permettent une preuve de convergence de CMA-ES qui repose sur l’analysede stabilité de chaînes de Markov sous-jacentes, puisque la normalisation de la matrice de covariancedéfinit un espace d’état qui est une variété, et car les adaptations de pas standards peuvents être non-lisses. Le chapitre 2 explique comment utiliser la méthode mentionnée ci-dessus pour prover que la chaîne normalisée est une T-chaîne irréductible et apériodique.Nous démontrons ensuite son ergodicité en utilisant une méthode de Foster-Lyapunov. Dans lechapitre 4, nous trouvons une fonction de potentiel qui satisfait une condition de dérive en-dehors d’uncompact. Puisque la chaîne est une T-chaîne, les compacts sont petits et puisqu’elle est irréductible etapériodique, une condition de dérive géométrique en-dehors d’un ensemble petit démontre l’ergodicitégéometrique. Cependant, la complexité de la chaîne (avec plusieurs variables dont une matrice decovariance normalisée) nous impose to restreindre notre preuve à des fonctions objectifs ellipsoïdales.L’étape finale de notre démonstration est donnée dans le chapitre 5. Nous utilisons un théorèmeergodique et une loi des grands nombres pour déduire la convergence linéaire de CMA-ES. De plus, nousutilisons l’invariance par transformations affines de l’algorithme pour établir que la matrice de covariancede CMA-ES apprend l’inverse de la Hessienne de fonctions convexe-quadratiques, et que le taux deconvergence est indépendant de quelle fonction ellipsoïdale est minimsée.