NDLI: An Efficient Algorithm For Weak Hierarchical Lasso

Please wait, while we are loading the content...

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 11

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 10

Issue 4(Special Issue on SIGKDD 2014, Special Issue on BIGCHAT and Regular Papers), July 2016

Issue 3, February 2016

Mining User Development Signals for Online Community Churner Detection

Put Three and Three Together: Triangle-Driven Community Detection

Multimodal Data Mining in a Multimedia Database Based on Structured Max Margin Learning

Do Anesthesiologists Know What They Are Doing? Mining a Surgical Time-Series Database to Correlate Expert Assessment with Outcomes

Collective Graph Identification

Mining Influencers Using Information Flows in Social Streams

Toward Generalizing the Unification with Statistical Outliers: The Gradient Outlier Factor Measure

DeltaCon: Principled Massive-Graph Similarity Function with Attribution

Mining Product Adopter Information from Online Reviews for Improving Product Recommendation

Adaptive Model Rules From High-Speed Data Streams

Synchronization-Core-Based Discovery of Processes with Decomposable Cyclic Dependencies

An Efficient Algorithm For Weak Hierarchical Lasso

Issue 2, October 2015

Issue 1, July 2015

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 9

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 8

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 7

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 6

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 5

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 4

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 3

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 2

ACM Transactions on Knowledge Discovery from Data (TKDD) : Volume 1

An Efficient Algorithm For Weak Hierarchical Lasso

Content Provider	ACM Digital Library
Author	Liu, Yashu Ye, Jieping Wang, Jie
Copyright Year	2016
Abstract	Linear regression is a widely used tool in data mining and machine learning. In many applications, fitting a regression model with only linear effects may not be sufficient for predictive or explanatory purposes. One strategy that has recently received increasing attention in statistics is to include feature interactions to capture the nonlinearity in the regression model. Such model has been applied successfully in many biomedical applications. One major challenge in the use of such model is that the data dimensionality is significantly higher than the original data, resulting in the small sample size large dimension problem. Recently, weak hierarchical Lasso, a sparse interaction regression model, is proposed that produces a sparse and hierarchical structured estimator by exploiting the Lasso penalty and a set of hierarchical constraints. However, the hierarchical constraints make it a non-convex problem and the existing method finds the solution to its convex relaxation, which needs additional conditions to guarantee the hierarchical structure. In this article, we propose to directly solve the non-convex weak hierarchical Lasso by making use of the General Iterative Shrinkage and Thresholding (GIST) optimization framework, which has been shown to be efficient for solving non-convex sparse formulations. The key step in GIST is to compute a sequence of proximal operators. One of our key technical contributions is to show that the proximal operator associated with the non-convex weak hierarchical Lasso admits a closed-form solution. However, a naive approach for solving each subproblem of the proximal operator leads to a quadratic time complexity, which is not desirable for large-size problems. We have conducted extensive experiments on both synthetic and real datasets. Results show that our proposed algorithm is much more efficient and effective than its convex relaxation. To this end, we further develop an efficient algorithm for computing the subproblems with a linearithmic time complexity. In addition, we extend the technique to perform the optimization-based hierarchical testing of pairwise interactions for binary classification problems, which is essentially the proximal operator associated with weak hierarchical Lasso. Simulation studies show that the non-convex hierarchical testing framework outperforms the convex relaxation when a hierarchical structure exists between main effects and interactions.
Starting Page	1
Ending Page	24
Page Count	24
File Format	PDF
ISSN	15564681
e-ISSN	1556472X
DOI	10.1145/2791295
Volume Number	10
Issue Number	3
Journal	ACM Transactions on Knowledge Discovery from Data (TKDD)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-01-29
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sparse learning Non-convex Proximal operator Weak hierarchical Lasso
Content Type	Text
Resource Type	Article
Subject	Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An efficient algorithm for weak hierarchical lasso

Efficient Methods for Overlapping Group Lasso

Proximal methods for hierarchical sparse coding

Screening Rules for Lasso with Non-Convex Sparse Regularizers

Proximal methods for hierarchical sparse coding (2011)

A relaxed-PPA contraction method for sparse signal recovery

Convex Sparse PCA for Unsupervised Feature Learning

An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering

Sparse Signal Estimation by Maximally Sparse Convex Optimization

An Efficient Algorithm For Weak Hierarchical Lasso

Similar Documents

An efficient algorithm for weak hierarchical lasso

Efficient Methods for Overlapping Group Lasso

Proximal methods for hierarchical sparse coding

Screening Rules for Lasso with Non-Convex Sparse Regularizers

Proximal methods for hierarchical sparse coding (2011)

A relaxed-PPA contraction method for sparse signal recovery

Convex Sparse PCA for Unsupervised Feature Learning

An Efficient Smoothing Proximal Gradient Algorithm for Convex Clustering

Sparse Signal Estimation by Maximally Sparse Convex Optimization

An Efficient Algorithm For Weak Hierarchical Lasso