First Order Algorithm on an Optimization Problem with Improved Convergence when Problem is Convex

Abstract

We propose a first order algorithm, a modified version of FISTA, to solve an optimization problem with an objective function that is a 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}(\hat{I}{\mu }^{-2})$ to find an $\hat{I}\mu$-approximate solution to the problem, and this complexity improves to $\mathcal{O}(\hat{I}{\mu }^{-2/3})$ when the objective function turns out to be convex. We further provide asymptotic convergence rate for the algorithm of worst case $o(\hat{I}{\mu }^{-2})$ iterations to find an $\hat{I}\mu$-approximate solution to the problem, with worst case $o(\hat{I}{\mu }^{-2/3})$ iterations when its objective function is convex.

15 pages