The Fundamental Limits of Least-Privilege Learning

Thank you very much for taking the time to read our paper and the valuable suggestions. Below, we try to address your comments.

Comparison to other learning techniques: The review rightly notes that the literature suggests a wide range of learning techniques to address attribute leakage in deep network models. As we show in Section 3.2, Theorem 2, however, the trade-off between a representation’s utility and achieving the LPP applies “regardless of the way the feature representations are obtained” (Section 3.2, page 6). In Section 4, we provide an empirical evaluation that supports our theoretical results: Regardless of a model's learning task and even under censoring, the LPP cannot be fulfilled while simultaneously providing high utility for the prediction task.

We furthermore note that to the best of our knowledge none of the existing techniques in the literature can actually achieve the desired goal of LPL. To do so, the features learned by the model would need to simultaneously restrict leakage for any sensitive attribute $S$. Techniques to defend against attribute inference are mostly limited to one or two fixed sensitive attributes and hence cannot achieve this goal.

Complexity of feature extractor: Our theoretical results imply that the trade-off applies not only regardless of the learning technique, but also regardless of a model’s architecture. We have run additional experiments using a different model architecture (ResNet-18) on the same image dataset to confirm that, as predicted by Theorem 2, the trade-off applies regardless of the exact architecture choices. We have uploaded these results as supplementary material, and we them to the Appendix.

Additional dataset: In the supplementary material, we provide the results of an additional experiment which demonstrates the strict trade-off between model utility and the LPP on a very different type of data and model. As for tabular data, together with image data, sharing feature encodings instead of raw data is often suggested as a solution to limit harmful inferences, we chose the Texas Hospital dataset and the TabNet model architecture (Arik & Pfister, 2021) for these experiments.

The results show that, as predicted by Theorem 2 (Section 3.2), for any learning task there always exists a sensitive attribute that violates the LPP.

Thank you very much for the review and your questions which we try to clarify below.

Key difference to existing information-theoretic approaches:

Connection to CEB: Our formalisation of the (previously only stated informally) problem of least-privilege learning can be thought of as a version of the generalised Conditional Entropy Bottleneck (CEB) problem (Fischer, 2020), as we explain in Section 3.2, page 5. In contrast to standard CEB, we consider a stronger notion of leakage, i.e., maximal leakage rather than mutual information, between the representations $Z$ and the sensitive raw data $X$. Weaker notions of leakage are not adequate in our case where we want to assess the least-privilege claim.

Connection to Privacy Funnels: The Privacy Funnel (PF) problem is different from the least-privilege problem that we consider in this work; as Asoodeh & Calmon, 2020 point out, PF and bottleneck-type problems like CEB are "duals" of each other.

As the review notes, privacy funnels operate in a different setting. Most crucially, because they consider only a single fixed attribute. As we discuss in Section 3 (“Attribute Inference”), we have to treat any attribute other than the learning task as sensitive to capture the least-privilege principle: We want the representation to leak nothing else other than the fundamental leakage implied by the learning task.

Limits of empirical evaluation: In the Supplementary Material, we provide the results of an additional experiment which demonstrates that the strict trade-off between model utility and the LPP also holds on a very different type of dataset and model. As for tabular data, together with image data, sharing feature encodings instead of raw data is often suggested as a solution to limit harmful inferences, we chose the Texas Hospital dataset and the TabNet model architecture (Arik & Pfister, 2021) for these experiments.

The results show that, as predicted by Theorem 2, Section 3.2, for any learning task there always exists a sensitive attribute that violates the LPL.

We limit the empirical evaluation to single attribute inference attacks as, despite their simplicity, they are sufficient to support our theoretical result: As soon as the adversary’s inference gain on a single attribute exceeds the features’ utility for the learning task, the features cannot be claimed to fulfil the LPL claim. We note, however, that Theorem 2 covers any type of inference attack, incl. data reconstruction attacks for the case where $S=X$.

We have uploaded a revised version of our paper that

• clarifies the connection to related information theoretic problems, such as CEB and Privacy Funnel (see Section 3.2 page 5).
• contains additional experiment results that confirm that, as predicted by our theoretical results, the trade-off also applies to other types of data (see Appendix C.3, Figure 9).

We hope that these revisions address your comments in a satisfactory way.

Thank you for the review. As the review has pointed out in the summary, our paper provides the first formalisation and a generic characterization of the trade-offs involved in least-privilege learning, which was proposed in the prior work (Melis et al., 2019; Brown et al., 2022). Our characterization applies to any method of obtaining feature representations, covering the model partitioning and collaborative learning settings. Please let us know if there are any questions we can answer to change the assessment of the contribution significance, or to clarify any concrete issues with the presentation.

We would like to thank you for the thoughtful review and the questions which we will try to address as best as possible next.

