Optimizing Data Collection for Machine Learning

Modern deep learning systems require huge data sets to achieve impressive performance, but there is little guidance on how much or what kind of data to collect. Over-collecting data incurs unnecessary present costs, while under-collecting may incur future costs and delay workflows. We propose a new paradigm for modeling the data collection workflow as a formal optimal data collection problem that allows designers to specify performance targets, collection costs, a time horizon, and penalties for failing to meet the targets. Additionally, this formulation generalizes to tasks requiring multiple data sources, such as labeled and unlabeled data used in semi-supervised learning. To solve our problem, we develop Learn-Optimize-Collect (LOC), which minimizes expected future collection costs. Finally, we numerically compare our framework to the conventional baseline of estimating data requirements by extrapolating from neural scaling laws. We significantly reduce the risks of failing to meet desired performance targets on several classification, segmentation, and detection tasks, while maintaining low total collection costs.


Introduction
When deploying a deep learning model in an industrial application, designers often mandate that the model must meet a pre-determined baseline performance, such as a target metric over a validation data set. For example, an object detector may require a certain minimum mean average precision before being deployed in a safety-critical setting. One of the most effective ways of meeting target performances is by collecting more training data for a given model.
Determining how much data is needed to meet performance targets can impact costs and development delays. Overestimating the data requirement incurs excess costs from collection, cleaning, and annotation. For instance, annotating segmentation masks for a driving data set takes between 15 to 40 seconds per object. For 100,000 images the annotation could require between 170 and 460 days-equivalent of time [1,2]. On the other hand, collecting too little data may incur future costs and workflow delays from having to collect more later. For example, in medical imaging applications, this means further clinical data acquisition rounds that require expensive clinician time. In the worst case, designers may even realize that a project is infeasible only after collecting insufficient data.
The growing literature on sample complexity in machine learning has identified neural scaling laws that scale model performance with data set sizes according to power laws [3][4][5][6][7][8][9][10]. For instance, Rosenfeld et al. [6] fit power law functions on the performance statistics of small data sets to extrapolate the learning curve with more data. In contrast, Mahmood et al. [2] consider estimating data requirements and show that even small errors in a power law model of the learning curve can translate to massively over-or underestimating how much data is needed. Beyond this, different data sources have different costs and scale differently with performance [11][12][13][14]. For example, although unlabeled data may be easier to collect than labeled data, some semi-supervised learning tasks may need an order of magnitude more unlabeled data to match the performance of a small labeled set. Thus, collecting more data based only on estimation will fail to capture uncertainty and collection costs.  Figure 1: In the optimal data collection problem, we iteratively determine the amount of data that we should have, pay to collect the additional data, and then re-evaluate our model. Our approach, Learn-Optimize-Collect, optimizes for the minimum amount of data q * t to collect. In this paper, we propose a new paradigm for modeling the data collection workflow as an optimal data collection problem. Here, a designer must minimize the cost of collecting enough data to obtain a model capable of a desired performance score. They have multiple collection rounds, where after each round, they re-evaluate the model and decide how much more data to order. The data has per-sample costs and moreover, the designer pays a penalty if they fail to meet the target score within a finite horizon. Using this formal framework, we develop an optimization approach for minimizing the expected future collection costs and show that this problem can be optimized in each collection round via gradient descent. Furthermore, our optimization problem immediately generalizes to decisions over multiple data sources (e.g., unlabeled, long-tail, cross-domain, synthetic) that have different costs and impacts on performance. Finally, we demonstrate the value of optimization over naïvely estimating data set requirements (e.g., [2]) for several machine learning tasks and data sets.
Our contributions are as follows. (1) We propose the optimal data collection problem in machine learning, which formalizes data collection workflows. (2) We introduce Learn-Optimize-Collect (LOC), a learning-and-optimizing framework that minimizes future collection costs, can be solved via gradient descent, and has analytic solutions in some settings. (3) We generalize the data collection problem and LOC to a multi-variate setting where different types of data have different costs. To the best of our knowledge, this is the first exploration of data collection with general multiple data sets in machine learning, covering for example, semi-supervised and long-tail learning. (4) We perform experiments over classification, segmentation, and detection tasks to show, on average, approximately a 2× reduction in the chances of failing to meet performance targets, versus estimation baselines.

