The Greedy Miser: Learning under Test-time Budgets

As machine learning algorithms enter applications in industrial settings, there is increased interest in controlling their cpu-time during testing. The cpu-time consists of the running time of the algorithm and the extraction time of the features. The latter can vary drastically when the feature set is diverse. In this paper, we propose an algorithm, the Greedy Miser, that incorporates the feature extraction cost during training to explicitly minimize the cpu-time during testing. The algorithm is a straightforward extension of stagewise regression and is equally suitable for regression or multi-class classification. Compared to prior work, it is significantly more cost-effective and scales to larger data sets.

• Publication year

  2012

• Venue

  International Conference on Machine Learning

• Publication date

  2012-06-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1206.6451
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• SpeedBoost: Anytime Prediction with Uniform Near-Optimality

  2012cited by this paper
• Classifier Cascade for Minimizing Feature Evaluation Cost

  2012cited by this paper
• Active Classification based on Value of Classifier

  2011cited by this paper
• Using classifier cascades for scalable e-mail classification

  2011cited by this paper
• Joint Cascade Optimization Using A Product Of Boosted Classifiers

  2010cited by this paper
• Object Bank: A High-Level Image Representation for Scene Classification & Semantic Feature Sparsification

  2010cited by this paper
• Exploiting site-level information to improve web search

  2010cited by this paper
• Early exit optimizations for additive machine learned ranking systems

  2010influential reference
• Designing efficient cascaded classifiers: tradeoff between accuracy and cost

  2010cited by this paper
• Yahoo! Learning to Rank Challenge Overview

  2010cited by this paper
• Boosting Classifier Cascades

  2010cited by this paper
• Boosted multi-task learning

  2010cited by this paper
• Feature hashing for large scale multitask learning

  2009cited by this paper
• A General Boosting Method and its Application to Learning Ranking Functions for Web Search

  2007cited by this paper
• Joint Optimization of Cascaded Classifiers for Computer Aided Detection

  2007cited by this paper
• Beyond Bags of Features: Spatial Pyramid Matching for Recognizing Natural Scene Categories

  2006cited by this paper
• Boosting as a Regularized Path to a Maximum Margin Classifier

  2004cited by this paper
• The Elements of Statistical Learning

  2003cited by this paper
• Cumulated gain-based evaluation of IR techniques

  2002cited by this paper
• Robust Real-Time Face Detection

  2001cited by this paper
• Robust Real-time Object Detection

  2001cited by this paper
• Greedy function approximation: A gradient boosting machine.

  2001influential reference
• The Kernel Trick for Distances

  2000cited by this paper
• A Brief Introduction to Boosting

  1999cited by this paper
• Finding Naked People

  1996cited by this paper
• Classification and regression trees

  1983cited by this paper

• A Survey on Active Feature Acquisition Strategies

  2025cites this paper
• Learning to Inference Adaptively for Multimodal Large Language Models

  2025cites this paper
• Stochastic Encodings for Active Feature Acquisition

  2025cites this paper
• Beyond Linear Probes: Dynamic Safety Monitoring for Language Models

  2025cites this paper
• Scalable Interactive Machine Learning for Future Command and Control

  2024cites this paper
• AIM: Adaptive Inference of Multi-Modal LLMs via Token Merging and Pruning

  2024cites this paper
• Active feature elicitation: An unified framework

  2023cites this paper
• Machine Learning in Real-Time Internet of Things (IoT) Systems: A Survey

  2022cites this paper
• Budgeted Classification with Rejection: An Evolutionary Method with Multiple Objectives

  2022influential citation
• Minimizing Compute Costs: When Should We Run More Expensive Malware Analysis?

  2022cites this paper
• To Predict or Not to Predict: The Case of the Emergency Department

  2021cites this paper
• Large-scale Cost-Aware Classification Using Feature Computational Dependency Graph

  2021cites this paper
• The Expando-Mono-Duo Design Pattern for Text Ranking with Pretrained Sequence-to-Sequence Models

  2021cites this paper
