[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v49y2024i4p2492-2526.html
   My bibliography  Save this article

Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition

Author

Listed:
  • You-Lin Chen

    (Department of Statistics, The University of Chicago, Chicago, Illinois 60637)

  • Sen Na

    (International Computer Science Institute, Berkeley, California 94704; Department of Statistics, University of California, Berkeley, California 94720)

  • Mladen Kolar

    (Booth School of Business, The University of Chicago, Chicago, Illinois 60637)

Abstract
We study the convergence of accelerated stochastic gradient descent (SGD) for strongly convex objectives under the growth condition , which states that the variance of stochastic gradient is bounded by a multiplicative part that grows with the full gradient and a constant additive part. Through the lens of the growth condition, we investigate four widely used accelerated methods: Nesterov’s accelerated method (NAM), robust momentum method (RMM), accelerated dual averaging method (DAM+), and implicit DAM+ (iDAM+). Although these methods are known to improve the convergence rate of SGD under the condition that the stochastic gradient has bounded variance, it is not well understood how their convergence rates are affected by the multiplicative noise. In this paper, we show that these methods all converge to a neighborhood of the optimum with accelerated convergence rates (compared with SGD), even under the growth condition. In particular, NAM, RMM, and iDAM+ enjoy acceleration only with a mild multiplicative noise, whereas DAM+ enjoys acceleration, even with a large multiplicative noise. Furthermore, we propose a generic tail-averaged scheme that allows the accelerated rates of DAM+ and iDAM+ to nearly attain the theoretical lower bound (up to a logarithmic factor in the variance term). We conduct numerical experiments to support our theoretical conclusions.

Suggested Citation

  • You-Lin Chen & Sen Na & Mladen Kolar, 2024. "Convergence Analysis of Accelerated Stochastic Gradient Descent Under the Growth Condition," Mathematics of Operations Research, INFORMS, vol. 49(4), pages 2492-2526, November.
    • Handle: RePEc:inm:ormoor:v:49:y:2024:i:4:p:2492-2526
    DOI: 10.1287/moor.2021.0293
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/moor.2021.0293
    Download Restriction: no
    File URL: https://libkey.io/10.1287/moor.2021.0293?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
    ---><---

    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:inm:ormoor:v:49:y:2024:i:4:p:2492-2526. 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.

    We have no bibliographic references for this item. You can help adding them by using 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.