nips nips2010 nips2010-248 nips2010-248-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Katya Scheinberg, Shiqian Ma, Donald Goldfarb
Abstract: Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an ℓ1 -regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem’s special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an ϵ-optimal solution in O(1/ϵ) iterations. Numerical experiments on both synthetic and real data from gene association networks show that a practical version of this algorithm outperforms other competitive algorithms. 1
[1] S. Lauritzen. Graphical Models. Oxford University Press, 1996.
[2] B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM Journal on Computing, 24:227– 234, 1995.
[3] J.-B. Hiriart-Urruty and C. Lemar´ chal. Convex Analysis and Minimization Algorithms II: Advanced e Theory and Bundle Methods. Springer-Verlag, New York, 1993.
[4] M. Yuan and Y. Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94(1):19–35, 2007.
[5] J. Friedman, T. Hastie, and R. Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 2007.
[6] M. Wainwright, P. Ravikumar, and J. Lafferty. High-dimensional graphical model selection using ℓ1 regularized logistic regression. NIPS, 19:1465–1472, 2007.
[7] O. Banerjee, L. El Ghaoui, and A. d’Aspremont. Model selection through sparse maximum likelihood estimation for multivariate gaussian for binary data. Journal of Machine Learning Research, 9:485–516, 2008.
[8] L. Li and K.-C. Toh. An inexact interior point method for l1 -regularized sparse covariance selection. preprint, 2010.
[9] R. Tibshirani. Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc B., 58(1):267–288, 1996.
[10] L. Sun, R. Patel, J. Liu, K. Chen, T. Wu, J. Li, E. Reiman, and J. Ye. Mining brain region connectivity for alzheimer’s disease study via sparse inverse covariance estimation. KDD’09, 2009.
[11] A. Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2005.
[12] K. Scheinberg and I. Rish. Sinco - a greedy coordinate ascent method for sparse inverse covariance selection problem. 2009. Preprint available at http://www.optimizationonline.org/DB HTML/2009/07/2359.html.
[13] J. Duchi, S. Gould, and D. Koller. Projected subgradient methods for learning sparse Gaussian. Conference on Uncertainty in Artificial Intelligence (UAI 2008), 2008.
[14] Y. E. Nesterov. Smooth minimization for non-smooth functions. Math. Program. Ser. A, 103:127–152, 2005.
[15] Y. E. Nesterov. Introductory lectures on convex optimization. 87:xviii+236, 2004. A basic course.
[16] A. D’Aspremont, O. Banerjee, and L. El Ghaoui. First-order methods for sparse covariance selection. SIAM Journal on Matrix Analysis and its Applications, 30(1):56–66, 2008.
[17] Z. Lu. Smooth optimization approach for sparse covariance selection. SIAM J. Optim., 19(4):1807–1827, 2009.
[18] X. Yuan. Alternating direction methods for sparse covariance selection. 2009. Preprint available at http://www.optimization-online.org/DB HTML/2009/09/2390.html.
[19] C. Wang, D. Sun, and K.-C. Toh. Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm. preprint, 2009.
[20] M. Fortin and R. Glowinski. Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems. North-Holland Pub. Co., 1983.
[21] R. Glowinski and P. Le Tallec. Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia, Pennsylvania, 1989.
[22] Y. E. Nesterov. A method for unconstrained convex minimization problem with the rate of convergence O(1/k2 ). Dokl. Akad. Nauk SSSR, 269:543–547, 1983.
[23] P. Tseng. On accelerated proximal gradient methods for convex-concave optimization. submitted to SIAM J. Optim., 2008.
[24] A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sciences, 2(1):183–202, 2009.
[25] D. Goldfarb, S. Ma, and K. Scheinberg. Fast alternating linearization methods for minimizing the sum of two convex functions. Technical report, Department of IEOR, Columbia University, 2010. 9