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.


extfieldsofstudy:
Computer Science
Engineering

text:
Simple and Efficient Architectures for Semantic Segmentation

Though the state-of-the architectures for semantic segmentation, such as HRNet, demonstrate impressive accuracy, the complexity arising from their salient design choices hinders a range of model acceleration tools, and further they make use of operations that are inefficient on current hardware. This paper demonstrates that a simple encoder-decoder architecture with a ResNet-like backbone and a small multi-scale head, performs on-par or better than complex semantic segmentation architectures such as HRNet, FANet and DDRNets. Naively applying deep backbones designed for Image Classification to the task of Semantic Segmentation leads to sub-par results, owing to a much smaller effective receptive field of these backbones. Implicit among the various design choices put forth in works like HRNet, DDRNet, and FANet are networks with a large effective receptive field. It is natural to ask if a simple encoder-decoder architecture would compare favorably if comprised of backbones that have a larger effective receptive field, though without the use of inefficient operations like dilated convolutions. We show that with minor and inexpensive modifications to ResNets, enlarging the receptive field, very simple and competitive baselines can be created for Semantic Segmentation. We present a family of such simple architectures for desktop as well as mobile targets, which match or exceed the performance of complex models on the Cityscapes dataset. We hope that our work provides simple yet effective baselines for practitioners to develop efficient semantic segmentation models.

Introduction
Convolutional Neural Network based approaches to Semantic Image Segmentation have seen a lot of progress in the past years in terms of architectures, training techniques, Figure 1. FFNet Architecture comprises of a backbone (encoder), in this case ResNet-like, feeding into a compact multi-branch Uphead (decoder), that subsequently feeds multi-scale features to the task specific head. 's' indicates the block or layer stride. The choices for the stem, widths & depths of the backbone blocks, widths of the convolutions in the Up-head, choice of upsampling operator (bilinear vs nearest), and the design of the task head depend on the target platform and the task. The backbone options considered in this paper are listed in Table 1, and the stem, Uphead and Segmentation-head options are depicted in Figure 2. datasets and loss functions. The extent of improvement arising from various aspects of the improved CNN architectures can often get muddled due to the specifics of training, datasets and training pipeline differences.
For semantic image segmentation of natural images, researchers and practitioners who are new to the field look to state-of-the-art tables [2] and available code bases [1] as a starting point, and build on top [27] of these. Unfortunately, these benchmarks happen to be dominated by increasingly complex and costly architectures [10,22,26].
We set out to examine the extent of efficacy of these complex designs over a conceptually simpler architecture. The baseline architecture we use is most closely related to FPN [15], originally proposed for object detection. Specifically, we investigate whether the accuracy gains of the more complex architectures hold up when their associated non-architectural improvements are applied to this simple baseline architecture. We see that when using ResNet-50/101 [9] backbones comprised of bottleneck-blocks in an FPN-like design the network is indeed markedly worse than the more complex designs. In this paper, we conjec- Figure 2. Various choices for the Stem, Up-head, and Segmentation-head that we consider in this paper. These are connected to backbone networks of varying widths and depths, listed in Table 1. For GPU models, bilinear upsampling is used. For mobile models, nearest neighbour upsampling is used. The choices depicted are not comprehensive, and only meant to represent a few distinct points in a potential NAS search space. In the text we will refer to the Stem, Up-head and Segmentation-head choice combinations as A-B-B, C-B-C etc.
ture that this drop in performance is mainly due to the decrease in receptive field due to using bottleneck-blocks [5]. We show that with similarly deep ResNet backbones comprised of basic-blocks, with a consequently much larger receptive field, the simple architecture does compare favorably to the more complex designs. Our simple architecture named FFNet not only reduces the inference time and compute costs, but is comprised entirely of operations well supported on a wide variety of hardware, further making on-device deployment easier.
We describe the FFNet meta-architecture in Section 2, and present results for a family of FFNet models in Section 3. Given the extent of the experiments and the compute requirements, we limit the experiments to the Cityscapes dataset.

