{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T12:39:50Z","timestamp":1790685590057,"version":"4.1.0"},"reference-count":53,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"Shenzhen Research Fund","award":["KQTD2015033114415450"],"award-info":[{"award-number":["KQTD2015033114415450"]}]},{"DOI":"10.13039\/501100011002","name":"National Natural Science Foundation of China-Yunnan Joint Fund","doi-asserted-by":"publisher","award":["11771269"],"award-info":[{"award-number":["11771269"]}],"id":[{"id":"10.13039\/501100011002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100011002","name":"National Natural Science Foundation of China-Yunnan Joint Fund","doi-asserted-by":"publisher","award":["11831002"],"award-info":[{"award-number":["11831002"]}],"id":[{"id":"10.13039\/501100011002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1462408"],"award-info":[{"award-number":["CMMI-1462408"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007931","name":"Shanghai University of Finance and Economics","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007931","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2020,1]]},"abstract":"<jats:p>In this paper, we propose a unified two-phase scheme to accelerate any high-order regularized tensor approximation approach on the smooth part of a composite convex optimization model. The proposed scheme has the advantage of not needing to assume any prior knowledge of the Lipschitz constants for the gradient, the Hessian, and\/or high-order derivatives. This is achieved by tuning the parameters used in the algorithm adaptively in its process of progression, which has been successfully incorporated in high-order nonconvex optimization [C. Cartis, N. I. M. Gould, and Ph. L. Toint, Found. Comput. Math., 18 (2018), pp. 1073--1107; E. G. Birgin et al., Math. Program., 163 (2017), pp. 359--368]. By adopting a similar approximate measure of the subproblem in [E. G. Birgin et al., Math. Program., 163 (2017), pp. 359--368] for nonconvex optimization, we establish the overall iteration complexity bounds for three specific algorithms to obtain an $\\epsilon$-optimal solution for composite convex problems. In general, we show that the adaptive high-order method has an iteration bound of $O\\left( 1 \/ \\epsilon^{1\/(p+1)} \\right)$ if the first $p$th-order derivative information is used in the approximation, which has the same iteration complexity as in [M. Baes, Estimate Sequence Methods: Extensions and Approximations, Institute for Operations Research, ETH, Z\u00fcrich, 2009; Y. Nesterov, Math. Program., published online Nov. 21, 2019, https:\/\/doi.org\/10.1007\/s10107-019-01449-1], where the Lipschitz constants are assumed to be known, and the subproblems are assumed to be solved exactly. Thus, our results partially address the problem of incorporating adaptive strategies into the high-order accelerated methods raised by Nesterov in [ Math. Program., published online Nov. 21, 2019, https:\/\/doi.org\/10.1007\/s10107-019-01449-1], although our strategies cannot ensure the convexity of the auxiliary problem, and such adaptive strategies are already popular in high-order nonconvex optimization [C. Cartis, N. I. M. Gould, and Ph. L. Toint, Found. Comput. Math., 18 (2018), pp. 1073--1107; E. G. Birgin et al., Math. Program., 163 (2017), pp. 359--368]. Specifically, we show that the gradient method achieves an iteration complexity on the order of $O\\left( 1 \/ \\epsilon^{1\/2} \\right)$, which is known to be best possible (cf. [Y. Nesterov, Lectures on Convex Optimization, 2nd ed., Springer, 2018]), while the adaptive cubic regularization methods with the exact\/inexact Hessian matrix achieve an iteration complexity on the order of $O\\left( 1 \/ \\epsilon^{1\/3} \\right)$, which matches that of the original accelerated cubic regularization method presented in [Y. Nesterov, Math. Program., 112 (2008), pp. 159--181]. The results of our numerical experiment clearly show the effect of the acceleration displayed in the adaptive Newton's method with cubic regularization on a set of regularized logistic regression instances.<\/jats:p>","DOI":"10.1137\/19m1286025","type":"journal-article","created":{"date-parts":[[2020,10,8]],"date-time":"2020-10-08T14:05:03Z","timestamp":1602165903000},"page":"2897-2926","source":"Crossref","is-referenced-by-count":15,"title":["A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization"],"prefix":"10.1137","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8924-3185","authenticated-orcid":true,"given":"Bo","family":"Jiang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5323-1852","authenticated-orcid":true,"given":"Tianyi","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5838-1676","authenticated-orcid":true,"given":"Shuzhong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2020,10,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0499-2"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1293-1"},{"key":"atypb3","unstructured":"M. Baes,\n                      Estimate Sequence Methods: Extensions and Approximations\n                      , Institute for Operations Research, ETH, Z\u00fcrich, Switzerland, 2009."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080716542"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2020.1725751"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1093\/imanum\/dry009"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/15M1031631"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-1065-8"},{"key":"atypb9","unstructured":"B. Bullins and R. Peng,\n                      Higher-Order Accelerated Methods for Faster Nonsmooth Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1906.01621, 2019."},{"key":"atypb10","unstructured":"S. Bubeck, Q. Jiang, Y. T. Lee, Y. Li, and A. Sidford,\n                      Near-Optimal Method for Highly Smooth Convex Optimization\n                      , preprint, https:\/\/arxiv.org\/abs\/1812.08026, 2018."},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0941-y"},{"key":"atypb12","unstructured":"L. Calatroni and A. Chambolle,\n                      Backtracking Strategies for Accelerated Descent Methods with Smooth Composite Objectives\n                      , preprint,https:\/\/arxiv.org\/abs\/1709.09004, 2017."},{"key":"atypb13","unstructured":"Y. Carmon and J. Duchi,\n                      Gradient Descent Efficiently Finds the Cubic-Regularized Non-convex Newton Step\n                      , preprint,https:\/\/arxiv.org\/abs\/1612.00547v2, 2016."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0286-5"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0337-y"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2011.602076"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/100812276"},{"key":"atypb18","unstructured":"C. Cartis, N. I. M. Gould, and Ph. L. Toint,\n                      Improved Second-Order Evaluation Complexity for Unconstrained Nonlinear Optimization Using High-Order Regularized Models\n                      , preprint,https:\/\/arxiv.org\/abs\/1708.04044, 2017."},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-017-9363-y"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106316"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/18M1166511"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"X. Chen and Ph. L. Toint,\n                      High-order evaluation complexity for convexly-constrained optimization with non-Lipschitzian group sparsity terms\n                      , Math. Program., to appear; published online Jan. 28, 2020,https:\/\/doi.org\/10.1007\/s10107-020-01470-9.","DOI":"10.1007\/s10107-020-01470-9"},{"key":"atypb23","first-page":"2121","volume":"12","author":"Duchi J.","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"atypb24","first-page":"1392","volume":"99","author":"Gasnikov A.","year":"2019","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0846-1"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-015-0871-8"},{"key":"atypb27","unstructured":"S. Ghadimi, H. Liu, and T. Zhang,\n                      Second-Order Methods with Cubic Regularization under Inexact Information\n                      , preprint,https:\/\/arxiv.org\/abs\/1710.05782, 2017."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-017-9964-z"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1137\/17M1142077"},{"key":"atypb30","unstructured":"G. N. Grapiglia and Y. Nesterov,\n                      Tensor Methods for Minimizing Functions with H\u00f6lder Continuous Higher-Order Derivatives\n                      , preprint,https:\/\/arxiv.org\/abs\/1904.12559, 2019."},{"key":"atypb31","unstructured":"G. N. Grapiglia and Y. Nesterov,\n                      Tensor Methods for Finding Approximate Stationary Points of Convex Functions\n                      , preprint,https:\/\/arxiv.org\/abs\/1907.07053, 2019."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9286-4"},{"key":"atypb33","unstructured":"B. Jiang, T. Lin, and S. Zhang,\n                      A Unified Scheme to Accelerate Adaptive Cubic Regularization and Gradient Methods for Convex Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1710.04788, 2017."},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-018-0034-y"},{"key":"atypb36","unstructured":"A. Karparthy,\n                      A Peak at Trends in Machine Learning\n                      , Medium, posted April 7, 2017,https:\/\/medium.com\/@karpathy\/a-peek-at-trends-in-machine-learning-ab8a1085a106."},{"key":"atypb37","unstructured":"D. Kingma and J. Ba,\n                      Adam: A Method for Stochastic Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1412.6980, 2014."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1137\/130921428"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-014-9694-4"},{"key":"atypb40","doi-asserted-by":"crossref","unstructured":"D. G. Luenberger and Y. Ye,\n                      Linear and Nonlinear Programming\n                      , 4th ed., Internat. Ser. Oper. Res. Management Sci. 228, Springer, Cham, 2016.","DOI":"10.1007\/978-3-319-18842-3_6"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1137\/17M1115472"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9802-0"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1137\/110833786"},{"key":"atypb44","first-page":"543","volume":"269","author":"Nesterov Y.","year":"1983","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0706-8"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0089-x"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0629-5"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Lectures on Convex Optimization\n                      , 2nd ed., Springer Optim. Appl. 137, Springer, Cham, 2018.","DOI":"10.1007\/978-3-319-91578-4_2"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"Y. Nesterov,\n                      Implementable tensor methods in unconstrained convex optimization\n                      , Math. Program., to appear; published online Nov. 21, 2019,https:\/\/doi.org\/10.1007\/s10107-019-01449-1.","DOI":"10.1007\/s10107-019-01449-1"},{"key":"atypb50","unstructured":"J. Nocedal and S. J. Wright,\n                      Numerical Optimization\n                      , Springer, 2006."},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-014-9189-9"},{"key":"atypb52","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-016-0997-3"},{"key":"atypb53","first-page":"26","volume":"4","author":"Tieleman T.","year":"2012","journal-title":"COURSERA: Neural Networks for Machine Learning"},{"key":"atypb54","unstructured":"A. Wilson, L. Mackey, and A. Wibisono,\n                      Accelerating Rescaled Gradient Descent: Fast Optimization of Smooth Functions\n                      , preprint,https:\/\/arxiv.org\/abs\/1902.08825, 2019."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1286025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:51Z","timestamp":1787337531000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1286025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1137\/19M1286025"],"URL":"https:\/\/doi.org\/10.1137\/19m1286025","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}