Unifying Variational View of Accelerated Primal-Dual Methods

Abstract

We develop a unifying variational framework for accelerated primal-dual flows in affinely constrained convex optimization. In particular, it is shown that applying the Euler-Lagrange-Rayleigh (ELR) principle to coupled augmented Bregman Lagrangians systematically generates accelerated dynamics over general Bregman geometries and recovers a family of existing primal-dual mirror and Alternating Direction Method of Multipliers (ADMM) flows as special cases. We then establish $\mathcal{O}(e^{-b_t})$ convergence guarantees for these flows under mild assumptions. Lastly, we show that the proposed framework for algorithmic development extends from finite-dimensional optimization to constrained optimization over probability distributions.