The global rate of convergence for optimal tensor methods in smooth convex optimization

Understand

We consider convex optimization problems with the objective function having Lipshitz-continuous $p$-th order derivative, where $p\geq 1$.

• We propose a new tensor method, which closes the gap between the lower $O\left(\varepsilon^{-\frac{2}{3p+1}} \right)$ and upper $O\left(\varepsilon^{-\frac{1}{p+1}} \right)$ iteration complexity bounds for this class of optimization problems.
• We also consider uniformly convex functions, and show how the proposed method can be accelerated under this additional assumption.
• Moreover, we introduce a $p$-th order condition number which naturally arises in the complexity analysis of tensor methods under this assumption.