×

A proximal point dual Newton algorithm for solving group graphical Lasso problems. (English) Zbl 1448.90096

Summary: Undirected graphical models have been especially popular for learning the conditional independence structure among a large number of variables where the observations are drawn independently and identically from the same distribution. However, many modern statistical problems would involve categorical data or time-varying data, which might follow different but related underlying distributions. In order to learn a collection of related graphical models simultaneously, various joint graphical models inducing sparsity in graphs and similarity across graphs have been proposed. In this paper, we aim to propose an implementable proximal point dual Newton algorithm (PPDNA) for solving the group graphical Lasso model, which encourages a shared pattern of sparsity across graphs. Though the group graphical Lasso regularizer is nonpolyhedral, the asymptotic superlinear convergence of our proposed method PPDNA can be obtained by leveraging on the local Lipschitz continuity of the Karush-Kuhn-Tucker solution mapping associated with the group graphical Lasso model. A variety of numerical experiments on real data sets illustrates that the PPDNA for solving the group graphical Lasso model can be highly efficient and robust.

MSC:

90C35 Programming involving graphs or networks
62J10 Analysis of variance and covariance (ANOVA)

Software:

QUIC; glasso
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] O. Banerjee, L. E. Ghaoui, and A. d’Aspremont, Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data, J. Mach. Learn. Res., 9 (2008), pp. 485-516. · Zbl 1225.68149
[2] M. Bollhöfer, A. Eftekhari, S. Scheidegger, and O. Schenk, Large-scale sparse inverse covariance matrix estimation, SIAM J. Sci. Comput., 41 (2019), pp. A380-A401, https://doi.org/10.1137/17M1147615. · Zbl 1414.65043
[3] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000. · Zbl 0966.49001
[4] A. Cardoso-Cachopo, Improving Methods for Single-label Text Categorization, Ph.D. Thesis, Instituto Superior Tecnico, Universidade Tecnica de Lisboa, Lisbon, Portugal, 2007.
[5] F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990, https://doi.org/10.1137/1.9781611971309. · Zbl 0696.49002
[6] F. H. Clarke, Y. S. Ledyaev, R. J. Stern, and P. R. Wolenski, Nonsmooth Analysis and Control Theory, Grad. Texts in Math. 178, Springer, New York, 1998. · Zbl 1047.49500
[7] Y. Cui, D. F. Sun, and K.-C. Toh, On the R-superlinear convergence of the KKT residuals generated by the augmented Lagrangian method for convex composite conic programming, Math. Program., 178 (2019), pp. 381-415. · Zbl 1423.90171
[8] P. Danaher, P. Wang, and D. M. Witten, The joint graphical lasso for inverse covariance estimation across multiple classes, J. R. Stat. Soc. Ser. B Stat. Methodol., 76 (2014), pp. 373-397. · Zbl 07555455
[9] F. Facchinei and J.-S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2007.
[10] J. Friedman, T. Hastie, and R. Tibshirani, Sparse inverse covariance estimation with the graphical lasso, Biostatistics, 9 (2008), pp. 432-441. · Zbl 1143.62076
[11] J. Friedman, T. Hastie, and R. Tibshirani, A Note on the Group Lasso and a Sparse Group Lasso, preprint, https://arxiv.org/abs/1001.0736, 2010.
[12] A. J. Gibberd and J. D. Nelson, Regularized estimation of piecewise constant Gaussian graphical models: The group-fused graphical lasso, J. Comput. Graph. Statist., 26 (2017), pp. 623-634.
[13] D. Hallac, Y. Park, S. Boyd, and J. Leskovec, Network inference via the time-varying graphical lasso, in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, 2017, pp. 205-213.
[14] C.-J. Hsieh, M. A. Sustik, I. S. Dhillon, and P. Ravikumar, QUIC: Quadratic approximation for sparse inverse covariance estimation, J. Mach. Learn. Res., 15 (2014), pp. 2911-2947. · Zbl 1319.65048
[15] X. Y. Lam, J. Marron, D. F. Sun, and K.-C. Toh, Fast algorithms for large-scale generalized distance weighted discrimination, J. Comput. Graph. Statist., 27 (2018), pp. 368-379. · Zbl 07498954
[16] H. Li and J. Gui, Gradient directed regularization for sparse Gaussian concentration graphs, with applications to inference of genetic networks, Biostatistics, 7 (2006), pp. 302-317. · Zbl 1169.62378
[17] X. Li, D. F. Sun, and K.-C. Toh, On efficiently solving the subproblems of a level-set method for fused lasso problems, SIAM J. Optim., 28 (2018), pp. 1842-1866, https://doi.org/10.1137/17M1136390. · Zbl 1401.90145
[18] M. Lin, Y.-J. Liu, D. F. Sun, and K.-C. Toh, Efficient sparse semismooth Newton methods for the clustered Lasso problem, SIAM J. Optim., 29 (2019), pp. 2026-2052, https://doi.org/10.1137/18M1207752. · Zbl 1427.90200
[19] Z. Lu and Y. Zhang, An augmented Lagrangian approach for sparse principal component analysis, Math. Program., 135 (2012), pp. 149-193. · Zbl 1263.90093
[20] F. J. Luque, Asymptotic convergence analysis of the proximal point algorithm, SIAM J. Control Optim., 22 (1984), pp. 277-293, https://doi.org/10.1137/0322019. · Zbl 0533.49028
[21] J.-J. Moreau, Proximité et dualité dans un espace Hilbertien, Bull. Soc. Math. France, 93 (1965), pp. 273-299. · Zbl 0136.12101
[22] S. M. Robinson, Some continuity properties of polyhedral multifunctions, in Mathematical Programming at Oberwolfach, Springer, New York, 1981, pp. 206-214. · Zbl 0449.90090
[23] R. T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1 (1976), pp. 97-116. · Zbl 0402.90076
[24] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), pp. 877-898, https://doi.org/10.1137/0314056. · Zbl 0358.90053
[25] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1996.
[26] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Grundlehren Math. Wiss. 317, Springer, Berlin, 1998. · Zbl 0888.49001
[27] A. J. Rothman, P. J. Bickel, E. Levina, and J. Zhu, Sparse permutation invariant covariance estimation, Electron. J. Statist., 2 (2008), pp. 494-515. · Zbl 1320.62135
[28] N. Simon, J. Friedman, T. Hastie, and R. Tibshirani, A sparse-group lasso, J. Comput. Graph. Statist., 22 (2013), pp. 231-245.
[29] D. F. Sun, The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications, Math. Oper. Res., 31 (2006), pp. 761-776. · Zbl 1278.90304
[30] D. F. Sun and L. Qi, Solving variational inequality problems via smoothing-nonsmooth reformulations, J. Comput. Appl. Math., 129 (2001), pp. 37-62. · Zbl 0987.65059
[31] C. J. Wang, D. F. Sun, and K.-C. Toh, Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm, SIAM J. Optim., 20 (2010), pp. 2994-3013, https://doi.org/10.1137/090772514. · Zbl 1211.90130
[32] S. J. Wright, R. D. Nowak, and M. A. Figueiredo, Sparse reconstruction by separable approximation, IEEE Trans. Signal Process., 57 (2009), pp. 2479-2493. · Zbl 1391.94442
[33] J. Yang, D. F. Sun, and K.-C. Toh, A proximal point algorithm for log-determinant optimization with group Lasso regularization, SIAM J. Optim., 23 (2013), pp. 857-893, https://doi.org/10.1137/120864192. · Zbl 1285.65037
[34] S. Yang, Z. Lu, X. Shen, P. Wonka, and J. Ye, Fused multiple graphical lasso, SIAM J. Optim., 25 (2015), pp. 916-943, https://doi.org/10.1137/130936397. · Zbl 1320.90055
[35] K. Yosida, Functional Analysis, Springer, Berlin, 1964. · Zbl 0830.46001
[36] M. Yuan and Y. Lin, Model selection and estimation in regression with grouped variables, J. R. Stat. Soc. Ser. B Stat. Methodol., 68 (2006), pp. 49-67. · Zbl 1141.62030
[37] M.-C. Yue, Z. Zhou, and A. M.-C. So, A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property, Math. Program., 174 (2019), pp. 327-358. · Zbl 1412.49061
[38] N. Zhang, Y. Zhang, D. F. Sun, and K.-C. Toh, An Efficient Linearly Convergent Regularized Proximal Point Algorithm for Fused Multiple Graphical Lasso Problems, preprint, https://arxiv.org/abs/1902.06952, 2019.
[39] Y. Zhang, N. Zhang, D. F. Sun, and K.-C. Toh, An efficient Hessian based algorithm for solving large-scale sparse group Lasso problems, Math. Program., 179 (2020), pp. 223-263. · Zbl 1435.90112
[40] X.-Y. Zhao, D. F. Sun, and K.-C. Toh, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20 (2010), pp. 1737-1765, https://doi.org/10.1137/080718206. · Zbl 1213.90175
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.