We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is the sum of a possibly nonconvex function, with Lipschitz continuous gradient, and a convex function which can be nonsmooth. The algorithm is shown to have an iteration complexity of \(\mathcal{O}(\epsilon^{-2})\) to find an \(\epsilon\)-approximate solution to the problem, and this complexity improves to \(\mathcal{O}(\epsilon^{-2/3})\) when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case \(o(\epsilon^{-2})\) iterations to find an \(\epsilon\)-approximate solution to the problem, with worst case \(o(\epsilon^{-2/3})\) iterations when its objective function is convex.
Citation
Submitted