Comparison-Based Natural Gradient Optimization in High Dimension

Youhei Akimoto 1 Anne Auger 1 Nikolaus Hansen 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 : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download
Contributor : Nikolaus Hansen <>
Submitted on : Wednesday, December 31, 2014 - 7:18:51 PM
Last modification on : Thursday, April 5, 2018 - 12:30:12 PM
Long-term archiving on : Wednesday, April 1, 2015 - 10:35:30 AM


Files produced by the author(s)


  • HAL Id : hal-00997835, version 1



Youhei Akimoto, Anne Auger, Nikolaus Hansen. Comparison-Based Natural Gradient Optimization in High Dimension. Genetic and Evolutionary Computation Conference GECCO'14, ACM, Jul 2014, Vancouver, Canada. ⟨hal-00997835⟩



Record views


Files downloads