FrugalMCT: Efficient Online ML API Selection for Multi-Label Classification Tasks
Authors: Lingjiao Chen
Matei Zaharia
James Zou
Venue: ICLR 2022 Submitted (2022)
Keywords: ML as a Service
Multi-label classifications
ML systems
adaptive learning

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 single label 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.

Under review as a conference paper at ICLR 2022
FRUGALMCT: EFFICIENT ONLINE ML API SELEC- TION FOR MULTI-LABEL CLASSIFICATION TASKS
Anonymous authors Paper under double-blind review
ABSTRACT
Multi-label classification tasks such as OCR and multi-objeet recognition are a major focus of the growing machine learning as 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 their prices and performance. Recent work has shown how to efficiently select and combine single- label 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 use for different data in 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 experiments using MI 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.
accuracy estimator. We run systematic
INTRODUCTION
Many machine learning users are starting to adopt machine learning as a service (MLaaS) APIs 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 image with wide range of possible labels for $0.0015, or Microsoft's ''s API (Mic) for $0.0010. Another example to extract all text strings from an image for $0.005 via iFLYTEK's s API (lii) 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 all (02)) proposed FrugalML, an algorithmic framework that adaptively decides which APIs to call for a data point to optimize accuracy and cost. Their approach learns fast decision rule for each possible output label that can significantly improve pest-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, carl and fear, bike/ separately for an image whose true keywords are fperson, 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 MI. API selection strategies for multi-label classification tasks maximize accuracy within budget?
We propose FrugalMCT, principled framework that learns the strengths and weaknesses of differ- ent 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. MI (a). FrugalMCT directly estimates the accuracy of each API combination and predicted labels of that input. Then it uses fast service selector based on the estimated accuracy to balance accuracy and budget. For example, might first call API A input. If A returns
a particular input based on the features

---

