worst-case global complexity bounds

On Inexact Solution of Auxiliary Problems in Tensor Methods for Convex Optimization

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization Tags , , , ,

    In this paper we study the auxiliary problems that appear in p-order tensor methods for unconstrained minimization of convex functions with \nu-Holder continuous pth derivatives. This type of auxiliary problems corresponds to the minimization of a (p+\nu)-order regularization of the pth order Taylor approximation of the objective. For the case p=3, we consider the use … Read more

    Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives

  • Geovani Nunes Grapiglia
  • Yurii Nesterov
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    In this paper we study p-order methods for unconstrained minimization of convex functions that are p-times differentiable with $\nu$-Hölder continuous pth derivatives. We propose tensor schemes with and without acceleration. For the schemes without acceleration, we establish iteration complexity bounds of $\mathcal{O}\left(\epsilon^{-1/(p+\nu-1)}\right)$ for reducing the functional residual below a given $\epsilon\in (0,1)$. Assuming that $\nu$ … Read more