Rapid: Rapidly accelerated proximal gradient algorithms for convex minimization

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(x), our algorithm introduces a simple line search step after each proximal gradient step in APG so that a biconvex function f(θx) is minimized over scalar variable θ > 0 while fixing variable 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 ≥ 1), 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 [1], making it converge faster in practice. We apply our algorithm to many important convex optimization problems such as sparse linear regression. Our experimental results demonstrate that our algorithm converges faster than APG, even comparable to some sophisticated solvers.