Data Minimization at Inference Time
Authors: Cuong Tran
Ferdinando Fioretto
Venue: NeurIPS 2023 poster (2023)
Keywords: Privacy; data minimization
TL;DR: The paper defines the concept of data minimization at inference time and introduces an efficient sequential algorithm to achieve data minimization.

Abstract: In high-stakes domains such as legal, banking, hiring, and healthcare, learning models frequently rely on sensitive user information for inference, necessitating the complete set of features. This not only poses significant privacy risks for individuals but also demands substantial human effort from organizations to verify information accuracy. 
This study asks whether it is necessary to use all input features for accurate predictions at inference time. The paper demonstrates that, in a personalized setting, individuals may only need to disclose a small subset of features without compromising decision-making accuracy. The paper also provides an efficient sequential algorithm to determine the appropriate attributes for each individual to provide. Evaluations across various learning tasks show that individuals can potentially report as little as 10\% of their information while maintaining the same accuracy level as a model that employs the full set of user information.

Data Minimization at Inference Time
Cuong Tran
Ferdinando Fioretto Department of Computer Science University of Virginia f fioretto@virginia. edu
Department of Computer Science University of Virginia kxb7sd@virginia. edu
Abstract
In domains with high stakes such as law, recruitment, and healtheare, learning mod- els frequently rely on sensitive user data for inference, necessitating the complete set of features. This not only poses significant privacy risks for individuals but also demands substantial human effort from organizations to verify information accuracy. This paper asks whether is necessary use all input features for accu- rate predictions at inference time. The paper demonstrates that, in a personalized setting, individuals may only need to disclose small subset of their features with- out compromising decision-making accuracy. The paper also provides an efficient sequential algorithm to determine the appropriate attributes for each individual provide. Evaluations across various learning tasks show that individuals potentially report as little as 10% of their information while maintaining the same accuracy level model that employs the full set of user information.
Introduction
The remarkable success of machine learning (ML) models also brought with it pressing challenges the interface of privacy and decision- decision-making.. mnaking.especingg when deployed in consequential domains such legal processes, banking. hiring, and healthcare (23). A particularly intriguing aspect the conventional requirement for users to disclose their entire set of features during inference, thereby creating gateway for potential data breaches, as exemplified in recent instances where millions of individuals' data were compromised []. Concurrently, this practice also places a burden companies and organizations to ensure the accuracy and legal compliance of the disclosed information, often observed in financial operations, mandated by legislations like the Corporate Transparency Act[].
Significantly, this conventional approach of disclosing the enture feature during inference might also also violate the data minimization principle, comnrrtone of several global privacy regulations including the Eurpean General Data Protection Regulation 22] the California Privacy Rights Act M. and the Brazilian General Data Protection Law [3]. among others. Through this lens, the discourse on enhancing privacy and reducing the verification onus ML systems, particularly in crucial decision-makin domains, gains nuanced dimension, warranting a thorough examination.
This paper challenges this setting and asks whether it is necessary require all input features for model to produce accurate or nearly accurate predictions during inference. We refer to this question the data minimization for inference problem. This unique question bears profound implications for privacy in model personalization, which often necessitates the disclosure of substantial user data. We show that, under a personalized setting, each individual may only need release small subset of their features to achieve the same prediction errors as those obtained when all features are disclosed. The overall framework is depicted in Figure I Following this result, we also provide an efficient sequential algorithm to identify the minimal set of attributes that each individual should reveal. Evaluations across various learning tasks indicate that individuals may be able to report as little as 10% of their information while maintaining the same accuracy level as model using the complete set of user information.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

At inference time
Trained Model
data minimization
fo
representatiive
label
Core festure set (R)
Figure 1: Illustrative example of the proposed framework. The figure higlights the online and personalized nature of the minimization process. For each user, a key subset of features is identified to be used (core feature set). The minimized data sample is then processed by the pre-trained model, which generates a representative label.
In summary, the paper makes the following contributions: (1) it initiates study to analyze the optimal subset of data features that each individual should disclose at inference time in order to achieve the same accuracy as if all features were disclosed; (2) it links this analysis to a new concept of data minimization for inference in relation to privacy, (3) it proposes theoretically motivated and efficient algorithms for determining the minimal set of attributes each individual should provide to minimize their data; and (4) it conducts a comprehensive evaluation illustrating the effectiveness of the proposed methods in preserving privacy no or small costs in accuracy.
Related work. To the best of our knowledge, this is the first work studying the connection between data minimization and accuracy at inference time. This work was motivated by the core principle in data minimization which states that "all collected data shall be adequate, relevant and limited to what necessary in relation to the purposes for which they are processed". This principle adopted as privacy cornestone in different data protection regulations, including the General Data Protection Regulation 2 in Europe, the California Privacy Rigths Act in the US [1, the General Personal Data Protection Law in Brasil (3, the Protection of Personal Information Act, in South Africa [5], and the Personal Information Protection Act, in South Korea (4.
While we are not aware of studies on data minimization for inference problems, we draw connections with differential privacy, feature selection, and active learning. Differential Privacy (DP) 14 is a strong privacy notion that determines and bounds the risk of disclosing sensitive information of individuals participating in computation. In the context of machine learning. DP ensures that algorithms can learn the relations between data and predictions while preventing them from memorizing sensitive information about any specific individual in the training data. In such a context, DP is primarily adopted to protect training data (6 12 32) and thus the setting contrasts with that studied in this work, which focuses on identifying the superfluous features revealed by users at test time to attain high accuracy. Furthermore, achieving tight constraints in differential privacy often comes at the cost of sacrificing accuracy, while the proposed privacy framework can reduce privacy loss without sacrificing accuracy under the assumption of linear classifiers.
Feature selection 10 the process of identifying a relevant subset of features from larger set for use in model construction, with the goal of improving performance by reducing the complexity and dimensionality of the data. The problem studied in this work can be considered specialized form of feature selection with the added consideration of personalized levels, where each individual may use a different subset of features. This contrasts standard feature selection (20, which selects the same subset of features for each data sample. Additionally, and unlike traditional feature selection, which is performed during training and independent of the deployed classifier [10]. the proposed framework performs feature selection at deployment time and is inherently dependent the deployed classifier.
The framework proposed in this paper shares some similarities with active learning 1 26 [3],
whose goal is to iteratively select samples for experts to label in order to construct an accurate classifier with the least number of labeled samples. Similarly, the proposed framework iteratively asks individuals to reveal one attribute given their released features so far, with the goal of minimizing the uncertainty in model predictions. Finally, our study share some connections with active feature acquisition 228 13 21 which can be categorized as one branch in active learning. However, these priors focus mostly on minimizing the total number of users features at training step. This is in sharp contrast with ours work which concentrate inferece time.

---

2 Settings and objectives
We consider a dataset consisting of samples (a, y) drawn from an unknown distribution 11. Here, X' is feature vector and y E 3' [Z] is label with L classes. The features in categorized into public z and sensitive zs features, with their respective indexes in vector x denoted as P and S, respectively. We consider classifiers fo : X' + Y/ which are trained on public dataset from the same data distribution IT above. The classifier produces score fo(x) E TR_ over the classes and final output class, (a) E [4] given input æ. The model's outputs fo and fa( are also often referred to as hard and soft predictions, respectively.
Without loss of generality, we assume that all features in X' lie within the range [-1, 1]. In this setting, we are given a trained model fo and, at inference time, we have access to the public features x p. These features might be revealed through user queries collected by the provider during previous interactions. Our focus is on the setting where |S| < [D], and for simplicity, the following considers binary classifiers, where ) = {0. } and fo E R. Multi-clas classcccsss settings are addressed in Appendix C
In this paper, the term data leakage of model, refers to the percentage of sensitive features that are revealed unnecessarily, meaning that their exclusion would not sigmificantly impact the model's s output. Our goal is to design algorithms that accurately predict the output of the model using the smallest possible number of sensitive featurrs features, thus minimizing the data leakage at inference time. This objective reflects desire for privacy.
To clarify key points discussed in the paper, let us consider a loan approval task where individual features are represented by the set [Job, Loc(action), Inc(ome)). In this example, the Job feature E xp is public, whereas Loc and Inc E &g are sensitive. We also consider a trained linear model fe = Job 0.5 Loc + 0.5 Inc 0 and look at a scenario where user (A) has public feature Job = 1.0, and user (B) has public feature Job = -09.. Both users' sensitive feature values are unknown. However, for user A. the outcome can be conclusively determined without revealing any additional information since all features are bounded within [-1, 1]. In contrast, for user B, the outcome cannot be determined solely based on the public feature, but revealing the sensitive feature Loc 1.0 is enough to confirm the classifier outcome.
This example highlights two important observations that motivate our study: (1) not all sensitive attributes may required for decision-making during inference, and (2) different individuals may need to disclose different amounts and types of sensitive information for decision-making.
Core feature sets
With these considerations in mind, this section introduces the notion of core feature set, the first contribution of the paper, which will be used to quantify data minimization. The paper presents the key findings and defers all proofs in Appendix A
Throughout the paper, the symbols R and U are used to represent the sets of indices for revealed and unrevealed features of the sensitive attribute S, respectively. Given vector and an index set I, use F to denote the vector containing entries indexed by and X, to represent the corresponding random variable. Finally, we write Jo (Xu, xR= as shorthand for (Xu, XR - xR, X Xp=pp) to denote the prediction made by the model when the features in U are unrevealed.
Our objective is develop algorithums that can identify the smallest subset of sensitive features to disclose, ensuring that the model's output is accurate (with high probability) irrespective of the values of the undisclosed features. We refer to this subset the core feature set.
Definition 1 (Core feature set). Consider subset R of sensitive features S. and let U U= \ R be the unrevealed features. The set R is a core feature set if. for some I E V,
Pr (Jo(XOX X = Fn) = 5) 2 - 6.
where 8 [0, is a failure probability
When 8 = 0 the core feature set is called pure. Additionally, the label ÿ satisfying Equation T is called the representative label for the core feature set R. The concept of the representative label y is crucial for the algorithms that will be discussed later. These algorithms use limited information to
3

---

make predictions and when predictions are made using a set of unrevealed features, the representative label y will be used in place of the model's prediction.
In identifying core feature sets to minimize data leakage, it's crucial to consider model uncertainty, which refers to the unknown values of unrevealed features. The following result links core feature sets with model entropy, which measures uncertainty and is used by this work to minimize data leakage.
Proposition 1. Let R S be a core feature set with failure probability 6 < 0.5. Then, there exists monotonic decreasing function 6 114 - RR with c(1) = 0 such that:
H (o Xx œл)] - c(1 5),
where -07]=-Eveepg Pr(Z = 2) log Pr(Z- 2) the entropy of the random variable Z.
This property highlights the relationship between care feature and entropy associated with model using incomplete information. As the 8 value decreases, the model's s predictions become more certain. When equals zero (or when Rt represents a pure core feature set), the model's predictions can be fully understood without observing IV, resulting in entropy of O.
It is worth noticing that enhancing prediction accuracy necessitates revealing additional information, as illustrated by the previous result and the renowned information theoretical proposition below: Proposition 2. Given two subsets R and I'' of sensitive features S, with R S It'
(X,, zR)) 2 H (fo(Xu), Xx = 2g )),
where U S \ and U' S
Cumulative frequency
1.0
Thus, the parameter plays crucial role in balancing the trade-off between privacy loss and model prediction's 's un- certainty. It determines the amount of sensitive information that must be disclosed to have enough confidence on model predictions. As 8 increases, fewer sensitive features need to be revealed, resulting in reduced data leakage but also less certainty model predictions, and vice versa. Note that disclosing more sensitive attributes does not necessarily improve the accuracy of predictions for specific individual, as highlighted in previous research (30]. Although it's chal-
0.5
0.0
0
2
4
6
Min pure core feat set set size Figure 2: Frequency associated with the size of the minimum pure core feature set.
lenging rigorously analyze the relationship between privacy loss and predictive accuracy across various contexts, our empirical studies across multiple datasets and learning algorithms do suggest that exposing more sensitive features generally enhances prediction accuracy. Thus, the parameter d appears to govern the trade-off between sacrificing privacy and gaining predictive performance.
As highlighted in the previous example, the core feature set is not uniform for all users. This is further exemplified in Figure using the Credit dataset ( with a logistic regression classifier. The figure reports the cumulative count of users against the minimum number of features they need to disclose to ensure confident predictions. demonstrates that many individuals need disclose no additional information to attain accurate predictions (corresponding to a pure feature of set size 0), and most individuals can achieve accurate predictions by disclosing only S 2 sensitive features. These insights, together with the previous observations linking core feature sets to entropy, motivate the proposed online algorithm, the second contribution of the paper.
4 MinDRel: An algorithm to minimize data release at inference time
The goal of the proposed algorithm, called Minimize Data Reveal (MinDRel), is to uphold privacy during inference by revealing sensitive features one at a time based on their released feature values. This section provides high-level description of the algorithm and outlines its challenges. Next, Section 5 applies MinDRel to linear classifiers and discusses its performance on several datasets and benchmarks. Further, Section 6 extends MinDRel non-linear classifiers and considers an evaluation over a range standard datasets.
Overview of MinDRel. MinDRel operates fundamentally on two critical actions: 1. determining the next feature to reveal for each user and 2. verifying whether the disclosed features make up a core feature set for that user. These two operations will be discussed in sections and 4.2 respectively.

---

The algorithm determines which feature to disclose for specific user by inspecting the posterior probabilities Pr - = xp) for each unrevealed feature j E U, taking into account the disclosed sensitive features n and public features p. Given the current set of disclosed features nn and unrevealed features zV, MinDRel chooses the subsequent feature j E U as follows:
j argmax F J3 8) = argmax jEU
[fo I.. Xa zT)].
(2)
jeU
where F' is a scoring function that evaluates the amount of information that can be acquired about the model's predictions when feature Xj is disclosed. As suggested in previous sections, it's desirable to reveal the feature that provides the most insight into the model prediction upon disclosure. MinDRel uses Shannon entropy for this purpose as it offers a natural method for quantifying information. Once feature Xj is disclosed with value of zy, the algorithm updates the posterior probabilities for all remaining unrevealed features. The process concludes either when all sensitive features have been disclosed or when a core feature set has been identified. should also be noted that, within this framework, there is no need to perform data imputation when some features are missing. Unrevealed features are treated as random variables and are integrated during the prediction process.
Both the computation of the scoring function E' and the verification of whether set of disclosed features constitute core feature set present significant challenges for the algorithm. The rest of the section delves into these difficulties.
4.1 Computing the scoring function
Designing scoring function F that measures how confident model's prediction is when user discloses an additional feature Xj brings up two key challenges. First, the value of X, is unknown until the decision to reveal it is made, which complicates the computation of the entropy function. Second, even if the value of Xj were known, determining the entropy of model predictions in an efficient manner is another difficulty. We next discuss how overcome these challenges.
Dealing with unknown values. To address the first challenge, we exploit the information encoded in the disclosed features to infer X, 's value and compute the posterior probability Pr(X,) XX =IR) of the unrevealed feature X, given the values the revealed ones. The scoring function, abbreviated as F(X,), can thus be modeled the expected negative entropy given the randomness of Xj.
F(X,) Ex,- [X] XUMu X æR)
f H [f =2 XUNu), Xxn X
Pr(X, = = 2|xa RR) dz,
(3)
where z E X, is a value in the support of Xj.
Efficient entropy computation. The second difficulty relates to how to estimate this scoring function efficiently. Indeed this challenged by two key components. The first (A) is the entropy of the model's prediction given specific unrevealed feature value, X, 2. This prediction is function of the random variable XUyer. and, due to Proposition [] its estimation is linked to the conditional densities Pr(Xu [R = ZR. X2 = 2). The second (B) the conditional probability Pr(X, = = x| R). Efficient computation of these conditional densities is discussed next.
First, we discuss result relying on the joint Gaussian assumption of the input features. This result will be useful in providing computationally efficient method to estimate such conditional density functions. In the following, Σn represents a nub-matrix of size [ x [J] of a matrix Σ formed by selecting rows indexed by and columns indexed by J.
Proposition 3. The conditional distribution of any subset of featuress U C given the the values of released features XR = IR is given by:
Pr(Xur IR) -N( -N(1N) (ver R
PR), Eggu- EV'R 2 RU
where Σ is the covariance matrix.
Note that Equation 3 considers U (j), and thus, component (B) can be computed ef- ficiently exploiting the result above. To complete Equation 3), we need to estimate the
5

---

entropy H[ = 2, Pr(X,[XR==za) This poses challenge due to the non non-linearity of the hard model predictions fa adopted. To tackle this computational challenge, we first estimate component A using soft la- bels fo and then apply thresholding operator. More specifically, we first estimate Pr(fo =2,
(component A) for specific instance 2 drawn from
((x and, based on this distribution, we subsequentially estimate fo as 1 2 0}. where 1 is the indicator function. In the following sections, we will show how to assess this estimate for linear and non-linear classifiers. Finally, by approximating the distribution over soft model predictions through Monte Carlo sampling, the score function in F(X,) can be computed as
F(X) ~ - 1/21 Σ H [Jo[X ,, Xoxo6n XR= mg)]
z'EZ
where Z is set of random samples drawn from Pr(X, zR) and estimated through Proposition 3 which thus can be computed efficiently.
When the Gaussian assumption does not hold, one can recur to (slower) Bayesian approaches to estimate the uncertainty of unrevealed features X given the set of revealed features X zR- common approach involves treating Xu as the target variable and employing a neural network to establish the mapping Xy = Iw (XR). Utilizing Bayesian techniques [17] 18). the posterior of the network's 's parameter p(w) w D) = p(w)p(( D w) can be computed initially. Based on the posterior distribution of the model's ' parameters w, the posterior of unrevealed features can be calculated as = zτ). However, implementing such Bayesian network not only significantly increases training time but also inference time. Since it is necessary
Pr(Xe= = zy Xx = xrt Pr Prw-p(w) D)
to compute Pr(Xu XR = IR) for all possible choices of U E S, the number of Bayesian neural network regressors scales exponentially with (S].
Accuracy
Data Leakage
0.220
Importantly, in our evaluation, the data mini-
Bayesian NN
Bayesian MN Gaussian
mization method that operates under the Gaus- sian assumption maintains similar decision- making and produces comparable outcomes to the Bayesian approach, even in cases where the Gaussian assumption is not applicable in practi- cal settings. Figure 3 illustrates this comparison, showcasing the performance of the proposed mechanism on a real dataset (Credit dataset with
0.225
Gaussian
0.5
0.4
0.30
0.2
0.
0.800
0x
6-87
8-82
Figure 3: Comparison between Bayesian NN vs Gaus- sian in term of accuracy and data Lekage.
[S] = 5) concerning accuracy (higher is better) and data leakage (lower is better) across various failure probability 8 values. Notice how similar is the performance of the mechanisms that either leverage the Gaussian assumption or operate without it (Bayesian NN). Importantly, the assumption of a Gaussian distribution is not overly restrictive or uncommon. In fact, is a cornerstone in many areas of machine learning, including Gaussian Processes 31,, Bayesian optimization [27]. and Gaussian Graphical models 24).
4.2 Testing a core feature set
The proposed iterative algorithm terminates once it determines whether a subset of the sensitive feature set S constitutes a core feature set. This validation process falls into two scenarios:
When 8= To confirm that is a pure core feature set, it is sufficient to verify that fo(X XR= 1.
RR) remains constant for all possible realizations of Xv. As we will show in Section 5 linear classifiers can perform this check in linear time without making any specific assumptions about the input distribution.
2. When d >>0 0: In this case, the property above is no longer valid. As per Definition I to confirm a
core feature set, it is essential to estimate the distribution of Pr(fo Xn xR)). ). In Section 5
we demonstrate how to analytically estimate this distribution for linear classifiers. Furthermore, in Section 6 we illustrate how to locally approximate this distribution for nonlinear classifiers and derive a simple yet effective estimator that can be readily implemented practice.
5 MinDRel for linear classifiers
This section will devote to estimating the distribution expressed as Pr(fo(Xu X =xR)) and provides an instantiation of MinDRel for linear classifiers.
simply

