IDEAS home Printed from https://ideas.repec.org/a/eee/spapps/v145y2022icp269-307.html
   My bibliography  Save this article

An ODE method to prove the geometric convergence of adaptive stochastic algorithms

Author

Listed:
  • Akimoto, Youhei
  • Auger, Anne
  • Hansen, Nikolaus

Abstract

We consider stochastic algorithms derived from methods for solving deterministic optimization problems, especially comparison-based algorithms derived from stochastic approximation algorithms with a constant step-size. We develop a methodology for proving geometric convergence of the parameter sequence {θn}n⩾0 of such algorithms. We employ the ordinary differential equation (ODE) method, which relates a stochastic algorithm to its mean ODE, along with a Lyapunov-like function Ψ such that the geometric convergence of Ψ(θn) implies – in the case of an optimization algorithm – the geometric convergence of the expected distance between the optimum and the search point generated by the algorithm. We provide two sufficient conditions for Ψ(θn) to decrease at a geometric rate: Ψ should decrease “exponentially” along the solution to the mean ODE, and the deviation between the stochastic algorithm and the ODE solution (measured by Ψ) should be bounded by Ψ(θn) times a constant. We also provide practical conditions under which the two sufficient conditions may be verified easily without knowing the solution of the mean ODE. Our results are any-time bounds on Ψ(θn), so we can deduce not only the asymptotic upper bound on the convergence rate, but also the first hitting time of the algorithm. The main results are applied to a comparison-based stochastic algorithm with a constant step-size for optimization on continuous domains.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:spapps:v:145:y:2022:i:c:p:269-307
    DOI: 10.1016/j.spa.2021.12.005
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304414921002076
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.spa.2021.12.005?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. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2006. "Stochastic Approximations and Differential Inclusions, Part II: Applications," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 673-695, November.
    2. G. Giorgi & S. Komlósi, 1992. "Dini derivatives in optimization — Part I," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 15(1), pages 3-30, March.
    3. Michel Benaim & Josef Hofbauer & Sylvain Sorin, 2005. "Stochastic Approximations and Differential Inclusions II: Applications," Levine's Bibliography 784828000000000098, UCLA Department of Economics.
    4. Enlu Zhou & Shalabh Bhatnagar, 2018. "Gradient-Based Adaptive Stochastic Search for Simulation Optimization Over Continuous Space," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 154-167, February.
    5. G. Giorgi & S. Komlósi, 1992. "Dini derivatives in optimization — Part II," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 15(2), pages 3-24, September.
    6. Pieter-Tjerk de Boer & Dirk Kroese & Shie Mannor & Reuven Rubinstein, 2005. "A Tutorial on the Cross-Entropy Method," Annals of Operations Research, Springer, vol. 134(1), pages 19-67, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

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

    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. Bobtcheff, Catherine & Mariotti, Thomas, 2012. "Potential competition in preemption games," Games and Economic Behavior, Elsevier, vol. 75(1), pages 53-66.
    2. Ceparano, Maria Carmela & Quartieri, Federico, 2017. "Nash equilibrium uniqueness in nice games with isotone best replies," Journal of Mathematical Economics, Elsevier, vol. 70(C), pages 154-165.
    3. Michel Benaïm & Mathieu Faure, 2013. "Consistency of Vanishingly Smooth Fictitious Play," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 437-450, August.
    4. Michel Benaim & Olivier Raimond, 2007. "Simulated Annealing, Vertex-Reinforced Random Walks and Learning in Games," Levine's Bibliography 122247000000001702, UCLA Department of Economics.
    5. Josef Hofbauer & Sylvain Sorin & Yannick Viossat, 2009. "Time Average Replicator and Best-Reply Dynamics," Mathematics of Operations Research, INFORMS, vol. 34(2), pages 263-269, May.
    6. Viossat, Yannick & Zapechelnyuk, Andriy, 2013. "No-regret dynamics and fictitious play," Journal of Economic Theory, Elsevier, vol. 148(2), pages 825-842.
    7. Michel Benaïm & Josef Hofbauer & Sylvain Sorin, 2012. "Perturbations of Set-Valued Dynamical Systems, with Applications to Game Theory," Dynamic Games and Applications, Springer, vol. 2(2), pages 195-205, June.
    8. Mathieu Faure & Gregory Roth, 2010. "Stochastic Approximations of Set-Valued Dynamical Systems: Convergence with Positive Probability to an Attractor," Mathematics of Operations Research, INFORMS, vol. 35(3), pages 624-640, August.
    9. Saeed Hadikhanloo & Rida Laraki & Panayotis Mertikopoulos & Sylvain Sorin, 2022. "Learning in nonatomic games, part Ⅰ: Finite action spaces and population games," Post-Print hal-03767995, HAL.
    10. Andriy Zapechelnyuk, 2009. "Limit Behavior of No-regret Dynamics," Discussion Papers 21, Kyiv School of Economics.
    11. Sylvain Sorin, 2023. "Continuous Time Learning Algorithms in Optimization and Game Theory," Dynamic Games and Applications, Springer, vol. 13(1), pages 3-24, March.
    12. Dileep Kalathil & Vivek S. Borkar & Rahul Jain, 2017. "Approachability in Stackelberg Stochastic Games with Vector Costs," Dynamic Games and Applications, Springer, vol. 7(3), pages 422-442, September.
    13. Benaïm, Michel & Hofbauer, Josef & Hopkins, Ed, 2009. "Learning in games with unstable equilibria," Journal of Economic Theory, Elsevier, vol. 144(4), pages 1694-1709, July.
    14. Xi Chen & Enlu Zhou, 2015. "Population model-based optimization," Journal of Global Optimization, Springer, vol. 63(1), pages 125-148, September.
    15. Lvyang Qiu & Shuyu Li & Yunsick Sung, 2021. "3D-DCDAE: Unsupervised Music Latent Representations Learning Method Based on a Deep 3D Convolutional Denoising Autoencoder for Music Genre Classification," Mathematics, MDPI, vol. 9(18), pages 1-17, September.
    16. Anastasia Spiliopoulou & Ioannis Papamichail & Markos Papageorgiou & Yannis Tyrinopoulos & John Chrysoulakis, 2017. "Macroscopic traffic flow model calibration using different optimization algorithms," Operational Research, Springer, vol. 17(1), pages 145-164, April.
    17. Deng, Xiangtian & Zhang, Yi & Jiang, Yi & Zhang, Yi & Qi, He, 2024. "A novel operation method for renewable building by combining distributed DC energy system and deep reinforcement learning," Applied Energy, Elsevier, vol. 353(PB).
    18. Zhang, Yali & Shang, Pengjian, 2019. "Multivariate multiscale distribution entropy of financial time series," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 72-80.
    19. Bolte, Jérôme & Le, Tam & Pauwels, Edouard & Silveti-Falls, Antonio, 2022. "Nonsmooth Implicit Differentiation for Machine Learning and Optimization," TSE Working Papers 22-1314, Toulouse School of Economics (TSE).
    20. A. Gouda & T. Szántai, 2008. "Rare event probabilities in stochastic networks," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 16(4), pages 441-461, December.

    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:eee:spapps:v:145:y:2022:i:c:p:269-307. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/505572/description#description .

    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.