Optimization Online


Convergence Analysis of ISTA and FISTA for "Strongly + Semi" Convex Programming

Ke Guo(keguo2014***at***126.com)
Xiaoming Yuan(xmyuan***at***hkbu.edu.hk)
Shangzhi Zeng(15484203***at***life.hkbu.edu.hk)

Abstract: The iterative shrinkage/thresholding algorithm (ISTA) and its faster version FISTA have been widely used in the literature. In this paper, we consider general versions of the ISTA and FISTA in the more general "strongly + semi" convex setting, i.e., minimizing the sum of a strongly convex function and a semiconvex function; and conduct convergence analysis for them. The consideration of a semiconvex function makes it possible to consider some noncovex regularization arising often in contemporary sparsity-driven applications such as the well-known smoothly clipped absolute deviation (SCAD) penalty. Meanwhile, the semiconvex function makes the convergence analysis more challenging than the regular "convex + convex" case. We develop a new analytic framework based on the Fejer monotonicity for the convergence analysis. In the "strongly + semi" convex setting, the respective O(1/k) and O(1/k^2) convergence rates of the general ISTA and FISTA are also established, where k is the iteration counter. We apply the general versions of ISTA and FISTA to solve the SCAD-l2 model and show their efficiency including the apparent acceleration effectiveness of the latter.

Keywords: Iteratively shrinkage/thresholding algorithm, FISTA, semiconvex, nonconvex penalty, SCAD, convergence rate

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )


Download: [PDF]

Entry Submitted: 06/22/2016
Entry Accepted: 06/22/2016
Entry Last Modified: 06/22/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society