---

In particular, it shows that both the estimation of the conditional distributions required to compute the scoring function F)X;) and the termination condition test whether a set of revealed features is core feature set, can be computed efficiently. This is an important property for the developed algorithms, which are designed to be online and interactive.
5.1 Efficiently Estimating X IR))
For linear classifier fo A x, notice that when the input features are jointly Gaussian, the model predictions fz) are also Gaussian, as highlighted by the following result.
Proposition 4. The model soft prediction, fo XR xR) Ou 0RR a random variable following Gaussian distribution N (m,, 07), with
m = R 0g (nD + LUR MR)) of = 0 (Evu )
(5)
(6)
where Oy is the sub-vector of parameters 0 corresponling to the unrevealed features U.
The result above is used to assist in calculating the conditional distribution of the model hard predictions fz))), following thresholding. This is random variable that adheres to a Bernoulli distribution, as shown next, and will be used compute the entropy of the model predictions, as well as to determine if subset of features constitutes core set.
Proposition 5. Let the soft model predictions (X XR= = IR) be a random variable following a Gaussian distribution N [m,, of). Then, the model prediction following thresholding fo X RR) a random variable following a Bernoulli distribution B(p) with p 4b mi) where $(.) is the CDF of the standard Normal distribution, and my and j, are given in Eqs (5) and (6), respectively.
5.2 Testing pure core feature sets
In this subsection, we outline the methods for determining if subset U is pure core feature set, and, if so, identifying its representative label. As per Definition is a pure core feature set (X, = πR) = ÿ for all Xu. This implics that (Xu, XR = σR) = 0f + 0 must have the same sign for all Xy in the range of [-1, 1 Given the box constraint Xy E 1-1, 1] the linearity of the model considered allows to directly compute the maximum and minimum
values of fo (Xu, Xn æn), rather than enumerating all possible values. Specifically, have:
max max fu 0H ||0 11 0
X
min min o X = -10 || + 0 Xu
Thus, if both these maximum and minimum values are negative (non-negative), then is considered pure core feature set with representative label ÿ 0 1). If not, U is not a pure feature set.
Importantly, determining whether a subset R of sensitive features constitutes a pure core feature set can be accomplished in linear time with respect to the number of features.
Proposition 6. Assume fo is a linear classifier. Then, determining if a subset U sensitive featurre S is a pure core feature set can be performed in O(IPI + |S]) time.
5.3 MinDRel-linear Algorithm and Evaluation
pseudo-code of MinDRel specialized for linear classifiers reported in Algorithm T time, the algorithm takes input sample æ (which only exposes the set of public features x)) and uses the training data D to estimate the mean and covariance matrix needed to compute the conditio-
At inference
nal distribution of the model predictions given the unrevealed features (line 1). as discussed above. After initializing empty the set of revealed features (line 2), it iteratively releases a feature at a time until a core feature set (and its associated representative label) are determined, as discussed in detail in Section 5.2 The released feature X,- is the one, among the unrevealed features U, that maximizes the scoring function F (line 12). Computing such scoring function entails estimating the conditional
7

---