Under review as a conference paper at ICLR 2022
0.55
0.50
Microsoft
Acouracy
6.45
Everyphcol
Accuracy
Service
Label Combiner
860
$0.01
G $15
0.30
FrugaIMCT
FrugalMIL
0.25
20
Budgat
Proposed FrugaIMCT
(b): Performance
Accuracy
Service Selector
Accuracy Predictor
Service Selector
Predictor [E0.5, 0.51, 0.45, 0.54
(( 0:92, 0.82, 0.60)
person:0
person 0.46 tennix racket
foddy
oitHub (S30)
(SSD)
weightnd
Label
weightnn.44
person:8.46
(person, feddy bear)
(parson, sports ball, tonnis racket))
threa=0.08
Example 1
Example
Demonstration of FrugalMCT. (a): FrugalMCT workflow. (b): Performance of Fru- galMCT COCO, multi-label image dataset, using real commercial ML APIs. (c), (d): Exam- ples of FrugalMCT's behavior on different inputs. In (c), FrugalMCT estimates that the accuracy of cheap open source SSD model from GitHub is high, and thus directly returns its predictions. In (d), Fru estimates that combining SSD's results with the Everypixel API has a much higher estimated accuracy, and thus it invokes EveryPixel and combines its results with SSD's results.
Figure 1:
person and teddy bear and the accuracy predictor gives relatively high estimated accuracy (Fig. (c)), then stop and report /person, teddy bear) 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. II (d)).
Contributions. FrugalMCT 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 new query based on casy-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 accuracy provably close to the offline method as well as small computational cost. All components in FrugalMCT are trainable, making it easy customize for different applications. To our knowledge, FrugalMCT is the first work on how to effectively select and combine multi-label MI. APIs
Empirically, MCU produces substantially better prediction performance than individual APIs and than FrugalML. adapted for multi-label tasks (Fig. MI (b)). Extensive experiments with real com- mercial 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 295,212 samples annotated by commercial multi-label APIs as the largest dataset and resource for studying multi-label ML prediction APIs.
Related work. MLLaS: With the growing importance and adoption of MLaaS APIs (Ama) Ient
God IBM Mid), existing research has largely focused on evaluating individual API for their per- formance (Yao 2012), robustness (Hossemmico et all 2017),, biases (Koenecke et all 202 and
applications (Huolamwini & Gebru, 20IS Hosseimi atll 2019: Reis 2018). Recent work
FrugalML (Chen et all 2020) studies API calling strategies for single label classification. While their approach's computational complexity is exponential in the number of labels, FrugalMCT's
2

---

Under review as a conference paper at ICLR 2022
complexity does not depend on the number of labels, making it suitable for multi-label prediction APIs. In addition, FrugalMML selects only one API per user query, while FrugalMCT considers the combination of multiple APIs' output for each imput data. This improves the overall accuracy (as shown in Sec 9), but also creates unique optimization challenges that we solve.
Ensembles for multi-label classification: Ensemble learning is natural approach to combine dif- ferent predictors' output. Several ensemble methods have been developed, such as using pruned sets (Readetal, 2008), classifier chains (Read all 20TT), and random subsets ([ & Viabavas. 2007),, with applications in image annotations (Xu et all, 20 document classification (Chen et all 2017), and speech categorization (Liu 2019). Moyano all (2018) provide detailed survey of this area, Almost all of these ensemble methods require joint training of the base classifiers, but MLaaSS 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 budget constraint.
Model cascades: A series of works (Viola & Jones, 200E Sun all 2013; Cai et all 2015:
Wang et all 2010: eul 2014 Chen-etal. etall 2018: Kumar all 2018: Chen (0TSS explores cascades (a sequence of models) to balance the quality and runtime of inference. Model cascades use single predicted quality score to avoid calling computationally expensive models, but FrugalM strategies utilize both quality scores and predicted label sets to select an expensive add-on service.
AutoML for multi-label classification: AutoML (Thornton ef all 201 3) automates the customiza- tion of ML pipelines, including the selection, combination, and parametrization of the learning al- gorithms. There is rich literature of AutoML techniques for standard single label tasks, and fewer methods on multi-label predictions (Wever et all, 2021I (e.g. genetic algorithms (de Sá et all 2017) and 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 sys- tems 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 Vance & Toth 1993), such as keyword bidding (Zhou & Naroditskiy, 2008) and quality of service control et 1999). While NP-hard (Sinha.K & Zoltners, 1979), various approximations have been proposed for MCKP, such as branch and bound (Pamela H. Vance & Toth), (1993), convex hull relaxation (Akbar et all, 2006) and bi-objective transformation (Bednarezuk et all 2013). Inherently an integer linear programming (ILP) problem. MCKP can also be tackled by ILP solvers, motivated by online adwords searching (Devanur & Hayes, (009),, resource allocation (Devanur & Hayes, 2019) and general linear program- ming (Lletaal (02()). The service selector of FrugalMCT can be viewed MCKP with the same item cost vector per item group, which we leverage to obtain a customized fast and online solver.
2 PRELIMINARIES
Notation. We denote matrices and vectors in bold, and scalars, sets, and functions in standard script. Given a matrix A E R=xm, we let Ai, denote its entry at location (i, 1() represents the indicator function.
Multi-label classification Tasks. Throughout this paper, we focus on multi-label classification tasks: assigning label set C y' any data point X. In contrast basic supervised learning. in lubti-label learning each data point is associated with set of labels instead of a single label. Many MLaaS APIs target such tasks. Consider, for example, image tagging, where X' set of set of all tags. Example label sets could be [person, car) or [bag, train, sky].
images and y is the
MLaaS Market. Consider a MLaaS market consisting of K different ML services for some multi- label task. For data point the ktth service returns to the user set of labels with their quality scores, denoted by Ys C y x [o. 1]. For example, one API for multi-label image classification might produce (=(x)= = [person, 0.8), (car, 0.7)), indicating the label person with confidence 0.8 and car with confidence 0.7. Let the vector e E I denote the unit cost of all services. For example, C₁ 0.01 means that users need to pay $0.01 every time they call the kth service.
3

---

Under review as a conference paper at ICLR 2022
budget 5
Data point x
Symbol
Moaning
data point
pick base service
ith service
e X²
budget
f,j
service
(x(x)) y
service's
Accuracy predictor
Service selector
jth service
Y=(=)
(ixx,) -) (x)) + [0,1]
quality score function
combiner
a(*) R
estimated accuracy
Return Y (a)
Y (a)
returned labels
(A)
(b)
Figure 2: Overview of FrugalMCT. (a) shows how it works: Given a data point, FrugalMCT first invokes a base service. An accuracy predictor then estimates the performance of different APIs. Next, an add-on service is selected based on the predicted accuracy and budget. Finally, the add-on and base services' predictions are combined to return FrugalMCTTs prediction. (b) lists notation.
3 FRUGALMCT FRAMEWORK
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 M (a) to K' ML services. As shown in Figure D. FrugalMCT contains three main components: an accuracy estimator, service selector, and a label combiner.
Given data point x, it first calls some base service, denoted by base, which is one of the K APIs, and obtains Ybase()), Often, base a cheap or free service; we discuss how to choose buse in Section B4 Next, an accuracy predictor produces vector â(x) E [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 + [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 II (d) as example. The image is first passed the GitHub model, which produces ((person, 0.46), 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. the following sections, we explain the key of accuracy predictor, API selector and the label combiner in more detail.
3.1 ACCURACY PREDICTION
The accuracy predictor à(-) can be obtained by two steps. The first step is generate feature vector for every data point in the training dataset X & {x:"r, xh ..... , Tr. feature vector can be any embedding of the data point x and base service prediction Ynase In this paper we adopt a simple approach: if the label For example, given y {person, car, bike) } and (x) { (person, 0.8), (car, 0.7)). the generated feature vector is [0.8, 0.7, 0J. For unbounded D, 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.
Generally the
is bounded, | dimensional vector is
generated using one hot encoding on Yisse
The next step is to train the accuracy predictor. For each .T' E xTT,, as its true label sets and prediction from each API are available, we can construct its true accuracy vector a(x,"") E [0, 1]K whose keth 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 accuracy (Zhang & Zhou, 2014) as a concrete
|YnY' [OU?]
where Y/Y" is the true/predicted label set.
4

---

Under review as a conference paper at ICLR 2022
metric. FrugalMCT can easily another metric such as Fi-score, precision or subset accuracy.
3.2 THE API SELECTION PROBLEM
key part of FrugalMCT is the API selector s: given budget and the estimated aceuracy a(z). which service should be invoked? Let X - {21, #2, ,#N) be the entire unlabeled dataset to be classified, and S _ {1, 2, ..... K) 3 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 E S, s(x) = base implies no add-on API needed, and s(x) = k & base implies kth API is invoked. Our goal is to find some $ E S to maximize the estimated accuracy while satisfying the budget constraint, formally stated below.
Definition 1. Let n be the optimal solution to the budget aware API selection problem
N
K
max ZERNXK,
N
ΣΣ
2n, (x
(3.1)
N
K
s.t.
Zn, + Cbase S b;
mn,k = 1, Zn, E {0, Vn,
N
n=1
R= begbbbe
R=1
Then the optimal FrugalMCT strategy is given by s" (Ix) arg max ZT,
Here, the objective quantifies the average accuracy, the first constraint models the budget require- ment, and the last two constraints enforces only one add-on API is picked for each data point. Base service needed for every data point and thus its cost Chuse appears for every n in the budget con- straint. Note that Problem 3 MCKP (and thus integer linear program) and NP-hard in general.
3.3
AN ONLINE ALGORITHM FOR FRUGALMCT
In many time-sensitive applications, the input data vn (as well as the accuracy vector a(z,)) )) 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) computa- tions 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 given data point Hn and p e R. let us define a strategy s (z,n & arg max; å& (Ix,) - pea bydease and break ties by picking k with smallest cost. Here, is parameter to balance between accuracy a(x,, and cost c. When p = O. (I,,,) selects the API with highest estimated accuracy. When p is large enough (x enforces to pick the base API. In fact, larger value of p implies more weights on cost and smaller favors more the accuracy. Let r(s) & N En== as(z.,) (zx) denote the average accuracy achieved by strategy We can show, interestingly, an appropriate choice of p leads to small average accuracy loss.
Theorem 1. Assume the probability density of az)) is continuous function on [0, 1]K, Then with probability there exists p" such that s² satisfies budget constraint, and r(s"" 2 r(s") N-
In words, s² (I:)) gives solution to the API selection problem with accuracy loss at most 1. In practice, (zz) is continuous for standard ML models of accuracy predictors (c.g., logistic regressors) and thus the assumption holds. In addition, it is computationally efficient: at iteration it only re- quires computing (x,)) pe;: 1 kybbase for 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', natural idea is to estimate using the training dataset. More precisely, given the training dataset {of 2 Pr Lyr.). ). let p, be the optimal solution to the following problem
min (1 5) Chase )p + Σ gn, s.t. n.900
N
Ck 1I P + + 2
(x Tr)
Nr Vn, k
(3.2)
Nr
==1
where 8 E 10 is a small buffer to ensure that we don't exceed the budget (in practice we set 5 0.01). Technically, Problem [3 is the dual problem the linear programming by relaxing the
5

---

Under review as a conference paper at ICLR 2022
integer constraint in Problem [ the training dataset with budget (1 8)6, and p corresponds to the near-optimal strategy for the training dataset. If the training and testing datasets are from the same distribution, then small can ensure with high probability, I is slightly less than p" and thus s satisfies the budget constraint. Given P. one can use 8 to select the APIs in an online fashion. The details given in Algorithm []
Algorithm FrugalMCT Online API Selection Algorithm.
Input :c, b, {xf"", 222 ,... xTr (.1, "2,,"" .NN]
online API selector (+)
1: Compute p by solving Problem 3.2 and set 1 = N(b Chase).
2: At itteatiin ............
(Ixn) if Czp(zn) 20
3: (x base o/W
4: 6" ===6 6 (xn) 1 (2())) ($boee
Here, is used to ensure the generated solution is always feasible. The following theorem gives the performance guarantee of the online solution.
(V lng N/C N
and the probability density of of(() is continuous function on [0, 1] then s satisfies the budget constraint, and with probability least 1 c, r(s") 2
Theorem 2. Ifō =
Ing NT N
r(8*)
log N/c
log /
N
Roughly speaking, 8 leads accuracy loss most O log N
log N N
compared the
optimal offline strategy. For large training and testing datasets, such an accuracy loss is often negli- gible, which is also verified by our experiments on real world datasets.
3.4 BASE SERVICE SELECTION AND LABEL COMBINATION
Now we describe how the base service is selected and how the label combiner works. The base service can be picked by an offline scarching process. More precisely, for each possible base service, we train FrugalMCT strategy and evaluate its performance base service corresponding to the highest performance.
validation dataset, and pick the
The label combiner contains two phases. First, 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 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 0.3, new confidence for person is 0.3 0.8 0.24, for car is 0.3 x 0.7 0.7 0.5 0.46, and for bike is 0.7 x 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 0.25, the label person would be removed, and the final predicted label set becomes (car, bike). The parameters 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
4 EXPERIMENTS
We compare the accuracy and incurred costs of FrugalMCT to that of real world ML services for various tasks. Our goal is (i) understand when and why FrugalMCT can reduce cost without hurting accuracy, (ii) investigate the trade-offs between accuracy and cost achieved by FrugalM and (iii) assess the effect of training data size and accuracy predictors on FrugalMCTTs performance.
Tasks, ML services, and Datasets. We focus 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 image, STR seeks to

---

Under review as a conference paper at ICLR 2022
Table 1: MI services used for each task. Price unit: USD/10,000 queries. A publicty available (and thus free) GitHub model is also used per task: single shot detector (SSD) (SSD) pretrained on Open Images V4 (Kuznetsova et all 2020) for MIC, convolutional recurrent neural network (PP-OCR) (Pad) pretrained on an industrial dataset (Du et all 2020) for S7R, and a convolutional
neural network (spaCy (Spa)) pretrained on OntoNotes (Weischedel et 2017) for NER.
Task
ML Service
Price
MI. Service
Price
MI. Service
Price
MIC
Everypixel (Eve)
6
Microsoft (Mic)
10
Google (Goo)
15
STR
Google (Gio))
15
iFLYTEK (fit)
50
Tencent (Ie
210
NER
Amazon (Ama)
3
Google (GoN)
10
IBM MBM
30
52.3%
weigho-0.0
6.52
6.00
Accurery
0.50
4.00
46.4%
weighe-o.a
0.45
2.80
Accuracy Predictor
Label Combiner
0.000
0.015
0.000 6:805
0.019
0.000
Selector
PIKEL
Weight Value
Weight Value (G)
(b)
Inpur
maN (x) + cosle
Method
MS API
Frugal ML
FrugalMCT
Majority Vate
Images
Accurasy (%)
47.5
40.1
51.4
50.1
Cost (S)
10
6
31.0
weightmB.2
API selector
CBC
MOSEK
GUROBI
Rumtme (e)
0.291
500.53
38.2
20.3
Figure 3: A FrugalMCT strategy learned on the dataset COCO. (a) shows that FrugalMCT reduces cost by mostly calling the Everypixel API (45.4%) the GitHub API (22. I 1%) only. (b) and (c) show how the accuracy and cost vary with weight The blue point corresponds to 0.006, the learned p. (d) shows the accuracy and cost of FrugalMCT, FrugalML, Microsoft API, and majority vote. (e) gives the runtime performance of our (online) API selector and three commercial ILP solvers.
recognize all texts in image, and NER desires extract all entities in text paragraph. The ML. services used for each task as well as their prices are summarized Table II 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 ac- curacy 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 's quality score for the label corresponding to If a label is not predicted, the corresponding value O. 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 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 classifica- tion on the COCO dataset. We set budget 6 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 the same budget (= 6) as another baseline.
2020) with
Figure B demonstrates the learned FrugalMCT strategy. As shown in Figure E (a), the learned FrugalMCT reduces the cost by mostly using the Everypixel API (45%, 6S) and occasionally calling Microsoft API (32%, 10$).Note that its performance depends on the threshold value p. As shown in Figure E (b) and (c), for small thresholds. FrugalMCT tends to call the more accurate and expensive APIs. However, 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 ő value learned by FrugalMCT (blue point in Figure Hl (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
7

---

Under review as a conference paper at ICLR 2022
Table 2: Cost savings achieved by FrugalMCT that reaches same accuracy as the best commercial
API. On average the cost saving across the evaluated datasets is 73%.
Dataset
Accuracy (%)
Best API S
Our $
Save
PASCAL (Everingham ala 2015)
74.8
1.4
86%
MIR Husskes & Lev. 2008)
41.2
10
4.2
58%
COCO at 2014
47.5
3
70%
MTWI (He al
67.9
210
30
86%
ReCTS Zhang ct al, 2019)
61.3
210
78
63%
LSVT (Sun all 2019)
53.8
210
67
68%
CONLL (Sang & Meulder M11E
52.6
3
1.5
50%
ZHNER ZZN
61.3
30
0.7
98%
GMB
50.1
4.1
80%
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 B (c). 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.
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 Table 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 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 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 the training dataset. We also com- pared with an adapted version of the previous state-of-the-at for single label task, FrugalML. To adapt it multi-label tasks, we use the average quality score over all predicted labels as a single score, and cluster all labels into "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 accuracy estimator) than FrugalML (directly using the label info), and (ii) adopts label combiner designed for multi-label tasks. Ensemble methods such as majority votes (in the appendix ( produce accuracy similar FrugalMCT, but their cost is much higher.
Note that there is little performance difference between the online FrugalMCT strategy and the of- fline 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 g shows, Fru- gaIMCT able provide nontrivial accuracy estimates which enables its success. It's interesting to note that the accuracy predictor doesn't It need to be perfect for FrugalMCT to do well; for example, the root mean square error (RMSE) of the accuracy predictor 0.28 PASCAL, but FrugalMCT still produces consistently better accuracy than FrugalML. We also evaluated FrugalMCT's perfor- mance when the accuracy predictors are obtained via two AutoML toolkits, auto-sklearn (Feurer
atll 20A) and Auto-Py Torch (Mendoza et all 2019) instead of random forest, and observe similar performance.
8

---

Under review as a conference paper at ICLR 2022
0.60
0.55
Accuracy
6.60
6.70
6.75
0.65
6.66
350
Everypixel
Microsoft
FrugaIMCT (DAP)
FrugelML
FrugalMCT
FrugalMCT (OFL)
Google
20.40 00.4
025
0.33
0.30
0.45
0.0
SSD
Everypixel
Google
Accuracy
0:25
0.3
045
644
Everypixal
Microsoft
Google
0.50
23
0.15
10
20
026
10
20
Budget
Budget
Budget
(a) PASCAL
(b) MIR
(c) COCO
0.65
Accuracy
Accuracy
0.00
Tencent
2.55
Tencent
Google
ILYTEE
Tencent
0.55
PP-OCK
Google
FLYTEK
0.50
PP.OCR
Sbogle
PP-OCR
ViFLYTEK
0.60
0.90
Budget
Budget
Budget
(d) MTWI
(e) ReCTS
LSVT
0.60
0.75
0.55
Accuracy
Accuracy
Accuracy
6.50
1BM
Google
IBM
0.80
Google
IBM
8.45
Spacy
Spacy
Amazon
Google
Spacy
20
Budget
Budget
Budget
(g) CONLL
(h) ZHNER
GMB
Figure 4: Accuracy cost trade-offs. The offline FrugalMCT (black) observes the full data and then make decisions. The online FrugalMCT (red) matches the offline performance in all the experiments. DAP (grey) is an oblation of FrugalMCT where dummy accuracy predictor is used. FrugalML (orange) is the previous state-of-the-art method. The task of row 1, 2, 3 is MIC, STR, and NER.
0.80
0.70
0.60
Accuracy
Accuracy
Accuracy
0.75
0.65
0.55
FrugalMCT
FrugalMCT (OFL)
0.70
2000
4000
6000
0.60
2000
4000
0.50
2000
4000
Training Data Size
Training Data Size
Training Data Size
(a) PASCAL
(b) MTWI
(c) CONLL
Figure 5: Testing accuracy v.s.training data size. The fixed budget is 6, 15, respectively.
Effects of Training Sample Size. Finally we study how the training dataset size affects Fru- galMCT's performance. As shown in Figure B. across different tasks, few thousand training samples are typically sufficient to learn the optimal FrugalMCT strategy. This is usually more effi- cient than training customized ML model from scratch.
CONCLUSION
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 fore- casts 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 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 empir- ical 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.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Amazon Comprehend API. 2020].
aews.amazon. com/ com/comprehent
[Accessed Oct-
Everypixel Image Tagging API. 2020J.
Ltts:/ api [Accessed Oct-
Google NLP http://///a.....0000000000/11110 -anguugganggeeeeee [Accessed Oct- 2020].
Google Vision API. Btt::///00o...0000100000011/2112 [Accessse
[Accessed Oct-2020).
IBM NLP
www...bb 1bm. htt.://:wwo.........ooooooooooo.
www.
[Accessed Oct-2020J.
iFLYTEK Text Recognition TttC:///4A0.......0.0000002.111. [Accessed Oct-2020].
Microsoft computer
httss://aurre.icrroocff htt.c/ooooo..coomee-s/////////- com//ee/su///eee1cc
[Accessed Oct-2020).
PaddleOCR, text recgonition tool from GitHub. PadaTe0c1 [Accessed Oct-2020j.
SSD, multi-label image classification tool from GitHuub/ensooffooWHHbb. https://tthup
dev /ttp//////ppe/eaaaa....../ wttp////ee..e///o//ooooooeeetet. v2/1 [Accessed Oct-2020).
spaCy, named entity recognition tool from https///ttthb...mm//pp..... seacy [Accessed Oct-2020).
Tencent Text Recognition http:://iii..i.oooo.o..e..o.ooo. [Accessed Oct-2020).
ZHNER http:////.ll..oooooyry././/aaaee
Bata [Accessed Oct-2020).
Md. Mostofa Akbar, Mohammad Sohel Rahman, Mohammad Kaykobad, Eric G. Manning, and Gholamali C. Shoja. Solving the multidimensional multiple-choice knapsack problem by con- structing convex hulls. Comput. Oper. Res., 33: 2359-121227, 2006. doi: 10. c0.10066).0rr.20400..000 URL htt.ttttt//.o...om wtt.//0...06///./..... cor 2004. 09.00.........
Ewa M. Bednarczuk, Janusz Miroforidis, and Przemyslaw Pyzel. A multi-criteria approach to approximate solution of multiple-choice knapsack problem. Comput. Optim. Appl., 70(3):
889-910, 2018. doi: 10.10077110589--11-999833 URL https://dol.orgg org.
81M589 -98H-
Johan Bos. The groningen meaning bank. Proceedings of the Joint Symposium on Semantic Processing. Textual Inference and Structures in Corpora, JSSP 2013, Trento, Italy, November 20-22, 2013, 2. Association for Computational Linguistics, 2013. URL hetps: /ww.
8C Bclweb. O.C/ wwt.:/rr/w.ttoooy./ooooom
Joy Buolamwini and Timnit Gebru. Gender shades: Intersectional accuracy disparities in com- mercial gender classification. In Sorelle Friedler and Christo Wilson (eds.), Conference on Fairness, Accountability and Transparency, FAT 2018, 23-24 February 2018, New York, NY, USA, volume 81 of Proceedings of Machine Leurning Research, pp. 77-91. PMLR, 2018. URL http://proceent ngs m.r. press / vtt/vv1/bbbuu http/bullaattt ammw iin html
Zhaowei Cai, Mohammad Saberian, and Nuno Vasconcelos. Learning complexity aware cascades for deep pedestrian detection. In 2015 IEEE International Conference Computer Vision, ICCV 2015, Santiago, Chile, December 7-13, 2015, pp. 3361-3369. IEEE Computer Society, 2015. doi: 10.1 109/ICC2.2015.884 URL https: org/ 1T................. 15..1/99/CCC 2015. 2015.384 384.
10

---

Under review as a conference paper at ICLR 2022
Guibin Chen, Deheng Ye, Zhenchang Xing, Jieshan Chen, and Erik Cambria. Ensemble appli- cation of convolutional and recurrent neural networks for multi-label text categorization. In 2017 International Joint Conference
Neural Networks, IJCNN 2017, Anchorage, AK, USA, May 14-19, 2017, pp- 2377-2383. IEEE, 2017. doi: 00.1109/CCNN.2211.7966666
URL
https: /o01 ww.. TO. T1097 JCNN. 2017 7966144
Lingjiao Chen, Matei 7aharia, and James Y. Zou. Frugalml: How to use ML prediction apis more accurately and cheaply. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33; An- nual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
Xuan Chen, JunHao Liew, Wei Xiong, Chee-Kong Chui, and Sim Heng Ong. Focus, segment and erase: An efficient network for multi-label brain tumor segmentation. In Vittorio Ferrari, Mar- tial Hebert, Cristian Sminchisescu, and Yair Weiss (eds.), Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XIII, vol- ume 11217 of Lecture Notes in Computer Science, pp. 674-689, Springer, 2018. doi: 10.1007/ 01261
URL https://dos www.oo.rrr//oooooooooo 10.
e00.
Alex G. C. de Sá, Gisele I.. Pappa, and Alex A. Freitas. Towards a method for automatically selecting and configuring multi-label classification algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO '17, pp. 11251132, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450349390, doi: 10.1145/ 3067695.3082053. URL
3082055
Nikhil R. Devanur and Thomas P. Hayes. The adwords problem: Online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, EC '09, pp. 7178, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605584588 doi: 10.1145//566377115563444
URL sEtos://dol
01155/166677441663338 1666384
Nikhil R. Devanur and Thomas P. Hayes. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. J. ACM, 66(1), January 2019. ISSN 0004-5411. I. doi: 10.1 145/3284 URL
Yuning Du Chenxia Li, Ruoyu Guo, Xiaoting Yin, Weiwei Liu, Jun Zhou, Yifan Bai, Zilin Yu, Yehua Yang, Qingqing Dang, and Haoshuang Wang. PP-OCR: A practical ultra lightweight OCR system. CoRR, 099944,,,,94,, 2020. URL bttps://arxii http:////awww..o////////////////
org. wtw.aa///....... 099411
Mark Everingham, S. M. Ali Eslami, Luc Van Gool, Christopher K. I. Williams, John M. Winn, and Andrew Zisserman. The pascal visual object classes challenge: A retrospective. Int. J. Comput. Vis., 111(1):98-136 2015. doi: 10.10077/11263-0140000 T00 7007/51 (007/511233-11--1111
URL bttas://aoi.oro:
Matthias Feurer, Aaron Klein, Katharina Eggensperger, Jost Springenberg, Manuel Blum, and Frank Hutter. Efficient and robust automated machine learning. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems 28, pp. 2962-2970 Curran Associates, Inc., 2015.
Mengchao He, Yuliang Liu, Zhibo Yang, Sheng Zhang, Canjie Luo, Feiyu Gao, Qi Zheng, Yongpan Wang, Xin Zhang, and Lianwen Jin. ICPR2018 contest on robust reading for multi-type web images. In 24th International Conference on Pattern Recognition, ICPR 2018, Beijing, China, August 20-24, 2018, pp. 7-12. IEBE Computer Society, 2018. doi: 20009//PP..018.55444444 6546143
URL https: / dol. org. 10. 11tp//00..99//1...2200
Hossein Hosseini, Baicen Xiao, and Radha Poovendran. Google's cloud vision API is not robust to noise. In Xuewen Chen, Bo Luo, Feng Luo, Vasile Palade, and M. Arif Wani (eds.), 16th IEEE International Conference on Machine Learning and Applications, ICMLA 2017, Cancun, Mexico, December 18-21, 2017, pp. 101-105. IEEE, 2017. doi: 10.1109/C
172.
URL https: /tops:://oo..o /ooi .rrg///// 10. 110.1109/TMMM.. 2017. 0-77201172
11

---

Under review as a conference paper at ICLR 2022
Hossein Hosseini, Baicen Xiao, and Radha Poovendran. Studying the live cross pross-platform circulation of images with computer vision API: An experiment based on a sports media event. International Journal of Communication, 13:1825-1845, 2019.
Mark Huiskes and Michael S. Lew. The MIR flickr retrieval evaluation. Michael S. Lew, Alberto Del Bimbo, and Erwin M. Bakker (eds.), Proceedings of the 1st ACM SIGMM Interna- tional Conference on Multimedia Information Retrieval, MIR 2008, Vancouver, British Columbia, doi: 10.1145/1 111.660099111611100 1400104. URL
Canada, October 30-31, 2008, pp. 39 43. ACM, 2008.
460096. 11w.1144119666..... 1461104
T145/
Allison Koenecke, Andrew Nam, Emily Lake, Joe Nudell, Minnie Quartey, Zion Mengesha, Connor Toups. John R. Rickford, Dan Jurafsky, and Sharad Goel. Racial disparities in au- tomated speech recognition. Proc. Narl. Acad. Sci. USA, 117(14)7684-768, 2020. doi: REtp::/ /ttp///t..o.ooo/.//oo//ooo/oooot .rg/ 10. 10/3/ 19157 1915768117
10.1073/pnas.1915 1915768117.
Pulkit Kumar, Monika Grewal, and Muktabh Mayank Srivastava. Boosted cascaded convnets for multilabel classification of thoracic diseases in chest radiographs. In Aurélio Campilho, Fakhri Karray, and Bart M. Haar Romeny (eds.), Image Analysis and Recognition 15th Interna- tional Conference, ICIAR 2018, Póvoa de Varzim, Portugal, June 27-29, 2018, Proceedings, vol- 10882 of Lecture Notes in Computer Science, pp. 546-552, Springer, 2018. doi: 10.1007/ 978-3-319-93000-88
URL htttps://do..oo www./orgg...o....... wtt.or/g.....0/11...11. 3- 319 93000-8
62
Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper R. R. Uijlings, Ivan Krasin, Jordi Pont- Tuset, Shahab Kamali, Stefan Popox, Matteo Malloci, Alexander Kolesnikov, Tom Duerig, and Vittorio Ferrari. The open images dataset V4. Int. J. Comput. Vis., 18887))1956-191,,, 2020. doi: 10.1007/ 11123--22000111--2 URL https: /tops://doi.coo 10t.:/1....000111 /tt.:/0....0011.110000..1225231. 2100011001000112222-000000-11110
Chen Lee, John Lehoczky, Ragunathan Rajkumar, and Daniel Siewiorek. On quality of service optimization with discrete qos options. In Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposim, RTAS'99 '9, Vancouver, British Columbia, Canada, June 2-4, 1999, URL nEEDS://
pp. 276. IEEE Computer Society, 1999. doi: 10.109/TTTAS..199.7777 10. 1.....119/TTTA.. 1999. 777680.
Xiaocheng Li, Chunlin Sun, and Yinyu Ye. Simple and fast algorithm for binary integer and online linear programming. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: An- nual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6- 12, 2020, virtual, 2020. URL httt::://proceeeiiig www.unn....nnurrro nww.ipe.ppp.... wtwpuu//w..cc/aaeeee///////////
www.://aabraaaaZZ..... 74he:/ -aaebb//5hhh---stt Abst htmll
Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Pi- otr Dollár, and C. Lawrence Zitnick. Microsoft COCO: common objects in context. In David J. Fleet, Tomás Pajdla, Bernt Schiele, and Tinne Tuytelaars (eds.), Computer Vision ECCV 2014
13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V, vol-
ume 8693 of Lecture Notes in Computer Science, pp. 740-755. Springer, 2014. doi: 10.1007/
978-3-319- 10602- 48. URL pttps: //o:://doo...o org 11t.1100.001/191 10-311910605 10602-1
88.
Han Liu, Pete Burnap, Wafa Alorainy, and Matthew L.. Williams. Fuzzy multi-task learning for hate speech type identification. Ling Liu, Ryen W. White, Amin Mantrach, Fabrizio Silvestri, Julian J. McAuley, Ricardo Baeza- Yates, and Leila Zia (eds.), The World Wide Web Conference, WWW 2019, San Francisco, CA, USA, May 13-17, 2019, pp. 3006-3012, ACM, 2019. doi: 10. 0t55/3308855.3313544 URL bitps: /tt.////ii/// org 10. 114.1..333111581111.8 3313546
Hector Mendoza, Aaron Klein, Matthias Feurer, Jost Tobias Springenberg, Matthias Urban, Michael Burkart, Maximilian Dippel, Marius Lindauer, and Frank Hutter. Towards automatically-tuned deep neural networks. In Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren (eds.), Auto- mated Machine Learning Methods, Systems, Challenges, The Springer Series Challenges in Machine Learning, pp. 135-149. Springer, 2019. doi: 10. kttps://0a /tg//0.000 1007 0700777788-18 0-009778---00000--1000000000000-
URL
12

---

Under review as a conference paper at ICLR 2022
Jose M. Moyano, Eva Lucrecia Gibaja Galindo, Krzysztof J. Cios, and Sebastián Ventura. Review of ensembles of multi-label classifiers: Models, experimental study and prospects. Inf. Fusion, 44:33 45, 2018. doi: 10.
URL kttps: /o1 wtt./o..01.....
inf fuffus.e 2017 12.00...
Arjun Pakrashi and Brian Mac Namee. Cascademl: An automatic neural network architecture evo- lution and training algorithm for multi-label classification (best technical paper). In Max Bramer and Miltos Petridis (eds.), Artificial Intelligence XXXVI 39th SGAI International Conference on Artificial Intelligence, Al 2019, Cambridge, UK, December 17-19, 2019, Proceedings, vol- ume 11927 of Lecture Notes in Computer Science, pp. 3-17. Springer, 2019. doi: 10.1007/ 978-3-030-34885-41 URL https: http://doo..rggooo. www.org///..... 1007/978 10 030 34885-4--001
(S. Martello Pamela H. Vance and P. Toth). Knapsack problems: Algorithms and computer im- plementations, SIAM Rev. 35(4):684-685, 1993. doi: 10.1 10.1137/1035174
URL https:
//doi.orq/ 111.0.1..11011111
Jesse Read, Bernhard Pfahringer, and Geoffrey Holmes. Multi-label classification using ensembles of pruned sets. In Proceedings of the 8th IEEE International Conference on Data Mining (ICDM 2008), December 15-19, 2008, Pisa, Italy pp. 995-1000. IEEE Computer Society, 2008. doi: 10.1 10/1100..2222000..4 URL httpp::/dont org
(A..0///C..220/0 2008.
Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for multi-label classification. Mach. Learn., 85(3)3333-359 2011, doi: 10.10077110994401-55555-- URL
https://doi.co http://00..000110001111111111111 525---6-555
Arsénio Reis, Dennis Paulino, Vítor Filipe, and João Barroso. Using online artificial vision ser- vices to assist the blind an assessment of microsoft cognitive services and google cloud vi- sion. In Álvaro Rocha, Hojjat Adeli, Luís Paulo Reis, and Sandra Costanzo (eds.), Trends and Advances in Information Systems and Technologies Volume 2 [WorldCIST" 18, Naples, Italy, March 27-29, 2018], volume 746 of Advances in Intelligent Systems and Computing, pp. 174- doi:
184. Springer, 2018
URL attps:/ org/10.
2007/978-3-319-777
17.
Erik F. Tjong Kim Sang and Fien De Meulder. Introduction to the conll-2003 shared task: Language- independent named entity recognition. In Walter Daelemans and Miles Osborne (eds.), Proceed- ings of the Seventh Conference on Natural Language Learning. CoNLL 2003, Held in cooperation with HLT-NAACL 2003, Edmonton, Canada, May 31 June 1, 2003, pp- 142- 147. ACL, 2003.
URL https: www acl
Prabhakant Sinha and Andris A. Zolmers. The multiple-choice knapsack problem. Oper: Res., 27 (3):503-515, 1979. doi: (0.1287/0pre.27.3.500 URL
22 3. 54X1.
Yi Sun, Xiaogang Wang. and Xiaoou Tang. Deep convolutional network cascade for facial point detection. In 2013 IEEE Conference on Computer Vision and Pattern Recognition, Portland, OR, USA, June 23-28, 2013, pp. 3476-3483. IEBE Computer Society, 2013. doi: 10.1109/CVPR. 2013.446.
Yipeng Sun, Dimosthenis Karatzas, Chee Seng Chan, Lianwen Jin, Zihan Ni, Chee Kheng Chng. Yuliang Liu, Canjie Luo, Chun Chet Ng, Junyu Han, Errui Ding, and Jingtuo Liu. ICDAR 2019 competition on large-scale street view text with partial labeling RRC-LSVT. In 2019 Inter- national Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019, pp. 1557-1562. IEEE, 2019, doi: 10. 20.110//CDAR..2110000022 URL
/ttps://dor www.oo../0........ 1109/ ICDAR 2019.0025000
Chris Thorton,, Frank Hutter, Holger H. Hoos, and Kevin reyton-Brown. Auto-weka: Com- bined selection and hyperparameter optimization of classification algorithms. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, KDD '13, pp. 847855, New York, NY. USA, 2013. Association for Computing Machin- ery. ISBN 9781450321747. doi: 10. 10.11452487355.2448666 URL attps://do1 (T45/2487575
13

---

Under review as a conference paper at ICLR 2022
Grigorios Tsoumakas and loannis P. Vlahavas. Random k -labelsets: An ensemble method for multilabel classification. In Joost N. Kok, Jacek Koronacki, Ramón López de Mántaras, Stan Matwin, Dunja Mladenic, and Andrzej Skowron (eds.), Machine Learning: ECML 2007, 18th European Conference on Machine Learning, Warsaw, Poland, September 17-21, 2007, Proceed- ings, volume 4701 of Lecture Notes in Computer Science, pp. 406-417. Springer, 2007. doi: 10.1007/978-3 0--540074458-55
Paul Viola and Michael Jones. Robust real-time object detection. In International Journal of Com- puter Vision, 2001a.
Paul A. Viola and Michael J. Jones. Fast and robust classification using asymmetric adaboost and detector cascade. In Thomas G. Dietterich, Suzanna Becker, and Zoubin Ghahramani (eds.), Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, Canada], pp. 1311-1318. MIT Press, 2001b.
Lidan Wang, Jimmy J. Lin, and Donald Metzler. A cascade ranking model for efficient ranked retrieval. In Ying Ma, Jian Yun Nic, Ricardo Baeza- Yates. Tat-Seng Chua, and W. Bruce Croft (eds.), Proceeding of the 34th International ACM SIGIR Conference on Research and De- velopment in Information Retrieval, SIGIR 2011, Beijing, China, July 25-29, 2011, I, pp- 105- 114. ACM, 2011. doi: 10.1145/2009916.209933 URL https: /ttp//doi..gg////oooooooo
2009918 6. 20099341
R. Weischedel, E. Hovy, M. Marcus, and Martha Palmer. Ontonotes
large training corpus for
enhanced processing. 2017.
Marcel Wever, Alexander Tornede, Felix Mohr, and Eyke Hüllermeier. Automl for multi-label classification: Overview and empirical evaluation. IEEE Trans. Pattern Anal. Mach. Intell., 43 (9):3037-3054, 2021. doi: 10.1109/TPAMM.2201..0000
URL Fttps://doi.orq/
[109/TPAMI 2021 3051276
Xin-Shun Xu, Yuan Jiang, Liang Peng. Xiangyang Xue, and Zhi-Hua Zhou. Ensemble approach based on conditional random field for multi-label image and video annotation. In K. Selçuk Candan, Sethuraman Panchanathan, Balakrishnan Prabhakaran, Hari Sundaram, Wu-chi Feng, and Nieu Sebe (eds.), Proceedings the 19th International Conference on Multimedia 2011, Scottsdale, AZ, USA. November 28- December 1, 2011, pp. 1377-1380. ACM, 2011. doi: 10. URL pttps://doi.co 1ttp:/00111//222222222 2072019.
1145/2072298.2077222
Zhixiang Eddie Xu, Matt J. Kusner, Kilian Q. Weinberger, Minmin Chen, and Olivier Chapelle. Classifier cascades and trees for minimizing feature evaluation cost. Mach. Learn. Res., 15(1): 2113-2144, 2014, URL http: //d1 acm. www..orrr/cc..o carr//cite tatii on cfm? d=2670319.
Yuanshun Yao, Zhujun Xiao, Bolun Wang, Bimal Viswanath, Haitao Zheng, and Ben Y. Zhao. Complexity vs. performance: empirical analysis of machine learning as service. In Steve Uhlig and Olaf Maennel (eds.), Proceedings of the 2017 Internet Measurement Conference, IMC 2017, London, United Kingdom, November 1-3, 2017, pp. 397. ACM, 2017. doi: (0.11455//3133533333322 URL https: htt.///olor//oo///ooooooo wtt.:///1.1.111111111111.. 31313721
Min-Ling Zhang and Hui-Hua Zhou. A review on multi-label learning algorithms. IEEE Trans. Knowl. Data Eng., 26(8):181911837, 2014. doi: 10. (0.1109/TKDD.22133..33 URL httos://do1.
org/10. 1109 TADE. 2013.39
Rui Zhang, Mingkun Yang, Xiang Bai, Baoguang Shi, Dimosthenis Karatzas, Shijian Lu, C. V. Jawahar. Yongsheng Zhou, Qianyi Jiang, Qi Song, Nan Li, Kai Zhou, Lei Wang, Dong Wang. and Minghui Liao. ICDAR 2019 robust reading challenge on reading chinese text on signboard. In 2019 International Conference on Document Analysis and Recognition, ICDAR 2019, Sydney, Australia, September 20-25, 2019, pp. 1577-1581. IEEF, 2019. doi: 10.1 10.1100//DDRR.200 2019.00253. URL /tEtps://do..rrg/ /ttp:///oooooooooo//oooo 10. T10 09/ ICDAR. 2019 00253
Yunhong Zhou and Victor Naroditskiy. Algorithm for stochastic multiple-choice knapsack prob- lem and application to keywords bidding. In Proceedings of the 17th International Confer- World Wide Web, WWW '08, pp. 11751176. New York, NY, USA, 2008. Associa- tion for Computing Machinery. ISBN 9781605580852. doi: 10.1144//367499.133777 URL ht.tps://doi.. .tw.:ioorgg/000 11t.:/..0r011111111111111000
14


Reviews:
[{"review_id": "rDT-c6WgJlP", "reviewer": "Reviewer_rXPL", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Strengths:\n- novel problem setup of MLaaS, which is very practical for industrial practionioners\n- solving the API selection problem as relaxed integer programing seems techincal sounds\n- most of the writing is clear and easy to follow\n\n## Weakness:\n- While the paper aims to solve for multi-label problem, most components in the proposed FrugalMCT seem not tailor for the mulit-label problem, except for label combination part mentioned in Sec 3.4.\n- FrugalMCT needs call all candidate APIs do prediction on the training set so that it can collect supervision to learn the accuracy predictors. This step induces extra costs, but did not show up in the experiment results.\n\n## Major Comments\n- It seems to me that we can also apply FrugalMCT framework to an online production systems, where we have several ML predictors each with different inference latencies. We would like to select multiple ML predictors under the total latency constraint while striving for the best overal accuracy. It would be very interesting to see the impact of FrugalMCT in such cases.\n\n## Minor Comments\n- In the caption of Figure 1, \"is is high\" => \"is high\"\n", "summary_of_the_paper": "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.\n", "summary_of_the_review": "This paper is novel and techinical sounds. The proposed framework is not specially optimized for multi-label problems, but it is still a good paper to see in ICLR. Thus, I am incline that is paper is marginally above the acceptance threshold.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "okULlBnz3I", "reviewer": "Reviewer_R1P4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Soundness of the claims\nThe presented work is both theoretically grounded and empirically evaluated. In theory the authors' approach has convenient performance guarantees and can be implemented efficiently due to leveraging the specific structure of the problem. In the empirical evaluation the authors also prove the practical benefit of their approach demonstrating that their approach can achieve a higher predictive accuracy at a lower cost than the single best API, thereby outperforming the single best MLaaS platform in terms of both accuracy and cost which is not a really surprising result as long as the performances of the different APIs are complementary but still a strong result with practical benefits.\n\n# Significance\nThe contribution is significant and I estimate that this work will have great impact on the respective community.\n\n# Novelty\nAlthough the basic idea of selecting APIs has already been done in previous work (FrugalML), except for the basic idea, the remaining paper is to the best of my knowledge novel.\n\n# Relation with prior work\nRelated work is adequately and discussed in sufficient detail.\n\n# Clarity of writing\nThe paper is very well structured and clearly written. As already said, I really enjoyed the reading.\n\n# Relevance\nThe paper is definitely relevant to the machine learning community. The considered problem is relevant from a practical and very interesting from a methological perspective.", "summary_of_the_paper": "In the paper \"FrugalMCT: Efficient Online ML API Selection for Multi-Label Classification Tasks\" the authors present an approach to learn how to select online APIs that machine learning as a service (MLaaS) for the problem of multi-label classification. As APIs differ in terms of accuracy and query cost, their approach achieves greater accuracy than a single API at a lower cost than the best single API.", "summary_of_the_review": "Overall, I really enjoyed reading the paper and it was refreshing to see such a practical application and benefit for the end-user when using the approach in terms of both predictive accuracy and reduced costs. Therefore, I recommend to accept the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "RmYlVnovhuN", "reviewer": "Reviewer_py8t", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is a practical problem to combine the existing ML APIs for better performance under a budget. This paper focus on three multi-label classification tasks, which is more challenging than single-label classification. The most related previous work FrugalML ignores correlation between different ML APIs, while FrugalMCT could select from the combination of them.\n\nThis paper provides sufficient formalism and proofs. The empirical results show that FrugalMCT is effective on three multi-label classification tasks, including computer vision and NLP tasks. And the GitHub model cost is also analyzed. The case study demonstrate that the proposed FrugalMCT improves the classification results compared to the single ML API.\n\nThe authors mention that the complexity of FrugalML is exponential to the number of labels. It could be interesting to compare the training and inference time of FrugalML and FrugalMCT with different ML APIs.\n\n**Typo**\n\nIn the caption of Figure 1 *a cheap open source SSD model from GitHub **is is** high*.", "summary_of_the_paper": "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.", "summary_of_the_review": "This paper addresses a practical problem to combine the different ML APIs for multi-label classification and provides sufficient theoretical and empirical analyses. Recommended for acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "JnyKzrKr0C8", "reviewer": "Reviewer_S7of", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper amis to porpose a novel MLC method within a budget limitation. The technique is very old, the novelty and the experiments are very limited.\n1.The paper claims that \"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\". However, the paper does not provide the time cost of their proposed method and also do not report their time cost in the experiments. Since the paper aims to design an efficient ML API selection strategies for multi-label classification tasks, but the paper did no show any benifit of time of their proposed method from both thoery and experiments. This is a major flaw.\n2,The paper just combines existing technique, but did not bring any new technique, or new theory or new insight.\n3.The paper presents online algorithm. Then what is the regret bounds, i.e. bounding the regret of the proposed algorithm over the worst-case sequence?\n4.There are too many efficient XMLC methods. What are the advantanges and disadvantages of the proposed methods and other existing MLC or XMLC methods?What is the different and connection between them?\n5.Can the proposed method converge? Can you provide the theory and experiments guarantee?\n6.Can you test your method on XMLC datasets? Can you compare your method with popular XMLC methods such as PPD-Sparse, SLEEC,SiameseXML,ECLARE,LightXML on Amazon-3M and WikiLSHTC-325K\t? please refer to http://manikvarma.org/downloads/XC/XMLRepository.html", "summary_of_the_paper": "The paper porposes a method to adaptively select and combine ML APIs for multi-label classificaiton within a budget limitation. The techinique is very old, the novelty and the experiments are very limited.", "summary_of_the_review": "1.The paper claims that \"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\". However, the paper does not provide the time cost of their proposed method and also do not report their time cost in the experiments. Since the paper aims to design an efficient ML API selection strategies for multi-label classification tasks, but the paper did no show any benifit of time of their proposed method from both thoery and experiments. This is a major flaw.\n2,The paper just combines existing technique, but did not bring any new technique, or new theory or new insight.\n3.The paper presents online algorithm. Then what is the regret bounds, i.e. bounding the regret of the proposed algorithm over the worst-case sequence?\n4.There are too many efficient XMLC methods. What are the advantanges and disadvantages of the proposed methods and other existing MLC or XMLC methods?What is the different and connection between them?\n5.Can the proposed method converge? Can you provide the theory and experiments guarantee?\n6.Can you test your method on XMLC datasets? Can you compare your method with popular XMLC methods such as PPD-Sparse, SLEEC,SiameseXML,ECLARE,LightXML on Amazon-3M and WikiLSHTC-325K\t? please refer to http://manikvarma.org/downloads/XC/XMLRepository.html", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors study a practical problem of selecting/combining existing multi-label classification APIs under a budget constraint for a specific problem instance on hand. The task can be viewed as an (online) integer programming problem when given an accuracy estimator for the combination performance. The authors relax the integer constraints and propose a framework to solve the task in the dual form. They also run experiments to validate that the proposed framework is advantageous (cost or accuracy-wise) over the best single API.

Most of the reviewers are positive about the practical value and the potential impacts of the work in applications/products/services. There are several disputes between the authors and some reviewers that cannot be fully resolved during the rebuttal. In the end, no reviewers express willingness to strongly champion for the acceptance of the paper, making the paper a borderline case. The decision is based on a careful examination of the current manuscript and every side's opinions.

* Novelty: Some reviewers question about the novelty of the work. There are two aspects about novelty: one is on whether the problem itself is novel (are the authors trying to propose a new multi-label method?) In this aspect, the authors' response, which states that they are not aiming at proposing a new method, but at solving an automation task for MLaaS users, appears believable. The other aspect is whether the solution technique, namely the relaxed integer programming and other techniques, are sufficiently novel. Some reviewers find the novelty aspect satisfactory, while others believe that the proposed optimization technique have been widely used in machine learning community. The authors did not clarify the similarity/difference of the proposed technique to existing ones during the rebuttal. In this sense, the technical novelty is not well justified.

* Speed: Some reviewers are concerned about different aspects of the running time and other costs. The authors emphasized the rapid speed in inference phase, particularly in Figure 3. Less is discussed about the time needed for the training phase (although the authors claim to be much smaller than the inference time)---somehow even the most positive reviewers have some questions about this aspect. The authors could add more clarification about the different "time" costs to the discussion. One dispute between some reviewers and the authors is about the *complexity* analysis of time, which is indeed missing in the current manuscript and can be a nice-to-have for future todos.

* Theoretical Guarantee: One major dispute between some reviewers and the authors is on the theoretical guarantee provided. The reviewers suggest a regret-style bound, which compares the solution to the worst-case sequence; the authors provide an optimization-style bound, which compares the solution to the absolute optimal solution. Different bounds have their different roles for supporting the framework. Given that the authors have provided some reasonable bounds, the lack of regret bound is not taken against the authors.

* Specialty: One concern raised by some reviewers is that the technique does not seem particularly tailored for multi-label classification (except some minor parts). In this sense, it is nice to have for the authors to discuss more on the wider applicability of the technique, and/or include some more specialty of the multi-label classification problem into the technique design.

After taking all the factors above into account, and calibrating the received scores to the distribution across the papers, it seems that the paper could use some more revision before being mature enough as an impactful work.
Decision: Reject