A New Class of Composite Objective Multi-step Estimating-sequence Techniques (COMET)

Abstract

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.

31 pages, 3 figures

References in corpus (9)

• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• A Variational Perspective on Accelerated Methods in Optimization
• Convex Optimization for Big Data
• A geometric alternative to Nesterov's accelerated gradient descent
• From Averaging to Acceleration, There is Only a Step-size
• A Generalized Accelerated Composite Gradient Method: Uniting Nesterov's Fast Gradient Method and FISTA
• Generalizing the optimized gradient method for smooth convex minimization
• An Accelerated Composite Gradient Method for Large-scale Composite Objective Problems
• Projected Nesterov's Proximal-Gradient Algorithm for Sparse Signal Reconstruction with a Convex Constraint