A New Primal-Dual Algorithm with Two Convex Combinations and Linesearch for General Convex-Concave Saddle-Point Problems

Abstract

Convex-concave saddle-point problems are ubiquitous across diverse domains, including machine learning, image processing, economics, and equilibrium problems. Primal-dual algorithms provide a highly effective and powerful framework for convex-concave saddle-point problems. Convex combination has become a crucial acceleration technique for primal-dual algorithms, and the integration of this technique has recently made these algorithms a highly active research topic. The choice of the convex combination parameter often has a significant impact on both the theoretical analysis and the numerical performance of the corresponding algorithms. However, the requirements on this parameter imposed by theory are sometimes inconsistent with those suggested by numerical experiments. For instance, theoretical analysis often requires the parameter to be small, while numerical experiments tend sometimes to favor larger values. To address this inconsistency and further advance primal-dual algorithms with convex combination, we develop a novel strategy based on two convex combinations, integrate it into a primal-dual framework, and propose a new primal-dual algorithm with linesearch, termed NPDAL-n, for general convex-concave saddle-point problems. The proposed two convex combinations in NPDAL-n ensure that the permissible range of the convex combination parameters is mainly determined by theoretical considerations, with little regard for numerical performance. Through rigorous Lyapunov energy descent analysis, we establish the global convergence and a sublinear ergodic convergence rate of $\mathcal{O}(1/N)$ for NPDAL-n under standard assumptions. When the primal function is strongly convex, we develop an accelerated version of NPDAL-n that achieves an optimal $\mathcal{O}(1/N^2)$ rate.