  Primal-dual hybrid gradient method (PDHG, a.k.a. Chambolle and Pock method)
is a well-studied algorithm for minimax optimization problems with a bilinear
interaction term. Recently, PDHG is used as the base algorithm for a new LP
solver PDLP that aims to solve large LP instances by taking advantage of modern
computing resources, such as GPU and distributed system. Most of the previous
convergence results of PDHG are either on duality gap or on distance to the
optimal solution set, which are usually hard to compute during the solving
process. In this paper, we propose a new progress metric for analyzing PDHG,
which we dub infimal sub-differential size (IDS), by utilizing the geometry of
PDHG iterates. IDS is a natural extension of the gradient norm of smooth
problems to non-smooth problems, and it is tied with KKT error in the case of
LP. Compared to traditional progress metrics for PDHG, IDS always has a finite
value and can be computed only using information of the current solution. We
show that IDS monotonically decays, and it has an $\mathcal O(\frac{1}{k})$
sublinear rate for solving convex-concave primal-dual problems, and it has a
linear convergence rate if the problem further satisfies a regularity condition
that is satisfied by applications such as linear programming, quadratic
programming, TV-denoising model, etc. The simplicity of our analysis and the
monotonic decay of IDS suggest that IDS is a natural progress metric to analyze
PDHG. As a by-product of our analysis, we show that the primal-dual gap has
$\mathcal O(\frac{1}{\sqrt{k}})$ convergence rate for the last iteration of
PDHG for convex-concave problems. The analysis and results on PDHG can be
directly generalized to other primal-dual algorithms, for example, proximal
point method (PPM), alternating direction method of multipliers (ADMM) and
linearized alternating direction method of multipliers (l-ADMM).
