Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation

doi:10.1007/s40305-022-00398-5

Journal of the Operations Research Society of China ›› 2022, Vol. 10 ›› Issue (3): 471-506.doi: 10.1007/s40305-022-00398-5

收稿日期:2021-06-26 修回日期:2021-12-16 出版日期:2022-09-30 发布日期:2022-09-06

Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation

Ru-Jun Jiang¹, Zhi-Shuo Zhou¹, Zi-Rui Zhou²

1. School of Data Science, Fudan University, Shanghai 200433, China;
2. Huawei Technologies Canada, Burnaby, BC, Canada

Received:2021-06-26 Revised:2021-12-16 Online:2022-09-30 Published:2022-09-06
Contact: Ru-Jun Jiang,Zhi-Shuo Zhou,Zi-Rui Zhou E-mail:rjjiang@fudan.edu.cn;zhouzs18@fudan.edu.cn;zirui.zhou@huawei.com
Supported by:
The first author is supported in part by the National Natural Foundation of China (Nos.11801087 and 12171100).

摘要/Abstract

Abstract: Thecubicregularization (CR) algorithmhasattractedalotofattentionsintheliterature in recent years.We propose a new reformulation of the cubic regularization subproblem.The reformulation is an unconstrained convex problem that requires computing the minimum eigenvalue of the Hessian.Then,based on this reformulation,we derive a variant of the (non-adaptive) CR provided a known Lipschitz constant for the Hessian and a variant of adaptive regularization with cubics (ARC).We show that the iteration complexity of our variants matches the best-known bounds for unconstrained minimization algorithms using first-and second-order information.Moreover,we show that the operation complexity of both of our variants also matches the state-of-the-art bounds in the literature.Numerical experiments on test problems from CUTEst collection show that the ARC based on our new subproblem reformulation is comparable to the existing algorithms.

Key words: Cubic regularization subproblem, First-order methods, Constrained convex optimization, Complexity analysis

中图分类号:

. [J]. Journal of the Operations Research Society of China, 2022, 10(3): 471-506.

Ru-Jun Jiang, Zhi-Shuo Zhou, Zi-Rui Zhou. Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation[J]. Journal of the Operations Research Society of China, 2022, 10(3): 471-506.

参考文献

[1] Nesterov, Y., Polyak, B.T.:Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177-205(2006)
[2] Cartis, C., Gould, N.I.M., Toint, P.L.:Adaptive cubic regularisation methods for unconstrained optimization. Part I:motivation, convergence and numerical results. Math. Program. 127(2), 245-295(2011)
[3] Griewank, A.:The modification of Newton's method for unconstrained optimization by bounding cubic terms. Technical report, Technical report NA/12,(1981)
[4] Cartis, C., Gould, N.I.M., Toint, P.L.:Adaptive cubic regularisation methods for unconstrained optimization. Part ii:worst-case function-and derivative-evaluation complexity. Math. Program. 130(2), 295-319(2011)
[5] Curtis, F.E., Robinson, D.P., Royer, C.W., Wright, S.J.:Trust-region Newton-CG with strong secondorder complexity guarantees for nonconvex optimization. SIAM J. Optim. 31(1), 518-544(2021)
[6] 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-1199. ACM,(2017)
[7] Yair, C., Duchi, J.C., Hinder, O., Sidford, A.:Accelerated methods for nonconvex optimization. SIAM J. Optim. 28(2), 1751-1772(2018)
[8] Royer, C.W., Wright, S.J.:Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM J. Optim. 28(2), 1448-1477(2018)
[9] Royer, C.W., O'Neill, M., Wright, S.J.:A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Math. Program. 180(1), 451-488(2020)
[10] Yair, C., Duchi, J.C.:Analysis of Krylov subspace solutions of regularized non-convex quadratic problems. In Advances in Neural Information Processing Systems, pp. 10705-10715(2018)
[11] Carmon, Y., Duchi, J.C.:First-order methods for nonconvex quadratic minimization. SIAM Rev. 62(2), 395-436(2020)
[12] Carmon, Yair, Duchi, John:Gradient descent finds the cubic-regularized nonconvex Newton step. SIAM J. Optim. 29(3), 2146-2178(2019)
[13] Jiang, Rujun, Yue, Man-Chung., Zhou, Zhishuo:An accelerated first-order method with complexity analysis for solving cubic regularization subproblems. Comput. Optim. Appl. 79(2), 471-506(2021)
[14] Flippo,O.E.,Jansen,B.:Dualityandsensitivityinnonconvexquadraticoptimizationoveranellipsoid. Eur. J. Oper. Res. 94(1), 167-178(1996)
[15] Ho-Nguyen, Nam, Kılınç-Karzan, Fatma:A second-order cone based approach for solving the trustregion subproblem and its variants. SIAM J. Optim. 27(3), 1485-1512(2017)
[16] Wang, Jiulin, Xia, Yong:A linear-time algorithm for the trust region subproblem based on hidden convexity. Optim. Lett. 11(8), 1639-1646(2017)
[17] Jiang, R., Li, D.:Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2), 1603-1633(2019)
[18] Nesterov, Y.:Lectures on Convex Optimization, vol. 137. Springer, Berlin (2018)
[19] Xu, P., Roosta, F., Mahoney, M.W.:Newton-type methods for non-convex optimization under inexact Hessian information. Math. Program. 184(1), 35-70(2020)
[20] Vandenberghe, L..:Accelerated Proximal Gradient Methods. Lecture notes, https://www.seas.ucla. edu/~vandenbe/236C/lectures/fgrad.pdf,(2021)
[21] Kuczy′ nski, Jacek, Wó zniakowski, Henryk:Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094-1122(1992)
[22] Jonathan, B., Borwein, J.M.:Two-point step size gradient methods. IMA J. Numer. Anal. 8(1), 141-148(1988)
[23] Gould, N.I.M., Orban, D., Toint, P.L.:Cutest:a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545-557(2015)
[24] O'Donoghue,Brendan,Candes,Emmanuel:Adaptiverestartforacceleratedgradientschemes.Found. Comput Math. 15(3), 715-732(2015)
[25] Ito, Naoki, Takeda, Akiko, Toh, Kim-Chuan.:A unified formulation and fast accelerated proximal gradient method for classification. J. Mach. Learn. Res. 18(1), 510-558(2017)
[26] Dolan, E.D., Moré, J.J.:Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213(2002)
[27] Birgin, E.G., Gardenghi, J.L., Martínez, J.M., Santos, S.A., Toint, P.L.:Worst-case evaluation complexityforunconstrainednonlinearoptimizationusinghigh-orderregularizedmodels.Math.Program. 163(1-2), 359-368(2017)
[28] Jiang, Bo., Lin, Tianyi, Zhang, Shuzhong:A unified adaptive tensor approximation scheme to accelerate composite convex optimization. SIAM J. Optim. 30(4), 2897-2926(2020)
[29] Nesterov,Yurii:Implementabletensormethodsinunconstrainedconvexoptimization.Math.Program. 186(1), 157-183(2021)
[30] Geovani Nunes Grapiglia and Yu Nesterov:On inexact solution of auxiliary problems in tensor methods for convex optimization. Optim. Methods Softw. 36(1), 145-170(2021)

Cubic Regularization Methods with Second-Order Complexity Guarantee Based on a New Subproblem Reformulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价