On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM

ABSTRACT

Pointwise and ergodic iteration-complexity results for the proximal alternating direction method of multipliers (ADMM) for any stepsize in $(0,(1+\sqrt{5}\left)/2\right)$ have been recently established in the literature. In addition to giving alternative proofs of these results, this paper also extends the ergodic iteration-complexity result to include the case in which the stepsize is equal to $(1+\sqrt{5})/2$. As far as we know, this is the first ergodic iteration-complexity for the stepsize $(1+\sqrt{5})/2$ obtained in the ADMM literature. These results are obtained by showing that the proximal ADMM is an instance of a non-Euclidean hybrid proximal extragradient framework whose pointwise and ergodic convergence rate are also studied.

KEYWORDS:

• Alternating direction method of multipliers
• hybrid proximal extragradient method
• non-Euclidean Bregman distances
• iteration-complexity

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 90C60
• 90C30
• 90C25
• 49M27

Acknowledgments

The authors would like to thank an anonymous reviewer and the associate editor for their insightful comments on earlier drafts of this paper. We also thank the reviewer for bringing [26] to our attention.

Disclosure statement

No potential conflict of interest was reported by the authors.

ORCID

Max L. N. Gonçalves  http://orcid.org/0000-0001-9563-1101

Additional information

Funding

The work of these authors was supported in part by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Grants 302666/2017-6 and 406975/2016-7. The work of this author was partially supported by NSF Grant CMMI-1300221.