Non-ergodic convergence rate of an inertial accelerated primal-dual algorithm for saddle point problems

2023/11/19 by Xin He, He, X., Nan‐jing Huang +3 · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Mathematics #Mathematical Inequalities and Applications #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2311.11274

openalex publication_date 2023/11/19 · openalex created_date 2023/11/22 · openalex updated_date 2026/07/28

Abstract

In this paper, we design an inertial accelerated primal-dual algorithm to address the convex-concave saddle point problem, which is formulated as min_xmax_y f(x) + ⟨ Kx, y ⟩ - g(y). Remarkably, both functions f and g exhibit a composite structure, combining ``nonsmooth'' + ``smooth'' components. Under the assumption of partially strong convexity in the sense that f is convex and g is strongly convex, we introduce a novel inertial accelerated primal-dual algorithm based on Nesterov's extrapolation. This algorithm can be reduced to two classical accelerated forward-backward methods for unconstrained optimization problem. We show that the proposed algorithm achieves a non-ergodic O(1/k²) convergence rate, where k represents the number of iterations. Several numerical experiments validate the efficiency of our proposed algorithm.

Cited by

• Inertial accelerated primal-dual algorithms for non-smooth convex optimization problems with linear equality constraints
• Preconditioned primal-dual algorithms for saddle point problems: non-ergodic convergence rates

Related

• Accelerated Primal-Dual Methods for Convex-Strongly-Concave Saddle Point Problems
• An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function
• Accelerated Primal-dual Scheme for a Class of Stochastic Nonconvex-concave Saddle Point Problems
• Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component
• Non-Stationary First-Order Primal-Dual Algorithms with Faster Convergence Rates