FFNet: A Simple Architecture
In Figure 1, we depict a schema of our Fuss-Free Network (FFNet); a simple architecture inspired by the FPN architecture. It has an encoder-decoder structure. The encoder is comprised of a ResNet backbone without the classification head. Instead of just using features from the very last layer of the backbone, features at different spatial resolutions are extracted from all intermediate residual stages. These features are passed on to a light convolutional decoder head that upsamples and incorporates features from lower resolution branches to higher resolution branches. This decoder head, which we will refer to as 'Uphead', also outputs features at different spatial resolutions. These multi-scale features are subsequently used as input to a small task-specific head, such as for segmentation or classification.
A lot of flexibility exists within the general setup of FFNet. We can freely change the width, depth, and the type of backbone building blocks, number of feature scales, the head type and the head width. Figure 2 depicts the various stem, Up-head, and Segmentation-head choices we investigate in this paper, marked as A/B/C. These are combined with various backbone width and depth configurations depicted in Table 1, depending on the target platform. The first residual block in the backbone can have a stride of 1 or 2, which changes the spatial resolution of the output. We show results for both in Section 3. Specific instantiations of FFNets throughout the paper will refer to a backbone, such as ResNet-50, paired with a Stem-Up-Seg combination denoted as A-B-B.
We show models for desktop GPU and mobile targets. The desktop models use bilinear upsampling in the Uphead, while mobile models use nearest neighbour upsampling.
This is a simple design with no particular restrictions imposed on the number of stages in the backbone or the number of feature scales being output, the choice of striding in the stem and the backbone. The architecture can thus easily be adapted for other tasks.

Experimental Setup
Dataset. The Cityscapes [7] dataset is comprised of videos of urban street scenes recorded from a moving vehicle. 5k image frames have high quality pixel-level annotations of 19 semantic classes, and a further 20k frames that are weakly annotated.
Training Setup. Since the number of annotated frames in the Cityscapes dataset is limited, we utilize ImageNet pretraining of the models. The FFNet models are pretrained on the ILSVRC2012 [8] dataset in the FFNet form, using the classification head from HRNet [22] in place of the segmentation head. For ImageNet pretraining, we make use of Pytorch Image Models [23], and train for 150 epochs.
For Cityscapes training, the stem and the backbone are initialized from the ImageNet pretraining. The Up-head and the Segmentation-head are initialized from scratch. Since the fine grained annotations on the Cityscapes dataset are Table 1. Configurations of backbones examined in the paper. The naming convention follows that of ResNets [9], even though these are paired up with different stems and heads depicted in Figure 2, which changes the overall number of layers. limited to 5k images, learning meaningful and generalizable feature representations with deep CNNs can be challenging. We use pseudo labels from Tao et al. [21] on the images with coarse annotations. Additionally, we use the RMI [28] loss as an auxiliary loss while training. The models are trained for 175 epochs with a batch size of 8. We will make the ImageNet and Cityscapes training hyperparameters available with the models.

Experiments and Comparisons
We examine various configurations of FFNets. The backbones of different depths, widths, and block types that we tried are detailed in Table 1. These backbones are paired with various stem, Up-head, and Segmentation options from Figure 2, and the configurations referred to as A-B-B etc.
For desktop GPU FFNets, we use input images of size 1024 × 2048. We show FFNet models with a stride of 1 and 2 in the first residual stage of the ResNet backbone, with an output segmentation map resolution of 256 × 512 and 128 × 256 respectively. We'll refer to these models as FFNet-GPU-Large and FFNet-GPU-Small respectively.
For mobile FFNets, we use a stride of 2 in the first residual stage, with an input resolution of 1024 × 2048, and a stride of 1 when the input resolution is 512 × 1024, both resulting in a segmentation map resolution of 128 × 256.

Efficacy of Basic Blocks vs Bottleneck Blocks
FFNets with backbones comprised of basic-blocks far outperform backbones comprised of bottleneck blocks, for FFNet-GPU-Large and FFNet-GPU-Small models. See FFNet A-A-A in Figure 3 and Figure 5. Prior work has primarily used ResNet-101 and ResNet-50 as backbones in baselines for Segmentation, and seen poor results on account of an inadequately large receptive field, and needing to enlarge the receptive field through tricks like dilated convolution [5]. New backbones like ResNet-150, 134, 86, 56 described in Table 1, and known backbones like ResNet-34, which are all comprised of basic-blocks fare far better than ResNet-50 and ResNet-101, particularly in the case of FFNet-GPU-Large which operates on larger feature maps.

Exploring the Model Space
While the effects of varying the backbone depth are obvious and expected, we also experiment with varying the width of the backbone, and the width of the Up-head and the Segmentation-head. For FFNet-GPU-Large models, given the larger spatial resolution of the output feature maps, significant speed improvements arise from narrowing the Uphead and the Segmentation-head. FFNet A-B-B (cyan) in Figure 3, which uses narrower Up-head and Segmentationhead, provides a better speed-accuracy trade-off than FFNet A-A-A (blue) with its wider heads. For FFNet-GPU-Small  Table 2.

