{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:35Z","timestamp":1778231435441,"version":"3.51.4"},"reference-count":50,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>Many recent studies on first-order methods (FOMs) focus on composite nonconvex nonsmooth optimization with linear and\/or nonlinear function constraints. Upper (or worst-case) complexity bounds have been established for these methods. However, little can be claimed about their optimality, as no lower bound is known except for a few special smooth nonconvex cases. In this paper, we make the first attempt to establish lower complexity bounds of FOMs for solving a class of composite nonconvex nonsmooth optimization with linear constraints. Assuming two different first-order oracles, we establish lower complexity bounds of FOMs to produce a (near) [Formula: see text]-stationary point of a problem (and its reformulation) in the considered problem class for any given tolerance [Formula: see text]. Our lower bounds indicate that the existence of a nonsmooth convex regularizer can evidently increase the difficulty of an affinely constrained regularized problem over its nonregularized counterpart. In addition, we show that our lower bound of FOMs with the second oracle is tight, with a difference of up to a logarithmic factor from an upper complexity bound established in a longer arXiv version of this work.<\/jats:p>\n                  <jats:p>Funding: This work was partly supported by the Office of Naval Research [Grant N00014-22-1-2573] and the National Science Foundation [Grants DMS-2053493, DMS-2406896, and IIS-2147253].<\/jats:p>","DOI":"10.1287\/moor.2023.0377","type":"journal-article","created":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T12:20:27Z","timestamp":1749730827000},"page":"1659-1682","source":"Crossref","is-referenced-by-count":0,"title":["Lower Complexity Bounds of First-Order Methods for Affinely Constrained Composite Nonconvex Problems"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2376-8974","authenticated-orcid":false,"given":"Wei","family":"Liu","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2943-3267","authenticated-orcid":false,"given":"Qihang","family":"Lin","sequence":"additional","affiliation":[{"name":"Department of Business Analytics, University of Iowa, Iowa City, Iowa 52242"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4163-3723","authenticated-orcid":false,"given":"Yangyang","family":"Xu","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1137\/140985639"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01406-y"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01431-x"},{"key":"B4","first-page":"1","volume":"88","author":"Cartis C","year":"2012","journal-title":"Math. Optim. Soc. Newsletter"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0617-9"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1016-4"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971309"},{"key":"B8","unstructured":"Dahal H, Liu W, Xu Y (2023) Damped proximal augmented Lagrangian method for weakly-convex problems with convex constraints. Preprint, submitted November 15, https:\/\/arxiv.org\/abs\/2311.09065."},{"key":"B9","unstructured":"Goncalves MLN, Melo JG, Monteiro RDC (2017) Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems. Preprint, submitted February 7, https:\/\/arxiv.org\/abs\/1702.01850."},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/draa021"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1561\/0100000006"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1290-4"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01365-4"},{"key":"B14","unstructured":"Hong M (2016) Decomposing linearly constrained nonconvex problems by a proximal primal dual approach: Algorithms, convergence, and applications. Preprint, submitted April 2, https:\/\/arxiv.org\/abs\/1604.00543."},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1137\/140990309"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.52202\/075280-2679"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-018-0034-y"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1137\/18M1171011"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.1301"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-39568-1"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/ijoo.2021.0052"},{"key":"B22","first-page":"1792","volume":"34","author":"Li H","year":"2021","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B23","unstructured":"Lin T, Jin C, Jordan M (2020) On gradient descent ascent for nonconvex-concave minimax problems. Daum\u00e9 III H, Singh A, eds.\n                      Proc. 37th Internat. Conf. Machine Learn. (ICML 2020)\n                      , Proceedings of Machine Learning Research, vol. 119 (PMLR, New York), 6083\u20136093."},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-022-00358-y"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1137\/21M1408713"},{"issue":"212","key":"B26","first-page":"1","volume":"24","author":"Liu W","year":"2023","journal-title":"J. Machine Learn. Res."},{"key":"B27","unstructured":"Liu W, Lin Q, Xu Y (2023a) First-order methods for affinely constrained composite non-convex non-smooth problems: Lower complexity bound and near-optimal methods. Preprint, submitted July 14, https:\/\/arxiv.org\/abs\/2307.07605."},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2020.2986363"},{"key":"B29","unstructured":"Melo JG, Monteiro RDC (2017) Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs. Preprint, submitted May 20, https:\/\/arxiv.org\/abs\/1705.07229."},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-023-02218-z"},{"key":"B31","unstructured":"Murty KG, Kabadi SN (1985) Some NP-complete problems in quadratic and nonlinear programming. Technical Report 85-23, University of New Brunswick, Fredericton, NB, Canada."},{"key":"B32","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"Nemirovsky AS","year":"1983"},{"key":"B33","first-page":"10","volume":"88","author":"Nesterov Y","year":"2012","journal-title":"Math. Optim. Soc. Newsletter"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/drz074"},{"key":"B35","first-page":"3965","author":"Sahin MF","year":"2019","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2019.2943230"},{"key":"B37","first-page":"12680","volume":"32","author":"Thekumparampil K","year":"2019","journal-title":"Adv. Neural Inform. Processing Systems"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2023.1360"},{"key":"B39","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-021-01409-y"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1137\/16M1082305"},{"key":"B41","doi-asserted-by":"publisher","DOI":"10.1287\/ijoo.2019.0033"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1137\/23M1558677"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01919-z"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-022-01174-8"},{"key":"B45","doi-asserted-by":"publisher","DOI":"10.1137\/19M1242276"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1137\/20M135474X"},{"key":"B47","unstructured":"Zhang J, Pu W, Luo Z (2022) On the iteration complexity of smoothed proximal ALM for nonconvex optimization problem with convex constraints. Preprint, submitted July 13, https:\/\/arxiv.org\/abs\/2207.06304."},{"key":"B48","unstructured":"Zhang J, Lin H, Jegelka S, Sra S, Jadbabaie S (2020) Complexity of finding stationary points of nonconvex nonsmooth functions. Daum\u00e9 III H, Singh A, eds.\n                      Proc. 37th Internat. Conf. Machine Learn. (ICML 2020)\n                      , Proceedings of Machine Learning Research, vol. 119 (PMLR, New York), 11173\u201311182."},{"key":"B49","unstructured":"Zhang S, Yang J, Guzm\u00e1n C, Kiyavash N, He N (2021) The complexity of nonconvex-strongly-concave minimax optimization. de Campos C, Maathuis MH, eds.\n                      Proc. 37th Conf. Uncertainty Artif. Intell. (UAI 2021)\n                      , Proceedings of Machine Learning Research, vol. 161  (PMLR, New York), 482\u2013492."},{"key":"B50","unstructured":"Zhu Z, Chen F, Zhang J, Wen Z (2023) On the optimal lower and upper complexity bounds for a class of composite optimization problems. Preprint, submitted August 12, https:\/\/arxiv.org\/abs\/2308.06470."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2023.0377","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:24:16Z","timestamp":1778228656000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2023.0377"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2023.0377"],"URL":"https:\/\/doi.org\/10.1287\/moor.2023.0377","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}