An adaptive accelerated proximal gradient method and its homotopy continuation for sparse optimization
详细信息 查看全文
- 作者：Qihang Lin (1)
Lin Xiao (2)
1. Tippie College of Business ; The University of Iowa ; Iowa City ; IA ; 52242 ; USA
2. Machine Learning Groups ; Microsoft Research ; Redmond ; WA ; 98052 ; USA - 关键词：Proximal gradient method ; Sparse optimization ; L1 ; regularized least ; squares ; Homotopy continuation ; First ; order method
- 刊名：Computational Optimization and Applications
- 出版年：2015
- 出版时间：April 2015
- 年：2015
- 卷：60
- 期：3
- 页码：633-674
- 全文大小：883 KB
- 参考文献：1. Agarwal, A, Negahban, SN, Wainwright, MJ (2012) Fast global convergence of gradient methods for high-dimensional statistical recovery. Ann. Stat. 40: pp. 2452-2482 CrossRef
2. Beck, A, Teboulle, M (2009) A fast iterative shrinkage-threshold algorithm for linear inverse problems. SIAM J. Imaging Sci. 2: pp. 183-202 CrossRef
3. Bredies, K, Lorenz, DA (2008) Linear convergence of iterative soft-thresholding. J. Fourier Anal. Appl. 14: pp. 813-837 CrossRef
4. Bruckstein, AM, Donoho, DL, Elad, M (2009) From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Rev. 51: pp. 34-81 CrossRef
5. Cand猫s, EJ, Tao, T (2005) Decoding by linear programming. IEEE Trans. Inform. Theory 51: pp. 4203-4215 CrossRef
6. Cand猫s, EJ, Tao, T (2006) Near-optimal signal recovery from random projections: universal encoding strategies?. IEEE Trans. Inform. Theory 52: pp. 5406-5425 CrossRef
7. Cand猫s, EJ, Romberg, J, Tao, T (2006) Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52: pp. 489-509 CrossRef
8. Chen, SS, Donoho, DL, Saunders, MA (1998) Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20: pp. 33-61 CrossRef
9. Donoho, DL (2006) Compressed sensing. IEEE Trans. Inform. Theory 52: pp. 1289-1306 CrossRef
10. Gonzaga, CC, Karas, EW (2013) Fine tuning Nesterov鈥檚 steepest descent algorithm for differentiable convex programming. Math. Program. Ser. A 138: pp. 141-166 CrossRef
11. Gu, M, Lim, L-H, Wu, CJ (2013) ParNes: a rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals. Numer. Algorithms 64: pp. 321-347 CrossRef
12. Hale, ET, Yin, W, Zhang, Y (2008) Fixed-point continuation for $$\ell _1$$ 鈩1 -minimization: methodology and convergence. SIAM J. Optim. 19: pp. 1107-1130 CrossRef
13. Li, S, Mo, Q (2011) New bounds on the restricted isometry constant $$\delta _{2k}$$ 未 2 k. Appl. Comput. Harmon. Anal. 31: pp. 460-468 CrossRef
14. Luo, Z-Q, Tseng, P (1992) On the linear convergence of descent methods for convex essentially smooth minimization. SIAM J. Control Optim. 30: pp. 408-425 CrossRef
15. Monteiro, R.D.C., Ortiz, C., Svaiter, B.F.: An adaptive accelerated first-order method for convex optimization. Technical report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA (2012)
16. Nemirovski, A, Yudin, D (1983) Problem Complexity and Method Efficiency in Optimization. Wiley, New York
17. Nesterov, Y (2004) Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, Boston CrossRef
18. Nesterov, Y (2005) Smooth minimization of nonsmooth functions. Math. Program. 103: pp. 127-152 CrossRef
19. Nesterov, Y (2008) How to advance in structural convex optimization. OPTIMA: Math. Program. Soc. Newsl. 78: pp. 2-5
20. Nesterov, Y (2013) Gradient methods for minimizing composite objective function. Math. Program. Ser. B 140: pp. 125-161 CrossRef
21. Nesterov, Y, Nemirovski, A (1994) Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia CrossRef
22. O鈥橠onoghue, B., Cand猫s, E.J.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. (2013). doi:10.1007/s10208-013-9150-3
23. Rockafellar, RT (1970) Convex Analysis. Princeton University Press, Princeton
24. Tibshirani, R (1996) Regression shrinkage and selection via the lasso. J. R Stat. Soc. Ser. B 58: pp. 267-288
25. Tseng, P.: On accelerated proximal gradient methods for convex鈥揷oncave optimization. Manuscript (2008)
26. Wright, SJ, Nowad, RD, Figueiredo, MAT (2009) Sparse reconstruction by separable approximation. IEEE Trans. Signal Process. 57: pp. 2479-2493 CrossRef
27. Wright, SJ (2012) Accelerated block-coordinate relaxation for regularized optimization. SIAM J. Optim. 22: pp. 159-186 CrossRef
28. Wen, Z, Yin, W, Goldfarb, D, Zhang, Y (2010) A fast algorithm for sparse reconstruction based on shrinkage, subspace optimization and continuation. SIAM J. Sci. Comput. 32: pp. 1832-1857 CrossRef
29. Xiao, L, Zhang, T (2013) A proximal-gradient homotopy method for the sparse least-squares problem. SIAM J. Optim. 23: pp. 1062-1091 CrossRef
30. Zhang, C-H, Huang, J (2008) The sparsity and bias of the lasso selection in high-dimensional linear regression. Ann. Stat. 36: pp. 1567-1594 CrossRef - 刊物类别：Mathematics and Statistics
- 刊物主题：Mathematics
Optimization
Operations Research and Mathematical Programming
Operation Research and Decision Theory
Statistics
Convex and Discrete Geometry - 出版者：Springer Netherlands
- ISSN：1573-2894
文摘
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.