research-article

Comparison-based natural gradient optimization in high dimension

Authors:

Youhei Akimoto,

Nikolaus HansenAuthors Info & Claims

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

Pages 373 - 380

https://doi.org/10.1145/2576768.2598258

Published: 12 July 2014 Publication History

Abstract

We propose a novel natural gradient based stochastic search algorithm, VD-CMA, for the optimization of high dimensional numerical functions. The algorithm is comparison-based and hence invariant to monotonic transformations of the objective function. It adapts a multivariate normal distribution with a restricted covariance matrix with twice the dimension as degrees of freedom, representing an arbitrarily oriented long axis and additional axis-parallel scaling. We derive the different components of the algorithm and show linear internal time and space complexity. We find empirically that the algorithm adapts its covariance matrix to the inverse Hessian on convex-quadratic functions with an Hessian with one short axis and different scaling on the diagonal. We then evaluate VD-CMA on test functions and compare it to different methods. On functions covered by the internal model of VD-CMA and on the Rosenbrock function, VD-CMA outperforms CMA-ES (having quadratic internal time and space complexity) not only in internal complexity but also in number of function calls with increasing dimension.

References

[1]

Y. Akimoto, Y. Nagata, I. Ono, and S. Kobayashi. Bidirectional Relation between CMA Evolution Strategies and Natural Evolution Strategies. In Parallel Problem Solving from Nature -- PPSN XI, pages 154--163, 2010.

Digital Library

[2]

Y. Akimoto, Y. Nagata, I. Ono, and S. Kobayashi. Theoretical Foundation for CMA-ES from Information Geometry Perspective. Algorithmica, 64:698--716, 2012.

Digital Library

[3]

S. Amari. Natural Gradient Works Efficiently in Learning. Neural Computation, 10(2):251--276, 1998.

Digital Library

[4]

S. Amari, H. Park, and K. Fukumizu. Adaptive method of realizing natural gradient learning for multilayer perceptrons. Neural Computation, 12:1399--1409, 2000.

Digital Library

[5]

Y. Ollivier, L. Arnold, A. Auger, and N. Hansen. Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles. arXiv:1106.3708, 2011.

[6]

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.

[7]

T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra, and J. Schmidhuber. Exponential Natural Evolution Strategies. In Proceedings of Genetic and Evolutionary Computation Conference, pages 393--400, 2010.

Digital Library

[8]

N. Hansen and A. Auger. Principled Design of Continuous Stochastic Search: From Theory to Practice. In Y. Borenstein and A. Moraglio, editors, Theory and Principled Methods for the Design of Metaheuristics. Springer, 2013.

[9]

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

[10]

N. Hansen and A. Ostermeier. Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2):159--195, 2001.

Digital Library

[11]

N. Hansen, A. Ostermeier, and A. Gawelczyk. On the Adaptation of Arbitrary Normal Mutation Distributions in Evolution Strategies: The Generating set Adaptation. In Proceedings of the Sixth International Conference on Genetic Algorithms, pages 57--64, 1995.

Digital Library

[12]

D. A. Harville. Matrix Algebra from a Statistician's Perspective. Springer-Verlag, 2008.

[13]

A. Honkela, M. Tornio, T. Raiko, and J. Karhunen. Natural conjugate gradient in variational inference. In Neural Information Processing, 14th International Conference, ICONIP 2007, pages 305--314, 2008.

Digital Library

[14]

L. Malagò, M. Matteucci, and G. Pistone. Towards the geometry of estimation of distribution algorithms based on the exponential family. In Foundations of Genetic Algorithms, pages 230--242. 2011.

Digital Library

[15]

A. Miyamae, Y. Nagata, I. Ono, and S. Kobayashi. Natural Policy Gradient Methods with Parameter-based Exploration for Control Tasks. In Advances in Neural Information Processing Systems 23, pages 1660--1668, 2010.

[16]

J. Peters and S. Schaal. Natural actor-critic. Neurocomputing, 71(7--9):1180--1190, 2008.

Digital Library

[17]

J. Poland and A. Zell. Main vector adaptation: A CMA variant with linear time and space complexity. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1050--1055, 2001.

[18]

R. Ros and N. Hansen. A simple modification in CMA-ES achieving linear time and space complexity. Parallel Problem Solving from Nature--PPSN X, pages 296--305, 2008.

Digital Library

[19]

Y. Sun, F. Gomez, T. Schaul, and J. Schmidhuber. A Linear Time Natural Evolution Strategy for Non-Separable Functions. GECCO'13 Companion, pages 61--62, 2013.

Digital Library

[20]

T. Suttorp, N. Hansen, and C. Igel. Efficient covariance matrix update for variable metric evolution strategies. Machine Learning, 75(2):167--197, 2009.

Digital Library

[21]

D. Wierstra, T. Schaul, J. Peters, and J. Schmidhuber. Natural evolution strategies. In IEEE Congress on Evolutionary Computation, pages 3381--3387, 2008.

Cited By

