CV Home Publications Professional Activities Softwares Awards Collaborators Contact Album
Research Topic: Large-Scale Sparse Learning
Sparse Learning has recently become a popular research topic, due to its ability of conducting simultaneous classification and feature selection.The most well-known sparsity inducing norm is the L1 norm, which is convex and has many favorable theoretical results.
In many applications, the data features can have some intrinsic structures, e.g. the features may have some meaningful order. Such structure can be used as the prior information for the model to be learned. When incorporating the structure information into sparse learning, we have the so-called structured sparse learning. It has been shown that, the structured sparse learning can help achieve improved regression/classification performance, and yield the interpretable results via the identified markers. The current research on structured sparse learning are based on the various extensions of the L1 norm:
I mainly study the efficient optimization of the different structured sparse learning models, and have developed the SLEP (Sparse Learning with Efficient Projections) package. The main challenge of the different sparse learning formulations is that, the penalty terms are nonsmooth. To make use of the existing first-order optimization methods such as the accelerated gradient descent, a key building block is to efficiently solving the associated Euclidean projections (proximal operators, Moreau-Yosida regularization). For different penalties, we make use of different techniques that utilize the specific structures for fast convergence.
The current version of the SLEP package is implemented in Matlab, with the associated Euclidean projections in C. New functions / features are being added into the SLEP package. The C version shall be distributed soon.
My contributions on this topic:
Moreau-Yosida Regularization for Grouped Tree Structure Learning [PDF] [Code] [Bib \cite{Liu:nips:2010}]
Jun Liu and Jieping Ye
Advances in Neural Information Processing Systems (NIPS) 2010
We developed an efficient algorithm for the tree structured group Lasso, which is an extension of our UAI'09 paper.
We showed that, the Moreau-Yosida regularization associated with the tree structured group Lasso, which is one of the key building blocks, can be computed analytically.
We also showed how to specify the effective interval for the regularization parameter, which is key to the practical application of this method.
The main technique employed in the proof is the subdifferential, which has played important roles in non-smooth convex analysis.
Experimental results on facial expression classification were reported, where image pixels are represented as a tree structure.
Efficient L1/Lq Norm Regularization [PDF] [Bib \cite{Liu:L1Lq:2010}]
Jun Liu and Jieping Ye
We considered the group Lasso via L1/Lq regularization. One key subroutine is the L1/Lq regularized Euclidean projection.
We revealed the key theoretical properties of the L1/Lq regularized Euclidean projection, which explains why the computation for the general q is significantly more challenging than q=2 and infinity.
We proposed to efficiently compute the L1/Lq regularized Euclidean projection by solving two zero finding problems.
Fast Overlapping Group Lasso [PDF] [Bib \cite{Liu:fogl:2010}]
Jun Liu and Jieping Ye
We considered the efficient optimization of the overlapping group Lasso penalized problem.
We revealed several key properties of the proximal operator associated with the overlapping group Lasso.
We computed the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization.
An Efficient Algorithm for a Class of Fused Lasso Problems [PDF] [Code] [Bib \cite{Liu:kdd:2010}] [Poster]
Jun Liu, Lei Yuan, and Jieping Ye
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2010
The fused Lasso penalty enforces sparsity in both the coefficients and their successive differences, which is desirable for applications with features ordered in some meaningful way.
We proposed an efficient algorithm for solving this class of problems.
A key building block in each iteration is the fused Lasso signal approximator, for which we proposed a Subgradient Finding Algorithm (SFA).
The proposed SFA can 1) control the duality gap, 2) be significantly accelerated with a novel restart technique; and 3) allow the warm start.
Mining Sparse Representations: Formulations, Algorithms, and Applications [PDF] [Code] [Bib \cite{Liu:sdm:2010}]
Jun Liu, Shuiwang Ji, and Jieping Ye
SIAM Conference on Data Mining (SDM) 2010
This tutorial is on different sparse Formulations, Algorithms, and Applications.
The Group Dantzig Selector [PDF
Han Liu, Jian Zhang, Xiaoye Jiang, and Jun Liu
International Conference on Artificial Intelligence and Statistics (AISTATS) 2010
Group Dantzig Selector is a new method for high dimensional sparse regression with group structure.
We obtained improved theoretical results than Dantzig Selector, under a group restricted isometry condition.
SLEP: Sparse Learning with Efficient Projections [PDF] [Code] [Bib \cite{Liu:2009:SLEP:manual}]
Jun Liu, Shuiwang Ji, and Jieping Ye
Arizona State University 2009
This is the manual for the SLEP package developed and maintained at Arizona State University.
Multi-Task Feature Learning Via Efficient L_{2,1}-Norm Minimization [PDF] [Code] [Bib \cite{Liu:uai:2009}]
Jun Liu, Shuiwang Ji, and Jieping Ye
Conference on Uncertainty in Artificial Intelligence (UAI) 2009
One way for considering task relatedness in multi-task learning is to assume that different tasks share a common set of features.
The L_{2,1}-Norm can induce a solution with group sparsity, thus enabling feature selecting in the group manner.
We proposed several reformulations which can be solved efficiently via the Nesterov's method.
Jun Liu and Jieping Ye
International Conference on Machine Learning (ICML) 2009
The one-norm ball constraint is widely employed in sparse learning for introducing the desired sparsity.
We showed that the Euclidean projection onto the L_{1}-norm ball can be converted to a zero finding problem.
We proposed an improved bisection algorithm for finding the desired root.
Our algorithm can solve the problem with size10M in about 0.2 seconds on a personal computer.
Large-Scale Sparse Logistic Regression [PDF] [Code] [Bib \cite{Liu:kdd:2009}]
Jun Liu, Jianhui Chen, and Jieping Ye
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2009
We proposed the Lassplore algorithm for the L_{1}-norm regularized logistic regression, by using the Nesterov's method.
An adaptive line search scheme for the Nesterov's method is developed, which allows adaptively tuning the step size.
A Convex Formulation for Learning Shared Structures from Multiple Tasks [PDF
Jianhui Chen, Lei Tan, Jun Liu, and Jieping Ye
International Conference on Machine Learning (ICML) 2009
We presented an improved formulation (iASO) for multi-task learning based on the non-convex alternating structure optimization (ASO) algorithm.
The iASO, a non-convex formulation, was converted into a relaxed convex one.
We proposed an alternating optimization (cASO) algorithm which solves the convex relaxation efficiently
A theoretical condition, under which cASO can find a globally optimal solution to iASO, was given.
Mining Brain Region Connectivity for Alzheimer's Disease Study via Sparse Inverse Covariance Estimation [PDF
Liang Sun, Rinkal Patel, Jun Liu, Kewei Chen, Teresa Wu, Jing Li, Eric Reiman, and Jieping Ye
ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) 2009
We applied the sparse inverse covariance estimation to mine brain region connectivity for Alzheimer's Disease study.
Our proposed method allowed the user feedback (e.g., prior domain knowledge) to be incorporated into the estimation process.
Efficient Recovery of Jointly Sparse Vectors [PDF] [Bib \cite{Sun:nips:2009}]
Liang Sun, Jun Liu, Jianhui Chen, and Jieping Ye
Annual Conference on Neural Information Processing Systems (NIPS) 2009
Multiple Measurement Vector (MMV) is an extension of the single measurement vector model employed in standard compressive sensing.
We considered the reconstruction of sparse signals in the MMV model, in which the signal, represented as a matrix, consists of a set of jointly sparse vectors.
We proposed a new (dual) reformulation of the convex optimization problem in MMV and develop an efficient algorithm based on the prox-method.
Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data [PDF] [Code] [Bib \cite{Huang:nips:2009}]
Shuai Huang, Jing Li, Liang Sun, Jun Liu, TeresaWu, Kewei Chen, Adam Fleisher, Eric Reiman, and Jieping Ye
Annual Conference on Neural Information Processing Systems (NIPS) 2009
We reveal an important "monotone property" of the sparse inverse covariance estimation .
We studied the connectivity of Alzheimer's Disease, and obtained interesting results.
Some useful sources on this topic: