2023/06/01 by Tianlong Nan, Yuan Gao, Nan, Tianlong +3 · 2 citations
Computer Science · Mathematics · #Adaptive Dynamic Programming Control #Advanced Optimization Algorithms Research #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis
paper · pdf · doi:10.48550/arxiv.2306.01796
openalex publication_date 2023/06/01 · openalex created_date 2023/06/07 · openalex updated_date 2026/07/28
We study the last-iterate convergence of variance reduction methods for extragradient (EG) algorithms for a class of variational inequalities satisfying error-bound conditions. Previously, last-iterate linear convergence was only known under strong monotonicity. We show that EG algorithms with SVRG-style variance reduction, denoted SVRG-EG, attain last-iterate linear convergence under a general error-bound condition much weaker than strong monotonicity. This condition captures a broad class of non-strongly monotone problems, such as bilinear saddle-point problems commonly encountered in two-player zero-sum Nash equilibrium computation. Next, we establish linear last-iterate convergence of SVRG-EG with an improved guarantee under the weak sharpness assumption. Furthermore, motivated by the empirical efficiency of increasing iterate averaging techniques in solving saddle-point problems, we also establish new convergence results for SVRG-EG with such techniques.