Approximate first-order primal-dual algorithms for saddle point problems

Abstract:

We propose two approximate versions of the first-order primal-dual algorithm (PDA) to solve a class of convex-concave saddle point problems. The introduced approximate criteria are easy to implement in the sense that they only involve the subgradient of a certain function at the current iterate. The first approximate PDA solves both subproblems inexactly and adopts the absolute error criteria, which are based on non-negative summable sequences. Assuming that one of the PDA subproblems can be solved exactly, the second approximate PDA solves the other subproblem approximately and adopts a relative error criterion. The relative error criterion only involves a single parameter in the range of $[0, 1)$, which makes the method more applicable. For both versions, we establish the global convergence and $O(1/N)$ convergence rate measured by the iteration complexity, where $N$ counts the number of iterations. For the inexact PDA with absolute error criteria, we show the accelerated $O(1/N^2)$ and linear convergence rate under the assumptions that a part of the underlying functions and both underlying functions are strongly convex, respectively. Then, we prove that these inexact criteria can also be extended to solve a class of more general problems. Finally, we perform some numerical experiments on sparse recovery and image processing problems. The results demonstrate the feasibility and superiority of the proposed methods.