{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T06:29:50Z","timestamp":1781332190413,"version":"3.54.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T00:00:00Z","timestamp":1616803200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,6]]},"DOI":"10.1007\/s10589-021-00274-7","type":"journal-article","created":{"date-parts":[[2021,3,27]],"date-time":"2021-03-27T10:02:38Z","timestamp":1616839358000},"page":"471-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["An accelerated first-order method with complexity analysis for solving cubic regularization subproblems"],"prefix":"10.1007","volume":"79","author":[{"given":"Rujun","family":"Jiang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7992-9490","authenticated-orcid":false,"given":"Man-Chung","family":"Yue","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhishuo","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,3,27]]},"reference":[{"key":"274_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 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 1195\u20131199. ACM (2017)","DOI":"10.1145\/3055399.3055464"},{"issue":"1","key":"274_CR2","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1093\/imanum\/8.1.141","volume":"8","author":"J Barzilai","year":"1988","unstructured":"Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141\u2013148 (1988)","journal-title":"IMA J. Numer. Anal."},{"issue":"1","key":"274_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\u2013thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imag. Sci."},{"issue":"1","key":"274_CR4","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/s10589-014-9672-x","volume":"60","author":"T Bianconcini","year":"2015","unstructured":"Bianconcini, T., Liuzzi, G., Morini, B., Sciandrone, M.: On the use of iterative methods in cubic regularization for unconstrained optimization. Comput. Optim. Appl. 60(1), 35\u201357 (2015)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"274_CR5","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/s10589-019-00089-7","volume":"73","author":"E Birgin","year":"2019","unstructured":"Birgin, E., Mart\u00ednez, J.: A Newton-like method with mixed factorizations and cubic regularization for unconstrained minimization. Comput. Optim. Appl. 73(3), 707\u2013753 (2019)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"274_CR6","doi-asserted-by":"publisher","first-page":"2146","DOI":"10.1137\/17M1113898","volume":"29","author":"Y Carmon","year":"2019","unstructured":"Carmon, Y., Duchi, J.: Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM J. Optim. 29(3), 2146\u20132178 (2019)","journal-title":"SIAM J. Optim."},{"key":"274_CR7","unstructured":"Carmon, Y., Duchi, J.C.: Analysis of Krylov subspace solutions of regularized non-convex quadratic problems. In: Advances in Neural Information Processing Systems, pp. 10705\u201310715 (2018)"},{"issue":"2","key":"274_CR8","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 nonconvex optimization. SIAM J. Optim. 28(2), 1751\u20131772 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"274_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10107-009-0286-5","volume":"127","author":"C Cartis","year":"2011","unstructured":"Cartis, C., Gould, N.I., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Progr. 127(2), 245\u2013295 (2011)","journal-title":"Math. Progr."},{"issue":"2","key":"274_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Progr. 91(2), 201\u2013213 (2002)","journal-title":"Math. Progr."},{"issue":"1","key":"274_CR11","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0377-2217(95)00199-9","volume":"94","author":"OE Flippo","year":"1996","unstructured":"Flippo, O.E., Jansen, B.: Duality and sensitivity in nonconvex quadratic optimization over an ellipsoid. Eur. J. Oper. Res. 94(1), 167\u2013178 (1996)","journal-title":"Eur. J. Oper. Res."},{"issue":"3","key":"274_CR12","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/s10589-017-9964-z","volume":"69","author":"H Ghanbari","year":"2018","unstructured":"Ghanbari, H., Scheinberg, K.: Proximal quasi-Newton methods for regularized convex optimization with linear and accelerated sublinear convergence rates. Comput. Optim. Appl. 69(3), 597\u2013627 (2018). https:\/\/doi.org\/10.1007\/s10589-017-9964-z","journal-title":"Comput. Optim. Appl."},{"key":"274_CR13","doi-asserted-by":"crossref","DOI":"10.56021\/9781421407944","volume-title":"Matrix Computations","author":"GH Golub","year":"2013","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. Johns Hopkins University Press, Baltimore (2013)","edition":"4"},{"issue":"3","key":"274_CR14","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s10589-014-9687-3","volume":"60","author":"NI Gould","year":"2015","unstructured":"Gould, N.I., Orban, D., Toint, P.L.: Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545\u2013557 (2015)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"274_CR15","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1137\/16M1065197","volume":"27","author":"N Ho-Nguyen","year":"2017","unstructured":"Ho-Nguyen, N., Kilinc-Karzan, F.: A second-order cone based approach for solving the trust-region subproblem and its variants. SIAM J. Optim. 27(3), 1485\u20131512 (2017)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"274_CR16","first-page":"510","volume":"18","author":"N Ito","year":"2017","unstructured":"Ito, N., Takeda, A., Toh, K.C.: A unified formulation and fast accelerated proximal gradient method for classification. J. Mach. Learn. Res. 18(1), 510\u2013558 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"274_CR17","doi-asserted-by":"publisher","first-page":"1603","DOI":"10.1137\/18M1174313","volume":"29","author":"R Jiang","year":"2019","unstructured":"Jiang, R., Li, D.: Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2), 1603\u20131633 (2019). https:\/\/doi.org\/10.1137\/18M1174313","journal-title":"SIAM J. Optim."},{"issue":"4","key":"274_CR18","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczy\u0144ski","year":"1992","unstructured":"Kuczy\u0144ski, J., Wo\u017aniakowski, H.: Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"274_CR19","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. Progr. 108(1), 177\u2013205 (2006)","journal-title":"Math. Progr."},{"issue":"2","key":"274_CR20","first-page":"372","volume":"27","author":"YE Nesterov","year":"1983","unstructured":"Nesterov, Y.E.: A method for solving the convex programming problem with convergence rate $${O}(1\/k^2)$$. Soviet Math. Doklady 27(2), 372\u2013376 (1983)","journal-title":"Soviet Math. Doklady"},{"issue":"3","key":"274_CR21","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10208-013-9150-3","volume":"15","author":"B O\u2019Donoghue","year":"2015","unstructured":"O\u2019Donoghue, B., Candes, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715\u2013732 (2015)","journal-title":"Found. Comput. Math."},{"issue":"2","key":"274_CR22","doi-asserted-by":"publisher","first-page":"1448","DOI":"10.1137\/17M1134329","volume":"28","author":"CW Royer","year":"2018","unstructured":"Royer, C.W., Wright, S.J.: Complexity analysis of second-order line\u2013search algorithms for smooth nonconvex optimization. SIAM J. Optim. 28(2), 1448\u20131477 (2018)","journal-title":"SIAM J. Optim."},{"issue":"6","key":"274_CR23","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1109\/JPROC.2010.2044010","volume":"98","author":"JA Tropp","year":"2010","unstructured":"Tropp, J.A., Wright, S.J.: Computational methods for sparse solution of linear inverse problems. Proc. IEEE 98(6), 948\u2013958 (2010)","journal-title":"Proc. IEEE"},{"issue":"8","key":"274_CR24","doi-asserted-by":"publisher","first-page":"1639","DOI":"10.1007\/s11590-016-1070-0","volume":"11","author":"J Wang","year":"2017","unstructured":"Wang, J., Xia, Y.: A linear-time algorithm for the trust region subproblem based on hidden convexity. Optim. Lett. 11(8), 1639\u20131646 (2017)","journal-title":"Optim. Lett."},{"issue":"1","key":"274_CR25","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/18M1167498","volume":"29","author":"MC Yue","year":"2019","unstructured":"Yue, M.C., Zhou, Z., Man-Cho So, A.: On the quadratic convergence of the cubic regularization method under a local error bound condition. SIAM J. Optim. 29(1), 904\u2013932 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"274_CR26","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s10107-018-1280-6","volume":"174","author":"MC Yue","year":"2019","unstructured":"Yue, M.C., Zhou, Z., So, A.M.C.: A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property. Math. Progr. 174(1\u20132), 327\u2013358 (2019)","journal-title":"Math. Progr."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00274-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-021-00274-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-021-00274-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,22]],"date-time":"2022-12-22T17:08:54Z","timestamp":1671728934000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-021-00274-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,27]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["274"],"URL":"https:\/\/doi.org\/10.1007\/s10589-021-00274-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,27]]},"assertion":[{"value":"28 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}