On the Convergence of Bregman ADMM With Variational Inequality

Abstract

The alternating direction method of multipliers (ADMM) is one of most foundational algorithms for linear constrained composite minimization problems. For different specific problems, variations of ADMM (like linearized ADMM, proximal ADMM) are developed. By using the Bregman distances, lots of ADMMs can be formulated into a uniform mathematical scheme. Although variational inequalities have been well used to study ADMMs, the use for BADMM has still been missing. In this paper, we study the convergence of BADMM by variational inequalities. We present a proof framework for BADMMs. And then, we present very concise convergence proof for the basic BADMM. As applications, we consider several variations of BADMM and obtain corresponding convergence results.

Keywords

• Convex proximal inertial gradient descent
• heavy-ball method
• non-ergodic convergence rates
• block coordinate descent
• computational complexity
• machine learning algorithms