AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Adaptive Linearized Alternating Direction Method of Multipliers for Non-Convex Compositely Regularized Optimization Problems

Linbo Qiao, Bofeng Zhang, Xicheng Lu, Jinshu Su( )
College of Computer, National University of Defense Technology, and National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410073, China.
College of Computer, National University of Defense Technology, Changsha 410073, China.
Show Author Information

Abstract

We consider a wide range of non-convex regularized minimization problems, where the non-convex regularization term is composite with a linear function engaged in sparse learning. Recent theoretical investigations have demonstrated their superiority over their convex counterparts. The computational challenge lies in the fact that the proximal mapping associated with non-convex regularization is not easily obtained due to the imposed linear composition. Fortunately, the problem structure allows one to introduce an auxiliary variable and reformulate it as an optimization problem with linear constraints, which can be solved using the Linearized Alternating Direction Method of Multipliers (LADMM). Despite the success of LADMM in practice, it remains unknown whether LADMM is convergent in solving such non-convex compositely regularized optimizations. In this research, we first present a detailed convergence analysis of the LADMM algorithm for solving a non-convex compositely regularized optimization problem with a large class of non-convex penalties. Furthermore, we propose an Adaptive LADMM (AdaLADMM) algorithm with a line-search criterion. Experimental results on different genres of datasets validate the efficacy of the proposed algorithm.

Keywords

adaptive linearized alternating direction method of multipliersnon-convex compositely regularized optimizationcappled-l1 regularized logistic regression

References

