Stochastic Variance Reduced Primal–Dual Hybrid Gradient Methods for Saddle-Point Problems

Weixin An, Yuanyuan Liu (), Fanhua Shang () and Hongying Liu ()
Additional contact information
Weixin An: The Key Laboratory of Intelligent Perception and Image Understanding of the Ministry of Education, School of Artificial Intelligence, Xidian University, Xi’an 710126, China
Yuanyuan Liu: The Key Laboratory of Intelligent Perception and Image Understanding of the Ministry of Education, School of Artificial Intelligence, Xidian University, Xi’an 710126, China
Fanhua Shang: The College of Intelligence and Computing, Tianjin University, Tianjin 300072, China
Hongying Liu: Medical College, Tianjin University, Tianjin 300072, China

Mathematics, 2025, vol. 13, issue 10, 1-44

Abstract: Recently, many stochastic Alternating Direction Methods of Multipliers (ADMMs) have been proposed to solve large-scale machine learning problems. However, for large-scale saddle-point problems, the state-of-the-art (SOTA) stochastic ADMMs still have high per-iteration costs. On the other hand, the stochastic primal–dual hybrid gradient (SPDHG) has a low per-iteration cost but only a suboptimal convergence rate of 𝒪 ( 1 / S ) . Thus, there still remains a gap in the convergence rates between SPDHG and SOTA ADMMs. Motivated by the two matters, we propose (accelerated) stochastic variance reduced primal–dual hybrid gradient ((A)SVR-PDHG) methods. We design a linear extrapolation step to improve the convergence rate and a new adaptive epoch length strategy to remove the extra boundedness assumption. Our algorithms have a simpler structure and lower per-iteration complexity than SOTA ADMMs. As a by-product, we present the asynchronous parallel variants of our algorithms. In theory, we rigorously prove that our methods converge linearly for strongly convex problems and improve the convergence rate to 𝒪 ( 1 / S 2 ) for non-strongly convex problems as opposed to the existing 𝒪 ( 1 / S ) convergence rate. Compared with SOTA algorithms, various experimental results demonstrate that ASVR-PDHG can achieve an average speedup of 2 × ∼ 5 × .

Keywords: saddle-point problem; stochastic optimization; variance reduction; asynchronous parallelism (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/10/1687/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/10/1687/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:10:p:1687-:d:1660965

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().