  In this paper, we propose a new algorithm to speed-up the convergence of
accelerated proximal gradient (APG) methods. In order to minimize a convex
function $f(\mathbf{x})$, our algorithm introduces a simple line search step
after each proximal gradient step in APG so that a biconvex function
$f(\theta\mathbf{x})$ is minimized over scalar variable $\theta>0$ while fixing
variable $\mathbf{x}$. We propose two new ways of constructing the auxiliary
variables in APG based on the intermediate solutions of the proximal gradient
and the line search steps. We prove that at arbitrary iteration step $t
(t\geq1)$, our algorithm can achieve a smaller upper-bound for the gap between
the current and optimal objective values than those in the traditional APG
methods such as FISTA, making it converge faster in practice. In fact, our
algorithm can be potentially applied to many important convex optimization
problems, such as sparse linear regression and kernel SVMs. Our experimental
results clearly demonstrate that our algorithm converges faster than APG in all
of the applications above, even comparable to some sophisticated solvers.
