Objective improvement in information-geometric optimization

DOI10.1145/2460239.2460241MaRDI QIDQ5276106zbMATH OpenOpenAlexFDO

Authors Youhei Akimoto, Y. Ollivier

Publication date 14 July 2017

Published in Proceedings of the twelfth workshop on Foundations of genetic algorithms XII (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1211.3831, https://hal.inria.fr/hal-00752489v3/file/sigproc-sp.pdf

zbMATH Keywords

black-box optimizationinformation-geometric optimizationnatural gradientquantile improvementstep size

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Approximation methods and heuristics in mathematical programming (90C59)

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.

Recommendations

• Information-geometric optimization algorithms: a unifying picture via invariance principles
• Information-geometric optimization: the interest of information theory for discrete and continuous optimization. (Abstract)
• Optimization via Information Geometry
• Theoretical foundation for CMA-ES from information geometry perspective
• Information Geometry of the Gaussian Distribution in View of Stochastic Optimization

Cited in

(6)

• Koszul information geometry and Souriau geometric temperature/capacity of Lie group thermodynamics
• Optimization via Information Geometry
• Information-geometric optimization algorithms: a unifying picture via invariance principles
• Information-geometric optimization: the interest of information theory for discrete and continuous optimization. (Abstract)
• Analysis of surrogate-assisted information-geometric optimization algorithms
• Improving weighted information criterion by using optimization

This page was built for publication: Objective improvement in information-geometric optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5276106)