distribution Pr(X,|Xx= = 2R) (line 8), constructing sample set Z from such distribution (line 9), and approximating the distribution over soft model predictions through Monte Carlo sampling to compute (line 10). Finally, after each iteration, the algorithm updates the set of the revealed and unrevealed features (line 13).
Notice that MinDRel relies on estimat- ing the mean vector and covariance ma- trix from the training data, which is con- sidered public, for the scope of this pa- per. If the training data is private, vari- ous techniques exist release DP mean,
Algorithm 1: MinDRel for linear classifiers
input :A test sample æ; training data /)
output:A A core feature set R and its representative label Ø
(1, Σ) - ( (h) ((EWED 2, jd] Elawre -n)(z (1)
Initialize R =
and variance (22) and can be readily adopted. Nonetheless, the protection of training data is beyond the focus of this work.
while True do if R. a core feature set with repr. label ÿ then return (Rt, 5)
else
foreach j U do
Figure reports the cumulative count of users (y-axis) against the minimum number of features they need to disclose (X-axis) ensure confident predictions, for various failure probabilities 8. The 11 model adopted is a Logistic Regression classifier trained
Compute Pr(X, X, X zR) (using Prop 3
t sample
X mR)) T times
Compute Pr
(X 2, XevG) xn))
(using Prop
and
Compute F (X,) (using Eq. 4
the Bank dataset 12 i +- argmax, F(X,)
[ The data minimization achieved by MinDRel is clearly apparent. For each test sample, MinDRel identifies core feature sets that are significantly smaller than the total sensitive feature set size |S| 7. Interestingly, when 6 > O, it discovers core feature sets smaller than 2 for majority of users. This implies that most users would only need to reveal small portion of their sensitive data to achieve accurate model predictions with either absolute certainty or high confidence.
(R. +
6 MinDRel for non-linear classifiers
Cumulative frequency
MinDRel
1.0
Next, the paper focuses on computing the estimate Pr(Jo(Xy, Xn = and determining core feature sets when fo a nonlinear classifier. Then, the section presents results that illustrate the practical benefits of MinDRel for data minimization at inference time on neural networks.
0.5
6=0
5=0.1
6=0.2
0.0
6.1 Efficiently estimating Pr(fo(Xu. Xn. Fn))
6
Core feature set size Figure 4: Cumulative count of against their care feature set size various
First notice that even if the input features x are jointly Gaussian, the outputs fa( will longer adhere to Gaussian distribution after a non-linear transformation. This complicates estimating the distribution Pr(fo Xn= RR) To tackle this challenge, the paper takes local approximation of the model predictions fo using Gaussian distribution, as demonstrated in the following result.
Theorem 1. The distribution of the random variable fo fo(Xu, XR 2R) where Xu ( pos >oo) can be approximated by a Normal distribution as
jo N (Fo(Xu
1~N(Fooxs = -u
pos .R 2R), g0 pos 90).
pos X xn) is the grudient of model prediction at X 1ey where gu Vx = Pi
pos
Therein, the mean vector Py pos and covariance matrix xos of |r((x] are derived from Proposition 3
This result leverages first-order Taylor approximation of model fo around its mean.

---

6.2 Testing pure core feature sets
Unlike linear classifiers, the case for nonlinear models lacks an exact and efficient method to determine whether set is a core feature set. This is primarily due to the non-convex nature of the adopted models, which poses challenges in finding a global optimum. This section thus proposes an approximate testing routine and demonstrates its practical ability to significantly minimize data leakage during testing while maintaining high accuracy.
To determine if a subset U of the sensitive features S is a pure core feature set, we consider a set Q of input points &R). The entries corresponding to the revealed features are set the value TR, while the entries corresponding to the unrevealed features are sampled from the distribution Pr(Xu>XXR = æR). The test verifies if the model predictions (ax remain constant for all in Q. In the next section, we will show that even considering arbitrary classifiers (e.g., we use standard neural networks), MinDRel can reduce data leakage dramatically when compared standard approaches. The MinDRel algorithm for nonlinear classifiers differs from Algorithm primarily in the method used to compute the estimates for the distribution Pr(fo(X; = 2, X Xn = IR)) of the soft model predictions (line 11). In this case, this estimate is computed by leveraging the results from Theorem [ and Proposition [5] Moreover, the termination test of the algorithm is based on the discussion in the previous section. BipendixxBrrppoonee a description of the algorithm's 's pseudocode.
7 Experiments
Datasets and settings. This section evaluates MinDRel's effectiveness in limiting data exposure during inference. The experiments are conducted on six standard UCI datasets [9]. To further emphasize the benefits of MinDRel, we compare it two baselines: the optimal model, which employs a brute force method to find the smallest core feature set and its representative label and assumes all sensitive features are known, and the all-features model, which simply adopts the original classifiers using all the data features for each test sample. The performances are displayed for varying number of sensitive attributes |S] E [2. 5]. while we delegate a study for larger [S] to the Appendix (which excludes the time-consuming baseline optimal, as intractable for large |S'). For each choice of [S], we randomly select [S] features from the entire feature set and designate them as sensitive attributes. The remaining attributes are considered public. The average accuracy and data leakage are then reported based on 100 random sensitive attribute selections. Due to page limit, we present a selection of the results and discuss their trends Bank dataset. A comprehensive overview, additional analysis, and experiments are available in the Appendix D
7.1 Linear classifiers
Opt
feaures
WinORe (833.)
MirDRwiS-02 022)
F-Score
Importance
Random
Figure 5 depicts performance results in accuracy (top subplots/higher is bet- ter) and relative data leakage (bottom subplots/lower is better) with varying number of revealable sensitive fea- tures |S]. The comparison includes three MinDRel versions: P-Score, which utilizes the scoring function elaborated in Section Ioo select the next feature to disclose (left); Impor- tance, which employs feature impor- tance criterion leveraging the model fe parameters to rank features (mid- dle), detailed in the Appendix; and Random, which arbitrarily selects the next feature to reveal (right). All three versions use the same test procedure to validate whether a set qualifies as a core feature set.
0.80
Accuracy
0.79
0.78
10a
Data Leakage
10
10
Sensitive Features Sensitive Features Sensitive Features
Figure 5: Comparison of F Score, Importance and Random method for different 5 with two baseline methods: Optimal and All features in term of Accuracy and Data Leakage. The underlying classifier a logistic regression classifier.
Firstly, notice that MinDRel achieves equal or better accuracy than the optimal mechanism and baseline that utilizes all features during testing. This suggests that data minimization can be accom- plished under linear models without compromising accuracy! Next, observe that an increase in 8

---

aids in safeguarding data minimization, as evidenced by the drop in relative data leakage (note the logarithmic scale of the y-axis). This is attributable to the influence of ó on the test for identifying a core feature set, thereby reducing its size.
Finally, the proposed scoring function outperforms other versions in terms of data leakage minimiza- tion, allowing users to disclose substantially fewer sensitive features. The Appendix also includes experiments with larger quantities of sensitive features, presenting analogous trends, where, however, a comparison against an optimal baseline was not possible in due to its exponential time complexity.
7.2 Non-linear classifiers
Opc
fexures
MinOHo (5-0.1)
MinDReld-00 2)
To assess MinDRel's performance in reducing data leakage when employ- ing standard nonlinear classifiers, we use neural network with two hidden layers and ReLU activation functions and train the models using stochastic gradient descent (see Appendix for additional details). The evaluation cri- teria, baselines, and benchmarks ad-
0.84
F-Score
Importance
Random
Accuracy
0.88
0.82
0.81
109
Data Leakage
here to the same parameters set in Sec-
10-1
tion 5.3
Figure showcases the results in terms of accuracy (top subplots) and data leakage (bottom subplots). Un- like linear classifiers, nonlinear mod- els using MinDRel with failure prob- ability of 8 = 0 cannot guarantee the same level of accuracy the "all features" baseline model. However, this accuracy difference is minimal. Notably, a failure probability of 5 O enables users to disclose less than half, and up to 90% fewer sensitive features across different datasets, while achieving accuracies similar those of conventional classifiers. Next, similarly to as observed in the previous section, MinDRel with the proposed F-score selector significantly outperforms the other variants in terms of data leakage minimization. Furthermore, when considering higher failure probabilities, data leakage decreases significantly. For instance, with 0.1, users need to disclose only 5% of their sensitive features while maintaining accuracies comparable to the baseline models (the largest accuracy difference reported was 0.005%). These results are significant: They show that the introduced notion of privacy leakage and the proposed algoritium can become a valuable tool to protect individuals' data privacy at test time, without significantly comprom compromising accuracy.
Sensitive Features Sensitive Features Sensitive Features
Figure 6: Comparison of F Score, Importance and Random method for different ó with two baseline methods: Optimal and All features in term of Accuracy and Data Leakage. The underlying classifier a neural network.
Conclusion and Future Work
This paper introduced the concept of data minimization at test time whose goal is to minimize the number of features that individuals need to disclose during model inference while maintaining accurate predictions from the model. The motivations of this notion are grounded in the privacy risks imposed by the adoption of learning models in consequential domains, and align with the data minimization principle. The paper then discusses an iterative and personalized algorithm that selects the features each individual should release with the goal of minimizing data leakage while retaining exact (in the case of linear classifiers) or high (for non- non-lincar classifiers) accuracy. Experiments over range of benchmarks and datasets indicate that individuals may be able to release as little as 10% of their information without compromising the accuracy of the model, providing a strong argument for the effectiveness of this approach in protecting privacy while preserving the accuracy of the model.
While this study is the first attempt at defining data minimization during inference, it also opens up avenues for further research. First, establishing bounds on the data leakage provided by our proposed method compared to an optimal procedure presents an interesting and open challenge. Second, exploring the relationship between data minimization principles and their consequent disparate impacts presents another open direction. Lastly, developing effective algorithms to provably construct core feature sets for non non-linear classifiers is another important area of investigation.
10

---

Acknowledgements
This research was partially supported by NSF grant 2133169, a Google Research Scholar Award and an Amazon Research Award.
References
[1] California privacy rights act. lattps://cpa..a. gov/
Accessed: 2023-10-23.
[2] General data protection regulation. setpp:///dpp-innft eu/
Accessed: 2023-10-23.
[3] General personal data protection law.
[4] Personal information protection act. htttps:/ klri. re. do7hssegs5304441nng-- Eng Accessed: 2023-10-23.
[5] Protection of personal information act. https://popia..oo.zz Accessed: 2023-10-23.
[6] Abadi and al. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016.
[7] K. Amin, T. Dick, A. Kulesza, A. Munoz, and S. Vassilvitskii. Differentially private covariance estimation. Advances in Neural Information Processing Systems, 32, 2019.
[8] C. M. Bishop and N. M. Nasrabadi. Pattern recognition and machine learning, volume Springer, 2006.
[9] C. Blake and C. Merz. Uci repository of machine learning databases, 1988.
[10] G. Chandrashekar and F. Sahin. A survey on feature selection methods. Computers & Electrical Engineering, 40(1):16-25 2014.
[11] C.-H. Chang, M. Mai, and A. Goldenberg. Dynamic measurement scheduling for event forecasting using deep rl. pages 951-960, 2019.
[12] K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk mini- mization. Journal of Machine Learning Research, 2011.
[13] G. Contardo, L. Denoyer, and T. Artières, Sequential cost-sensitive feature acquisition. pages 284-294, 2016.
[14] C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284, Springer, 2006.
[15] Y. Fu, X. Zhu, and B. Li. survey on instance selection for active learning. Knowledge and information systems, 35(2):249-283, 2013.
[16] A. Krause and C. Guestrin. A note the budgeted maximization of submodular functions. Citeseer, 2005.
[17] R. Krishnan, P. Esposito, and M. Subedar. Bayesian-torces Bayesian neural network layers for uncertainty estimation, Jan. 2022.
[18] R. Krishnan and O. Tickoo. Improving model calibration with accuracy versus uncertainty optimization. In Advances in Neural Information Processing Systems, volume 33, pages 18237-18248, 2020.
[19] Larxel. Children fetal health dataset. httpss//wwww..gggg..oo/aaaatttts fetal- classification 2021.
[20] J. Li, K. Cheng, S. Wang, F. Morstatter, R. P. Trevino, J. Tang, and H. Liu. Feature selection: A data perspective. ACM computing surveys (CSUR), 50(6): 2017.
[21] Y. and Oliva. Active feature acquisition with generative surrogate models. pages 6450- 6459, 2021.

---

[22] X. Liu, W. Kong, S. Kakade, and S. Oh. Robust and differentially private mean estimation. Advances neural information processing systems, 34:3887-3901, 2021.
[23] N. Papernot, P. McDaniel, A. Sinha, and M. Wellman. Towards the science of security and privacy in machine learning. arXiv preprint 1rXiv:1611.038/1 2016.
[24] C. Peterson, F. C. Stingo, and M. Vannucci. Bayesian inference of multiple gaussian graphical models. Journal of the American Statistical Association, 110(509):559-774, 2015.
[25] S. Roy. Car insurance data.
car- insurance-daaa 2021.
[26] B. Settles. Active learning literature survey. 2009.
[27] B. Shahriari, K. Swersky, Z. Wang, R. P. Adams, and N. De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1): 148)):444-77, 2015.
[28] H. Shim, S. J. Hwang, and E. Yang. Why pay more when you can pay less: A joint learning framework for active feature acquisition and classification. arXiv preprint 170.v0/709.05964 2017.
[29] A. Sudarshan. Customer segmentation data.
abisteessudarrahanccuttttt costonenncstteerrrro www.romtrteeeeenetttiio.oom 2021.
[30] B. Ustun, Y. Liu, and D. Parkes. Fairness without harm: Decoupled classifiers with preference guarantees. In International Conference on Machine Learning, pages 6373 6382. PMLR, 2019.
[31] C. K. Williams and C. E. Rasmussen. Gaussian processes for machine learning, volume MIT press Cambridge, MA, 2006.
[32] L. Xie, K. Lin, S. Wang, F. Wang, and J. Zhou. Differentially private generative adversarial network. arXiv preprint #rXv::/802.0673. 2018.
[33] S. Yu, B. Krishnapuram, R. Rosales, and R. B. Rao. Active sensing. pages 639-646, 16-18 Apr 2009.
12

---

A Missing proofs
Proposition Given core feature S failure failure probability d 0.5, then there exists function : IR + R that is monotonic decreasing function with e(1) = 0 such that:
H [ XR = =R)] S <(11-)) - 8),
where =1z]=-Eae11 Pr(Z=)) log Pr(Z 2) is the entropy of the random variable Z.
Proof. In this proof, we demonstrate the binary classification case. The extension multi-class scenario can be achieved through a similar process.
By the definition of the core feature set, there exists representative label, denoted as {0, 1} such that the probability of (Xf, = πR) ) = y) is greater than or equal to 1 - 8. Without loss of generality,
assume that the representative label is 1. Therefore, if we denote Z as the probability of Pr(fo(XX (Xu, X = FR) = 1). then the probability of (X, = ØR) = 0) = Z. Additionally, we have Z 2
> 0.5 due to the definition of core feature set 0.5. The entropy of the model's prediction can be represented as: and by the assumption that <
H [Xo,Xu, Xn =n)] - log Z (1 2) log(1 2).
Choose (() = -Z log 2 - (1 2) log(1 - Z). The derivative of c(Z) is given by de(2)
dz
log 1-2 < 0, as Z > 0.5. As a result, <Z)) is a monotonically decreasing function, so c (Z) I
<1 5)
When ò 0, we have Z = 1, and by the property of the entropy H [Xu XR = xR)] 0.
Proposition 2. Given two subsets R and R' of sensitive features S, with R C R',
( XR RR) 2 H(Jo(Xur, X IR))),
where U = S and U = S.AA R'.
Proof. This is due to the property that conditioning reduces the uncertainty, or the well-known information never hurts theorem in information theory [I6).
Proposition 3. The conditional distribution of any subset of unrevealed feattur U' E U, given the the values of released features Xn = I. is given by:
Pr(Xur|XR = IR) N -N(Mer  + En - pR), Errr - EU'R IR,0))
where E is the covariance matrix
Proof. This is a well-known property of the Gaussian distribution and we refer the reader to Chapter 2.3.2 of the textbook [ for further details.
Proposition 4. The model predictions before thresholding, (Xu, Xn xn) 0y + n is random variable with Gaussian distribution N (m,, (T), where
mf 0n O (po + FynERnla pn))
(8)
of = AT (Evv- E ) Ou.
where Og is the sub-vector of parameters 0 corresponding to the features U.
Proof. The proof of this statement is straightforward due to the property that linear combination of Gaussian variables Xy is also Gaussian. Additionally, the posterior distribution of X is already provided in Proposition
XR Proposition 5. Let the model predictions prior thresholding fo 6 = IR). be a random
variable following Gaussian distribution ( Then, the model prediction following thresh- olding fo fo(Xu. XR 2R) is random variable following Bernoulli distribution Bern(p) with ((Th ((LL))) where (-) refers to the CDF of the standard normal distribution, and m and o are
given in Equations
(5) and (6). respectively.
13

---

Proof. In the case of a binary classifier, we have fo(x) 1{f((x) 2 0}. If follows normal distribution, denoted f (m,,, of)) then by the properties of the normal distribution, f0 follows Bernoulli distribution, denoted as fo Bern(p), with parameter p Φ 07 where o(-) is the cumulative density function the standard normal distribution.
Proposition 6. Assume fe a linear classifier. Then, determining if subser U of sensitive features S is a pure core feature set can be performed in O(IPI + (S]) time.
Proof. As discussed in the main text, to if subset U core feature not, we need to check if the following two terms have the same sign (either negative or non-negative):
0 Xu + 0 RR = ||0 || 0R
max
Xu
(10)
min 0f 0f Xv + 0nE -100 + h.
Xu
These can be solved in time O(IPI + (S]) due to the property the linear equality above.
Theorem 1. The distribution of the random variable fo = folXu, Xn = xn) where Xu N pos EpOS) can be approximated by a Normal distribution as
fo ~ Nfo((X = =10
pos Xn Fn). 9ú 20 gu)
(11)
where gu = Xxu = 4 pos Xn = n) is the gradient of model prediction at Xu = poe
Proof. The proof relies on the first Taylor approximation of classifier f around its mean:
folNu, Xu= vR,) = fo(Xu- = pos Xx = FR) + (Xu - -10 (VPP))xxx
Vx, FolXu = P Xx = FR)
(12)
Since Xu N( (ops >:Dos) hence Xu 1er : distribution, the right-hand side of Equation 12) is linear combination of Gaussian variables, and it also Gaussian.
pos No, 2
poss) By the properties of normal
B Algorithms Pseudocode
The pscudocode for MinDRel for non-linear classifiers is presented in Algorithm 2 There are two main differences between this algorithm and the case of linear classifiers. Firstly, unlike linear classifiers, the procedure of pure core feature testing line 5 does not require the guarantee (see again Section 6.2). The accuracy of the testing procedures depends on the number of random samples that evaluate. The greater the number of drawn samples, the more likely the testing procedure is to be accurate. During experiments, we draw 10 samples to perform the testing. Additionally, use Theorem to estimate the distribution of the soft prediction as distribution cannot be computed analytically as in the case of linear classifiers.
line 11, the exact
C Extension from binary to multiclass classification
In the main text, provide the implementation of MinDRel for binary classification problems. In this section, we extend the method to the multiclass classification problem.
C.1 Estimating P(f = 2R))
In order to achieve our goals of determining if subset is a core feature set for given 8 > 0, and computing the entropy in the scoring function, we need to estimate the distribution of [x XR = xR). In this section, we first discuss the method of computing the distribution of fo(Nu, X2 xn) for both linear and non-linear models. Once this is done, we then address the challenge of estimating the hard label distribution P(f0( X XR = IR))-
It is important to note that, under the assumption that the input features X are normally distributed with mean μ and covariance matrix Σ, the linear classifier fo 0 will also have multivariate
14

