Optimization Online


An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization

Qihang Lin(qihangl***at***andrew.cmu.edu)
Lin Xiao(lin.xiao***at***microsoft.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/2013
Entry Accepted: 04/06/2013
Entry Last Modified: 04/05/2013

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