GECCO 2017: Deriving and Improving CMA-ES with Information-Geometric Trustregions

CMA-ES is one of the most popular stochastic search algorithms. It performs favourably in many tasks without the need of extensive parameter tuning. The algorithm has many beneficial properties, including automatic step-size adaptation, efficient covariance updates that incorporates the current samples as well as the evolution path and its invariance properties. Its update rules are composed of well established heuristics where the theoretical foundations of some of these rules are also well understood. In this paper we will fully derive all CMA-ES update rules within the framework of expectation-maximisation-based stochastic search algorithms using information-geometric trust regions. We show that the use of the trust region results in similar updates to CMA-ES for the mean and the covariance matrix while it allows for the derivation of an improved update rule for the step-size. Our new algorithm, Trust-Region Covariance Matrix Adaptation Evolution Strategy (TR-CMA-ES) is fully derived from first order optimization principles and performs favourably in compare to standard CMA-ES algorithm.

  • A. Abdolmaleki, B. Price, N. Lau, L. P. Reis, and G. Neumann, “Deriving and improving CMA-ES with Information geometric trust regions,” in The Genetic and Evolutionary Computation Conference (GECCO 2017), 2017.
    [BibTeX] [Abstract] [Download PDF]

    CMA-ES is one of the most popular stochastic search algorithms. It performs favourably in many tasks without the need of extensive parameter tuning. The algorithm has many beneficial properties, including automatic step-size adaptation, efficient covariance updates that incorporates the current samples as well as the evolution path and its invariance properties. Its update rules are composed of well established heuristics where the theoretical foundations of some of these rules are also well understood. In this paper we will fully derive all CMA-ES update rules within the framework of expectation-maximisation-based stochastic search algorithms using information-geometric trust regions. We show that the use of the trust region results in similar updates to CMA-ES for the mean and the covariance matrix while it allows for the derivation of an improved update rule for the step-size. Our new algorithm, Trust-Region Covariance Matrix Adaptation Evolution Strategy (TR-CMA-ES) is fully derived from first order optimization principles and performs favourably in compare to standard CMA-ES algorithm.

    @inproceedings{lirolem27056,
    year = {2017},
    booktitle = {The Genetic and Evolutionary Computation Conference (GECCO 2017)},
    title = {Deriving and improving CMA-ES with Information geometric trust regions},
    month = {July},
    author = {Abbas Abdolmaleki and Bob Price and Nuno Lau and Luis Paulo Reis and Gerhard Neumann},
    url = {http://eprints.lincoln.ac.uk/27056/},
    abstract = {CMA-ES is one of the most popular stochastic search algorithms.
    It performs favourably in many tasks without the need of extensive
    parameter tuning. The algorithm has many beneficial properties,
    including automatic step-size adaptation, efficient covariance updates
    that incorporates the current samples as well as the evolution
    path and its invariance properties. Its update rules are composed
    of well established heuristics where the theoretical foundations of
    some of these rules are also well understood. In this paper we
    will fully derive all CMA-ES update rules within the framework of
    expectation-maximisation-based stochastic search algorithms using
    information-geometric trust regions. We show that the use of the trust
    region results in similar updates to CMA-ES for the mean and the
    covariance matrix while it allows for the derivation of an improved
    update rule for the step-size. Our new algorithm, Trust-Region Covariance
    Matrix Adaptation Evolution Strategy (TR-CMA-ES) is
    fully derived from first order optimization principles and performs
    favourably in compare to standard CMA-ES algorithm.},
    keywords = {ARRAY(0x55fe0a68ca88)}
    }