{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T20:23:08Z","timestamp":1787343788177,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["1006977"],"award-info":[{"award-number":["1006977"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["WBS R-266-000-158-133"],"award-info":[{"award-number":["WBS R-266-000-158-133"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1953686"],"award-info":[{"award-number":["DMS-1953686"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-2107304"],"award-info":[{"award-number":["IIS-2107304"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1653435"],"award-info":[{"award-number":["CMMI-1653435"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CIF-1910385"],"award-info":[{"award-number":["CIF-1910385"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1727757"],"award-info":[{"award-number":["CMMI-1727757"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider the convex-concave saddle point problem [Formula: see text], where the decision variables [Formula: see text] and\/or [Formula: see text] are subject to certain multi-block structure and affine coupling constraints, and [Formula: see text] possesses certain separable structure. Although the minimization counterpart of this problem has been widely studied under the topics of ADMM, this minimax problem is rarely investigated. In this paper, a convenient notion of [Formula: see text]-saddle point is proposed, under which the convergence rate of several proposed algorithms are analyzed. When only one of [Formula: see text] and [Formula: see text] has multiple blocks and affine constraint, several natural extensions of ADMM are proposed to solve the problem. Depending on the number of blocks and the level of smoothness, [Formula: see text] or [Formula: see text] convergence rates are derived for our algorithms. When both [Formula: see text] and [Formula: see text] have multiple blocks and affine constraints, a new algorithm called [Formula: see text]xtra-[Formula: see text]radient Method of [Formula: see text]ultipliers (EGMM) is proposed. Under desirable smoothness conditions, an [Formula: see text] rate of convergence can be guaranteed regardless of the number of blocks in [Formula: see text] and [Formula: see text]. An in-depth comparison between EGMM (fully primal-dual method) and ADMM (approximate dual method) is made over the multi-block optimization problems to illustrate the advantage of the EGMM.<\/jats:p>","DOI":"10.1137\/21m1451944","type":"journal-article","created":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T05:30:52Z","timestamp":1687411852000},"page":"1035-1060","source":"Crossref","is-referenced-by-count":5,"title":["Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems"],"prefix":"10.1137","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2194-9664","authenticated-orcid":true,"given":"Junyu","family":"Zhang","sequence":"first","affiliation":[{"name":"Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore 117576, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mengdi","family":"Wang","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingyi","family":"Hong","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN 55455 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"ref1","unstructured":"J. Abernethy , \nK. A. Lai , and \nA. Wibisono , Last-Iterate Convergence Rates for Min-Max Optimization, preprint, https:\/\/arxiv.org\/abs\/1906.02027, 2019."},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600425"},{"key":"ref3","volume-title":"Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers","author":"Boyd S.","year":"2011"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-016-9860-y"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-010-9757-3"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0957-3"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0826-5"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1155\/2013\/183961"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/130919362"},{"key":"ref11","unstructured":"Y. Chen , \nL. Li , and \nM. Wang , Scalable Bilinear   \\(\\pi\\)   Learning Using State and Action Features, preprint, 2018."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1214\/17-AOS1595"},{"key":"ref13","unstructured":"B. Dai , \nA. Shaw , \nL. Li , \nL. Xiao , \nN. He , \nZ. Liu , \nJ. Chen , and \nL. Song , SBEED: Convergent reinforcement learning with nonlinear function approximation, in Proceedings of the International Conference on Machine Learning (PMLR\u201818), 2018, pp. 1125\u20131134."},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-015-0048-x"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-018-0232-4"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1137\/110836936"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1034-2"},{"key":"ref18","unstructured":"A. Jalilzadeh , \nE. Y. Hamedani , and \nN. S. Aybat , A Doubly-Randomized Block-Coordinate Primal-Dual Method for Large-Scale Saddle Point Problems, preprint, https:\/\/arxiv.org\/abs\/1907.03886, 2019."},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1287\/10-SSY011"},{"key":"ref20","first-page":"694","volume":"19","author":"Korpelevich G. M.","year":"1983","journal-title":"\u00c8konom. i Mat. Metody"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595915500244"},{"key":"ref22","unstructured":"T. Liang  and \nJ. Stokes , Interaction matters: A note on non-asymptotic local convergence of generative adversarial networks, in Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics, 2019, pp. 907\u2013915."},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2013.2257618"},{"key":"ref24","unstructured":"T. Lin , \nC. Jin , \nM. Jordan , Et al., Near-Otimal Algorithms for Minimax Optimization, preprint, https:\/\/arxiv.org\/abs\/2002.02417, 2020."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/140971178"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s40305-015-0092-0"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-016-0182-0"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2018.2846606"},{"key":"ref29","unstructured":"A. Mokhtari , \nA. Ozdaglar , and \nS. Pattathil , A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach, in Proceedings of the International Conference on Artificial Intelligence and Statistics (PMLR\u201820), 2020, pp. 1497\u20131507."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/110849468"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623403425629"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0034-z"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.3934\/dcds.2011.31.1383"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01420-0"},{"key":"ref36","volume-title":"Theory of Games and Economic Behavior, commemorative ed.","author":"von Neumann J.","year":"2007"},{"key":"ref37","unstructured":"Y. Wang  and \nJ. Li , Improved Algorithms for Convex-Concave Minimax Optimization, preprint, https:\/\/arxiv.org\/abs\/2006.06359, 2020."},{"key":"ref38","first-page":"1634","volume":"20","author":"Xiao L.","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"ref39","unstructured":"J. Zhang , \nM. Hong , and \nS. Zhang , On Lower Iteration Complexity Bounds for the Saddle Point Problems, preprint, https:\/\/arxiv.org\/abs\/1912.07481, 2019."},{"key":"ref40","unstructured":"J. Zhang , \nA. Koppel , \nA. S. Bedi , \nC. Szepesvari , and \nM. Wang , Variational Policy Gradient Method for Reinforcement Learning with General Utilities, preprint, https:\/\/arxiv.org\/abs\/2007.02151, 2020."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1451944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:46Z","timestamp":1787340226000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1451944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,22]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M1451944"],"URL":"https:\/\/doi.org\/10.1137\/21m1451944","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,22]]}}}