Li ZWu WZhang QCai X(2025)Exploring high-dimensional optimization by sparse and low-rank evolution strategySwarm and Evolutionary Computation10.1016/j.swevo.2024.10182892(101828)Online publication date: Feb-2025
https://doi.org/10.1016/j.swevo.2024.101828
Shimizu HToyoda MSilva SPaquete L(2023)A Dynamic Partial Update for Covariance Matrix AdaptationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596385(2394-2397)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596385
Hoffman ZHuntsman SWagner M(2022)Benchmarking an algorithm for expensive high-dimensional objectives on the bbob and bbob-largescale testbedsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534006(1725-1733)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534006
Show More Cited By

Index Terms

Comparison-based natural gradient optimization in high dimension
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
    2. Numerical analysis
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

Projection-Based Restricted Covariance Matrix Adaptation for High Dimension
GECCO '16: Proceedings of the Genetic and Evolutionary Computation Conference 2016

We propose a novel variant of the covariance matrix adaptation evolution strategy (CMA-ES) using a covariance matrix parameterized with a smaller number of parameters. The motivation of a restricted covariance matrix is twofold. First, it requires less ...
Analysis of a natural gradient algorithm on monotonic convex-quadratic-composite functions
GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

In this paper we investigate the convergence properties of a variant of the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Our study is based on the recent theoretical foundation that the pure rank-μ update CMA-ES performs the natural ...
Improved block preconditioners for linear systems arising from half-quadratic image restoration
Abstract
In this paper, the minimization problem with a half-quadratic (HQ) regularization for image restoration is studied. For the structured linear system arising at each step of the Newton method for solving the minimization problem, we ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '14: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation

July 2014

1478 pages

ISBN:9781450326629

DOI:10.1145/2576768

Editor-in-chief:
Christian Igel
Ruhr University of Bochum, University of Copenhagen
,
General Chair:
Dirk V. Arnold
Dalhousie University

Copyright © 2014 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 the author(s) 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: 12 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Agence Nationale de la Recherche

Conference

GECCO '14

Sponsor:

SIGEVO

GECCO '14: Genetic and Evolutionary Computation Conference

July 12 - 16, 2014

BC, Vancouver, Canada

Acceptance Rates

GECCO '14 Paper Acceptance Rate 180 of 544 submissions, 33%;

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
255
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li ZWu WZhang QCai X(2025)Exploring high-dimensional optimization by sparse and low-rank evolution strategySwarm and Evolutionary Computation10.1016/j.swevo.2024.10182892(101828)Online publication date: Feb-2025
https://doi.org/10.1016/j.swevo.2024.101828
Shimizu HToyoda MSilva SPaquete L(2023)A Dynamic Partial Update for Covariance Matrix AdaptationProceedings of the Companion Conference on Genetic and Evolutionary Computation10.1145/3583133.3596385(2394-2397)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583133.3596385
Hoffman ZHuntsman SWagner M(2022)Benchmarking an algorithm for expensive high-dimensional objectives on the bbob and bbob-largescale testbedsProceedings of the Genetic and Evolutionary Computation Conference Companion10.1145/3520304.3534006(1725-1733)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3520304.3534006
Cuccu GRolshoven LVorpe FCudré-Mauroux PGlasmachers TWagner M(2022)DiBBProceedings of the Genetic and Evolutionary Computation Conference10.1145/3512290.3528764(341-349)Online publication date: 8-Jul-2022
https://dl.acm.org/doi/10.1145/3512290.3528764
Nomura MOno I(2022)Fast Moving Natural Evolution Strategy for High-Dimensional Problems2022 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC55065.2022.9870206(1-8)Online publication date: 18-Jul-2022
https://doi.org/10.1109/CEC55065.2022.9870206
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
Nomura MOno I(2022)Towards a Principled Learning Rate Adaptation for Natural Evolution StrategiesApplications of Evolutionary Computation10.1007/978-3-031-02462-7_45(721-737)Online publication date: 15-Apr-2022
https://doi.org/10.1007/978-3-031-02462-7_45
Morinaga DFukuchi KSakuma JAkimoto YKrawiec K(2021)Convergence rate of the (1+1)-evolution strategy with success-based step-size adaptation on convex quadratic functionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3449639.3459289(1169-1177)Online publication date: 26-Jun-2021
https://dl.acm.org/doi/10.1145/3449639.3459289
He XZheng ZZhou Y(2021)MMES: Mixture Model-Based Evolution Strategy for Large-Scale OptimizationIEEE Transactions on Evolutionary Computation10.1109/TEVC.2020.303476925:2(320-333)Online publication date: Apr-2021
https://doi.org/10.1109/TEVC.2020.3034769
He XZhou YChen ZZhang JChen W(2021)Large-Scale Evolution Strategy Based on Search Direction AdaptationIEEE Transactions on Cybernetics10.1109/TCYB.2019.292856351:3(1651-1665)Online publication date: Mar-2021
https://doi.org/10.1109/TCYB.2019.2928563
Show More Cited By

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