  We devise a new accelerated gradient-based estimating sequence technique for
solving large-scale optimization problems with composite structure. More
specifically, we introduce a new class of estimating functions, which are
obtained by utilizing a tight lower bound on the objective function. Then, by
exploiting the coupling between the proposed estimating functions and the
gradient mapping technique, we construct a class of composite objective
multi-step estimating-sequence techniques (COMET). We propose an efficient line
search strategy for COMET, and prove that it enjoys an accelerated convergence
rate. The established convergence results allow for step size adaptation. Our
theoretical findings are supported by extensive computational experiments on
various problem types and datasets. Moreover, our numerical results show
evidence of the robustness of the proposed method to the imperfect knowledge of
the smoothness and strong convexity parameters of the objective function.
