Timezone: »
Poster
Regret Bounds for Non-decomposable Metrics with Missing Labels
Nagarajan Natarajan · Prateek Jain
We consider the problem of recommending relevant labels (items) for a given data point (user). In particular, we are interested in the practically important setting where the evaluation is with respect to non-decomposable (over labels) performance metrics like the $F_1$ measure, \emph{and} training data has missing labels. To this end, we propose a generic framework that given a performance metric $\Psi$, can devise a regularized objective function and a threshold such that all the values in the predicted score vector above and only above the threshold are selected to be positive. We show that the regret or generalization error in the given metric $\Psi$ is bounded ultimately by estimation error of certain underlying parameters. In particular, we derive regret bounds under three popular settings: a) collaborative filtering, b) multilabel classification, and c) PU (positive-unlabeled) learning. For each of the above problems, we can obtain precise non-asymptotic regret bound which is small even when a large fraction of labels is missing. Our empirical results on synthetic and benchmark datasets demonstrate that by explicitly modeling for missing labels and optimizing the desired performance metric, our algorithm indeed achieves significantly better performance (like $F_1$ score) when compared to methods that do not model missing label information carefully.
Author Information
Nagarajan Natarajan (Microsoft Research)
Prateek Jain (Microsoft Research)
More from the Same Authors
-
2019 Poster: Provable Non-linear Inductive Matrix Completion »
Kai Zhong · Zhao Song · Prateek Jain · Inderjit Dhillon -
2019 Poster: Efficient Algorithms for Smooth Minimax Optimization »
Kiran Thekumparampil · Prateek Jain · Praneeth Netrapalli · Sewoong Oh -
2019 Poster: Shallow RNN: Accurate Time-series Classification on Resource Constrained Devices »
Don Dennis · Durmus Alp Emre Acar · Vikram Mandikal · Vinu Sankar Sadasivan · Venkatesh Saligrama · Harsha Vardhan Simhadri · Prateek Jain -
2018 Workshop: 2nd Workshop on Machine Learning on the Phone and other Consumer Devices (MLPCD 2) »
Sujith Ravi · Wei Chai · Yangqing Jia · Hrishikesh Aradhye · Prateek Jain -
2018 Poster: Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds »
Raghav Somani · Chirag Gupta · Prateek Jain · Praneeth Netrapalli -
2018 Spotlight: Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds »
Raghav Somani · Chirag Gupta · Prateek Jain · Praneeth Netrapalli -
2018 Poster: FastGRNN: A Fast, Accurate, Stable and Tiny Kilobyte Sized Gated Recurrent Neural Network »
Aditya Kusupati · Manish Singh · Kush Bhatia · Ashish Kumar · Prateek Jain · Manik Varma -
2018 Poster: Multiple Instance Learning for Efficient Sequential Data Classification on Resource-constrained Devices »
Don Dennis · Chirag Pabbaraju · Harsha Vardhan Simhadri · Prateek Jain -
2017 Poster: Learning Mixture of Gaussians with Streaming Data »
Aditi Raghunathan · Prateek Jain · Ravishankar Krishnawamy -
2017 Poster: Consistent Robust Regression »
Kush Bhatia · Prateek Jain · Parameswaran Kamalaruban · Purushottam Kar -
2016 Workshop: Learning in High Dimensions with Structure »
Nikhil Rao · Prateek Jain · Hsiang-Fu Yu · Ming Yuan · Francis Bach -
2016 Poster: Structured Sparse Regression via Greedy Hard Thresholding »
Prateek Jain · Nikhil Rao · Inderjit Dhillon -
2016 Poster: Selective inference for group-sparse linear models »
Fan Yang · Rina Barber · Prateek Jain · John Lafferty -
2016 Poster: Mixed Linear Regression with Multiple Components »
Kai Zhong · Prateek Jain · Inderjit Dhillon -
2015 Poster: Robust Regression via Hard Thresholding »
Kush Bhatia · Prateek Jain · Purushottam Kar -
2015 Poster: Sparse Local Embeddings for Extreme Multi-label Classification »
Kush Bhatia · Himanshu Jain · Purushottam Kar · Manik Varma · Prateek Jain -
2015 Poster: Predtron: A Family of Online Algorithms for General Prediction Problems »
Prateek Jain · Nagarajan Natarajan · Ambuj Tewari -
2015 Poster: Consistent Multilabel Classification »
Oluwasanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2015 Poster: Alternating Minimization for Regression Problems with Vector-valued Outputs »
Prateek Jain · Ambuj Tewari -
2014 Poster: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Poster: Non-convex Robust PCA »
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain -
2014 Poster: Provable Tensor Factorization with Missing Data »
Prateek Jain · Sewoong Oh -
2014 Spotlight: Consistent Binary Classification with Generalized Performance Metrics »
Sanmi Koyejo · Nagarajan Natarajan · Pradeep Ravikumar · Inderjit Dhillon -
2014 Spotlight: Non-convex Robust PCA »
Praneeth Netrapalli · Niranjan Uma Naresh · Sujay Sanghavi · Animashree Anandkumar · Prateek Jain -
2014 Poster: Provable Submodular Minimization using Wolfe's Algorithm »
Deeparnab Chakrabarty · Prateek Jain · Pravesh Kothari -
2014 Poster: Online and Stochastic Gradient Methods for Non-decomposable Loss Functions »
Purushottam Kar · Harikrishna Narasimhan · Prateek Jain -
2014 Oral: Provable Submodular Minimization using Wolfe's Algorithm »
Deeparnab Chakrabarty · Prateek Jain · Pravesh Kothari -
2014 Poster: On Iterative Hard Thresholding Methods for High-dimensional M-Estimation »
Prateek Jain · Ambuj Tewari · Purushottam Kar -
2013 Poster: Learning with Noisy Labels »
Nagarajan Natarajan · Inderjit Dhillon · Pradeep Ravikumar · Ambuj Tewari -
2013 Poster: Phase Retrieval using Alternating Minimization »
Praneeth Netrapalli · Prateek Jain · Sujay Sanghavi -
2013 Poster: Memory Limited, Streaming PCA »
Ioannis Mitliagkas · Constantine Caramanis · Prateek Jain -
2012 Poster: Multilabel Classification using Bayesian Compressed Sensing »
Ashish Kapoor · Raajay Viswanathan · Prateek Jain -
2012 Poster: Supervised Learning with Similarity Functions »
Purushottam Kar · Prateek Jain -
2011 Poster: Orthogonal Matching Pursuit with Replacement »
Prateek Jain · Ambuj Tewari · Inderjit Dhillon -
2011 Poster: Similarity-based Learning via Data Driven Embeddings »
Purushottam Kar · Prateek Jain -
2010 Spotlight: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Poster: Guaranteed Rank Minimization via Singular Value Projection »
Prateek Jain · Raghu Meka · Inderjit Dhillon -
2010 Spotlight: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2010 Poster: Inductive Regularized Learning of Kernel Functions »
Prateek Jain · Brian Kulis · Inderjit Dhillon -
2010 Poster: Hashing Hyperplane Queries to Near Points with Applications to Large-Scale Active Learning »
Prateek Jain · Sudheendra Vijayanarasimhan · Kristen Grauman -
2009 Poster: Matrix Completion from Power-Law Distributed Samples »
Raghu Meka · Prateek Jain · Inderjit Dhillon -
2008 Poster: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman -
2008 Oral: Online Metric Learning and Fast Similarity Search »
Prateek Jain · Brian Kulis · Inderjit Dhillon · Kristen Grauman