IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v86y2023i1d10.1007_s10898-022-01249-6.html
   My bibliography  Save this article

Global linear convergence of evolution strategies with recombination on scaling-invariant functions

Author

Listed:
  • Cheikh Toure

    (IP Paris)

  • Anne Auger

    (IP Paris)

  • Nikolaus Hansen

    (IP Paris)

Abstract

Evolution Strategies (ESs) are stochastic derivative-free optimization algorithms whose most prominent representative, the CMA-ES algorithm, is widely used to solve difficult numerical optimization problems. We provide the first rigorous investigation of the linear convergence of step-size adaptive ESs involving a population and recombination, two ingredients crucially important in practice to be robust to local irregularities or multimodality. We investigate the convergence of step-size adaptive ESs with weighted recombination on composites of strictly increasing functions with continuously differentiable scaling-invariant functions with a global optimum. This function class includes functions with non-convex sublevel sets and discontinuous functions. We prove the existence of a constant r such that the logarithm of the distance to the optimum divided by the number of iterations converges to r. The constant is given as an expectation with respect to the stationary distribution of a Markov chain—its sign allows to infer linear convergence or divergence of the ES and is found numerically. Our main condition for convergence is the increase of the expected log step-size on linear functions. In contrast to previous results, our condition is equivalent to the almost sure geometric divergence of the step-size on linear functions.

Suggested Citation

  • Cheikh Toure & Anne Auger & Nikolaus Hansen, 2023. "Global linear convergence of evolution strategies with recombination on scaling-invariant functions," Journal of Global Optimization, Springer, vol. 86(1), pages 163-203, May.
    • Handle: RePEc:spr:jglopt:v:86:y:2023:i:1:d:10.1007_s10898-022-01249-6
    DOI: 10.1007/s10898-022-01249-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-022-01249-6
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-022-01249-6?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Akimoto, Youhei & Auger, Anne & Hansen, Nikolaus, 2022. "An ODE method to prove the geometric convergence of adaptive stochastic algorithms," Stochastic Processes and their Applications, Elsevier, vol. 145(C), pages 269-307.
    2. Vitaliy Feoktistov, 2006. "Differential Evolution," Springer Optimization and Its Applications, Springer, number 978-0-387-36896-2, June.
    3. Jensen, Søren Tolver & Rahbek, Anders, 2007. "On The Law Of Large Numbers For (Geometrically) Ergodic Markov Chains," Econometric Theory, Cambridge University Press, vol. 23(4), pages 761-766, August.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Cavaliere, Giuseppe & Rahbek, Anders & Taylor, A.M. Robert, 2010. "Cointegration Rank Testing Under Conditional Heteroskedasticity," Econometric Theory, Cambridge University Press, vol. 26(6), pages 1719-1760, December.
    2. Nicolas Heslot & Vitaliy Feoktistov, 2020. "Optimization of Selective Phenotyping and Population Design for Genomic Prediction," Journal of Agricultural, Biological and Environmental Statistics, Springer;The International Biometric Society;American Statistical Association, vol. 25(4), pages 579-600, December.
    3. Giuseppe Cavaliere & Thomas Mikosch & Anders Rahbek & Frederik Vilandt, 2023. "Asymptotics for the Generalized Autoregressive Conditional Duration Model," Papers 2307.01779, arXiv.org.
    4. Fokianos, Konstantinos & Rahbek, Anders & Tjøstheim, Dag, 2009. "Poisson Autoregression," Journal of the American Statistical Association, American Statistical Association, vol. 104(488), pages 1430-1439.
    5. Vurukonda Sathish & Siuli Mukhopadhyay & Rashmi Tiwari, 2022. "Autoregressive and moving average models for zero‐inflated count time series," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 76(2), pages 190-218, May.
    6. Christian M. Dahl & Emma M. Iglesias, 2021. "Asymptotic normality of the MLE in the level-effect ARCH model," Statistical Papers, Springer, vol. 62(1), pages 117-135, February.
    7. Nielsen, Heino Bohn & Rahbek, Anders, 2014. "Unit root vector autoregression with volatility induced stationarity," Journal of Empirical Finance, Elsevier, vol. 29(C), pages 144-167.
    8. Kristensen, Dennis & Rahbek, Anders, 2010. "Likelihood-based inference for cointegration with nonlinear error-correction," Journal of Econometrics, Elsevier, vol. 158(1), pages 78-94, September.
    9. Peter Boswijk, H. & van der Weide, Roy, 2011. "Method of moments estimation of GO-GARCH models," Journal of Econometrics, Elsevier, vol. 163(1), pages 118-126, July.
    10. Theis Lange, 2009. "First and second order non-linear cointegration models," CREATES Research Papers 2009-04, Department of Economics and Business Economics, Aarhus University.
    11. Frédérique Bec & Anders Rahbek & Neil Shephard, 2008. "The ACR Model: A Multivariate Dynamic Mixture Autoregression," Oxford Bulletin of Economics and Statistics, Department of Economics, University of Oxford, vol. 70(5), pages 583-618, October.
    12. Abdullah B Nasser & Kamal Z Zamli & AbdulRahman A Alsewari & Bestoun S Ahmed, 2018. "Hybrid flower pollination algorithm strategies for t-way test suite generation," PLOS ONE, Public Library of Science, vol. 13(5), pages 1-24, May.
    13. Konstantinos Fokianos & Dag Tjøstheim, 2012. "Nonlinear Poisson autoregression," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 64(6), pages 1205-1225, December.
    14. Hanan Elsaied & Roland Fried, 2021. "On robust estimation of negative binomial INARCH models," METRON, Springer;Sapienza Università di Roma, vol. 79(2), pages 137-158, August.
    15. Line Elvstrøm Ekner & Emil Nejstgaard, 2013. "Parameter Identification in the Logistic STAR Model," Discussion Papers 13-07, University of Copenhagen. Department of Economics.
    16. Kristensen Dennis & Rahbek Anders, 2009. "Asymptotics of the QMLE for Non-Linear ARCH Models," Journal of Time Series Econometrics, De Gruyter, vol. 1(1), pages 1-38, April.
    17. Nahar F. Alshammari & Mohamed Mahmoud Samy & Shimaa Barakat, 2023. "Comprehensive Analysis of Multi-Objective Optimization Algorithms for Sustainable Hybrid Electric Vehicle Charging Systems," Mathematics, MDPI, vol. 11(7), pages 1-31, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jglopt:v:86:y:2023:i:1:d:10.1007_s10898-022-01249-6. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.