{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T21:57:31Z","timestamp":1747173451482,"version":"3.40.5"},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T00:00:00Z","timestamp":1678752000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Alternating direction method of multipliers (ADMM) receives much attention in the field of optimization and computer science, etc. The generalized ADMM (G-ADMM) proposed by Eckstein and Bertsekas incorporates an acceleration factor and is more efficient than the original ADMM. However, G-ADMM is not applicable in some models where the objective function value (or its gradient) is computationally costly or even impossible to compute. In this paper, we consider the two-block separable convex optimization problem with linear constraints, where only noisy estimations of the gradient of the objective function are accessible. Under this setting, we propose a stochastic linearized generalized ADMM (called SLG-ADMM) where two subproblems are approximated by some linearization strategies. And in theory, we analyze the expected convergence rates and large deviation properties of SLG-ADMM. In particular, we show that the worst-case expected convergence rates of SLG-ADMM are <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096012952300004X_inline1.png\"\/><jats:tex-math>\n$\\mathcal{O}\\left( {{N}^{-1\/2}}\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096012952300004X_inline2.png\"\/><jats:tex-math>\n$\\mathcal{O}\\left({\\ln N} \\cdot {N}^{-1}\\right)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for solving general convex and strongly convex problems, respectively, where <jats:italic>N<\/jats:italic> is the iteration number, similarly hereinafter, and with high probability, SLG-ADMM has <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096012952300004X_inline3.png\"\/><jats:tex-math>\n$\\mathcal{O}\\left ( \\ln N \\cdot N^{-1\/2} \\right ) $\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S096012952300004X_inline4.png\"\/><jats:tex-math>\n$\\mathcal{O}\\left ( \\left ( \\ln N \\right )^{2} \\cdot N^{-1} \\right ) $\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> constraint violation bounds and objective error bounds for general convex and strongly convex problems, respectively.<\/jats:p>","DOI":"10.1017\/s096012952300004x","type":"journal-article","created":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T10:42:50Z","timestamp":1678790570000},"page":"162-179","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Stochastic linearized generalized alternating direction method of multipliers: Expected convergence rates and large deviation properties"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3072-757X","authenticated-orcid":false,"given":"Jia","family":"Hu","sequence":"first","affiliation":[]},{"given":"Tiande","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Congying","family":"Han","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2023,3,14]]},"reference":[{"key":"S096012952300004X_ref13","first-page":"81","article-title":"On the convergence properties of alternating direction method of multipliers","volume":"39","author":"He","year":"2017","journal-title":"Numerical Mathematics, a Journal of Chinese Universities(Chinese Series)"},{"key":"S096012952300004X_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0621-6"},{"key":"S096012952300004X_ref19","doi-asserted-by":"publisher","DOI":"10.1137\/140998135"},{"key":"S096012952300004X_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/140974237"},{"key":"S096012952300004X_ref20","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"S096012952300004X_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-018-0757-z"},{"key":"S096012952300004X_ref22","first-page":"80","volume-title":"Proceedings of the 30th International Conference on Machine Learning","author":"Ouyang","year":"2013"},{"key":"S096012952300004X_ref12","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2017.0875"},{"key":"S096012952300004X_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0871-8"},{"key":"S096012952300004X_ref28","doi-asserted-by":"publisher","DOI":"10.1137\/19M1242276"},{"key":"S096012952300004X_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-021-00368-3"},{"key":"S096012952300004X_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0078-2"},{"key":"S096012952300004X_ref24","first-page":"392","volume-title":"Proceedings of the 30th International Conference on Machine Learning","author":"Suzuki","year":"2013"},{"key":"S096012952300004X_ref25","first-page":"736","volume-title":"Proceedings of the 31th International Conference on Machine Learning","author":"Suzuki","year":"2014"},{"key":"S096012952300004X_ref21","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"S096012952300004X_ref10","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/197509R200411"},{"key":"S096012952300004X_ref29","first-page":"69","volume-title":"Proceedings of the 32th International Conference on Machine Learning","author":"Zhao","year":"2015"},{"key":"S096012952300004X_ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0846-1"},{"key":"S096012952300004X_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0434-y"},{"key":"S096012952300004X_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"S096012952300004X_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-018-0034-y"},{"key":"S096012952300004X_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"S096012952300004X_ref15","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s00211-014-0673-6","article-title":"On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers","volume":"130","author":"He","year":"2015","journal-title":"Numerische Mathematik"},{"key":"S096012952300004X_ref6","doi-asserted-by":"crossref","first-page":"2341","DOI":"10.1137\/120880811","article-title":"Stochastic first-and zeroth-order methods for nonconvex stochastic programming","volume":"23","author":"Ghadimi","year":"2013","journal-title":"SIAM Journal on Optimization"},{"key":"S096012952300004X_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-9054-3_4"},{"key":"S096012952300004X_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1"},{"key":"S096012952300004X_ref23","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729586"},{"key":"S096012952300004X_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"S096012952300004X_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096012952300004X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,3]],"date-time":"2024-06-03T11:01:57Z","timestamp":1717412517000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096012952300004X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,14]]},"references-count":29,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["S096012952300004X"],"URL":"https:\/\/doi.org\/10.1017\/s096012952300004x","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2023,3,14]]},"assertion":[{"value":"\u00a9 The Author(s), 2023. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}