{'fraction_non_alphanumeric': 0.02583082974571809, 'fraction_numerical': 0.006101526930343482, 'mean_word_length': 5.123269486061066, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning to Limit Data Collection via Scaling Laws: Data Minimization Compliance in Practice

Data minimization is a legal obligation defined in the European Union’s General Data Protection Regulation (GDPR) as the responsibility to process an adequate, relevant, and limited amount of personal data in relation to a processing purpose. However, unlike fairness or transparency, the principle has not seen wide adoption for machine learning systems due to a lack of computational interpretation. In this paper, we build on literature in machine learning and law to propose the first learning framework for limiting data collection based on an interpretation that ties the data collection purpose to system performance. We formalize a data minimization criterion based on performance curve derivatives and provide an effective and interpretable piecewise power law technique that models distinct stages of an algorithm’s performance throughout data collection. Results from our empirical investigation offer deeper insights into the relevant considerations when designing a data minimization framework, including the choice of feature acquisition algorithm, initialization conditions, as well as impacts on individuals that hint at tensions between data minimization and fairness.


Introduction
Article 5(1)(c) of the European Union's Data Protection Regulation [1] as well as data protection laws in other jurisdictions mandate a principle of data minimization: "Personal data shall be: [...] adequate, relevant and limited to what is necessary in relation to the purposes for which they are processed (data minimisation)" reviving the discussion about the principle, a dearth of concrete mathematical definitions is one of the main factors inhibiting adoption [11]. Indeed, qualitative research has shown a lack of consistent data minimization standards and interpretations of the principle among software developers [12].
Addressing some of the above challenges, a recent interpretation proposes to tie the processing purpose in data-driven systems to performance metrics, an interpretation termed performance-based data minimization [2]. Our work follows this interpretation. We address the question of how to proactively satisfy the performance-based data minimization principle in machine learning with personal data.
Contributions. To the best of our knowledge, this is the first paper to propose a learning framework for ongoing personal data collection in compliance with the GDPR's data minimization principle. The key challenge lies in adaptively learning an algorithm's performance curve so that a compliant data collection stopping point can be determined accurately. Our approach builds on an insight from the machine learning literature that identifies three distinct phases in the performance curves of learning algorithms: the small data phase, the power law phase, and the diminishing returns phase [6]. We conceptually align these phases with legal requirements and propose a parametrized data collection stopping criterion based on empirical performance curve derivatives.
We demonstrate that the performance phases can be observed in the context of user data collection and that their presence makes standard power law curve fitting approaches not accurate enough to base compliant minimization on. Instead of fitting a single power law curve, we propose to model data collection stages separately by adaptively learning a piecewise power law curve. This approach allows us to not only learn the performance curve more accurately as data is acquired but also satisfy practical constraints of data minimization. Explicitly modeling performance curves maintains compliance with data protection principles that require interpretability (transparency, auditability), while remaining flexible to different underlying feature acquisition algorithms used in practice. Finally, beyond model-level data minimization, we examine issues related to user-level data minimization. We demonstrate the impacts that algorithmic components such as active feature acquisition (AFA) might have on minimization outcomes. We find that AFA can lead to unequal, concentrated data collection from a small set of users, in addition to decreased minimization performance for evolving user communities or when sensitive features are excluded from initial data collection.

Related Work
Ideas related to the legal concept of data minimization exist across fields in ML; those include performance curve estimation, sample complexity, sufficient sample sizes, and active feature acquisition.
Performance Curves. Our technical approach is closely related to empirical research on performance curve estimation, which examines the relationship between dataset size and model performance. The literature considers a large spread of metrics for model performance, including sensitivity [13], error rates [14], accuracy [15,16], and confidence [17,18]. While these works typically assume a power law relationship, alternatives have been considered and shown to be comparable in accuracy [19,16].
Tae and Whang [8] propose a data collection framework which is most closely related to ours. They use performance curves to identify classes which require more data to achieve equitable error rates. Tae and Whang [8] assume a power law relationship throughout the data collection process. In contrast, we model regions of the performance curve separately, and most importantly, use the performance curve to identify a data collection stopping point.
Sample Complexity. Sample complexity corresponds to the number of samples required for a learning algorithm to achieve an error rate of with a probability of (1 − δ). Literature on sample complexity takes a theoretical approach to the central task of our work: tying data collection to model performance. Earlier work quantifies sample complexity assuming random sample acquisition [20], while more recent work studies sample complexity for active learning methods [21,22] and recommendation systems [23]. Hestness et al. [6] note the gap between theoretical guarantees and empirical trends for performance curves and highlight this as an area for future work.
Active Feature Acquisition. AFA concerns the intelligent collection of feature-values given a fixed budget. There are several well-known AFA techniques, namely (i) using matrix completion with the assumption of being low rank [24][25][26] (ii) estimating the expected model improvement of accuracy  [6] plots the stages of data collection. On the right, we plot model performance over data collection from GoogleLocal and MovieLens. Preprocessing details can be found in the supplement.
for tasks such as clustering or classification [27,28] (iii) applying techniques to address ice-start [29] and cold-start problems [30] and (iv) using variational techniques to approximate the posterior distribution [31]. Although the performance of many AFA approaches is based on a given query budget, it remains unclear how budget sizes relate to performance. Our work lies adjacent to this research in that we aim to learn a performance-based budget given a feature acquisition algorithm. While the proposed method significantly outperforms existing work under different feature acquisition regimes, we show that AFA algorithms might have undesirable properties in the context of data minimization.

Interpreting Limitation
The GDPR requires that no more data than is necessary to achieve a declared processing purpose (in line with the purpose limitation principle) be processed. Data minimization is both a key principle under Article 5(1)(c) GDPR as well as a component of data protection by design and by default.
While it has been shown empirically that data can be minimized through various domain-and algorithm-specific heuristics [2], a question remains of how to automatically learn when to stop data collection for various personalization systems and feature acquisition strategies; the remainder of this paper focuses on this problem. For a thorough treatment of the harms data minimization protects against, we refer the interested reader to Finck and Biega [11].

Computational and Legal Basis
The main conceptual proposal in this paper is to maximally limit data collection given a target performance using performance curves. We plot the true performance curve for the GoogleLocal-L dataset [32] in Figure 1 and contrast it with a figure from Hestness et al. [6] that identifies three stages of data collection. The stages are: (1) the small data region, where the collected data is insufficiently representative and model performance is poor, (2) the power-law region, where there is a direct trade-off between the amount of data collected and performance, and (3) the irreducible error region, where the collection of more data does not lead to model improvements.
From a practical perspective, the data collection stages could be used to decide when collecting more data is necessary for reliable model performance (the small data region), when a user should decide whether to trade more data for better performance (the power-law region), and when data collection should stop (the irreducible error region).
The distinction of these phases is also pertinent from a legal perspective. In particular, the application of data minimization's necessity criterion would indicate that continued collection of personal data in the third stage would be hard to justify as personal data is not "necessary" to improve the model and meet its underlying purpose. We formalize these implications into a formal stopping criterion based on an empirical derivative of the the learned performance curve.

Formal Interpretation
We follow a recent interpretation that ties the processing purpose of data collection in machine learning models to improvements in model performance metrics [2]. This interpretation raises an open question of what it means to minimize data in relation to a metric-based purpose. We propose a formalization based on the returns in performance from additional data.
Scenario and Notation. We assume a scenario where a data processor operates a service (a model M , such as a classifier or a recommender system) and collects data from a pool of queryable data P (consisting of user-feature-value triples) generated by a population of users U. The acquired data is used to train M and make predictions for each user u ∈ U. We further assume that, when the data collection starts, the data processor has access to some initial data: I for training the model and V set aside to validate model performance predictions. Such initial data would include any data that is historical, purchased, or collected in different markets.
During data collection, the processor applies a feature acquisition policy H(P, n) which queries n feature values from P. Queries equate to the collection of a specific user-feature-value for inclusion in the training set for model M . We refer to the union of initial and acquired data as A and let | · | denote the cardinality of a set. Let σ M represent the true performance curve for M , which maps a domain of training dataset sizes to a range of model performances as measured by a performance metric σ. User-specific performance curves for M are termed σ u M for a given user u. The processor can use the resulting predicted performance curve to adhere to a concrete data minimization objective. We propose one such objective below: returns-based data minimization.
Minimizing by Returns in Performance. We minimize in reference to a threshold on the return in model performance of additional data. One could select an appropriate threshold by assessing user preferences or selecting a sufficiently small threshold such that user experience is not affected. Formally, a data collector would cease data collection once the slope of the performance curve drops below threshold t: Producing an accurate approximation of σ M is thus central to any performance-based data minimization objective. Our experiments show that existing approaches produce performance curves that are insufficient for the stated objectives. We compensate for these shortcomings by proposing a more accurate method to approximate σ M . Experiments in the supplement furthermore engage an alternate formalization of data minimization, where the stopping criterion is determined by the relative model performance achieved rather than the performance returns, providing further evidence of the framework's flexibility.

Data Minimization via Scaling Laws
The framework accepts three parameters: feature acquisition algorithm H, model M , and performance metric σ. There are three steps: (1) H acquires a portion of the available data (Data Collection), (2) the performance curve is fit to the new data (Curve Fitting), and (3) Steps 1 and 2 repeat until the conditions of Step 3 (Stopping Criterion Evaluation) are met.
Data Collection. In this step, a feature acquisition algorithm H collects q observations from the pool of available observations P. Smaller q translate to more conservative data collection processes and to more accurate estimates of the stopping criterion at the expense of decreased efficiency (smaller q mean that Steps 2 and 3 are executed more frequently). One might choose to set a larger q early on during data processing, and decrease it as the data processing continues.
Curve Fitting. The key idea underpinning this step is to model the stages of data collection separately via a piecewise power law curve. The piecewise power law curve is the piece-wise combination of two power law curves, which we will refer to as f 0 and f 1 : where f (x) accepts as input a training set size x. We fit the piecewise power law curve to subsamples of A of different sizes. More specifically, given the query size parameter q, we generate |A|/q samples such that the size of each consecutive sample increases by q. For each sample, we evaluate model performance on V, and use the resulting pairs of values (sample size and performance on the validation set) to fit the performance curves. Details on how we fit the parameters are included in the supplement.
Finally, we choose a threshold t such that the slopes of f 0 and f 1 maximally differ. More formally, assuming b t 0 refers to the decay parameter of the first power law curve trained given a threshold of t, we set t to be: max This follows our intuition regarding the power law region and the diminishing returns region: namely, that the two stages are distinguished by the differing return in additional data. Note that in this paper we assume that model performance increases as we collect more data. This is a common assumption in the performance curve literature [16,6], but there are cases in which additional data may hurt model performance. In these settings, a different family of parametric curves should be used.
In theory, one could compute a stopping criterion directly from the subsamples of A, without fitting the performance curve. This is undesirable for two reasons. The first problem is the noise inherent to individual subsamples, as we will see in later experiments. Second, learning a performance curve affords flexibility to a range of data minimization objectives, including those that cease data collection based on absolute model performance rather than performance increase rate (relevant experiments are in the supplement).
Stopping Criterion Evaluation. In this step, the resulting performance curve is used to accomplish a specific data minimization objective. Note that these are not the only reasonable data minimization objectives and the framework can adapt to different formulations. Minimizing by returns requires the data collector to specify a threshold for return after which data collection should stop, t ∈ R. We can use the performance curves to estimate this quantity by taking the derivative at a given sample size: Onceŝ falls below t, data collection stops.

Experiments
Datasets. We perform experiments on two datasets in the recommender system domain: MovieLens-20M [33] and GoogleLocal [34,32]. The datasets contain user ratings for movies and businesses, respectively. For each, the task is to predict user ratings for unseen items. We sample each dataset at two sizes to examine how results generalize across user numbers and sparsity levels. Dataset statistics can be found in Table 1 and preprocessing pipelines can be found in the supplement.
Each dataset is subject to the same initial, validation, and test splits, where each split is 10% of the total ratings and stratified across users. The remaining 70% of the data is the queryable rating set Q. We produce 5 random splits of each dataset according to these divisions. All results are reported over the 5 splits. We assume random feature acquisition unless otherwise stated. Baselines. Methods relating dataset size to performance commonly assume a power law model [6,8]. We include 2P-PL-Initial to determine the benefit of updating the curve as data is acquired, and a two-parameter power law method 2P-PL to represent the most common approach to fitting performance curves [8,35]. The remaining baselines represent variations of the power law curve that capture the notion of diminishing returns. The first (3P-PL) models the irreducible error directly and the second (3P-PL-Exp) models an additional exponential decay. The parameter fitting approach is the same for our method and described in the supplement.

Evaluation of Data Minimization Objective
Minimization by diminishing returns proposes that one should decide to stop collecting data based on the return that data affords, where we define this return to be the improvement in model performance.
In this experiment, we compare the amount of data collected by a stopping criterion based on the true performance curve to the amount of data collected by the estimated performance curves. In order to apply a returns-based stopping criteria to the true performance curve, we calculate the true return via a smoothed approximation of the slope over discrete subsamples. Results replicated over different degrees of smoothing are included in the supplement and consistent with those reported below.
For a variety of thresholds, the proposed method halts data collection significantly closer to a criterion with access to the entire performance curve ( Table 2, p-value = 3e-6). Due to the noise of the heuristic-based approximation, (Naive) produces stopping criteria that are both noisier and further from the true stopping point. Later experiments show that Naive fails to generalize to different feature acquisition algorithms and moreover, cannot accommodate alternate performance-based data minimization objectives.
The slope estimates drawn from the performance curve in our framework are more accurate than those of the curve-fitting baselines across the stages of data collection (Figure 2 (A,C)). 3P-PL-Exp consistently underestimates the return on additional data over the course of data collection, and subsequently halts data collection too early. In contrast, 2P-PL-Initial, 2P-PL, and 3P-PL overestimate the return on additional data and frequently halt data collection later than the empirically derived stopping point. These results suggest that the use of 3P-PL-Exp would produce a conservative data minimization approach in that such a data minimization method would be unlikely collect data past a certain threshold. The reverse is true for the remaining baselines -such a data minimization approach would likely collect more data than is required. This is a direct result of each method's ability to model the last stage of data collection accurately. Examine each method's ability to forecast performance given the entire dataset (Figure 2 (B,D)). Each method converges to the true value for model performance (red) over the course of data collection. The power law baselines (2P-PL-Initial, 2P-PL, 3P-PL) underestimate error given P. This is in line with prior work in machine translation, which shows the underestimation of test error using power law curves to approximate performance curves [16], and a consequence of extrapolation from the power law region into the diminishing returns region. 3P-PL-Exp instead overestimates test error because the e −bx term produces a curve too flat to describe the true relationship; illustrative plots for the performance curve fits are included in the supplement.
Our approach's halting points for both GoogleLocal-S and MovieLens-S exhibit more noise than their larger counterparts. This suggests that attaining a reliable estimate of the return on additional data is more challenging in the context of smaller datasets.
Robustness to Feature Acquisition Algorithms. Thus far, we have considered data collection where observations are queried randomly from Q. AFA methods improve upon this approach by   Table 3: Robustness to AFA Algorithm. The proposed method adheres most closely to the true stopping point across AFA algorithms applied to data collection from GoogleLocal-L.
instead querying feature values based on their uncertainty [26,36,37] or contribution to a downstream task [38,27]. Successful AFA methods collect less data than random feature acquisition and deliver equivalent performance. Recent work has shown that this success is often dependent on experimental conditions [39].
We consider two popular AFA methods: Stability and Query-by-Committee (QBC). QBC [37] employs three matrix imputation approaches (k-NN, EM, and SVD) to predict missing feature values. Stability takes a similar approach and predicts missing feature-values using SVD given different ranks. Each feature-value's uncertainty corresponds to the variance in predictions. Both algorithms request the highest variance feature-values. For Stability, we follow the approach of [26] and set the ranks to be [1,2,3,4,5].
Across both AFA algorithms and multiple thresholds, our approach halts data collection closest to the true stopping point (p-value = .003). Table 3 reports these results for GoogleLocal-L. It is worth noting that existing approaches are more competitive in this setting. This could be attributed to an expanded power law region; the performance curves for Stability and QBC can be found in the supplement and each suggest that the power law region is expanded by AFA algorithms. In general, trends for each baseline hold in this setting: the baselines which use a single power law (2P-PL-Initial, 2P-PL, 3P-PL) stop collecting data too late on average, while 3P-PL-Exp stops collecting data too early. Naive is naturally affected by the noisier performance curves and performs significantly worse than the other methods.
Robustness to Query Size. In the previous experiments we used a query size of 2% of the full dataset size. Here, we investigate the robustness of the predictions to different query size values q ∈ [0.005, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07]. Large q simulate a setting in which large batches of data are acquired at one time, while smaller q simulate the continuous arrival of new user data. Table 4 reports that the proposed method provides the closest estimation of the true model performance across different query sizes. Plots in the appendix support this observation for other datasets and variation in the true stopping point across query sizes is due to both the random splits and the stochasticity of FunkSVD. While our method produces the most faithful estimates of the true stopping point across query sizes it is more sensitive to small query sizes compared to baselines using a single power law curve. Lower query sizes require models to be retrained more frequently to produce data to fit the performance curve. In the context of models with computationally intensive training  Table 4: Robustness to Query Size. Applied to GoogleLocal-L, each method's robustness to different query sizes sheds light on the tradeoffs involved in query size selection. The proposed method and Naive are competitive in their accuracy in estimating the true stopping point, while 2P-PL and 3P-PL produce the most consistent stopping criteria over threshold sizes. Figure 3: (A) User-specific performance metrics when minimized data collection learns one curve for all users (left) and a curve for each user (right). Unsurprisingly, we see that the mode of user-specific performance increases as t increases. This is also the case when learning user-specific performance curves, but there is a large spread of true returns on additional data. This suggests future areas of work for learning accurate user-specific performance curves. (B) We show that the performance achieved during data collection depends on both the AFA algorithm employed and the initialization conditions. Error bars are reported over 5 random initializations. (C) We also show that a small portion of users bear the majority of the data collection burden in a histogram of the quantity of features acquired per user by Stability from MovieLens-S halfway through data collection.
procedures, it is optimal to choose the largest query size that maintains accuracy. On the other hand, smaller queries will lead to more accurate stopping decisions and less data overcollection. It is up to a practitioner to select the query size based on their domain knowledge, and our results suggest that the set of query sizes producing accurate estimates is quite large.

User-specific Data Minimization: Considerations
Previous sections discuss minimized data collection in terms of diminishing returns. In this section, we examine the method's effect on per-user metrics. We discuss how user performance-based data minimization departs from traditional assumptions for performance curves and recommend areas for further research.

Per-User Performance Curves
Here, we analyze the performance of the proposed method on user-specific performance metrics in two cases. In the first, we replicate the setting discussed in previous sections and learn a performance curve for the entire dataset. In the second, the data collection method learns a performance curve per user and applies a stopping criterion based on goal t to each curve. We use the same procedure to estimate t u as t earlier, except we use a user-specific performance curve rather than a global performance curve. The user-specific performance curve is learned by replacing a global performance metric (MSE over all users) with a user-specific performance metric (MSE over a set of items specific to one user). Estimating t u from σ u M produces a t u for each user.
In Figure 3(A), we plot the distribution of user returns in performance given a global threshold t (left). As t increases, the distribution mode shifts up and the variance in user fractions of performance decreases. Note that the x-axis for each histogram extends beyond 1. This is because more data does not necessarily translate to increased per-user performance. Two factors are responsible: 1) The small validation set size for each user produces noisy performance estimates and 2) the collection of additional data could still hurt user performance if this data is not representative. In this setting, the assumption of monotonically increasing performance over data collection does not hold, and accordingly, the minimized data collection method does not perform as well. One key takeaway from this experiment is that the return in performance may not be an appropriate metric for data minimization on a per user level. We include comments on how the method may be further adapted to the per user setting in the supplement.

