PaperlayerView exact revision on arXiv

Source-linked AI summary

FrugalML: How to Use ML Prediction APIs More Accurately and Cheaply

Lingjiao Chen, Matei Zaharia, James Zou

arXiv:2006.07512v1cs.LGcs.GTstat.ML

TL;DR

Because API prices and performance vary across providers and input classes, choosing APIs for a task and budget is challenging. FrugalML learns these differences and optimizes adaptive sequential API use; across evaluated tasks, it can reduce cost while matching the best API’s accuracy or improve accuracy at the same cost.

  • Problem

    Different providers charge different prices and perform better on different input classes, complicating API selection for a user’s data and budget.

    Source: §1 · p. 1

  • Method

    FrugalML jointly learns API strengths and weaknesses across data and optimizes an adaptive strategy that selects APIs within a user’s budget.

    Source: §1 · pp. 1–2

  • Results

    Across evaluated tasks, FrugalML matches the best individual API’s accuracy with up to 90% lower cost, or improves accuracy by up to 5% at the same cost.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The work characterizes heterogeneity in API cost and performance and leverages it to identify budget-aware strategies for calling APIs.

    Source: §5 · p. 9

    The demonstrated formulation uses 0-1 loss, though the reward can be generalized to other forms such as negative square loss for regression.

    Source: §3 · p. 4

Abstract

from arXiv · show

Prediction APIs offered for a fee are a fast-growing industry and an important part of machine learning as a service. While many such services are available, the heterogeneity in their price and performance makes it challenging for users to decide which API or combination of APIs to use for their own data and budget. We take a first step towards addressing this challenge by proposing FrugalML, a principled framework that jointly learns the strength and weakness of each API on different data, and performs an efficient optimization to automatically identify the best sequential strategy to adaptively use the available APIs within a budget constraint. Our theoretical analysis shows that natural sparsity in the formulation can be leveraged to make FrugalML efficient. We conduct systematic experiments using ML APIs from Google, Microsoft, Amazon, IBM, Baidu and other providers for tasks including facial emotion recognition, sentiment analysis and speech recognition. Across various tasks, FrugalML can achieve up to 90% cost reduction while matching the accuracy of the best single API, or up to 5% better accuracy while matching the best API's cost.

1 Introduction

Different APIs vary in price and in the input classes where they perform best, making API selection difficult under a user’s budget. FrugalML learns these differences and optimizes adaptive API strategies, achieving substantial cost savings or accuracy gains in experiments.

1 Introduction

  • API prices and performance vary across providers and input classes, and the more expensive APIs are not uniformly better.For example, Face++ performs best on FER+ surprise images, while Microsoft performs best on neutral images.Source: §1 · p. 1
  • FrugalML selects a base API, then can choose an add-on using both the base API’s quality score and predicted label.Unlike a simple cascade that uses a quality score alone, its adaptive strategy can choose a downstream service based on the predicted class.Source: §1 · pp. 1–3, Figure 1 · p. 2
  • Natural sparsity in the strategy optimization can be leveraged to design an efficient algorithm with provable guarantees.The optimization must account for the second predictor’s dependence on the first API’s prediction and confidence, and may allocate different budget fractions across classes.Source: §1 · p. 2
  • Up to 90% lower cost while matching the best individual API’s accuracy, or up to 5% better accuracy at the same cost, across evaluated classification tasks.Experiments use real-world APIs from diverse providers on facial emotion recognition, sentiment analysis, and speech recognition.Source: §1 · p. 2
  • The authors release a dataset of 612,139 samples annotated by commercial APIs to support further study of API differences and usage.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the classification setting and the outputs and costs of services in an MLaaS market.

2 Preliminaries

  • Vectors and matrices use bold notation, while scalars, sets, and functions use standard script; the section also defines all-ones and zero arrays, matrix indexing, [n], and the indicator function.Source: §2 · p. 3
  • The paper studies multiclass classification, assigning an input x from distribution D to one of L label classes.Source: §2 · p. 3
  • An MLaaS market contains K services for the same task; each returns a predicted label and quality score, with a unit cost for each call.A larger quality score indicates higher prediction confidence.Source: §2 · p. 3

3 FrugalML: a Frugal Approach to Adaptively Leverage ML Services

FrugalML chooses a budget-feasible adaptive API-calling strategy, using a base service’s label and quality score to decide whether and which add-on service to call. Its optimization exploits sparsity to support an efficient algorithm.

