Convergence Analysis of Inexact Over-relaxed ADMM via Dissipativity Theory

Qiang Zhou, Sinno Jialin Pan
Proceedings of the 16th Asian Conference on Machine Learning, PMLR 260:1080-1095, 2025.

Abstract

We present a new convergence analysis for the over-relaxed alternating direction method of multipliers (ADMM) when the subproblem cannot be exactly solved, \ie, inexact over-relaxed ADMM. Our method builds on \citep{hu2017dissipativity} that relates the convergence analysis of optimization algorithms to the stability of a discrete-time linear dynamic system. By expressing the inexact over-relaxed ADMM as a discrete-time linear dynamic system, we show that both the linear and sublinear convergence of inexact over-relaxed ADMM can be obtained by solving or verifying the feasibility of a small semidefinite program (SDP). More importantly, we prove that the associated SDP has an analytical solution for various parameters. We demonstrate the theoretical result by applying the inexact over-relaxed ADMM to solve a distributed ℓ1-norm regularized logistic regression problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-v260-zhou25b, title = {Convergence Analysis of Inexact Over-relaxed ADMM via Dissipativity Theory}, author = {Zhou, Qiang and Pan, Sinno Jialin}, booktitle = {Proceedings of the 16th Asian Conference on Machine Learning}, pages = {1080--1095}, year = {2025}, editor = {Nguyen, Vu and Lin, Hsuan-Tien}, volume = {260}, series = {Proceedings of Machine Learning Research}, month = {05--08 Dec}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v260/main/assets/zhou25b/zhou25b.pdf}, url = {https://proceedings.mlr.press/v260/zhou25b.html}, abstract = {We present a new convergence analysis for the over-relaxed alternating direction method of multipliers (ADMM) when the subproblem cannot be exactly solved, \ie, inexact over-relaxed ADMM. Our method builds on \citep{hu2017dissipativity} that relates the convergence analysis of optimization algorithms to the stability of a discrete-time linear dynamic system. By expressing the inexact over-relaxed ADMM as a discrete-time linear dynamic system, we show that both the linear and sublinear convergence of inexact over-relaxed ADMM can be obtained by solving or verifying the feasibility of a small semidefinite program (SDP). More importantly, we prove that the associated SDP has an analytical solution for various parameters. We demonstrate the theoretical result by applying the inexact over-relaxed ADMM to solve a distributed $\ell_1$-norm regularized logistic regression problem.} }
Endnote
%0 Conference Paper %T Convergence Analysis of Inexact Over-relaxed ADMM via Dissipativity Theory %A Qiang Zhou %A Sinno Jialin Pan %B Proceedings of the 16th Asian Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Vu Nguyen %E Hsuan-Tien Lin %F pmlr-v260-zhou25b %I PMLR %P 1080--1095 %U https://proceedings.mlr.press/v260/zhou25b.html %V 260 %X We present a new convergence analysis for the over-relaxed alternating direction method of multipliers (ADMM) when the subproblem cannot be exactly solved, \ie, inexact over-relaxed ADMM. Our method builds on \citep{hu2017dissipativity} that relates the convergence analysis of optimization algorithms to the stability of a discrete-time linear dynamic system. By expressing the inexact over-relaxed ADMM as a discrete-time linear dynamic system, we show that both the linear and sublinear convergence of inexact over-relaxed ADMM can be obtained by solving or verifying the feasibility of a small semidefinite program (SDP). More importantly, we prove that the associated SDP has an analytical solution for various parameters. We demonstrate the theoretical result by applying the inexact over-relaxed ADMM to solve a distributed $\ell_1$-norm regularized logistic regression problem.
APA
Zhou, Q. & Pan, S.J.. (2025). Convergence Analysis of Inexact Over-relaxed ADMM via Dissipativity Theory. Proceedings of the 16th Asian Conference on Machine Learning, in Proceedings of Machine Learning Research 260:1080-1095 Available from https://proceedings.mlr.press/v260/zhou25b.html.

Related Material