Timezone: »
Several real-world applications require real-time prediction on resource-scarce devices such as an Internet of Things (IoT) sensor. Such applications demand prediction models with small storage and computational complexity that do not compromise significantly on accuracy. In this work, we propose ProtoNN, a novel algorithm that addresses the problem of real-time and accurate prediction on resource-scarce devices. ProtoNN is inspired by k-Nearest Neighbor (KNN) but has several orders lower storage and prediction complexity. ProtoNN models can be deployed even on devices with puny storage and computational power (e.g. an Arduino UNO with 2kB RAM) to get excellent prediction accuracy. ProtoNN derives its strength from three key ideas: a) learning a small number of prototypes to represent the entire training set, b) sparse low dimensional projection of data, c) joint discriminative learning of the projection and prototypes with explicit model size constraint. We conduct systematic empirical evaluation of ProtoNN on a variety of supervised learning tasks (binary, multi-class, multi-label classification) and show that it gives nearly state-of-the-art prediction accuracy on resource-scarce devices while consuming several orders lower storage, and using minimal working memory.
Author Information
Chirag Gupta (Microsoft Research, India)
ARUN SUGGALA (Carnegie Mellon University)
Ankit Goyal (University of Michigan)
Saurabh Goyal (IBM India Pvt Ltd)
Ashish Kumar (Microsoft Research)
Bhargavi Paranjape (Microsoft Research)
Harsha Vardhan Simhadri (Microsoft Research)
Raghavendra Udupa (Microsoft Research)
Manik Varma (Microsoft Research)
Prateek Jain (Microsoft Research)
Related Events (a corresponding poster, oral, or spotlight)
-
2017 Poster: ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices »
Wed. Aug 9th 08:30 AM -- 12:00 PM Room Gallery #16
More from the Same Authors
-
2021 Poster: SiameseXML: Siamese Networks meet Extreme Classifiers with 100M Labels »
Kunal Dahiya · Ananye Agarwal · Deepak Saini · Gururaj K · Jian Jiao · Amit Singh · Sumeet Agarwal · Purushottam Kar · Manik Varma -
2021 Spotlight: SiameseXML: Siamese Networks meet Extreme Classifiers with 100M Labels »
Kunal Dahiya · Ananye Agarwal · Deepak Saini · Gururaj K · Jian Jiao · Amit Singh · Sumeet Agarwal · Purushottam Kar · Manik Varma -
2020 : Discussion Panel »
Krzysztof Dembczynski · Prateek Jain · Alina Beygelzimer · Inderjit Dhillon · Anna Choromanska · Maryam Majzoubi · Yashoteja Prabhu · John Langford -
2020 : Invited Talk 1 Q&A - Manik Varma »
Manik Varma -
2020 : Invited Talk 1 - DeepXML: A Framework for Deep Extreme Multi-label Learning - Manik Varma »
Manik Varma -
2020 : Introduction to Extreme Classification »
Manik Varma · Yashoteja Prabhu -
2020 Poster: Soft Threshold Weight Reparameterization for Learnable Sparsity »
Aditya Kusupati · Vivek Ramanujan · Raghav Somani · Mitchell Wortsman · Prateek Jain · Sham Kakade · Ali Farhadi -
2020 Poster: Optimization and Analysis of the pAp@k Metric for Recommender Systems »
Gaurush Hiranandani · Warut Vijitbenjaronk · Sanmi Koyejo · Prateek Jain -
2020 Poster: DROCC: Deep Robust One-Class Classification »
Sachin Goyal · Aditi Raghunathan · Moksh Jain · Harsha Vardhan Simhadri · Prateek Jain -
2019 Poster: SGD without Replacement: Sharper Rates for General Smooth Convex Functions »
Dheeraj Nagaraj · Prateek Jain · Praneeth Netrapalli -
2019 Oral: SGD without Replacement: Sharper Rates for General Smooth Convex Functions »
Dheeraj Nagaraj · Prateek Jain · Praneeth Netrapalli -
2018 Poster: Differentially Private Matrix Completion Revisited »
Prateek Jain · Om Dipakbhai Thakkar · Abhradeep Thakurta -
2018 Oral: Differentially Private Matrix Completion Revisited »
Prateek Jain · Om Dipakbhai Thakkar · Abhradeep Thakurta -
2017 Workshop: ML on a budget: IoT, Mobile and other tiny-ML applications »
Manik Varma · Venkatesh Saligrama · Prateek Jain -
2017 Poster: Resource-efficient Machine Learning in 2 KB RAM for the Internet of Things »
Ashish Kumar · Saurabh Goyal · Manik Varma -
2017 Poster: Recovery Guarantees for One-hidden-layer Neural Networks »
Kai Zhong · Zhao Song · Prateek Jain · Peter Bartlett · Inderjit Dhillon -
2017 Poster: Nearly Optimal Robust Matrix Completion »
Yeshwanth Cherapanamjeri · Prateek Jain · Kartik Gupta -
2017 Poster: Active Heteroscedastic Regression »
Kamalika Chaudhuri · Prateek Jain · Nagarajan Natarajan -
2017 Talk: Active Heteroscedastic Regression »
Kamalika Chaudhuri · Prateek Jain · Nagarajan Natarajan -
2017 Talk: Nearly Optimal Robust Matrix Completion »
Yeshwanth Cherapanamjeri · Prateek Jain · Kartik Gupta -
2017 Talk: Recovery Guarantees for One-hidden-layer Neural Networks »
Kai Zhong · Zhao Song · Prateek Jain · Peter Bartlett · Inderjit Dhillon -
2017 Talk: Resource-efficient Machine Learning in 2 KB RAM for the Internet of Things »
Ashish Kumar · Saurabh Goyal · Manik Varma