3 FrugalML: a Frugal Approach to Adaptively Leverage ML Services

  • The strategy first selects a base API, then uses its label and quality score to decide whether to invoke an add-on API and which one to use.The add-on choice can depend on both the base API’s predicted label and quality score.Source: §3 · pp. 3–4

3.1 Sparsity Structure in the Optimal Strategy

  • An optimal feasible strategy can choose its base service from at most two APIs, a sparsity structure that reduces the optimization problem’s computational complexity.Fixing the quality thresholds and add-on choices makes the optimization linear in the base-service probabilities; the stated sparsity result motivates a smaller master problem.Source: §3.1 · pp. 4–5

3.2 A Practical Algorithm

  • Algorithm 1 estimates conditional accuracy, interpolates budget-value functions, solves the master problem, then reconstructs the strategy by solving subproblems for the selected base services.For K and L around ten and more than a few thousand samples, the authors report M = 10 as a good value for accuracy and computational cost.Source: §3.2 · p. 5
  • With probability 1−ϵ, Theorem 3 bounds the produced strategy’s accuracy gap from the optimal strategy under its stated smoothness and sampling assumptions.The supplied theorem passage truncates the bound itself.Source: §3.2 · p. 5

4 Experiments

Experiments evaluate FrugalML on facial emotion recognition, sentiment analysis, and speech-to-text, examining cost savings, accuracy–cost trade-offs, and training-data needs. Across these settings, it often reduces cost while preserving or improving accuracy.

Experimental Setup

  • The evaluation covers facial emotion recognition, sentiment analysis, and speech-to-text, using commercial APIs and less expensive open-source models.The study also examines when FrugalML reduces cost without harming accuracy and how training-data size affects performance.Source: §4 · p. 6

Facial Emotion Recognition: A Case Study

  • On FER+, FrugalML exceeds Microsoft Face’s accuracy at much lower cost; 55% of inputs need only GitHub’s open-source CNN, keeping cost below half of Microsoft’s.The learned label-specific thresholds balance misclassification risk against unnecessary add-on calls.Source: §4 · p. 6, Figure 3 · p. 7
  • Majority vote reaches 82% accuracy but costs $30, six times FrugalML’s $5 budget; mixture of experts matches Microsoft at 81% accuracy and $10.Both comparison methods require fixed costs, whereas FrugalML lets users choose a budget.Source: §4 · pp. 6–7

Analysis of Cost Savings

  • FrugalML typically saves more than half the cost to match the best single API’s accuracy, reaching 90% savings on AUDIOMNIST.Table 3 summarizes cost savings at the accuracy of the best commercial API.Source: §4 · p. 7, Table 3 · p. 7

Accuracy and Cost Trade-offs

  • On FER+ and AFFECTNET, small costs yield over 2% accuracy gains; on RAFDB, larger costs yield over 5%, and no API leads across all sentiment datasets.Baidu NLP performs best on WAIMAI and SHOP, while Google NLP performs best on YELP and IMDB.Source: Figure 4 · p. 8, §4 · p. 8

Effects of Training Sample Size

  • In Figure 5, with fixed budgets of 5, 1.2, and 20, 3,000 labeled samples were enough across all datasets, although datasets with more classes needed more samples.Source: §4 · p. 9, Figure 5 · p. 9

5 Conclusion and Open Problems

The conclusion presents FrugalML as a budget-aware framework for selecting API-calling strategies, reports efficient learning and empirical benefits, and identifies extension beyond classification as future work.

Conclusion

  • FrugalML identifies API-calling strategies under a user’s budget, with theoretical and empirical evidence of cost reduction and accuracy improvement.The paper reports that learning typically takes a few minutes on a modern machine.Source: §5 · p. 9
  • The work characterizes heterogeneity in API costs and performance and leverages it in FrugalML; it also plans to release 612,139 API-annotated samples and code.The dataset and code are offered as resources to stimulate further MLaaS research.Source: §5 · p. 9

Open Problems

  • Extending FrugalML beyond classification, including to object detection and language translation, is left as future work.Source: §5 · p. 9

A Extra Notations

The appendix defines notation for service-label probabilities and conditional quality and accuracy functions, and specifies common product operators.

Extra Notations

  • A_k,ℓ denotes the probability that service k predicts label ℓ; F_k,ℓ(X) is the conditional probability that its quality score is at most X.The passage conditions F_k,ℓ on the predicted label being ℓ.Source: A Extra Notations · p. 13
  • ψ_k1,k2,ℓ(α) denotes expected executed accuracy for service k2 when service k1 predicts label ℓ with a quality score below the corresponding threshold.The definition describes the conditional setup for the expected accuracy.Source: A Extra Notations · p. 13

