A new class of composite objective multistep estimating sequence techniques

A plethora of problems arising in signal processing, machine learning and statistics can be cast as large-scale optimization problems with a composite objective structure. Such problems are typically solved by utilizing iterative first-order algorithms. In this work, we devise a new accelerated gradient-based estimating sequence technique for solving large-scale optimization problems with composite objective structure. Specifically, we introduce a new class of estimating functions, which are obtained by utilizing both a tight lower bound on the objective function, as well as the gradient mapping technique. Then, using the proposed estimating functions, we construct a class of Composite Objective Multi-step Estimating-sequence Techniques (COMET), which are endowed with an efficient line-search procedure. We prove that our proposed COMET enjoys the accelerated convergence rate, and our newly established convergence results allow for step-size adaptation. Our theoretical findings are supported by extensive computational experiments on various problem types and real-world 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.