  We introduce a framework, which we denote as the augmented estimate sequence,
for deriving fast algorithms with provable convergence guarantees. We use this
framework to construct a new first-order scheme, the Accelerated Composite
Gradient Method (ACGM), for large-scale problems with composite objective
structure. ACGM surpasses the state-of-the-art methods for this problem class
in terms of provable convergence rate, both in the strongly and non-strongly
convex cases, and is endowed with an efficient step size search procedure. We
support the effectiveness of our new method with simulation results.
