Quadratic error bound of the smoothed gap and the restarted averaged primal-dual hybrid gradient

Understand

We study the linear convergence of the primal-dual hybrid gradient method.

• After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems.
• We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems.
• Equipped with this tool, we manage to prove tighter convergence rates.