RAPID: Rapidly Accelerated Proximal Gradient Algorithms for Convex Minimization
This incremental improvement addresses convergence speed for convex optimization problems, benefiting practitioners in machine learning and optimization.
The authors tackled the problem of slow convergence in accelerated proximal gradient (APG) methods for convex minimization by introducing a line search step and new auxiliary variable constructions, resulting in a smaller upper-bound for the objective gap and faster convergence in applications like sparse linear regression and kernel SVMs.
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(θ\mathbf{x})$ is minimized over scalar variable $θ>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.