Graph-Structured Multi-task Regression and an Efficient Optimization Method for General Fused Lasso

By X. Chen, Seyoung Kim, Qihang Lin, Jaime G. Carbonell, Eric P. Xing. 2010

111 citations recorded by the source corpus.

We consider the problem of learning a structured multi-task regression, where the output consists of multiple responses that are related by a graph and the correlated response variables are dependent on the common inputs in a sparse but synergistic manner. Previous methods such as l1/l2-regularized multi-task regression assume that all of the output variables are equally related to the inputs, although in many real-world problems, outputs are related in a complex manner. In this paper, we propose graph-guided fused lasso (GFlasso) for structured multi-task regression that exploits the graph structure over the output variables. We introduce a novel penalty function based on fusion penalty to encourage highly correlated outputs to share a common set of relevant inputs. In addition, we propose a simple yet efficient proximal-gradient method for optimizing GFlasso that can also be applied to any optimization problems with a convex smooth loss and the general class of fusion penalty defined on arbitrary graph structures. By exploiting the structure of the non-smooth ''fusion penalty'', our method achieves a faster convergence rate than the standard first-order method, sub-gradient method, and is significantly more scalable than the widely adopted second-order cone-programming and quadratic-programming formulations. In addition, we provide an analysis of the consistency property of the GFlasso model. Experimental results not only demonstrate the superiority of GFlasso over the standard lasso but also show the efficiency and scalability of our proximal-gradient method.

Subfields: Orthopedics and Sports Medicine

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

A Convex Feature Learning Formulation for Latent Task Structure Discovery (2012, background): “Alternatively, Chen et al. (2010) assume that the relations between the tasks are known and propose employing a regularizer that penalizes deviations in weight vectors for highly correlated tasks.”
Inductive multi-task learning with multiple view data (2012, background): “Recent studies on MTL proposed that the relatedness of multiple tasks has a structure such as a graph or a tree [10, 17], or different tasks share a common subspace representation [9].”
Multi-target regression via input space expansion: treating targets as inputs (2012, methodology): “…and Pontil 2004; Ando and Zhang 2005; Argyriou et al 2006, 2008; Chen et al 2009, 2010a; Obozinski et al 2010), while there are methods assuming that tasks are organized in structures such as clusters (Jacob et al 2008; Zhou et al 2011a), trees (Kim and Xing 2010) and graphs (Chen et al 2010b).”