{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T04:22:35Z","timestamp":1773894155448,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:00:00Z","timestamp":1565136000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:00:00Z","timestamp":1565136000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s10107-019-01420-0","type":"journal-article","created":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T16:03:27Z","timestamp":1565193807000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":61,"title":["Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems"],"prefix":"10.1007","volume":"185","author":[{"given":"Yuyuan","family":"Ouyang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4163-3723","authenticated-orcid":false,"given":"Yangyang","family":"Xu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,7]]},"reference":[{"key":"1420_CR1","unstructured":"Arjevani, Y., Shamir, O.: Dimension-free iteration complexity of finite sum optimization problems. In: Advances in Neural Information Processing Systems, pp. 3540\u20133548. (2016)"},{"key":"1420_CR2","unstructured":"Arjevani, Y., Shamir, O.: On the iteration complexity of oblivious first-order optimization algorithms. In: International Conference on Machine Learning, pp. 908\u2013916. (2016)"},{"issue":"1","key":"1420_CR3","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1420_CR4","unstructured":"Carmon Y, Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. (2017) arXiv preprint arXiv:1710.11606"},{"key":"1420_CR5","unstructured":"Carmon Y, Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points II: First-order methods. (2017) arXiv preprint arXiv:1711.00841"},{"issue":"1","key":"1420_CR6","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":"4","key":"1420_CR7","doi-asserted-by":"publisher","first-page":"1779","DOI":"10.1137\/130919362","volume":"24","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779\u20131814 (2014)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1420_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10107-017-1161-4","volume":"165","author":"Y Chen","year":"2017","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Accelerated schemes for a class of variational inequalities. Math. Program. 165(1), 113\u2013149 (2017)","journal-title":"Math. Program."},{"issue":"2","key":"1420_CR9","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s10957-012-0245-9","volume":"158","author":"L Condat","year":"2013","unstructured":"Condat, L.: A primal-dual splitting method for convex optimization involving lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460\u2013479 (2013)","journal-title":"J. Optim. Theory Appl."},{"issue":"1\u20132","key":"1420_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s10107-013-0677-5","volume":"146","author":"O Devolder","year":"2014","unstructured":"Devolder, O., Glineur, F., Nesterov, Y.: First-order methods of smooth convex optimization with inexact oracle. Math. Program. 146(1\u20132), 37\u201375 (2014)","journal-title":"Math. Program."},{"issue":"4","key":"1420_CR11","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1137\/09076934X","volume":"3","author":"E Esser","year":"2010","unstructured":"Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015\u20131046 (2010)","journal-title":"SIAM J. Imaging Sci."},{"issue":"2","key":"1420_CR12","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s40305-018-0232-4","volume":"7","author":"X Gao","year":"2019","unstructured":"Gao, X., Xu, Y., Zhang, S.: Randomized primal-dual proximal block coordinate updates. J. Oper. Res. Soc. China 7(2), 205\u2013250 (2019)","journal-title":"J. Oper. Res. Soc. China"},{"issue":"2","key":"1420_CR13","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.-Z.: 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"},{"issue":"3","key":"1420_CR14","doi-asserted-by":"publisher","first-page":"1588","DOI":"10.1137\/120896219","volume":"7","author":"T Goldstein","year":"2014","unstructured":"Goldstein, T., O\u2019Donoghue, B., Setzer, S., Baraniuk, R.: Fast alternating direction optimization methods. SIAM J. Imaging Sci. 7(3), 1588\u20131623 (2014)","journal-title":"SIAM J. Imaging Sci."},{"issue":"1","key":"1420_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jco.2014.08.003","volume":"31","author":"C Guzm\u00e1n","year":"2015","unstructured":"Guzm\u00e1n, C., Nemirovski, A.: On lower complexity bounds for large-scale smooth convex optimization. J. Complexity 31(1), 1\u201314 (2015)","journal-title":"J. Complexity"},{"key":"1420_CR16","unstructured":"Hamedani, E.Y., Aybat, N.S.: A primal-dual algorithm for general convex-concave saddle point problems. (2018) arXiv preprint arXiv:1803.01401"},{"issue":"2","key":"1420_CR17","doi-asserted-by":"publisher","first-page":"700","DOI":"10.1137\/110836936","volume":"50","author":"B He","year":"2012","unstructured":"He, B., Yuan, X.: On the $${O}(1\/n)$$ convergence rate of the douglas-rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700\u2013709 (2012)","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"1420_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1137\/14096757X","volume":"26","author":"Y He","year":"2016","unstructured":"He, Y., Monteiro, R.D.: An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems. SIAM J. Optim. 26(1), 29\u201356 (2016)","journal-title":"SIAM J. Optim."},{"key":"1420_CR19","unstructured":"Jaggi, M.: Revisiting frank-wolfe: Projection-free sparse convex optimization. In: ICML, vol. 1, pp. 427\u2013435. (2013)"},{"issue":"1","key":"1420_CR20","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1287\/10-SSY010","volume":"4","author":"A Juditsky","year":"2014","unstructured":"Juditsky, A., Nesterov, Y.: Deterministic and stochastic primal-dual subgradient algorithms for uniformly convex minimization. Stoch. Syst. 4(1), 44\u201380 (2014)","journal-title":"Stoch. Syst."},{"key":"1420_CR21","unstructured":"Lan, G.: The complexity of large-scale convex programming under a linear optimization oracle. (2013) arXiv preprint arXiv:1309.5550"},{"issue":"1\u20132","key":"1420_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s10107-015-0955-5","volume":"159","author":"G Lan","year":"2016","unstructured":"Lan, G.: Gradient sliding for composite optimization. Math. Program. 159(1\u20132), 201\u2013235 (2016)","journal-title":"Math. Program."},{"key":"1420_CR23","unstructured":"Lan, G., Ouyang, Y.: Accelerated gradient sliding for structured convex optimization. (2016) arXiv preprint arXiv:1609.04905"},{"issue":"1\u20132","key":"1420_CR24","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-015-0861-x","volume":"155","author":"G Lan","year":"2016","unstructured":"Lan, G., Renato, D., Monteiro, C.: Iteration-complexity of first-order augmented lagrangian methods for convex programming. Math. Program. 155(1\u20132), 511\u2013547 (2016)","journal-title":"Math. Program."},{"issue":"2","key":"1420_CR25","doi-asserted-by":"publisher","first-page":"1379","DOI":"10.1137\/140992382","volume":"26","author":"G Lan","year":"2016","unstructured":"Lan, G., Zhou, Y.: Conditional gradient sliding for convex optimization. SIAM J. Optim. 26(2), 1379\u20131409 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1420_CR26","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10107-017-1173-0","volume":"171","author":"G Lan","year":"2018","unstructured":"Lan, G., Zhou, Y.: An optimal randomized incremental gradient method. Math. Program. 171(1\u20132), 167\u2013215 (2018)","journal-title":"Math. Program."},{"issue":"4","key":"1420_CR27","doi-asserted-by":"publisher","first-page":"1688","DOI":"10.1137\/100801652","volume":"21","author":"RD Monteiro","year":"2011","unstructured":"Monteiro, R.D., Svaiter, B.F.: Complexity of variants of Tseng\u2019s modified F-B splitting and Korpelevich\u2019s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems. SIAM J. Optim. 21(4), 1688\u20131720 (2011)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1420_CR28","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1137\/110849468","volume":"23","author":"RD Monteiro","year":"2013","unstructured":"Monteiro, R.D., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475\u2013507 (2013)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1420_CR29","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":"4","key":"1420_CR30","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"1420_CR31","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovski","year":"1983","unstructured":"Nemirovski, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience Series in Discrete Mathematics, Wiley, New York (1983)"},{"issue":"2","key":"1420_CR32","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0885-064X(92)90013-2","volume":"8","author":"AS Nemirovski","year":"1992","unstructured":"Nemirovski, A.S.: Information-based complexity of linear operator equations. J. Complexity 8(2), 153\u2013175 (1992)","journal-title":"J. Complexity"},{"issue":"2","key":"1420_CR33","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0885-064X(91)90001-E","volume":"7","author":"A Nemirovsky","year":"1991","unstructured":"Nemirovsky, A.: On optimality of krylov\u2019s information when solving linear operator equations. J. Complexity 7(2), 121\u2013130 (1991)","journal-title":"J. Complexity"},{"key":"1420_CR34","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publisher, Dordrecht (2004)"},{"issue":"1","key":"1420_CR35","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"1420_CR36","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10107-012-0629-5","volume":"140","author":"Y Nesterov","year":"2013","unstructured":"Nesterov, Y.: Gradient methods for minimizing composite functions. Math. Program. 140(1), 125\u2013161 (2013)","journal-title":"Math. Program."},{"issue":"1","key":"1420_CR37","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":"1420_CR38","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"2015","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (2015)"},{"key":"1420_CR39","unstructured":"Simchowitz, M.: On the randomized complexity of minimizing a convex quadratic function. (2018) arXiv preprint arXiv:1807.09386"},{"key":"1420_CR40","unstructured":"Woodworth, B.E., Srebro, N.: Tight complexity bounds for optimizing composite objectives. In: Advances in Neural Information Processing Systems, pp. 3639\u20133647. (2016)"},{"issue":"3","key":"1420_CR41","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."},{"key":"1420_CR42","unstructured":"Xu, Y.: Iteration complexity of inexact augmented lagrangian methods for constrained convex programming. (2017) arXiv preprint arXiv:1711.05812"},{"issue":"1","key":"1420_CR43","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/s10589-017-9972-z","volume":"70","author":"Y Xu","year":"2018","unstructured":"Xu, Y., Zhang, S.: Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70(1), 91\u2013128 (2018)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"1420_CR44","doi-asserted-by":"publisher","first-page":"1698","DOI":"10.1007\/s10915-018-0680-3","volume":"76","author":"M Yan","year":"2018","unstructured":"Yan, M.: A new primal-dual algorithm for minimizing the sum of three functions with a linear operator. J. Sci. Comput. 76(3), 1698\u20131717 (2018)","journal-title":"J. Sci. Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01420-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01420-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01420-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,18]],"date-time":"2021-01-18T15:49:25Z","timestamp":1610984965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01420-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,7]]},"references-count":44,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["1420"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01420-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,7]]},"assertion":[{"value":"6 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}