  


Structured Sparsity via Alternating Direction Methods
Zhiwei (Tony) Qin (zq2107columbia.edu) Abstract: We consider a class of sparse learning problems in high dimensional feature space regularized by a structured sparsityinducing norm which incorporates prior knowledge of the group structure of the features. Such problems often pose a considerable challenge to optimization algorithms due to the nonsmoothness and nonseparability of the regularization term. In this paper, we focus on two commonly adopted sparsityinducing regularization terms, the overlapping Group Lasso penalty $l_1/l_2$norm and the $l_1/l_\infty$norm. We propose a unified framework based on the augmented Lagrangian method, under which problems with both types of regularization and their variants can be efficiently solved. As the core buildingblock of this framework, we develop new algorithms using an alternating partiallinearization/splitting technique, and we prove that the accelerated versions of these algorithms require $O(\frac{1}{\sqrt{\epsilon}})$ iterations to obtain an $\epsilon$optimal solution. To demonstrate the efficiency and relevance of our algorithms, we test them on a collection of data sets and apply them to two realworld problems to compare the relative merits of the two norms. Keywords: structured sparsity, overlapping Group Lasso, alternating directions methods, variable splitting, augmented Lagrangian Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Download: [PDF] Entry Submitted: 05/03/2011 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  