An Optimal High-Order Tensor Method for Convex Optimization

This paper is concerned with finding an optimal algorithm for minimizing a composite convex objective function. The basic setting is that the objective is the sum of two convex functions: the first function is smooth with up to the dth-order derivative information available, and the second function is possibly nonsmooth, but its proximal tensor mappings can be computed approximately in an efficient manner. The problem is to find—in that setting—the best possible (optimal) iteration complexity for convex optimization. Along that line, for the smooth case (without the second nonsmooth part in the objective), Nesterov proposed an optimal algorithm for the first-order methods ($d=1$) with iteration complexity $O\left(1/k^2\right)$, whereas high-order tensor algorithms (using up to general dth-order tensor information) with iteration complexity $O\left(1/k^{\mathit{d}+1}\right)$ were recently established. In this paper, we propose a new high-order tensor algorithm for the general composite case, with the iteration complexity of $O\left(1/k^{\left(3\mathit{d}+1\right)/2}\right)$, which matches the lower bound for the dth-order methods as previously established and hence is optimal. Our approach is based on the accelerated hybrid proximal extragradient (A-HPE) framework proposed by Monteiro and Svaiter, where a bisection procedure is installed for each A-HPE iteration. At each bisection step, a proximal tensor subproblem is approximately solved, and the total number of bisection steps per A-HPE iteration is shown to be bounded by a logarithmic factor in the precision required.