Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
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.

First, 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.

Second, 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.

Third, 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?

Some tiny points not worth including in the review narrative:
* 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.
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_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: The key contributions of the paper are:
1. formalizing the setting for auditing models with respect to the data minimization principle
2. developing algorithms for how the necessity for individual features can be assessed through imputations with a limited query budget.
3. providing a metric for model uncertainty under feature imputations.

These are important contributions for machine learning models where the feature set is specified apriori. 

My 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. 
limitations_and_societal_impact: The limitations with respect to applicability for automatic feature detectors (e.g. deep neural nets) are not addressed.

---- after rebuttal ---
The above concern has been addressed by the authors.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 

Towards 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). 

Given 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. 

The approach and efficiencies of the query budget are demonstrated across three real-world datasets.
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. 

Metrics 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.

The 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. 

The paper is generally well written. But I think there are some framing and contextual points that would better place the work. 

First 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? 

Related 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.

More 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.

Note 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.
limitations_and_societal_impact: There isn't really any discussion of the limitations in the paper. 

Some 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_title: null

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)