Accelerated Primal Dual Method for a Class of Saddle Point Problem with Strongly Convex Component

Understand

This paper presents a simple primal dual method named DPD which is a flexible framework for a class of saddle point problem with or without strongly convex component.

• The presented method has linearized version named LDPD and exact version EDPD.
• Each iteration of DPD updates sequentially the dual and primal variable via simple proximal mapping and refines the dual variable via extrapolation.
• Convergence analysis with smooth or strongly convex primal component recovers previous state-of-the-art results, and that with strongly convex dual component attains full acceleration $O(1/k^2)$ in terms of primal dual gap.