---

Algorithm 2: MinDRel for non-linear classifiers
input :A test sample x; training data D
output:4 :A core feature set and its representative label y j [D E(a.tED
E < [Di L(aueED( - 10 - p)
Initialize R R=
while True do
a core feature set with repr. label then return (R, D)
else
foreach j E U do
Compute Pr(X,|XR RR) (using Prop. 3
10
Z sample(Pr(X,)) XR 2R)) T times
Compute Pr (Jo(X, = u) xn)) using Theorem
Compute F(X,) (using Eq. 4
j argmax, F(X;)
R RU (j* U+U U U
15
normal distribution. Specifically, if Xu NNt nos - then fo(Xu, IR) N(0 Tfr pos , 200)
For non-linear classifiers, the output (X XR = ZR) not Gaussian distribution due to the non-linear transformation. To approximate it, we use Theorem ] which states that the non- non-linear function fXu, Xn nn can be approximated as multivariate Gaussian distribution.
Challenges when estimating P(f XR = zR)). For multi-class classification problems, the hard label fo (Xu, Xx = FR) obtained by selecting the class with the highest score, which given by (r fá(N,, = IR). However, due to the non-analytical nature of the argmax function,
when fo(Nu, Xn .R) follows Gaussian distribution, the distribution of fo(Xu, Xn = Fn) cannot be computed analytically. To estimate this distribution, we resort to Monte Carlo sampling. Specifically, we draw a number of samples from P(fo(Xu, X = æR)), and for each class y E y we approximate the probability P(fe (Xu XR = IR) y) the proportion of samples that fall in that class y.
We provide experiments of MinDRel for multi-class classification cases in Section D.5
D Experiments details
Datasets information. To show the advantages of the suggested MinDRel technique for safe- guarding feature-leved privacy, employ benchmark datasets in experiments. These datasets include both binary and multi-class classification datasets. The proposed method was evaluated on the following datasets for binary classification tasks:
Bank dataset 9.. The objective of this task predict whether customer will subscribe to a term deposit using data from various features, including but not limited to call duration and age. There are total of 16 features available for this analysis.
2. Adult income dataset [9] more than $50,000 annually. After preprocessing the data, there total of 40 features available for analysis, including but not limited to occupation, gender, race, and age.
The goal of this task is to predict whether an individual earns
3. Credit card default dataset [9] The objective of this task is to predict whether a customer will default on a loan. The data used for this analysis includes 22 different features, such as the customer's age, marital status, and payment history.
15

---

4. Car insurance dataset [25]. The task at hand is to predict whether customer has filed claim with their car insurance company. The dataset for this analysis provided by the insurance company and includes 16 features related to the customer, such as their gender, driving experience, age, and credit score.
Furthermore, we also evaluate the proposed method on two additional multi-class classification datasets:
Customer segmentation dataset [29]. The task at hand to classify a customer into one of four distinct categories: A, B, C, and D. The dataset used for this task contains 9 different features, including profession, gender, and working experience, among others.
2. Children fetal health dataset [19]. The task hand is elassify the health of fetus into one of three categories: normal, suspect, or pathological, using data from CTG (cardiotocog- raphy) recordings. The data includes approximately 21 different features, such heart rate and the number of uterine contractions.
Settings. For each dataset, 70% of the data will be used for training the classifiers, while the remaining 30% will be used for testing. The number of sensitive features, denoted as [S), will be chosen randomly from the set of all features. The remaining features will be considered public. 100 repetition experiments will be performed for each choice [S], under different random seeds, and the results will be averaged. All methods that require Monte Carlo sampling will use 100 random samples. The performance of different methods will be evaluated based on accuracy and data leakage. Two different classifiers will be considered.
1. Linear classifiers: We use Logistic Regression as the base classifier.
2. Nonlinear classifiers: The nonlinear classifiers used in this study consist of a neural network with two hidden layers, using the ReLU activation function. The number of nodes in each hidden layer is set to 10. The network is trained using stochastic gradient descent (SGD) with a batch size of 32 and a learning rate of 0.001 for 300 epochs.
For Bayesian NN, we employ the package bayesian-tone torch [17 with the default settings. The base regressor is a neural network with one hidden layer that has 10 hidden nodes and a ReLU activation function. We train the network in 300 epochs with learning rate of 0.001.
Baseline models.
We compare our proposed algorithms with the following baseline models:
1. All features: This refers to the usage of the original classifier which asks users to reveal all sensitive features.
2. Optimal:
This method involves evaluating all possible subsets of sensitive features (2|$) in total) order to identify the minimum pure core feature set. For each subset, the verification algorithm is used to determine whether it is pure core feature set. The minimum pure core feature set that is found is then selected. It should be noted that all possible subsets are evaluated, all sensitive feature values must be revealed. Therefore, this approach is not practical in real-world scenarios. However, it does provide lower bound on data leakage for MinDRel (when 8 = 0).
important steps: (1) core feature set verification and (2) selection next feature to reveal. As additional baselines, we keep the core feature set verification and vary the selection process. We consider the following three feature selection methods:
MinDRel models. In MinDRel there
1. F-Score: We choose the feature based on the amount of information on model prediction gain after revealing one feature provided in Equation 3
2. Importance:
We reveal the unknown sensitive features based on the descending order of feature importance until we find core feature set. The feature importance is determined as follows. We firstly fit Logistic Regression fe(x) = 1(0" x 2 0} on the training dataset using all features (public included). The importance of one sensitive feature e S is determined by ||0, 2|2-
3. Random: We reveal the unrevealed sensitive feature random order until the revealed set is core feature set.
16

---

Almones
Optns
Alledess
PROMI
0.80
F-Sore
Importance
Rondom
0.945
Score
Importance
Pandom
0.844
0.843
0.78
10a
Datt (eatage
10-3
10-1
Data
10"
Sendtiive Features
Senoitive features
Sensitive Features
Sensttive Features
SensRtve features
SensRivve features
(a) Bank dataset
(b) Income datasct
#H00162m0.2
F-Sene
Importence
Bendom
1-Groee
lmm importance
Random
Accussi
0.8175
0.00
V
0.84
0.8165
Date tesbage
10-4
10-1
10-2
Sensitive Features
Sensttvve Features
Sensitive Features
Sensttive Features
Sensitive Features
SensRivve Features
(c) Credit datasct
(d) Insurance dataset
Figure 7: Comparison between using (left) proposed F-Score (left) with Importance (Middle) and Random (Right) for different choices of the number of sensitive features |S]. The baseline classifier Logistic Regression
Metries.
We compare all different algorithms in terms of accuracy and data leakage:
1. Accuracy. For algorithms that based the feature set, such MinDRel and Optimal, the representative label is used as the model's prediction. Again, the representative label for d = 0 can be identified using testing pure core feature procedures. For the representative label is given by ÿ argmax y P(f((Xu = xv, XR xR) y) P(Xu Xx xR)dz.. The accuracy is then determined by comparing this representative label the ground truth.
2. Data leakage. We compute the percentage of the number of sensitive features that users need to provide on the test set. Small data leakage is considered better.
D.1 Additional comparison between using Gaussian assumption and Bayesian NN
We first show empirically the benefits of our proposed Gaussian assumption compared to using Bayesian NN which allows more flexibility in modeling the conditional distribution P(Xu XX TR). We report both training and inference time between Bayesian NN and our Gaussian assumption on various datasets when the number of sensitive features |S] = 5 in Table and Table 2 When |S| = 5 the number of possible subsets U E S is 2 32 which requires training 32 Bayesian NN models. This will be especially slow for datasets with a large number of training samples (e.g., Income with 50K samples). In contrast, using Gaussian assumption just need to precompute 32 inverse matrices HR which is pretty fast for data that have small number of features (less than 50 in our experiments). It is noted again that in this paper we focus on the case when the number of training samples is much more than the number of features. Likewise, during inference time, with Gaussian assumption, can compute the distribution of model prediction in a closed form by simple matrix multiplication which takes (d2)) Instead, using Bayesian NN, requires expensive Monte Carlo sampling, especially when [U]] is large to obtain an accurate estimation of P(Xu X ZR).
17

---

Almores
PROMI
PM 2002
0.84
F-Sore
Importance
Rondom
Score
importance
Pandom
0..83
0.820
0.82
0.818
0.81
Dart (natage
Data
10"1
Sendtive Features
Senditive features
Sensitive features
Sensttive Features
SensRive features
SensRive features
Nnotel/b22))
Opasa
Alleates
F-Score
importance
Random
F-Scrre
importance
Pandom
0.835
0.842
0.840
Data Lestage
Dete
10-1
Sensdiive Faaitrmss
Sensdtive Peatunes
Sansiive Tealtres
Sansiiee Features
Sanadive Deatures
Samskion Peotures
(a) Income dataset
(b) Insurance dataset
Figure 8: Comparison between using (left) our proposed F-Score (left) with Importance (Middle) and Random (Right) for different choices of the number of sensitive features SS]. The baseline classifier
neural network classifier.
Method
Bank
Income
Credit
Insurance
Bayesian
204
375
125
90
Gaussian assumption
0.01
0.02
0.02
0.01
Table Comparison between using Bayesian neural network and our Gaussian assumption in terms of training time (minutes) when ISI = 5 for various datasets.
We also report the performance in terms of accuracy and data leakage between using Gaussian assumption and Bayesian NN in Figure 9 We see no significant difference in terms of accuracy and data leakage between two choices of modeling P(Xu Xx = æR). addition, as indicated above using the Gaussian assumption reduces significantly the training and inference time, in the subsequent experiments we will use the Gaussian assumption MinRDel with F-Score selection.
D.2 Additional experiments on linear binary classifiers
Additional experiments were conducted to compare the performance of MinDRel to that of the baseline methods using linear classifiers the Bank, Adult income, Credit, and Insurance datasets, as shown in Figure 7 As in the main text, consistent trend in terms of performance is observed.
Method
Bank
Income
Credit
Insurance
Bayesian NN
40
254
220
34
Gaussian assumption
15
78
66
9
Table 2: Comparison between using Bayesian neural network and Gaussian assumption in terms of inference time (minutes) on the test set when |S| = 5, = for various datasets.
18