Related work
Neural Scaling Laws. According to the neural scaling law literature, the performance of a model on a validation set scales with the size of the training data set q via a power law V ∝ θ 0 q θ1 [5,6,[8][9][10][15][16][17][18][19]. Hestness et al. [5] observe this property over vision, language, and audio tasks, Bahri et al.
[9] develop a theoretical relationship under assumptions on over-parametrization and the Lipschitz continuity of the loss, model, and data, and Rosenfeld et al.
[6] estimate power laws using smaller data sets and models to extrapolate future performance. Multi-variate scaling laws have also been considered for some specific tasks, for example in transfer learning from synthetic to real data sets [11]. Finally, Mahmood et al. [2] explore data collection by estimating the minimum amount of data needed to meet a given target performance over multiple rounds. Our paper extends these prior studies by developing an optimization problem to minimize the expected total cost of data collected. Specifically, we incorporate the uncertainty in any regression estimate of data requirements and further generalize to multiple data sources with different costs.
Active Learning. In active learning, a model sequentially collects data by selecting new subsets of an unlabeled data pool to label under a pre-determined labeling budget that replenishes after each round [20][21][22][23][24]. In contrast, our work focuses on systematically determining an optimal collection budget. After determining how much data to collect, we can use active learning techniques to collect the desired amount of data.
Statistical Learning Theory. Theoretical analysis of the sample complexity of machine learning models is typically only tight asymptotically, but some recent work have empirically analyzed these relationships [25,26]. Particularly, Bisla et al.
[10] study generalization bounds for deep neural networks, provide empirical validation, and suggest using them to estimate data requirements. In contrast, our paper formally explores the consequences of collection costs on data requirements.
Optimal Experiment Design. The topic of how to collect data, select samples, and design scientific experiments or controlled trials is well-studied in econometrics [27][28][29]. For example, Bertsimas et al. [30] optimize the assignment of samples into control and trial groups to minimize inter-group variances. Most recently, Carneiro et al. [31] optimize how many samples and covariates to collect in a statistical experiment by minimizing a treatment effect estimation error or maximizing t-test power. However, our focus on industrial machine learning applications differs from experiment design by having target performance metrics and continual rounds of collection and modeling.

Main Problem
In this section, we give a motivating example before introducing the formal data collection problem. We include a table of notation in Appendix A.
Motivating Example. A startup is developing an object detector for use in autonomous vehicles within the next T = 5 years. Their model must achieve a mean Average Precision greater than V * = 95% on a pre-determined validation set or else they will lose an expected profit of P = $1, 000, 000. Collecting training data requires employing drivers to record videos and annotators to label the data, where the marginal cost of obtaining each image is approximately c = $1. In order to manage annual finances, the startup must plan how much data to collect at the beginning of each year.
Let z ∼ p(z) be data drawn from a distribution p. For instance, z := (x, y) may correspond to images x and labels y. Consider a prediction problem for which we train a model with a data set D of points sampled from p(z). Let V (D) be a score function evaluating the model trained on D.
Optimal Data Collection. We possess an initial data set D q0 := {z i } q0 i=1 of q 0 points; we omit the subscript on D referring to its size when it is obvious. Our problem is defined by a target score V * > V (D q0 ), a cost-per-sample c of collection, a horizon of T rounds, and a penalty P for failure. At the end of each round t ∈ {1, . . . , T }, let q t be the current amount of data collected. Our goal is to minimize the total collection cost while building a model that can achieve the target score: The collection cost is measured by the difference in data set size between the final and the 0-th round c(q T − q 0 ) = c T t=1 (q t − q t−1 ), Because we collect data iteratively over multiple rounds (see Figure 1), we break (1) into the sum of differences per round. Specifically in each round, we 1. Decide to grow the data set to q t ≥ q t−1 points by samplingD : . Pay a cost c(q t − q t−1 ) and update D ← D ∪D.
2. Train the model and evaluate the score. If V (D) ≥ V * , then terminate. 3. If t = T , then pay the penalty P and terminate. Otherwise, repeat for the next round.
The model score typically increases monotonically with data set size [5,6]. This means that the minimum cost strategy for (1) is to collect just enough data such that V (D q T ) = V * . We can estimate this minimum data requirement by modeling the score function as a stochastic process. Let V q := V (D q ) and let {V q } q∈Z+ be a stochastic process whose indices represent training set sizes in different rounds. Then, collecting data in each round yields a sequence of subsampled data sets D qt−1 ⊂ D qt and their performances V (D qt ). The minimum data requirement is the stopping time which is a random variable giving the first time that we pass the target. Note that q * 1 = · · · = q * T = D * is a minimum cost solution to the optimal data collection problem, incurring a total cost c(D * − q 0 ) 1 .
Estimating D * using past observations of the learning curve is difficult since we have only T rounds. Further, Mahmood et al. [2] empirically show that small errors in fitting the learning curve can cause massive over-or under-collection. Thus, robust policies must capture the uncertainty of estimation.

Learn-Optimize-Collect (LOC)
Our solution approach, which we refer to as Learn-Optimize-Collect (LOC), minimizes the total collection cost while incorporating the uncertainty of estimating D * . Although D * is a discrete random variable, it is realized typically on the order of thousands or greater. To simplify our problem and ensure differentiability, we assume that D * is continuous and has a well-defined density. Assumption 1. The random variable D * is absolutely continuous and has a cumulative density function (CDF) F (q) and probability density function (PDF) f (q) := dF (q)/dq.
In Section 4.1, we first develop an optimization model when given access to the CDF f (q) and PDF F (q). In Section 4.2, we estimate these distributions and combine them with the optimization model. Finally in Section 4.3, we delineate our optimization approach from prior regression methods.

Optimization Model
We propose an optimization problem that for any t, can simultaneously solve for the optimal amounts of data to collect q t , . . . , q T in all future rounds. Consider t = 1 and to develop intuition, suppose we know a priori the exact stopping time D * . Then, problem (1) can be re-written as where the objective function is defined recursively as follows The objective differs slightly from (1) due to the indicator terms, which ensure that once we collect enough data, we terminate the problem. The second line follows from gathering the terms. The third line follows from observing that q 1 ≤ q 2 ≤ · · · ≤ q T are constrained.
In practice, we do not know D * a priori since it is an unobserved random variable. Instead, suppose we have access to the CDF F (q). Then, we take the expectation over the objective E[L(q 1 , . . . , q T ; D * )] to formulate a stochastic optimization problem for determining how much data to collect: Note that the collection variables should be discrete q 1 , . . . , q T ∈ Z + , but similar to the modeling of D * , we relax the integrality requirement, optimize over continuous variables, and round the final solutions. Furthermore, although problem (4) is constrained, we can re-formulate it with variables d t := q t −q t−1 ; this consequently replaces the current constraints with only non-negativity constraints d t ≥ 0. Finally due to Assumption 1, problem (4) can be optimized via gradient descent.

Learning and Optimizing the Data Requirement
Solving problem (4) requires access to the true distribution F (q), which we do not have in reality. In each round, given a current training data set D qt of q t points, we must estimate these distribution functions F (q) and f (q) and then incorporate them into our optimization problem.
Given a current data set D qt , we may sample an increasing sequence of R subsets D qt/R ⊂ D 2qt/R ⊂ · · · ⊂ D qt , fit our model to each subset, and compute the scores to obtain a data set of the learning curve R := {(rq t /R, V (D rqt/R ))} R r=1 . In order to model the distribution of D * , we can take B bootstrap resamples of R to fit a series of regression functions and obtain corresponding estimates . Given a set of estimates of the data requirement, we estimate the PDF via Kernel Density Estimation (KDE). Finally to fit the CDF, we numerically integrate the PDF.
In our complete framework, LOC, we first estimate F (q) and f (q). We then use these models to solve problem (4). Note that in the t-th round of collection, we fix the prior decision variables q 1 , . . . q t−1 constant. Finally, we collect data as determined by the optimal solution q * t to problem (4). Full details of the learning and optimization steps, including the complete Algorithm, are in Appendix B.

Comparison to Mahmood et al. [2]
Our prediction model extends the previous approach of Mahmood et al. [2], who consider only point estimation of D * . They (i) build the set R, (ii) fit a parametric functionv(q; θ) to R via least-squares minimization, and (iii) solve forD = arg min q {q |v(q; θ) ≥ V * }. They use several parametric functions from the neural scaling law literature, including the power law function (i.e., v(q; θ) := θ 0 q θ1 + θ 2 [2,8] where θ := {θ 0 , θ 1 , θ 2 }), and use an ad hoc correction factor obtained by trial and error on past tasks to help decrease the failure rate. Instead, we take bootstrap samples of R to fit multiple regression functions, estimate a distribution forD, and incorporate them into our novel optimization model. Finally, we show in the next two sections that our optimization problem has analytic solutions and extends to multiple sources.

Analytic Solutions for the T = 1 Setting
In this section, we explore analytic solutions for problem (4). The unobservable D * and sequential decision-making nature suggest this problem can be formulated as a Partially Observable Markov Decision Process (POMDP) with an infinite state and action space (see Appendix C.1), but such problems rarely permit exact solution methods [32]. Nonetheless, we can derive exact solutions for the simple case of a single T = 1 round, re-stated below Theorem 1. Assume F (q) is strictly increasing and continuous. If there exists then there exists an ≤ 1 − F (q 0 ) that satisfies P = c/f (F −1 (1 − )) and an optimal solution to the corresponding problem (5) is q * 1 := F −1 (1 − ). Otherwise, the optimal solution is q * 1 := q 0 .
When the penalty P is specified via a failure risk , the optimal solution to problem (5) is equal to a quantile of the distribution of D * . We defer the proof and some auxiliary results to Appendix C.2.
Theorem 1 further provides guidelines on choosing values for the cost and penalty parameters. While c is the dollar-value cost per-sample, which includes acquisition, cleaning, and annotation, P can reflect their inherent regret or opportunity cost of failing to meet their target score. A designer can accept a risk of failing to collect enough data Pr{q * < D * } = . From Theorem 1, their optimal strategy should be to collect F −1 (1 − ) points, which is also the optimal solution to problem (5).
6 The Multi-variate LOC: Collecting Data from Multiple Sources So far, we have assumed that a designer only chooses how much data to collect and must pay a fixed per-sample collection cost. We now explore the multi-variate extension of the data collection problem where there are different types of data with different costs. For example, consider long-tail learning where samples for some rare classes are harder to obtain and thus, more expensive [33], semi-supervised learning where labeling data may cost more than collecting unlabeled data [34], or domain adaptation where a source data set is easier to obtain than a target set [35]. In this section, we highlight our main formulation and defer the complete multi-variate LOC to Appendix D.
Consider K ∈ N data sources (e.g., K = 2 with labeled and unlabeled) and for each k ∈ {1, . . . , K}, let z k ∼ p k (z k ) be data drawn from their distribution. We train a model with a data set D := ∪ K k=1 D k where each D k contains points of the k-th source. The performance or score function of our model is V (D 1 , . . . , D K ). For each k, we initialize with q k 0 points. Let q 0 = (q 1 0 , . . . , q K 0 ) T denote the vector of data set sizes and let c = (c 1 , . . . , c K ) T denote costs (i.e., c k is the cost of collecting data from p k (z k )). Given a target V * , penalty P , and T rounds, we want to minimize the total cost of collection We follow the same steps shown in Section 4 for this problem. First, the learning curve is now a stochastic process {V q } q∈Z K + indexed in K dimensions. Next, the multi-variate analogue of the minimum data requirement in (2) is the minimum cost amount of data needed to meet the target: We randomly pick a unique solution to break ties. From Assumption 1, D * is a random vector with a PDF f (q) and a CDF F (q) := q 0 f (q)dq. Finally, the multi-variate analogue of problem (4) is The Multi-variate LOC requires multi-variate PDFs, which we can fit in the same way as discussed in Section 4.2. However, we now need multi-variate regression functions that can accommodate different types of data. In Appendix D, we propose an additive family of power law regression functions that can handle an arbitrary number of K sources. In our experiments, we also generalize the estimation approach of Mahmood et al. [2] to the multi-source setting for comparison.

Empirical Results
We explore the data collection problem over two sets of experiments covering single-variate K = 1 (Section 4) and multi-variate K = 2 (Section 6) problems. We consider image classification, segmentation, and object detection tasks. For every data set and task, LOC significantly reduces the number of instances where we fail to meet a data requirement V * , while incurring a competitive cost with respect to the conventional baseline of naïvely estimating the data requirement [2].
In this section, we summarize the main results. We detail our data collection and experiment setup in Appendix E. We expand our full results and experiments with additional baselines in Appendix F .

Data and Methods
When K = 1, the designer decides how much data to sample without controlling the type of data. We explore classification on CIFAR-10 When K = 2, the designer collects two types of data with different costs. We first divide CIFAR-100 into two subsets containing data from the first and last 50 classes, respectively. Here, we assume that the first 50 classes are more expensive to collect than the last; this mimics a real-world scenario where collecting data for some classes (e.g., long-tail) is more expensive than others. We then explore semi-supervised learning on BDD100K where the labeled subset of this data is more expensive than the unlabeled data; the cost difference between these two types is equal to the cost of data annotation.
We use a simulation model of the deep learning workflow following the procedure of Mahmood et al. [2], to approximate the true problem while simplifying the experiments (see Appendix E for full details). To avoid repeatedly sampling data, re-training a model, and evaluating the score, each  Figure 2: Mean ± standard deviation of 5 seeds of the ratio of data collected q * T /D * for different V * . The rows correspond to T = 1, 3, 5 and the columns to different data sets. The black line corresponds to collecting exactly the minimum data requirement. LOC almost always remains slightly above the black line, meaning we rarely fail to meet the target.
simulation uses a piecewise-linear approximation of a 'ground truth' learning curve that returns model performance as a function of data set size. In our problems, we initialize with q 0 = 10% of the full data set (we use 20% for VOC). Then in each round, we solve for the amount of data to collect and then call the piecewise-linear learning curve to obtain the current score.
We compare LOC against the conventional estimation approach of Mahmood et al. [2] who fit a regression model to the learning curve statistics, extrapolate the learning curve for larger data sets, and then solve for the minimum data requirement under this extrapolation. There are many different regression models that can be used to fit learning curves [15,17,5,8]. Since power laws are the most commonly studied approach in the neural scaling law literature, we focus on these. In Appendix F.4, we show that our optimization approach can be incorporated with other regression models.

Main Results
We consider T = 1, 3, 5 rounds and V * ∈ [V (D q0 ) + 1, V (D)] targets, where D is the entire data set. We evaluate all methods on (i) the failure rate, which is how often the method fails to achieve the given V * within T rounds, and (ii) the cost ratio, which is the suboptimality of an algorithm for solving problem (4), i.e., c T (q * Note that the suboptimality does not count the penalty for failure since this would distort the average metrics. For K = 1, we also measure the ratio of points collected q * T /D * . Although there is a natural trade-off between low cost ratio (under-collecting) and failure rate (over-collecting), we emphasize that our goal is to have low cost but with zero chance of failure.
The Value of Optimization over Estimation when K = 1. Figure 2 compares LOC versus the corresponding power law regression baseline when c = 1 and P = 10 7 (P = 10 6 for VOC and P = 10 8 for ImageNet). If a curve is below the black line, then it failed to collect enough data to meet the target. LOC consistently remains above this black line for most settings. In contrast, even with up to T = 5 rounds, collecting data based only on regression estimates leads to failure. Table 1 aggregates the failure rates and cost ratios for each setting. To summarize, LOC fails at less than 10% of instances for 12/18 settings, whereas regression fails over 30% for 15/18 settings. In particular, regression nearly always under-collects data when given a single T = 1 round. Here, LOC reduces the risk of under-collecting by 40% to 90% over the baseline. While this leads to a marginal increase in costs, our cost ratios are consistently less than 0.5 for 12/18 settings, meaning that we spend at most 50% more than the true minimum cost.
We remark that previously, Mahmood et al. [2] observed that incorrect regression estimates necessitated real machine learning workflows to collect data over multiple rounds. Instead, with LOC, we can make significantly improved data collection decisions even with a single round.
Robustness to Cost and Penalty Parameters (see Appendix F.2 for details). Figure 3 evaluates the ratio of points collected for T = 5 when the cost and the penalty of the optimization problem are  Table 1: Average cost ratio c T (q * T − q 0 )/c T (D * − q 0 ) − 1 and failure rate measured over a range of V * for each T and data set. We fix c = 1 and P = 10 7 (P = 10 6 for VOC and P = 10 8 for ImageNet). The best performing failure rate for each setting is bolded. The cost ratio is measured only for instances that achieve V * . LOC consistently reduces the average failure rate, often down to 0%, while keeping the average cost ratio almost always below 1 (i.e., spending at most 2× the optimal amount).    varied. Our algorithm is robust to variations in these parameters, as LOC retains the same shape and scale for almost every parameter setting and data set. Further, LOC consistently remains above the horizontal 1 line, showing that even after varying c and P , we do not fail as frequently as the baseline. Finally, validating Theorem 1, the penalty parameter P provides natural control over the amount of data collected. As we increase P , the ratio of data collected increases consistently. Figure 4 compares LOC versus regression at T = 5 with different costs, showing that we maintain a similar cost ratio to the regression alternative, but with lower failure rates. Table 2 aggregates failure rates and cost ratios for all settings, showing LOC consistently achieves lower failure rates for nearly all settings of T . When T = 5, LOC also achieves lower cost ratios versus regression on CIFAR-100, meaning that with multiple rounds of collection, we can ensure meeting performance requirements while paying nearly the optimal amount of data. However, solving the optimization problem is generally more difficult as K increases, and we sometimes over-collect data by large margins. In practice, these outliers can be identified from common sense (e.g., if a policy suggests collecting more data than we can reasonably afford, then we would not use the policy suggestion). Consequently, we report these results after removing the 99-th percentile outliers with respect to total cost for both methods. Nonetheless, this challenge remains when T = 1, particularly for CIFAR-100.

Discussion
We develop a rigorous framework for optimizing data collection workflows in machine learning applications, by introducing an optimal data collection problem that captures the uncertainty in estimating data requirements. We generalize this problem to more realistic settings where multiple data sources incur different collection costs. We validate our solution algorithm, LOC, on six data sets covering classification, segmentation, and detection tasks to show that we consistently meet pre-determined performance metrics regardless of costs and time horizons.
Our approach relies on estimating the CDF and PDF of the minimum data requirement, which is a challenging problem, especially with multiple data sources. Nonetheless, LOC can be deployed on top of future advances in estimating neural scaling laws. Further, we allow practitioners to input problem-specific costs and penalties, but these quantities may not always be readily available. We provide some theoretical insight into parameter selection and show that LOC is robust to these parameters. Finally, our empirical analysis focuses on computer vision, but we expect our approach to be viable in other domains governed by scaling laws.  Table 2: Average cost ratio c T (q * T −q 0 )/c T (D * −q 0 )−1 and failure rate over different V * for each T and c, after removing 99-th percentile outliers. We fix P = 10 13 for CIFAR-100 and P = 10 8 for BDD100K. The best performing failure rate for each setting is bolded. The cost ratio is measured over instances that achieve V * . LOC consistently reduces the average failure rate, and for T > 1, preserves the cost ratio. Further, LOC is more robust to uneven costs than regression.
Improving data collection practices yields potentially positive and negative societal impacts. LOC reduces the collection of extraneous data, which can, in turn, reduce the environmental costs of training models. On the other hand, equitable data collection should also be considered in real-world data collection practices that involve humans. We envision a potential future work to incorporate privacy and fairness constraints to prevent over-or under-sampling of protected groups. Finally, our method is guided by a score function on a held-out validation set. Biases in this set may be exacerbated when optimizing data collection to meet target performance.
There is a folklore observation that over 80% of industry machine learning projects fail to reach production, often due to insufficient, noisy, or inappropriate data [46,47]. Our experiments verify this by showing that naïvely estimating data requirements will often yield failures to meet target performances. We believe that robust data collection policies obtained via LOC can reduce failures while further guiding practitioners on how to manage both costs and time.
[6] Jonathan S Rosenfeld, Amir Rosenfeld, Yonatan Belinkov, and Nir Shavit. A constructive prediction of the generalization error across scales. In International Conference on Learning Representations, 2020.
[ [27] Kirstine Smith. On the standard deviations of adjusted and interpolated values of an observed polynomial function and its constants and the guidance they give towards a proper choice of the distribution of observations. Biometrika, 12(1/2):1-85, 1918.
[28] David Cohn. Neural network exploration using optimal experiment design. Advances in neural information processing systems, 6, 1993.  4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...   V q := V (D q ) Short-hand notation for model valuation.
The minimum data requirement.
The CDF of the minimum data requirement.
The PDF of the minimum data requirement.
Amount of data to collect in round t.
The regression set representing the learning curve of a given model and data set.
K ∈ N Number of data sources in multi-source setting.
q t ∈ N K Vector containing number of data points per-source in round t.
c ∈ N K Vector of per-source costs.

B Learn-Optimize-Collect
Algorithm 1 summarizes the complete workflow of LOC within the data collection problem. Given a target score V * , we collect data until we have met the target or until T rounds have passed. In this section, we first expand our complete LOC algorithm. We then provide further details on the regression procedure used to estimate the data requirement distributions. Finally, we introduce a more practical reformulation of our optimization problem (4), which is what we later use in our numerical experiments.

B.1 Details on the Learning and Optimizing Approach
Our approach for determining how much data to collect consists of three steps. The first step is to collect performance statistics by measuring the training dynamics of the current data set D qt . Here, we sample subsets of the current data set, train our model on the subset, and evaluate the score. We repeat this process for up to R subsets, where R denotes the size of our performance statistics regression data set R.
The second step is to model the data requirement distribution D * . We perform this by creating bootstrap samples from R, and then fitting a regression modelv(q; θ) that can estimate the model score as a function of data set size. We then invert this regression function by solving for the minimum q for which the model will predict that we have exceeded the target performance. We repeat this process to obtain B bootstrap estimates of D * . We can then fit any density estimation model to approximate a probability density and a cumulative density function. In this paper, we focus on Kernel Density Estimation (KDE) and Gaussian Mixture models since such models can be easily fit and provide functional forms of the PDF.
Finally in the third step, we solve our optimization problem (4) via gradient descent. This problem yields the optimal data set sizes q * 1 , . . . , q * T that we should have at the end of each round. Furthermore, if we are in the t-th round for t > 1, we freeze the values for q 1 , . . . , q t−1 to the data set sizes that we have observed in the previous rounds. Upon solving this problem, we then collect data until we have q t samples, and then re-train our model to evaluate our current state. COLLECT PERFORMANCE STATISTICS 5: Initialize R = ∅, D0 = ∅ 6: for r ∈ {1, . . . , R} do 7: Sub-sample D q t r/R ⊂ Dq t by augmenting to D q t (r−1)/R 8: Evaluate V (D q t r/R ) and update R ← R ∪ {(qtr/R, V (D q t r/R )} 9: end for 10: end 11: ESTIMATE DATA REQUIREMENT DISTRIBUTION 12: Initialize Q = ∅ 13: for b ∈ {1, . . . , B} do 14: Create bootstrap R b by sub-sampling with replacement from R 15: Fit regression model θ * = arg min θ (q,v)∈R b (v −v(q; θ)) 2 16: Estimate data requirementq b = arg min q {q |v(q; θ * ) ≥ V * } 17: Update Q ← Q ∪ {q b } 18: end for 19: Fit Density Estimation model f (q) using the empirical distribution Q and let F (q) = q 0 f (q)dq 20: end 21: COLLECT DATA 22: Solve problem (4) using Density Estimation models f (q) and F (q) to obtain q * 1 , . . . , q * T . 23: SampleD ∼ p(z) until |D| = qt − qt−1 24: Update loss L ← L + c(qt − qt−1) 25: Update Dq t = Dq t−1 ∪D 26: end 27: Evaluate V (Dq t ) and update t ← t + 1 Update loss L ← L + P 31: end if 32: Output: Final collected data set Dq t , loss L

B.2 Regression Model for D *
To estimate the data requirement, we build a regression model of the learning curve and then invert this curve. The classical learning curve literature proposes using structured functions to regress on the learning curve. For example with neural scaling laws, the most common function is a power law modelv(q; θ) := θ 0 q θ1 + θ 2 where θ := {θ 0 , θ 1 , θ 2 } [5, 18, 16, 6, 9, 10, 19, 8, 2]. As a result, the main experiments of our paper use this model.
We fit each regression function by minimizing a least squares problem using the Levenberg-Marquardt algorithm as implemented by Scipy [48, 49]. The parameters for each function are initialized to either 1 or 0 depending on if they are product or bias terms. To further help fit the data, we use weighted least squares where each subsequent point is weighted twice as much as the previous point. This ensures that our regression model is tuned to better fit the curve for larger q.

B.3 Alternate Re-formulation of Problem (4)
Although problem (4) has a differentiable objective function, it includes a set of lower bound constraints, meaning that a vanilla gradient descent algorithm may not immediately apply. A naive solution algorithm may be to use projected gradient descent. Instead, we show that the problem can be reformulated to remove these constraints.
For each t, let d t = q t − q t−1 denote the additional amount of data collected in each round. Note that we can recursively re-define q t = q 0 + new variables: The objective in the above formulation remains differentiable. Moreover, the non-negativity constraints can be removed by re-writing d t ← softplus(d t ) for all t. As a result, we can solve this problem by using an off-the-shelf gradient descent algorithm. Finally we note that in our experiments, we implemented a projected gradient descent based on (4) and the above gradient descent algorithm. We found that the above streamlined approach to generate slightly better final solutions.

C Details on the Main Theory
In this section, we explore mathematical properties and challenges of the optimal data collection problem. In Section C.1, we discuss the drawbacks of alternative approaches to our modeling framework. Then in Section C.2, we prove our main theorem demonstrating an analytic solution in the single-round problem.

C.1 Markov Decision Process Alternatives
The data collection problem requires sequential decision-making in terms of collecting additional data in each round. A natural modeling approach for such problems is via Markov Decision Processes (MDPs). However, MDP techniques are challenging for this problem due to (i) the unobservability of the state, and (ii) an infinite state space. That is, until we have collected enough data to meet the target, we do not know how much data is the minimum, which can furthermore be arbitrarily large.
Here, we sketch a potential alternative MDP framework and highlight the core challenge.
Our sequential decision-making problem can be written as a Because the state variable is unobserved, POMDPs are typically solved by using a belief distribution of the state variable to average the reward in the value function. When both the state and the action space of a POMDP are finite, Smallwood and Sondik [53] show that this value function is piecewiselinear and can be solved by exact methods, albeit under a curse of dimensionality with respect to these spaces. Unfortunately, for a general POMDP with an infinite state and action space, these methods do not apply and we most often resort to approximation techniques [54]. Moreover in our case, approximations based on discretizing the state and action space fall prey to the curse of dimensionality.
Alternatively, we may naively consider applying reinforcement learning. However, note that realworld data collection tasks do not contain the requisite sizes of learning data or generalizable simulation mechanisms that are staples in reinforcement learning techniques. These challenges, coupled with the goal of delivering practical managerial guidelines for data collection operations, motivate us to explore easy-to-implement techniques for optimizing data collection.

C.2 Proof of Theorem 1
Our main theorem states that the one-round problem has an analytic solution. However, the proof requires several auxiliary results. For clarity, we first reproduce the theorem.

Theorem 1 (Repeated). Consider the one-round problem
Assume F (q) is strictly increasing and continuous. For any such that F (q 0 ) < 1 − , let P := c/f (F −1 (1 − )). The optimal solution to the corresponding problem (5) is q * 1 = F −1 (1 − ). Furthermore, the optimal solution satisfies F (q * 1 ) = 1 − . The assumption of a strictly increasing and continuous cumulative density function is needed to ensure that the data requirement distribution has a well-defined quantile function F −1 (p) := inf q {q | F (q) ≥ p}, where the optimal solution for any p ∈ (0, 1) is unique.
The proof for Theorem 1 relies on equating the one-round optimization problem to the following constrained optimization problem: where > 0 is a pre-determined parameter. This above problem (8) is solving for the least amount of additional data to collect such that with probability at least 1 − , we collect above the minimum data requirement. We first characterize the properties of problem (8). Lemma 1. Problem (8) is a convex optimization problem.
Proof. We only need to prove that the set {q 1 | F (q 1 ) ≥ 1 − } is a convex set, since the objective and remaining constraint are convex. Since F (q) is a monotonically non-decreasing function in q, for any θ ∈ [0, 1] and q <q that satisfy the CDF constraint, we have Because the convex combination of any two points is in the set, the set must be convex.

Lemma 2.
The optimal solution to problem (8) is Proof. First consider the case where F (q 0 ) ≥ 1 − . Then, q 0 is a feasible solution to problem (8). Furthermore due to the second constraint, any q < q 0 is infeasible. Since q 0 minimizes the objective, it is optimal.
Next consider the case where F (q 0 ) < 1 − . Then, let q 1 = F −1 (1 − ) = inf{q | F (q) ≥ 1 − } be the smallest solution that satisfies the CDF constraint. By the monotonicity of F (q), it follows that q 1 > q 0 . Therefore, this solution minimizes the objective.
We are now ready to prove Theorem 1.
Proof of Theorem 1. We prove this result by first developing two different characterizations of the optimal solution set of problem (5) and then applying their equivalence.
First note that problem (5) is an optimization problem with one variable q 1 over a constrained domain [q 0 , ∞). Furthermore, the objective function is continuous everywhere, meaning that there are two possible scenarios: • q * 1 satisfies f (q 1 ) = c/P . • q * 1 := q 0 and the optimal value is P (1 − F (q 0 )).
The first scenario is obtained by taking the derivative of the objective function and setting it to 0. The second scenario comes from the boundary condition. Moreover, note that the objective is unbounded as q 1 → +∞ meaning the above scenario is the only boundary condition that we need to consider.
Next, note that problem (5) is equivalent to the following optimization problem min q1, For any fixed , problem (9) is equivalent to problem (8), and therefore by Lemma 1, the problem is convex optimization problem.
We can optimize problem (9) by breaking into two cases. First, for any fixed ≥ 1 − F (q 0 ), setting q * 1 ( ) = 0 attains a feasible solution and mnimizes the objective to P . Second, for any fixed ≤ 1 − F (q 0 ), Lemma 2 states that q * 1 ( ) = F −1 (1 − ) is a corresponding optimal solution and the objective function reduces to Moreover, from the original formulation (5), we can substitute q * 1 ( ) and obtain f (F −1 (1 − ) = c/P . Finally, problem (9) is optimized via the second case if and only if there exists a feasible ≤ 1−F (q 0 ) that satisfies We can rewrite this condition as follows. Let q 1 > q 0 and assume that (6) holds. Then, , meaning that there is a feasible q 1 > q 0 to problem (9) with lower objective function value than q 0 . Thus, assumption (6) guarantees that problem (9) has an optimal solution q * (6) is not satisfiable for any q 1 > q 0 , then we can use the same steps to show that q * 1 = q 0 is an optimal solution to the problem.

D Optimal Data Collection with Multiple Sources
The multi-variate data collection problem considers multiple sources delivering different types of data required to train a model. Consider K data sets with q 1 , . . . , q K points in each, respectively. Rather than collecting up to q t data points in each round, we optimize a vector q t ∈ R K + where each element q k t refers to how much data we need from the k-th source. Furthermore, the minimum data requirement is now a vector D * . This problem can be solved using the same general approach outlined in Algorithm 1, but with two changes. First, we require a multi-variate version of the PDF and CDF of D * . This necessitates new neural scaling law regression models for dealing with multiple data sources. Second, we modify the optimization problem from Appendix B to accommodate decision vectors. We highlight the above two steps in this section.

D.1 A General Multi-variate Neural Scaling Law
In order to construct a PDF and CDF in the multi-variate setting, we follow the same general steps as in Algorithm 1. We first collect a data set of performance statistics R := {(q r , V (D 1 as before. We then use bootstrap resamples of this data set to fit parameters θ * to a regression modelv(q 1 , . . . , q K ; θ) and then solve for q := arg min q {c T q |v(q 1 , . . . , q K ; θ * ) ≥ V * }.
Finally, we fit a density estimation model over our data set ofq.
The key challenge to this approach however is in designing a multi-variate regression function. To the best of our knowledge, the neural scaling law literature has not explored general power law models that can accommodate K different types of data for arbitrary tasks.
We may also incorporate other base models in the same way, such as the logarithmic or arctan functions introduced in Mahmood et al. [2].
The benefit of this additive regression model is that we can easily fit it via least squares minimization using a regression data set R : . Furthermore, additive models are simple and offer interpretable explanations on the contributions of each data type to performance by assuming that each data set has an independent effect. Finally, additive models are common in many other tasks, such as when estimating the valuation of specific data points [55].
We remark that some recent research has explored neural scaling laws for specific tasks with multiple data types. For instance, Mikami et al.
[11] explore a K = 2 power law for transfer learning from synthetic to real domains, where they use a multiplicative component that captures an interaction between real and synthetic data sets. Because scaling laws in multi-variate settings remain an open area of study, if there exist specific structural regression functions for a given application with different types of data, then such functions should be used in place of the additive model. Moreover, our downstream optimization model operates independently of the regression model, as long as the regression model can be re-trained with bootstrap samples in order to facilitate density estimation.

D.2 The Optimization Problem with Multiple Decisions
Just as in the single-variate case, problem (7) has a differential objective function but a series of lower bound constraints. We can use the same approach highlighted in Appendix B to reformulate this problem and remove the constraints. We summarize this reformulation below.
For each t, let d t = q t − q t−1 be the additional data collected in each round. Then, we recursively re-define q t = q 0 + t r=1 d r and re-write the problem to The above problem can now be solved using off-the-shelf gradient descent.

E Simulation Experiment Setup
The most intuitive approach of validating our data collection problem is by repeatedly sampling from a data set, training a model, and solving the optimization problem. However, performing a large set of such experiments over many data sets becomes computationally intractable. Instead, we follow the approach introduced in Mahmood et al. [2], which proposes a simulation model of the data collection problem. This section summarizes the simulation setup.
The simulation replicates the steps in Algorithm 1 except with one key difference. In the simulation, we replace the score function V (D) with a ground truth function v gt (q) that serves as an oracle which reports the expected score of the model trained with q data points. Thus, rather than having to collect data and train a model in each round, we evaluate v gt (q t ) and treat this as the current model score.
The optimization and regression models do not have access to v gt (q).

E.1 A Piecewise-Linear Ground Truth Approximation
In order to build a ground truth function, we first use the sub-sampling procedure in Algorithm 1 to collect performance statistics over subsets of the entire training data set. Using these observed statistics, we then build a piecewise-linear model of the ground truth. Below, we first highlight how to construct a piecewise-linear model when given a set of data set sizes and their corresponding scores.
In the next subsection, we will detail the exact data collection process.
The Single-variate (K = 1) Case. Mahmood et al. [2] develop a ground truth function as follows. Let q 0 ≤ q 1 ≤ q 2 ≤ · · · be a series of data set sizes and let D q0 ⊂ D q1 ⊂ D q2 ⊂ · · · be their corresponding sets. Then, consider the following piecewise-linear function: v gt (q) := This function is concave and monotonically increasing, which follows the general trend of real learning curves [5]. Furthermore Mahmood et al. [2] show that given sufficient resolution, i.e., enough data subsets, this piecewise linear function is an accurate approximation of the true learning curve V (D).
The Multi-variate (K = 2) Case. In the previous K = 1 case, the ground truth was formed by taking linear approximations between different subset sizes. When K > 1, we have multiple subsets that are used to evaluate the score V (D 1 , . . . , D K ).
For each tuple (q 1 s , q 2 t ) in the above grid, let V (D 1 ) be the score of a model trained on two data sets of the corresponding respective sizes.
For each index (s, t) we fit linear models on the corresponding lower right and upper left triangles. First, let (α(s, t), β(s, t), γ(s, t)) be the parameters of the plane defined by the lower triangle {(q 1 s−1 , q 2 t ), (q 1 s , q 2 t−1 ), (q 1 s , q 2 t )}, i.e., the unique solution to the following linear system: Thus, for any data set sizes (q 1 , q 2 ) in this triangle, we evaluate the ground truth by the linear model α(s, t)q 1 + β(s, t)q 2 + γ(s, t). Similarly, let (α(s, t), β(s, t), γ(s, t)) be the parameters of the plane defined by the upper triangle {(q 1 s , q 2 t ), (q 1 s+1 , q 2 t ), (q 1 s , q 2 t+1 )}, i.e., the unique solution to the following linear system: Similarly for any (q 1 , q 2 ) in this triangle, the ground truth is obtained by the linear model α(s, t)q 1 + β(s, t)q 2 + γ(s, t).
Finally, we define our ground truth function v gt (q 1 , q 2 ). For any q 1 ≥ q 1 0 , q 2 ≥ q 2 0 , this function first identifies the interval [q 1 s , q 1 s+1 ] × [q 2 t , q 2 t+1 ] in which the point lies. Then, the function assigns a For K > 2. The piecewise linear approximations grow increasingly complex as the dimension K increases. Furthermore, the number of subsets of data set sizes required to create a piecewise linear approximation increases exponentially with K. Specifically for k ∈ {1, . . . , K}, let M k denote the number of subsets (i.e., |{q k 0 , q k 1 , . . . , q k M k }|) of a data set that we consider when creating subsets. For each combination of K subsets, we must then train a model and evaluate it's performance to record V (D 1 , . . . , D K ). Thus, we must subsample and train our model for O( k M k ) combinations. This can quickly become computationally prohibitive.

E.2 Data Collection
We now summarize the data collection and training process used to create the above piecewise-linear functions for each data set and task. All models were implemented using PyTorch and trained on machines with up to eight NVIDIA V100 GPU cards. For all experiments, we set the initial data set at q 0 = 10% of the data. In data collection, we create five subsets containing 2%, 4%, · · · , 10% of the training data, five subsets containing 12%, 14%, · · · , 20% of the training data, and eight subsets containing 30%, 40%, · · · , 100% of the data. Note that we use higher granularity in the early stage as this is where the dynamics of the learning curve vary the most. With more data, the learning curve eventually has a nearly zero slope. For each subset, we train our respective model and evaluate performance.
VOC. We use the Single-Shot Detector 300 (SSD300) [45] based on a VGG16 backbone [57], following the same procedure as in Elezi et al. [58]. All models are trained using SGD with momentum. We evaluate all models on mean AP.
BDD100K. We use Deeplabv3 [39] with ResNet50 backbone. We use random initialization for the backbone. We use the original data set split from Yu et al. [40] with 7, 000 and 1, 000 data points in the train and validation sets respectively. The evaluation metrics is mean Intersection over Union (IoU). We follow the same protocol used in the Image classification tasks to create our subsets of data.
nuScenes. We use the "Lift Splat" architecture [42], which is used for BEV segmentation from driving scenes, following the steps from the original paper to train this model. We evaluate on mean IoU. Our data collection procedure follows the same steps and percentages of the data set as used for BDD100K and the Image classification tasks.
CIFAR-100 (2 Types). We partition this data set into two subsets D 1 and D 2 of 25, 000 images each containing the first 50 and last 50 classes, respectively. We then train a ResNet18 [38] using different fractions of the two subsets. We follow the same training procedure as in the single-variate case except with one difference. Since some of the data sets will naturally be imbalanced (e.g., if we train with half of the first subset and all of the second subset), we employ a class-balanced cross entropy loss using the inverse frequency of samples per class.
For each D k subsets, respectively, we follow the same subsampling procedure used in the singlevariate case. That is, we let q 1 0 = 10% of the first data subset and q 2 0 = 10% of the second data subset. For each subset, we create 10 subsampled sets at intervals of 2%, 4%, 6%, · · · , 20% of the respective data subset. We then create eight further subsampled sets at 30%, 40%, · · · , 100% of the respective data subset. Finally, we train our model and evaluate the score on every combination of the subsampled subsets of D 1 × D 2 .
BDD100K (Semi-supervised). For this task, we consider semi-supervised segmentation via pseudolabeling the unlabeled data set in BDD100K. The data is partitioned into two subsets D 1 and D 2 containing 7, 000 labeled and 70, 000 unlabeled scenes. As before, we use the Deeplabv3 [39] architecture with a ResNet50 backbone. Here however, we: 1. First train with a labeled subset of D 1 via supervised learning.
2. Pseudo-label an unlabeled subset of D 2 using the trained model.
3. Re-train the model with the labeled subset and the pseudo-labeled subset.
We follow the same procedure as in the single-variate case for both training steps, except we weigh the unlabeled data by 0.2 to reduce its contribution to the loss.
Training via semi-supervised learning on BDD100K requires long compute times, so we reduce the number of subsets used in this experiment. For the labeled set D 1 , we create subsets with 5%, 10%, 15%, 20%, 40%, 60%, 80%, 100% of the data. For the unlabeled set D 2 , we create subsets with 0%, 10%, 25%, 50%, 100% of the data. Note that we have five settings of unlabeled data since we include the case of training with no unlabeled data as well.

E.3 LOC Implementation
For all experiments, we initialize with 10% of the training data set. We consider T = 1, 3, 5 rounds and sweep a range of V * . We provide a summary of parameters in Table 5.
For the experiments with K = 1, we model the data requirement PDF f (q) in each round of the problem as follows. We first draw B = 500 bootstrap resamples of the current training statistics R, where R = {(rq 0 /R, V (D rq0/R ))} R r=1 ∪ {(q s , V (D qs ))} t s=1 contains all of the measured statistics up to the initial data set (e.g., for CIFAR-10, this includes performance with 2%, 4%, · · · , 10% of the data), and the previous collected data. The latter is obtained by calling our piecewiselinear ground truth approximation. For each bootstrap resample, we fit a power regression model v(q; θ) = θ 0 q θ1 + θ 2 and solve for the estimated minimum data requirement. We then use our set of The mean is consistently higher than the unknown ground truth, whereas the shaded region can at times cover it.
estimates to fit a Kernel Density Estimation (KDE) model after gridsearching for the best bandwidth parameter.
For the experiments with K = 2, we use the same above procedure but fit Gaussian Mixture Models (GMM) due to their having an easily computable CDF via the Gaussian erf(·), rather than numerically integrating the PDF. We grid-search over the number of mixture components for the GMM model.
We optimize over problems (4) and (7) using gradient descent techniques. Depending on the current state and data set, different hyperparameters perform better. As a result, we perform extensive hyperparameter tuning every time we need to solve the optimization problem. Here, we sweep over gradient descent with momentum and Adam with learning rates between 0.005 to 500.
We initialize each problem with q t equal to the baseline regression solution and q t+s = q t /(s + 1) for all 1 ≤ s ≤ T − t. That is, we set the initial value for future collection amounts to be fractions of the initial value of the immediate amount of data to collect. We identified this initialization by manually inspecting the solutions found by LOC, consequently it improves the conditioning of the loss landscape relative to other random initialization schemes.

F Additional Numerical Results
This section contains expanded results of our numerical experiments and further ablations. Our key results include: • In Appendix F.1, we evaluate the effectiveness of estimating F (q) by plotting the estimated learning curves as well as the empirical histograms used to model the data requirement distribution.
• In Appendix F.2, we explore the sensitivity of our optimization algorithm to variations in the cost and penalty parameters. In all except one instance, LOC consistently maintains a low total cost and failure rate.
• In Appendix F.3, we explore the multi-variate LOC (i.e., K = 2) for problems where we have a small number of T = 1, 3 rounds. The baseline fails for almost all instances of T = 1, whereas LOC maintains a low failure rate.
• In Appendix F.4, we consider variants of LOC where we use different regression functions to estimate the data requirement distribution. Our optimization framework can be deployed on top of any regression function to reduce the failure rate.

F.1 Estimating the Data Requirement Distribution F (q)
To estimate F (q), we first create an ensemble of estimated learning curves, which we then invert to obtain an empirical distribution of estimated values for D * . Figure 5 plots our bootstrap resampled estimated learning curves versus the ground truth performance for the first round of data collection when we have access to an initial D q0 containing 10% of the full data set. As noted in Mahmood et al. [2], the mean estimated learning curve diverges from the ground truth. However, by bootstrap resampling an ensemble of learning curves, we can cover the ground truth with some probability. Figure 6 plots the empirical histograms of estimated D * as well as the estimated F (q) obtained via KDE on CIFAR-10 with three different values for V * . Although the mode of the estimated distribution is far from the ground truth D * , the estimated distribution assigns some probability to the ground truth region. LOC optimizes over this estimated F (q), which allows us to conservatively collect data and reduce the chances of failure. Relative frequency CIFAR-100 (V * = 70) Figure 6: For a fixed seed, the histogram of estimates of D * from different bootstrapped models (blue bars), the estimated F (q) (orange curve), and the ground truth D * (black dashed line). Each plot corresponds to a different V * for CIFAR-100 (see Figure 5 for the learning curve). With higher targets, regression (i.e., collecting the mean of the distribution) will lead to larger under-estimations. Power Law c=1e-03 c=1e-02 c=1e-01 c=1e+00 Figure 7: Mean ± standard deviation of the ratio of data collected q * T /D * for different V * when we sweep the cost parameter from 0.001 to 1 and fix P = 10 7 . We show T = 1, 3 and refer to the main paper for T = 5. The dashed black line corresponds to collecting exactly the minimum data requirement. For nearly all settings, LOC remains stable to variations in the cost parameter. Nonetheless, careful parameter selection becomes important as T decreases. This is due to the fact that for low costs, the  Figure 8: Mean ± std of the ratio of data collected q * T /D * for different V * when we sweep the penalty parameter from 10 6 to 10 9 and fix c = 1. We show T = 1, 3 and refer to the main paper for T = 5. The dashed black line corresponds to collecting exactly the minimum data requirement. total amount of data collected increases as T decreases (e.g., c = 0.001 for BDD100K). Furthermore, Figure 8 expands the penalty parameter sweep from Figure 3 (Bottom row). Here, we observe similar properties to the cost parameter sweep.

F.2 Robustness to the Cost and Penalty Parameters
Although LOC is relatively stable on all other data sets, our results demonstrate some extreme results for VOC, potentially due to noise in the simulation. For example in Figure 8, setting P = 10 9 , V * = 71, and T = 3 led to collecting 10, 000 times the minimum data requirement. Such a situation is unrealistic in a production-level implementation, since in a real implementation, we could impose further constraints onto problem (4), such as upper bounds on the total amount of data permissible.  Table 2 in that the baseline has considerably higher failure rates versus LOC. In particular for BDD100K at T = 1, the baseline fails consistently for four out of five random seeds. On the other hand, recall that LOC admits a higher cost ratio compared to the baseline when T = 1. We can observe now that this high cost ratio is due to the method incurring high cost for a few target V * values. This behavior is similar to the observation above on VOC with high penalties at T = 3. : For experiments on CIFAR-100 with two data types, mean ± standard deviation over 5 seeds of the cost ratio c T (q * T − q 0 )/c T (D * − q 0 ) − 1 and failure rate for different V after removing 99-th percentile outliers. We fix c 0 = 1 and P = 10 13 . The rows correspond to T = 1, 3 (see the main paper for T = 5) and the columns correspond to c 1 = c 0 /2, c 0 /5, c 0 /10, c 0 /20.  Figure 10: For experiments on BDD100K with two data types, mean ± standard deviation over 5 seeds of the cost ratio c T (q * T − q 0 )/c T (D * − q 0 ) − 1 and failure rate for different V after removing 99-th percentile outliers. We fix c 0 = 1 and P = 10 13 . The rows correspond to T = 1, 3 (see the main paper for T = 5) and the columns correspond to c 1 = c 0 /2, c 0 /5, c 0 /10, c 0 /20.

F.4 LOC with Alternative Regression Functions
Mahmood et al. [2] show that we can use other regression functions instead of the power law to estimate the data requirement. Moreover, some functions tend to consistently over-or under-estimate the requirement. LOC can be deployed on top of any such regression function, since the regression function is only used to generate bootstrap samples. Table 6 highlights experiments on CIFAR-100 with three alternative regression functions that were used by Mahmood et al. [2]. For both functions, we observe the same trends seen in Table 1. That is, LOC reduces the failure rate down to approximately zero, at a marginal relative increase in cost.
Noting that Power Law Regression often leads to failure, Mahmood et al. [2] also propose a correction factor heuristic wherein they learn a parameter τ such that if the data collection problem requires a  Table 6: For experiments on CIFAR-100, average cost ratio c T (q * T − q 0 )/c T (D * − q 0 ) − 1 and failure rate measured over a range of V * and T . We fix c = 1 and P = 10 7 . The best performing failure rate for each setting is bolded. The cost ratio is measured only for instances that achieve V * . LOC consistently reduces the average failure rate, almost consistently down to 0%.  Table 7: Comparison against the correction factorbased Power Law Regression of Mahmood et al. [2] using the same setup as in Table 1. The best performing cost ratio is underlined and the best performing failure rate for each setting is bolded. Although the baseline is designed specifically to achieve low failure rates, LOC often can achieve competitive failure rates while reducing the cost ratios by an order of magnitude.
target performance V * , we should instead aim to collect enough data to meet V * + τ . In order to learn this correction factor, we require a pre-existing data set upon which we can simulate a data collection policy. Mahmood et al. [2] suggest setting τ such that we can achieve the data requirement V * for any V * on the pre-existing data set, and then fixing this parameter for new data sets. Table 7 compares LOC (i.e., repeating Table 1) with the Correction factor-based Power Law regression baseline of Mahmood et al. [2]. Following the original paper, we tune τ using CIFAR-10 and apply it on all other data sets. The correction factor is designed to minimize the failure rate and thus, achieves nearly 0% failure rate for all settings, but often at high cost ratios. On the other hand, LOC achieves generally low failure rates and low cost ratios. Specifically, for T = 3, 5, we are competitive with the baseline on failure rates for most tasks while obtaining up to an order of magnitude decrease in costs. For T = 1, we typically admit higher failure rates; however for the segmentation and detection tasks, we obtain up multiple orders of magnitude lower costs. Finally, note that this baseline requires a similar prior task to be effective. For example, the baseline outperforms us on cost and failure rate both only on CIFAR-100, since it is tuned on CIFAR-10. On the other hand, LOC does not require this prior data set to be effective as evidence by its performance on non-classification tasks.