Impact of AFA on Users
AFA is a natural choice for limited data collection. In this section, we illuminate several impacts of standard AFA algorithms on data subjects.
Disparate data collection burden. First of all, AFA algorithms collect different number of features from different users. Figure 3(C), plots a histogram of the quantity of collected data over users for AFA algorithm Stability, for dataset MovieLens-S (similar trends exist for other setups).
AFA algorithms "exploit" a small number of users by collecting a large number of feature-values from them. Yet, our experiments also show that increased data collection significantly correlates with better performance for individual users. Thus, the overall behavior of AFA in the context of data minimization raises questions of both the user fairness as well as user agency. Should users be able to decide whether they would like to become high-collection users in exchange for higher performance? How marginal must this improvement be to no longer justify data collection? Sensitivity to initial system data. In Figure 3(B), we examine the dependence of minimized recommendation performance on (1) the type of initialized data and (2) the feature acquisition algorithm employed. We consider two additional types of initialization; user-subset (initialized randomly across a subset of users) and item-subset (initialized randomly across subset of items). In each of these cases, the test set is formed from a random sample that includes ratings from all users.
In line with findings in prior work [39], we observe that the performance depends on data initialization conditions. Several observations have furthermore important consequences for the practice of data minimization. Note that when the initialization data is a random sample across users and items, AFA algorithms perform similarly. However, when the initialization data contains only a subset of users, or only a subset of items, non-random AFA begins to decrease in performance. This observation is consequential in cases where (i) the population of data subjects is evolving (initialization data would not contain the data of users who join at a later time), and (ii) the data processor is not initially allowed to collect certain feature values because of other constraints (such as the feature being sensitive).

