SINCO - An Efficient Greedy Method for Learning Sparse INverse COvariance Matrix

author: Katya Scheinberg, Lehigh University
published: Jan. 19, 2010, recorded: December 2009, views: 260

Slides

Slides
0:00	SINCO - a greedy coordinate ascent approach for sparse inverse covariance selection
0:18	Morpheus, “The Matrix”, movie
1:09	Sparse inverse covariance selection
1:35	Optimizing log likelihood
2:33	Enforcing sparsity
3:29	Choosing the regularization parameter λ
4:03	Enforcing sparsity
4:17	Choosing the regularization parameter λ
4:43	Primal-dual pair of problems
6:28	First-order methods
8:27	Block coordinate ascent
9:58	Coordinate descent for Lasso
11:05	Coordinate descent variants
13:50	Coordinate descent for the original primal
16:09	Work per iteration
16:26	Summary of the approach
16:35	Testing environment
16:43	ROC curves for varying tolerance or λ in SINCO, ROC curves for GLASSO
16:59	Percentage of true positives in λ paths
17:28	Poor ROC curves for tolerance and lambda still follow each other
18:09	TP and FP with growing N and lambda
18:17	Classification task using the estimated inverse covariance
18:21	CPU time scaling with p, with proportional # of nonzeros, scale-free networks
18:33	What about the CPU time scaling with tol?
18:57	Conclusions and Future work
21:58	Thank you!

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

Herein, we propose a simple greedy algorithm (SINCO) for solving this optimization problem. SINCO solves the primal problem (unlike its predecessors such as COVSEL [10] and glasso [4]), using coordinate ascent, in a greedy manner, thus naturally preserving the sparsity of the solution. As demonstrated by our empirical results, SINCO has better capability in reducing the false-positive error rate (while maintaining similar true positive rate when networks are sufficiently sparse) than glasso [4], because of its greedy incremental nature.