Practical implications for users and service providers: This is an excellent question which we tried to partially address in Sections 4.1 and 4.2 (“Takeaways”). The primary conclusion we draw from our results is that service providers should carefully evaluate the trade-off between utility and unintended information leakage for a given learning task and more openly communicate their results to increase transparency and avoid unexpected inferences, with potentially harmful consequences, on the user side. In particular, service providers should evaluate the fundamental leakage of a task and inform users that “any data attribute that is correlated with the chosen task” (Section 4.1, page 8) might also be revealed. This would enable users to make informed choices about the risk they might take by the use of a prediction service or by contributing their data for model training.

Second, going forward, we encourage both researchers and practitioners to more rigorously evaluate broad claims, such as, the claim that sharing feature representations instead of raw data records limits information leakage to “only the features relevant to a given task” (Melis et al., 2019). We hope that our formal definitions serve as a good basis to evaluate such claims and any future proposals.

Strong assumption on sharing label information: The assumption that the service provider has access to the correct label information of a particular target record is primarily motivated by the observation that it is impossible to achieve the strict LPP definition given in Section 3.1, Definition 1. To allow for any meaningful learning, we have to at least allow for the fundamental leakage through the task label (see Section 3.2, page 5), which means we have to assume that the label is known to the adversary. We note that a weaker assumption on the fundamental leakage adversary would result in an even worse trade-off between unintended feature leakage and a model’s utility.

In some preliminary experiments, we did assess the success of an adversary that only has access to a record’s predicted task label instead of the ground truth. We observed that, as expected, the adversary’s success in predicting a sensitive attribute from the predicted task label increased with increasing model utility. In our analysis and final experiments, we decided to only consider the worst-case adversary that has access to the correct task label as this gives us a lower bound on the adversary’s multiplicative gain and hence the best method to analyse the trade-off.

Relation to other privacy-preserving techniques: ln short, alternative solutions to this problem, such as encryption or complete data isolation and local processing are orthogonal to the idea of sharing feature representations instead of the raw data to prevent harmful inferences. As Osia et al., 2017 and 2018, discuss, these methods are often not efficient enough for big data and deep learning.

Data anonymisation can indeed be thought of as an instance of sharing a representation of the data rather than the data itself (see Makhdoumi, et al., 2014); with the crucial difference that the set of sensitive attributes is fixed and limited and that the learning task is not defined upfront. This hence leads to a different trade-off between preserving and hiding information than in our setting.

Response to minor comments:

• The transition kernels between Y - X - W can be arbitrary so long as $Y \bot W \mid X$.

• The positive posterior requirement implies both upper and lower bound as the notation is a shorthand for $P(Y = y \mid X = x) > 0$ for all $y \in \mathbb{Y}$. Indeed, the assumption allows distributions that are arbitrarily close to a point distribution, but not exactly point distributions.

• The bar in the third row should indeed be coloured red. We apologise for this data plotting error. A negative value indicates that the performance of the classifier has dropped below the majority class baseline guess, i.e., that the features learned by the model do not provide any utility for the prediction task. This is a common side effect of censoring techniques which often lead to a degradation in model performance (see, for instance, Song & Shmatikov, 2019 and Raff & Sylvester, 2018).

First, thank you for taking the time to review our work and the insightful comments which we try to address below.

Model splitting between server and clients is counter-intuitive: The model partitioning setup, as we describe it in this paper, is a common paradigm in the area of privacy-preserving cloud computing and in the context of privacy for MLaaS (see, for instance, Osia et al., 2018, Wang et al., 2018, Chi et al., 2018, Li et al., 2021, and Brown et al., 2022). The main motivation, cited in all works and also the focus of our work, is to prevent harmful inferences from raw data records. Other reasons to not share the full model might include intellectual property concerns or scalability considerations (see Osia et al., 2018 for a more detailed discussion).

Effect of the splitting method on theoretical and empirical conclusions: In Section 3.2, Theorem 2, we show that the trade-off between a representation’s utility and achieving the LPP applies to any feature representation regardless of the exact splitting method, model architecture or “the way the feature representations are obtained” (Section 3.2, page 6).

In our experiments, we evaluate the trade-off between utility and unintended inferences on the last layer feature representations of a CNN model. We choose the last layer because it is where a record’s feature activations are expected to be most learning task specific (Melis et al., 2019 and Mo et al. 2021) and hence the claim that these representations meet the LPP is the strongest. Our results demonstrate that, even at the last layer and under censoring of particular attributes, the least-privilege claim does not hold true.

