{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:04Z","timestamp":1787337184564,"version":"build-2736575974"},"reference-count":56,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100003802","name":"University Research Committee, University of Hong Kong","doi-asserted-by":"publisher","award":["12302318"],"award-info":[{"award-number":["12302318"]}],"id":[{"id":"10.13039\/501100003802","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001747","name":"Hong Kong Baptist University","doi-asserted-by":"publisher","award":["RC-NACAN-ZHANG J"],"award-info":[{"award-number":["RC-NACAN-ZHANG J"]}],"id":[{"id":"10.13039\/501100001747","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11571056"],"award-info":[{"award-number":["11571056"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11601458"],"award-info":[{"award-number":["11601458"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Numer. Anal."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In the literature, error bound conditions have been widely used to study the linear convergence rates of various first-order algorithms. Most of the literature focuses on how to ensure these error bound conditions, usually posing numerous assumptions or special structures on the model under discussion. In this paper, we focus on the alternating direction method of multipliers (ADMM) and show that the known error bound conditions for studying the ADMM's linear convergence rate can indeed be further weakened if the error bound is studied over the specific iterative sequence it generates. An error bound condition based on ADMM's iterations is thus proposed, and linear convergence under this condition is proved. Furthermore, taking advantage of a specific feature of ADMM's iterative scheme by which part of the perturbation is automatically zero, we propose the so-called partial error bound condition, which is weaker than known error bound conditions in the literature, and we derive the linear convergence rate of ADMM. We further show that this partial error bound condition is useful for interpreting the difference if the two primal variables are updated in different orders when implementing the ADMM. This has been empirically observed in the literature, yet no theory is known.<\/jats:p>","DOI":"10.1137\/17m1144623","type":"journal-article","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T13:50:29Z","timestamp":1531835429000},"page":"2095-2123","source":"Crossref","is-referenced-by-count":19,"title":["Partial Error Bound Conditions and the Linear Convergence Rate of the Alternating Direction Method of Multipliers"],"prefix":"10.1137","volume":"56","author":[{"given":"Yongchao","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoming","family":"Yuan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shangzhi","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6691-5612","authenticated-orcid":true,"given":"Jin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,7,17]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/15M103580X"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.9.1.87"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/120878951"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"atypb5","volume-title":"Technical report","author":"Chan T. F.","year":"1978"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971309"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-87821-8"},{"key":"atypb10","volume-title":"Quadratic Growth, and Linear Convergence of Proximal Methods, preprint, https:\/\/arxiv.org\/abs\/1602.06661","author":"Drusvyatskiy D.","year":"2016"},{"key":"atypb11","volume-title":"LIDS-P, Laboratory for Information and Decision Systems","author":"Eckstein J.","year":"1990"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"},{"key":"atypb13","first-page":"619","volume":"11","author":"Eckstein J.","year":"2015","journal-title":"Pacific J. Optim."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0078-2"},{"key":"atypb15","volume-title":"Finite-dimensional Variational Inequalities and Complementarity Problems","author":"Francisco F.","year":"2007"},{"key":"atypb16","volume-title":"Stud. Math. Appl. 15","author":"Fortin M.","year":"1983"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-9054-3_4"},{"key":"atypb19","first-page":"41","volume-title":"RAIRO, R2","author":"Glowinski R.","year":"1975"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970838"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/100813415"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-012-0220-5"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0914-1"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1137\/15M1012608"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/16M1086881"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1137\/15M1052299"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/16M1088752"},{"key":"atypb28","volume-title":"Linear rate convergence of the alternating direction method of multipliers for convex composite quadratic and semi-definite programming, preprint, arXiv:1508.02134","author":"Han D. R.","year":"2015"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/120886753"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(98)00044-3"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/100814494"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-014-0673-6"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401395553"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1034-2"},{"key":"atypb36","volume-title":"The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices, https:\/\/arxiv.org\/abs\/1009.5055","author":"Lin Z. C.","year":"2010"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-014-5469-5"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s11228-008-0095-7"},{"key":"atypb40","first-page":"154","volume":"4","author":"Martinet B.","year":"1970","journal-title":"Rev. Fran\u00e7aise Informat. Recherche Op\u00e9rationnelle"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"atypb42","volume-title":"A General Analysis of the Convergence of ADMM, https:\/\/arxiv.org\/abs\/1502.02009","author":"Nishihara R.","year":"2015"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/0712056"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1137\/0713043"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.1.43"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02431-3"},{"key":"atypb47","unstructured":"R. Shefi,\n                      Rate of Convergence Analysis for Convex Nonsmooth Optimization Algorithms\n                      , Ph.D. thesis, Tel Aviv University, Israel, 2015."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0477-9"},{"key":"atypb49","volume-title":"Testing and Non-Linear Preconditioning of the Proximal Point Method, arXiv:1703.05705","author":"Valkonen T.","year":"2017"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-016-0692-2"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1137\/110833543"},{"key":"atypb52","volume-title":"Linear Convergence of the Proximal Gradient Method for Nonsmooth Nonconvex Optimization Problems via Variational Analysis, manuscript","author":"Wang X. F.","year":"2017"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2012-02598-1"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1137\/140974237"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1287\/moor.22.4.977"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1137\/090746379"}],"container-title":["SIAM Journal on Numerical Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1144623","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:48:14Z","timestamp":1787334494000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1144623"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1144623"],"URL":"https:\/\/doi.org\/10.1137\/17m1144623","relation":{},"ISSN":["0036-1429","1095-7170"],"issn-type":[{"value":"0036-1429","type":"print"},{"value":"1095-7170","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}