IDEAS home Printed from https://ideas.repec.org/a/inm/ormoor/v47y2022i2p1443-1473.html

Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems

Author

Listed:
  • Renbo Zhao

    (Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142)

Abstract

We develop stochastic first-order primal-dual algorithms to solve a class of convex-concave saddle-point problems. When the saddle function is strongly convex in the primal variable, we develop the first stochastic restart scheme for this problem. When the gradient noises obey sub-Gaussian distributions, the oracle complexity of our restart scheme is strictly better than any of the existing methods, even in the deterministic case. Furthermore, for each problem parameter of interest, whenever the lower bound exists, the oracle complexity of our restart scheme is either optimal or nearly optimal (up to a log factor). The subroutine used in this scheme is itself a new stochastic algorithm developed for the problem where the saddle function is nonstrongly convex in the primal variable. This new algorithm, which is based on the primal-dual hybrid gradient framework, achieves the state-of-the-art oracle complexity and may be of independent interest.

Suggested Citation

  • Renbo Zhao, 2022. "Accelerated Stochastic Algorithms for Convex-Concave Saddle-Point Problems," Mathematics of Operations Research, INFORMS, vol. 47(2), pages 1443-1473, May.
    • Handle: RePEc:inm:ormoor:v:47:y:2022:i:2:p:1443-1473
    DOI: 10.1287/moor.2021.1175
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Efe A. Ok, 2007. "Preliminaries of Real Analysis, from Real Analysis with Economic Applications," Introductory Chapters, in: Real Analysis with Economic Applications, Princeton University Press.
    2. NESTEROV, Yurii, 2013. "Gradient methods for minimizing composite functions," LIDAM Reprints CORE 2510, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Laurent Condat, 2013. "A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms," Journal of Optimization Theory and Applications, Springer, vol. 158(2), pages 460-479, August.
    4. NESTEROV, Yurii, 2007. "Smoothing technique and its applications in semidefinite optimization," LIDAM Reprints CORE 1951, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    5. Hui Zou & Trevor Hastie, 2005. "Addendum: Regularization and variable selection via the elastic net," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 67(5), pages 768-768, November.
    6. Qihang Lin & Lin Xiao, 2015. "An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization," Computational Optimization and Applications, Springer, vol. 60(3), pages 633-674, April.
    7. Hui Zou & Trevor Hastie, 2005. "Regularization and variable selection via the elastic net," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 67(2), pages 301-320, April.
    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. Weixin An & Yuanyuan Liu & Fanhua Shang & Hongying Liu, 2025. "Stochastic Variance Reduced Primal–Dual Hybrid Gradient Methods for Saddle-Point Problems," Mathematics, MDPI, vol. 13(10), pages 1-44, May.
    2. Erfan Yazdandoost Hamedani & Afrooz Jalilzadeh, 2023. "A stochastic variance-reduced accelerated primal-dual method for finite-sum saddle-point problems," Computational Optimization and Applications, Springer, vol. 85(2), pages 653-679, June.

    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. Quoc Tran-Dinh, 2019. "Proximal alternating penalty algorithms for nonsmooth constrained convex optimization," Computational Optimization and Applications, Springer, vol. 72(1), pages 1-43, January.
    2. Rahul Mazumder & Peter Radchenko & Antoine Dedieu, 2023. "Subset Selection with Shrinkage: Sparse Linear Modeling When the SNR Is Low," Operations Research, INFORMS, vol. 71(1), pages 129-147, January.
    3. David Degras, 2021. "Sparse group fused lasso for model segmentation: a hybrid approach," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 15(3), pages 625-671, September.
    4. Summer Atkins & Gudmundur Einarsson & Line Clemmensen & Brendan Ames, 2023. "Proximal methods for sparse optimal scoring and discriminant analysis," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 17(4), pages 983-1036, December.
    5. VÁZQUEZ-ALCOCER, Alan & SCHOEN, Eric D. & GOOS, Peter, 2018. "A mixed integer optimization approach for model selection in screening experiments," Working Papers 2018007, University of Antwerp, Faculty of Business and Economics.
    6. Peiran Yu & Ting Kei Pong, 2019. "Iteratively reweighted $$\ell _1$$ ℓ 1 algorithms with extrapolation," Computational Optimization and Applications, Springer, vol. 73(2), pages 353-386, June.
    7. Santanu Soe & Matthew K. Tam & Vellaichamy Vetrivel, 2026. "The golden ratio primal-dual algorithm with two new stepsize rules for convex-concave saddle point problems," Computational Optimization and Applications, Springer, vol. 93(3), pages 1355-1399, April.
    8. Jian Huang & Yuling Jiao & Lican Kang & Jin Liu & Yanyan Liu & Xiliang Lu, 2022. "GSDAR: a fast Newton algorithm for $$\ell _0$$ ℓ 0 regularized generalized linear models with statistical guarantee," Computational Statistics, Springer, vol. 37(1), pages 507-533, March.
    9. Quoc Tran-Dinh & Ling Liang & Kim-Chuan Toh, 2022. "A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization," Mathematics of Operations Research, INFORMS, vol. 47(1), pages 508-539, February.
    10. Wenli Huang & Yuchao Tang & Meng Wen & Haiyang Li, 2022. "Relaxed Variable Metric Primal-Dual Fixed-Point Algorithm with Applications," Mathematics, MDPI, vol. 10(22), pages 1-16, November.
    11. Tutz, Gerhard & Pößnecker, Wolfgang & Uhlmann, Lorenz, 2015. "Variable selection in general multinomial logit models," Computational Statistics & Data Analysis, Elsevier, vol. 82(C), pages 207-222.
    12. Hauzenberger, Niko & Huber, Florian & Klieber, Karin & Marcellino, Massimiliano, 2025. "Bayesian neural networks for macroeconomic analysis," Journal of Econometrics, Elsevier, vol. 249(PC).
    13. Oxana Babecka Kucharcukova & Jan Bruha, 2016. "Nowcasting the Czech Trade Balance," Working Papers 2016/11, Czech National Bank, Research and Statistics Department.
    14. Carstensen, Kai & Heinrich, Markus & Reif, Magnus & Wolters, Maik H., 2020. "Predicting ordinary and severe recessions with a three-state Markov-switching dynamic factor model," International Journal of Forecasting, Elsevier, vol. 36(3), pages 829-850.
    15. Hou-Tai Chang & Ping-Huai Wang & Wei-Fang Chen & Chen-Ju Lin, 2022. "Risk Assessment of Early Lung Cancer with LDCT and Health Examinations," IJERPH, MDPI, vol. 19(8), pages 1-12, April.
    16. Margherita Giuzio, 2017. "Genetic algorithm versus classical methods in sparse index tracking," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 40(1), pages 243-256, November.
    17. Nicolaj N. Mühlbach, 2020. "Tree-based Synthetic Control Methods: Consequences of moving the US Embassy," CREATES Research Papers 2020-04, Department of Economics and Business Economics, Aarhus University.
    18. Hajime Shimao & Sung Joo Kim & Warut Khern-Am-Nuai & Maxime C. Cohen, 2025. "Revisiting the CEO Effect Through a Machine Learning Lens," Management Science, INFORMS, vol. 71(6), pages 5396-5408, June.
    19. Wang, Qiao & Zhou, Wei & Cheng, Yonggang & Ma, Gang & Chang, Xiaolin & Miao, Yu & Chen, E, 2018. "Regularized moving least-square method and regularized improved interpolating moving least-square method with nonsingular moment matrices," Applied Mathematics and Computation, Elsevier, vol. 325(C), pages 120-145.
    20. Dmitriy Drusvyatskiy & Adrian S. Lewis, 2018. "Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 919-948, August.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    JEL classification:

    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:inm:ormoor:v:47:y:2022:i:2:p:1443-1473. 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: 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.