A proximal ADMM for multiblock problems with block anti-upper triangular constraints

Zhanwang Deng, Yuqiu Su, Wen Huang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:24284-24312, 2026.

Abstract

In this paper, we present the convergence analysis of the proximal Alternating Direction Method of Multipliers (ADMM) for problems with block anti-upper triangular constraints. While the linear constraints can be treated separately, most analyses of ADMM and its variants predominantly regard the linear constraints as one. Hence, it relies on assumptions related to the entire constraint matrix, such as the full column rank. However, some problems with block anti-upper triangular constraints that can be solved by ADMM do not satisfy these assumptions. To fill this gap, a new assumption is proposed and used to guarantee the global convergence of the proximal ADMM for nonconvex problems. In the strongly convex setting, we also prove the global convergence of the proximal ADMM and establish the linear convergence under four different scenarios. This work extends the theoretical understanding of the multi-block ADMM to more general cases with block anti-upper triangular constraints.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-deng26s, title = {A proximal {ADMM} for multiblock problems with block anti-upper triangular constraints}, author = {Deng, Zhanwang and Su, Yuqiu and Huang, Wen}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {24284--24312}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/deng26s/deng26s.pdf}, url = {https://proceedings.mlr.press/v306/deng26s.html}, abstract = {In this paper, we present the convergence analysis of the proximal Alternating Direction Method of Multipliers (ADMM) for problems with block anti-upper triangular constraints. While the linear constraints can be treated separately, most analyses of ADMM and its variants predominantly regard the linear constraints as one. Hence, it relies on assumptions related to the entire constraint matrix, such as the full column rank. However, some problems with block anti-upper triangular constraints that can be solved by ADMM do not satisfy these assumptions. To fill this gap, a new assumption is proposed and used to guarantee the global convergence of the proximal ADMM for nonconvex problems. In the strongly convex setting, we also prove the global convergence of the proximal ADMM and establish the linear convergence under four different scenarios. This work extends the theoretical understanding of the multi-block ADMM to more general cases with block anti-upper triangular constraints.} }
Endnote
%0 Conference Paper %T A proximal ADMM for multiblock problems with block anti-upper triangular constraints %A Zhanwang Deng %A Yuqiu Su %A Wen Huang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-deng26s %I PMLR %P 24284--24312 %U https://proceedings.mlr.press/v306/deng26s.html %V 306 %X In this paper, we present the convergence analysis of the proximal Alternating Direction Method of Multipliers (ADMM) for problems with block anti-upper triangular constraints. While the linear constraints can be treated separately, most analyses of ADMM and its variants predominantly regard the linear constraints as one. Hence, it relies on assumptions related to the entire constraint matrix, such as the full column rank. However, some problems with block anti-upper triangular constraints that can be solved by ADMM do not satisfy these assumptions. To fill this gap, a new assumption is proposed and used to guarantee the global convergence of the proximal ADMM for nonconvex problems. In the strongly convex setting, we also prove the global convergence of the proximal ADMM and establish the linear convergence under four different scenarios. This work extends the theoretical understanding of the multi-block ADMM to more general cases with block anti-upper triangular constraints.
APA
Deng, Z., Su, Y. & Huang, W.. (2026). A proximal ADMM for multiblock problems with block anti-upper triangular constraints. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:24284-24312 Available from https://proceedings.mlr.press/v306/deng26s.html.

Related Material