---

MinDRekd-0)
MinDRe(6600.2)
MinDRel5-9)
MiDReell--22)
Sezzulu cocumation
Sunas WV
8445
20-1
2017
Sersfive Farures
Send Diee Reatures
Savotive ieatures
Songtive Festures
(a) Bank dataset
(b) Income dataset
MinDReliS-01
MIDORel6-0:11
MIDRRNIS-021
MinDRel(6-0.2)
Usanc on courppoe
BostslanhM
0.05
Gazzalen
Scpssion Me
0.8175
0.050
0.82
C40 Celuaabae
SSamiitee Poatures
Sersiive Peatures
Sersitno Poutunds
(c) Credit dataset
(d) Insurance dataset
Figure 9: Comparison between using Bayesian NN with Gaussian assumption in terms of (I): accuracy and (2) data leakage for different choices of the number sensitive features |S] on different datasets using Logistic Regression classifier.
As the number of sensitive attributes, [S], increases, the data leakage introduced by MinDRel with various values of 8 increases at slower rate. With different choices of [S], MinDRel (with 5 0) requires the revelation at most 50% of sensitive information. To significantly reduce the data leakage of MinDRel, the value of 5 can be relaxed. As mentioned in the main text, 5 controls the trade-off between accuracy and data leakage here. The larger is, the greater uncertainty the model prediction has, which implies the fewer sensitive features users need to reveal and the lower accuracy of the model prediction. By choosing an appropriate value for the failure probability, such as ō = 0.1, only minimal accuracy is sacrificed (at most 0.002%), while the data leakage can be reduced as low as 5% of the total number of sensitive attributes.
D.3 Additional experiments on non-linear binary classifiers
Additional experiments were conducted to compare the performance of MinDRel to that of the baseline methods using non-linear classifiers on the Bank, Adult income, Credit, and Insurance datasets, as shown in Figure 8 As seen, while the baseline All features method requires the revelation of all sensitive attributes, MinDRel with different values of 8 only requires the revelation of much smaller number of sensitive attributes. The accuracy difference between the Baseline method and MinDRel is also minimal (at most 2%). These results demonstrate the effectiveness of MinDRel in protecting privacy while maintaining good prediction performance for test data.
D.4 Sclability of MinDRel for large |S]
We demonstrate the performance of MinDRel when have a large number of sensitive features |S]. Note that to reduce the runtime we did not run the Optimal method which performs an exponential search over all possible choices of the subset of S.
first report the accuracy and data leakage MinDRel when using F-Score or using either two heuristic rules Importance and Random in the case of logistic regression classifiers in Figure I0
19

---

MrDRaRA-O)
Teaber
F-Score
Random
F-Score
Importance
Random
0.845
Accursty
Accuraty
0.79
0.040
10"
10"
Data Leakage
Dsta Laakage
10-1
10-1
10 Sensitive Features
10
Sensitive Festures
Sensitive Festures
Sensitive
Festures
Sensitive Festures
(a) Bank dataset
(b) Income dataset
features
Vachandeo
Importanc
F-Spore
Importance
Random
Accurary
0.815
Accuracy
0.84
0.810
10"
Dasa Laaloge
Data Laaloge
10-1
100-
10 15
10
15
10
10 *Sensitive Features
10 Sensitive Features
10 Sensitive Features
Senstivv Features
Sensitive Features
Sensitive Features
(c) Credit dataset
(d) Insurance dataset
Figure 10: Comparison between using (left) proposed F-Score (left) with Importance (Middle) and Random (Right) for different choices number sensitive features |S]. The baseline classifier is a logistic regression classifier.
Income
Bank
Insurance
Credit
101
rog Pred Time (StenSet
109
10a
10a
10a
10-1
10
Random
10
10
10:2
Importainc nce
Importance F-Scare
Importance
Importance
F-Scome
F-Score
10-2
F-Score
10-3
10
10
10-1
10-3
10
15
7.5
10.0 12.5
B Sensitive Features
10
12
10
15
Sensitive Features
Sensitive Features
Sensitive Features
Figure 11: Comparison in terms of average prediction time (seconds) among F-Score, Importance and Random method in MinDRel (5 for different [S].
Finally, we report the average testing time (in seconds) to get the model prediction per user of MinDRel in Figure IT It is noted that in this case, assume the time taken by users to release sensitive features is negligible. It is evident that when |S] > 15, our proposed MinDRel with F-Score take slightly more than I second to get the model prediction per user. This demonstrates the applicability of the models in practice.
D.5 Evaluation of MinDRel multi-class classifiers
Linear classifiers We also provide comparison of accuracy and data leakage between our proposed MinDRel and the baseline models for linear classifiers. These metrics are reported for the Customer and Children Fetal Health datasets in Figures 12a and 12b respectively. The figures clearly show
20

---

Albadess
PRO JOOD Adbal
Iniees
F.oore
Importance
Rondom
Score
importance
Pandom
0.91
Accraey
0.90
0.48
0.89
Dath Lnatage
Date tentage
10-1
19
19
15]
19
19
(a) Customer datasct
(b) Children fetal health dataset
Figure 12: Comparison between using our proposed F-Score (left) with Importance (Middle) and Random (Right) for different choices of the number of sensitive features |S]. The baseline classifier a multinomial Logistic Regression.
bokees
Peitie
Sptiral
porfancce
imprrtance
0.91
0.51
0.50
0.90
0.49
0.89
10a
10a
Dora Lentgg
Des
10
10
Sansétive Peatures
Sunsiivn Peatures
Sensativn Feuturns
Peatures
(a) Customer dataset
(b) Children fetal health dataset
Figure 13: Comparison between using our proposed F-Score (left) with Importance (Middle) and
Random (Right) for different choices of the number of sensitive features [S]. The baseline classifier is neural network classifier.
the benefits of MinDRel in reducing data leakage while maintaining a comparable accuracy to the baseline models.
Nonlinear classifiers Similarly, present comparison of proposed algorithms with the baseline methods when using non-linear classifiers. These metrics are reported for the Customer and Children Fetal Health datasets in Figures 3 0 results in a minimal decrease in accuracy, but significantly reduces
and 13b] respectively. The results show that using
MinDRel with a value the amount of data leakage compared the Baseline method.
E
Exetended Motivation
Finally, delve deeper into the motivational aspects underscoring our research. Our study primarily concerns tabular datasets where the total number of features is significantly outnumbered by the training samples. We concentrate on applications necessitating user-provided personal information for decision-making, such as lending, online insurance services, and healthcare services. The prevailing weaknesses of these applications, which our work attempts address, are outlined as follows:
The primary issue stems from the need for users to disclose sensitive information. For instance, in the context of online healthcare services, patients are required to share an array of sensitive health lata-weight, height, smoking habits, etc.-via website or mobile application. This exposes users to potential privacy threats.
Privacy Concerns:
21

---

2. User and Organizational Expenditure of Time and Effort: Numerous applications. such lending, involve the time-consuming and effort-intensive process of gathering sensitive information and its supporting evidence. Users, for example, are required to validate their income through payslips or employment contracts in lending applications. Similarly, the organization must invest time and resources to verify the authenticity of submitted documents.
3. Legal Constraints: According the EU General Data Protection Regulation's 's principle of data minimization, the collection of excessive personal information by companies and organizations is restricted. Our primary text illustrates that it is not imperative report all features to preserve the model's ' accuracy.
Inference Time. We also emphasize the importance of low inference time from both user and business perspectives. From the user's viewpoint, applications such as online car insurance require answering series of questions to determine the insurance plan. Naturally, users prefer answering fewer questions in the least amount of time. From a business standpoint, prolonged inference time may lead to customer dissatisfaction, potentially resulting in contract termination. This serves as the basis for our algorithmic choices, in lieu of more complex conditional distribution modeling methods, which can significantly increase inference time.
22


