Efficient Covariance Matrix Update for Variable Metric Evolution Strategies

Thorsten Suttorp 1 Nikolaus Hansen 2, 3, 4 Christian Igel 1
2 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
3 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : Randomized direct search algorithms for continuous domains, such as Evolution Strategies, are basic tools in machine learning. They are especially needed when the gradient of an objective function (e.g., loss, energy, or reward function) cannot be computed or estimated efficiently. Application areas include supervised and reinforcement learning as well as model selection. These randomized search strategies often rely on normally distributed additive variations of candidate solutions. In order to efficiently search in non-separable and ill-conditioned landscapes the covariance matrix of the normal distribution must be adapted, amounting to a variable metric method. Consequently, Covariance Matrix Adaptation (CMA) is considered state-of-the-art in Evolution Strategies. In order to sample the normal distribution, the adapted covariance matrix needs to be decomposed, requiring in general $\Theta(n^3)$ operations, where $n$ is the search space dimension. We propose a new update mechanism which can replace a rank-one covariance matrix update and the computationally expensive decomposition of the covariance matrix. The newly developed update rule reduces the computational complexity of the rank-one covariance matrix adaptation to $\Theta(n^2)$ without resorting to outdated distributions. We derive new versions of the elitist Covariance Matrix Adaptation Evolution Strategy (CMA-ES) and the multi-objective CMA-ES. These algorithms are equivalent to the original procedures except that the update step for the variable metric distribution scales better in the problem dimension. We also introduce a simplified variant of the non-elitist CMA-ES with the incremental covariance matrix update and investigate its performance. Apart from the reduced time-complexity of the distribution update, the algebraic computations involved in all new algorithms are simpler compared to the original versions. The new update rule improves the performance of the CMA-ES for large scale machine learning problems in which the objective function can be evaluated fast.
Type de document :
Article dans une revue
Machine Learning, Springer Verlag, 2009
Liste complète des métadonnées

Littérature citée [64 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00369468
Contributeur : Nikolaus Hansen <>
Soumis le : lundi 8 mars 2010 - 20:04:12
Dernière modification le : jeudi 10 mai 2018 - 02:06:34
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 13:55:25

Fichier

SuttorpEtAl-finaldraft.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369468, version 1

Collections

Citation

Thorsten Suttorp, Nikolaus Hansen, Christian Igel. Efficient Covariance Matrix Update for Variable Metric Evolution Strategies. Machine Learning, Springer Verlag, 2009. 〈inria-00369468〉

Partager

Métriques

Consultations de la notice

557

Téléchargements de fichiers

933