Models for Mobile
For FFNet models intended for mobile deployment, we utilize narrower ResNet backbones and heads. Instead of bilinear upsampling in the heads, FFNet-Mobile models use nearest neighbour upsampling. We show a family of models with their inference times on a Samsung S21 DSP, in Figure 6 and Table 4. Changing the input resolution, and the width of the head allows on-device models to be created with a better speed-accuracy tradeoff. See black, blue and cyan plots in Figure 6.

3-Stage Backbone
We experiment with the backbone structure, beyond the depth and width of the backbone, in order to create a more efficient FFNet. Typical ResNets are comprised of 4 residual stages. The first stage operates on the largest feature maps, and has a significant compute and memory cost. We create a 3-stage ResNet backbone, removing the first residual stage. For FFNets, the 3-stage backbone interfaces with the Up-head, using the output from the stem instead of the output from the first residual stage of a 4-stage backbone. See  NS C-C-C (light green) in Figure 6.
It is unclear if the 3 stage model would also be better at higher accuracies, but this experimentation reveals a new dimension of exploration to be covered in a potential NAS search space.

Comparisons to Prior Art
We use HRNet [22], DDRNet [10], and FANet [12] as our points of comparison to prior work. HRNets are commonplace in much of semantic segmentation work. DDR-Net demonstrates better performance than several classes of GPU efficient networks for Semantic Segmentation. FANets also claim GPU efficiency, and are the closest to our design, but make use of self-attention in the head. We compare the accuracy and GPU inference timings for the models, and refrain from making FLOP comparisons for a few reasons. Various libraries for FLOP computation are not able to correctly handle all kinds of operations, and may need operations implemented a certain way to correctly account for the FLOPs. Further, several operations such as tensor concatenation and channel shuffling do not have a compute cost associated, but incur a large memory access time cost. Hence, we restrict ourselves to inference time comparisons. We retrain all the models that we compare to, using the same training scheme, to make comparisons fair. Hence, the performance reported for these models is much higher than that in their respective papers. However, there may yet be better accuracy possible with model specific training-hyperparameter tuning. The validation accuracy is given for single scale inference, with no test-time augmentation used.
Comparison with HRNet: HRNet utilizes multi-scale feature representations throughout the network, with repeated information exchange across the feature scales, and a multi-scale feature output that is used by the task specific head. FFNet A-A-A (blue) models using backbones comprised of basic-blocks perform on par with HRNets (red), as shown in Figure 3, while FFNet A-A-A (violet) models using bottleneck-blocks are markedly worse. A key feature of HRNet that is not remarked upon, is that the network is 75+ layers deep, and comprised of basic-blocks. It consequently has a larger effective receptive field than bottleneck-block based networks like ResNet-50/101. We find that a multi-scale feature output constructed with the simple FFNet architectures achieves similar accuracy, when the backbones are made of basic-blocks. These results point to the fact that the large receptive field is a critical contributor to the overall accuracy, and comparable results are possible with simple designs like the FFNets, without requiring other components such as a repeated information exchange across scales. It would need to be determined when and if the repeated information exchange across feature scales is effective. Other families of FFNets with narrower heads and backbones can perform better than HRNets as seen in Table 2.
tectures such as DDRNet [10] and BiseNet [24,25] have followed HRNet, claiming that it is important to maintain higher resolution information throughout the network, as well inter-branch information exchange. They propose to make such a design faster through reducing the width of the backbone, and maintaining only one higher resolution feature scale instead of multiple. They too, however, use a backbone with a large receptive field. We show comparisons with DDRNet, which has a better reported performance than BiseNets.
FFNet A-A-A (blue) models using backbones comprised of basic-blocks also perform on par with DDRNets (red), as shown in Figure 5. As with the case of HRNets, this demonstrates that with a suitably large receptive field, simple encoder-decoder models can work as well as 2-stream models like DDRNets. By changing the backbone and head width of FFNets (blue, black), models that are better than DDRNets can be found for all speed-accuracy tradeoffs. See Table 3. The 3-stage FFNet-GPU-Large models (green) also outperform DDRNets.
Comparison with FANet: Approaches like FANet [12] and CCNet [13] that make use of attention, could be viewed as attempts to increase the effective receptive field of the network, when using backbones with small effective receptive fields. Indeed, FANets with bottleneck-blocks in the backbone are comparable to FANets with basic-blocks in the backbone. See Figure 5.
One of the questions that it naturally leads to is whether an equivalent compute cost increase through enlarging the receptive field of backbone delivers the same accuracy boost that incorporating these attention-based structures does. As shown in Figure 5 and Table 3, FFNet A-A-A (blue) models with a backbone with an adequately large receptive are on-par with FANet (orange, brown) models, and the selfattention head of FANet provides diminishing returns.