• Evolutionary Optimization of High-Coverage Budgeted Classifiers

  2021influential citation
• Cost Aware Feature Elicitation

  2020cites this paper
• Implications on Feature Detection When Using the Benefit–Cost Ratio

  2020cites this paper
• Adaptive covariate acquisition for minimizing total cost of classification

  2020influential citation
• Orthogonalized SGD and Nested Architectures for Anytime Neural Networks

  2020cites this paper
• Pretrained Transformers for Text Ranking: BERT and Beyond

  2020cites this paper
• Knowledge-infused Mining and Learning for Social Impact Editors :

  2020cites this paper
• Test-Cost Sensitive Ensemble of Classifiers Using Reinforcement Learning

  2020cites this paper
• ResOT: Resource-Efficient Oblique Trees for Neural Signal Classification

  2020cites this paper
• Neural Speed Reading Audited

  2020cites this paper
• A Clustering based Selection Framework for Cost Aware and Test-time Feature Elicitation

  2020cites this paper
• Interpretable & Time-Budget-Constrained Contextualization for Re-Ranking

  2020cites this paper
• Multi-Stage Document Ranking with BERT

  2019cites this paper
• Opportunistic Learning: Budgeted Cost-Sensitive Learning from Data Streams

  2019cites this paper
• Gradient Regularized Budgeted Boosting

  2019influential citation
• Joint Optimization of Cascade Ranking Models

  2019cites this paper
• Cost-Sensitive Diagnosis and Learning Leveraging Public Health Data.

  2019cites this paper
• Datasets for Business and Consumer Analytics

  2019cites this paper
• Cost aware Inference for IoT Devices

  2019cites this paper
• Nutrition and Health Data for Cost-Sensitive Learning

  2019cites this paper
• Classification with costly features in hierarchical deep sets

  2019cites this paper
• Better Never Than Late: Timely Edge Video Analytics Over the Air

  2019cites this paper
• Hardware-Efficient Seizure Detection

  2019cites this paper
• A Variable Importance Measure for a Cost Sensitive Random forest Predition on a Budget.

  2019cites this paper
• Cost-Sensitive Feature-Value Acquisition Using Feature Relevance

  2019influential citation
• ALERT: Accurate Anytime Learning for Energy and Timeliness

  2019cites this paper
• Classification with costly features as a sequential decision-making problem

  2019cites this paper
• Learning to Rank in Theory and Practice: From Gradient Boosting to Neural Networks and Unbiased Learning

  2019cites this paper
• Anytime Stereo Image Depth Estimation on Mobile Devices

  2018cites this paper
• Prediction-time Efficient Classification Using Feature Computational Dependencies

  2018influential citation
• Dynamic Feature Acquisition Using Denoising Autoencoders

  2018influential citation
• Efficient Test-Time Predictor Learning With Group-Based Budget

  2018influential citation
• Assessment of metal ion concentration in water with structured feature selection.

  2017cites this paper
• Sequential Dynamic Decision Making with Deep Neural Nets on a Test-Time Budget

  2017cites this paper
• Dynamic Model Selection for Prediction Under a Budget

  2017influential citation
• Learning Anytime Predictions in Neural Networks via Adaptive Loss Balancing

  2017cites this paper
• Cost efficient gradient boosting

  2017influential citation
• Classification with Costly Features using Deep Reinforcement Learning

  2017cites this paper
• Field of Groves: An Energy-Efficient Random Forest

  2017cites this paper
• Adaptive Classification for Prediction Under a Budget

  2017cites this paper
• Multi-Scale Dense Convolutional Networks for Efficient Prediction

  2017cites this paper
• Learning to Rank Using Localized Geometric Mean Metrics

  2017cites this paper
• Instance Specific Discriminative Modal Pursuit: A Serialized Approach

  2017cites this paper
• Resource-efficient Machine Learning in 2 KB RAM for the Internet of Things

  2017cites this paper
