Timezone: »
We routinely encounter scenarios where at test-time we must predict on a budget. Feature costs in Internet, Healthcare, and Surveillance applications arise due to feature extraction time and feature/sensor acquisition~\cite{trapeznikov:2013b} costs. Data analytics applications in mobile devices are often performed on remote cloud services due to the limited device capabilities, which imposes memory/prediction time costs. Naturally, in these settings, one needs to carefully understand the trade-off between accuracy and prediction cost. Uncertainty in the observations, which is typical in such scenarios, further adds to complexity of the task and requires a careful understanding of both the uncertainty as well as accuracy-cost tradeoffs.
In this workshop, we aim to bring together researchers from various domains to discuss the key aspects of the above mentioned emerging and critical topic. The goal is to provide a platform where ML/statistics/optimization researchers can interact closely with domain experts who need to deploy ML models in resource-constrained settings (like an IoT device maker), and chart out the foundational problems in the area and key tools that can be used to solve them.
Motivation
===================
Prediction under budget constraints is a critical problem that arise in several settings like medical diagnosis, search engines and surveillance. In these applications, budget constraints arise as a result of limits on computational cost, time, network-throughput and power-consumption. For instance, in search engines CPU cost during prediction-time must be budgeted to enable business models such as online advertising. Additionally, search engines have time constraints at prediction-time as users are known to abandon the service is the response time of the search engine is not within a few tens of milliseconds. In another example, modern passenger screening systems impose constraints on throughput.
An extreme version of these problems appear in the Internet of Things (IoT) setting where one requires prediction on tiny IoT devices which might have at most 2KB of RAM and no floating point computation unit. IoT is considered to be the next multi-billion industry with “smart” devices being designed for production-line, cars, retail stores, and even for toothbrush and spoons. Given that IoT based solutions seem destined to significantly permeate our day-to-day lives, ML based predictions on the device become critical due to several reasons like privacy, battery, latency etc.
Learning under resource constraints departs from the traditional machine learning setting and introduces new exciting challenges. For instance, features are accompanied by costs (e.g. extraction time in search engines or true monetary values in medical diagnosis) and their amortized sum is constrained at test-time. Also, different search strategies in prediction can have widely varying computational costs (e.g., binary search, linear search, dynamic programming). In other settings, a system must maintain a throughput constraint to keep pace with arriving traffic.
In IoT setting, the model itself has to be deployed on a 2-16KB RAM, posing an extremely challenging constraint on the algorithm.
The common aspect of all of these settings is that we must seeks trade-offs between prediction accuracy and prediction cost. Studying this tradeoff is an inherent challenge that needs to be investigated in a principled fashion in order to invent practically relevant machine learning algorithms. This problems lies at the intersection of ML, statistics, stochastic control and information theory. We aim to draw researchers working on foundational, algorithmic and application problems within these areas. We plan on organizing a demo session which would showcase ML algorithms running live on various resource-constrained device, demonstrating their effectiveness on challenging real-world tasks. In addition, we plan to invite Ofer Dekel from Microsoft Research to present a new platform for deploying ML on tiny devices which should provide a easy way to deploy and compare various ML techniques on realistic devices and further spur multiple research directions in this area.
Author Information
Manik Varma (Microsoft Research)
Venkatesh Saligrama (Boston University)
Prateek Jain (Microsoft Research)
More from the Same Authors
-
2022 : Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 : ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 : Acting Optimistically in Choosing Safe Actions »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 : ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 : Achieving High TinyML Accuracy through Selective Cloud Interactions »
Anil Kag · Igor Fedorov · Aditya Gangrade · Paul Whatmough · Venkatesh Saligrama -
2022 : FedHeN: Federated Learning in Heterogeneous Networks »
Durmus Alp Emre Acar · Venkatesh Saligrama -
2022 Poster: Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 Spotlight: Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk »
Tianrui Chen · Aditya Gangrade · Venkatesh Saligrama -
2022 Poster: Faster Algorithms for Learning Convex Functions »
Ali Siahkamari · Durmus Alp Emre Acar · Christopher Liao · Kelly Geyer · Venkatesh Saligrama · Brian Kulis -
2022 Poster: ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 Spotlight: ActiveHedge: Hedge meets Active Learning »
Bhuvesh Kumar · Jacob Abernethy · Venkatesh Saligrama -
2022 Spotlight: Faster Algorithms for Learning Convex Functions »
Ali Siahkamari · Durmus Alp Emre Acar · Christopher Liao · Kelly Geyer · Venkatesh Saligrama · Brian Kulis -
2021 Poster: Debiasing Model Updates for Improving Personalized Federated Training »
Durmus Alp Emre Acar · Yue Zhao · Ruizhao Zhu · Ramon Matas · Matthew Mattina · Paul Whatmough · Venkatesh Saligrama -
2021 Spotlight: Debiasing Model Updates for Improving Personalized Federated Training »
Durmus Alp Emre Acar · Yue Zhao · Ruizhao Zhu · Ramon Matas · Matthew Mattina · Paul Whatmough · Venkatesh Saligrama -
2021 Poster: Memory Efficient Online Meta Learning »
Durmus Alp Emre Acar · Ruizhao Zhu · Venkatesh Saligrama -
2021 Spotlight: Memory Efficient Online Meta Learning »
Durmus Alp Emre Acar · Ruizhao Zhu · Venkatesh Saligrama -
2021 Poster: Training Recurrent Neural Networks via Forward Propagation Through Time »
Anil Kag · Venkatesh Saligrama -
2021 Spotlight: Training Recurrent Neural Networks via Forward Propagation Through Time »
Anil Kag · Venkatesh Saligrama -
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: Piecewise Linear Regression via a Difference of Convex Functions »
Ali Siahkamari · Aditya Gangrade · Brian Kulis · Venkatesh Saligrama -
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 -
2020 Poster: Minimax Rate for Learning From Pairwise Comparisons in the BTL Model »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Poster: Graph Resistance and Learning from Pairwise Comparisons »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Oral: Graph Resistance and Learning from Pairwise Comparisons »
Julien Hendrickx · Alex Olshevsky · Venkatesh Saligrama -
2019 Poster: SGD without Replacement: Sharper Rates for General Smooth Convex Functions »
Dheeraj Nagaraj · Prateek Jain · Praneeth Netrapalli -
2019 Poster: Learning Classifiers for Target Domain with Limited or No Labels »
Pengkai Zhu · Hanxiao Wang · Venkatesh Saligrama -
2019 Oral: SGD without Replacement: Sharper Rates for General Smooth Convex Functions »
Dheeraj Nagaraj · Prateek Jain · Praneeth Netrapalli -
2019 Oral: Learning Classifiers for Target Domain with Limited or No Labels »
Pengkai Zhu · Hanxiao Wang · Venkatesh Saligrama -
2018 Poster: Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers »
Yao Ma · Alex Olshevsky · Csaba Szepesvari · Venkatesh Saligrama -
2018 Oral: Gradient Descent for Sparse Rank-One Matrix Completion for Crowd-Sourced Aggregation of Sparsely Interacting Workers »
Yao Ma · Alex Olshevsky · Csaba Szepesvari · Venkatesh Saligrama -
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 Poster: ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices »
Chirag Gupta · ARUN SUGGALA · Ankit Goyal · Saurabh Goyal · Ashish Kumar · Bhargavi Paranjape · Harsha Vardhan Simhadri · Raghavendra Udupa · Manik Varma · Prateek Jain -
2017 Poster: Adaptive Neural Networks for Efficient Inference »
Tolga Bolukbasi · Joseph Wang · Ofer Dekel · Venkatesh Saligrama -
2017 Talk: ProtoNN: Compressed and Accurate kNN for Resource-scarce Devices »
Chirag Gupta · ARUN SUGGALA · Ankit Goyal · Saurabh Goyal · Ashish Kumar · Bhargavi Paranjape · Harsha Vardhan Simhadri · Raghavendra Udupa · Manik Varma · Prateek Jain -
2017 Talk: Adaptive Neural Networks for Efficient Inference »
Tolga Bolukbasi · Joseph Wang · Ofer Dekel · Venkatesh Saligrama -
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 Poster: Connected Subgraph Detection with Mirror Descent on SDPs »
Cem Aksoylar · Orecchia Lorenzo · Venkatesh Saligrama -
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: Connected Subgraph Detection with Mirror Descent on SDPs »
Cem Aksoylar · Orecchia Lorenzo · Venkatesh Saligrama -
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