Timezone: »
Poster
Speedup Matrix Completion with Side Information: Application to Multi-Label Learning
Miao Xu · Rong Jin · Zhi-Hua Zhou
Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
In standard matrix completion theory, it is required to have at least $O(n\ln^2 n)$ observed entries to perfectly recover a low-rank matrix $M$ of size $n\times n$, leading to a large number of observations when $n$ is large. In many real tasks, side information in addition to the observed entries is often available. In this work, we develop a novel theory of matrix completion that explicitly explore the side information to reduce the requirement on the number of observed entries. We show that, under appropriate conditions, with the assistance of side information matrices, the number of observed entries needed for a perfect recovery of matrix $M$ can be dramatically reduced to $O(\ln n)$. We demonstrate the effectiveness of the proposed approach for matrix completion in transductive incomplete multi-label learning.
Author Information
Miao Xu (University of Queensland/AIP)
Rong Jin (Michigan State University (MSU))
Zhi-Hua Zhou (Nanjing University)
More from the Same Authors
-
2021 Poster: Actively Identifying Causal Effects with Latent Variables Given Only Response Variable Observable »
Tian-Zuo Wang · Zhi-Hua Zhou -
2021 Poster: Dual Adaptivity: A Universal Algorithm for Minimizing the Adaptive Regret of Convex Functions »
Lijun Zhang · Guanghui Wang · Wei-Wei Tu · Wei Jiang · Zhi-Hua Zhou -
2020 Poster: Dynamic Regret of Convex and Smooth Functions »
Peng Zhao · Yu-Jie Zhang · Lijun Zhang · Zhi-Hua Zhou -
2020 Poster: An Unbiased Risk Estimator for Learning with Augmented Classes »
Yu-Jie Zhang · Peng Zhao · Lanjihong Ma · Zhi-Hua Zhou -
2020 Poster: Towards Convergence Rate Analysis of Random Forests for Classification »
Wei Gao · Zhi-Hua Zhou -
2019 Poster: Bridging Machine Learning and Logical Reasoning by Abductive Learning »
Wang-Zhou Dai · Qiuling Xu · Yang Yu · Zhi-Hua Zhou -
2019 Poster: Learning to Confuse: Generating Training Time Adversarial Data with Auto-Encoder »
Ji Feng · Qi-Zhi Cai · Zhi-Hua Zhou -
2019 Poster: A Refined Margin Distribution Analysis for Forest Representation Learning »
Shen-Huan Lyu · Liang Yang · Zhi-Hua Zhou -
2018 Poster: Adaptive Online Learning in Dynamic Environments »
Lijun Zhang · Shiyin Lu · Zhi-Hua Zhou -
2018 Poster: Multi-Layered Gradient Boosting Decision Trees »
Ji Feng · Yang Yu · Zhi-Hua Zhou -
2018 Poster: Preference Based Adaptation for Learning Objectives »
Yao-Xiang Ding · Zhi-Hua Zhou -
2018 Poster: $\ell_1$-regression with Heavy-tailed Distributions »
Lijun Zhang · Zhi-Hua Zhou -
2018 Poster: Unorganized Malicious Attacks Detection »
Ming Pang · Wei Gao · Min Tao · Zhi-Hua Zhou -
2017 Poster: Improved Dynamic Regret for Non-degenerate Functions »
Lijun Zhang · Tianbao Yang · Jinfeng Yi · Rong Jin · Zhi-Hua Zhou -
2017 Poster: Learning with Feature Evolvable Streams »
Bo-Jian Hou · Lijun Zhang · Zhi-Hua Zhou -
2017 Poster: Subset Selection under Noise »
Chao Qian · Jing-Cheng Shi · Yang Yu · Ke Tang · Zhi-Hua Zhou -
2016 Poster: What Makes Objects Similar: A Unified Multi-Metric Learning Approach »
Han-Jia Ye · De-Chuan Zhan · Xue-Min Si · Yuan Jiang · Zhi-Hua Zhou -
2015 Poster: Subset Selection by Pareto Optimization »
Chao Qian · Yang Yu · Zhi-Hua Zhou -
2014 Poster: Extracting Certainty from Uncertainty: Transductive Pairwise Classification from Pairwise Similarities »
Tianbao Yang · Rong Jin -
2014 Poster: Top Rank Optimization in Linear Time »
Nan Li · Rong Jin · Zhi-Hua Zhou -
2013 Poster: Mixed Optimization for Smooth Functions »
Mehrdad Mahdavi · Lijun Zhang · Rong Jin -
2013 Poster: Linear Convergence with Condition Number Independent Access of Full Gradients »
Lijun Zhang · Mehrdad Mahdavi · Rong Jin -
2013 Poster: Stochastic Convex Optimization with Multiple Objectives »
Mehrdad Mahdavi · Tianbao Yang · Rong Jin -
2012 Poster: Nystr{รถ}m Method vs Random Fourier Features: A Theoretical and Empirical Comparison »
Tianbao Yang · Yu-Feng Li · Mehrdad Mahdavi · Rong Jin · Zhi-Hua Zhou -
2012 Poster: Semi-Crowdsourced Clustering: Generalizing Crowd Labeling by Robust Distance Metric Learning »
Jinfeng Yi · Rong Jin · Anil K Jain · Shaili Jain -
2012 Poster: Stochastic Gradient Descent with Only One Projection »
Mehrdad Mahdavi · Tianbao Yang · Rong Jin · Shenghuo Zhu -
2010 Poster: Active Learning by Querying Informative and Representative Examples »
Sheng-Jun Huang · Rong Jin · Zhi-Hua Zhou -
2010 Poster: Multi-View Active Learning in the Non-Realizable Case »
Wei Wang · Zhi-Hua Zhou -
2010 Poster: Multi-label Multiple Kernel Learning by Stochastic Approximation: Application to Visual Object Recognition »
Serhat S Bucak · Rong Jin · Anil K Jain -
2009 Poster: Adaptive Regularization for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu · Zhirong Yang -
2009 Spotlight: Adaptive Regularization for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu · Zhirong Yang -
2009 Poster: Regularized Distance Metric Learning:Theory and Algorithm »
Rong Jin · Shijun Wang · Yang Zhou -
2009 Poster: Learning Bregman Distance Functions and Its Application for Semi-Supervised Clustering »
Lei Wu · Rong Jin · Steven Chu-Hong Hoi · Jianke Zhu · Nenghai Yu -
2009 Poster: DUOL: A Double Updating Approach for Online Learning »
Peilin Zhao · Steven Chu-Hong Hoi · Rong Jin -
2009 Poster: Learning to Rank by Optimizing NDCG Measure »
Hamed Valizadegan · Rong Jin · Ruofei Zhang · Jianchang Mao -
2009 Spotlight: Learning to Rank by Optimizing NDCG Measure »
Hamed Valizadegan · Rong Jin · Ruofei Zhang · Jianchang Mao -
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 -
2008 Poster: An Extended Level Method for Efficient Multiple Kernel Learning »
Zenglin Xu · Rong Jin · Irwin King · Michael R Lyu -
2008 Poster: Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization »
Liu Yang · Rong Jin · Rahul Sukthankar -
2008 Spotlight: Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization »
Liu Yang · Rong Jin · Rahul Sukthankar -
2007 Poster: Efficient Convex Relaxation for Transductive Support Vector Machine »
Zenglin Xu · Rong Jin · Jianke Zhu · Irwin King · Michael R Lyu -
2006 Poster: Multi-Instance Multi-Label Learning with Application to Scene Classification »
Zhi-Hua Zhou · Min-Ling Zhang -
2006 Spotlight: Multi-Instance Multi-Label Learning with Application to Scene Classification »
Zhi-Hua Zhou · Min-Ling Zhang -
2006 Poster: Generalized Maximum Margin Clustering and Unsupervised Kernel Learning »
Hamed Valizadegan · Rong Jin