On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems
- PDF / 804,678 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 36 Downloads / 203 Views
On the Linear Convergence of a Proximal Gradient Method for a Class of Nonsmooth Convex Minimization Problems Haibin Zhang · Jiaojiao Jiang · Zhi-Quan Luo Received: 7 December 2012 / Revised: 4 March 2013 / Accepted: 23 April 2013 / Published online: 16 May 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
Abstract We consider a class of nonsmooth convex optimization problems where the objective function is the composition of a strongly convex differentiable function with a linear mapping, regularized by the sum of both 1 -norm and 2 -norm of the optimization variables. This class of problems arise naturally from applications in sparse group Lasso, which is a popular technique for variable selection. An effective approach to solve such problems is by the Proximal Gradient Method (PGM). In this paper we prove a local error bound around the optimal solution set for this problem and use it to establish the linear convergence of the PGM method without assuming strong convexity of the overall objective function. Keywords Proximal gradient method · Error bound · Linear convergence · Sparse group Lasso
1 Introduction Consider an unconstrained nonsmooth convex optimization problem of the form min F (x) = f1 (x) + f2 (x),
x∈Rn
This work was partially supported by the National Natural Science Foundation of China (Nos. 61179033, DMS-1015346). Part of this work was performed during a research visit by the first author to the University of Minnesota, with support from the Education Commission of Beijing Municipal Government. H. Zhang · J. Jiang College of Applied Science, Beijing University of Technology, Beijing 100124, China Z.-Q. Luo () Department of Electrical and Computer Engineering, University of Minnesota, Minneapolis, MN 55455, USA e-mail: [email protected]
(1)
164
H. Zhang et al.
where f1 is a nonsmooth convex function given by f1 (x) =
wJ xJ + λx1 ,
(2)
J ∈J
with J a partition of {1, · · · , n} and λ, {wJ }J ∈J some given nonnegative constants; f2 (x) is a composite convex function f2 (x) = h(Ax),
(3)
where h : Rm → R is a continuously differentiable strongly convex function and A ∈ Rm×n is a given matrix. Notice that unless A has full column rank (i.e., rank(A) = n), the composite function f2 (x) is not strongly convex. 1.1 Motivating Applications Nonsmooth convex optimization problems of the form (1) arise in many contemporary statistical and signal applications [4, 24] including signal denoising, compressive sensing, sparse linear regression and high dimensional multinomial classification. To motivate the nonsmooth convex optimization problem (1), we briefly outline some application examples below. Example 1 Suppose that we have a noisy measurement vector d ∈ Rm about an unknown sparse vector x ∈ Rn , where the signal model is linear and given by d ≈ Ax for some given matrix A ∈ Rm×n . A popular technique to estimate the sparse vector x is called Lasso [17, 23] which performs simultaneous estimation and variab
Data Loading...