B Algorithm Subroutines

The subroutines estimate API parameters, approximate intermediate functions, solve a subproblem, and optimize the master problem through a budget allocation.

Estimating Parameters

  • Parameter estimation uses empirical means and label-conditional quality-score quantiles, interpolates ψ estimates, and derives estimates of r_b and r^[−].The quantiles are computed from service scores conditional on the service’s predicted label.Source: B Algorithm Subroutines · p. 13

Solving subproblem 3.3

  • The subproblem solver evaluates candidate β values and uses piecewise-quadratic objectives that can be optimized efficiently over each piece.The passage identifies the optimization steps as maximizing φ_i and φ_i,j.Source: B Algorithm Subroutines · pp. 13–14

Constructing g_i(·)

  • The algorithm approximates g_i with linear interpolation between sampled values, setting g_i(c_i) and values below c_i to zero.Source: B Algorithm Subroutines · p. 14

Solving Master Problem 3.2

  • The master solver enumerates service and interpolation-interval candidates, solves linear programs for budget splits, and returns the best candidate solution.The split budgets must sum to the available budget.Source: B Algorithm Subroutines · p. 14

C.1 Helpful Lemmas

These lemmas establish sparse optimal solutions and regularity properties used in the paper’s optimization analysis. They also bound the error from approximating a Lipschitz function by linear interpolation.

C.1 Helpful Lemmas

  • An optimal solution exists with at most two nonzero entries.The proof constructs a feasible solution with the same objective value as an optimum and support size at most two.Source: §C.1 · pp. 14, 16
  • For u, C, v ≥ 0 and d > 0, the optimal value F(w) is Lipschitz continuous.The proof considers the ranges on either side of a feasible point with Cz∗ < d, then combines the bounds.Source: §C.1 · pp. 16–17
  • Linear interpolation from estimates with error at most ∆2 has error at most 3∆2 + 2∆1(b − a)/M.This applies when f is Lipschitz with constant ∆1 on [a,b] and the interval is divided into M steps.Source: §C.1 · p. 18

C.2 Proof of Lemma 1

The proof reduces the optimization over the first-stage API distribution to a linear program, then uses a sparsity lemma to characterize an optimal solution.

C.2 Proof of Lemma 1

  • The expected-accuracy and cost formulation yields a linear program over the first-stage distribution p[1].Its constraints include nonnegative probabilities, total mass at most one, and an additional linear constraint.Source: §C.2 · p. 19
  • An optimal first-stage distribution exists with at most two nonzero entries.The proof applies Lemma 4 after relaxing the total-mass equality to an inequality.Source: §C.2 · p. 19

C.3 Proof of Lemma 2

The proof derives expected accuracy and cost for an adaptive strategy by conditioning on its base service and any add-on service. The resulting expressions match those in Lemma 2.

C.3 Proof of Lemma 2

  • The strategy’s expected accuracy is obtained by conditioning on the base service and any add-on service.When no add-on is called, the strategy uses the base service’s prediction; when an add-on is called, the reward is that service’s reward.Source: §C.3 · p. 19
  • Expected cost is computed by conditioning on the base and add-on services, whose costs add when both are used.With no add-on, the strategy uses the base service and incurs its cost alone.Source: §C.3 · p. 20
  • The derived expected-accuracy and expected-cost expressions have the same form as those in Lemma 2.Source: §C.3 · pp. 19–20

C.4 Proof of Theorem 3

The proof of Theorem 3 analyzes the generated strategy’s computational cost, estimation error, and approximation error, using sparse optimization structure to establish exactness for Algorithm 2 and derive guarantees. It also bounds the accuracy penalty from adjusting the budget to control cost, including an O(Δb) loss when the available budget is reduced by Δb.

