research-article

Objective improvement in information-geometric optimization

Authors:

Youhei Akimoto,

Yann OllivierAuthors Info & Claims

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

Pages 1 - 10

https://doi.org/10.1145/2460239.2460241

Published: 16 January 2013 Publication History

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-μ 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.

References

[1]

Y. Akimoto, A. Auger, and N. Hansen. Convergence of the continuous time trajectories of isotropic evolution strategies on monotonic 5?2-composite functions. In Parallel Problem Solving from Nature - PPSN XII, 12th International Conference, number 7491 in Lecture Notes in Computer Science, pages 42--51, Taormina, Italy, September 1-5 2012. Springer.

Digital Library

[2]

Y. Akimoto, Y. Nagata, I. Ono, and S. Kobayashi. Bidirectional relation between CMA evolution strategies and natural evolution strategies. In R. Schaefer, C. Cotta, J. Kolodziej, and G. Rudolph, editors, Parallel Problem Solving from Nature - PPSN XI, 11th International Conference, volume 6238 of Lecture Notes in Computer Science, pages 154--163, Krakóow, Poland, September 11-15 2010. Springer.

Digital Library

[3]

S.-i. Amari. Natural gradient works efficiently in learning. Neural Computation, 10(2):251--276, 1998.

Digital Library

[4]

S.-i. Amari and H. Nagaoka. Methods of Information Geometry. Translations of Mathematical Monographs vol. 191. American Mathematical Society, 2000.

[5]

L. Arnold, A. Auger, N. Hansen, and Y. Ollivier. Information-Geometric Optimization algorithms: A unifying picture via invariance principles. arXiv:1106.3708v1, 2011.

[6]

S. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithm. In Proceedings of the 12th International Conference on Machine Learning, pages 38--46, 1995.

[7]

P.-T. D. Boer, D. P. Kroese, S. Mannor, and R. Y. Rubinstein. A tutorial on the cross-entropy method. Annals of Operations Research, (134):19--67, 2005.

[8]

V. S. Borkar. Stochastic approximation: a dynamical systems viewpoint. Cambridge University Press, 2008.

[9]

P. Dayan and G. E. Hinton. Using expectation-maximization for reinforcement learning. Neural Computation, 9(2):271--278, 1997.

Digital Library

[10]

M. Dorigo, V. Maniezzo, and A. Colorni. The ant system: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - part B, 26(1):1--13, 1996.

Digital Library

[11]

N. Hansen, S. D. Muller, and P. Koumoutsakos. Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1):1--18, 2003.

Digital Library

[12]

G. E. Hinton. Connectionist learning procedures. Artificial Intelligence, 40(1--3):185--234, 1989.

Digital Library

[13]

S. Kullback. Information theory and statistics. Dover Publications Inc., Mineola, NY, 1997. Reprint of the second (1968) edition.

[14]

H. J. Kushner and G. G. Yin. Stochastic approximation and recursive algorithms and applications. Springer Verlag, 2nd edition, 2003.

[15]

P. Larra naga and J. A. Lozano. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2002.

[16]

L. Malagò, M. Matteucci, and G. Pistone. Towards the geometry of estimation of distribution algorithms based on the exponential family. In H.-G. Beyer and W. B. Langdon, editors, FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms, pages 230--242. ACM, 2011.

Digital Library

[17]

F. Sehnke, C. Osendorfer, T. Rückstie', A. Graves, J. Peters, and J. Schmidhuber. Parameter-exploring policy gradients. Neural Networks, 23(4):551--559, 2010.

Digital Library

Cited By

Akimoto YWagner M(2022)Monotone improvement of information-geometric optimization algorithms with a surrogate functionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528690(1354-1362)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528690
Akimoto Y(2022)Analysis of Surrogate-Assisted Information-Geometric Optimization AlgorithmsAlgorithmica10.1007/s00453-022-01087-886:1(33-63)Online publication date: 22-Dec-2022
https://doi.org/10.1007/s00453-022-01087-8
Pierrot TPerrin-Gilbert NSigaud O(2021)First-Order and Second-Order Variants of the Gradient Descent in a Unified FrameworkArtificial Neural Networks and Machine Learning – ICANN 202110.1007/978-3-030-86340-1_16(197-208)Online publication date: 7-Sep-2021
https://doi.org/10.1007/978-3-030-86340-1_16
Show More Cited By

Index Terms

Objective improvement in information-geometric optimization
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Information-geometric optimization algorithms: a unifying picture via invariance principles

We present a canonical way to turn any smooth parametric family of probability distributions on an arbitrary search space X into a continuous-time black-box optimization method on X, the information-geometric optimization (IGO) method. Invariance as a ...
Exponential natural evolution strategies
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computation

The family of natural evolution strategies (NES) offers a principled approach to real-valued evolutionary optimization by following the natural gradient of the expected fitness. Like the well-known CMA-ES, the most competitive algorithm in the field, ...
Comparing natural evolution strategies to BIPOP-CMA-ES on noiseless and noisy black-box optimization testbeds
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computation

Natural Evolution Strategies (NES) are a recent member of the class of preal-valued optimization algorithms that are based on adapting search distributions. Exponential NES (xNES) are the most common instantiation of NES, and particularly appropriate ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOGA XII '13: Proceedings of the twelfth workshop on Foundations of genetic algorithms XII

January 2013

198 pages

ISBN:9781450319904

DOI:10.1145/2460239

General Chairs:
Frank Neumann
The University of Adelaide, Australia
,
Kenneth De Jong
George Mason University, USA

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 January 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

FOGA '13

Sponsor:

SIGEVO

FOGA '13: Foundations of Genetic Algorithms XII

January 16 - 20, 2013

Adelaide, Australia

Acceptance Rates

Overall Acceptance Rate 72 of 131 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Akimoto YWagner M(2022)Monotone improvement of information-geometric optimization algorithms with a surrogate functionProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528690(1354-1362)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528690
Akimoto Y(2022)Analysis of Surrogate-Assisted Information-Geometric Optimization AlgorithmsAlgorithmica10.1007/s00453-022-01087-886:1(33-63)Online publication date: 22-Dec-2022
https://doi.org/10.1007/s00453-022-01087-8
Pierrot TPerrin-Gilbert NSigaud O(2021)First-Order and Second-Order Variants of the Gradient Descent in a Unified FrameworkArtificial Neural Networks and Machine Learning – ICANN 202110.1007/978-3-030-86340-1_16(197-208)Online publication date: 7-Sep-2021
https://doi.org/10.1007/978-3-030-86340-1_16
Wen YChen XWei YFan YZeng TDing Z(2019)SAR Parameter Estimation Method for Rectangle Plane Based on Information Geometry2019 IEEE International Conference on Signal, Information and Data Processing (ICSIDP)10.1109/ICSIDP47821.2019.9173226(1-5)Online publication date: Dec-2019
https://doi.org/10.1109/ICSIDP47821.2019.9173226
Ollivier YArnold LAuger AHansen N(2017)Information-geometric optimization algorithmsThe Journal of Machine Learning Research10.5555/3122009.312202718:1(564-628)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3122027
Loshchilov I(2017)Lm-cmaEvolutionary Computation10.1162/EVCO_a_0016825:1(143-171)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00168
Bensadon J(2015)Black-Box Optimization Using Geodesics in Statistical ManifoldsEntropy10.3390/e1701030417:1(304-345)Online publication date: 13-Jan-2015
https://doi.org/10.3390/e17010304

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten