A Unified Adaptive Tensor Approximation Scheme to Accelerate Composite Convex Optimization

Understand

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.