Reviews:
[{"review_id": "4EJTyJvZHq", "reviewer": "Reviewer_oWvc", "summary": "The work presents a method to increase privacy of ML predictions at test time by asking users to reveal fewer features. The proposed method asks for features that are maximally informative of the prediction outcome given the features seen thus far and stops when the prediction outcome can be decided. The method addresses the case of linear as well as non-linear thresholded classifiers assuming Gaussian-distributed features and a local Taylor approximation of predicted label probability. Experiments on multiple real datasets show reduction in data required for similar accuracy as baselines.", "questions": "Notation in Definition 1 is unclear. What does the probability of prediction f_\\theta mean for unobserved variables X_U? Do we take expectation over different values of X_U? An example of the meaning of this probability would help me.\nSimilarly, how are the unrevealed variables in entropy calculations, e.g. in term A of equation (3), handled?\n\nSuppose we remove all 5 of the sensitive features, does this have significantly lower accuracy? That is, does choosing the sensitive features matter at all for prediction.\n\nHow is entropy computed in equation 4? Please describe the Bayesian model used for the data.\n\nConsider adding the related work on following topics and discuss whether these are applicable to the problem setting. \nActive measurement of features e.g. Li and Oliva 2021 ‘Active Feature Acquisition with Generative Surrogate Models’ http://proceedings.mlr.press/v139/li21p.html\nDynamic measurement of features in time e.g. Chang et al. 2019 ‘Dynamic Measurement Scheduling for Event Forecasting using Deep RL’ https://proceedings.mlr.press/v97/chang19a.html\nFeature pruning for causal effect estimation e.g. Makar et al. 2019 ‘A Distillation Approach to Data Efficient Individual Treatment Effect Estimation’ https://ojs.aaai.org/index.php/AAAI/article/view/4375\n\n---\nAfter the rebuttal\n\nMy remaining concern relates to the second question above. Reasons for the success of the method are not clear from the experiments and how they are presented. For instance, seeing the accuracy of a baseline which removes all sensitive features (minimum data leakage) will help contextualize all line plots (e.g. percentage improvement from such a baseline can be the y-axis). This helps answer how much of the success is due to the method's feature selection versus predictability of the public features in the datasets.\nFurther, a detailed analysis of the examples that are predicted correctly with < 2 sensitive features will be instructive (e.g. looking at whether these are the same set of features or personalized to the data point).\nThis said I appreciate baselines included by authors to check the selection criteria and experiments to check effect of linearity, which are also required for a newly proposed method.", "limitations": "Limitations on modeling assumptions and theoretical analysis are acknowledged.\n\n\n## Minor comments, no response is aspected\n\nLine 4 of the Algorithm 1 to check core features should be explained in detail for the case of \\delta>0.\n\nPlease specify the assumption that input features are jointly Gaussian more prominently. e.g. in an Assumption environment, in the lines 177-180. \n\nPlease cite information processing inequality in Proposition 2 in main text.\n\nPropositions 2 to 5 and Theorem 1 are known results so they can be mentioned in text or denoted as lemmas with references.\n\nThe statement in line 174 does not require pointing to Proposition 1. It holds because of the definition of entropy.\n\nPlease provide guidelines on how to use the Gaussian approximation for categorical features.\n\nIntroduction is nicely written. However, the goal / objective of the paper is repeated multiple times which can be removed to be concise.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Writing is clear. The method is explained clearly step-by-step. I like the presentation of the results in the plots.\n\nMethod is simple and is shown to work on real datasets. The idea of selecting maximally informative features until decision is reached is natural. The idea is executed well.\n\nProblem of reducing data required for a prediction is important to increase user privacy, so the method has practical significance.", "weaknesses": "On the writing, some algorithmic details can be improved like mentioning the entropy calculation and calculating the core features sets for \\delta>0. Core feature sets can be defined more rigorously by mentioning the sources of randomness in the probability expression. Results from datasets other than Credit, which are presented in Appendix, can be summarised in the main text.\n\nReasons for the effectiveness of the method is not clear to me and are not sufficiently explored in experiments. This is needed given the success of simplifying assumptions on Gaussian distribution of features. Is this because of the dataset or model characteristics, or is due to the algorithm? Baselines such as removing all sensitive features might help check if dataset characteristics are the main contributor. An analysis of the examples which are predicted correctly without revealing features can shed more light. \n\nSome related work is missing. See detailed remarks. The technical contributions in light of this work is unclear.\n\nTheoretical analysis leaves many questions open e.g. the impact of approximations, what does optimal procedures look like, how much training data is needed to get significant privacy gains, how to extend the method to non-linear classifiers and high-dimensional data.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review!  Below, we report our answers to your questions. Feel free to let us know if there are further questions or concerns. and we'll be more than happy to elaborate. We also hope that you consider updating your score, if these replies answer your questions. \n\n**Q1: Notation**: In our context, since $X_U$ represents unobserved variables, we treat them as multivariate random variables following the conditional distribution $ P(X_U ∣ X_R=x_R) $. The model prediction $f_\\theta$ is inherently a function of $X_U$ and, therefore, is also considered a random variable.\n\nTo clarify with an example, if $P(X_U | X_R = x_R) = 0.8$, this implies that for all samples drawn from the distribution \n$x_U \\sim P(X_U | X_R = x_R)$, 80% of the time you will observe the model prediction \n$f(X_R = x_R, X_U = x_U)$ resulting in a value of 1, and 20% of the time, the prediction will be 0.\n\nThe unrevealed variables in entropy calculations, such as in term A of equation (3), are handled through similar probabilistic reasoning, where the conditional probabilities are leveraged to account for the uncertainty associated with these variables. We hope this clears up any confusion regarding the notation and handling of unobserved variables.\n\n**Q2: Clarification**: The impact of removing the 5 sensitive features depends on their importance relative to public features. If they're significant contributors, their removal could notably affect accuracy. In our specific experiments, all features contributed to prediction. Thus, designating some as sensitive and excluding them could lead to a drop in accuracy. The choice of sensitive features indeed matters in our case.\n\n**Q3: Entropy computation**: The entropy in Equation (4) quantifies the uncertainty in the model’s prediction for unobserved sensitive features $X_U$. It's computed by estimating the distribution $f(X_R = x_R, X_U)$ of the model responses with revealed variables $X_R$, which requires estimating the conditional distribution $P(X_U | X_R = x_R) from the training data. This can be done efficiently under a Gaussian assumption or less efficiently with a Bayesian neural network model.\n\nWe detail the Bayesian model used to estimate these conditional densities from Line 198 to Line 205, adhering to standard Bayesian neural network training and inference.\n\n**Q4: Related Work**: We appreciate the reviewer for highlighting relevant works related to active measurement, dynamic measurement, and feature pruning. Please notice that we reported a detailed discussion of related work and connection with differential privacy, feature selection, and active learning, in Appendix B.\nAmong the mentioned papers, we find the work by Li and Oliva (2021) to be the most closely aligned with our research. However, there are distinct differences.\n\nIn our study, as demonstrated in the motivating example of Section 2 and the testing core feature set in Section 5.2, we show that users do not need to reveal all sensitive features to obtain a hard-label prediction with 100% confidence. Additionally, we provide an efficient algorithm that determines whether the current set of revealed features can ascertain the value of the model prediction with complete certainty.\n\nAs for the other mentioned works, Chang et al. (2019) and Makar et al. (2019), we find their topics relevant but only tangentially connected to our problem setting. We assure you that we will include these related works and the nuanced discussions in our revised paper. Thank you for pointing us toward these resources.\n\n**Other comments**: Thank you for the detailed and insightful feedback. We sincerely appreciate your comments and will take them into account as we revise our paper.\n\nRegarding the use of categorical features, it is possible to employ a Bayesian network to estimate $P(X_U | X_R = x_R)$. However, it is essential to recognize that learning a Bayesian network can be a slow process, particularly when dealing with high-dimensional data. We would like to clarify that this challenge is not specific to our work but is a general concern in conditional density modeling of multivariate variables. The contribution of our work falls obviously beyond these constraints.\n\nWe hope this addresses your concern, and we welcome any further questions or feedback."}, {"review_id": "jyQqlO6pwx", "reviewer": "Reviewer_ahUZ", "summary": "The authors propose that in a large number of application of machine learning reasonable model accuracy can be realized without the model having access to the entire feature set. This has implications for privacy and data-sharing, as a model that adaptively selects features to solicit would retain model performance even when minimal sensitive data is revealed to the model. ", "questions": "The authors proposed a feature sampling strategy based on greedy selection on the Exected Information Gain. Such a strategy has shown benefit in other areas of machine learning especially in active learning. There could be potentially many other well motivated acquisition functions in the context of the problem the authors present. Have the authors considered other such possibilities? If yes, can the authors comment as to why Expected Information Gain (Entropy) was selected as the most reasonable choice. \n\n\nThe presented algorithm in its current stage does a one step-greedy lookahead which would work when the relationship between features is linear. Can the authors comment on tractability when looking at the power set of all potentia features that make the coreset?\n\n\nI am willing to tweak my scores based on engagement with the authors and other reviewers in the discussion phase.", "limitations": "There are issues with model safety and trust when a model adaptively solicits information from a user. Specifically, can the authors comment on how such an approach might effect users trust in the system when the model seeks disparate information from disparate users? \n\nI am not looking for a theoretical argument here, but more of a value judgement based discussion of potential implications of disparate treatment under such a model. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* The motivation for the paper is clear and important. The ability to reduce the amount of disclosed data is appealing and a thoughtful, timely contribution. \n\n* The authors attempt to address obvious questions that may arise, specifically around the relationship between the input features being non-linear.  \n", "weaknesses": "* the empirical evaluation of the model is somewhat weak. The authors do present results in terms of accuracy, however, there is no discussion as to what is the source of performance degradation, if any. It would be nice to see a more holistic evaluation that takes into account other aspects of the classifier performance, including ROC performance and calibration. \n\n* For linear classifiers, computing the argmax over the estimated entropy is easy as it factorizes over the individual dimensions of the core set. However, this may not be the case when the relationship between features is non-linear. Can the authors comment on this. Specifically can the presented algorithm still be tractable if higher-order interactions between core-set of features considered? \n\n* The current evaluation pipeline randomly assign attributes as un disclosed at random. I would recommend pre-specifying the disclosure rate based on certain notion of harm revelation of that feature would cause.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review! If there are further questions or concerns and we'll be more than happy to elaborate. \n\n### Empirical evaluation \nWe appreciate the suggestion to include a more holistic view of the classifier's performance. Below, we address your concerns and provide additional insights.\n\n1. **Trade-off between Data Leakage and Accuracy:** We indeed discuss the trade-off between data leakage (the number of features a user needs to reveal) and model accuracy in Section 3. Our approach is tailored to the user's willingness to reveal more or fewer features, leading to varying levels of accuracy. We believe this aspect of our work offers a nuanced understanding of how information revelation impacts predictions.\n\n2. **Choice of Evaluation Metric:** We chose accuracy over the AUC metric for two main reasons:\n- AUC is generally designed for binary classification tasks. In our work, as elaborated in the Appendix, we also tackle multiclass classification problems.\n- Our primary concern is to obtain the model's hard prediction, which can be estimated with 100% confidence (delta = 0) even when not all sensitive features are revealed. This contrasts with soft-label prediction, where 100% confidence is impossible if some features remain unrevealed. Hard-label prediction requires users to reveal less sensitive information than soft-label prediction when considering minimum uncertainty or aiming for 100% confidence.\n\n3. **Additional AUC Analysis:** We understand the importance of the AUC metric, and to address your concern, we have evaluated our F-score (with $\\delta=0.2$) method against the Random and Feature Importance methods on Bank data. The results, shown in the table below, indicate similar AUC values to the baseline Importance, with the added benefit that users need to reveal fewer features (as detailed at the bottom of Figure 6).\n\n|   m  | F-score | Random | Importance |\n|------|---------|--------|------------|\n|  4   |  0.874  | 0.871  |   0.874    |\n|  5   |  0.874  | 0.872  |   0.875    |\n|  6   |  0.860  | 0.854  |   0.860    |\n\n### Entropy computation\nWe recognize that the complexity of computing the argmax over the estimated entropy becomes more challenging when we move from linear to non-linear models. Specifically, the ease of factorization over individual dimensions, as found in linear classifiers, no longer applies in the non-linear context. In our exploration, we observed that non-linear models do indeed incur more computational overhead but this increase in complexity is a trade-off we accept for the following reasons:\n- _Increased Accuracy_: Non-linear models are often capable of capturing more intricate relations within the data, leading to higher accuracy in general compared to linear ones.\n- _Higher-Order Interactions_: Despite the added complexity, our algorithm's ability to consider higher-order interactions between core-set features opens the door to more sophisticated and nuanced modeling. This approach may allow us to uncover relationships that linear models cannot.\n\nWe believe that the potential gains in modeling capability justify this trade-off. \n\n### Evaluation pipeline\nWe agree that sensitivity varies by application and cultural context, and expert knowledge is often needed to make these determinations. For example, the disclosure of political orientation might have different implications in different regions.\n\nIn our current evaluation, we opted for random assignment to maintain generality. However, we acknowledge that your suggestion could lead to a more nuanced evaluation. Your insight is appreciated, and we're open to further dialogue on this matter.\n\n### Q1 (Expected information gain)\n\nThank you for this insightful question. \nIndeed, we explored several alternative methods for our feature sampling strategy, including **(1)** an importance-based approach that prioritizes revealing more critical features first, and **(2)** a strategy based on the uncertainty of a feature given all revealed features. Our work compares the former in the main text and appendix. \n\nNote that approaches such as uncertainty score, do not account for the model's prediction, limiting their effectiveness, while the Expected Information Gain is able to capture the benefit of revealing a particular feature in the context of our problem. \nWe believe that our choice, backed by its proven efficacy in areas like active learning, represents a well-motivated and robust solution for the data minimization context, but we remain open to exploring other methods.\n\n\n### Q2 (Algorithm's details)\n\nAs we elaborated in the main text (Lines 311 to 313), we did compare our proposed model with an _Optimal_ method that considers all possible subsets to choose the smallest coreset. Unfortunately, this exhaustive approach is not practical.\nAdditionally, it poses a significant challenge in that it requires users to reveal all features at testing time, which is against the core motivation of this work. \n\nOur proposed strategy, in contrast, offers a more tractable solution, particularly when the relationship between features is linear, balancing efficiency with effectiveness.\n\n### Q3 (Fairness)\n\nYou raise a great point regarding trust and disparate treatment. While our current work primarily focuses on the trade-off between accuracy and data leakage, we recognize the importance of fairness and the potential implications of unequal information solicitation across different demographic groups. \n\nIndeed, this is subject of our ongoing investigation. Ensuring fairness by equalizing the amount of information revealed across groups is a promising direction, and it's one that we're actively exploring in our current work.\n\nWe fully acknowledge that a thorough investigation of these ethical and social dimensions is needed. \n\nWe hope these clarifications adequately address your concerns. We are committed to making any necessary adjustments and look forward to any further suggestions you may have.\n"}, {"review_id": "IEV7a0sea0", "reviewer": "Reviewer_dE9z", "summary": "This paper considers the problem of data minimization at inference time. Consider a set of features X which consists of public features Xp, and private features X\\Xp. A model has been trained with all the features X, i.e., f(X). Now, the goal is to allow for inference revealing only a subset of the private features Xr and keep some of them unrevealed Xu.\nIn essence, X=Xp U Xr U Xu.\n", "questions": "See Weaknesses\nCOMMENT: After rebuttal, I increased my score by 2 points.", "limitations": "See Weaknesses (last point on my major concern)", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper introduces a new and interesting problem, i.e., data minimization during inference time.\n\nThey provide entropy-based measures to decide whether to include a feature or not. \n\nThey also provide theoretical guarantees and experimental results.", "weaknesses": "While the authors say this is the \"first\" work to do so, I think there are substantial similarities with the problem of feature selection or feature engineering as well as inference under missing data. The differences should be made clear with references.\n\nThe use of the term leakage can be a bit confusing since leakage is used here for the number of features revealed. But of course, the features can just be random noise and hence not leak anything, whereas one feature can also be much informative of everything and cause leakage. I think a different terminology should be used here since leakage sounds more like \"information\" rather than \"number of features\".\n\nMy most important concern: How does this approach compare with applying a local explanation framework and dropping the least important private features? For example, for each user, if you apply SHAP or LIME or even feature attributions, and then drop the private features with the least contribution for that local user. What performance would you get and how would that compare to your method?\nI would be happy to increase my rating based on a discussion/comparison with just applying existing local explanations for this problem statement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review. Below, we report our answers to your questions. Feel free to let us know if there are further questions or concerns and we'll be more than happy to elaborate. \n\n### Q1\n\nThank you for pointing out the apparent similarities between our work and existing problems in feature selection, feature engineering, and inference under missing data. We acknowledge that these are relevant domains, and a thorough understanding of how our work differs is crucial.\n\n*We have indeed addressed these differences in Section B (Related Work) of the Appendix*, where we detailed the distinctions between our approach and prior works. The space constraints in the main text prevented us from including this comparison there, but we ensured that the appendix provides a comprehensive examination.\n\nShould you require more specific insights or have any particular concerns about these comparisons, please let us know, and we'll be glad to address them.\n\n\n### Q2\n\nThank you for highlighting the potential confusion surrounding our use of the term \"leakage\" to describe the number of features revealed. Your observation about the possibility of one feature being highly informative, or features being mere random noise, is insightful.\n\nIn our work, we specifically focused on the concept of leakage as the percentage of sensitive features a user needs to reveal. This notion aligns with privacy policies on data minimization, such as GDPR, and we found it to be an interpretable measure in our context. In all the datasets we explored, the corner case you mentioned did not occur.\n\nHowever, we do acknowledge your concern and agree that considering alternative terminology could help clarify our intentions. Additionally, the idea of reporting a noisy version of a sensitive feature as a privacy precaution is worth further exploration. Your feedback has prompted us to reflect on our terminology, and we appreciate the opportunity to clarify our approach. We will take into account your suggestion in our revision.\n\n### Q3\n\nThis is a great question. In our specific context of data minimization, applying SHAP or LIME to each individual would necessitate the revelation of *ALL* features at test time in order to quantify the contribution of each feature. This requirement contrasts with our goal of minimizing the number of sensitive features released at test time.\n\nOur method is aligned with preserving privacy by controlling the information revealed, and we've designed it to consistently improve over methods that selects features based on their importance (evaluated on the entire population). Our results across different datasets substantiate this improvement.\n\nWe appreciate this thoughtful feedback, and it will certainly guide our further analysis and discussions in future revisions. We also hope you could reconsider your score, in light of our responses to your questions. "}, {"review_id": "k6lCQbzNiq", "reviewer": "Reviewer_ddiE", "summary": "The authors address the problem of data minimization at inference time, which poses a real-world challenge in real-world applications, where users might want to hide sensitive or personal attributes. They provide an efficient algorithm to sequentially determine the appropriate attributes for an individual, with the goal to maintain the original predictive accuracy (based on all attributes).", "questions": "Can you comment on the weakness above and limitations below?", "limitations": "The novelty of the work is rather limited, as relevant work on this topic has already addressed similar challenges.\nThe formalization of the approach and the theoretical framework is limited as it mainly aims for maintaining the high accuracy, and it does not consider the true privacy of the features that users wish to hide.\nThe evaluation is also focused on accuracy, which is not a meaningful measure in real-world ML applications based on tabular user data.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The considered problem is important and timely.\n2. The proposed theoretical framework introduces some interesting novel concepts.\n3. The paper is well motivated and well-written.", "weaknesses": "1. The addressed problem is inherently a privacy problem; if some feature values are not explicitly available at inference time, it does not mean that they can not be inferred. Actually, in practice if the predictive quality does not change after hiding some feature values, it is a strong indication that these values can be inferred from the other values.\n\n2. The overall objective of maintaining the original predictive quality with the minimum amount of private features is never explicitly formalized/defined.\n\n3. In many real-world applications that use personal data, accuracy is the worst measure for predictive quality, so focusing on and reporting this measure is not really meaningful (e.g., when the goal is good model calibration on imbalanced classes).\n\n4. Relevant related work has not been considered: I Prefer not to Say: Operationalizing Fair and User-guided Data Minimization\nT Leemann, M Pawelczyk, CT Eberle, G Kasneci", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review. Below, we report our answers to your questions. Feel free to let us know if there are further questions or concerns and we'll be more than happy to elaborate.\n\n### Comment on `The addressed problem is inherently a privacy problem ... can be inferred from the other values`\n\nWe appreciate your perspective on the inherent privacy concerns in the problem we've addressed. However, we'd like to clarify that the situation you describe might not necessarily hold in our context.\n\nTo illustrate our point, let's revisit the motivating example from Section 2 of our paper. In this example, the model's prediction remains invariant with respect to sensitive attributes like _Income_ and _Location_ when _Job_ equals 1. This behavior holds true even if all variables are independent.\n\nThus, in this particular case, the fact that the predictive quality does not change after hiding some feature values does not imply that these values can be inferred from the other values. Given the published _Job_ information, it is ineffective to use the model predictions to infer the original values of _Income_ and _Location_.\n\nWe understand the broader concern about potential inference from hidden features, and we agree that it's a critical consideration in privacy-related research. However, the specific mechanism we've explored offers safeguards against such inference in the scenarios we've examined.\n\nWe're open to further discussion if you have additional concerns or insights.\n\n### Q2 formalization of our objective\n\nwe have indeed described the overall objective of maintaining the original predictive quality with the minimum amount of private features. This description can be found in Line 65 of Section 2. \nWe chose to express this goal through an English description, believing it to be sufficiently clear and avoiding additional mathematical notation that might complicate the reading.\n\nHowever, we are receptive to your feedback and we are certainly open to incorporate a formal definition upon paper acceptance.\n\n\n### Q3 Choice of accuracy metric\n\nWe acknowledge that accuracy may not be suitable for all real-world applications, however, in the context of our work, we adopted accuracy as the evaluation metric for specific reasons. \n\n- First, we considered both binary and multiclass classification problems, making AUC less applicable in our situation. This decision is elaborated further in the Appendix.\n\n- Second, and more crucially, our work emphasizes obtaining the model's hard prediction, where confidence can be assessed with 100% certainty even when some sensitive features remain unrevealed. This scenario differs fundamentally from soft-label prediction, where a full confidence estimation of the prediction score is impossible if any features are undisclosed.\n\nIn essence, our focus on hard-label prediction, as opposed to soft-label prediction, requires users to reveal less sensitive information. This approach is aligned with the concept of minimum uncertainty, allowing us to achieve the highest confidence in our predictions.\n\nWe of course are open to considering other suitable metrics and appreciate your insights, but we also hope this explanation clarifies our choice of accuracy as the evaluation metric.\n\n\n### Q4 related work\n\nThank you for bringing the paper by Leemann et al. to our attention. We are aware of this work. It focuses on the privacy concerns related to opting out from data collection for individuals who choose not to share certain information.\nWhile the subject of privacy is a common theme between our work and the paper you mentioned, the direction and approach taken in our research are quite distinct. In our study, we are primarily concerned with minimizing data leakage by revealing the least amount of sensitive features without affecting prediction accuracy.\n\nAlthough the connection between the two works is somewhat tangential, we will consider adding a reference to this paper in the final version of our work for completeness and to acknowledge the broader context of privacy research.\n\n\n\nWe appreciate your feedback and hope you could reconsider your score, in light of our responses to your questions."}, {"review_id": "0vu5nbVQv7", "reviewer": "Reviewer_ZsPJ", "summary": "This paper questions the necessity of soliciting all user information at inference time, with an eye towards privacy-sensitive domains such as law, recruitment, and healthcare, where learning models typically require access to extensive and sensitive user data for accurate prediction. The authors propose in some settings, individuals might only need to provide a small subset of their information to obtain accurate predictions, thereby protecting their privacy and easing the burden on organizations verifying the accuracy of disclosed information. To that end, the authors introduce a framework for simultaneously considering model certainty and data minimization. Their setup includes considering subsets of features that individuals can disclose in order to receive comparable prediction quality while providing fewer features. The authors propose algorithms for choosing the appropriate subset and present theoretical justification and empirical findings. Initial evaluations reveal that individuals may only need to disclose about 10% of their information to achieve the same accuracy level as a model that uses all user information.", "questions": "- Can you explain or justify your use of model entropy as a proxy for model performance?\n- The thresholding explanation on line 190 was a bit confusing -- can you explain this process in more detail?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The primary strength of this paper is that it thoughtfully addresses a neglected and high-impact research question. As the authors note, there is strong evidence that \"most users would only need to reveal a small portion of their sensitive data to achieve accurate model predictions with either absolute certainty or high confidence.\" They include a strong motivating example in Section 2, Figure 1, to make it clear that it's possible that a label could be obtained without requesting all sensitive features. Similarly, they underscore the importance of this work by noting the real-world impacts on privacy and the burden of verifying the provided information.\n\nOther strengths:\n- This paper includes a thoughtful framework for studying this problem, quantifying the tradeoff between model certainty (though not model performance, as claimed) and privacy loss. \n- The proposed methods include an efficient algorithm for a joint Gaussian setting as well as a less efficient Bayesian modeling alternative\n- The experiments appear well-designed, including considering random subsets of \"private\" features using publicly available datasets", "weaknesses": "The primary weakness of this work is the use of entropy as a proxy for model performance. While the authors state that initially that their goal is the \"produce accurate or nearly accurate predictions during inference\" using fewer features, the goalposts subtly shift to \"accurately predict[ing] the **output of the model** using the smallest possible number of sensitive features.\" This shift motivates the use of prediction entropy, rather than predictive performance, as a metric for the impact of obtaining additional features. This is significant because while entropy obeys the \"information never hurts\" principle, predictive performance does not (see, e.g., https://proceedings.mlr.press/v97/ustun19a.html). Considering predictive performance (instead of entropy) likely makes this problem more difficult, and it's possible that using entropy is a reasonable proxy in some cases. However, this choice merits at minimum discussion and ideally theoretical and experimental justification. \n\nOther weaknesses:\n\nUnclear/imprecise notation and language:\n- \"data leakage\" is used inconsistently throughout the paper. It is introduced as \"the percentage of sensitive features that are revealed unnecessarily, meaning that their exclusion would not significantly impact the model’s output,\" but the authors later state that \"[increasing $\\delta$ yields] reduced data leakage but also less precise model predictions\" which appears contradictory. This term is later used as a metric in the experiments, but without a precise definition and with axes that seem to contradict prior use.\n- on line 155-156, the authors state that the imputation does not occur, and the \"unrevealed features are treated as random variables and are integrated during the prediction process.\" This process is not further explained but appears to be implicit in Equation 5 with a Schur complement (and arguably as a form of imputation). \n- \"public\" is used both to describe a subset of features \"public x_P and sensitive x_S features\" and a subset of samples \"trained on a public dataset\"\n- The hyperparameter T appears on line 9 of Algorithm 1 but is not discussed from what I could tell, either theoretically or empirically\n- In line 13 of Algorithm 1, it is unclear if feature j* is actually obtained here or if it is added to the set of features to be obtained. I assume the former. \n- The assumption that the cost of obtaining each feature is uniform should be explicitly stated. \n\n\nOther:\n- The authors claim throughout the paper that they are the first to study this type of work (line 47, line 420) despite the presence of several other publications on this topic (e.g., https://arxiv.org/abs/1602.03600 or https://proceedings.mlr.press/v5/yu09a.html)\n- Some words were used improperly (e.g., \"contrast\" on line 9, \"recur\" on 196, \"valid\" (sufficient?) on line 227). Overall, could use another pass to make the writing more clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and review. Below, we report our answers to your questions. Feel free to let us know if there are further questions or concerns and we'll be more than happy to elaborate.\n\n\n### Comment on hyperparameter T\n\nYou are right, and we appreciate the catch. $T$ is indeed the number of Monte Carlo samples used in the algorithm. We acknowledge that this was not clearly explained in the original text, and we will include a more detailed explanation of this hyperparameter in our revision.\n\n### Comment on line 13 of Algorithm 1\n\nYour assumption is correct. In line 13 of Algorithm 1, we identify the most promising unrevealed feature $j^\\star$ that provides the most information about the model's prediction. The value of this feature is then obtained from the user, and we remove it from the set of unrevealed features $U$ and add it to the set of revealed features \n$R$.\n\n### Comment on cost of obtaining each feature\n\nThank you for highlighting this point. We indeed operate under the scenario in which the cost, whether it's the privacy cost or the cost of obtaining the feature value for sensitive features, is uniform across the features. This assumption will be explicitly stated in our revised manuscript to ensure clarity.\n\n### Comment on related work\n\nWe appreciate the reviewer for highlighting these relevant works. Upon review, we found that the papers shared focus on different aspects, such as training time, reinforcement learning (in the first paper), and multi-view learning (in the second paper). \n\nOur work, in contrast, specifically targets the testing phase where a pretrained classifier is given. Therefore, while the cited works are indeed valuable and related, the context and focus of our research distinguish it from the prior studies. This helps clarify the claim made in lines 47 and 420 about the novelty of our approach in this particular domain. \n\nWe will be happy to discuss such related work in the final version of our paper (please also see current discussion of related work in Appendix B).\n\n### Q1: Model performance\n\nIndeed, the use of model entropy in our work serves as a tool to measure the uncertainty associated with the model's predictions. We focus on the trade-off between revealing sensitive features and maintaining prediction accuracy and want to achieve better accuracy for the whole population while minimizing data leakage, which includes revealing fewer features.\n\nThe model entropy helps us quantify the uncertainty in the model's predictions. As we reveal more features, the entropy typically decreases, reflecting that the model becomes more confident in its predictions. Conversely, if we reveal fewer features, the entropy may increase, indicating higher uncertainty.\n\nHowever, it is important to note that revealing more sensitive features does not necessarily imply higher prediction accuracy for some individuals. This is obviously important in personalization settings. \nHowever, and importantly, in our study, we have empirically observed that revealing more features generally ensures better accuracy across the whole population (see, for instance Figure 6). But designing a personalized algorithm that considers both data leakage and accuracy can be challenging, and this relationship may not hold for every individual.\n\n### Q2: Further explanation of line 190\n\nAbsolutely! In our framework, we have to compute the distribution of $\\tilde{f}_\\theta$ over the uncertainty of certain unrevealed sensitive features. If the distribution of these unrevealed features follows a Gaussian distribution, then the distribution of the soft-label prediction (i.e., $f_\\theta(x) = \\theta^\\top x$) is also linear, or approximately linear in the case of non-linearity.\n\nNow, here's where thresholding comes into play. To move from the soft-label prediction to a hard-label prediction, we apply a thresholding operation. Since the soft-label prediction follows a Gaussian distribution, thresholding this Gaussian turns it into a Bernoulli variable. In other words, we are converting a continuous-valued prediction into a binary decision by comparing it to a threshold.\n\nThe thresholding process is a key step in translating continuous predictions into categorical outcomes, especially when we are dealing with uncertainties tied to unrevealed features. We understand that the concise description in line 190 might have been unclear, and we plan to include a more extended and illustrative description in the final version of the paper to alleviate any confusion.\n\nWe hope we have addressed all your concerns, and we welcome any further questions or feedback.\n"}]

Author rebuttal:

Meta-review: Reviewers engaged with this paper and identified strengths in its focus on data minimization and its technical contributions. Following the rebuttal period, the overall sentiment for the paper was "uniformly weakly positive": all five reviewers leaned towards acceptance, but there was no champion. Given the borderline scores and the potential for impact, I also reviewed the submission, reading the reviews, responses, and the original submission. 

**My recommendation is to accept the paper.** This recommendation is based on a uniformly positive assessment from all 5 reviewers, the lack of fatal flaws in the work, the broader need for technical work on data minimization in the literature, and the potential impact of this work provided that the authors can carry out some simple revisions. Below, I list the high-level strengths and weaknesses I weighed and include my suggested changes for the camera ready.

### Evaluation

**Strengths**

- Studies an emerging topic in the privacy (e.g., data minimization). This is a valuable task that deserves more attention in the literature.

- Proposed methods to train classifiers that minimize features at test time has several valuable implications (e.g., to minimize sensitive features in healthcare applications, or to minimize features that are costly to acquire)

**Weaknesses**

- Proposed methods "minimize features requested at prediction time" using "entropy" as a proxy. This issue is glossed over in the work and merits further attention.

- Motivation: The paper motivates the need for data minimization in a way that is overly abstract. This would be stronger with a few specific examples.

- Presentation: The paper suffers from a set of baffling decisions that make it difficult to read and evaluate. Methods are developed in standalone sections that also include experiments. Related work is deferred to an Appendix. Captions for the figures are short and uninformative. I have included suggestions below to address these issues.

### Proposed Revisions

### 1. Explicit Discussion of the Use of Entropy as a Surrogate.

I agree with ZsPj in that the greatest weakness of this work is the fact that the proposed methods use entropy as a surrogate measure. This decision could backfire in a harmful way ([see e.g., comments by ZsPj](https://openreview.net/forum?id=cZS5X3PLOR&noteId=0vu5nbVQv7)). It can also ability to apply the approach to analogous methods that minimize data with respect to other metrics (see e.g., the comments of [ddIE](https://openreview.net/forum?id=cZS5X3PLOR&noteId=5jHf3H9W6Q)).  

IN this case, I did not find the authors' response to ZsPj convincing or commensurate with the concerns surrounding this issue. However, I decided to recommend acceptance as the experiments suggest that the proposed methods can work effectively. Given the positive results, I recommend a number of changes to improve clarity and establish soundness:

1. Explicitly state the potential limitations of the design choice in the main text (e.g., by using a Remark). Note that the assumption was only caught by ZsPj but missed by 4 of 5 reviewers.

2. Explicitly characterize when you would expect to run into failure modes as a result of the surrogate. This can be done, for example, by referring to related work, developing counterexamples, and evaluating in the experiments.

3. State the potential limitations in the conclusion. Discuss how to deal with it in practice, and how it might affect the design of future work.

### 2. Strengthen Motivation

If accepted, the paper will be well-positioned to inspire future work on this topic. To this end, I would advise the authors to articulate a clear and convincing case for data minimization -- with tangible examples and references to policies and laws. 

As stands, the motivation for data minimization in the introduction is weak because it is too abstract. Consider the following statement from the introduction: 

> This practice not only presents significant privacy risks for users but also burdens companies and organizations with an extensive human effort to verify the accuracy of disclosed information (e.g., auditing in finance operations).

Who is the "user" and "the organization?" What is the "burden"? What are the "privacy risks?" Has this actually happened or is this some narrative? The text would be far more convincing if it could update sentences like these to paint a clear picture to, e.g., an undergraduate student. Point to actual instances and regulations, naming users, organizations, and explaining the "burden" in precise terms. 

### 3. Restructure for Readability

The paper would be far easier to read, skim, and understand if you could make a few changes.

- Integrate Related Work Section: I strongly recommend that the authors include a Related Work section in the paper. As mentioned by ddiE /  ZsPj, the paper overlooks a number of recent work related to data minimization. I would recommend the work reference these papers clearly and plainly to highlight a broader stream of research on this topic, and to cite principles and laws beyond legal requirements beyond those in the GDPR. The relationship between the current work and related papers should be *crystal clear*.

- Separate Methods from Evaluation: The last 3 sections of the paper should be restructured. I would recommend bundling them all into a single section with subsections ("Scoring Features", "Linear Alg", "Non-Linear Alg"). The experiments should be placed in a standalone section. The current structure doesn't allow for easy comparison between the algorithms and wastes space (leading to e.g., short captions and related work in the Appendix)

- Figure 1: This is a missed opportunity to clearly convey your problem and proposed solution. It should be developed into a full-width Figure so that readers who skim the paper can quickly understand your setting, and readers who read the paper can understand the order of operations. Note that [dE9z](https://openreview.net/forum?id=cZS5X3PLOR&noteId=IEV7a0sea0) would not have asked questions about the LIME/SHAP attribution method had there been a clear description of what you are trying to do.

- Captions: The captions for all figures in this work are too short and uninformative (e.g., "Figure 6 Neural Network Classifiers"). These captions should be updated to explain what you are showing and why.
Decision: Accept (poster)