IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v188y2021i3d10.1007_s10957-020-01799-3.html
   My bibliography  Save this article

A Unified Convergence Analysis of Stochastic Bregman Proximal Gradient and Extragradient Methods

Author

Listed:
  • Xiantao Xiao

    (Dalian University of Technology)

Abstract

We consider a mini-batch stochastic Bregman proximal gradient method and a mini-batch stochastic Bregman proximal extragradient method for stochastic convex composite optimization problems. A simplified and unified convergence analysis framework is proposed to obtain almost sure convergence properties and expected convergence rates of the mini-batch stochastic Bregman proximal gradient method and its variants. This framework can also be used to analyze the convergence of the mini-batch stochastic Bregman proximal extragradient method, which has seldom been discussed in the literature. We point out that the standard uniformly bounded variance assumption and the usual Lipschitz gradient continuity assumption are not required in the analysis.

Suggested Citation

  • Xiantao Xiao, 2021. "A Unified Convergence Analysis of Stochastic Bregman Proximal Gradient and Extragradient Methods," Journal of Optimization Theory and Applications, Springer, vol. 188(3), pages 605-627, March.
    • Handle: RePEc:spr:joptap:v:188:y:2021:i:3:d:10.1007_s10957-020-01799-3
    DOI: 10.1007/s10957-020-01799-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10957-020-01799-3
    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-020-01799-3?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. Michael C. Fu, 2002. "Feature Article: Optimization for simulation: Theory vs. Practice," INFORMS Journal on Computing, INFORMS, vol. 14(3), pages 192-215, August.
    2. Aswin Kannan & Uday V. Shanbhag, 2019. "Optimal stochastic extragradient schemes for pseudomonotone stochastic variational inequality problems and their variants," Computational Optimization and Applications, Springer, vol. 74(3), pages 779-820, December.
    3. Trong Phong Nguyen & Edouard Pauwels & Emile Richard & Bruce W. Suter, 2018. "Extragradient Method in Optimization: Convergence and Complexity," Journal of Optimization Theory and Applications, Springer, vol. 176(1), pages 137-162, January.
    4. Heinz H. Bauschke & Jérôme Bolte & Marc Teboulle, 2017. "A Descent Lemma Beyond Lipschitz Gradient Continuity: First-Order Methods Revisited and Applications," Mathematics of Operations Research, INFORMS, vol. 42(2), pages 330-348, May.
    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. Gui-Hua Lin & Zhen-Ping Yang & Hai-An Yin & Jin Zhang, 2023. "A dual-based stochastic inexact algorithm for a class of stochastic nonsmooth convex composite problems," Computational Optimization and Applications, Springer, vol. 86(2), pages 669-710, November.

    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. Noordhoek, Marije & Dullaert, Wout & Lai, David S.W. & de Leeuw, Sander, 2018. "A simulation–optimization approach for a service-constrained multi-echelon distribution network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 114(C), pages 292-311.
    2. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, December.
    3. Roberto Aringhieri & Giuliana Carello & Daniela Morale, 2016. "Supporting decision making to improve the performance of an Italian Emergency Medical Service," Annals of Operations Research, Springer, vol. 236(1), pages 131-148, January.
    4. Jianxin Fang & Brenda Cheang & Andrew Lim, 2023. "Problems and Solution Methods of Machine Scheduling in Semiconductor Manufacturing Operations: A Survey," Sustainability, MDPI, vol. 15(17), pages 1-44, August.
    5. Warren B. Powell, 2009. "What you should know about approximate dynamic programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 56(3), pages 239-249, April.
    6. HyungSeon Oh, 2021. "Distributed optimal power flow," PLOS ONE, Public Library of Science, vol. 16(6), pages 1-27, June.
    7. Jack P. C. Kleijnen & Susan M. Sanchez & Thomas W. Lucas & Thomas M. Cioppa, 2005. "State-of-the-Art Review: A User’s Guide to the Brave New World of Designing Simulation Experiments," INFORMS Journal on Computing, INFORMS, vol. 17(3), pages 263-289, August.
    8. Zehui Jia & Jieru Huang & Xingju Cai, 2021. "Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems," Journal of Global Optimization, Springer, vol. 80(4), pages 841-864, August.
    9. Xiao-Juan Zhang & Xue-Wu Du & Zhen-Ping Yang & Gui-Hua Lin, 2019. "An Infeasible Stochastic Approximation and Projection Algorithm for Stochastic Variational Inequalities," Journal of Optimization Theory and Applications, Springer, vol. 183(3), pages 1053-1076, December.
    10. Fan Wu & Wei Bian, 2023. "Smoothing Accelerated Proximal Gradient Method with Fast Convergence Rate for Nonsmooth Convex Optimization Beyond Differentiability," Journal of Optimization Theory and Applications, Springer, vol. 197(2), pages 539-572, May.
    11. Sigrún Andradóttir & Andrei A. Prudius, 2009. "Balanced Explorative and Exploitative Search with Estimation for Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 21(2), pages 193-208, May.
    12. Stefan Vonolfen & Michael Affenzeller, 2016. "Distribution of waiting time for dynamic pickup and delivery problems," Annals of Operations Research, Springer, vol. 236(2), pages 359-382, January.
    13. Annamaria Barbagallo & Serena Guarino Lo Bianco, 2023. "A random time-dependent noncooperative equilibrium problem," Computational Optimization and Applications, Springer, vol. 84(1), pages 27-52, January.
    14. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "A Block Inertial Bregman Proximal Algorithm for Nonsmooth Nonconvex Problems with Application to Symmetric Nonnegative Matrix Tri-Factorization," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 234-258, July.
    15. L. Jeff Hong & Barry L. Nelson, 2006. "Discrete Optimization via Simulation Using COMPASS," Operations Research, INFORMS, vol. 54(1), pages 115-129, February.
    16. Emanuel Laude & Peter Ochs & Daniel Cremers, 2020. "Bregman Proximal Mappings and Bregman–Moreau Envelopes Under Relative Prox-Regularity," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 724-761, March.
    17. Kleijnen, J.P.C. & Sanchez, S.M. & Lucas, T.W. & Cioppa, T.M., 2003. "A User's Guide to the Brave New World of Designing Simulation Experiments," Discussion Paper 2003-1, Tilburg University, Center for Economic Research.
    18. Fu, Quanlu & Wu, Jiyan & Wu, Xuemian & Sun, Jian & Tian, Ye, 2024. "Managing network congestion with link-based incentives: A surrogate-based optimization approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 182(C).
    19. Yin Liu & Sam Davanloo Tajbakhsh, 2023. "Stochastic Composition Optimization of Functions Without Lipschitz Continuous Gradient," Journal of Optimization Theory and Applications, Springer, vol. 198(1), pages 239-289, July.
    20. Michael C. Fu, 2008. "What you should know about simulation and derivatives," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(8), pages 723-736, 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:spr:joptap:v:188:y:2021:i:3:d:10.1007_s10957-020-01799-3. 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.