- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization Qihang Lin(qihanglandrew.cmu.edu) Lin Xiao(lin.xiaomicrosoft.com) Abstract: We consider optimization problems with an objective function that is the sum of two convex terms: one is smooth and given by a black-box oracle, and the other is general but with a simple, known structure. We first present an accelerated proximal gradient (APG) method for problems where the smooth part of the objective function is also strongly convex. This method incorporates an efficient line-search procedure, and achieves the optimal iteration complexity for such composite optimization problems. In case the strong convexity parameter is unknown, we also develop an adaptive scheme that can automatically estimate it on the fly, at the cost of a slightly worse iteration complexity. Then we focus on the special case of solving the $\ell_1$-regularized least-squares problem in the high-dimensional setting. In such a context, the smooth part of the objective (least-squares) is not strongly convex over the entire domain. Nevertheless, we can exploit its restricted strong convexity over sparse vectors using the adaptive APG method combined with a homotopy continuation scheme. We show that such a combination leads to a global geometric rate of convergence, and the overall iteration complexity has a weaker dependency on the restricted condition number than previous work. Keywords: Accelerated gradient method, sparse optimization, restricted eigenvalue conditions, homotopy continuation Category 1: Convex and Nonsmooth Optimization Citation: Microsoft Research Technical report MSR-TR-2013-41, April, 2013. Download: [PDF]Entry Submitted: 04/05/2013Entry Accepted: 04/06/2013Entry Last Modified: 04/05/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.