Journal article
An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
Computational optimization and applications, Vol.60(3), pp.633-674
04/01/2015
DOI: 10.1007/s10589-014-9694-4
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 -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.
Details
- Title: Subtitle
- An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
- Creators
- Qihang Lin - University of IowaLin Xiao - Microsoft
- Resource Type
- Journal article
- Publication Details
- Computational optimization and applications, Vol.60(3), pp.633-674
- Publisher
- Springer Nature
- DOI
- 10.1007/s10589-014-9694-4
- ISSN
- 0926-6003
- eISSN
- 1573-2894
- Number of pages
- 42
- Language
- English
- Date published
- 04/01/2015
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380513502771
Metrics
1 Record Views