{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:16Z","timestamp":1787340736488,"version":"build-2736575974"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: [Formula: see text]. Under the standard first-order smoothness conditions where [Formula: see text] is [Formula: see text]-smooth in both arguments and [Formula: see text]-strongly concave in [Formula: see text], existing literature shows that the optimal complexity for first-order methods to obtain an [Formula: see text]-stationary point is [Formula: see text], where [Formula: see text] is the condition number. However, when [Formula: see text] has [Formula: see text]-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an [Formula: see text] complexity by designing an accelerated proximal point algorithm enhanced with the \u201cConvex Until Proven Guilty\u201d technique. Moreover, an improved [Formula: see text] lower bound for first-order method is also derived for sufficiently small [Formula: see text]. As a result, given the second-order smoothness of the problem, the complexity of our method improves the state-of-the-art result by a factor of [Formula: see text], while almost matching the lower bound except for a small [Formula: see text] factor.<\/jats:p>","DOI":"10.1137\/23m1566972","type":"journal-article","created":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T04:01:16Z","timestamp":1727755276000},"page":"3342-3370","source":"Crossref","is-referenced-by-count":0,"title":["Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness"],"prefix":"10.1137","volume":"34","author":[{"given":"Nuozhou","family":"Wang","sequence":"first","affiliation":[{"name":"Department of Industrial & Systems Engineering, University of Minnesota, Minneapolis, MN 55455, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2194-9664","authenticated-orcid":true,"given":"Junyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Industrial Systems Engineering and Management, National University of Singapore, Singapore, 117576."}],"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 & Systems Engineering, University of Minnesota, Minneapolis, MN 55455, USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,10,1]]},"reference":[{"key":"ref1","unstructured":"N. Agarwal, Z. Allen-Zhu, B. Bullins, E. Hazan, and T. Ma, Finding Approximate Local Minima for Nonconvex Optimization in Linear Time, preprint, https:\/\/arxiv.org\/abs\/1611.01146, 2016."},{"key":"ref2","first-page":"8194","volume":"18","author":"Allen-Zhu Z.","year":"2017","journal-title":"J. Mach. Learn. Res."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01957-1"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1974.10489171"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.jors.2600425"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1065-8"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/21M1465470"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1137\/21M1395764"},{"key":"ref9","unstructured":"Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, \u201cConvex until proven guilty\u201d: Dimension-free acceleration of gradient descent on non-convex functions, in International Conference on Machine Learning, PMLR, 2017, pp. 654\u2013663."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/17M1114296"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01406-y"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01431-x"},{"key":"ref13","unstructured":"L. Chen, Y. Ma, and J. Zhang, Near-optimal Fully First-order Algorithms for Finding Stationary Points in Bilevel Optimization, preprint, https:\/\/arxiv.org\/abs\/2306.14853, 2023."},{"key":"ref14","author":"Chen Z.","year":"2023","journal-title":"Trans. Mach. Learn. Res."},{"key":"ref15","unstructured":"Y.H. Dai, J. Wang, and L. Zhang, Optimality Conditions and Numerical Algorithms for a Class of Linearly Constrained Minimax Optimization Problems, preprint, https:\/\/arxiv.org\/abs\/2204.09185, 2022."},{"key":"ref16","first-page":"377","volume":"20","author":"Do C. B.","year":"2007","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref17","unstructured":"S. Ghadimi and M. Wang, Approximation Methods for Bilevel Programming, preprint, https:\/\/arxiv.org\/abs\/1802.02246, 2018."},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/3422622"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-022-01819-6"},{"key":"ref20","unstructured":"M. Huang, K. Ji, S. Ma, and L. Lai, Efficiently Escaping Saddle Points in Bilevel Optimization, preprint, https:\/\/arxiv.org\/abs\/2202.03684, 2022."},{"key":"ref21","unstructured":"K. Ji and Y. Liang, Lower Bounds and Accelerated Algorithms for Bilevel Optimization, preprint, https:\/\/arxiv.org\/abs\/2102.03926, 2021."},{"key":"ref22","unstructured":"K. Ji, J. Yang, and Y. Liang, Bilevel optimization: Convergence analysis and enhanced design, in International Conference on Machine Learning, PMLR, 2021, pp. 4882\u20134892."},{"key":"ref23","unstructured":"R. Jiang and A. Mokhtari, Generalized Optimistic Methods for Convex-concave Saddle Point Problems, preprint, https:\/\/arxiv.org\/abs\/2202.09674, 2022."},{"key":"ref24","unstructured":"C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan, How to escape saddle points efficiently, in International Conference on Machine Learning, PMLR, 2017, pp. 1724\u20131732."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1137\/20M1313222"},{"key":"ref26","volume":"24","author":"Li H.","year":"2023","journal-title":"J. Mach. Learn. Res."},{"key":"ref27","first-page":"1792","volume":"34","author":"Li H.","year":"2021","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref28","unstructured":"T. Lin, C. Jin, and M. Jordan, On gradient descent ascent for nonconvex-concave minimax problems, in International Conference on Machine Learning, PMLR, 2020, pp. 6083\u20136093."},{"key":"ref29","unstructured":"T. Lin, C. Jin, and M. I. Jordan, Near-optimal algorithms for minimax optimization, in Conference on Learning Theory, PMLR, 2020, pp. 2738\u20132779."},{"key":"ref30","unstructured":"T. Lin, and M. Jordan, Perseus: A Simple High-order Regularization Method for Variational Inequalities, preprint, https:\/\/arxiv.org\/abs\/2205.03202, 2022."},{"key":"ref31","first-page":"2353","volume":"48","author":"Lin T.","year":"2023","journal-title":"Math. Oper. Res."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2020.2986363"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"L. Luo, Y. Li, and C. Chen, Finding Second-order Stationary Points in Nonconvex-strongly-concave Minimax Optimization, preprint, https:\/\/arxiv.org\/abs\/2110.04814, 2021.","DOI":"10.52202\/068431-2657"},{"key":"ref34","unstructured":"L. Luo, G. Xie, T. Zhang, and Z. Zhang, Near Optimal Stochastic Algorithms for Finite-sum Unbalanced Convex-concave Minimax Optimization, preprint, https:\/\/arxiv.org\/abs\/2106.01761, 2021."},{"key":"ref35","first-page":"20566","volume":"33","author":"Luo L.","year":"2020","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"ref38","first-page":"14934","volume":"32","author":"Nouiehed M.","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref39","first-page":"1576","volume":"28","author":"Shafieezadeh Abadeh S.","year":"2015","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref40","unstructured":"A. Sinha, H. Namkoong, R. Volpi, and J. Duchi, Certifying Some Distributional Robustness with Principled Adversarial Training, preprint, https:\/\/arxiv.org\/abs\/1710.10571, 2017."},{"key":"ref41","first-page":"12680","volume":"32","author":"Thekumparampil K. K.","year":"2019","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref42","unstructured":"I. Tsaknakis, M. Hong, and S. Zhang, Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods, preprint, https:\/\/arxiv.org\/abs\/2110.11210, 2021."},{"key":"ref43","unstructured":"H. Yang, L. Luo, C. J. Li, M. Jordan, and M. Fazel, Accelerating inexact hypergradient descent for bilevel optimization, in OPT 2023: 15th Annual Workshop on Optimization for Machine Learning, 2023."},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1137\/21M1451944"},{"key":"ref45","first-page":"482","volume-title":"Uncertainty in Artificial Intelligence, PMLR","author":"Zhang S.","year":"2021"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1566972","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:45:47Z","timestamp":1787337947000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1566972"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,1]]},"references-count":45,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1137\/23M1566972"],"URL":"https:\/\/doi.org\/10.1137\/23m1566972","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,10,1]]}}}