FRUGALMCT: EFFICIENT ONLINE ML API SELEC-
Year: 2021

Abstract:
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 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 their prices and performance. Recent work has shown how to efficiently select and combine singlelabel APIs to optimize performance and cost. However, its computation cost is exponential in the number of labels, and 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 the user’s budget. It allows combining ML APIs’ predictions for any single data point, and selects the best combination based on an accuracy estimator. We run 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 these 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.

heading: 1 INTRODUCTION
text: Many machine learning users are starting to adopt machine learning as a service (MLaaS) APIs to obtain high-quality predictions. One of the most common tasks these APIs target is multi-label classification. For example, one can use Google’s computer vision API (Goo) to tag an image with a wide range of possible labels for $0.0015, or Microsoft’s API (Mic) for $0.0010. Another example is to extract all text strings from an image for $0.005 via iFLYTEK’s API (Ifl) or $0.021 via Tencent’s API (Ten). In practice, these APIs also provide different performance on different types of input data (e.g., English vs Chinese text). The heterogeneity in APIs’ performance and prices makes it hard for users to decide which API, or combination of APIs, to use for their own datasets and budgets.
Recent work (Chen et al., 2020) proposed FrugalML, an algorithmic framework that adaptively decides which APIs to call for a data point to optimize accuracy and cost. Their approach learns a fast decision rule for each possible output label that can significantly improve cost-performance over the individual APIs. However, FrugalML requires a large amount of training data and involves solving a non-convex optimization problem with complexity exponential in the number of distinct labels. This prevents it from being used for tasks with large number of labels, such as multi-label classification. Furthermore, FrugalML ignores correlation between different APIs’ predictions, potentially limiting its accuracy. For example, APIs A and B may output {person, car} and {car, bike} separately for an image whose true keywords are {person, car, bike}. FrugalML would select one of the two label sets, but combining them results in the true label set and thus higher accuracy. Thus, this paper aims to solve these significant limitations and address the question: how do we design efficient ML API selection strategies for multi-label classification tasks to maximize accuracy within a budget?
We propose FrugalMCT, a principled framework that learns the strengths and weaknesses of different combinations of multi-label classification APIs, and efficiently selects the optimal combinations of APIs to call for different data items and budget constraints. As shown in Fig. 1 (a), FrugalMCT directly estimates the accuracy of each API combination on a particular input based on the features and predicted labels of that input. Then it uses a fast service selector based on the estimated accuracy to balance accuracy and budget. For example, we might first call API A on an input. If A returns
person and teddy bear and the accuracy predictor gives relatively high estimated accuracy (Fig. 1 (c)), then we stop and report {person, teddy bear} as the label set. If A returns person and tennis racket, and we predict that combining it with API B’s output gives a much higher accuracy, then we invoke API B and combine their prediction to obtain {person, sports ball, tennis racket} (Fig. 1 (d)).
Contributions. FrugalMCT is an end-to-end approach that integrates the selection of APIs and the combination of their outputs for individual user queries. It leverages our key finding that current commercial APIs have complementary strengths and weaknesses, and that we can reliably predict which APIs are likely to work well for a new query based on easy-to-generate metadata about its input. FrugalMCT then executes an efficient online algorithm to determine which combination of APIs to call for different user queries. We show that the online algorithm enjoys an accuracy provably close to the offline method as well as a small computational cost. All components in FrugalMCT are trainable, making it easy to customize for different applications. To our knowledge, FrugalMCT is the first work on how to effectively select and combine multi-label ML APIs.
Empirically, FrugalMCT produces substantially better prediction performance than individual APIs and than FrugalML adapted for multi-label tasks (Fig. 1 (b)). Extensive experiments with real commercial APIs on several tasks, including multi-label image classifications, scene text recognition, and named entity recognition, show that FrugalMCT typically provides over 60% (as high as 98%) cost reduction when aiming to match the best commercial API’s performance. Also, when targeting the same cost as the best commercial API, FrugalMCT can improve performance up to 8%.
We will release our dataset of 295,212 samples annotated by commercial multi-label APIs as the largest dataset and resource for studying multi-label ML prediction APIs.
Related work. MLaaS: With the growing importance and adoption of MLaaS APIs (Ama; Ten; Goo; IBM; Mic), existing research has largely focused on evaluating individual API for their performance (Yao et al., 2017), robustness (Hosseini et al., 2017), biases (Koenecke et al., 2020) and applications (Buolamwini & Gebru, 2018; Hosseini et al., 2019; Reis et al., 2018). Recent work on FrugalML (Chen et al., 2020) studies API calling strategies for single label classification. While their approach’s computational complexity is exponential in the number of labels, FrugalMCT’s
complexity does not depend on the number of labels, making it suitable for multi-label prediction APIs. In addition, FrugalML selects only one API per user query, while FrugalMCT considers the combination of multiple APIs’ output for each input data. This improves the overall accuracy (as shown in Sec 4), but also creates unique optimization challenges that we solve.
Ensembles for multi-label classification: Ensemble learning is a natural approach to combine different predictors’ output. Several ensemble methods have been developed, such as using pruned sets (Read et al., 2008), classifier chains (Read et al., 2011), and random subsets (Tsoumakas & Vlahavas, 2007), with applications in image annotations (Xu et al., 2011), document classification (Chen et al., 2017), and speech categorization (Liu et al., 2019). Moyano et al. (2018) provide a detailed survey of this area. Almost all of these ensemble methods require joint training of the base classifiers, but MLaaS APIs are black box to the users. Also, while ensemble methods focus only on improving accuracy, FrugalMCT explicitly considers the cost of each API and enforces a budget constraint.
Model cascades: A series of works (Viola & Jones, 2001a;b; Sun et al., 2013; Cai et al., 2015; Wang et al., 2011; Xu et al., 2014; Chen et al., 2018; Kumar et al., 2018; Chen et al., 2018) explores cascades (a sequence of models) to balance the quality and runtime of inference. Model cascades use a single predicted quality score to avoid calling computationally expensive models, but FrugalMCT’ strategies utilize both quality scores and predicted label sets to select an expensive add-on service.
AutoML for multi-label classification: AutoML (Thornton et al., 2013) automates the customization of ML pipelines, including the selection, combination, and parametrization of the learning algorithms. There is a rich literature of AutoML techniques for standard single label tasks, and fewer methods on multi-label predictions (Wever et al., 2021) (e.g. genetic algorithms (de Sá et al., 2017) and a neural network-based search scheme (Pakrashi & Namee, 2019)). Applying AutoML to use multiple ML APIs is underexplored, and FrugalMCT can be viewed as the first AutoML approch designed for automating the selection of multiple mutlti-label ML APIs. While most AutoML systems exclusively focus on prediction performance, FrugalMCT optimizes accuracy and cost jointly, which is desirable for cost-sensitive API users.
Multiple choice knapsack and integer programming: Many resource allocation problems can be modeled as multiple choice knapsack problem (MCKP) (Pamela H. Vance & Toth), 1993), such as keyword bidding (Zhou & Naroditskiy, 2008) and quality of service control (Lee et al., 1999). While NP-hard (Sinha & Zoltners, 1979), various approximations have been proposed for MCKP, such as branch and bound (Pamela H. Vance & Toth), 1993), convex hull relaxation (Akbar et al., 2006) and bi-objective transformation (Bednarczuk et al., 2018). Inherently an integer linear programming (ILP) problem, MCKP can also be tackled by ILP solvers, motivated by online adwords searching (Devanur & Hayes, 2009), resource allocation (Devanur & Hayes, 2019) and general linear programming (Li et al., 2020). The service selector of FrugalMCT can be viewed as a MCKP with the same item cost vector per item group, which we leverage to obtain a customized fast and online solver.