Discussion
Unlike other data protection principles, including fairness and transparency, GDPR's data minimization principle has not yet seen wide adoption due to insufficient attention and the resulting lack of computational formalizations. Aligning insights and concepts in machine learning and law, this paper bridges the gap, developing formal minimization objectives and the first framework that learns compliant data collection stopping points. Our empirical investigation illuminated caveats that make data minimization challenging in practice. We demonstrated properties of active feature acquisition-a technique which might be thought of as a go-to tool for data minimization-that might be undesirable in the context of personal data protection. We showed how AFA might place excess data collection burden on a small set of users, and that the technique's performance depends on data initialization conditions, with degrading performance under conditions simulating evolving user communities or restricted feature sets.
In light of these complexities, we believe that data minimization compliance in machine learning models will require similar efforts as the principle of fairness has garnered. Definitions, formal implementations and caveats will depend on the application domain, the underlying model (recommendation, classification), as well as societal, cultural and individual preferences (when to minimize, or which data to prioritize). The piecewise power law may not be appropriate for all domains, including user-specific data minimization and cases where additional data significantly degrades model performance. Finally, it is important to recognize that GDPR does not impose a hierarchy of importance of different principles -data minimization and other principles must be satisfied at the same time. In practice, this requires examining the trade-offs between different data protection principles. While this paper focuses on the relationship between data minimization and accuracy, our empirical study, like some of the prior work [40], suggests there exists a tension between data minimization and fairness. Reconciling such tensions and making sure data minimization does not disproportionately affect marginalized populations will be imperative to broader adoption.