  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 \textit{adaptively} in its process of
progression, which has been successfully incorporated in high-order nonconvex
optimization (CartisGouldToint2018,
Birgin-Gardenghi-Martinez-Santos-Toint-2017). 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 that
of the nonadaptive version in (Baes-2009, Nesterov-2018) 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 {\it accelerated} methods raised by
Nesterov in (Nesterov-2018), although our strategies cannot assure the
convexity of the auxiliary problem and such adaptive strategies are already
popular in high-order nonconvex optimization (CartisGouldToint2018,
Birgin-Gardenghi-Martinez-Santos-Toint-2017). Our numerical experiment results
show a clear effect of real acceleration displayed in the adaptive Newton's
method with cubic regularization on a set of regularized logistic regression
instances.
