Objective Improvement in Information-Geometric Optimization

Youhei Akimoto 1 Yann Ollivier 1
1 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 : Information-Geometric Optimization (IGO) is a unified framework of stochastic algorithms for optimization problems. Given a family of probability distributions, IGO turns the original optimization problem into a new maximization problem on the parameter space of the probability distributions. IGO updates the parameter of the probability distribution along the natural gradient, taken with respect to the Fisher metric on the parameter manifold, aiming at maximizing an adaptive transform of the objective function. IGO recovers several known algorithms as particular instances: for the family of Bernoulli distributions IGO recovers PBIL, for the family of Gaussian distributions the pure rank-mu CMA-ES update is recovered, and for exponential families in expectation parametrization the cross-entropy/ML method is recovered. This article provides a theoretical justification for the IGO framework, by proving that any step size not greater than 1 guarantees monotone improvement over the course of optimization, in terms of q-quantile values of the objective function f. The range of admissible step sizes is independent of f and its domain. We extend the result to cover the case of different step sizes for blocks of the parameters in the IGO algorithm. Moreover, we prove that expected fitness improves over time when fitness-proportional selection is applied, in which case the RPP algorithm is recovered.
Type de document :
Communication dans un congrès
Foundations of Genetic Algorithms XII, Jan 2013, Adelaide, Australia. 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00752489
Contributeur : Youhei Akimoto <>
Soumis le : jeudi 7 mars 2013 - 12:14:45
Dernière modification le : jeudi 5 avril 2018 - 12:30:12
Document(s) archivé(s) le : dimanche 2 avril 2017 - 10:06:10

Fichiers

sigproc-sp.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00752489, version 3
  • ARXIV : 1211.3831

Collections

Citation

Youhei Akimoto, Yann Ollivier. Objective Improvement in Information-Geometric Optimization. Foundations of Genetic Algorithms XII, Jan 2013, Adelaide, Australia. 2013. 〈hal-00752489v3〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

154