*波 江 (上海财经大学)
Abstract: In this talk we discuss the acceleration 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 can be viewed as a relaxation over the existing algorithms in the literature. Under the assumption that the subproblems can be solved approximately, we establish the overall iteration complexity bounds for three specific algorithms to obtain an \epsilon-optimal solution. In general, we show that the adaptive high-order method has an iteration bound of O(1/ epsilon^{1/(p+1)}) if the first p-th order derivative information is used in the approximation, which has the same iteration complexity as in (Nesterov, 2018) where the Lipschitz constants are assumed to be known and subproblems are assumed to be solved exactly. Thus, our results answer an open problem raised by Nesterov on adaptive strategies for high-order accelerated methods. Specifically, we show that the gradient method achieves an iteration complexity in the order of O(1/ epsilon^{1/2}), which is known to be best possible (cf. Nesterov, 1983), while the adaptive cubic regularization methods with the exact/inexact Hessian matrix both achieve an iteration complexity in the order of O(1/ epsilon^{1/3}), which matches that of the original accelerated cubic regularization method presented in (Nesterov, 2008) assuming the availability of the exact Hessian information and the Lipschitz constants, and the global solution of the sub-problems. Our numerical experiment results show a clear effect of acceleration displayed in the adaptive Newton's method with cubic regularization on a set of regularized logistic regression instances.
Math formula preview: