Auditing Black-Box Prediction Models for Data Minimization Compliance
Authors: Bashir Rastegarpanah
Krishna P. Gummadi
Mark Crovella
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Responsible ML
Privacy
Data Minimization

Abstract: In this paper, we focus on auditing black-box prediction models for compliance with the GDPR’s data minimization principle. This principle restricts prediction models to use the minimal information that is necessary for performing the task at hand. Given the challenge of the black-box setting, our key idea is to check if each of the prediction model’s input features is individually necessary by assigning it some constant value (i.e., applying a simple imputation) across all prediction instances, and measuring the extent to which the model outcomes would change. We introduce a metric for data minimization that is based on model instability under simple imputations. We extend the applicability of this metric from a finite sample model to a distributional setting by introducing a probabilistic data minimization guarantee, which we derive using a Bayesian approach. Furthermore, we address the auditing problem under a constraint on the number of queries to the prediction system. We formulate the problem of allocating a budget of system queries to feasible simple imputations (for investigating model instability) as a multi-armed bandit framework with probabilistic success metrics. We define two bandit problems for providing a probabilistic data minimization guarantee at a given confidence level: a decision problem given a data minimization level, and a measurement problem given a fixed query budget. We design efficient algorithms for these auditing problems using novel exploration strategies that expand classical bandit strategies. Our experiments with real-world prediction systems show that our auditing algorithms significantly outperform simpler benchmarks in both measurement and decision problems.

Auditing Black-Box Prediction Models for Data Minimization Compliance
Bashir Rastegarpanah Boston University bashir@bu. edu
Krishna P. Gummadi
Mark Crovella Boston University crovellafbu.c edu
MPI-SWS Summadiimpiissss
Abstract
In this paper, we focus on auditing black-box prediction models for compliance with the GDPR's data minimization principle. This principle restricts prediction models to use the minimal information that is necessary for performing the task at hand. Given the challenge of the black-box setting, key idea is to check if each of the prediction model's s input features is individually necessary by assigning it some constant value (i.e., applying simple imputation) across all prediction instances, and measuring the extent to which the model outcomes would change. We introduce metric for data minimization that is based model instability under simple imputations. We extend the applicability of this metric from a finite sample model distributional setting by introducing a probabilistic data minimization guarantee, which we derive using a Bayesian approach. Furthermore, we address the auditing problem under constraint on the number of queries the prediction system. We formulate the problem of allocating budget of system queries to feasible simple imputations (for investigating model instability) as a multi- armdd bandit framework with probabilistic success metrics. We define two bandit problems for providing a probabilistic data minimization guarantee a given confidence level: decision problem given data minimization level, and measurement problem given a fixed query budget. We design efficient algorithms for these auditing problems using novel exploration strategies that expand classical bandit strategies. Our experiments with real-world prediction systems show that our auditing algorithms significantly outperform simpler benchmarks in both measurement and decision problems.
1 Introduction
Concerns about the widespread use of data-driven prediction models and their growing reliance on personal data of individuals, have led to a number of data protection laws and regulations recent years [17 19 24). Prominent amongst such regulations is the GDPR (article 5.1.c) [19 that proposes the data minimization principle to control the extent to which personal data can be acquired and used by prediction models. Specifically, the data minimization principle states that: "Personal data shall be adequate, relevant and limited to what necessary for the purposes for which they are processed." "
Despite considerable public debate about the GDPR and the data minimization principle, to date, only few works [8] have attempted operationalize (i.e., formally interpret) the legal principle for prediction models. These works have focused on finding operationalizations of data minimization that tie the purpose of data processing to some performance metric such as prediction accuracy (e.g., in recommender systems (2). or in classification (18). Specifically, they study whether prediction model can be redesigned to achieve similar prediction performance, while using fewer input features. In the process, these works assume transparent setting, where the full knowledge of the prediction algorithm, training procedure, and desired performance metrics is available to the party investigating the feasibility of reducing data inputs.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

When putting data minimization into practice, an important case to consider is an auditing scenario where an outsider (auditor) wants test given prediction model for compliance with the data minimization principle at deployment time. As prediction algorithms are often important business assets, a more realistic auditing scenario one in a black-box setting in which the auditor interacts with the model without access to the model internals.
In this paper, we propose an operational definition of the data minimization principle that allows auditing black-box prediction models for compliance at deployment time. In particular, we assume an auditor who does not have access to how the prediction model works, or to the training data, or to information about the purpose of the prediction model. All the auditor can do is using data points to query a given black-box prediction model with a fixed set of imput features, and observe the outcomes. We believe our black-box model setting covers many real-world scenarios, as it only requires the designers of prediction models to allow auditors to query their models with prediction instances.
Our key insight is that the auditor can test whether an input feature is needed by the prediction model, by imputing (i.e., guessing) its value and checking the extent to which the outcomes change (i.e., are unstable) for different prediction instances. Intuitively, if the actual value of an input feature is not needed (i.e., can be replaced with a constant) arrive at similar (stable) outcomes for most prediction instances, then the use of the feature violates the data minimization principle. Note that operatlonalization does not require knowledge of the purpose of the prediction model and is independent of performance metrics. Such an operational definition is particularly important given that is common for companies who provide personalized services to justify data collection simply as "for improving service" (9]
our instability-
We show how simple imputations, where the actual values of individual features are replaced with a constant value, can be leveraged as a strategy for limiting data inputs to a prediction system at deployment time. We define a data minimization guarantee that is based on a metric of model instability under different feasible simple imputations. While this guarantee induces a procedure for auditing data minimization assuming finite sample model, we extend the applicability of our auditing framework in two ways. First, we propose probabilistic audit that allows the auditor to provide a data minimization guarantee some confidence level with respect to an underlying data distribution. We achieve this goal by introducing the notion of a probabilistic data minimization guarantee and adopting a Bayesian approach. Second, we address the auditing problem under a constraint on the number of queries to the prediction system and we design auditing algorithms that use a budget of system queries strategically in order to provide a data minimization guarantee.
We cast the problem of allocating a query budget to feasible simple imputations into a multi-armed bandit framework, and we formulate two bandit problems that correspond to different auditing tasks given a fixed confidence level: a decision problem given a data minimization level, and a measurement problem given fixed query budget. Furthermore, we design efficient algorithms for the above problems using exploration strategies for selecting arms. We propose four heuristic exploration strategies: two strategies inspired by Thompson sampling, and two that are custom for our setting.
Finally, we study the effectiveness of our auditing algorithms using different real-world prediction systems. We build prediction models by applying standard model evaluation and feature selection methods, and use the resulting models to perform black-box audits. Our experiments show that algorithms that exploit the proposed bandit framework significantly outperform simpler benchmarks.
2 Related Work
Data Minimization. Only few recent papers have addressed the problem of operationalizing data minimization in prediction systems. Biega et al. [2) propose definitions that are based on recom- mender systems' performance, and conduct an empirical study to check the original recommender performance can be preserved, while limiting the number of known user ratings. The authors in [8 suggest a formulation based on classification accuracy and study the trade-off between data minimiza- tion and satisfying other fairness properties. Clavell et al. [10) interpret data minimization limiting the use of sensitive personal data and do an experimental analysis that suggests data minimization should not be applied without consideration of other social concerns such as fairness.
Model Instability in Machine Learning. The instability of prediction models studied in both adversarial and aon-adversaiial settings. The traditional non-adversarial setting is concerned with the

---

instability of a model under different training data [15 8 The adversarial setting studies the effects of data perturbations on the model predictions. Perturbations in training data often called data poisoning and has been studied for various prediction models [23]. The more relevant problem to our setting is however studying the effect of test data perturbations, which known as evasion attacks at test time [ [6].
key difference between our instability metric and model instability under evasion attacks is in the type of perturbation that we define. While evasion attacks consider perturbations defined as modifying a data instance inside fixed-radius ball under a particular norm, we consider perturbations defined as projections induced by simple imputations. Moreover, the evasion attack problem concerns the instability of model prediction locally at each data point whereas the audit problem concerned with global notion of instability (see Section 3)
3 Model Instability-based Data Minimization Guarantees
In this section, we first formalize our setting and define metric for model instability under simple imputations. Then we show how this metric can be leveraged to define a data minimization guarantee.
Setting. We consider a prediction model being audited at deployment time for adherence to data minimization principle. The model has a fixed set of inputs variables (features) and output variable from a discrete domain. We assume a black-box setting, i.e., for any prediction instance, an auditor can query the model by specifying the values of all input features and observe the produced output, while the procedure used for generating the output from the inputs is unknown to the auditor. The auditor's ' goal then is measure the level of data minimization satisfied by the prediction model using a limited number of queries. A schematic illustration of this setting is provided in Appendix A.
Notation. Formally, let YF denote a prediction model over set of input features is F {f...... fa). where each feature f. takes values from domain X, X' = I X, denotes the input space of Yp. For any prediction instance
X, YF (x) y denotes the prediction made by Yp for x, and 3 is the discrete set of targets in the output space. We also consider a distribution Px over the input space from which samples (data points) are drawn in deployment. The auditor's challenge is to test whether the the model Yp satisfies data minimization principle over Px.
Assessing the need for individual features with simple imputations. To assess the need for individual features, we propose using simple imputations. Simple imputation is a procedure that is commonly used for handling missing data, and it works by assigning a constant value to feature f; in any prediction instance in which fi is missing. If an auditor finds that imputing a constant value to an input feature fs has or small effect on outcomes across different prediction instances, then the auditor can conclude that information about the actual values of f, are not needed by Yr to arrive at prediction outcomes. Our idea is to quantify the instability or changes in prediction outcomes to determine the level or extent to which the data minimization principle has been satisfied or violated.
metric for model instability under simple imputations. We now define a metric for instability of a prediction model, Yr, under simple feature imputations, Formally, we define an imputation function T such that for any prediction instance x, Tx),((x) returns vector in which the value of feature fs is replaced with E X₁. Let Ly, (x. fz. b) be binary indicator variable that is I if the prediction made by Yp for x changes after imputing fy with b, or 0 otherwise. Formally,
{
if (x) # (F(TT,,(x))
1yp (x, fz
(I)
otherwise
Let X be random variable that takes values x E X according to underlying data distribution Px. We define the instability of Yr over Px with respect to feature fn and imputation value b as:
3 = Fx [ (X,
In other words, 83 denotes the probability that the prediction for a data point drawn randomly from Px changes after imputing f, by b.
Instability- data minimization guarantee. We now define data minimization guarantee an auditor can offer using our model instability metric 8y. Intuitively, the imputation b that induces
iii

---

the minimum prediction instability for feature f, determines how necessary the feature ff is for generating the predicted outcomes. So a natural data minimization guarantee can be arrived at by finding the greatest lower bound on the need for each individual feature f3 (which in turn requires finding a feasible imputation for each fj that induces minimum instability) [
Formally we defne:
Definition A prediction model Fr satisfies data minimization at level B if there does not exist any feature I, E F and any imputation value b X2 such that (3) < B. The highest level f3 which data minimization is satisfied constitutes the best data minimization guarantee an auditor can offer for Yp-
Intuitively, data minimization guarantee at level 3 ensures that every input feature used by prediction model is indeed necessary to reach the predictions made for at least a certain fraction, B, of prediction instances. Note that if prediction model satisfies data minimization at level 3, it also satisfies data minimization at any level 3' < B. practice, the auditor would be interested in finding the best guarantee, i.e., the largest value of B at which a prediction system satisfies data minimization.
4 Audit Mechanisms for Data Minimization Guarantees
We now consider the challenge of designing efficient black-box audit mechanisms for producing the data minimization guarantee discussed in the previous section. Notice that we defined model instabilities as the expected value of an indicator random variable over an underlying data distribution Px. In practice, however, the auditor can only query the black- box model with finite number of samples drawn from the distribution to estimate the model instability. We call this set of available query samples (prediction instances) the audit dataset D
Population audit. Given an audit dataset and assuming a finite sample model, the model instability with respect to each simple imputation, i.e., each (feature, imputation value) pair, be computed using the the population mean over all prediction instances in the audit dataset. In particular,
Σ
(3)
D Audit
xEDAsdit
The auditor can then measure the data minimization level by exhaustively searching over all features and imputation values and finding the minimum instability based on the the population mean over all prediction instances in the audit dataset. We call this procedure "population audir."
However, in many practical auditing scenarios, population audit may not be feasible because the number of queries an auditor can issue to the prediction system is limited, and an exhaustive search would exceed the query budget many times over. Furthermore, auditors are often interested in guarantee that valid over yet unseen samples drawn from the underlying data distribution.
In the following, we address the above shortcomings of population audit by introducing a proba- bilistic audit mechanism for data minimization. In a probabilistic audit, the auditor investigates the prediction model's instability by observing its outputs for a limited number of query data points, and offers a probabilistic guarantee about the data minimization level satisfied by the model.
Probabilistic data minimization guarantee. In order to design probabilistic audit mechanism, we first define the probabilistic data minimization guarantee. This guarantee allows an auditor to extend the applicability of the instability-basee data minimization metric from finite sample model to distributional setting. Similarly to the data minimization guarantee in Definition I we define:
Definition 2 A prediction model Vp satisfies data minimization at level B with a percent confidence if the probability that B3 for at least one feature f3 F and one imputation value b X, is less than or equal to a.
Intuitively, satisfying this guarantee at a high confidence a means that with high probability, there does not exist simple feature imputation using which the model prediction changes for less than B fraction of samples drawn from distribution Px-
We only consider the necessity of each individual feature for achieving system outputs, and leave the more general case of considering all feature combinations for future work.
iv

---

Probabilistic audit. Now we present a mechanism for providing the above probabilistic guarantee. First, the probabilistic auditor can adopt a Bayesian approach measure the uncertainty about the model instability under different simple imputations. Assuming a prior distribution for each By. the success probability of the Bernoulli variable ly, (X, fj. b). the auditor can apply the Bayesian update rule to achieve its posterior distribution based on the observations about the model instability under Tf,.00. Each observation corresponds querying the prediction model for investigating the model instability under this imputation for a data point drawn randomly from Px.
In particular, let S denote the number of observations for which the simple imputation +/2
changes the model prediction, and F be the number of observations whose prediction does not change. Using the standard choice of modeling the mean of Bernoulli variable with the Beta distribution and the resulting update rule, we get the posterior distribution 8 ~ BBlaaaa Sy. c+ FJ)
when the prior belief is B3 Beta(a, c) for each feature f; and imputation value b X,.
Next, we explain how an auditor can use the the posterior distributions of all 883s to infer probabilistic data minimization guarantee, i.e., verify whether with high probability a, all Bys are greater than some level 3.
To satisfy the probabilistic data minimization guarantee at level 3 with confidence a, Definition 2 requires the probability of the following event to be small (less than or equal to 1 - a)): "for at least one feature f F and one imputation value b Xz. it is true that B3 s B." Formally, we can rewrite the statement as:
Pr[3(f E F, E 2,) S.L. S 5
(4)
We can use Boole's 's inequality find an upper bound for the the probability in the left hand side of (4). We can find a lower bound for the same using the observation that the probability that 39 S B for least one feature ʃg and imputation b is greater equal than the probability that 89 S 3 for any arbitrary ʃj and b. In particular we have:
max fEE.bEX
Pr[s I م < Pr[3(, E F, s.t. E
Σ
Pr[3) S $
(5)
BEEFEE
Given the posterior distribution of 33. let T1( = (a + S c + F denote its cumulative distribution function. We can rewrite 5 as:
LJ(0) S PrBUs E,,, s.t 83 S EEF,DEX,
max
Σ
L3(3)
(6)
fEEREE
The auditor can use these bounds decide whether not prediction system satisfies data mini- mization at given level B and a given confidence level a as follows:
If the upper bound in 6 is less than or equal to (1 - a). then the auditor can declare that prediction system satisfies the probabilistic data minimization guarantee (as the probability that at least one $39 is less than 8 is smaller than (1 - a:). On the other hand, if the lower bound in (6) is greater than or equal to ar the auditor can declare that prediction system does not satisfy the probabilistic data minimization guarantee at level B with confidence
If neither of the above conditions apply, the auditor cannot decide and would need to issue more queries to the black-box model and improve its estimate of posterior distributions of BBs.
Alternately, if the auditor is concerned with measuring the best data minimization level that the prediction system satisfies with given confidence a, they can leverage the observation that the upper bound in (6) is a monotonically increasing function of 3, and apply binary search find such that the upper bound in (6) is equal to 1 - a. The resulting 3 would be the best data minimization level that can be guaranteed with confidence based on the posterior distribution
5 Auditing With a Limited Query Budget
Using the framework introduced in Section 4 an auditor can provide a probabilistic data minimization guarantee based on the posterior distributions that are created for the model instability with respect
A visualization of our probabilistic audit mechanism is provided in the supplementary (Appendix B).

---

to each simple imputation. As an auditor investigates the model instability with respect to different imputations, each posterior distribution is updated. Clearly, reducing the uncertainty about the instabilities of certain imputations may be more effective than others in finding data minimization guarantee with high confidence.
Since it is desirable to limit or minimize the total number of queries used, challenging problem faced by the auditor is how distribute queries investigate the effect of different simple imputations on the model instability. In particular, while a naive auditing approach may allocate equal numbers of queries for updating each posterior distribution, reducing the uncertainty about the model instability with respect to certain imputations might be more helpful than others, when providing a probabilistic data minimization guarantee. Thus an intelligent auditing strategy would spend more queries on investigating those imputations.
We address the above query allocation problem by introducing auditing algorithms that query the prediction system strategically. Hence we cast the problem of allocating a query budget to simple imputations into a bandit framework. Within this framework we consider two stopping criteria, corresponding to the two auditing task types. In particular, we formally define two bandit problems that correspond to the following tasks: (i) measuring the greatest data minimization level satisfied by a prediction model given a fixed query budget, and (ii) deciding whether or not data minimization is satisfied at a given level using the minimum number of system queries. In Section 6 we introduce auditing algorithms for each of the above problems.
Multi-armed Bandit Framework. The multi-armed bandit problem [3] is a standard framework for modeling sequential decision problems under uncertainty, in which the actions (choices) are defined by a set of arms. A player sequentially chooses arms to play, and observes noisy signals of their quality, also known as rewards. The goal is then to optimize some utility while acquiring new knowledge about the arms. The query allocation problem for an auditor can be appropriately formulated as stochastic bandit in which the rewards are modeled by a Bernoulli distribution associated with each arm.
In particular, we consider an arm for each pair (fz, b) of imput feature f/ E F and feasible imputation value E Xz. In each round, the auditor chooses an arm (f,, b) and observes a binary reward that is a sample from a Bernoulli distribution with success probability 8/. More specifically, each observation of arm (fz. b) corresponds to evaluating 4r, (X. fy. b) at a data point x drawn randomly from Px- This evaluation requires querying the prediction system to check whether the model prediction for x changes using the simple imputation associated with (fz, b). The success probabilities, i.e., the mean rewards of the arms, are unknown to the auditor. Furthermore, we incorporate the Bayesian assumption introduced in Section + and model the success probability of each arm using a Beta distribution whose shape parameters depend on the observations from that arm.
Bandit algorithms are traditionally developed for optimizing cumulative reward, a goal that requires both exploration and exploitation. However, our auditing problem is pure exploration bandit since the auditor's s objective is to explore arms in order to obtain good estimation of the mean rewards (i.e., model instabilities). Previous approaches pure exploration problems have focused on two main objectives: minimizing simple regret 4. and the best arm identification problem ①. Our objective however different from these, as explore arms in order provide probabilistic data minimization guarantee. As explained in Section 4 equation (6) can be used to provide two types of guarantees depending on whether the data minimization level 3 is fixed or not. Consequently, in the following we define two pure exploration bandit problems, where each is associated to different auditing task: a decision problem, and measurement problem. Both problems use the bandit setting described above, but each has different set of input parameters and different stopping condition, which results in different data minimization guarantee.
Decision Problem: Fixed Confidence and Fixed Level. In this problem, the auditor's goal is to guarantee with given confidence that whether or not a prediction system satisfies data minimization at given level B. A good auditing strategy for this problem tries to use small number of system queries to provide this guarantee. Formally, based on equation (6) and using the bandit framework introduced in 5 the auditor seeks to solve the following problem:
vi

---

"Given confidence and data minimization level 3, iteratively select an arm (fz. b) to explore, and up- date the posterior distribution of 8 based on the observed rewards; such that the resulting posteriors induce Σ (3( < (1 a) or < max (3) using the minimum number of observations." feF
GEF DE
DEAS
Measurement Problem: Fixed Confidence and Fixed Budget. Alternatively, in this problem the auditor is given a fixed query budget and the goal is to measure 3, the highest level of data minimization that the prediction system is guaranteed to satisfy, with a given confidence a. Note that as explained in Section 4 for fixed confidence a and any state of posterior beliefs, 3 can be computed using binary search. A good auditing strategy however uses its query budget to provide the highest level of data minimization guarantee it can. Formally, we define the following bandit problem:
"Given confidence a and query budget T, iteratively select arm (fz,b) to explore, and update the posterior distribution of f3 each round; such that after T roundy the value 3 that satisfies L3) = (1 (1-a) is maximized." f
Σ
6 Auditing Algorithms
In this section present our algorithms for addressing the auditing problems defined in Section These algorithms provide framework for meeting the probabilistic guarantees required by the decision and measurement versions of a data minimization audit. Furthermore. we address the need to make audits efficient. The key challenge in making an audit efficient is to intelligently select which queries to present to the system under audit. We present a number of strategies, including novel strategies designed for our probabilistic setting; we will demonstrate the efficiency of these strategies in Section 7
Algorithms | and present solution strategies for the two versions of the auditing problem. Each algorithm assumed be able query the prediction model Yr, and be able sample an audit dataset DD Algorithm D summarizes the auditing procedure for solving the decision problem with confidence a and data minimization level 8,, where a and are provided as the inputs to the algorithm. The auditing procedure for solving the measurement problem is presented in Algorithm 2 In this algorithm instead of fixing the data minimization level, a fixed query budget T' is given as the input and the algorithm returns the level of data minimization that can be guaranteed to be satisfied with confidence a.
Algorithm 1: Data Minimization Audit (Decision Problem)
Algorithm 2: Data Minimization Audit
(Measurement Problem)
Input: YF, D, confidence a, level B
Input: YF, D, confidence a, budget T
Sh 0, 0, F. + 0; (V E Fb E X,) repeat
S + 0, F$ + 0-; (V', E F X3)
2 for t in 1 to do
(fs, SelectArm(3)
Find ( using binary search
Draw from uniformly at random
4
(fz, b) +- SelectArm (39"")
Query Yr to evaluate r = Jyp (x, fa, b) Increment either 5 or 1 based on r until A decision can be made for and 3: return The binary decision made using Eq
5
Draw x from D uniformly at random
Query Yp to evaluate r = Iy, (x, Jz, b) Increment either S or F/ based on r
7
return 3
Each algorithm has at its core an exploration strategy, i.c., a decision about the next query to present to the system. which we denote SelectArm() () (reflecting the bandit problem viewpoint). This decision uses the current knowledge about the reward distributions of the arms, and some exploration strategies given level B as well. As described in the previous section, the choice of which bandit arm to sample corresponds to a choice of (fz, b) and the sampling itself consists of querying Ty (x, (x, where x is random data point from D. The algorithms accumulate knowledge about arm (f,, by maintaining success and failure counters St. and F/.
When solving the decision problem (Algorithm()) [T] the arms are explored iteratively until a decision
can be made based the posterior distributions of the success rates of arms. That is, until the auditor
vii

---

can accept or reject that the prediction model satisfies data minimization at level | with confidence using Eq. For the measurement problem on the other hand (Algorithm[2) ( the auditing algorithm keeps selecting arms and querying the system until all the query budget is used. The largest data minimization level that can guaranteed with confidence a then computed using binary search.
Now we present the strategies for choosing which imputation to apply to the query sample used in each iteration of the auditing algorithms. While the bandit setting is natural one for our problems, the probabilistic nature of our problems does not correspond to any classical bandit problem. Hence, we propose and evaluate heuristic exploration strategies that are either based on classical approaches or new approaches we design in light of the specific nature of our problems. In particular, we propose four exploration strategies: the first two algorithms are based on Thompson Sampling, while the second two are designed specifically for obtaining lower bound guarantee on the mean reward
Thompson Sampling (TS). Our first approach is based on Thompson sampling (2 Thompson sampling is a heuristic for maximizing the expected reward when choosing actions sequentially under uncertainty, and it is shown to have good performance in practice [5] We adapt Thompson sampling to be used in our auditing algorithms as an arm selection procedure. In particular, at each iteration and for each arm (fz; b) a sample 03 is drawn from Beta(1; 55. + a, F + c) given the current success and failure counters. The arm that corresponds to the minimum sample is then selected to be explored next. The idea behind Thomson sampling to explore an arm according to the chance that reducing the uncertainty about its mean reward would better help finding a data minimization guarantee, which a probabilistic lower bound on all success probabilities. Thus, we choose the arm that corresponds to the minimum sample, instead of the maximum sample used in the original Thompson sampling.
Top-Two Thompson Sampling (TTTS). While Thompson sampling is effective in maximizing the expected cumulative reward, it is not a good strategy if the goal is to identify the optimal arm, as it may select a suboptimal arm at the outset, and then continue exploring that arm, resulting in little chance for other arms to be explored. In fact, it is known that algorithms achieving small cumulative regret cannot be optimal for the best arm identification problem 4.. Top-Two TS (20 addresses this drawback by randomly choosing between two of the best alternatives at each iteration. That is, with probability y returns the arm selected by TS, and with probability - y keeps sampling until an alternative arm is selected.
Previous work has studied the sample complexity of the best arm identification problem 4 as well as the convergence rate of TS- based strategies for both the expected cumulative regret [21 and the best arm identification problem (2).. In particular, it has been shown that using Top-Two TS, the probability that a sub-optimal arm is selected converges to zero at an exponential rate [20]. Notice that although identifying the arm with minimum mean reward induces a lower bound on all mean rewards, our problem is, in some sense, easier than the best arm identification problem since it does not require exact identification of the best arm far probabilistic lower bound on all arms is achieved.
Greedy. The previous two algorithms use the posterior beliefs about the mean rewards of the arms, and select arms with respect to their probability of having the minimum mean reward. However, the data minimization guarantee that we seek depends on the probability mass that is below some threshold 3 in all arms. Based on this observation, we develop two new approaches.
In the first approach, instead of sampling the posterior distributions at each iteration, we first evaluate (3). the cumulative distribution function at B3, for all arms. Then, using greedy approach, we select the arm whose posterior beta distribution has the maximum probability mass below B. Given that our data minimization guarantee for both decision and measurement problems depends on either the total sum or the maximum value over all L (B)'s 's the greedy selection more closely matches our algorithmic goal.
Probability Matching using CDFs (PM). Our second new algorithm adopts the probability match- ing strategy of TS, and applies it to the cumulative distribution functions of arm rewards at the given threshold B. That is, it selects arms in proportion to the amount of probability mass that is below / in each reward distribution, thus allowing more arms to be explored compared to Greedy.
3 Peecddoodee for these algorithms are provided in the supplementary (Appendix C).
viii

---

8000
Carketece
Conidlece
(a) Census/DT
(b) Digits/DT
(c) Nursery/DT
Figure 1: Auditing for 1% data minimization.
TTT
610-
0.0
0145
(a) Census/DT
(b) Digits/DT
(c) Nursery/DT
Figure 2: Measuring data minimization with 95% confidence.
7 Auditing Real-world Prediction Systems
In this section we study the effectiveness of the algorithms introduced in section 6 in auditing real-world prediction systems for data minimization compliance"
We build prediction systems using datasets from the UCI machine learning repository 77. We use three datasets that have discrete features and discrete target variables, and we apply different learning algorithms together with standard feature selection and model validation methods build a prediction model. In particular, we use the following prediction systems.
Digits/SVM. A dataset of 3823 images of written digits from the MNIST 14 database is used.
Each data point is an 8 x 8 matrix whose elements are integers from the range [0. 16), along with label from the set {0, 1,...,99 9). A support vector machine with linear kernel is used to build classifier that predicts the label associated with each image. 50% of data points are used to train the classifier, and recursive feature elimination procedure applied to select 9 features.
Census/Decision Tree. dataset of ~ 30K individuals from the US Census database used. Eleven features with discrete domain are available for each individual, and the goal is to predict whether person makes over $50K a year. A decision tree built using 20% of data samples as the training data, and recursive feature climination procedure is applied to select 5 features.
This dataset contains 8 discrete features from ~ 13K applicants for nursery schools in Slovenia. A label from a set of 5 priority groups is assigned to each applicant, and we use 20% of data samples to build a decision tree for predicting the priority group of each applicant.
Nursery/Decision Tree.
In the following experiments, for each system we use the whole data as the audit dataset from which query samples are drawn. All prior distributions for / parameters Jeffreys prior). The decision parameter in TTTS strategy is set to 1/2.
(1ta(1/2, 1/2) (i.e., the
In our first experiment, apply Algorithm I to decide whether each of the above systems satisfy data minimization at 1% level. We perform this task for 0.95 and 0.99 confidences, and using the exploration strategies introduced in section 6 As baseline algorithm, we also implement uniform exploration strategy that investigates all (feature, imputation value) pairs uniformly until a decision can be made.
*Code is available at: htttp:///gssauu..oo//r/attggggge http://aata-MMiniiaaaiiac Auditor
ix

---

The bar chart in Figure [ shows the average number of system queries used by each exploration algorithm and for each confidence level over 20 runs. The error bars show one standard deviation and the resulting Yes/No decisions, together with the frequencies of decisions, are printed over each bar. We observe that all three systems satisfy data minimization at 1% level, and our exploration algorithms reach this decision using significantly fewer queries compared to the uniform exploration method. Furthermore, the algorithms designed specifically for our auditing purpose (Greedy and PM) are on average slightly more effective than standard Thomson sampling based algorithms
Next we apply Algorithm[2jn to measure the level of data minimization satisfied by each system using different query budgets. We consider a .095 confidence for this measurement task, and in order to have a comparison point if the were no limit on the query budget, we compute the probabílistic data minimization level using the population audit, i.c., using all the data points in the audit dataset.
Figure 2 shows the level of data minimization that each algorithm can guarantee for each system and using different query budgets. In each experiment we increase the budget until one of the algorithms reaches the level measured by population audit. We observe that all of our exploration strategies significantly outperform the uniform exploration, i.e., they can guarantee a higher level of data minimization the given confidence for each query budget, and they can reach the level guaranteed by population audit using less than 5% of queries used by population audit. Finally, we observe that for smaller query budgets, Greedy and PM are on average more effective than TS-based algorithms.
Lastly, we illustrate the performance of our auditing framework for hypothetical scenario in which a data minimization audit may be particularly needed. We consider a case in which a prediction system has an input that is not actually used by the prediction model, i.e., the system collects excessive informa- tion from its users. We obtain such system by embedding the Census/DT model in another prediction system that asks for an additional attribute of the Census dataset but returns the output of the embedded model.
2000
aks
We apply the decision auditing algorithm for 1% data mini- mization level to this systems. Figure 3 presents the number of queries used, and the output of the auditing algorithms for each exploration strategy and two confidence levels. We observe that all algorithms return "No", i.e., detect that data minimization is not satisfied, as desired. More importantly, the exploration algorithms we propose use order of magnitude less queries to make this decision. And we particularly note that our Greedy strategy is significantly more effective than the other exploration strategies considered.
Figure 3
8 Summary and Concluding Remarks
In this paper we provide an operationalization of data minimization principle that is applicable to auditing prediction models. We propose using model instability as the purpose for which data needs to be minimized and we suggest exploiting simple imputations as tool for limiting data inputs at the test time. Adopting a Bayesian approach and a bandit framework, we provide efficient auditing algorithms that measure model instability with respect to different simple imputations and provide a probabilistic data minimization guarantee.
We initiated the audit framework assuming discrete feature values. In the scenarios where feature domains are relatively large (e.g., integers), more efficient bandit algorithms can be developed using ideas similar to (26] II 12), or [25] for infinitive domains. Other directions for future research include extending our individual features guarantee the case of all feature combinations, and studying the implications of instability-basee data minimization on different faimeess notions similar to works that have done it for accuracy-base -based data minimization [18]
Finally, although the framework we use in this paper is agnostic to the implementation details of the prediction model, an open question concerns the impact on data minimization of different feature selection techniques employed during model construction. On the other hand, our model-instability metric itself suggests feature importance metric, which may be used for feature selection; similar instability-base feature importance metrics have been previously proposed (c.g., 6)).
'The few "No"s in Figure Ic correspond to the prohabilistic nature of our guarantee.
X

---

Acknowledgments
This research was supported by the ERC Advanced Grant "Foundations for Fair Social Computing" (No. 789373), and the National Science Foundation under grant numbers IIS-1421759 and CNS- 1618207. We thank the anonymous reviewers for their helpful comments, which greatly improved the presentation of this paper.
References
[1] J.-Y. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits, In COLT, pages 41 41-53, 2010.
[2] A. J. Biega, P. Potash, H. Daumé, III, F. Diaz, and M. Finck. Operationalizing the legal principle of data minimization for personalization. In The 43rd International ACM SIGIR Conference on Research & Development
Information Retrieval, 2020.
[3] B. Biggio, I. Corona, D. Maiorca, B. Nelson, N. Šmdiić P. Laskov, G. Giacinto, and F. Roli. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pages 387-402. Springer, 2013.
[4] S. Bubeck, R. Munos, and G. Stoltz. Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer, 2009.
[5] O. Chapelle and L.. Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24:2249-223
2011. 2011.
[6] A. Datta, A. Datta, A. D. Procaccia, and Y. Zick. Influence in classification via cooperative game theory. In Twenty-Fourd International Joint Conference on Artificial Intelligence, 2015.
[7] D. Dua and C. Graff. UCI machine learning repository, 2017.
[8] K. Dwyer and R. Holte. Decision tree instability and active learning. In European conference on machine learning, pages 128-139. Springer, 2007.
[9] M. Finck and A. Biega. Reviving purpose limitation and data minimisation in personalisation, profiling and decision-making systems. Max Planck Institute for Innovation & Competition Research Puper, (21-04), 2021.
[10] G. Galdon Clavell, M. Martín Zamorano, C. Castillo, O. Smith, and A. Matic. Auditing algorithms: On lessons learned and the risks of data minimization. In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, pages 265-271, 2020.
[11] M. Jedor, J. Louedec, and V. Perchet. Categorized bandits. In Advances in Neural Information Processing Systems, 2019.
[12] S. Kumar, H. Gao, C. Wang, K. C.-C. Chang, and H. Sundaram. Hierarchical multi-armed bandits for discovering hidden populations. In Proceedings the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 145 153, 2019.
[13] T. Lattimore and C. Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
[14] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-2333 2324, 1998.
[15] R.-H. and G. Belford. Instability of decision tree classification algorithms. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 570-575, 2002.
[16] B. Nelson, B. Rubinstein, L. Huang, A. D. Joseph, and J. Tygar. Classifier evasion: Models and open problems. In International Workshop on Privacy and Security Issues in Data Mining and Machine Learning, pages 92-98. Springer, 2010.
xi

---

[17] E. O. of the President, C. Munoz, D. P. C. Director, M. U. C. O. S. O. of Science, T. Policy)), D. D. C. T. O. for Data Policy, D. S. P. of Science, and Policy)). Big data: report on algorithmic systems, opportunity, and civil rights. Executive Office of the President, 2016.
[18] B. Rastegarpanah, M. Crovella, and K. P. Gummadi. Fair inputs and fair outputs: The incompat- ibility of fairness in privacy and accuracy. In Adjunct Publication of the 28th ACM Conference on User Modeling, Adaptation and Personalization, pages 260-267, 2020.
[19] P. Regulation. Regulation (eu) 2016/679 of the european parliament and of the council. REGU- LATION (EU), 679:2016, 2016.
[20] D. Russo. Simple bayesian algorithms for best arm identification. In Conference on Learning Theory, pages 1417-1418, 2016.
[21] D. Russo and B. Van Roy. Learning to optimize via posterior sampling. Operations Research, 32(4):1211-144; 2014.
Mathematics of [22] D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen. A tutorial on thompson sampling. arXiv preprint arXiv: Xii::170..00000 00000000.8..... 2017.
[23] Steinhardt, W. Koh, and P. Liang. Certified defenses for data poisoning attacks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, page 3520-3532, 2017.
[24] P. Voigt and A. Von dem Bussche. The eu general data protection regulation (gdpr). A Practical Guide, 1st Ed., Cham: Springer International Publishing, 2017.
[25] Y. Wang. J.-Y. Audibert, and Munos. Infinitely many-armed bandits. In Advances Neural Information Processing Systems, 2008
[26] Y. Yue, S. A. Hong, and C. Guestrin. Hierarchical exploration for accelerating contextual bandits. arXiv preprint arXiv:1206.6455 2012.
xii


Reviews:
[{"review_id": "ws9w5zjZj47", "reviewer": "Reviewer_73BZ", "summary": "This paper presents a framework for auditing black-box prediction models for compliance with GDPR's data minimization principle. The audit framework is based on checking the necessity of each individual feature used in the prediction models by imputing them with constant values and checking the extent of variation in the predictions. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The key contributions of the paper are:\n1. formalizing the setting for auditing models with respect to the data minimization principle\n2. developing algorithms for how the necessity for individual features can be assessed through imputations with a limited query budget.\n3. providing a metric for model uncertainty under feature imputations.\n\nThese are important contributions for machine learning models where the feature set is specified apriori. \n\nMy main concerns are regarding the practical relevance of the proposed framework. Since the framework needs to impute each feature specified apriori individually to determine their necessity, automated feature detection based predictors (like deep neural networks) are not applicable for audit by the framework. This is a major limitation of the framework that prevents applicability on real-world datasets and complex models beyond SVMs and Decision Trees evaluated in the experiments. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations with respect to applicability for automatic feature detectors (e.g. deep neural nets) are not addressed.\n\n---- after rebuttal ---\nThe above concern has been addressed by the authors.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ZSrE9l9336g", "reviewer": "Reviewer_jdGr", "summary": "This paper defines a new setting generalizing existing work on establishing _data minimization_ as motivated by the GDPR. Unlike previous work, this work considers testing for data minimization in a black-box setting (previous work assumes access to model internals). Within this setting, the data minimization problem is defined according to a measure of model instability when certain features are replaced by constant imputation (as is often done for missing values in data preprocessing). Further, the problem of auditing a model for data minimization at a certain level (according to a metric the paper introduces) is framed as a pair of near-dual bandit problems: one which establishes the optimal auditing strategy to achieve a certain confidence that the metric is not violated, and another which assigns a fixed query budget in an expected-optimal way.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed this paper. I believe most of the things that don't quite work are also limitations of the prior work on which it builds, so I elect not to hold them against the paper. However, I will describe them in case that aids in the presentation.\n\nFirst, a black-box auditing setting is most useful for outsiders like activists or journalists. Enforcement entities or internal control entities would have the ability to demand access to model internals, and would want that anyway. Also, a probabilistic guarantee is less suitable in these cases, but is probably acceptable to outsiders who can't get details but might be able to interact with a tool in a query-oriented way. The paper doesn't say this explicitly and I think it should - in places it even intimates that the technique would be useful for enforcement-type or control-type auditing, and it should avoid that. That is, the value of the auditing tools to a specific constituency/application could be more clearly motivated, especially given the probability-oriented metric around which the contribution centers. Relatedly, there should be an explicit claim about whether the data considered for \"data minimization\" has any secondary uses beyond training the model under evaluation. One might fairly exclude such secondary use based on the way the GDPR ties data minimization explicitly to purpose limitation, but that may go too far into legal analysis of unsettled questions, risking that the paper's motivation would end up on the \"wrong side\" of future jurisprudence and guidance.\n\nSecond, I would appreciate some more careful contextualization of these new measures into existing literature on feature importance measures and feature engineering more broadly - if a feature is unnecessary in a data minimization sense, why should it be included at all? A typical answer would say that it helps to differentiate hard cases where other features coincide, so (as is noted in the discussion) there could be real and explicit tradeoffs with performance on minority subgroups or identification of rare phenomena. It would be interesting to explore this. I'm not deeply familiar with methods in the feature importance world, so it's hard for me to say to what extent the framing here is novel. But the setting is certainly novel, so I'm happy to leave that as an open question for other reviewers to fill in.\n\nThird, the algorithms supplied to solve the two bandit problems look correct to me, but even in the extensive discussion of sampling strategies there is no mention of the worst-case or even average-case sample complexity/convergence. It would be interesting to at least qualify this beyond the experiments performed (which seem to indicate that convergence is rapid enough to perform many runs without difficulty) - for example, is complexity dependent on the distribution in the problem being examined? Does it require distributional assumptions? How can an auditor know if convergence in a reasonable number of samples is likely?\n\nSome tiny points not worth including in the review narrative:\n* The paper claims to \"introduc[e] the notion of a probabilistic audit\" (at 155, but maybe elsewhere?). But this is not new. Even in financial auditing, it is quite common to use a sampling methodology to identify transactions in a record or activities within a corporation to reconcile against governance processes and then to express the audit's findings in terms of any identified deficiencies as well as a confidence level achieved that unexamined activities will not reveal additional deficiencies. So this claim should be weakened.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The work aims to address societal impact of other machine learning activities by providing insight into the extent to which a model relies on a minimal set of features. However, as noted in the main review, I think the work would be strengthened by more explicitly acknowledging limitations like explaining the settings in which claims of the sort the proffered technique produces will be acceptable/useful or acknowledging that collected data might be used in secondary places not examined by this approach or discussing the efficiency of the sampling strategies proposed more completely.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "RXKHPDEa67-", "reviewer": "Reviewer_xkzE", "summary": "The authors explore means for the blackbox auditing predictive models in line with data minimisation concerns. The key focus is on the role of particular features, i.e. whether they are necessary for the model or not. \n\nTowards this, the paper describes an instability-based data minimisation metric, based on various feature imputations, as well as a probabilistic measure of uncertainty (termed a data minimisation guarantee). \n\nGiven imputations can be expensive (require many queries), approaches considering query-budgets are described, where bandit frameworks are used for considering the greatest data minimisation level satisfied given a fixed query-budget, and whether a particular level of minimisation is satisfied using the minimum number of queries. \n\nThe approach and efficiencies of the query budget are demonstrated across three real-world datasets.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I found this paper relevant and interesting. Data minimisation is an important, and topical problem, and more work on this is certainly welcome. \n\nMetrics and methods regarding the impact of features in this context have the potential to encourage actions towards less 'invasive' systems (from a personal data perspective). Having means to assist minimisation, through defining probabilistic measures/metrics, and showing ways for reducing the associated overheads are of relevance to the community. Intuitively the methods seem sound, but I defer to the other reviewers to assess the specifics.\n\nThe evaluation appeared largely to focus on performance and the number of queries. This is clearly important. However, I was anticipating more about where data minimisation requirements are *not* met, and the role and effectiveness of the methods in uncovering these. This is done very briefly in Figure 3, in a scenario where some extraneous input features are added that do not impact the model. But there is a real opportunity for more exploration unpacking situations that are more messy, involving more features, etc (even if these are hypothetical/synthetic). (And indeed, something could have been said about the few \"NO\"s that cropped up in Fig 1). Given the general aim and context of this work, I think some exploration regarding scenarios that differ in how much they violate 'minimisation' is warranted. \n\nThe paper is generally well written. But I think there are some framing and contextual points that would better place the work. \n\nFirst regards the practicalities of the context and scenarios in which the use of these methods are envisaged. That is, how do they fit wrt a system? Given the focus is a 'black-box' audit, would this be e.g. through a remote service? These sorts of questions matter - e.g. to help understand if the method reducing 20k queries to 3k is sufficient? Moreover, many deployed systems won't have direct model interactions, but the model will operate as part of a larger system. This means a bunch of other data might be inputted to support the business process, only some of which flow to the model. Are there any implications of this? \n\nRelated is the intended target for these methods. The paper talks about an auditor, and with the legal discussion this comes across as a regulator. Would a regulator really employ a blackbox approach vs. using their other powers to audit and assess? In reading the paper, I actually felt this method might be better aimed at *internal* auditors (e.g. by developers/Q&A testers) rather 'external' entities. Some discussion clarifying things would help.\n\nMore broadly, it should be explicit that such approaches won't solve data minimisation concerns. GDPR is about technical *and* organisational measures - while what goes into a model can help, what is appropriate or not will depend on the specifics of the broader socio-technical processes involved.\n\nNote that these latter comments don't detract from the approach itself, but some mention of these sorts of things can help better frame the paper, the contributions and generally strengthen things.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There isn't really any discussion of the limitations in the paper. \n\nSome of that raised in the main review point to some of these.  I think it's important that the work is properly placed in its broader context -- that such approaches won't *solve* data minimisation problems, but might help.", "review_text": "", "extra_scores": {"ethical_concerns": "Fairly minimal. Though the paper should acknowledge that tackling issues of data minimisation are beyond what's discussed here.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors of this paper propose a principled approach to evaluate the data minimization principle of a black box model. Based on a defined model instability metric, the authors detail in their contribution how to audit a black box model (several sampling strategy are proposed) and how to assess how unstable the system becomes after several imputations. Real applications on small datasets are provided at the end of the paper.

The paper is very well written and clear. The problem tackled is highly relevant. While the probabilistic audit si well known and not new, the authors embed it nicely in their task at hand, auditing a black box model to assess the data minimization guarantee. Invoking multi arm bandit in their method is clever. This paper is an operational paper with a clear detailed method and some illustrations.

Based on the reviews and my own reading, I would like to suggest the authors to consider the following items, to further improve the quality of their paper: 

1) more extensive experiments.
2) guarantees on the data minimization principle depending on how one audits and how large the dataset is.
3) discuss how the imputation (single imputation is used here) strategy can impact the stability of the model.
Decision: Accept (Spotlight)