{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T16:24:10Z","timestamp":1787243050628,"version":"build-2736575974"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T00:00:00Z","timestamp":1623024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-172775 and CIF-1910385"],"award-info":[{"award-number":["CMMI-172775 and CIF-1910385"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10107-021-01660-z","type":"journal-article","created":{"date-parts":[[2021,6,7]],"date-time":"2021-06-07T07:03:49Z","timestamp":1623049429000},"page":"901-935","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["On lower iteration complexity bounds for the convex concave saddle point problems"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2194-9664","authenticated-orcid":false,"given":"Junyu","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mingyi","family":"Hong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,7]]},"reference":[{"key":"1660_CR1","unstructured":"Abadeh, S.S., Esfahani, P.M., Kuhn, D.: Distributionally robust logistic regression. In: Advances in Neural Information Processing Systems, pp. 1576\u20131584, (2015)"},{"key":"1660_CR2","unstructured":"Agarwal, N., Hazan, E.: Lower bounds for higher-order convex optimization. arXiv preprint arXiv:1710.10329, (2017)"},{"issue":"1\u20132","key":"1660_CR3","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10107-018-1293-1","volume":"178","author":"Y Arjevani","year":"2019","unstructured":"Arjevani, Y., Shamir, O., Shiff, R.: Oracle complexity of second-order methods for smooth convex optimization. Math. Progr. 178(1\u20132), 327\u2013360 (2019)","journal-title":"Math. Progr."},{"key":"1660_CR4","unstructured":"Arjovsky, M., Chintala, S., Bottou, L.: Wasserstein Gan. arXiv preprint arXiv:1701.07875, (2017)"},{"key":"1660_CR5","unstructured":"Azizian, W., Scieur, D., Mitliagkas, I., Lacoste-Julien, S., Gidel, G.: Accelerating smooth games by manipulating spectral shapes. arXiv preprint arXiv:2001.00602, (2020)"},{"key":"1660_CR6","volume-title":"Nonlinear Progr.","author":"DP Bertsekas","year":"1997","unstructured":"Bertsekas, D.P.: Nonlinear Progr. Athena Scientific, Nashua (1997)"},{"key":"1660_CR7","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-019-01406-y","volume":"184","author":"Y Carmon","year":"2017","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. Math. Progr. 184, 71\u2013120 (2017)","journal-title":"Math. Progr."},{"key":"1660_CR8","first-page":"1","volume":"158","author":"Y Carmon","year":"2019","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points II: first-order methods. Math. Progr. 158, 1\u20132 (2019)","journal-title":"Math. Progr."},{"issue":"1","key":"1660_CR9","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"issue":"1\u20132","key":"1660_CR10","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s10107-015-0957-3","volume":"159","author":"A Chambolle","year":"2016","unstructured":"Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal-dual algorithm. Mah. Progr. 159(1\u20132), 253\u2013287 (2016)","journal-title":"Mah. Progr."},{"issue":"2","key":"1660_CR11","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s40305-016-0131-5","volume":"5","author":"X Gao","year":"2017","unstructured":"Gao, X., Zhang, S.: First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5(2), 131\u2013159 (2017)","journal-title":"J. Oper. Res. Soc. China"},{"key":"1660_CR12","unstructured":"Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversaria nets. In: Advances in Neural Information Processing Systems, pages 2672\u20132680, (2014)"},{"key":"1660_CR13","unstructured":"Ibrahim, A., Azizian, W., Gidel, G., Mitliagkas, I.: Linear lower bounds and conditioning of differentiable games. arXiv preprint arXiv:1906.07300, (2019)"},{"key":"1660_CR14","unstructured":"Jin, C., Netrapalli, P., Jordan, M.I.: Minmax optimization: Stable limit points of gradient descent ascent are locally optimal. arXiv preprint arXiv:1902.00618, (2019)"},{"key":"1660_CR15","unstructured":"Jin, C., Netrapalli, P., Jordan, M.I.: What is local optimality in nonconvex-nonconcave minimax optimization? arXiv preprint arXiv:1902.00618, (2019)"},{"issue":"1","key":"1660_CR16","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/10-SSY011","volume":"1","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., Tauvel, C.: Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1(1), 17\u201358 (2011)","journal-title":"Stoch. Syst."},{"key":"1660_CR17","first-page":"747","volume":"12","author":"GM Korpelevich","year":"1976","unstructured":"Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon 12, 747\u2013756 (1976)","journal-title":"Matecon"},{"key":"1660_CR18","unstructured":"Lin, Q., Liu, M., Rafique, H., Yang, T.: Solving weakly-convex-weakly-concave saddle-point problems as weakly-monotone variational inequality. arXiv preprint arXiv:1810.10207, (2018)"},{"key":"1660_CR19","unstructured":"Lin, T., Jin, C., Jordan, M.: Near-optimal algorithms for minimax optimization. In: Annual Conference on Learning Theory, (2020)"},{"key":"1660_CR20","unstructured":"Lin, T., Jin, C., Jordan, M.I.: On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv:1906.00331, (2019)"},{"key":"1660_CR21","doi-asserted-by":"crossref","unstructured":"Lu, S., Tsaknakis, I., Hong, M., Chen, Y.: Hybrid block successive approximation for one-sided non-convex min-max problems: algorithms and applications. arXiv preprint arXiv:1902.08294, (2019)","DOI":"10.1109\/TSP.2020.2986363"},{"issue":"1","key":"1660_CR22","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0167-6377(87)90007-1","volume":"6","author":"P Marcotte","year":"1987","unstructured":"Marcotte, P., Dussault, J.-P.: A note on a globally convergent newton method for solving monotone variational inequalities. Oper. Res. Lett. 6(1), 35\u201342 (1987)","journal-title":"Oper. Res. Lett."},{"key":"1660_CR23","unstructured":"Mokhtari, A., Ozdaglar, A., Pattathil, S.: A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv preprint arXiv:1901.08511, (2019)"},{"issue":"1","key":"1660_CR24","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","volume":"15","author":"A Nemirovski","year":"2004","unstructured":"Nemirovski, A.: Prox-method with rate of convergence $$o(1\/t)$$ for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229\u2013251 (2004)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1660_CR25","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0885-064X(92)90013-2","volume":"8","author":"A Nemirovsky","year":"1992","unstructured":"Nemirovsky, A.: Information-based complexity of linear operator equations. J. Complex. 8(2), 153\u2013175 (1992)","journal-title":"J. Complex."},{"key":"1660_CR26","unstructured":"Nemirovsky, A., Yudin, D.B.: Problem complexity and method efficiency in optimization. (1983)"},{"key":"1660_CR27","unstructured":"Nesterov. Yu.: Implementable tensor methods in unconstrained convex optimization. CORE Discussion Paper, 2018\/05"},{"issue":"2\u20133","key":"1660_CR28","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-006-0034-z","volume":"109","author":"Yu Nesterov","year":"2007","unstructured":"Nesterov, Yu.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Progr. 109(2\u20133), 319\u2013344 (2007)","journal-title":"Math. Progr."},{"key":"1660_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91578-4","volume-title":"Lectures on convex optimization","author":"Yu Nesterov","year":"2018","unstructured":"Nesterov, Yu.: Lectures on convex optimization, vol. 137. Springer, Cham (2018)"},{"key":"1660_CR30","doi-asserted-by":"crossref","unstructured":"Yu. Nesterov and L.\u00a0Scrimali. Solving strongly monotone variational and quasi-variational inequalities. Available at SSRN 970903, 2006","DOI":"10.2139\/ssrn.970903"},{"key":"1660_CR31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic game theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.: Algorithmic game theory. Cambridge University Press, Cambridge (2007)"},{"issue":"1","key":"1660_CR32","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1137\/14095697X","volume":"8","author":"Y Ouyang","year":"2015","unstructured":"Ouyang, Y., Chen, Y., Lan, G., Pasiliao Jr., E.: An accelerated linearized alternating direction method of multipliers. SIAM J. Imaging Sci. 8(1), 644\u2013681 (2015)","journal-title":"SIAM J. Imaging Sci."},{"key":"1660_CR33","doi-asserted-by":"crossref","unstructured":"Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. arXiv preprint arXiv:1808.02901, (2018)","DOI":"10.1007\/s10107-019-01420-0"},{"key":"1660_CR34","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex analysis. Princeton University Press, Princeton (1970)"},{"key":"1660_CR35","unstructured":"Sanjabi, M., Razaviyayn, M., Lee, J.D.: Solving non-convex non-concave min-max games under Polyak-Lojasiewicz condition. arXiv preprint arXiv:1812.02878, (2018)"},{"issue":"1\u20133","key":"1660_CR36","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/BF01581276","volume":"58","author":"K Taji","year":"1993","unstructured":"Taji, K., Fukushima, M., Ibaraki, T.: A globally convergent newton method for solving strongly monotone variational inequalities. Math. Progr. 58(1\u20133), 369\u2013383 (1993)","journal-title":"Math. Progr."},{"key":"1660_CR37","volume-title":"Theory of games and economic behavior (commemorative edition)","author":"J von Neumann","year":"2007","unstructured":"von Neumann, J., Morgenstern, O., Kuhn, H.W.: Theory of games and economic behavior (commemorative edition). Princeton University Press, Princeton (2007)"},{"key":"1660_CR38","unstructured":"Wang, Y., Li, J.: Improved algorithms for convex-concave minimax optimization. arXiv preprint arXiv:2006.06359, (2020)"},{"issue":"43","key":"1660_CR39","first-page":"1","volume":"20","author":"L Xiao","year":"2019","unstructured":"Xiao, L., Yu, A., Lin, Q., Chen, W.: DSCOVR: randomized primal-dual block coordinate algorithms for asynchronous distributed optimization. J. Mach. Learn. Res. 20(43), 1\u201358 (2019)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"1660_CR40","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1137\/16M1082305","volume":"27","author":"Y Xu","year":"2017","unstructured":"Xu, Y.: Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3), 1459\u20131484 (2017)","journal-title":"SIAM J. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01660-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01660-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01660-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T15:13:19Z","timestamp":1656342799000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01660-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,7]]},"references-count":40,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1660"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01660-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,7]]},"assertion":[{"value":"13 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}