An Optimal HighOrder Tensor Method for Convex Optimization
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:17991801, 2019.
Abstract
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 (1983) proposed an optimal algorithm for the firstorder methods (d=1) with iteration complexity O( 1 / k^2 ). A highorder tensor algorithm with iteration complexity of O( 1 / k^{d+1} ) was proposed by Baes (2009) and Nesterov (2018). In this paper, we propose a new highorder tensor algorithm for the general composite case, with the iteration complexity of O( 1 / k^{(3d+1)/2} ), which matches the lower bound for the dth order methods as established in Nesterov (2018) and Shamir et al. (2018), and hence is optimal. Our approach is based on the Accelerated Hybrid Proximal Extragradient (AHPE) framework proposed in Monteiro and Svaiter (2013), where a bisection procedure is installed for each AHPE iteration. At each bisection step a proximal tensor subproblem is approximately solved, and the total number of bisection steps per AHPE iteration is bounded by a logarithmic factor in the precision required.
Related Material