Related Work
For a comprehensive survey of the developments in Deep Learning based Semantic Segmentation, see Minaee Figure 6. Inference latency vs Cityscapes validation accuracy for FFNet-Mobile Models on Samsung S21: The models run in realtime on the mobile DSP. Regardless of input resolution, all models output segmentation maps at the same resolution. Using a smaller input resolution (blue, cyan) affords a better speed-accuracy tradeoff than a higher input resolution with additional downsampling in the backbone (black). Narrowing the head B-B-B (blue) → B-C-C (cyan) offers a better speed-accuracy tradeoff. As for desktop GPUs, 3-stage backbones (green, light green) are more efficient than 4-stage models for mobile too. See Table 4. et al. [17]. Here we only cover aspects directly relevant to our discussion. The go-to architectures for image segmentation roughly belong to two categories. Encoder-decoder designs like UNet [20], DeepLabv1/v2/v3 [5,6], SegNet [3], with a downsampling backbone (encoder) and an upsampling head (decoder), and HRNet-like [10,22,26], designs which maintain features at multiple resolutions throughout the network. HRNet-like multi resolution networks typically dominate the results tables, with claims of higher accuracy.
Encoder-decoder designs can have similar sized backbone and head, such as for UNet, or make use of bigger ResNet-like backbones, with various smaller head designs that enable context aggregation, such as for DeepLabv3. DeepLabv1/v2/v3 utilize dilated convolutions in the ResNet-like backbones to increase the receptive field size. Dilated convolutions are not efficient on existing hardware. Recent designs such as MobileNetv3 [11] reduce the use of dilated convolutions by restricting them only to the last block, but do not entirely eliminate them. Kirillov et al. [14] show that the FPN [15] design with an un-modified ResNet [9] backbone is competitive with DeepLab [5] like designs which remove striding and employ dilated convolutions in the ResNet backbone. Panoptic-FPN [14] however still employs the ResNet backbones using bottleneck-  [6], with the goal to capture features of different scales. ASPP achieves this through convolutions with different dilations. We use a very simple decoder head, and future investigations can determine if substituting it with other head designs is helpful. As discussed in Section 3.5, the simple FFNet architecture performs on par with HRNet-like architectures like HRNet [22], DDRNet [10], and GPU-efficient encoderdecoder architectures like FANet [12].

Discussion
We have only taken a limited look at the avenues of efficiency improvements that can be explored to make FFNets even faster. Various approaches to efficient and real-time image segmentation [10,16,[24][25][26] make use of FLOP ef-ficient operations and narrower layers, but still within the context of complex meta-architectures. See the related work sections of Hong et al. [10] and Yu et al. [26] for a detailed discussion of efficient segmentation architectures. These approaches could also be applied to FFNets.
Ideally, the space of efficient architectural configurations should be explored using an automated approach, such as DONNA [19] or LANA [18]. Here too, the simplicity of the design of the meta-architecture is a significant advantage, because the architecture can be trivially split into a small number of simple blocks that can be handled by NAS approaches that rely on blockwise knowledgedistillation [4,18,19]. HRNet, DDRNet etc. either split into a small number of complex blocks, or a very large number of simple blocks, and handling these with blockwise NAS approaches becomes untenable.
Although our study only looks at road-scene semantic segmentation, the simple FFNet architectures could very well be competitive baselines for other computer vision tasks, as well as other semantic segmentation datasets.

Conclusion
We show that simple FPN-inspired baselines for Semantic Image Segmentation are efficient and extremely competitive with SoTA architectures across a variety of devices, ranging from highly accurate desktop GPU models to highly efficient mobile models. We also show that specific architecture instances designed for ImageNet are not necessarily the best for other tasks, and there exist better task specific architectures within the same design space. It is helpful to think about the specific requirements of the task before deciding to port a network from another task. We hope that this manuscript convinces the reader about the unexplored potential of simpler CNN architectures for semantic segmentation, and beyond.