heading: 2 PRELIMINARIES
text: Notation. We denote matrices and vectors in bold, and scalars, sets, and functions in standard script. Given a matrix A ∈ Rn×m, we let Ai,j denote its entry at location (i, j). 1(·) represents the indicator function.
Multi-label classification Tasks. Throughout this paper, we focus on multi-label classification tasks: assigning a label set Y ⊆ Y to any data point x ∈ X . In contrast to basic supervised learning, in multi-label learning each data point is associated with a set of labels instead of a single label. Many MLaaS APIs target such tasks. Consider, for example, image tagging, where X is a set of images and Y is the set of all tags. Example label sets could be {person, car} or {bag, train, sky}.
MLaaS Market. Consider a MLaaS market consisting of K different ML services for some multilabel task. For a data point x, the kth service returns to the user a set of labels with their quality scores, denoted by Yk(x) ⊆ Y × [0, 1]. For example, one API for multi-label image classification might produce Yk(x) = {(person, 0.8), (car, 0.7)}, indicating the label person with confidence 0.8 and car with confidence 0.7. Let the vector c ∈ RK denote the unit cost of all services. For example, ck = 0.01 means that users need to pay $0.01 every time they call the kth service.

heading: 3 FRUGALMCT FRAMEWORK
text: In this section, we present FrugalMCT, a framework to adaptively select ML APIs for multi-label classification tasks within a budget. All proofs are left to the appendix. We generalize the scheme in Figure 1 (a) to K ML services. As shown in Figure 2, FrugalMCT contains three main components: an accuracy estimator, a service selector, and a label combiner.
Given a data point x, it first calls some base service, denoted by base, which is one of the K APIs, and obtains Ybase(x). Often, base is a cheap or free service; we discuss how to choose base in Section 3.4. Next, an accuracy predictor produces a vector â(x) ∈ [0, 1]K , whose kth value estimates the accuracy of the label set produced by the label combiner using base’s and kth API’s outputs. The service selector s(·) : X 7→ [K] then decides if and which add-on service needs to be invoked. Finally, a label combiner generates a label set by combining the predictions from the base and add-on APIs. Take Figure 1 (d) as an example. The image is first passed to the GitHub model, which produces {(person, 0.46),(tennis racket,0.18)}, by which the accuracy predictor predicts the accuracy of the label set generated by combining each API’s output with GitHub model’s. The service selector then decides to further invoke Everypixel, which gives {(person, 0.46), (sports ball, 0.52)}. Finally, the label combiner uses both APIs’ output for the final prediction.
FrugalMCT allows users to customize the accuracy predictor and the label combiner, depending on the applications. For example, for the image tagging problem, one might use image features (e.g., brightness and contrast) to build the accuracy predictor, while word embeddings can be more useful for named entity recognition. In the following sections, we explain the key of accuracy predictor, API selector and the label combiner in more detail.

