Fast iterative shrinkage thresholding algorithm (FISTA) recently proposed by Beck and Teboulle have generate a lot of interested do its simplicity, effectiveness and the O(1/k^2) convergence rate when applied to certain classes of convex nonsmooth problems. However the strong condition that the step size has to be monotonically non-increasing limits the line search capability and the practical performance of FISTA.
We show how FISTA can be modified to allow for full line search for the step size. We show that a method with full line search can have the same complexity of $O(\sqrt{L(f)/\epsilon}$ as FISTA and other accelerated first-order methods. We also show a complexity estimate that depends on the ``average'' local Lipschitz constant, rather than the global or the worst case Lipschitz constant for the function gradient. Hence we show that our method can potentially have better convergence rate than FISTA.
We will also discuss the extensions of this approach to an alternating linearization scheme.
Copyright. All Rights Reserved.