  It has been shown in \cite{Lan13-1} that the accelerated prox-level (APL)
method and its variant, the uniform smoothing level (USL) method, have optimal
iteration complexity for solving black-box and structured convex programming
problems without requiring the input of any smoothness information. However,
these algorithms require the assumption on the boundedness of the feasible set
and their efficiency relies on the solutions of two involved subproblems. These
hindered the applicability of these algorithms in solving large-scale and
unconstrained optimization problems. In this paper, we first present a generic
algorithmic framework to extend these uniformly optimal level methods for
solving unconstrained problems. Moreover, we introduce two new variants of
level methods, i.e., the fast APL (FAPL) method and the fast USL (FUSL) method,
for solving large scale black-box and structured convex programming problems
respectively. Both FAPL and FUSL enjoy the same optimal iteration complexity as
APL and USL, while the number of subproblems in each iteration is reduced from
two to one. Moreover, we present an exact method to solve the only subproblem
for these algorithms. As a result, the proposed FAPL and FUSL methods have
improved the performance of the APL and USL in practice significantly in terms
of both computational time and solution quality. Our numerical results on
solving some large-scale least square problems and total variation based image
reconstruction have shown great advantages of these new bundle-level type
methods over APL, USL, and some other state-of-the-art first-order methods.
