Timezone: »
Selecting a small informative subset from a given dataset, also called column sampling, has drawn much attention in machine learning. For incorporating structured data information into column sampling, research efforts were devoted to the cases where data points are fitted with clusters, simplices, or general convex hulls. This paper aims to study nonconvex hull learning which has rarely been investigated in the literature. In order to learn data-adaptive nonconvex hulls, a novel approach is proposed based on a graph-theoretic measure that leverages graph cycles to characterize the structural complexities of input data points. Employing this measure, we present a greedy algorithmic framework, dubbed Zeta Hulls, to perform structured column sampling. The process of pursuing a Zeta hull involves the computation of matrix inverse. To accelerate the matrix inversion computation and reduce its space complexity as well, we exploit a low-rank approximation to the graph adjacency matrix by using an efficient anchor graph technique. Extensive experimental results show that data representation learned by Zeta Hulls can achieve state-of-the-art accuracy in text and image classification tasks.
Author Information
Yuanjun Xiong (The Chinese University of Hong Kong)
Wei Liu (Tencent)
Deli Zhao (Xiaomi AI Lab)
Xiaoou Tang (Chinese University of Hong Kong)
More from the Same Authors
-
2022 Poster: Rank Diminishing in Deep Neural Networks »
Ruili Feng · Kecheng Zheng · Yukun Huang · Deli Zhao · Michael Jordan · Zheng-Jun Zha -
2022 Spotlight: Lightning Talks 6A-4 »
Xiu-Shen Wei · Konstantina Dritsa · Guillaume Huguet · ABHRA CHAUDHURI · Zhenbin Wang · Kevin Qinghong Lin · Yutong Chen · Jianan Zhou · Yongsen Mao · Junwei Liang · Jinpeng Wang · Mao Ye · Yiming Zhang · Aikaterini Thoma · H.-Y. Xu · Daniel Sumner Magruder · Enwei Zhang · Jianing Zhu · Ronglai Zuo · Massimiliano Mancini · Hanxiao Jiang · Jun Zhang · Fangyun Wei · Faen Zhang · Ioannis Pavlopoulos · Zeynep Akata · Xiatian Zhu · Jingfeng ZHANG · Alexander Tong · Mattia Soldan · Chunhua Shen · Yuxin Peng · Liuhan Peng · Michael Wray · Tongliang Liu · Anjan Dutta · Yu Wu · Oluwadamilola Fasina · Panos Louridas · Angel Chang · Manik Kuchroo · Manolis Savva · Shujie LIU · Wei Zhou · Rui Yan · Gang Niu · Liang Tian · Bo Han · Eric Z. XU · Guy Wolf · Yingying Zhu · Brian Mak · Difei Gao · Masashi Sugiyama · Smita Krishnaswamy · Rong-Cheng Tu · Wenzhe Zhao · Weijie Kong · Chengfei Cai · WANG HongFa · Dima Damen · Bernard Ghanem · Wei Liu · Mike Zheng Shou -
2022 Spotlight: Egocentric Video-Language Pretraining »
Kevin Qinghong Lin · Jinpeng Wang · Mattia Soldan · Michael Wray · Rui Yan · Eric Z. XU · Difei Gao · Rong-Cheng Tu · Wenzhe Zhao · Weijie Kong · Chengfei Cai · WANG HongFa · Dima Damen · Bernard Ghanem · Wei Liu · Mike Zheng Shou -
2022 Spotlight: Improving 3D-aware Image Synthesis with A Geometry-aware Discriminator »
Zifan Shi · Yinghao Xu · Yujun Shen · Deli Zhao · Qifeng Chen · Dit-Yan Yeung -
2022 Spotlight: Lightning Talks 5B-1 »
Devansh Arpit · Xiaojun Xu · Zifan Shi · Ivan Skorokhodov · Shayan Shekarforoush · Zhan Tong · Yiqun Wang · Shichong Peng · Linyi Li · Ivan Skorokhodov · Huan Wang · Yibing Song · David Lindell · Yinghao Xu · Seyed Alireza Moazenipourasil · Sergey Tulyakov · Peter Wonka · Yiqun Wang · Ke Li · David Fleet · Yujun Shen · Yingbo Zhou · Bo Li · Jue Wang · Peter Wonka · Marcus Brubaker · Caiming Xiong · Limin Wang · Deli Zhao · Qifeng Chen · Dit-Yan Yeung -
2022 Poster: Egocentric Video-Language Pretraining »
Kevin Qinghong Lin · Jinpeng Wang · Mattia Soldan · Michael Wray · Rui Yan · Eric Z. XU · Difei Gao · Rong-Cheng Tu · Wenzhe Zhao · Weijie Kong · Chengfei Cai · WANG HongFa · Dima Damen · Bernard Ghanem · Wei Liu · Mike Zheng Shou -
2022 Poster: Improving 3D-aware Image Synthesis with A Geometry-aware Discriminator »
Zifan Shi · Yinghao Xu · Yujun Shen · Deli Zhao · Qifeng Chen · Dit-Yan Yeung -
2022 Poster: Improving GANs with A Dynamic Discriminator »
Ceyuan Yang · Yujun Shen · Yinghao Xu · Deli Zhao · Bo Dai · Bolei Zhou -
2021 Poster: Low-Rank Subspaces in GANs »
Jiapeng Zhu · Ruili Feng · Yujun Shen · Deli Zhao · Zheng-Jun Zha · Jingren Zhou · Qifeng Chen -
2021 Poster: Neural Routing by Memory »
Kaipeng Zhang · Zhenqiang Li · Zhifeng Li · Wei Liu · Yoichi Sato -
2021 Poster: Generalized and Discriminative Few-Shot Object Detection via SVD-Dictionary Enhancement »
Aming WU · Suqi Zhao · Cheng Deng · Wei Liu -
2020 Poster: Towards Playing Full MOBA Games with Deep Reinforcement Learning »
Deheng Ye · Guibin Chen · Wen Zhang · Sheng Chen · Bo Yuan · Bo Liu · Jia Chen · Zhao Liu · Fuhao Qiu · Hongsheng Yu · Yinyuting Yin · Bei Shi · Liang Wang · Tengfei Shi · Qiang Fu · Wei Yang · Lanxiao Huang · Wei Liu -
2020 Poster: Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies »
Yuehua Zhu · Muli Yang · Cheng Deng · Wei Liu -
2020 Poster: Optimal Epoch Stochastic Gradient Descent Ascent Methods for Min-Max Optimization »
Yan Yan · Yi Xu · Qihang Lin · Wei Liu · Tianbao Yang -
2020 Spotlight: Fewer is More: A Deep Graph Metric Learning Perspective Using Fewer Proxies »
Yuehua Zhu · Muli Yang · Cheng Deng · Wei Liu -
2020 Poster: Adversarial Learning for Robust Deep Clustering »
Xu Yang · Cheng Deng · Kun Wei · Junchi Yan · Wei Liu -
2019 Poster: Semantic Conditioned Dynamic Modulation for Temporal Sentence Grounding in Videos »
Yitian Yuan · Lin Ma · Jingwen Wang · Wei Liu · Wenwu Zhu -
2019 Poster: Cross-Modal Learning with Adversarial Samples »
CHAO LI · Shangqian Gao · Cheng Deng · De Xie · Wei Liu -
2019 Poster: Category Anchor-Guided Unsupervised Domain Adaptation for Semantic Segmentation »
Qiming ZHANG · Jing Zhang · Wei Liu · Dacheng Tao -
2018 Poster: Nonlocal Neural Networks, Nonlocal Diffusion and Nonlocal Modeling »
Yunzhe Tao · Qi Sun · Qiang Du · Wei Liu -
2018 Poster: Generalizing Graph Matching beyond Quadratic Assignment Model »
Tianshu Yu · Junchi Yan · Yilin Wang · Wei Liu · baoxin Li -
2018 Poster: Deep Non-Blind Deconvolution via Generalized Low-Rank Approximation »
Wenqi Ren · Jiawei Zhang · Lin Ma · Jinshan Pan · Xiaochun Cao · Wangmeng Zuo · Wei Liu · Ming-Hsuan Yang -
2018 Poster: Distilled Wasserstein Learning for Word Embedding and Topic Modeling »
Hongteng Xu · Wenlin Wang · Wei Liu · Lawrence Carin -
2018 Poster: DeepExposure: Learning to Expose Photos with Asynchronously Reinforced Adversarial Learning »
Runsheng Yu · Wenyu Liu · Yasen Zhang · Zhi Qu · Deli Zhao · Bo Zhang -
2018 Poster: Parsimonious Quantile Regression of Financial Asset Tail Dynamics via Sequential Learning »
Xing Yan · Weizhong Zhang · Lin Ma · Wei Liu · Qi Wu -
2017 Poster: Geometric Descent Method for Convex Composite Minimization »
Shixiang Chen · Shiqian Ma · Wei Liu -
2017 Poster: Mixture-Rank Matrix Approximation for Collaborative Filtering »
Dongsheng Li · Chao Chen · Wei Liu · Tun Lu · Ning Gu · Stephen Chu -
2016 Poster: Local Similarity-Aware Deep Feature Embedding »
Chen Huang · Chen Change Loy · Xiaoou Tang -
2014 Poster: Multi-View Perceptron: a Deep Model for Learning Face Identity and View Representations »
Zhenyao Zhu · Ping Luo · Xiaogang Wang · Xiaoou Tang -
2014 Poster: Discrete Graph Hashing »
Wei Liu · Cun Mu · Sanjiv Kumar · Shih-Fu Chang -
2014 Poster: Deep Learning Face Representation by Joint Identification-Verification »
Yi Sun · Yuheng Chen · Xiaogang Wang · Xiaoou Tang -
2014 Spotlight: Discrete Graph Hashing »
Wei Liu · Cun Mu · Sanjiv Kumar · Shih-Fu Chang -
2008 Poster: Cyclizing Clusters via Zeta Function of a Graph »
Deli Zhao · Xiaoou Tang