EconPapers    
Economics at your fingertips  
 

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 ().

 
Page updated 2025-05-24
Handle: RePEc:gam:jmathe:v:13:y:2025:i:10:p:1687-:d:1660965