Timezone: »
Poster
Projection onto A Nonnegative Max-Heap
Jun Liu · Liang Sun · Jieping Ye
We consider the problem of computing the Euclidean projection of a vector of length $p$ onto a non-negative max-heap---an ordered tree where the values of the nodes are all nonnegative and the value of any parent node is no less than the value(s) of its child node(s). This Euclidean projection plays a building block role in the optimization problem with a non-negative max-heap constraint. Such a constraint is desirable when the features follow an ordered tree structure, that is, a given feature is selected for the given regression/classification task only if its parent node is selected. In this paper, we show that such Euclidean projection problem admits an analytical solution and we develop a top-down algorithm where the key operation is to find the so-called \emph{maximal root-tree} of the subtree rooted at each node. A naive approach for finding the maximal root-tree is to enumerate all the possible root-trees, which, however, does not scale well. We reveal several important properties of the maximal root-tree, based on which we design a bottom-up algorithm with merge for efficiently finding the maximal root-tree. The proposed algorithm has a (worst-case) linear time complexity for a sequential list, and $O(p^2)$ for a general tree. We report simulation results showing the effectiveness of the max-heap for regression with an ordered tree structure. Empirical results show that the proposed algorithm has an expected linear time complexity for many special cases including a sequential list, a full binary tree, and a tree with depth 1.
Author Information
Jun Liu (Siemens Corporate Research)
Liang Sun (Arizona State University)
Jieping Ye (Arizona State University)
Related Events (a corresponding poster, oral, or spotlight)
-
2011 Spotlight: Projection onto A Nonnegative Max-Heap »
Wed. Dec 14th 12:00 -- 12:04 PM Room
More from the Same Authors
-
2014 Poster: Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets »
Jie Wang · Jieping Ye -
2014 Spotlight: Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets »
Jie Wang · Jieping Ye -
2014 Poster: A Safe Screening Rule for Sparse Logistic Regression »
Jie Wang · Jiayu Zhou · Jun Liu · Peter Wonka · Jieping Ye -
2013 Poster: Lasso Screening Rules via Dual Polytope Projection »
Jie Wang · Jiayu Zhou · Peter Wonka · Jieping Ye -
2013 Spotlight: Lasso Screening Rules via Dual Polytope Projection »
Jie Wang · Jiayu Zhou · Peter Wonka · Jieping Ye -
2012 Poster: Multi-Stage Multi-Task Feature Learning »
Pinghua Gong · Jieping Ye · Changshui Zhang -
2012 Poster: Multi-task Vector Field Learning »
Binbin Lin · Sen Yang · Chiyuan Zhang · Jieping Ye · Xiaofei He -
2012 Spotlight: Multi-Stage Multi-Task Feature Learning »
Pinghua Gong · Jieping Ye · Changshui Zhang -
2012 Poster: Generalization Bounds for Domain Adaptation »
Chao Zhang · Jieping Ye · Lei Zhang -
2011 Poster: Clustered Multi-Task Learning Via Alternating Structure Optimization »
Jiayu Zhou · Jianhui Chen · Jieping Ye -
2011 Poster: Efficient Methods for Overlapping Group Lasso »
Lei Yuan · Jun Liu · Jieping Ye -
2011 Poster: A Two-Stage Weighting Framework for Multi-Source Domain Adaptation »
Qian Sun · Rita Chattopadhyay · Sethuraman Panchanathan · Jieping Ye -
2011 Poster: Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis »
Shuai Huang · Jing Li · Jieping Ye · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman -
2011 Spotlight: Identifying Alzheimer's Disease-Related Brain Regions from Multi-Modality Neuroimaging Data using Sparse Composite Linear Discrimination Analysis »
Shuai Huang · Jing Li · Jieping Ye · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman -
2010 Poster: Moreau-Yosida Regularization for Grouped Tree Structure Learning »
Jun Liu · Jieping Ye -
2010 Poster: Multi-Stage Dantzig Selector »
Ji Liu · Peter Wonka · Jieping Ye -
2009 Poster: Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data »
Shuai Huang · Jing Li · Liang Sun · Jun Liu · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman · Jieping Ye -
2009 Spotlight: Learning Brain Connectivity of Alzheimer's Disease from Neuroimaging Data »
Shuai Huang · Jing Li · Liang Sun · Jun Liu · Teresa Wu · Kewei Chen · Adam Fleisher · Eric Reiman · Jieping Ye -
2009 Poster: Efficient Recovery of Jointly Sparse Vectors »
Liang Sun · Jun Liu · Jianhui Chen · Jieping Ye -
2008 Poster: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2008 Spotlight: Multi-label Multiple Kernel Learning »
Shuiwang Ji · Liang Sun · Rong Jin · Jieping Ye -
2007 Poster: Discriminative K-means for Clustering »
Jieping Ye · Zheng Zhao · Mingrui Wu