IDEAS home Printed from https://ideas.repec.org/p/tse/wpaper/31104.html
   My bibliography  Save this paper

Stochastic Heavy Ball

Author

Listed:
  • Gadat, Sébastien
  • Panloup, Fabien
  • Saadane, Sofiane

Abstract

This paper deals with a natural stochastic optimization procedure derived from the so-called Heavy-ball method differential equation, which was introduced by Polyak in the 1960s with his seminal contribution [Pol64]. The Heavy-ball method is a second-order dynamics that was investigated to minimize convex functions f. The family of second-order methods recently received a large amount of attention, until the famous contribution of Nesterov [Nes83], leading to the explosion of large-scale optimization problems. This work provides an in-depth description of the stochastic heavy-ball method, which is an adaptation of the deterministic one when only unbiased evalutions of the gradient are available and used throughout the iterations of the algorithm. We first describe some almost sure convergence results in the case of general non-convex coercive functions f. We then examine the situation of convex and strongly convex potentials and derive some non-asymptotic results about the stochastic heavy-ball method. We end our study with limit theorems on several rescaled algorithms.

Suggested Citation

  • Gadat, Sébastien & Panloup, Fabien & Saadane, Sofiane, 2016. "Stochastic Heavy Ball," TSE Working Papers 16-712, Toulouse School of Economics (TSE).
    • Handle: RePEc:tse:wpaper:31104
    as

    Download full text from publisher

    File URL: https://www.tse-fr.eu/sites/default/files/TSE/documents/doc/wp/2016/wp_tse_712.pdf
    File Function: Full text
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. S'ebastien Gadat & Laurent Miclo & Fabien Panloup, 2013. "A stochastic model for speculative bubbles," Papers 1309.6287, arXiv.org.
    2. Lemaire, Vincent, 2007. "An adaptive scheme for the approximation of dissipative systems," Stochastic Processes and their Applications, Elsevier, vol. 117(10), pages 1491-1518, October.
    3. Mattingly, J. C. & Stuart, A. M. & Higham, D. J., 2002. "Ergodicity for SDEs and approximations: locally Lipschitz vector fields and degenerate noise," Stochastic Processes and their Applications, Elsevier, vol. 101(2), pages 185-232, October.
    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. Nicolas Loizou & Peter Richtárik, 2020. "Momentum and stochastic momentum for stochastic gradient, Newton, proximal point and subspace descent methods," Computational Optimization and Applications, Springer, vol. 77(3), pages 653-710, December.
    2. Gadat, Sébastien & Gavra, Ioana, 2021. "Asymptotic study of stochastic adaptive algorithm in non-convex landscape," TSE Working Papers 21-1175, Toulouse School of Economics (TSE).
    3. Costa, Manon & Gadat, Sébastien & Bercu, Bernard, 2020. "Stochastic approximation algorithms for superquantiles estimation," TSE Working Papers 20-1142, Toulouse School of Economics (TSE).

    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. Lemaire, Vincent, 2007. "An adaptive scheme for the approximation of dissipative systems," Stochastic Processes and their Applications, Elsevier, vol. 117(10), pages 1491-1518, October.
    2. Laruelle Sophie & Pagès Gilles, 2012. "Stochastic approximation with averaging innovation applied to Finance," Monte Carlo Methods and Applications, De Gruyter, vol. 18(1), pages 1-51, January.
    3. Bao, Jianhai & Wang, Jian, 2022. "Coupling approach for exponential ergodicity of stochastic Hamiltonian systems with Lévy noises," Stochastic Processes and their Applications, Elsevier, vol. 146(C), pages 114-142.
    4. Shu, Huisheng & Jiang, Ziwei & Zhang, Xuekang, 2023. "Parameter estimation for integrated Ornstein–Uhlenbeck processes with small Lévy noises," Statistics & Probability Letters, Elsevier, vol. 199(C).
    5. Panloup, Fabien, 2008. "Computation of the invariant measure for a Lévy driven SDE: Rate of convergence," Stochastic Processes and their Applications, Elsevier, vol. 118(8), pages 1351-1384, August.
    6. Pagès Gilles & Rey Clément, 2019. "Recursive computation of the invariant distributions of Feller processes: Revisited examples and new applications," Monte Carlo Methods and Applications, De Gruyter, vol. 25(1), pages 1-36, March.
    7. Cai, Yongli & Kang, Yun & Wang, Weiming, 2017. "A stochastic SIRS epidemic model with nonlinear incidence rate," Applied Mathematics and Computation, Elsevier, vol. 305(C), pages 221-240.
    8. Cohen, Serge & Panloup, Fabien, 2011. "Approximation of stationary solutions of Gaussian driven stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 121(12), pages 2776-2801.
    9. Chen, Peng & Deng, Chang-Song & Schilling, René L. & Xu, Lihu, 2023. "Approximation of the invariant measure of stable SDEs by an Euler–Maruyama scheme," Stochastic Processes and their Applications, Elsevier, vol. 163(C), pages 136-167.
    10. Susanne Ditlevsen & Adeline Samson, 2019. "Hypoelliptic diffusions: filtering and inference from complete and partial observations," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 81(2), pages 361-384, April.
    11. Song, Renming & Xie, Longjie, 2020. "Well-posedness and long time behavior of singular Langevin stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 130(4), pages 1879-1896.
    12. Birrell, Jeremiah & Herzog, David P. & Wehr, Jan, 2012. "The transition from ergodic to explosive behavior in a family of stochastic differential equations," Stochastic Processes and their Applications, Elsevier, vol. 122(4), pages 1519-1539.
    13. Pagès, Gilles & Panloup, Fabien, 2014. "A mixed-step algorithm for the approximation of the stationary regime of a diffusion," Stochastic Processes and their Applications, Elsevier, vol. 124(1), pages 522-565.
    14. Quentin Clairon & Adeline Samson, 2020. "Optimal control for estimation in partially observed elliptic and hypoelliptic linear stochastic differential equations," Statistical Inference for Stochastic Processes, Springer, vol. 23(1), pages 105-127, April.
    15. Gilles Pagès & Clément Rey, 2023. "Discretization of the Ergodic Functional Central Limit Theorem," Journal of Theoretical Probability, Springer, vol. 36(1), pages 1-44, March.
    16. Qiu Lin & Ruisheng Qi, 2023. "Optimal Weak Order and Approximation of the Invariant Measure with a Fully-Discrete Euler Scheme for Semilinear Stochastic Parabolic Equations with Additive Noise," Mathematics, MDPI, vol. 12(1), pages 1-29, December.
    17. Ganguly, Arnab & Sundar, P., 2021. "Inhomogeneous functionals and approximations of invariant distributions of ergodic diffusions: Central limit theorem and moderate deviation asymptotics," Stochastic Processes and their Applications, Elsevier, vol. 133(C), pages 74-110.
    18. Gao, Shuaibin & Li, Xiaotong & Liu, Zhuoqi, 2023. "Stationary distribution of the Milstein scheme for stochastic differential delay equations with first-order convergence," Applied Mathematics and Computation, Elsevier, vol. 458(C).
    19. ur Rahman, Ghaus & Badshah, Qaisar & Agarwal, Ravi P. & Islam, Saeed, 2021. "Ergodicity & dynamical aspects of a stochastic childhood disease model," Mathematics and Computers in Simulation (MATCOM), Elsevier, vol. 182(C), pages 738-764.
    20. Mattingly, Jonathan C. & McKinley, Scott A. & Pillai, Natesh S., 2012. "Geometric ergodicity of a bead–spring pair with stochastic Stokes forcing," Stochastic Processes and their Applications, Elsevier, vol. 122(12), pages 3953-3979.

    More about this item

    Keywords

    Stochastic optimization algorithms; Second-order methods; Random dynamical systems;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:tse:wpaper:31104. 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: the person in charge (email available below). General contact details of provider: https://edirc.repec.org/data/tsetofr.html .

    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.