  In this paper we propose third-order methods for composite convex
optimization problems in which the smooth part is a three-times continuously
differentiable function with Lipschitz continuous third-order derivatives. The
methods are adaptive in the sense that they do not require the knowledge of the
Lipschitz constant. Trial points are computed by the inexact minimization of
models that consist in the nonsmooth part of the objective plus a quartic
regularization of third-order Taylor polynomial of the smooth part.
Specifically, approximate solutions of the auxiliary problems are obtained by
using a Bregman gradient method as inner solver. Different from existing
adaptive approaches for high-order methods, in our new schemes the
regularization parameters are adjusted taking into account the progress of the
inner solver. With this technique, we show that the basic method finds an
$\epsilon$-approximate minimizer of the objective function performing at most
$\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-\frac{1}{3}}\right)$ iterations of
the inner solver. An accelerated adaptive third-order method is also presented
with total inner iteration complexity of
$\mathcal{O}\left(|\log(\epsilon)|\epsilon^{-\frac{1}{4}}\right)$.
