An Optimal High-Order Tensor Method for Convex Optimization

Understand

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 d-th order derivative information available, and the second function is possibly non-smooth, 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 non-smooth part in the objective), Nesterov (1983) proposed an optimal algorithm for the first-order methods (d=1) with iteration complexity O( 1 / k^2 ).