Source-linked AI summary
Efficient Online ML API Selection for Multi-Label Classification Tasks
Lingjiao Chen, Matei Zaharia, James Zou
TL;DR
API prices and performance vary across services and inputs, while prior FrugalML has label-count-exponential complexity and does not combine APIs’ predictions. FrugalMCT predicts API-combination accuracy from input features and labels, then uses an online selector to choose services under a budget. FrugalMCT reports substantially better prediction performance than individual APIs and adapted FrugalML, with over 60% cost reduction, as high as 98%, when matching the best commercial API and up to 8% better performance at its cost.
Problem
API prices and performance vary across services and inputs, while prior FrugalML has label-count-exponential complexity and does not combine APIs’ predictions.
Source: §1 · p. 1Method
Results
FrugalMCT reports substantially better prediction performance than individual APIs and adapted FrugalML, with over 60% cost reduction, as high as 98%, when matching the best commercial API and up to 8% better performance at its cost.
Source: §1 · p. 2Takeaways & Limitations
FrugalMCT provides an end-to-end way to adaptively select and combine multi-label APIs within a budget, with experiments reporting improvements in cost and accuracy.
Source: §6 · p. 9In practice, ˆa(x) is continuous for standard ML accuracy predictors such as logistic regressors, and the authors state that the assumption holds.
Source: §4.3 · p. 5
Abstract
from arXiv · showhide
Multi-label classification tasks such as OCR and multi-object recognition are a major focus of the growing machine learning as a service industry. While many multi-label prediction APIs are available, it is challenging for users to decide which API to use for their own data and budget, due to the heterogeneity in those APIs' price and performance. Recent work shows how to select from single-label prediction APIs. However the computation complexity of the previous approach is exponential in the number of labels and hence is not suitable for settings like OCR. In this work, we propose FrugalMCT, a principled framework that adaptively selects the APIs to use for different data in an online fashion while respecting user's budget. The API selection problem is cast as an integer linear program, which we show has a special structure that we leverage to develop an efficient online API selector with strong performance guarantees. We conduct systematic experiments using ML APIs from Google, Microsoft, Amazon, IBM, Tencent and other providers for tasks including multi-label image classification, scene text recognition and named entity recognition. Across diverse tasks, FrugalMCT can achieve over 90% cost reduction while matching the accuracy of the best single API, or up to 8% better accuracy while matching the best API's cost.
1. Introduction
FrugalMCT addresses the difficulty of selecting multi-label APIs with heterogeneous costs and performance, extending API selection to combine services per input under a budget. Experiments report substantial cost savings while matching or improving on the best commercial API’s performance.
1. Introduction
- Heterogeneous API prices and performance make it difficult to choose a service or combination that fits a user’s data and budget.The introduction gives differing API prices for image tagging and text extraction as examples.Source: §1 · p. 1
- FrugalML’s training-data demands and complexity exponential in the number of labels make it unsuitable for large-label tasks, while selecting only one API also misses gains from combining complementary predictions.The example shows two APIs’ separate label sets jointly matching the true set.Source: §1 · p. 1
- FrugalMCT estimates the accuracy of API combinations for each input, then uses an online selector to choose which APIs to call and combines their predictions.It may return a cheap base model’s predictions directly or invoke an add-on API when the estimated combined accuracy is higher.Source: §1 · pp. 1–2
- FrugalMCT’s online algorithm has provable near-optimality and low computational cost, and its trainable components can be customized for different applications.The paper presents it as the first approach to effectively select and combine multi-label ML APIs.Source: §1 · p. 2
- Over 60% cost reduction, as high as 98%, is reported when matching the best commercial API’s performance; at the best API’s cost, performance improves up to 8%.Experiments span multi-label image classification, scene text recognition, and named entity recognition.Source: §1 · p. 2
2. Related Work
The related work positions FrugalMCT among API selection, ensembles, cascades, AutoML, and resource-allocation methods. Its distinguishing focus is selecting and combining black-box multi-label APIs while jointly respecting cost budgets.
MLaaS
- Unlike FrugalML, whose complexity grows exponentially with label count and which selects one API, FrugalMCT’s complexity does not depend on label count and it can combine APIs’ outputs.The related-work discussion says combining outputs improves overall accuracy but creates additional optimization challenges.Source: §2 · pp. 2–3
Ensembles for multi-label classification
- Unlike typical multi-label ensembles, which jointly train base classifiers and focus on accuracy, FrugalMCT handles black-box APIs and enforces a cost budget.The cited ensemble methods include pruned sets, classifier chains, and random subsets.Source: §2 · p. 3
Model cascades
- FrugalMCT uses both quality scores and predicted label sets to choose an expensive add-on service, and it lets users specify budget requirements unlike standard model cascades.The approach requires solving a harder optimization problem, such as dividing budget between classes.Source: §2 · p. 3
AutoML for multi-label classification
- FrugalMCT is presented as an early AutoML approach for selecting multiple multi-label APIs, jointly optimizing prediction performance and cost.The passage describes applying AutoML to multiple ML APIs as underexplored.Source: §2 · p. 3
Multiple choice knapsack and integer programming
- The service selector can be viewed as a multiple-choice knapsack problem with the same item-cost vector per group, a structure used for a customized fast online solver.The paper frames adapting ILP methods for this application—not developing a novel knapsack solver—as its goal.Source: §2 · p. 3
3. Preliminaries
The preliminaries define the multi-label prediction task and the MLaaS services whose outputs and costs FrugalMCT uses. They also establish notation for matrices, vectors, and indicator functions.
3. Preliminaries
- The notation uses bold matrices and vectors, standard script for scalars, sets, and functions, A_i,j for a matrix entry, and 1(·) for an indicator function.Source: §3 · p. 3
- Multi-label classification assigns each data point a set of labels rather than a single label.Image tagging is given as an example, with images as inputs and tags as labels.Source: §3 · p. 3
- An MLaaS market contains K services, each returning labels with quality scores, and a cost vector c records each service’s unit price.For example, a service output can associate person and car labels with confidence scores.Source: §3 · p. 3
4. FrugalMCT Framework
FrugalMCT predicts how well API combinations will perform on each input, then selects a budget-compatible add-on service and combines its output with a base service. Its framework covers accuracy prediction, budget-aware API selection, online decision-making, and label combination.
4. FrugalMCT Framework
- FrugalMCT calls a base service, predicts each API combination’s accuracy, selects an add-on using predicted accuracy and budget, then combines the predictions.The accuracy predictor and label combiner can be customized for the application.Source: §4 · p. 4
4.1. Accuracy prediction
- The accuracy predictor maps input and base-service features to estimated combination accuracies, trained against the true accuracies of combined API outputs.The paper uses one-hot label features for bounded label sets and weighted word embeddings for unbounded sets; it uses multi-label accuracy but allows other metrics.Source: §4.1 · p. 4, §4 · p. 4
4.2. The API selection problem
- The API selector is a multiple-choice knapsack integer program that maximizes estimated average accuracy subject to a budget and one API choice per input.The base service cost is charged for every data point; the problem is NP-hard in general.Source: §4.2 · pp. 4–5
4.3. An online algorithm for FrugalMCT
- For each input, the online strategy chooses the API maximizing estimated accuracy minus a penalty-weighted add-on cost, requiring O(K) computations per round.A larger penalty favors cost, while a smaller one favors estimated accuracy.Source: §4.3 · p. 5
- The online algorithm estimates its cost-accuracy penalty from training data using a budget reduced by a small buffer δ.The paper states that if training and test data share a distribution, a small buffer can make the estimated strategy satisfy the budget with high probability.Source: §4.3 · p. 5
- With a continuous predicted-accuracy density, online selection satisfies the budget and loses at most 1/N accuracy versus the offline optimum.The guarantee is stated for the online selector; the paper notes the loss is often negligible for large training and testing datasets.Source: §4.3 · p. 5
4.4. Base service selection and label combination
- The base service is chosen by validation performance; the combiner unions its labels with add-on labels, weights their scores, and thresholds low-confidence labels.The weighting and threshold are dataset-level hyperparameters selected to maximize overall performance.Source: §4.4 · p. 6
5. Experiments
Experiments across multi-label image classification, scene text recognition, and named entity recognition evaluate FrugalMCT’s accuracy–cost trade-offs, API selection, and training requirements. FrugalMCT often reduces cost while matching the best commercial API, and can improve accuracy at the same cost.
Multi-label Image Classification: A Case Study
- On COCO, FrugalMCT reaches 0.514 accuracy versus 0.475 for Microsoft and 0.501 for majority vote, at much lower cost.The learned strategy mostly uses Everypixel and occasionally calls Microsoft; its threshold balances accuracy against budget use.Source: §5 · p. 7, Figure 3 · p. 7
- The online API selector runs several orders of magnitude faster than CBC, MOSEK, and GUROBI by leveraging Problem 4.1’s structure.The comparison is shown in Figure 3(e).Source: §5 · p. 7
Analysis of Cost Savings
- 73% average cost saving is achieved across evaluated datasets while matching the best commercial API’s accuracy.Cost savings are typically more than 60% and reach 98% on ZHNER.Source: Table 4 · p. 7, §5 · p. 7
Accuracy and Cost Trade-offs
- Online FrugalMCT matches offline performance across experiments, and FrugalMCT outperforms FrugalML at the same budget.Majority-vote ensembles produce similar accuracy but at much higher cost.Source: Figure 4 · p. 8, §5 · p. 8
- More than 5% accuracy improvement is possible on COCO and ZHNER at the best API’s cost.FrugalMCT also lets users choose points along its accuracy–cost trade-off curve.Source: §5 · p. 8
Effects of Training Sample Size
- A few thousand training samples typically suffice, and training on half of COCO takes 59.5 seconds after $15.5 in labeling costs.Training is a one-time cost; the example estimates labeling 5,000 images by calling all APIs.Source: §5 · p. 9, Figure 5 · p. 9
6. Conclusion
FrugalMCT adaptively selects and combines multi-label APIs under a budget, and the authors report improved cost and accuracy in evaluations using commercial APIs. They also release the dataset used to develop the framework.
6. Conclusion
- FrugalMCT integrates API-accuracy forecasts with online constrained optimization to select and combine multi-label APIs within a budget.The conclusion reports strong empirical performance and theoretical guarantees.Source: §6 · p. 9
- Extensive evaluations using real commercial APIs show that FrugalMCT significantly improves both cost and accuracy.Source: §6 · p. 9
- The released development dataset contains 295,212 samples annotated by commercial multi-label prediction APIs.Source: §6 · p. 9
A. Technical Details
The technical details describe grid searches for the label combiner’s parameters and for δ, selecting settings by validation or accuracy.
A. Technical Details
- The label combiner’s weight w and quality threshold θ are selected by grid search over candidate pairs, choosing the pair with highest accuracy.The search evaluates M^2 combinations for each service; M = 10 was sufficient in practice.Source: A. Technical Details · p. 13
- The label-combiner search evaluates each candidate parameter pair by the accuracy of combining the base service with the kth service.Source: A. Technical Details · p. 13
- For δ, the authors search candidate α values, set δ = α log N / N, and select the value with highest validation accuracy.They report that CS = {−10, −9, …, 0, 1, …, 10} was sufficient in practice.Source: A. Technical Details · p. 13
B. Proofs
The proof section shifts the API-selection problem by subtracting the base service’s cost and then uses properties of the transformed problem to prove results for the original formulation.
B. Proofs
- The transformed problem defines adjusted budget as b̂ = b − c_base and adjusted service cost as ĉ_k = c_k · 1_{k ≠ base}.Source: B. Proofs · p. 13
- The authors rewrite the API-selection problem using the adjusted budget and service costs, then express its corresponding linear program.Source: B. Proofs · p. 13
- The proof strategy establishes properties of the two transformed problems before proving the desired results for the original API-selection problem.Source: B. Proofs · p. 13
B.1. Helpful Lemmas
The helpful-lemmas section uses probability and optimization arguments, including a continuous-density argument for zero-probability events and concentration bounds for two sample sequences.
B.1. Helpful Lemmas
- A contradiction step links forcing N2 + 1 equations in Ax′ = β to positive probability that β_U lies in the span of A_U.Source: §B.1 · p. 14
- For a fixed index set V of size N2 + 1, the proof argues that β_V lies in the span of A_V with probability zero, then applies a union bound across such sets.The argument uses a continuous density and the zero measure of the lower-dimensional span.Source: §B.1 · p. 14
- For two i.i.d. sample sequences, the proof applies Hoeffding’s inequality separately and then uses the triangle inequality.Source: §B.1 · p. 15
- The optimization comparison lemma assumes bounded differences in objective functions and constraints, then compares values using feasible solutions to both problems.Source: §B.1 · pp. 15–16
B.2. Proof of Theorem 4.2
The proof constructs a selector from an optimal solution to a relaxed problem, then shows it remains feasible under the budget while losing at most 1/N in estimated accuracy.
B.2. Proof of Theorem 4.2
- The construction yields a feasible selector whose reward is at least the optimal selector’s reward minus 1/N.The proof reduces feasibility to showing the constructed solution satisfies the relaxed problem’s budget constraint and the reward bound.Source: §B.2 · p. 16
- The proof compares the constructed solution with a sparse optimum of the relaxed problem, whose budget feasibility and estimated accuracy provide the benchmark.The stated proof strategy is to show closeness to that sparse optimum and that the difference neither violates budget nor reduces estimated accuracy by more than 1/N.Source: §B.2 · p. 16
- Complementary slackness and a matrix argument establish that, except for one data point, the constructed solution selects the unique maximizing API combination.The proof uses the bound on the number of satisfied equations and complementary slackness to identify the maximizing combination for all but one point.Source: §B.2 · pp. 16–17
- The final feasibility argument uses the relaxed optimum’s budget constraint and a lowest-cost tie break for the exceptional data point.The construction then satisfies the budget constraint of the original problem.Source: §B.2 · p. 18
B.3. Proof of Theorem 4.3
The proof controls the selector by discretizing its price parameter and bounding estimation error and budget feasibility with high probability. It then combines these bounds to establish the theorem’s guarantee.
B.3. Proof of Theorem 4.3
- The proof separately verifies budget feasibility with probability 1 − ϵ, then combines feasibility and reward bounds for the theorem.The proof states that the constructed selector is feasible with probability 1 − ϵ.Source: §B.3 · pp. 20, 25
- For any price parameter, the proof finds a point on a finite grid that gives the stated approximation bound with high probability.The proof partitions estimated-accuracy space by which API combination maximizes estimated accuracy minus price times cost, then uses the grid ΩM.Source: §B.3 · pp. 20, 22
- A distribution assumption bounds the probability mass of each region, supporting the finite-grid approximation.The proof assumes Pr(A) ≤ u∥A∥ for sets A in the probability space.Source: §B.3 · p. 20
- The proof bounds errors using concentration for i.i.d. estimated accuracies in [0, 1] and applies union bounds across the regions.It combines the resulting bounds with lemmas for the discretized problem.Source: §B.3 · pp. 21–22
C. Experimental Details
Experiments cover multi-label image classification, scene text recognition, and named entity recognition, using commercial APIs and open models across multiple datasets. The case studies examine complementary API strengths and how FrugalMCT’s performance depends on its accuracy predictors.
Experimental setup
- Experiments include image classification, scene text recognition, and named entity recognition, with nine datasets and commercial and GitHub APIs.The image task uses Google, Microsoft, Everypixel, and SSD; scene text uses Google, iFLYTEK, Tencent, and PP-OCR; NER uses Amazon, Google, IBM, and a GitHub model.Source: C. Experimental Details · p. 26
Case study on COCO
- The COCO case study spans 123,287 images and 80 labels, with person in over 50% of images but driver and toaster each in under 1%.This label imbalance is reported to impose high data and computational complexity on approaches that learn a decision rule per label.Source: C. Experimental Details · p. 27, Figure 6 · p. 27
- API strengths vary by label: Everypixel and Google do better on toaster, while Microsoft, Google, and GitHub often do better on kite and “knite.”The paper also reports that all APIs reach 90% precision and recall on zebra, suggesting some cases may not need every API call.Source: C. Experimental Details · pp. 27–28, Figure 7 · p. 30, Figure 8 · p. 31
- FrugalMCT improves precision and recall for almost every label over any single API, but cannot predict hair drier when no API predicts it correctly.Recognizing labels unseen by all APIs is left as an open question; applications with specific precision and recall needs may use different accuracy metrics.Source: C. Experimental Details · p. 28
Ensemble method comparison
- Across tasks and datasets, FrugalMCT and ensemble methods have similar performance at much lower cost, and it achieves higher accuracy than ensembles on COCO and ZHNER.Table 6 compares cost-aware approaches and ensembles; the reported strategies for FrugalMCT and FrugalML minimize cost while reaching the highest possible accuracy.Source: Table 6 · p. 28, C. Experimental Details · p. 29
Accuracy predictor performance
- FrugalMCT’s random-forest accuracy predictors have smaller RMSE and higher PCC than dummy accuracy predictors, alongside higher end-to-end performance.RMSE measures prediction error; PCC measures correlation between predicted and true accuracy.Source: Table 7 · p. 28, C. Experimental Details · p. 29