The Greedy Miser: Learning under Test-time Budgets

By Zhixiang Eddie Xu, Kilian Q. Weinberger, Olivier Chapelle. 2012

123 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Pretrained Transformers for Text Ranking: BERT and Beyond (2020, background): “s, does not seem practical because it would introduce complex ordering dependencies and necessitate frequent retraining, whenever an upstream component changes. 125 can be learned [Wang et al., 2010, Xu et al., 2012], to our knowledge this is an important issue that remains unexplored in the context”
Multi-Stage Document Ranking with BERT (2019, methodology): “Given this setup, a number of researchers have proposed techniques based, for example, on boosting for composing these stages in an end-to-end manner (Wang et al., 2011; Xu et al., 2012).”
A cross-benchmark comparison of 87 learning to rank methods (2015, methodology): “…j is the index of a dataset, n the number of datasets in the comparison, i and k are indices of an algorithm, M i ( j ) is the performance of the i -th algorithm on the j -th dataset, M is a ranking measure (such as NDCG or MAP), and I { M i ( j ) > M k ( j ) } is an indicator function such that”
Multi-Scale Dense Networks for Resource Efficient Image Classification (2017, methodology): “Various prior studies explore computationally efficient variants of traditional machine-learning models (Viola & Jones, 2001; Grubb & Bagnell, 2012; Karayev et al., 2014; Trapeznikov & Saligrama, 2013; Xu et al., 2012; 2013; Nan et al., 2015; Wang et al., 2015).”
Gradient boosted feature selection (2014, unknown): “Learning”
Bayesian Optimization with Inequality Constraints (2014, methodology): “In our experiments we obtain speedups of several order of magnitudes with kernel SVM, making the algorithm by Burges & Schölkopf (1997) (with cBO) suddenly a compelling option for many practitioners who care about test-time performance (Xu et al., 2012).”
Interpretable & Time-Budget-Constrained Contextualization for Re-Ranking (2020, background): “In traditional learning-to-rank the trade-off between effectiveness and efficiency has been thoroughly studied [34, 35, 37, 4].”
Training Efficient Tree-Based Models for Document Ranking (2013, background): “[6] take advantage of tree-based models, but their work aims to minimize feature extraction costs.”
A Reduction of the Elastic Net to Support Vector Machines with an Application to GPU Computing (2014, methodology): “5 Scene15, a scene recognition data set [20, 27] where we use the binary class 6 and 7 for feature selection; PEMS [1], a dataset that describes the occupancy rate, between 0 and 1, of different car lanes of San Francisco bay area freeways.”