heading: 3.1 ACCURACY PREDICTION
text: The accuracy predictor â(·) can be obtained by two steps. The first step is to generate a feature vector for every data point in the training dataset XTr ≜ {xTr1 , xTr2 , · · · , xTrNTr}. Generally the feature vector can be any embedding of the data point x and base service prediction Ybase(x). In this paper we adopt a simple approach: if the label set Y is bounded, a |Y| dimensional vector is generated using one hot encoding on Ybase(x). For example, given Y = {person, car, bike} and Ybase(x) = {(person, 0.8), (car, 0.7)}, the generated feature vector is [0.8, 0.7, 0]. For unbounded Y , word embedding is used to generate a vector for every predicted label, and the sum of them (weighted by their quality values) becomes the corresponding feature vector.
The next step is to train the accuracy predictor. For each xTrn ∈ XTr, as its true label sets and prediction from each API are available, we can construct its true accuracy vector a(xTrn ) ∈ [0, 1]K , whose kth element is the accuracy of the label produced by the label combiner using base and kth service predictions. Then we can train some regressor (e.g., random forest) to map the feature vector to the accuracy vector. We use standard multi-label accuracy1 (Zhang & Zhou, 2014) as a concrete
1 ∥Y ∩Y ′∥ ∥Y ∪Y ′∥ where Y /Y ′ is the true/predicted label set.
metric. FrugalMCT can as easily use another metric such as F1-score, precision or subset accuracy.

heading: 3.2 THE API SELECTION PROBLEM
text: A key part of FrugalMCT is the API selector s: given a budget b and the estimated accuracy â(x), which service should be invoked? Let X ≜ {x1, x2, · · · , xN} be the entire unlabeled dataset to be classified, and S ≜ {1, 2, · · · ,K}X be the set of all functions mapping each data point in X to an API. Let base be the index of the base service. For any s ∈ S, s(x) = base implies no add-on API is needed, and s(x) = k 6= base implies kth API is invoked. Our goal is to find some s ∈ S to maximize the estimated accuracy while satisfying the budget constraint, formally stated as below. Definition 1. Let Z∗n,k be the optimal solution to the budget aware API selection problem
max Z∈RN×K :
1
N N∑ n=1 K∑ k=1 Zn,kâk(xn)
s.t. 1
N N∑ n=1 K∑ k=1,k ̸=base Zn,kck + cbase ≤ b; K∑ k=1 Zn,k = 1,∀n;Zn,k ∈ {0, 1},∀n, k
(3.1)
Then the optimal FrugalMCT strategy is given by s∗(xn) ≜ argmaxkZ∗n,k.
Here, the objective quantifies the average accuracy, the first constraint models the budget requirement, and the last two constraints enforces only one add-on API is picked for each data point. Base service is needed for every data point and thus its cost cbase appears for every n in the budget constraint. Note that Problem 3.1 is a MCKP (and thus integer linear program) and NP-hard in general.

