Source-linked AI summary
The Greedy Miser: Learning under Test-time Budgets
Zhixiang Xu, Kilian Weinberger, Olivier Chapelle
TL;DR
Industrial machine learning applications face a test-time tradeoff between predictive accuracy and computation, including feature extraction costs. Greedy Miser incorporates those costs during training through a stage-wise regression extension. It reports matching unconstrained-baseline accuracy with an order-of-magnitude reduction in test-time cost, while scaling to large datasets.
Problem
Industrial test-time use requires balancing accuracy against computation, which includes both algorithm runtime and feature extraction.
Source: §1 · p. 1Method
Results
Greedy Miser matches unconstrained-baseline accuracy while reducing test-time cost by an order of magnitude across scene recognition and web-search ranking.
Source: §1 · p. 1Takeaways & Limitations
The Greedy Miser is a simple stage-wise regression extension that scales to large datasets and outperforms previously most cost-effective classifiers.
Source: §7 · p. 8
Abstract
from arXiv · showhide
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 stage-wise 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.
1. Introduction
Industrial test-time use creates an accuracy-versus-computation tradeoff involving both algorithm runtime and feature extraction. Greedy Miser incorporates feature costs during training and reports matching unconstrained accuracy with an order-of-magnitude reduction in test-time cost.
1. Introduction
- Test-time computation includes algorithm runtime and feature extraction, and a 1-second increase per run at 10 million daily runs would require 58 additional CPU-days per day.The motivating example pairs a 3% accuracy improvement with the additional second per execution.Source: §1 · p. 1
- Greedy Miser incorporates feature extraction costs during training to make the accuracy-cost tradeoff explicit and minimize test-time CPU usage.The paper relaxes a non-continuous global objective into a continuous loss and derives a greedy stage-wise regression update.Source: §1 · p. 1
- Greedy Miser matches unconstrained-baseline accuracy while reducing test-time cost by an order of magnitude across scene recognition and web-search ranking.The approach does not build classifier cascades.Source: §1 · p. 1
2. Related Work
Prior cost-sensitive methods commonly use classifier cascades, while approaches that account for individual feature costs remain distinct. Greedy Miser instead incorporates those costs into weak learners and applies naturally to regression and multiclass classification.
2. Related Work
- Earlier cost-sensitive methods include classifier cascades, including softcascades that use a global probabilistic model and are restricted to binary classification.Other cascade approaches include Adaboost for visual recognition and gradient boosting for web-search ranking.Source: §2 · p. 2
- Cronus incorporates feature extraction costs during training but constructs a cascade; Greedy Miser instead incorporates feature cost into weak learners without globally optimizing cascade stages.Cronus optimizes weak-classifier coefficients for classification error and tree or feature extraction costs at each stage.Source: §2 · p. 2
- Unlike approaches focused on cascades and individual feature costs, Greedy Miser’s stage-wise regression variant operates naturally in regression and multiclass classification.The paper describes Grubb and Bagnell (2012) as proposing a complementary approach to feature-cost-aware gradient boosting.Source: §2 · p. 2
3. Notation and Setup
The setup allows continuous or categorical labels and assigns an acquisition cost to each feature, assumed free or small on subsequent retrieval. The predictor uses a nonlinear feature mapping with limited-depth regression trees and minimizes a continuous loss within a test-time budget.
3. Notation and Setup
- Training examples have input vectors and continuous or categorical labels; each feature has an initial acquisition cost, with subsequent retrieval free or at a small cost.The examples are drawn from an unknown distribution.Source: §3 · p. 2
- The predictor is linear in a nonlinear feature mapping and aims to minimize a continuous loss within a test-time cost budget.Squared loss and multiclass log-loss are given as suitable examples.Source: §3 · p. 2
- The paper explicitly constructs its feature mapping with limited-depth regression trees, yielding a high-dimensional feature space and a correspondingly sparse weight vector.The mapping is represented by trees that split on input features.Source: §3 · p. 2
4. Method
The method frames test-time cost as tree evaluation plus feature extraction, then trains a stage-wise additive classifier to trade off loss against those costs. Greedy CART adds trees using an impurity function that penalizes the initial extraction of features.
4. Method
- Test-time cost combines evaluating selected trees with extracting every feature used by those trees.The objective includes both costs, with a predefined budget that cannot be exceeded at test time.Source: §4 · pp. 2–3
- Greedy CART builds an additive classifier by adding a limited-depth regression tree at each iteration.The trees are combined using regular stage-wise regression with a fixed step size.Source: §4 · p. 3
- The proposed impurity function approximates the negative loss gradient while penalizing feature extraction according to feature cost.An auxiliary indicator tracks whether a feature was already extracted, so its initial extraction cost is not charged again in later trees.Source: §4 · p. 3
- The Greedy Miser algorithm iteratively adds a tree chosen to minimize that impurity, then marks its used features as already extracted.It begins with an empty classifier and repeats this update for the specified number of iterations.Source: §4 · p. 3
5. Algorithm Derivation
The derivation connects the Greedy Miser to a relaxed version of the cost-constrained objective. It relaxes tree and feature costs, then uses coordinate descent to select successive trees along a budgeted solution path.
5. Algorithm Derivation
- The derivation shows that the Greedy Miser approximately solves a relaxed version of the original optimization problem.The original objective is non-continuous because its cost term uses the l0-norm.Source: §5 · p. 3, §5.1 · p. 3
5.1. Relaxation
- For tree-evaluation cost, the l0 penalty is relaxed to a rescaled l1 penalty that is exact when the scaled tree weights are binary.For feature costs, ordinary l1 would over-penalize reused features, so the derivation uses a capped penalty that behaves like l1 near zero and becomes constant at the step size.Source: §5.1 · pp. 3–4
- The relaxation splits the budget into tree-evaluation and feature-extraction budgets, applying a constraint to the former and a Lagrangian penalty to the latter.The resulting optimization problem uses separate terms for the two costs.Source: §5.1 · p. 4
5.2. Optimization
- Coordinate descent increments one weight by the step size per iteration, selecting the steepest-descent coordinate to form the solution path.The path is computed for evenly spaced tree-evaluation budgets, warm-starting each intermediate optimization from the previous solution.Source: §5.2 · p. 4
- The gradient combines the loss derivative with a feature-cost term, and its loss component can be expressed using negative derivatives with respect to current predictions.The derivation identifies the resulting quadratic form with the impurity minimized by the Greedy Miser.Source: §5.2 · pp. 4–5
- The iteration limit is tied to the tree-evaluation budget, while the feature-cost multiplier corresponds to the feature budget.The derivation assumes a sparse weight vector because the number of possible trees is extremely large relative to the iteration count; the paper sets the step size to 0.1.Source: §5.1 · p. 3, §5.2 · p. 5
6. Results
On Yahoo ranking, Miser nearly matches stage-wise regression’s ranking accuracy at one-tenth the cost and stays above Cronus and Early Exits on the cost-efficiency curve. On Scene-15, it offers a better accuracy-cost tradeoff than the baselines, while increasing the feature-cost penalty shifts selection toward cheaper features.
Experimental setup
- The evaluation covers Yahoo Learning to Rank and Scene-15; the scene experiments use 184 visual descriptors and average results over 10 random training/testing splits.Scene-15 contains 4,485 images across 15 scene classes.Source: §6 · pp. 5, 7
Yahoo Learning to Rank
- Miser nearly matches stage-wise regression’s ranking accuracy at 1/10 of the cost, while Cronus reduces cost to 1/4 and Early Exits to 1/2.The Yahoo cost-efficiency curve stays above both competing methods; increasing λ reduces test-time cost while NDCG@5 drops gradually relative to λ = 0.Source: §6 · pp. 5–6, Figure 1 · p. 6
Comparison with prior work
- Early Exit and Cronus improve stage-wise regression only modestly because feature acquisition, rather than tree computation, dominates cost; the cascade methods are complementary to Miser.Source: §6 · p. 6
Feature extraction
- As λ increases, Miser extracts fewer expensive features and reuses more cost-1 features, while cost-150-or-higher features can still be selected in early iterations.The cost-200 feature is always extracted across the illustrated λ settings.Source: §6 · pp. 6–7, Figure 2 · p. 6
Scene Recognition
- On Scene-15, Miser leads the accuracy-cost tradeoff and reaches accuracy similar to the multiple-kernel SVM at half its test-time cost.Multiple-kernel SVM and stage-wise regression require all features, increasing their test-time cost; Early Exit has limited improvement because it cannot select important expensive features early.Source: Figure 3 · p. 7, §6 · p. 7
7. Conclusion
The Greedy Miser extends stage-wise regression by incorporating feature cost during training; the authors report that it scales naturally to large data sets and outperforms previously most cost-effective classifiers. They identify combining it with early exits or cascade-based methods as future work.
7. Conclusion
- The Greedy Miser incorporates feature cost during training and outperforms previously most cost-effective classifiers.The authors describe it as a natural extension to stage-wise regression that scales to large data sets.Source: §7 · p. 8
- Future work includes combining the approach with early exits or cascade-based learning methods.The cited examples are Cambazoglu et al. (2010) and Chen et al. (2012).Source: §7 · p. 8