{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,27]],"date-time":"2026-07-27T16:39:44Z","timestamp":1785170384101,"version":"3.55.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1553086"],"award-info":[{"award-number":["1553086"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,11]]},"DOI":"10.1007\/s10107-019-01406-y","type":"journal-article","created":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T05:02:38Z","timestamp":1559883758000},"page":"71-120","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":69,"title":["Lower bounds for finding stationary points I"],"prefix":"10.1007","volume":"184","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5731-8640","authenticated-orcid":false,"given":"Yair","family":"Carmon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John C.","family":"Duchi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Oliver","family":"Hinder","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Sidford","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"issue":"5","key":"1406_CR1","doi-asserted-by":"crossref","first-page":"3235","DOI":"10.1109\/TIT.2011.2182178","volume":"58","author":"A Agarwal","year":"2012","unstructured":"Agarwal, A., Bartlett, P.L., Ravikumar, P., Wainwright, M.J.: Information-theoretic lower bounds on the oracle complexity of convex optimization. IEEE Trans. Inf. Theory 58(5), 3235\u20133249 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1406_CR2","doi-asserted-by":"crossref","unstructured":"Agarwal, N., Allen-Zhu, Z., Bullins, B., Hazan, E., Ma, T.: Finding approximate local minima faster than gradient descent. In: Proceedings of the Forty-Ninth Annual ACM Symposium on the Theory of Computing (2017)","DOI":"10.1145\/3055399.3055464"},{"issue":"126","key":"1406_CR3","first-page":"1","volume":"17","author":"Y Arjevani","year":"2016","unstructured":"Arjevani, Y., Shalev-Shwartz, S., Shamir, O.: On lower and upper bounds in smooth and strongly convex optimization. J. Mach. Learn. Res. 17(126), 1\u201351 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"1406_CR4","unstructured":"Arjevani, Y., Shamir, O., Shiff, R.: Oracle complexity of second-order methods for smooth convex optimization (2017). \narXiv:1705.07260\n\n [math.OC]"},{"key":"1406_CR5","first-page":"1","volume-title":"Flavors of Geometry","author":"K Ball","year":"1997","unstructured":"Ball, K.: An elementary introduction to modern convex geometry. In: Levy, S. (ed.) Flavors of Geometry, pp. 1\u201358. MSRI Publications, Cambridge (1997)"},{"issue":"2","key":"1406_CR6","first-page":"185","volume":"30","author":"D Berend","year":"2010","unstructured":"Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Prob. Math. Stat. 30(2), 185\u2013205 (2010)","journal-title":"Prob. Math. Stat."},{"issue":"1\u20132","key":"1406_CR7","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s10107-016-1065-8","volume":"163","author":"EG Birgin","year":"2017","unstructured":"Birgin, E.G., Gardenghi, J.L., Mart\u00ednez, J.M., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Program. 163(1\u20132), 359\u2013368 (2017)","journal-title":"Math. Program."},{"key":"1406_CR8","first-page":"2757","volume":"30","author":"N Boumal","year":"2016","unstructured":"Boumal, N., Voroninski, V., Bandeira, A.: The non-convex Burer\u2013Monteiro approach works on smooth semidefinite programs. Adv. Neural Inf. Process. Syst. 30, 2757\u20132765 (2016)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1406_CR9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"issue":"7","key":"1406_CR10","doi-asserted-by":"crossref","first-page":"4709","DOI":"10.1109\/TIT.2017.2701343","volume":"63","author":"G Braun","year":"2017","unstructured":"Braun, G., Guzm\u00e1n, C., Pokutta, S.: Lower bounds on the oracle complexity of nonsmooth convex optimization via information theory. IEEE Trans. Inf. Theory 63(7), 4709\u20134724 (2017)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"1406_CR11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"4","key":"1406_CR12","doi-asserted-by":"crossref","first-page":"1985","DOI":"10.1109\/TIT.2015.2399924","volume":"61","author":"EJ Cand\u00e8s","year":"2015","unstructured":"Cand\u00e8s, E.J., Li, X., Soltanolkotabi, M.: Phase retrieval via Wirtinger flow: theory and algorithms. IEEE Trans. Inf. Theory 61(4), 1985\u20132007 (2015)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1406_CR13","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Convex until proven guilty: dimension-free acceleration of gradient descent on non-convex functions. In: Proceedings of the 34th International Conference on Machine Learning (2017)"},{"key":"1406_CR14","unstructured":"Carmon, Y., Duchi, J.\u00a0C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points II: first-order methods (2017). \narXiv: 1711.00841\n\n [math.OC]. URL \nhttps:\/\/arxiv.org\/pdf\/1711.00841.pdf"},{"issue":"2","key":"1406_CR15","doi-asserted-by":"crossref","first-page":"1751","DOI":"10.1137\/17M1114296","volume":"28","author":"Y Carmon","year":"2018","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Accelerated methods for non-convex optimization. SIAM J. Optim. 28(2), 1751\u20131772 (2018)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"1406_CR16","doi-asserted-by":"crossref","first-page":"2833","DOI":"10.1137\/090774100","volume":"20","author":"C Cartis","year":"2010","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: On the complexity of steepest descent, Newton\u2019s and regularized Newton\u2019s methods for nonconvex unconstrained optimization problems. SIAM J. Optim. 20(6), 2833\u20132852 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1406_CR17","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/j.jco.2011.06.001","volume":"28","author":"C Cartis","year":"2012","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Complexity bounds for second-order optimality in unconstrained optimization. J. Complex. 28(1), 93\u2013108 (2012)","journal-title":"J. Complex."},{"key":"1406_CR18","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: How much patience do you have? A worst-case perspective on smooth nonconvex optimization. Optima 88, 1\u201310 (2012)"},{"key":"1406_CR19","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1080\/10556788.2012.722632","volume":"28","author":"C Cartis","year":"2013","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: A note about the complexity of minimizing nesterov\u2019s smooth Chebyshev\u2013Rosenbrock function. Optim. Methods Softw. 28, 451\u2013457 (2013)","journal-title":"Optim. Methods Softw."},{"key":"1406_CR20","unstructured":"Cartis, C., Gould, N.I.M., Toint, P.L.: Worst-case evaluation complexity and optimality of second-order methods for nonconvex smooth optimization (2017). \narXiv:1709.07180\n\n [math.OC]"},{"key":"1406_CR21","doi-asserted-by":"crossref","first-page":"328","DOI":"10.4153\/CJM-1951-038-3","volume":"3","author":"S Chowla","year":"1951","unstructured":"Chowla, S., Herstein, I.N., Moore, W.K.: On recursions connected with symmetric groups I. Can. J. Math. 3, 328\u2013334 (1951)","journal-title":"Can. J. Math."},{"key":"1406_CR22","series-title":"MPS-SIAM Series on Optimization","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719857","volume-title":"Trust Region Methods","author":"AR Conn","year":"2000","unstructured":"Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. MPS-SIAM Series on Optimization. SIAM, Bangkok (2000)"},{"issue":"1","key":"1406_CR23","first-page":"35","volume":"2","author":"WW Hager","year":"2006","unstructured":"Hager, W.W., Zhang, H.: A survey of nonlinear conjugate gradient methods. Pac. J. Optim. 2(1), 35\u201358 (2006)","journal-title":"Pac. J. Optim."},{"key":"1406_CR24","unstructured":"Hinder, O.: Cutting plane methods can be extended into nonconvex optimization. In: Proceedings of the Thirty First Annual Conference on Computational Learning Theory (2018)"},{"issue":"3","key":"1406_CR25","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1080\/10556788.2011.638924","volume":"28","author":"F Jarre","year":"2013","unstructured":"Jarre, F.: On Nesterov\u2019s smooth Chebyshev\u2013Rosenbrock function. Optim. Methods Softw. 28(3), 478\u2013500 (2013)","journal-title":"Optim. Methods Softw."},{"key":"1406_CR26","unstructured":"Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.I.: How to escape saddle points efficiently. In: Proceedings of the 34th International Conference on Machine Learning (2017)"},{"key":"1406_CR27","first-page":"2057","volume":"11","author":"RH Keshavan","year":"2010","unstructured":"Keshavan, R.H., Montanari, A., Oh, S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 11, 2057\u20132078 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"7553","key":"1406_CR28","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1038\/nature14539","volume":"521","author":"Y LeCun","year":"2015","unstructured":"LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521(7553), 436\u2013444 (2015)","journal-title":"Nature"},{"issue":"1","key":"1406_CR29","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01589116","volume":"45","author":"D Liu","year":"1989","unstructured":"Liu, D., Nocedal, J.: On the limited memory BFGS method for large scale optimization. Math. Program. 45(1), 503\u2013528 (1989)","journal-title":"Math. Program."},{"issue":"3","key":"1406_CR30","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1214\/12-AOS1018","volume":"40","author":"P-L Loh","year":"2012","unstructured":"Loh, P.-L., Wainwright, M.J.: High-dimensional regression with noisy and missing data: provable guarantees with nonconvexity. Ann. Stat. 40(3), 1637\u20131664 (2012)","journal-title":"Ann. Stat."},{"key":"1406_CR31","first-page":"559","volume":"16","author":"P-L Loh","year":"2013","unstructured":"Loh, P.-L., Wainwright, M.J.: Regularized M-estimators with nonconvexity: statistical and algorithmic theory for local optima. J. Mach. Learn. Res. 16, 559\u2013616 (2013)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"1406_CR32","doi-asserted-by":"crossref","first-page":"1092","DOI":"10.1137\/110833786","volume":"23","author":"RD Monteiro","year":"2013","unstructured":"Monteiro, R.D., Svaiter, B.F.: An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23(2), 1092\u20131125 (2013)","journal-title":"SIAM J. Optim."},{"key":"1406_CR33","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/BF02592948","volume":"39","author":"K Murty","year":"1987","unstructured":"Murty, K., Kabadi, S.: Some NP-complete problems in quadratic and nonlinear programming. Math. Program. 39, 117\u2013129 (1987)","journal-title":"Math. Program."},{"key":"1406_CR34","unstructured":"Nemirovski, A.: Efficient methods in convex programming. The Israel Institute of Technology, Technion (1994)"},{"key":"1406_CR35","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, Hoboken (1983)"},{"issue":"2","key":"1406_CR36","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $${O}(1\/k^2)$$. Sov. Math. Dokl. 27(2), 372\u2013376 (1983)","journal-title":"Sov. Math. Dokl."},{"key":"1406_CR37","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8853-9","volume-title":"Introductory Lectures on Convex Optimization","author":"Y Nesterov","year":"2004","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization. Kluwer Academic Publishers, Cambridge (2004)"},{"issue":"2","key":"1406_CR38","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/100802001","volume":"22","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2), 341\u2013362 (2012)","journal-title":"SIAM J. Optim."},{"key":"1406_CR39","first-page":"10","volume":"88","author":"Y Nesterov","year":"2012","unstructured":"Nesterov, Y.: How to make the gradients small. Optima 88, 10\u201311 (2012)","journal-title":"Optima"},{"key":"1406_CR40","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s10107-006-0706-8","volume":"108","author":"Y Nesterov","year":"2006","unstructured":"Nesterov, Y., Polyak, B.: Cubic regularization of Newton method and its global performance. Math. Program. Ser. A 108, 177\u2013205 (2006)","journal-title":"Math. Program. Ser. A"},{"key":"1406_CR41","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, Berlin (2006)"},{"issue":"5","key":"1406_CR42","doi-asserted-by":"crossref","first-page":"1131","DOI":"10.1007\/s10208-017-9365-9","volume":"18","author":"J Sun","year":"2018","unstructured":"Sun, J., Qu, Q., Wright, J.: A geometric analysis of phase retrieval. Found. Comput. Math. 18(5), 1131\u20131198 (2018)","journal-title":"Found. Comput. Math."},{"key":"1406_CR43","volume-title":"Information-Based Complexity","author":"J Traub","year":"1988","unstructured":"Traub, J., Wasilkowski, H., Wozniakowski, H.: Information-Based Complexity. Academic Press, Cambridge (1988)"},{"issue":"1","key":"1406_CR44","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/0803004","volume":"3","author":"SA Vavasis","year":"1993","unstructured":"Vavasis, S.A.: Black-box complexity of local minimization. SIAM J. Optim. 3(1), 60\u201380 (1993)","journal-title":"SIAM J. Optim."},{"key":"1406_CR45","first-page":"3639","volume":"30","author":"BE Woodworth","year":"2016","unstructured":"Woodworth, B.E., Srebro, N.: Tight complexity bounds for optimizing composite objectives. Adv. Neural Inf. Process. Syst. 30, 3639\u20133647 (2016)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1406_CR46","unstructured":"Woodworth, B.\u00a0E., Srebro, N.: Lower bound for randomized first order convex optimization (2017). \narXiv:1709.03594\n\n [math.OC]"},{"issue":"3","key":"1406_CR47","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1137\/110835335","volume":"33","author":"X Zhang","year":"2012","unstructured":"Zhang, X., Ling, C., Qi, L.: The best rank-1 approximation of a symmetric tensor and related spherical optimization problems. SIAM J. Matrix Anal. Appl. 33(3), 806\u2013821 (2012)","journal-title":"SIAM J. Matrix Anal. Appl."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01406-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01406-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01406-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,15]],"date-time":"2020-10-15T10:49:32Z","timestamp":1602758972000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01406-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":47,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["1406"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01406-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"13 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}