Multi-Task Feature Learning Via Efficient l2, 1-Norm Minimization

By Jun Liu, Shuiwang Ji, Jieping Ye. 2009

755 citations recorded by the source corpus.

The problem of joint feature selection across a group of related tasks has applications in many areas including biomedical informatics and computer vision. We consider the l2, 1-norm regularized regression model for joint feature selection from multiple tasks, which can be derived in the probabilistic framework by assuming a suitable prior from the exponential family. One appealing feature of the l2, 1-norm regularization is that it encourages multiple predictors to share similar sparsity patterns. However, the resulting optimization problem is challenging to solve due to the non-smoothness of the l2, 1-norm regularization. In this paper, we propose to accelerate the computation by reformulating it as two equivalent smooth convex optimization problems which are then solved via the Nesterov's method---an optimal first-order black-box method for smooth convex optimization. A key building block in solving the reformulations is the Euclidean projection. We show that the Euclidean projection for the first reformulation can be analytically computed, while the Euclidean projection for the second one can be computed in linear time. Empirical evaluations on several data sets verify the efficiency of the proposed algorithms.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

A Survey on Multi-Task Learning (2017, methodology): “[24] employ an optimal first-order optimization method to solve it.”
Learning Task Grouping and Overlap in Multi-task Learning (2012, background): “Another common assumption is that task parameters lie in a low dimensional subspace that captures the predictive structure for all the tasks (Argyriou et al., 2008a; Liu et al., 2009).”
A Convex Formulation for Learning Task Relationships in Multi-Task Learning (2010, background): “Similar to neural networks, multi-task feature learning [1, 20] also learns common features for all tasks but under the regularization framework.”
Multi-Stage Multi-Task Feature Learning (2012, neutral): “…et al., 2010; Negahban and Wainwright, 2011) and a common set of shared features (Argyriou et al., 2008; Gong et al., 2012; Kim and Xing, 2009; Kolar et al., 2011; Lounici et al., 2009; Liu et al., 2009; Negahban and Wainwright, 2008; Obozinski et al., 2006; Yang et al., 2009; Zhang et al., 2010).”
Learning Multi-Level Task Groups in Multi-Task Learning (2015, methodology): “Baselines used for comparison include a wide range of competitive MTL models: the multi-task feature learning (MTFL) model (Liu, Ji, and Ye 2009), the dirty model (DM) (Jalali et al. 2010), the Cascade model (Zweig and Weinshall 2013), the clustered multi-task learning (CMTL) model (Jacob, Bach,…”
Probabilistic Multi-Task Feature Selection (2010, methodology): “We restrict q to the range 1 q ≤ ∞ to ensure that all norms in this family are convex, making it easier to solve the optimization problem formulated based on it.”
Robust multi-task feature learning (2012, methodology): “On the contrary, algorithms under implicit structure sharing do not explicitly impose all tasks to share certain parameters, but they implicitly capture some common structures; for example, the algorithms in [29, 24] constrain all tasks to share a common low rank subspace and the algorithms in [27, ”
Learning with Whom to Share in Multi-task Feature Learning (2011, methodology): “…assume that the parameters used by all tasks are close to each other, either measured in the Frobenius norms of their differences (Evgeniou & Pontil, 2004; Liu et al., 2009; Zhang & Yeung, 2010; Parameswaran & Weinberger, 2010), or sharing a common prior (Yu et al., 2005; Lee et al., 2007; Daumé,…”
A review of unsupervised feature selection methods (2019, methodology): “Moreover, in this work, an efficient algorithm based on the Nesterov’s method (Liu et al. 2009a) for solving the regression problem was also proposed.”
Multilabel dimensionality reduction via dependence maximization (2008, background): “Recently there are some works on multi-task feature selection [Obozinski et al. 2006; Argyriou et al. 2008; Liu et al. 2009].”
Robust Joint Graph Sparse Coding for Unsupervised Spectral Feature Selection (2017, methodology): “[39] employed an 2,1-norm regularizer to achieve the similar objective.”
Traffic Sign Recognition via Multi-Modal Tree-Structure Embedded Multi-Task Learning (2017, neutral): “Then, each subproblem is: z=argmin z ( 1 2 ‖z− r‖2F +λ̃2 ( K∑ k=1 wk‖zk‖+α‖z‖1 )) (22) It is a special case of (18) induced by the index tree Tm, which can be solved by the same scheme as that of (18).”
Safe Screening for Multi-Task Feature Learning with Multiple Data Matrices (2015, methodology): “MTFL has found great success in many real-world applications including but not limited to: breast cancer classification (Zhang et al., 2010), disease progression prediction (Zhou et al., 2012), gene data analysis (Kim and Xing, 2009), and neural semantic basis discovery (Liu et al., 2009a).”
Efficient Spectral Feature Selection with Minimum Redundancy (2010, methodology): “Given λ , it ﬁrst solves an L 2 , 1 -norm regularized regression problem using a general solver based on the Nesterov’s method (Liu, Ji, and Ye 2009) (Line 11).”