[1]
Hastie T., Tibshirani R., Friedman J., Hastie T., Friedman J., and Tibshirani R., The Elements of Statistical Learning: Data mining, Inference, and Prediction. Springer, 2001.
Crossref
[2]
Tibshirani R. J. and Taylor J., The solution path of the generalized lasso, Annals of Statistics, vol. 39, no. 3, pp. 1335-1371, 2011.
Crossref Google Scholar
[3]
Wright S. J., Nowak R. D., and Figueiredo M. A. T., Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, vol. 57, no. 7, pp. 2479-2493, 2009.
Crossref Google Scholar
[4]
Beck A. and Teboulle M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183-202, 2009.
Crossref Google Scholar
[5]
Shevade S. K. and Keerthi S. S., A simple and efficient algorithm for gene selection using sparse logistic regression, Bioinformatics, vol. 19, no. 17, pp. 2246-2253, 2003.
Crossref Google Scholar
[6]
Wright J., Yang A. Y., Ganesh A., Sastry S. S., and Ma Y., Robust face recognition via sparse representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 2, pp. 210-227, 2009.
Crossref Google Scholar
[7]
Lan Q., Xun C., Wen M., Su H., Liu L., and Zhang C., Improving performance of gpu specific opencl program on cpus, in Parallel and Distributed Computing, Applications and Technologies (PDCAT), 2012 13th International Conference on, 2012, pp. 356-360.
Crossref
[8]
Xiao J., Single-target tracking of arbitrary objects using multi-layered features and contextual information, PhD Dissertation, University of Birmingham, Birmingham, UK, 2016.
[9]
Lai Z., Lam K. T., Wang C. L., and Su J., Latency aware dvfs for efficient power state transitions on many-core architectures, Journal of Supercomputing, vol. 71, no. 7, pp. 1-28, 2015.
Crossref Google Scholar
[10]
Sun Y., Zhang B., Zhao B., Su X., and Su J., Mixzones optimal deployment for protecting location privacy in vanet, Peer-to-Peer Networking and Applications, vol. 8, no. 6, pp. 1108-1121, 2015.
Crossref Google Scholar
[11]
Xu X., Liu C. M., Yang S. X., and Hu D. W., Hierarchical approximate policy iteration with binary-tree state space decomposition, IEEE Transactions on Neural Networks, vol. 22, no. 12, pp. 1863-1877, 2011.
Crossref Google Scholar
[12]
Candes E. J., Wakin M. B., and Boyd S. P., Enhancing sparsity by reweighted l1 minimization, Journal of Fourier Analysis and Applications, vol. 14, nos. 5&6, pp. 877-905, 2008.
Crossref Google Scholar
[13]
Fan J. and Li R., Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association, vol. 96, no. 456, pp. 1348-1360, 2001.
Crossref Google Scholar
[14]
Foucart S. and Lai M. J., Sparsest solutions of underdetermined linear systems via lq-minimization, Applied and Computational Harmonic Analysis, vol. 26, no. 3, pp. 395-407, 2009.
Google Scholar
[15]
Zhang C. H., Nearly unbiased variable selection under minimax concave penalty, Annals of Statistics, vol. 2, no. 1, pp. 894-942, 2010.
Crossref Google Scholar
[16]
Zhang T., Analysis of multi-stage convex relaxation for sparse regularization, Journal of Machine Learning Research, vol. 11, pp. 1081-1107, 2010.
Google Scholar
[17]
Zhang T., Multi-stage convex relaxation for feature selection, Bernoulli, vol. 19, no. 5B, pp. 2277-2293, 2013.
Crossref Google Scholar
[18]
Yang J. F. and Yuan X. M., Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization, Mathematics of Computation, vol. 82, no. 281, pp. 301-329, 2013.
Crossref Google Scholar
[19]
He B. and Yuan X., On the o⁢(1/n) convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, vol. 50, no. 2, pp. 700-709, 2012.
Crossref Google Scholar
[20]
Hong M. and Luo Z. Q., On the linear convergence of the alternating direction method of multipliers, arXiv preprint arXiv:1208.3922, 2012.
[21]
Qiao L., Zhang B., Su J., and Lu X., Linearized alternating direction method of multipliers for constrained nonconvex regularized optimization, in Asian Conference on Machine Learning (ACML), 2016, pp. 97-109.
[22]
Wen Z., Goldfarb D., and Yin W., Alternating direction augmented Lagrangian methods for semidefinite programming, Mathematical Programming Computation, vol. 2, nos. 3&4, pp. 203-230, 2010.
Crossref Google Scholar
[23]
Lu Z., Sequential convex programming methods for a class of structured nonlinear programming, arXiv preprint arXiv:1210.3039, 2012.
[24]
Gong P., Zhang C., Lu Z., Huang J. Z., and Ye J., A general iterative shrinkage and thresholding algorithm for non-convex regularized optimization problems, in Proceedings of ICML, 2013, p. 37.
[25]
Gong P. and Ye J., Honor: Hybrid optimization for non-convex regularized problems, in Proceedings of NIPS, 2015, pp. 415-423.
[26]
Zhong L. W. and Kwok J. T., Fast stochastic alternating direction method of multipliers, in Proceedings of ICML, 2013.
Crossref
[27]
Zhang R. and Kwok J., Asynchronous distributed admm for consensus optimization, in Proceedings of ICML, 2014, pp. 1701-1709.
[28]
Wang H., Banerjee A., and Luo Z. Q., Parallel direction method of multipliers, in Proceedings of NIPS, 2014, pp. 181-189.
[29]
Zhao P., Yang J., Zhang T., and Li P.. Adaptive stochastic alternating direction method of multipliers, in Proceedings of ICML, 2013, pp. 69-77.
[30]
Magnsson S., Chathuranga P., Rabbat M., and Fischione C., On the convergence of alternating direction lagrangian methods for nonconvex structured optimization problems, arXiv preprint arXiv:1409.8033, 2014.
[31]
Jiang B., Ma S., and Zhang S., Alternating direction method of multipliers for real and complex polynomial optimization models, Optimization, vol. 63, no. 6, pp. 883-898, 2014.
Crossref Google Scholar
[32]
Hong M., Luo Z. Q., and Razaviyayn M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM Journal on Optimization, vol. 26, no. 1, pp. 337-364, 2016.
Crossref Google Scholar
[33]
Yang L., Pong T. K., and Chen X., Alternating direction method of multipliers for nonconvex background/foreground extraction, arXiv preprint arXiv:1506.07029, 2015.
[34]
Wang F., Cao W., and Xu Z., Convergence of multiblock bregman admm for nonconvex composite problems, arXiv preprint arXiv:1505.03063, 2015.
[35]
Wang Y., Yin W., and Zeng J., Global convergence of admm in nonconvex nonsmooth optimization, arXiv preprint arXiv:1511.06324, 2015.
[36]
Li G. and Pong T. K., Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization, vol. 25, no. 4, pp. 2434-2460, 2015.
Crossref Google Scholar
[37]
Toland J., A duality principle for non-convex optimisation and the calculus of variations, Archive for Rational Mechanics and Analysis, vol. 71, no. 1, pp. 41-61, 1979.
Crossref Google Scholar
[38]
Gabay D. and Mercier B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & Mathematics with Applications, vol. 2, no. 1, pp. 17-40, 1976.
Crossref Google Scholar
[39]
Scheinberg K., Ma S., and Goldfarb D., Sparse inverse covariance selection via alternating linearization methods, in Proceedings of NIPS, 2010, pp. 2101-2109.
Tsinghua Science and Technology
Volume 22 Issue 3,
June 2017
Pages 328-341
DOI: 10.23919/TST.2017.7914204
Cite this article:
Qiao L, Zhang B, Lu X, et al. Adaptive Linearized Alternating Direction Method of Multipliers for Non-Convex Compositely Regularized Optimization Problems. Tsinghua Science and Technology, 2017, 22(3): 328-341. https://doi.org/10.23919/TST.2017.7914204

509

Views

13

Downloads

6

Crossref

N/A

Web of Science

9

Scopus

3

CSCD

Altmetrics
Received: 19 July 2016
Revised: 04 October 2016
Accepted: 20 October 2016
Published: 04 May 2017
© The authors 2017
Return