heading: 3.3 AN ONLINE ALGORITHM FOR FRUGALMCT
text: In many time-sensitive applications, the input data xn (as well as the accuracy vector â(xn)) comes sequentially, and the API needs to be selected before observing the future data. The selection process also needs to be fast.
To tackle this challenge, we present an efficient online algorithm, which requires O(K) computations per round and gives a provably near-optimal solution. The key idea is to explicitly balance between accuracy and cost at every iteration. Specifically, for a given data point xn and p ∈ R, let us define a strategy sp(xn) ≜ argmaxk âk(xn)− pck1k ̸=base and break ties by picking k with smallest cost. Here, p is a parameter to balance between accuracy â(xn) and cost c. When p = 0, sp(xn) selects the API with highest estimated accuracy. When p is large enough sp(xn) enforces to pick the base API. In fact, larger value of p implies more weights on cost and smaller p favors more the accuracy. Let r(s) ≜ 1N ∑N n=1 âs(xn)(xn) denote the average accuracy achieved by a strategy s. We can show, interestingly, an appropriate choice of p leads to small average accuracy loss. Theorem 1. Assume the probability density of â(x) is a continuous function on [0, 1]K . Then with probability 1, there exists p∗ such that sp ∗ satisfies budget constraint, and r(sp
∗ ) ≥ r(s∗)− 1N .
In words, sp ∗ (xn) gives a solution to the API selection problem with accuracy loss at most 1N . In practice, â(x) is continuous for standard ML models of accuracy predictors (e.g., logistic regressors) and thus the assumption holds. In addition, it is computationally efficient: at iteration n, it only requires computing âk(xn)− pck1k ̸=base for k = 1, 2, · · · ,K, which takes only O(K) computations. The remaining question is how to obtain p∗. As we cannot see the future data to compute p∗, a natural idea is to estimate it using the training dataset. More precisely, given the training dataset {xTr1 , xTr2 , · · · , xTrNTr}, let p̂, q̂ be the optimal solution to the following problem
min p,q≥0 (1− δ)(b− cbase)p+ NTr∑ n=1 qn, s.t. ck · 1k ̸=base · p NTr + qn ≥ âk(x Tr n ) NTr ,∀n, k (3.2)
where δ ∈ (0, 1) is a small buffer to ensure that we don’t exceed the budget (in practice we set δ ≤ 0.01). Technically, Problem 3.2 is the dual problem to the linear programming by relaxing the
integer constraint in Problem 3.1 on the training dataset with budget (1 − δ)b, and p̂ corresponds to the near-optimal strategy for the training dataset. If the training and testing datasets are from the same distribution, then a small δ can ensure with high probability, p̂ is slightly less than p∗ and thus sp̂ satisfies the budget constraint. Given p̂, one can use sp̂ to select the APIs in an online fashion. The details are given in Algorithm 1.
Algorithm 1 FrugalMCT Online API Selection Algorithm. Input :c, b, {xTr1 , xTr2 , · · · , xTrNTr}, {x1, x2, · · · , xN} Output :FrugalMCT online API selector so(·)
1: Compute p̂ by solving Problem 3.2 and set br = N(b− cbase). 2: At iteration n = 1, 2, · · · , N :
3: so(xn) = { sp̂(xn) if br − csp̂(xn) ≥ 0 base o/w 4: br = br − csp̂(xn)1sp̂(xn) ̸=base
Here, br is used to ensure the generated solution is always feasible. The following theorem gives the performance guarantee of the online solution.
Theorem 2. If δ = Θ (√
logN/ϵ N +
√ logNTr/ϵ
NTr
) and the probability density of â(x) is a continuous
function on [0, 1]K , then so satisfies the budget constraint, and with probability at least 1−ϵ, r(so) ≥ r(s∗)−O (√
logN/ϵ N +
√ logNTr/ϵ
NTr
) .
Roughly speaking, so leads to an accuracy loss at most O (√
logN N +
√ logNTr
NTr
) compared to the
optimal offline strategy. For large training and testing datasets, such an accuracy loss is often negligible, which is also verified by our experiments on real world datasets.

heading: 3.4 BASE SERVICE SELECTION AND LABEL COMBINATION
text: Now we describe how the base service is selected and how the label combiner works. The base service can be picked by an offline searching process. More precisely, for each possible base service, we train a FrugalMCT strategy and evaluate its performance on a validation dataset, and pick the base service corresponding to the highest performance.
The label combiner contains two phases. First, a new label set associated with its quality function is produced. The label set is simply the union of that from the base service and add-on service. The quality score is a weighted sum of the score from both APIs, controlled by w. For example, suppose the base predicts {(person, 0.8), (car, 0.7)} and the add-on predicts {(car, 0.5), (bike, 0.4)}. Given w = 0.3, new confidence for person is 0.3 × 0.8 = 0.24, for car is 0.3 × 0.7 + 0.7 × 0.5 = 0.46, and for bike is 0.7×0.4 = 0.28. Thus the combined set is {(person, 0.24), (car, 0.46), (bike, 0.28)}. Next, a threshold θ is applied to remove labels with low confidence. For example, given θ = 0.25, the label person would be removed, and the final predicted label set becomes {car, bike}. The parameters w and θ are global hyperparameters for each dataset, and can be obtained by an efficient searching algorithm to maximize the overall performance. The details are left to Appendix A.

heading: 4 EXPERIMENTS
text: We compare the accuracy and incurred costs of FrugalMCT to that of real world ML services for various tasks. Our goal is to (i) understand when and why FrugalMCT can reduce cost without hurting accuracy, (ii) investigate the trade-offs between accuracy and cost achieved by FrugalMCT, and (iii) assess the effect of training data size and accuracy predictors on FrugalMCT’s performance.
Tasks, ML services, and Datasets. We focus on three common ML tasks in different application domains: multi-label image classification (MIC), scene text recognition (STR), and named entity recognition (NER). MIC aims at obtaining all keywords associated with an image, STR seeks to
recognize all texts in an image, and NER desires to extract all entities in a text paragraph. The ML services used for each task as well as their prices are summarized in Table 1. For each task we use three datasets, with details in Appendix C.
Accuracy Predictors. Except when explicitly noted, we use a random forest regressor as the accuracy predictor for all the datasets. For MIC and STR datasets, we map each possible label to an index, and create a feature vector whose kth element is base service’s quality score for the label corresponding to k. If a label is not predicted, the corresponding value is 0. For NER datasets, we map each predicted label to a 96-dimensional vector using a word embedding from spaCy (Spa), and then use the sum weighted by their corresponding quality scores as the feature vector. The accuracy predictor is then trained on half of the datasets using the feature vectors generated as above.
Multi-label Image Classification: A Case Study. Let us start with multi-label image classification on the COCO dataset. We set budget b = 6, the price of Everypixel, the cheapest commercial API (except the open source model from GitHub). For comparison, we also use the average quality score over all predicted labels as the confidence score and adapt FrugalML (Chen et al., 2020) with the same budget (= 6) as another baseline .
Figure 3 demonstrates the learned FrugalMCT strategy. As shown in Figure 3 (a), the learned FrugalMCT reduces the cost by mostly using the Everypixel API (45%, 6$) and occasionally calling Microsoft API (32%, 10$).Note that its performance depends on the threshold value p̂. As shown in Figure 3 (b) and (c), for small thresholds, FrugalMCT tends to call the more accurate and expensive APIs. However, it runs out of budget quickly, and for many data points only base service can be used, leading to low accuracy. For large thresholds, FrugalMCT tends to call cheaper but less accurate APIs, failing to fully use the budget and thus causing low accuracy too. The p̂ value learned by FrugalMCT (blue point in Figure 3 (b) and (c)) produces the optimal accuracy given the budget. Figure 3 (d) shows that FrugalMCT’s accuracy (0.514) is higher than that of the best ML service (MS, 0.475) and majority vote (Maj 0.501), while its cost is much lower. This is primarily because
FrugalMCT learns when the cheaper APIs perform better and call them aptly. FrugalMCT also outperforms FrugalML by exploiting the label combination. As shown in Figure 3 (e), the API selector of FrugalMCT (Alg. 1) is several orders of magnitude faster than commercial ILP solvers, by leveraging the specific structure of Problem 3.1.
Analysis of Cost Savings. Next, we evaluate how much cost can be saved by FrugalMCT to reach the highest accuracy produced by a single API on different tasks. As shown in Table 2, FrugalMCT can typically save more than 60% of the cost. Interestingly, the cost saving can be up to 98% on the dataset ZHNER. This is probably because (i) the accuracy estimator enables the API selector to identify when the base service’s prediction is reliable and to avoid unnecessarily calling add-on services, and (ii) when add-on API is invoked, the apt combination of the base and add-on services leads to a high accuracy improvement.
Accuracy and Cost Trade-offs. Now we dive deeply into the accuracy and cost trade-offs achieved by FrugalMCT, shown in Figure 4. We compare with two oblations: “Offline”, where the full data is observed before making decision, “DAP”, where a dummy accuracy predictor is used, which, for each API, always returns its mean accuracy on the training dataset. We also compared with an adapted version of the previous state-of-the-art for single label task, FrugalML. To adapt it to multi-label tasks, we use the average quality score over all predicted labels as a single score, and cluster all labels into a “superclass”.
Compared to any single API, FrugalMCT allows users to pick any point in its trade-off curve and offers substantial more flexibility. In addition, FrugalMCT often achieves higher accuracy than any ML services it calls. For example, on COCO and ZHNER, more than 5% accuracy improvement can be reached with the same cost of the best API. Note that FrugalMCT also outperforms FrugalML with the same budget. This is primarily because FrugalMCT (i) utilizes a more principled way to use the features (learning an accuracy estimator) than FrugalML (directly using the label info), and (ii) adopts a label combiner designed for multi-label tasks. Ensemble methods such as majority votes (in the appendix C) produce accuracy similar to FrugalMCT, but their cost is much higher.
Note that there is little performance difference between the online FrugalMCT strategy and the offline approach, due to the carefully designed online algorithm. This directly supports our theory. The accuracy predictors play an important role in FrugalMCT’s performance. As Table 4 shows, FrugalMCT is able to provide nontrivial accuracy estimates which enables its success. It’s interesting to note that the accuracy predictor doesn’t need to be perfect for FrugalMCT to do well; for example, the root mean square error (RMSE) of the accuracy predictor is 0.28 on PASCAL, but FrugalMCT still produces consistently better accuracy than FrugalML. We also evaluated FrugalMCT’s performance when the accuracy predictors are obtained via two AutoML toolkits, auto-sklearn (Feurer et al., 2015) and Auto-PyTorch (Mendoza et al., 2019) instead of random forest, and observe a similar performance.
Effects of Training Sample Size. Finally we study how the training dataset size affects FrugalMCT’s performance. As shown in Figure 5, across different tasks, a few thousand training samples are typically sufficient to learn the optimal FrugalMCT strategy. This is usually more efficient than training a customized ML model from scratch.

heading: 5 CONCLUSION
text: In this paper, we presented FrugalMCT, an algorithmic framework to adaptively select and combine ML APIs for multi-label classification tasks within a budget constraint. FrugalMCT integrates forecasts of API’s accuracy with online constrained optimization to create an end-to-end algorithm with strong empirical performance and theoretical guarantees. How to efficiently use multi-label APIs is an important problem in practice for the large number of ML users who have chosen to rely on commercial prediction APIs, and has not been studied heavily in the ML literature. This work can help MLaaS users improve both the overall accuracy and cost of their applications. Extensive empirical evaluation using real commercial APIs shows that FrugalMCT significantly improves both cost and accuracy. To encourage more research on MLaaS, we also release the dataset used to develop FrugalMCT, consisting of 295,212 samples annotated by commercial multi-label prediction APIs.

Review summaries:
Given several mutli-label machine learning APIs, this paper study how to select those APIs under a budget constrant while striving to improve the overall accuracy. The author first formulate the budget API select problem as an integer linear programming problem, then relax the integer contraint and solving the relax problem in dual. The advantage of such modeling is to have a fast decision function for online deployment of their API selection systems. The experiment results are promising and consists of several ablation studies. 

This paper addresses the practical task to use the combination of ML APIs for multi-label classification. Different from the related work FrugalML which ignores the correlation between ML APIs, the proposed FrugalMCT allows selecting and combining the different ML APIs based on a budget. Sufficient theoretical and empirical analyses are provided to demonstrate the effective of FrugalMCT.