{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:33:27Z","timestamp":1780346007388,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"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"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1844855"],"award-info":[{"award-number":["CCF-1844855"]}],"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":[[2021,1]]},"DOI":"10.1007\/s10107-019-01431-x","type":"journal-article","created":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T14:11:51Z","timestamp":1568988711000},"page":"315-355","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Lower bounds for finding stationary points II: first-order methods"],"prefix":"10.1007","volume":"185","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,9,20]]},"reference":[{"key":"1431_CR1","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"},{"key":"1431_CR2","unstructured":"Allen-Zhu, Z.: Natasha 2: Faster non-convex optimization than SGD (2017). arXiv:1708.08694 [math.OC]"},{"key":"1431_CR3","unstructured":"Allen-Zhu, Z., Hazan, E.: Variance reduction for faster non-convex optimization. In: Proceedings of the 33rd International Conference on Machine Learning (2016)"},{"key":"1431_CR4","unstructured":"Arjevani, Y., Shamir, O., Shiff, R.: Oracle complexity of second-order methods for smooth convex optimization (2017). arXiv:1705.07260 [math.OC]"},{"issue":"1\u20132","key":"1431_CR5","doi-asserted-by":"publisher","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":"1431_CR6","doi-asserted-by":"publisher","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":"1","key":"1431_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011)","journal-title":"Found. Trends Mach. Learn."},{"key":"1431_CR8","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)"},{"issue":"2","key":"1431_CR9","doi-asserted-by":"publisher","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."},{"key":"1431_CR10","doi-asserted-by":"publisher","unstructured":"Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. Math. Program (to Appear) (2019). https:\/\/doi.org\/10.1007\/s10107-019-01406-y","DOI":"10.1007\/s10107-019-01406-y"},{"issue":"6","key":"1431_CR11","doi-asserted-by":"publisher","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":"1431_CR12","doi-asserted-by":"publisher","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":"1431_CR13","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 (2012)"},{"key":"1431_CR14","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). arXiv:1709.07180 [math.OC]"},{"key":"1431_CR15","doi-asserted-by":"publisher","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":"1431_CR16","unstructured":"Chung, F.R.K.: Spectral Graph Theory. AMS (1998)"},{"key":"1431_CR17","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":"1431_CR18","doi-asserted-by":"publisher","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":"1431_CR19","unstructured":"Jin, C., Ge, R., Netrapalli, P., Kakade, S.M., Jordan, M.\u00a0I.: How to escape saddle points efficiently. In: Proceedings of the 34th International Conference on Machine Learning (2017)"},{"key":"1431_CR20","unstructured":"Lei, L., Ju, C., Chen, J., Jordan, M.\u00a0I.: Nonconvex finite-sum optimization via SCSG methods. In: Advances in Neural Information Processing Systems, vol. 31 (2017)"},{"issue":"2","key":"1431_CR21","doi-asserted-by":"publisher","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":"1431_CR22","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)"},{"key":"1431_CR23","doi-asserted-by":"publisher","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, Dordrecht (2004)"},{"key":"1431_CR24","unstructured":"Nesterov, Y.: How to make the gradients small. Optima 88 (2012)"},{"key":"1431_CR25","doi-asserted-by":"publisher","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":"1431_CR26","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Hefny, A., Sra, S., Poczos, B., Smola, A.: Stochastic variance reduction for nonconvex optimization. In: Proceedings of the 33rd International Conference on Machine Learning (2016)","DOI":"10.1109\/ALLERTON.2016.7852377"},{"key":"1431_CR27","unstructured":"Simchowitz, M.: On the randomized complexity of minimizing a convex quadratic function (2018). arXiv:1807.09386 [cs.LG]"},{"key":"1431_CR28","doi-asserted-by":"crossref","unstructured":"Simchowitz, M., Aloui, A.E., Recht, B.: Tight query complexity lower bounds for PCA via finite sample deformed Wigner law. In: Proceedings of the Fiftieth Annual ACM Symposium on the Theory of Computing (2018)","DOI":"10.1145\/3188745.3188796"},{"issue":"1","key":"1431_CR29","doi-asserted-by":"publisher","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":"1431_CR30","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."},{"issue":"3","key":"1431_CR31","doi-asserted-by":"publisher","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-01431-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01431-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01431-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T04:51:08Z","timestamp":1664427068000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01431-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,20]]},"references-count":31,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["1431"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01431-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,20]]},"assertion":[{"value":"13 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}