Motivation:

This problem has gained attention in several communities including machine learning (ML), signal processing (SP), information theory (IT), and computer science (CS). In ML it has also been referred to as resource constraint learning (and “test-time cost sensitive learning”) and has often been addressed with classifier cascades (e.g. Viola and Jones, 2004). In IT and SP this problem has been referred to as controlled sensing where the goal is to adaptively manage and control multiple degrees of freedom in an information-gathering systems to fulfill the goal of different inference tasks. This problem has been referred to as the discrete function evaluation problem in CS, with the goal of identifying distinct classes from a set of objects while minimizing the cost of testing to differentiate between objects.

Learning and decision-making problems under budget constraints arise in particular in real-world industrial applications ranging from medical diagnosis, to 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 enabled 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.

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.

All settings have in common that they introduce a new trade-off 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. In addition, we aim to supply benchmark datasets (which are typically hard to obtain) and encourage participants to evaluate and compare their novel algorithms.

In this workshop, we plan to focus on two special themes:

1. budgeted learning with approximately submodular function optimization. Submodular functions are a special class of set functions that exhibit diminishing returns. Often, the ‘quality’ of a set of features is well-modeled by a submodular function. In the budgeted setting, one aims to maximize this quality subject to a modular (linear) feature cost constraint. In general, maximizing a submodular set function subject to a modular constraint is NP hard. However, lots of prior work has been done on greedy constant-factor approximation algorithms. Approximate submodular analysis has been applied to the development and analysis of greedy algorithms to learn decision trees and minimize classification loss. 

2. applications of resource efficient learning. Publications in resource efficient learning are often motivated by their applicability in real world applications. However it is unclear if algorithms from the ICML/NIPS community are really used in practice. In order to stay relevant, we want to make an explicit effort to connect the research community with practitioners in industry, health-care and other application settings. Hopefully this will help both sides to understand the limitations and opportunities within this exciting field of research.