C.4 Proof of Theorem 3

  • Algorithm 1’s complexity includes O(NMK²) estimation work and a master optimization that invokes the subproblem MK times.The subproblem costs O(K²ML + ML−1); estimating A requires O(NK) work.Source: §C.4 · pp. 20–21
  • With probability 1 − ε, Lemma 9 bounds estimated accuracy and cost errors uniformly over all strategies.The proof uses sample-mean estimates and Chernoff bounds, and uses Lipschitz continuity to bound interpolation error.Source: §C.4 · p. 21
  • Algorithm 2 returns the exact optimal solution and value for Problem B.1, using the problem’s sparse structure.Lemma 13 establishes that an optimal solution exists with at most two nonzero entries in Π.Source: §C.4 · pp. 22, 24
  • An optimal solution exists with at most two nonzero entries in Π.The sparsity result supports the proof of Algorithm 2’s exactness.Source: §C.4 · p. 22
  • The function ˆh_k,ℓ(β) is Lipschitz continuous in β for β ≥ 0, with constant O(γ).The proof gives a constant of 1 + γ min_{j ≠ k} c_j.Source: §C.4 · p. 26
  • For all budgets and services, the piecewise-linear approximation error is O(γ/M) + O(1/M).The proof combines bounds over three budget intervals.Source: §C.4 · p. 29
  • Theorem 16 establishes a high-probability lower bound on the produced strategy’s expected accuracy relative to the optimal strategy.Its proof handles computational complexity, accuracy loss, and excessive cost in turn.Source: §C.4 · p. 30
  • When b − Δb ≥ 0, the optimal strategy under budget b − Δb loses at most O(Δb) expected accuracy relative to the optimum under budget b.The proof uses Lipschitz continuity of the optimal value as the budget changes.Source: §C.4 · pp. 31–32
  • Subtracting the excessive-cost term be from the subroutine budgets ensures the produced strategy meets budget b with high probability, at an additional accuracy loss of at most O(be).The proof bounds be by O((log ϵ + log K + log L)/N), a term it says is subsumed by Theorem 16’s accuracy drop.Source: §C.4 · p. 32

D Experimental Details

The experiments span facial emotion recognition, sentiment analysis, and speech recognition across 12 datasets, using commercial APIs and open-source models. On FER+, FrugalML trades class-level accuracy against the dataset’s label distribution, outperforming the fixed-threshold cascade at the same cost while using less cost than majority-vote ensembles.

ML tasks and services

  • The evaluation uses Google, Microsoft, Face++, Amazon, Baidu, and IBM services alongside task-specific GitHub or rule-based models; returned speech text is mapped to labels by smallest edit distance.Google’s categorical FER confidence scores are linearly interpolated to numeric values; speech datasets include digits, commands, and phrases.Source: D Experimental Details · p. 33

Datasets

  • The experiments cover 12 datasets: four facial-emotion, four sentiment, and four speech-recognition datasets, with dataset-specific filtering and label preparation.FER+ uses only its test portion because the GitHub CNN was pretrained on its training set; RAFDB and AFFECTNET retain basic emotions, while EXPW uses aligned faces with face confidence above 0.6.Source: D Experimental Details · p. 33

GitHub Model Cost

  • GitHub models’ equivalent prices are $0.0005 per 10,000 images for CNN, $0.00016 for Bixin and Vader per 10,000 texts, and $0.016 for DeepSpeech per 10,000 utterances.These estimates use inference times measured on an Amazon EC2 t2.micro instance; the text and speech timing limits are under 300 words and under 15 seconds, respectively.Source: D Experimental Details · p. 33, Figure 6 · p. 34

Case Study Details

  • API accuracy varies by emotion: GitHub leads on anger (0.73%), fear (0.81%), happy (0.90%), and sad (0.60%); Face++ leads on disgust (0.60%) and surprise (0.85%), while Microsoft leads on neutral (90%).GitHub performs poorly on neutral, Face++ struggles to distinguish fear from surprise, and Google struggles to distinguish anger from disgust.Source: D Experimental Details · p. 34
  • The mixture-of-experts baseline selects Microsoft in every case and has the same confusion matrix as Microsoft; unlike FrugalML, it cannot accept user-specified budget or accuracy constraints.The authors suggest this may reflect Microsoft’s performance across subspaces defined by hyperplanes under their simple linear raw-image gating model; more complex mixtures require more training complexity.Source: D Experimental Details · p. 34
  • At half Microsoft’s cost, FrugalML reaches 84% accuracy versus Microsoft’s 81%; majority vote reaches 82% but costs $30, five times FrugalML’s cost.The simple cascade also matches Microsoft’s accuracy at half the cost, but FrugalML improves accuracy on all classes except disgust compared with that cascade.Source: D Experimental Details · pp. 34, 36
  • Figure 7 confusion matrices show true labels by row and predicted labels by column, with each entry giving the likelihood of a predicted label conditional on the true label.The caption’s example says FrugalML correctly predicts 87% of surprise images as surprise.Source: D Experimental Details · p. 34, Figure 7 · p. 35
  • FrugalML’s learned strategy depends on data distribution: FER+ is dominated by neutral and happy images, so it accepts a slight neutral-accuracy drop for a larger happy-image improvement.The passage notes that training on a different distribution may produce a different strategy.Source: D Experimental Details · p. 36, Figure 8 · p. 36

Related papers

Loading 2006.07512v1…