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

Perturbed Iterate SGD for Lipschitz Continuous Loss Functions

Author

Listed:
  • Michael R. Metel

    (Huawei Noah’s Ark Lab)

  • Akiko Takeda

    (The University of Tokyo
    RIKEN Center for Advanced Intelligence Project)

Abstract

This paper presents an extension of stochastic gradient descent for the minimization of Lipschitz continuous loss functions. Our motivation is for use in non-smooth non-convex stochastic optimization problems, which are frequently encountered in applications such as machine learning. Using the Clarke $$\epsilon $$ ϵ -subdifferential, we prove the non-asymptotic convergence to an approximate stationary point in expectation for the proposed method. From this result, a method with non-asymptotic convergence with high probability, as well as a method with asymptotic convergence to a Clarke stationary point almost surely are developed. Our results hold under the assumption that the stochastic loss function is a Carathéodory function which is almost everywhere Lipschitz continuous in the decision variables. To the best of our knowledge, this is the first non-asymptotic convergence analysis under these minimal assumptions.

Suggested Citation

  • Michael R. Metel & Akiko Takeda, 2022. "Perturbed Iterate SGD for Lipschitz Continuous Loss Functions," Journal of Optimization Theory and Applications, Springer, vol. 195(2), pages 504-547, November.
    • Handle: RePEc:spr:joptap:v:195:y:2022:i:2:d:10.1007_s10957-022-02093-0
    DOI: 10.1007/s10957-022-02093-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-022-02093-0
    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-02093-0?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. J. V. Burke & A. S. Lewis & M. L. Overton, 2002. "Approximating Subdifferentials by Random Sampling of Gradients," Mathematics of Operations Research, INFORMS, vol. 27(3), pages 567-584, August.
    2. Yurii NESTEROV & Vladimir SPOKOINY, 2017. "Random gradient-free minimization of convex functions," LIDAM Reprints CORE 2851, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. V. Kungurtsev & F. Rinaldi, 2021. "A zeroth order method for stochastic weakly convex optimization," Computational Optimization and Applications, Springer, vol. 80(3), pages 731-753, December.
    2. Hoang Tran & Qiang Du & Guannan Zhang, 2025. "Convergence analysis for a nonlocal gradient descent method via directional Gaussian smoothing," Computational Optimization and Applications, Springer, vol. 90(2), pages 481-513, March.
    3. Dmitriy Drusvyatskiy & Alexander D. Ioffe & Adrian S. Lewis, 2015. "Clarke Subgradients for Directionally Lipschitzian Stratifiable Functions," Mathematics of Operations Research, INFORMS, vol. 40(2), pages 328-349, February.
    4. W. L. Hare & A. S. Lewis, 2005. "Estimating Tangent and Normal Cones Without Calculus," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 785-799, November.
    5. Jean-Jacques Forneron, 2023. "Noisy, Non-Smooth, Non-Convex Estimation of Moment Condition Models," Papers 2301.07196, arXiv.org, revised Feb 2023.
    6. Alireza Aghasi & Saeed Ghadimi, 2025. "Fully Zeroth-Order Bilevel Programming via Gaussian Smoothing," Journal of Optimization Theory and Applications, Springer, vol. 205(2), pages 1-39, May.
    7. Giovanni Colombo & Antonio Marigonda & Peter R. Wolenski, 2013. "The Clarke Generalized Gradient for Functions Whose Epigraph Has Positive Reach," Mathematics of Operations Research, INFORMS, vol. 38(3), pages 451-468, August.
    8. Aleksandr Lobanov & Andrew Veprikov & Georgiy Konin & Aleksandr Beznosikov & Alexander Gasnikov & Dmitry Kovalev, 2023. "Non-smooth setting of stochastic decentralized convex optimization problem over time-varying Graphs," Computational Management Science, Springer, vol. 20(1), pages 1-55, December.
    9. Stefan Wager & Kuang Xu, 2021. "Experimenting in Equilibrium," Management Science, INFORMS, vol. 67(11), pages 6694-6715, November.
    10. Zhongruo Wang & Krishnakumar Balasubramanian & Shiqian Ma & Meisam Razaviyayn, 2023. "Zeroth-order algorithms for nonconvex–strongly-concave minimax problems with improved complexities," Journal of Global Optimization, Springer, vol. 87(2), pages 709-740, November.
    11. Milagros Loreto & Hugo Aponte & Debora Cores & Marcos Raydan, 2017. "Nonsmooth spectral gradient methods for unconstrained optimization," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 529-553, December.
    12. Elias S. Helou & Sandra A. Santos & Lucas E. A. Simões, 2018. "A fast gradient and function sampling method for finite-max functions," Computational Optimization and Applications, Springer, vol. 71(3), pages 673-717, December.
    13. Rajeeva Laxman Karandikar & Mathukumalli Vidyasagar, 2024. "Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications," Journal of Optimization Theory and Applications, Springer, vol. 203(3), pages 2412-2450, December.
    14. Fabrice Poirion & Quentin Mercier & Jean-Antoine Désidéri, 2017. "Descent algorithm for nonsmooth stochastic multiobjective optimization," Computational Optimization and Applications, Springer, vol. 68(2), pages 317-331, November.
    15. Chad Davis & Warren Hare, 2013. "Exploiting Known Structures to Approximate Normal Cones," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 665-681, November.
    16. Geovani Nunes Grapiglia, 2023. "Quadratic regularization methods with finite-difference gradient approximations," Computational Optimization and Applications, Springer, vol. 85(3), pages 683-703, July.
    17. Flavia Chorobura & Ion Necoara, 2024. "Coordinate descent methods beyond smoothness and separability," Computational Optimization and Applications, Springer, vol. 88(1), pages 107-149, May.
    18. Tianyu Wang & Yasong Feng, 2024. "Convergence Rates of Zeroth Order Gradient Descent for Łojasiewicz Functions," INFORMS Journal on Computing, INFORMS, vol. 36(6), pages 1611-1633, December.
    19. Youssef Diouane & Vyacheslav Kungurtsev & Francesco Rinaldi & Damiano Zeffiro, 2024. "Inexact direct-search methods for bilevel optimization problems," Computational Optimization and Applications, Springer, vol. 88(2), pages 469-490, June.
    20. Ghadimi, Saeed & Powell, Warren B., 2024. "Stochastic search for a parametric cost function approximation: Energy storage with rolling forecasts," European Journal of Operational Research, Elsevier, vol. 312(2), pages 641-652.

    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:195:y:2022:i:2:d:10.1007_s10957-022-02093-0. 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.