IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v196y2023i3d10.1007_s10957-022-02141-9.html
   My bibliography  Save this article

On the Parallelization Upper Bound for Asynchronous Stochastic Gradients Descent in Non-convex Optimization

Author

Listed:
  • Lifu Wang

    (Beijing Jiaotong University
    Beijing Municipal Commission of Education Beijing Jiaotong University)

  • Bo Shen

    (Beijing Jiaotong University
    Beijing Municipal Commission of Education Beijing Jiaotong University)

Abstract

In deep learning, asynchronous parallel stochastic gradient descent (APSGD) is a broadly used algorithm to speed up the training process. In asynchronous system, the time delay of stale gradients in asynchronous algorithms is generally proportional to the total number of workers. When the number of workers is too large, the time delay will bring additional deviation from the accurate gradient due to delayed gradients and may cause a negative influence on the convergence speed of the algorithm. One may ask: How many workers can be used at most to achieve both the convergence and the speedup? In this paper, we consider the asynchronous training problem with the non-convex case. We theoretically study this problem to find an approximating second-order stationary point using asynchronous algorithms in non-convex optimization and investigate the behaviors of APSGD near-saddle points. This work gives the first theoretical guarantee to find an approximating second-order stationary point in asynchronous algorithms and a provable upper bound for the time delay. The techniques we provide can be generalized to analyze other types of asynchronous algorithms to understand the behaviors of asynchronous algorithms in distributed asynchronous parallel training.

Suggested Citation

  • Lifu Wang & Bo Shen, 2023. "On the Parallelization Upper Bound for Asynchronous Stochastic Gradients Descent in Non-convex Optimization," Journal of Optimization Theory and Applications, Springer, vol. 196(3), pages 900-935, March.
    • Handle: RePEc:spr:joptap:v:196:y:2023:i:3:d:10.1007_s10957-022-02141-9
    DOI: 10.1007/s10957-022-02141-9
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-022-02141-9
    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/s10957-022-02141-9?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. Mao, Xuerong, 1996. "Razumikhin-type theorems on exponential stability of stochastic functional differential equations," Stochastic Processes and their Applications, Elsevier, vol. 65(2), pages 233-250, December.
    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. Zhou, Jianping & Park, Ju H. & Ma, Qian, 2016. "Non-fragile observer-based H∞ control for stochastic time-delay systems," Applied Mathematics and Computation, Elsevier, vol. 291(C), pages 69-83.
    2. Peng, Dongxue & Li, Xiaodi & Rakkiyappan, R. & Ding, Yanhui, 2021. "Stabilization of stochastic delayed systems: Event-triggered impulsive control," Applied Mathematics and Computation, Elsevier, vol. 401(C).
    3. Qi Wang & Huabin Chen & Chenggui Yuan, 2022. "A Note on Exponential Stability for Numerical Solution of Neutral Stochastic Functional Differential Equations," Mathematics, MDPI, vol. 10(6), pages 1-11, March.
    4. Natalya O. Sedova & Olga V. Druzhinina, 2023. "Exponential Stability of Nonlinear Time-Varying Delay Differential Equations via Lyapunov–Razumikhin Technique," Mathematics, MDPI, vol. 11(4), pages 1-15, February.
    5. Udom, Akaninyene Udo, 2012. "Exponential stabilization of stochastic interval system with time dependent parameters," European Journal of Operational Research, Elsevier, vol. 222(3), pages 523-528.
    6. Zihan Zou & Yinfang Song & Chi Zhao, 2022. "Razumikhin Theorems on Polynomial Stability of Neutral Stochastic Pantograph Differential Equations with Markovian Switching," Mathematics, MDPI, vol. 10(17), pages 1-15, August.
    7. Mao, Wei & Hu, Liangjian & Mao, Xuerong, 2015. "The existence and asymptotic estimations of solutions to stochastic pantograph equations with diffusion and Lévy jumps," Applied Mathematics and Computation, Elsevier, vol. 268(C), pages 883-896.
    8. Cheng, Pei & Deng, Feiqi, 2010. "Global exponential stability of impulsive stochastic functional differential systems," Statistics & Probability Letters, Elsevier, vol. 80(23-24), pages 1854-1862, December.
    9. Peng, Shiguo & Jia, Baoguo, 2010. "Some criteria on pth moment stability of impulsive stochastic functional differential equations," Statistics & Probability Letters, Elsevier, vol. 80(13-14), pages 1085-1092, July.
    10. Mao, Wei & Zhu, Quanxin & Mao, Xuerong, 2015. "Existence, uniqueness and almost surely asymptotic estimations of the solutions to neutral stochastic functional differential equations driven by pure jumps," Applied Mathematics and Computation, Elsevier, vol. 254(C), pages 252-265.
    11. Kao, Yonggui & Zhu, Quanxin & Qi, Wenhai, 2015. "Exponential stability and instability of impulsive stochastic functional differential equations with Markovian switching," Applied Mathematics and Computation, Elsevier, vol. 271(C), pages 795-804.
    12. Li, Dingshi & Lin, Yusen, 2021. "Periodic measures of impulsive stochastic differential equations," Chaos, Solitons & Fractals, Elsevier, vol. 148(C).
    13. Lijun Pan & Jinde Cao & Yong Ren, 2020. "Impulsive Stability of Stochastic Functional Differential Systems Driven by G-Brownian Motion," Mathematics, MDPI, vol. 8(2), pages 1-16, February.
    14. Shu, Huisheng & Wei, Guoliang, 2005. "H∞ analysis of nonlinear stochastic time-delay systems," Chaos, Solitons & Fractals, Elsevier, vol. 26(2), pages 637-647.

    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:joptap:v:196:y:2023:i:3:d:10.1007_s10957-022-02141-9. 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.