We have run additional experiments: (1) using a different model architecture (ResNet-18) on the same image dataset, and (2) using a different model (TabNet) on an additional tabular dataset (Texas Hospital dataset) to confirm that, as predicted by Theorem 2, the trade-off applies regardless of the exact model architecture choices. We have uploaded these empirical results as supplementary material, and will add add them to the Appendix.

Difference to Melis et al.: The review points out correctly that the setting which we use to motivate our work and in our empirical evaluation differs from the setting described by Melis et al., 2019 who model unintended feature leakage in a collaborative learning setting. Yet, as we state at the beginning of Section 2: “all of our formal results apply to any setting in which feature representations are used as a means to limit the data revealed to untrusted third parties, such as the collaborative learning setting” (Section 2, page 2). The gradients shared during collaborative learning are a noisy representation of the features learned by the model, and hence are also captured by our setting $Z = f_E(X)$ in the same way as feature representations in the model partitioning scenario.

Worst-case assumption on attributes considered sensitive and how it affects the trade-off: As mentioned in Section 3 ("Attribute Inference"), we want to model an adversary that captures the least-privilege principle which implies that the representations shared with the service provider leak nothing else other than the fundamental leakage implied by the learning task. To adequately capture this principle, we have to consider any attribute, other than the learning task, to be sensitive.

If we were to restrict the set of attributes considered sensitive, the problem would become similar to a version of the Privacy Funnel (PF) problem (Asoodeh & Calmon’20). PF is different from the least-privilege learning problem (a form of generalized Conditional Entropy Bottleneck (CEB) problem; see next) that we consider in this work. As Asoodeh & Calmon point out, PF and bottleneck-type problems like CEB are "duals" of each other.

Trade-off as a result of strong assumptions: As we discuss in Section 3.2, the strict trade-off between utility and the LPP exists because the LPP restricts the adversary’s inference gain in terms of maximal leakage. In the standard CEB problem (Fischer, 2020), which considers a weaker notion of unintended leakage, the mutual information between the representations $Z$ and the sensitive raw data $X$, there is hence no such trade-off (see Section 3.2, page 6). Such a weak notion of leakage, however, is not adequate to formalise and assess the original claim from many papers that it is possible to learn feature representations that protect against any harmful inferences and fulfil the least-privilege principle.

We have uploaded a revised version of our paper that

• better justifies our theoretical assumptions to consider all attributes as sensitive and to analyse the trade-off in terms of maximal leakage (see Section 3.2 page 5).
• better explains how these theoretical assumptions affect the strict trade-off between the least-privilege principle and utility (see Section 3.2 page 6)
• contains additional experiment results that confirm that, as predicted by our theoretical results, the trade-off applies to any feature representation regardless of the feature mapping (see Appendix C.1 and C.3, Figures 6 and 9).
• contains an updated version of Figure 4 that fixes the data plotting error that this reviewer thankfully pointed out.

We hope that these revisions address your comments in a satisfactory way.

Thanks to the authors for the response and clarifications. The evaluated partitioning scheme (where the server only has a small part of the model) and the overly strong privacy definition still lack significance to me.

Re the model partitioning scheme, let me rephrase the discrepancy. The authors only evaluate settings with a small classifier on the server side. By contrast, the model on the server side is large in most (if not all) cited works, especially in Melis et al.

Re the significance of the trade-off, as the authors acknowledge, the results largely result from the strong privacy definition and do not easily extend to settings with a subset of sensitive attributes. This makes the results less interesting/useful, as they only reinforce a common belief in the early work of Melis et al. below.

Of course, the purpose of ML is to discover new information about the data. Any useful ML model reveals something about the population from which the training data was drawn. For example, in addition to accurately classifying its inputs, a classifier model may reveal the features that characterize a given class or help construct data points that belong to this class. In this paper, we focus on inferring "unintended" features, i.e., properties that hold for certain subsets of the training data, but not generically for all class members.

This belief is the whole motivation of Melis et al., and follow-up works to focus on unintended features rather than all features. Therefore, why should we care about all features again in this paper?

Additionally, I'm puzzled by whether/how the trade-off under LPP (Theorem 2) does not hold under the conceptual representation $Z=\arg\max_{y}P(Y=y|X)$. Specifically, this representation does not reveal any more information than the class of the input data $X$, yet it yields Bayes optimal classification success.

• Is it because it violates certain assumptions required for Theorem 2?
• If so, does it imply Theorem 2 is too limited to cover representations that are similarly good, i.e., achieve Bayes-optimal classification success?

We agree that this instance of $Z$ can seem counter-intuitive, but it follows the trade-off just like any other feature representation. To see this, observe that this instance of $Z$ can actually reveal more information about $X$ than only the class label $Y$. It is easiest to see with an example. Consider a binary input space $\mathbb{X} = \{a, b\}$, and binary label space $\mathbb{Y} = \{0, 1\}$, both uniformly distributed: $P(Y = 1) = \frac{1}{2}$ and $P(X = a) = \frac{1}{2}$. Assume the data distribution is as follows:

Consider a full data reconstruction attack, so the sensitive attribute is $S = X$. Observe that optimal accuracy of predicting $X$ from only class label $Y$ is $P(X = \hat X(Y)) = \frac{1}{2} \cdot 0.6 + \frac{1}{2} \cdot 0.6 = 0.6$, so 60%. At the same time, observe that $Z$ and $X$ in this case are one-to-one, as $Z$ is a deterministic function of $X$. So, accuracy of predicting $X$ from $(Z, Y)$ is $P(X = \hat X(Z, Y)) \geq P(X = \hat X(Z)) = 1$, so 100%! Therefore, multiplicative leakage is quite high, $\log \frac{1}{0.6} \approx 0.74$. This is because $Y$ is random, so predicting $X$ from $Y$ carries uncertainty, whereas this instance of $Z$ always reveals $X$ exactly.

Regarding the model partitioning scheme: To clarify this point, we would like to distinguish between two questions (1) In what form are data representations made available to the service provider/adversary? (2) What is the architecture of the model and how is it split into an encoding $f_E$ and classification part $f_C$?

On (1), as we describe at the start of Section 2, some works evaluate unintended feature leakage in a collaborative learning setting (Melis et al., 2019), others in a model partitioning setting (Brown et al., 2020, Song & Shmatikov, 2020, Zhao et al., 2020 or Osia et al., 2018).

Melis et al., 2019 assume that the adversary/service provider has access to the full set of gradient updates across all layers of the model. They state that these "gradient updates can [...] be used to infer feature values, which are in turn based on [...] private training data". In our notation, the data representations $Z = f_E(X)$ are hence the (noisy) feature values of a (batch of) training examples across all layers of the model. Works such as Brown et al., 2020, Song & Shmatikov, 2020 or Zhao et al., 2020 assume that the service provider is given direct access to a record's representation at a particular output layer of the model.

While we have empirically evaluated the model partitioning setting, we highlight that our theoretical results equally apply to both settings.

On (2), this question only becomes relevant in the model partitioning setting. Here, we decide at which layer we split a model into its encoding and classification parts. This decision determines the output of the encoder $Z = f_E(X)$, which in turn determines what information is made available to the service provider/adversary to make a prediction about $Y = f_C(Z)$ and to makes a guess about $S = g(Z)$.

The main result of our work (Theorem 2) shows that the trade-off between limiting the inference about $S$ and preserving information about $Y$ holds for any feature mapping $f_E$; and equally for any classifier $f_C(Z)$. That is, these results hold independently of the size of the classification part on the server side.

To provide evidence of this fact, in Appendix C.2.2, we added an experiment in which we used the code by Zhao et al., 2020 to reproduce our results under their model architecture and training method (maximum entropy adversarial representation learning). In Figure 8, we show that the trade-off in Theorem 2 also applies to this scenario, which has a more extensive classification part than our original experiments.

Regarding the assumptions and significance of the results: The goal of this paper is to "provide [a] formalisation of the least-privilege principle for machine learning" (Section 1, page 2). The least-privilege concept is repeatedly mentioned in previous works, including Melis et al., as a promising avenue to solve the unintended leakage problem:

"We [...] showed that [...] defenses [...] are not effective. This should motivate future work on better defenses. Techniques that learn only the features relevant to a given task can potentially serve as the basis of "least-privilege" collaboratively trained models." (Melis et al., 2019, Section XI "Conclusions").

Even though many works point to the least-privilege concept as a solution, "so far this idea has not been formalised. Our goal is to formalise this principle and characterise its feasibility." (Section 2, page 3). Our formalisation allows us to show, for the first time, that the least-privilege principle turns out to be elusive in representation learning. Our results demonstrate that, as the reviewer suspects, the assumption that it is possible to achieve least-privilege learning, "learn only the features relevant to a given task" (Melis et al., 2019), is “too strong”. However, this was not at all obvious prior to our result. Instead, prior work repeatedly called for least-privilege learning as a promising way to solve the problem of overlearning (see, for instance, Melis et al., 2019, Brown et al., 2020).

As least-privilege learning comes with a stringent trade off, we agree with the reviewer’s sentiment that the only feasible goal is to limit inference with respect to a specific set of attributes. At that point, however, we have to abandon the concept of least-privilege learning as in “learning representations that contain information that is only relevant to the task itself” and move towards attribute obfuscation and formalisations such as the privacy funnel (see Zhao et al., 2020, Asoodeh and Calmon, 2020 for trade-offs for these problems). How to do that and what are its fundamental limits, is simply a different problem than the one we aimed to formalise and characterise.