{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T18:03:10Z","timestamp":1784224990671,"version":"3.55.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,5,28]],"date-time":"2018-05-28T00:00:00Z","timestamp":1527465600000},"content-version":"tdm","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":[[2019,11]]},"DOI":"10.1007\/s10107-018-1293-1","type":"journal-article","created":{"date-parts":[[2018,5,28]],"date-time":"2018-05-28T09:11:28Z","timestamp":1527498688000},"page":"327-360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":34,"title":["Oracle complexity of second-order methods for smooth convex optimization"],"prefix":"10.1007","volume":"178","author":[{"given":"Yossi","family":"Arjevani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Shamir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2502-8160","authenticated-orcid":false,"given":"Ron","family":"Shiff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,5,28]]},"reference":[{"key":"1293_CR1","unstructured":"Agarwal, N., Hazan, E.: Lower bounds for higher-order optimization. Working draft (2017)"},{"key":"1293_CR2","unstructured":"Allen-Zhu, Z., Hazan, E.: Optimal black-box reductions between optimization objectives. In: Advances in Neural Information Processing Systems, pp. 1614\u20131622 (2016)"},{"key":"1293_CR3","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)"},{"key":"1293_CR4","unstructured":"Arjevani, Y., Shamir, O.: Oracle complexity of second-order methods for finite-sum problems. arXiv preprint \n                    arXiv:1611.04982\n                    \n                   (2016)"},{"key":"1293_CR5","volume-title":"Estimate Sequence Methods: Extensions and Approximations","author":"M Baes","year":"2009","unstructured":"Baes, M.: Estimate Sequence Methods: Extensions and Approximations. Institute for Operations Research, ETH, Z\u00fcrich (2009)"},{"key":"1293_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":"6","key":"1293_CR7","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":"2","key":"1293_CR8","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1080\/10556788.2011.602076","volume":"27","author":"C Cartis","year":"2012","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization. Optim Methods Softw. 27(2), 197\u2013219 (2012)","journal-title":"Optim Methods Softw."},{"issue":"6","key":"1293_CR9","first-page":"89","volume":"3","author":"LV Kantorovich","year":"1948","unstructured":"Kantorovich, L.V.: Functional analysis and applied mathematics. Uspekhi Matematicheskikh Nauk 3(6), 89\u2013185 (1948)","journal-title":"Uspekhi Matematicheskikh Nauk"},{"issue":"2","key":"1293_CR10","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."},{"issue":"4","key":"1293_CR11","doi-asserted-by":"publisher","first-page":"1638","DOI":"10.1137\/15M1010890","volume":"36","author":"C Mu","year":"2015","unstructured":"Mu, C., Hsu, D., Goldfarb, D.: Successive rank-one approximations for nearly orthogonally decomposable symmetric tensors. SIAM J. Matrix Anal. Appl. 36(4), 1638\u20131659 (2015)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1293_CR12","unstructured":"Nemirovski, A.: Efficient methods in convex programming\u2014lecture notes (2005)"},{"key":"1293_CR13","volume-title":"Problem Complexity and Method Efficiency in Optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.: Problem Complexity and Method Efficiency in Optimization. Wiley, New York (1983)"},{"issue":"2","key":"1293_CR14","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate \n                    \n                      \n                    \n                    $$O(1\/k^2)$$\n                    \n                      \n                        \n                          O\n                          (\n                          1\n                          \/\n                          \n                            k\n                            2\n                          \n                          )\n                        \n                      \n                    \n                  . Sov. Math. Dokl. 27(2), 372\u2013376 (1983)","journal-title":"Sov. Math. Dokl."},{"key":"1293_CR15","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, vol. 87. Springer, Berlin (2004)"},{"issue":"1","key":"1293_CR16","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s10107-006-0089-x","volume":"112","author":"Y Nesterov","year":"2008","unstructured":"Nesterov, Y.: Accelerating the cubic regularization of newton method on convex problems. Math. Program. 112(1), 159\u2013181 (2008)","journal-title":"Math. Program."},{"key":"1293_CR17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior-Point Polynomial Algorithms in Convex Programming","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)"},{"issue":"1","key":"1293_CR18","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.T.: Cubic regularization of newton method and its global performance. Math. Program. 108(1), 177\u2013205 (2006)","journal-title":"Math. Program."},{"key":"1293_CR19","first-page":"12","volume":"3","author":"A Vladimirov","year":"1978","unstructured":"Vladimirov, A., Nesterov, Y.E., Chekanov, Y.N.: On uniformly convex functionals. Vestnik Moskov. Univ. Ser. XV Vychisl. Mat. Kibernet 3, 12\u201323 (1978)","journal-title":"Vestnik Moskov. Univ. Ser. XV Vychisl. Mat. Kibernet"},{"key":"1293_CR20","unstructured":"Woodworth, B., Srebro, N.: Lower bound for randomized first order convex optimization. arXiv preprint \n                    arXiv:1709.03594\n                    \n                   (2017)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1293-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1293-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1293-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,18]],"date-time":"2019-10-18T10:32:40Z","timestamp":1571394760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1293-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5,28]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["1293"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1293-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,5,28]]},"assertion":[{"value":"12 September 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}