• Problems in Learning under Limited Resources and Information

  2017cites this paper
• Machine learning under budget constraints

  2017cites this paper
• Finding Heavily-Weighted Features in Data Streams

  2017cites this paper
• The cascading neural network: building the Internet of Smart Things

  2017cites this paper
• Multi-Scale Dense Networks for Resource Efficient Image Classification

  2017cites this paper
• Learning in the Real World: Constraints on Cost, Space, and Privacy

  2016cites this paper
• A Task-Oriented Approach for Cost-Sensitive Recognition

  2016cites this paper
• Learning Dynamic Hierarchical Models for Anytime Scene Labeling

  2016cites this paper
• Learning Tree-Structured Detection Cascades for Heterogeneous Networks of Embedded Devices

  2016cites this paper
• Optimally Pruning Decision Tree Ensembles With Feature Cost

  2016cites this paper
• Trading-Off Cost of Deployment Versus Accuracy in Learning Predictive Models

  2016cites this paper
• Impatient DNNs - Deep Neural Networks with Dynamic Time Budgets

  2016cites this paper
• How to Allocate Resources For Features Acquisition?

  2016cites this paper
• Pruning Random Forests for Prediction on a Budget

  2016cites this paper
• Semantic proximity search on graphs with metagraph-based learning

  2016cites this paper
• Fast Ranking with Additive Ensembles of Oblivious and Non-Oblivious Regression Trees

  2016cites this paper
• Sequential Cost-Sensitive Feature Acquisition

  2016influential citation
• Generalized BROOF-L2R: A General Framework for Learning to Rank Based on Boosting and Random Forests

  2016cites this paper
• Recurrent Neural Networks for Adaptive Feature Acquisition

  2016cites this paper
• Learning with Scalability and Compactness

  2016cites this paper
• OTIMIZANDO MODELOS DE APRENDIZADO DE RANQUEAMENTO COM BASE EM AGREGAÇÃO DE ÁRVORES DE DECISÃO

  2016cites this paper
• R 4-B . 3 : Advanced Automated Target Recognition ( ATR ) in Security Imaging

  2015cites this paper
• Training-Time Optimization of a Budgeted Booster

  2015cites this paper
• QuickScorer: A Fast Algorithm to Rank Documents with Additive Ensembles of Regression Trees

  2015cites this paper
• Efficient Lasso training from a geometrical perspective

  2015cites this paper
• Sensor Selection by Linear Programming

  2015cites this paper
• AskWorld: Budget-Sensitive Query Evaluation for Knowledge-on-Demand

  2015influential citation
• A cross-benchmark comparison of 87 learning to rank methods

  2015cites this paper
• Efficient Learning by Directed Acyclic Graph For Resource Constrained Prediction

  2015cites this paper
• Feature-Budgeted Random Forest

  2015cites this paper
• Feature Cost Sensitive Random Forest

  2015influential citation
• Adaptive Algorithms for Online Convex Optimization with Long-term Constraints

  2015cites this paper
• Gradient boosted feature selection

  2014cites this paper
• Supervised Machine Learning Under Test-Time Resource Constraints: A Trade-off Between Accuracy and Cost

  2014influential citation
• Anytime Prediction: Efficient Ensemble Methods for Any Computational Budget

  2014influential citation
• Fast margin-based cost-sensitive classification

  2014cites this paper
• Master's thesis Computer Science (Chair: Databases, Track: Information System Engineering) Faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS) Scaling Learning to Rank to Big Data

  2014cites this paper
• Anytime Recognition of Objects and Scenes

  2014cites this paper
• A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing

  2014cites this paper
• Scaling Learning to Rank to Big Data: Using MapReduce to Parallelise Learning to Rank

  2014cites this paper
• Modeling Algorithm Performance on Highly-threaded Many-core Architectures

  2014cites this paper
• Learning to efficiently rank on big data

  2014cites this paper
• Speeding Up Tracking by Ignoring Features

  2014cites this paper