Enhancing Learning with Label Differential Privacy by Vector Approximation

## Abstract

Abstract Label differential privacy (DP) is a framework that protects the privacy of labels in training datasets, while the feature vectors are public. Existing approaches protect the privacy of labels by flipping them randomly, and then train a model to make the output approximate the privatized label. However, as the number of classes K 𝐾 K italic_K increases, stronger randomization is needed, thus the performances of these methods become significantly worse. In this paper, we propose a vector approximation approach, which is easy to implement and introduces little additional computational overhead. Instead of flipping each label into a single scalar, our method converts each label into a random vector with K 𝐾 K italic_K components, whose expectations reflect class conditional probabilities. Intuitively, vector approximation retains more information than scalar labels. A brief theoretical analysis shows that the performance of our method only decays slightly with K 𝐾 K italic_K . Finally, we conduct experiments on both synthesized and real datasets, which validate our theoretical analysis as well as the practical performance of our method.

## 1 Introduction

Differential privacy (DP) [] is an effective approach for privacy protection, and has been applied extensively [, , , ]. However, in supervised learning problems, the original definition of DP can be stronger than necessary, resulting in unnecessary sacrifice of utility. In particular, sometimes it is reasonable to assume that features are publicly available, while only labels are highly sensitive and need to be protected, such as recommender systems [], computational advertising [] and medical diagnosis []. These scenarios usually use some basic demographic information as features, which are far less sensitive than the labels. Under such background, label DP has emerged in recent years [, , , , ], under which the output is only required to be insensitive to the replacement of training labels.

There are several existing methods for learning with label DP, such as randomized response [], RRWithPrior [] and ALIBI []. These methods flip training labels $Y$ randomly to privatized labels $\tilde{Y}$ to satisfy the privacy requirement. However, a common issue is that the performances decrease sharply with the number of classes $K$. Intuitively, with $K$ increases, it is inevitable for the privatized label to be randomly selected from a large number of candidates, thus the probability of maintaining the original label $\text{P}(\tilde{Y}=Y)$ is small. It is possible to design some tricks to narrow down the candidate list, such as RRWithPrior [], which picks the candidates based on their prior probabilities. However, the performances under $\epsilon$-label DP with small $\epsilon$ are still far from the non-private baseline. From an information-theoretic perspective, a single scalar can only convey limited information [, ]. Therefore, as long as the label is transformed into a scalar, with increasing $K$, it is increasingly unlikely to maintain the statistical dependence between the original label and the privatized one, thus the model performance drops with $K$.

In this paper, we propose a *vector approximation* approach to solve the multi-class classification problem with large number of classes $K$ under label DP. To satisfy the privacy requirement, each label is transformed into a random vector $\mathbf{Z}=(Z(1),\ldots,Z(K))\in\{0,1\}^{K}$, and the transformation satisfies $\epsilon$-label DP. Intuitively, compared with scalar transformation, conversion of labels to multi-dimensional vectors preserves more information, which is especially important with large $K$, thus our method achieves a better performance.

We then move on to a deeper understanding of our new proposed approach. For a given feature vector $\mathbf{x}$, let $\Delta(\mathbf{x})$ be the maximum estimation error of regression function $\eta_{k}(\mathbf{x})$ over $k=1,\ldots,K$. Our analysis shows that as long as $\Delta(\mathbf{x})$ is smaller than the gap between the largest and second largest one among $\{\eta_{1}(\mathbf{x}),\ldots,\eta_{K}(\mathbf{x})\}$, the classifier will yield a Bayes optimal prediction. For statistical learning model, such as the nearest neighbor classifier, $\Delta(x)$ can be viewed as a union bound that only grows with $O(\sqrt{\ln K})$. For deep neural networks, while it is hard to analyze the growth rate of $\Delta(\mathbf{x})$ over $K$ rigorously, such growth rate is slow by intuition and experience [, , , ]. As a result, the classification performance of our approach only decreases slowly with $K$.

Finally, we conduct experiments on both synthesized data and standard benchmark datasets. The goal of using synthesized data is to display how the performance degrades with increasing number of classes $K$. The results show that with small $K$, our method achieves nearly the same results with existing approaches. However, with $K$ increases, our vector approximation method exhibits clear advantages. We then test the performance on some standard benchmark datasets, which also validate the effectiveness of our proposed method.

The contributions of this work are summarized as follows.

- •
We propose a vector approximation approach for learning with label DP. Our method is convenient to implement and introduces little additional computational complexity.
- •
We provide a brief theoretical analysis showing that the model performance remains relatively stable with increasing number of classes $K$.
- •
Numerical results on synthesized data validate the theoretical analysis, which shows that the performance of our method only decays slightly with $K$. Experiments on real datasets also validate the effectiveness of our proposed method.

## 2 Related Work

Central label DP. [] proposes an approach by clustering feature vectors, and then resampling each label based on the samples within the same cluster. [] proposes PATE, which splits the training datasets into several parts, and each part is used to train a teacher model. The labels are then altered by a majority vote from teacher models. Appropriate noise is added to the voting for privacy protection. Then PATE trains a student model using these altered labels. PATE is further improved in []. Despite achieving good performances, these methods are designed under central label DP requirement (see Definition 2), which requires that the curator is trusted, instead of protecting the privacy of each sample individually. Therefore, the accuracy scores are not comparable with ours.

Local label DP. Under local DP, labels are privatized before training to protect each sample individually. The performance of simple randomized response [] drops with $K$ sharply. Here we list two main modifications:

*1) RRWithPrior [].* This is an important improvement over the randomized response method, which partially alleviates the degradation of performance for large $K$. RRWithPrior picks transformed labels from some candidate labels with high conditional probabilities, instead of from all $K$ labels, thus it narrows down the list of candidates and somewhat reduces the label noise. However, this method requires multiple training stages to get a reliable estimate of prior probability. As a result, the samples in the beginning stages are used inefficiently. Moreover, RRWithPrior optimizes the probability of retaining the original label, i.e. $\text{P}(\tilde{Y}=Y)$, with $\tilde{Y}$ being the transformed one. Such optimization goal does not always align with the optimization of classification risk.

*2) ALIBI [].* This method conducts one-hot encoding first and then adds Laplacian noise to protect privacy. The design shares some similarities with our method. However, ALIBI generates outputs using Bayesian inference and normalizes them to $1$ using a softmax operation. Intuitively, such normalization causes bias. Moreover, the time complexity for transforming each label is $O(K^{2})$, thus the computation cost is high with large $K$. On the contrary, our vector approximation only requires $O(K)$ time for each label transformation.

Others. There are also some works on regression under label DP, such as [, ]. Moreover, some methods protect the privacy of training samples in a better way [, ]. Furthermore, [, ] discussed the case with both public and private features.

In this work, with the intuition of preserving more information, instead of transforming each label to another scalar label, our vector approximation approach privatizes each label into a vector $\mathbf{Z}$ that is not normalized to $1$. Compared with existing methods, our approach introduces little additional computational complexity, while achieving better performance with large number of classes $K$.

## 3 Preliminaries

### 3.1 Label DP

To begin with, we recall some concepts related to DP and introduce the notion of label DP.

###### Definition 1 .

(Differential Privacy (DP) []). Let $\epsilon\in\mathbb{R}{\geq 0}$. An algorithm $\mathcal{A}$ is $\epsilon$-differentially private (denoted as $\epsilon$-DP) if for any two adjacent datasets $D$ and $D^{\prime}$ and any $S\subseteq\operatorname{range}(\mathcal{A})$,

$$ $\displaystyle\text{P}(\mathcal{A}(D)\in S)\leq e^{\epsilon}\text{P}(\mathcal{A }(D^{\prime})\in S),$ (1) $$

in which two datasets $D$ and $D^{\prime}$ are adjacent if they differ on a single training sample, including both the feature vector and the label.

In supervised learning problems, the output of algorithm $\mathcal{A}$ is the trained model, while the input is the training dataset. Under Definition 1, both features and labels are privatized. However, in some scenarios, protecting features can be unnecessary, and we focus solely on the privacy of labels. Correspondingly, the notion of label DP is defined as follows:

###### Definition 2 .

(Label Differential Privacy (Label DP) []) An algorithm $\mathcal{A}$ is $\epsilon$-label differentially private (denoted as $\epsilon$-label DP) if for any two datasets $D$ and $D^{\prime}$ that differ on the label of a single training sample, and any $S\subseteq\operatorname{range}(\mathcal{A})$, (1) holds.

Compared with Definition 1, now the algorithm only needs to guarantee (1) when the label of a sample changes.

Throughout this paper, we consider the local DP setting, i.e. each label is transformed to a random variable (or vector) $\mathbf{Z}=M(Y)$ individually by a mechanism $M:\mathcal{Y}\rightarrow\mathcal{Z}$, in which $\mathcal{Y}$ denotes the set of all labels, while $\mathcal{Z}$ is the space of transformed variables or vectors. The local label DP is defined as follows.

###### Definition 3 .

A random mechanism $M:\mathcal{Y}\rightarrow\mathcal{Z}$ is $\epsilon$-local label DP if for any $y,y^{\prime}\in\mathcal{Y}$ and any $S\subseteq\mathcal{Z}$,

$$ $\displaystyle\text{P}(M(Y)\in S|Y=y)\leq e^{\epsilon}\text{P}(M(Y)\in S|Y=y^{ \prime}).$ (2) $$

Given $N$ training samples $(\mathbf{X}_{i},Y_{i})$, $i=1,\ldots,N$, the mechanism $M$ transforms $Y_{i}$ to $\mathbf{Z}_{i}$, $i=1,\ldots,N$. It can be easily shown that local label DP is a stronger privacy requirement compared with central label DP (Definition 2). To be more precise, as long as $M$ is local $\epsilon$-label DP, then any learning algorithms using $(\mathbf{X}_{i},\mathbf{Z}_{i})$, $i=1,\ldots,N$ as training samples are central $\epsilon$-label DP.

###### Definition 1 .

###### Definition 2 .

###### Definition 3 .

### 3.2 Classification Risk

Now we describe the goal and the evaluation metric of the classification task. For a $K$-class classification problem, the goal is to build a classifier that predicts the label $Y\in\mathcal{Y}=[K]$, in which $[K]=\{1,\ldots,K\}$, given a feature vector $\mathbf{X}\in\mathcal{X}\subseteq\mathbb{R}^{d}$. In this work, we use $0-1$ loss for classification. For a classifier $\hat{Y}=c(\mathbf{X})$, in which $\hat{Y}$ is the predicted label, the risk is defined as the expectation of the loss function:

$$ $\displaystyle R[\hat{Y}]=\mathbb{E}[\mathbf{1}(\hat{Y}\neq Y)]=\text{P}(c( \mathbf{X})\neq Y).$ (3) $$

Define $K$ functions, named $\eta_{1},\ldots,\eta_{K}$, as the conditional class probability given a specific feature vector $\mathbf{x}$:

$$ $\displaystyle\eta_{j}(\mathbf{x})=\text{P}(Y=j|\mathbf{X}=\mathbf{x}),j=1, \ldots,K.$ (4) $$

If $\eta_{k}$ is known, then for any test sample with feature vector $\mathbf{x}$, the classifier can make the prediction be the class with maximum conditional probability. Therefore, the Bayes optimal classifier $c^{*}$ is

$$ $\displaystyle c^{*}(\mathbf{x})=\underset{j\in[K]}{\arg\max}\;\eta_{j}(\mathbf {x}).$ (5) $$

The risk corresponds to the ideal classifier $c^{*}$, called Bayes risk, is

$$ $\displaystyle R^{*}=\text{P}(c^{*}(\mathbf{X})\neq Y).$ (6) $$

Bayes risk is the minimum risk among all possible classifiers. In reality, $\eta_{k}$ is unknown. Therefore, for a practical classifier that is trained using finite number of samples, there is some gap between its risk and the Bayes risk. Such gap $R-R^{*}$ is called the excess risk. Denote

$$ $\displaystyle\eta^{*}(\mathbf{x})=\underset{j}{\max}\;\eta_{j}(\mathbf{x})$ (7) $$

as the maximum of $m$ regression functions. The next proposition gives an expression of the excess risk.

###### Proposition 1 .

For any practical classifier $c:\mathcal{X}\rightarrow\mathcal{Y}$, the excess risk is

$$ $\displaystyle R-R^{*}=\int(\eta^{*}(\mathbf{x})-\mathbb{E}[\eta_{c(\mathbf{x}) }(\mathbf{x})])f(\mathbf{x})d\mathbf{x},$ (8) $$

in which $R^{*}$ is the Bayes risk, and $f$ is the probability density function (pdf) of feature vector $\mathbf{X}$, $\eta_{c(\mathbf{x})}(\mathbf{x})$ is just $\eta_{j}(\mathbf{x})$ with $j=c(\mathbf{x})$. Note that $c(\mathbf{x})$ is random due to the randomness of the training dataset. Therefore the expectation in (8) is taken over $N$ training samples.

###### Proof.

From (5) and (9), the Bayes risk is

$$ $\displaystyle R^{*}=\text{P}(Y\neq c^{*}(\mathbf{X}))=\int\text{P}(Y\neq c^{*} (\mathbf{x})|\mathbf{X}=\mathbf{x})f(\mathbf{x})d\mathbf{x}=\int(1-\eta^{*}( \mathbf{x}))f(\mathbf{x})d\mathbf{x}.$ (9) $$

The actual risk for a practical classifier is

$$ $\displaystyle R=\text{P}(Y\neq c(\mathbf{X}))=\mathbb{E}\left[\int\left(1-\eta _{c(\mathbf{x})}(\mathbf{x})\right)f(\mathbf{x})d\mathbf{x}\right].$ (10) $$

From (10) and (9),

$$ $\displaystyle R-R^{*}=\int(\eta^{*}(\mathbf{x})-\mathbb{E}[\eta_{c(\mathbf{x}) }(\mathbf{x})])f(\mathbf{x})d\mathbf{x}.$ (11) $$

The proof is complete.
∎

###### Proposition 1 .

###### Proof.

### 3.3 Notations

Finally, we clarify the notations. Throughout this paper, $a\wedge b=\min(a,b)$, $a\vee b=\max(a,b)$. We claim that $a\lesssim b$ if there exists a constant $C$ such that $a\leq Cb$. Notation $\gtrsim$ is defined similarly. $\operatorname{Lap}(\lambda)$ denotes the Laplacian distribution with parameter $\lambda$, whose probability density function (pdf) is $f(u)=e^{-|u|/\lambda}/(2\lambda)$. Furthermore, we use capital letters to denote random variables, and lowercase letters to denote values.

## 4 The Proposed Method

Here we present and explain our new method. Section 4.1 shows the basic idea. Section 4.2 gives an intuitive analysis. Finally, practical implementation with deep learning is discussed in Section 4.3.

### 4.1 Method description

Instead of transforming a label to another scalar, we construct a random vector $\mathbf{Z}\in\{0,1\}^{K}$, which can preserve more information than a random one-dimensional scalar. To be more precise, denote $Z(j)$ as the $j$-th element of $\mathbf{Z}$.

Given the original label $Y=j^{\prime}$, let the conditional distribution of $Z(j)$ be

$$ $\displaystyle\text{P}(Z(j)=1|Y=j^{\prime})=\left\{\begin{array}[]{ccc}\frac{e^ {\frac{\epsilon}{2}}}{1+e^{\frac{\epsilon}{2}}}&\text{if}&j=j^{\prime}\\ \frac{1}{1+e^{\frac{\epsilon}{2}}}&\text{if}&j\neq j^{\prime},\end{array}\right.$ (14) $$

and

$$ $\displaystyle\text{P}(Z(j)=0|Y=j^{\prime})=\left\{\begin{array}[]{ccc}\frac{1} {1+e^{\frac{\epsilon}{2}}}&\text{if}&j=j^{\prime}\\ \frac{e^{\frac{\epsilon}{2}}}{1+e^{\frac{\epsilon}{2}}}&\text{if}&j\neq j^{ \prime}.\end{array}\right.$ (17) $$

The privacy mechanism described by (14) and (17) is a simple form of RAPPOR [], which is also shown to be optimal in distribution estimation []. It is ensured that conditional on $Y$, $Z(j)$ for different $j$ are independent. The following theorem shows the DP property.

###### Theorem 1 .

The privacy mechanism (14), (17) is $\epsilon$-local label DP.

###### Proof.

For any $j$, $j^{\prime}$ and any $\mathbf{z}\in\{0,1\}^{K}$, we have

$$ $\displaystyle\frac{\text{P}(\mathbf{Z}=\mathbf{z}|Y=j)}{\text{P}(\mathbf{Z}= \mathbf{z}|Y=j^{\prime})}$ $\displaystyle=$ $\displaystyle\Pi_{l}\frac{\text{P}(Z(l)=z(l)|Y=j)}{\text{P}(Z(l)=z(l)|Y=j^{ \prime})}$ (18) $\displaystyle=$ $\displaystyle\frac{\text{P}(Z(j)=z(j)|Y=j)\text{P}(Z(j^{\prime})=z(j^{\prime}) |Y=j)}{\text{P}(Z(j)=z(j)|Y=j^{\prime})\text{P}(Z(j^{\prime})=z(j^{\prime})|Y= j^{\prime})}$ $\displaystyle\leq$ $\displaystyle(e^{\frac{\epsilon}{2}})^{2}=e^{\epsilon},$ $$

in which the first step holds since $Z(l)$ are conditional independent on $l$. The second step holds because changing $Y$ from $j$ to $j^{\prime}$ does not affect the conditional distributions of elements of $\mathbf{Z}$ other than the $j$-th and the $j^{\prime}$-th one, i.e. $\text{P}(Z(l)=z(l)|Y=j)=\text{P}(Z(l)=z(l)|Y=j^{\prime})$ for $l\notin\{j,j^{\prime}\}$. Therefore, we only need to bound the ratio of the probability mass of the $j$-th and $j^{\prime}$-th element. The last step holds since (14) and (17) ensures that $\text{P}(Z(j)=z(j)|Y=j)/\text{P}(Z(j)=z(j)|Y=j^{\prime})\leq e^{\epsilon/2}$. Therefore, the local label DP requirement in Definition 3 is satisfied. ∎

Following above procedures, the labels of all $N$ training samples $Y_{1},\ldots,Y_{N}$ are transformed into $N$ vectors $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{N}$. From (5), the optimal prediction is the class $j$ that maximizes $\eta_{j}(\mathbf{x})$. However, $\eta_{j}$ is unknown, and we would like to find a substitute. Towards this end, we train a model that can be either parametric (linear models, neural networks, etc.) or nonparametric ($k$ nearest neighbors, tree-based methods, etc.), to approximate $\mathbf{Z}_{1},\ldots,\mathbf{Z}_{N}$. The model output can be expressed by

$$ $\displaystyle\mathbf{g}(\mathbf{x})=(g_{1}(\mathbf{x}),\ldots,g_{K}(\mathbf{x} )).$ (19) $$

$g_{j}(\mathbf{x})$ denotes the $j$-th element of the output vector. With a good model and sufficient training samples, $g_{j}(\mathbf{x})$ approximates $\mathbb{E}[Z(j)|\mathbf{X}=\mathbf{x}]$. It is expected that picking $j$ that maximizes $\eta_{j}(\mathbf{x})$ is nearly equivalent to maximizing $g_{j}(\mathbf{x})$. Therefore, in the prediction stage, for any test sample whose feature vector is $\mathbf{x}$, the predicted label is

$$ $\displaystyle\hat{Y}=c(\mathbf{x}):=\underset{j\in[K]}{\arg\max}\;g_{j}( \mathbf{x}).$ (20) $$

###### Theorem 1 .

###### Proof.

### 4.2 A Brief Analysis

Now we briefly explain why our new method works. Define

$$ $\displaystyle\tilde{\eta}_{j}(\mathbf{x}):=\text{P}(Z(j)=1|\mathbf{X}=\mathbf{ x}).$ (21) $$

It is expected that the model output $(g_{1}(\mathbf{x}),\ldots,g_{K}(\mathbf{x}))$ approximates $(\tilde{\eta}_{1}(\mathbf{x}),\ldots,\tilde{\eta}_{K}(\mathbf{x}))$. Ideally, $g_{j}(\mathbf{x})=\tilde{\eta}_{j}(\mathbf{x})$, then from (20), $c(\mathbf{x})=\arg\max_{j}\tilde{\eta}_{j}(\mathbf{x})=\arg\max_{j}\eta_{j}(
\mathbf{x})=c^{*}(\mathbf{x})$ is the optimal prediction. However, in reality, there are some gaps between $(g_{1}(\mathbf{x}),\ldots,g_{K}(\mathbf{x}))$ and $(\tilde{\eta}_{1}(\mathbf{x}),\ldots,\tilde{\eta}_{K}(\mathbf{x}))$, thus the prediction may be suboptimal. To quantify the effect of approximation error on the excess risk, denote $\Delta(\mathbf{x})$ as the maximum approximation error for all classes, i.e.

$$ $\displaystyle\Delta(\mathbf{x})=\underset{j\in[K]}{\max}|g_{j}(\mathbf{x})- \tilde{\eta}_{j}(\mathbf{x})|.$ (22) $$

Then we show the following theorem.

###### Theorem 2 .

Denote $\eta_{s}(\mathbf{x})$ as the second largest conditional class probability given $\mathbf{x}$, i.e.

$$ $\displaystyle\eta_{s}(\mathbf{x})=\underset{j\neq c^{*}(\mathbf{x})}{\max}\; \eta_{j}(\mathbf{x}).$ (23) $$

Then

$$ $\displaystyle R-R^{*}\leq\int\mathbb{E}\left[2\Delta_{\epsilon}(\mathbf{x}) \mathbf{1}(\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})\leq 2\Delta_{\epsilon}( \mathbf{x}))\right]f(\mathbf{x})d\mathbf{x},$ (24) $$

in which

$$ $\displaystyle\Delta_{\epsilon}(\mathbf{x}):=\frac{e^{\frac{\epsilon}{2}}+1}{e^ {\frac{\epsilon}{2}}-1}\Delta(\mathbf{x}).$ (25) $$

###### Proof.

From Proposition 1, the prediction is suboptimal if $c(\mathbf{x})\neq c^{*}(\mathbf{x})$, which happens only if

$$ $\displaystyle g_{c(\mathbf{x})}(\mathbf{x})\geq g_{c^{*}(\mathbf{x})}(\mathbf{ x}).$ (26) $$

From the definition of $\Delta(\mathbf{x})$ in (22), (26) indicates that

$$ $\displaystyle\tilde{\eta}_{c(\mathbf{x})}(\mathbf{x})\geq\tilde{\eta}^{*}( \mathbf{x})-2\Delta(\mathbf{x}).$ (27) $$

From (14), (17) and (21), for all $j\in[K]$,

$$ $\displaystyle\tilde{\eta}_{j}(\mathbf{x})$ $\displaystyle=$ $\displaystyle\sum_{l=1}^{K}\text{P}(Y=l|\mathbf{X}=\mathbf{x})\text{P}(Z(j)=1| Y=l)$ (28) $\displaystyle=$ $\displaystyle\frac{1}{1+e^{\epsilon/2}}\sum_{l\neq j}\eta_{l}(\mathbf{x})+ \frac{e^{\epsilon/2}}{1+e^{\epsilon/2}}\eta_{j}(\mathbf{x})$ $\displaystyle=$ $\displaystyle\frac{1}{1+e^{\epsilon/2}}+\frac{e^{\epsilon/2}-1}{e^{\epsilon/2} +1}\eta_{j}(\mathbf{x}),$ $$

in which the last step holds since from (4), $\sum_{j}\eta_{j}(\mathbf{x})=1$. Therefore, (27) is equivalent to

$$ $\displaystyle\eta_{c(\mathbf{x})}(\mathbf{x})\geq\eta^{*}(\mathbf{x})-2\Delta_ {\epsilon}(\mathbf{x}),$ (29) $$

in which $\Delta_{\epsilon}$ has been defined in (25). Note that for all $j\neq c^{*}(\mathbf{x})$, the value of $\eta_{j}(\mathbf{x})$ is at most $\eta_{s}(\mathbf{x})$ (recall the definition (23)). Therefore, a suboptimal prediction $c(\mathbf{x})\neq c^{*}(\mathbf{x})$ can happen only if

$$ $\displaystyle\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})\leq 2\Delta_{\epsilon}( \mathbf{x}).$ (30) $$

(30) suggests that as long as the gap between the largest and the second largest conditional class probability is large enough with respect to $\epsilon$ and the function approximation error $\Delta(\mathbf{x})$, the classifier will make an optimal prediction, i.e. $\hat{Y}=c^{*}(\mathbf{x})$. Hence

$$ $\displaystyle\eta^{*}(\mathbf{x})-\eta_{c(\mathbf{x})}(\mathbf{x})\leq\left\{ \begin{array}[]{ccc}2\Delta_{\epsilon}(\mathbf{x})&\text{if}&\eta^{*}(\mathbf{ x})-\eta_{s}(\mathbf{x})\leq 2\Delta_{\epsilon}(\mathbf{x})\\ 0&\text{if}&\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})>2\Delta_{\epsilon}( \mathbf{x}).\end{array}\right.$ (33) $$

Recall Proposition 1,

$$ $\displaystyle R-R^{*}$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\left(\eta^{*}(\mathbf{x})-\mathbb{E}[\eta_{c( \mathbf{x})}(\mathbf{x})]\right)f(\mathbf{x})d\mathbf{x}\right]$ (34) $\displaystyle\leq$ $\displaystyle\mathbb{E}\left[\int\mathbf{1}\left(\eta^{*}(\mathbf{x})-\eta_{s} (\mathbf{x})\leq 2\Delta_{\epsilon}(\mathbf{x})\right)\cdot 2\Delta_{\epsilon} (\mathbf{x})f(\mathbf{x})d\mathbf{x}\right].$ $$

The proof of (24) is complete.
∎

Here we interpret Theorem 2. As a union bound on the estimation error of all classes, $\Delta(\mathbf{x})$ usually only grows slightly with $K$. For example, in Appendix B, we show that for $k$ nearest neighbor classifiers, $\Delta(\mathbf{x})$ grows with $\sqrt{\ln K}$. Deep learning models are much harder to analyze rigorously [], thus we only provide an intuitive argument in Appendix B to show that with increasing $K$, $\Delta$ remains nearly stable. Therefore, from (24), if the shape of $\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})$ is nearly fixed, then the excess error will not grow significantly with $K$. This happens if $K$ is large but the conditional class probabilities given $\mathbf{x}$ for most classes are very small.

###### Theorem 2 .

###### Proof.

### 4.3 Practical Implementation

Finally, we discuss the practical implementation with deep learning. (19) contains $K$ models $g_{1},\ldots,g_{K}$. Practically, it is not necessary to construct $K$ neural networks. For the convenience of implementation, we can let $\mathbf{w}_{1},\ldots,\mathbf{w}_{K}$ share most parameters, except the last layer. Therefore, we only need to construct one neural network. The last layer can use sigmoid activation to match the privatized vector $\mathbf{Z}$ using binary cross entropy loss. This will simplify the implementation and avoid extra computation costs. Compared with non-private learning, our method only introduces $O(NK)$ additional time complexity for label transformation.

Figure: (a) Scalar approximation.
Refer to caption: x1.png

Here a sigmoid activation at the last layer can not be replaced by softmax, since the randomized vector $\mathbf{Z}$ does not sum to $1$. Instead, $\mathbf{Z}$ may contain multiple elements with value $1$, thus we need to use sigmoid activation so that the output $(g_{1}(\mathbf{x}),\ldots,g_{K}(\mathbf{x}))$ can approximate $(\tilde{\eta}_{1}(\mathbf{x}),\ldots,\tilde{\eta}_{K}(\mathbf{x}))$.

Now we summarize the differences between the randomized response method (including its modifications []) and our new approach. The differences are illustrated in Figure 1. Instead of randomly flipping the label and then conducting one-hot encoding, we use a random vectorization according to (14) and (17). The resulting vector may contain multiple elements whose values are $1$. The activation of the last layer is also changed to sigmoid. Correspondingly, the loss function for model training is the binary cross entropy loss, instead of the multi-class version.

## 5 Numerical Experiments

### 5.1 Synthesized Data

To begin with, we show some results using randomly generated training samples to show how is the accuracy affected by increasing the number of classes $K$. Samples in all $K$ classes are normally distributed with mean $\mu_{i}$, $i=1,\ldots,K$ and standard deviation $\sigma$. $\mu_{i}$ are set to be equally spaced on a unit circle. For all experiments, we generate $N=10000$ training samples. We use the $k$ nearest neighbor method with $k=200$ as the base learner of all models. We compare our method with the randomized response, LP-2ST (which uses RRWithPrior randomization) [] and ALIBI []. All methods satisfy the local label DP requirement with $\epsilon=1$. The results are shown in Figure 2, in which each dot represents the average accuracy score over $1,000$ random trials.

Figure: (a) $\sigma=0.05$.
Refer to caption: x3.png

Figure 2(a) shows the result using $\sigma=0.05$. The result shows that with small $K$, our method achieves nearly the same accuracy as existing methods. However, with large $K$, the vector approximation method (the red line) shows clear advantage over other methods. Recall that our theoretical analysis shows that if $\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})$ is fixed, the excess risk will not grow significantly with the number of classes $K$. However, from Figure 2(a), the accuracy of vector approximation still decreases with $K$. Our explanation is that with large $K$, there is a stronger overlap between distributions for neighboring classes, thus $\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})$ becomes lower on average. According to Theorem 2, the excess risk is also larger correspondingly. In Figure 2(b), we show the result with $\sigma=2/K$, so that $\eta^{*}(\mathbf{x})-\eta_{s}(\mathbf{x})$ remains nearly the same with increasing $K$. In this case, with increasing $K$, the accuracy of our vector approximation approach remains stable.

In general, the experiment results with synthesized data validate our theoretical analysis and show that our method improves existing methods for cases with large number of classes $K$. Moreover, we show some additional experiments in Appendix A with other parameters, which validates that our method consistently outperforms existing approaches with large $K$.

### 5.2 Real Data

Now we evaluate our new method on standard benchmark datasets that have been widely used in previous works on differentially private machine learning, including MNIST [], Fashion MNIST [] CIFAR-10 and CIFAR-100[]. For the MNIST and Fashion MNIST datasets, we use a simple convolutional neural network composed of two convolution and pooling layers with dropout rate $0.5$, which achieves $99\%$ accuracy for non-private training samples. For CIFAR-10 and CIFAR-100, we use ResNet-18, which achieves $95\%$ and $76\%$ accuracy for non-private data, respectively. In recent years, many new models have emerged, such that the state-of-the-art accuracies on CIFAR-10 and CIFAR-100 have been greatly improved, such as vision transformer []. However, we still use ResNet-18 for a fair comparison with existing works.

**Table 1: Experiments on MNIST and Fashion MNIST dataset under different privacy levels using a simple CNN. The accuracy for non-private data is $99\%$.**
| $\epsilon$ | 0.2 | 0.3 | 0.5 | 0.7 | 1.0 | 2.0 |
| --- | --- | --- | --- | --- | --- | --- |
| RR | 58.0 | 64.1 | 74.9 | 89.5 | 95.3 | 97.7 |
| LP-2ST | 47.5 | 64.3 | 81.4 | 87.9 | 91.8 | 97.7 |
| ALIBI | 50.9 | 55.1 | 84.3 | 89.4 | 94.5 | 97.6 |
| Ours | 63.9 | 78.4 | 87.9 | 93.4 | 96.2 | 97.4 |

Table 1 shows the results on MNIST and Fashion MNIST datasets. The number in the table refers to the accuracy, i.e. percentage of correct predictions. LP-2ST is the method in [] using two stages. ALIBI comes from []. The results show that our new method outperforms existing methods in general. With large $\epsilon$, such that the accuracy is already close to the non-private case, the accuracy may be slightly lower than existing methods due to some implementation details and some random factors.

**Table 2: Experiments on CIFAR-10 dataset using ResNet-18. The accuracy for non-private data is $95\%$.**
| $\epsilon$ | 1 | 2 | 3 | 4 |
| --- | --- | --- | --- | --- |
| LP-1ST | 60.0 | 82.4 | 89.9 | 92.6 |
| LP-2ST | 63.7 | 86.1 | 92.2 | 93.4 |
| LP-1ST$\star$ | 67.6 | 84.0 | 90.2 | 92.8 |
| LP-2ST$\star$ | 70.2 | 87.2 | 92.1 | 93.5 |
| ALIBI | 71.0 | 84.2(^1^11Here $\epsilon=2.1$, slightly higher than $2$. This result comes from [], Table 1.) | - | - |
| Ours | 75.1 | 91.6 | 92.7 | 93.2 |

Table 2 shows the result with the CIFAR-10 dataset. In the table, LP-1ST$\star$ and LP-2ST$\star$ refer to the LP-1ST and LP-2ST methods, respectively, in which models have been pretrained with the CIFAR-100 dataset, which is regarded as public and no privacy protection is needed. Such setting follows []. The results of the first four rows of Table 2 come from [], Table 1. The fifth row is the result of ALIBI, which comes from [], Table 1. For the CIFAR-10 dataset, our method outperforms existing approaches with small $\epsilon$. Note that our method does not use pre-training. However, the results are still better than existing methods even with pre-training. Similar to the experiment of the MNIST dataset, the advantage of our method becomes less obvious when $\epsilon$ is large, and the accuracies of existing methods are already close to the non-private baseline.

Table 3 shows the result with the CIFAR-100 dataset. The results of LP-2ST and ALIBI come from Table 2 in [] and [], respectively. The results show that our method significantly outperforms LP-2ST and ALIBI. The advantage of our method is especially obvious with small $\epsilon$. It is worth mentioning that ALIBI calculates the soft label instead of conducting just a label flipping. The soft label can be expressed by a vector, thus the idea of ALIBI shares some similarity with our vector approximation method. As a result, ALIBI performs significantly better than LP-2ST. However, from Table 3, our method also outperforms ALIBI.

**Table 3: Experiments on CIFAR-100 dataset using ResNet-18. The accuracy for non-private data is $76\%$.**
| $\epsilon$ | 2 | 3 | 4 | 5 | 6 | 8 |
| --- | --- | --- | --- | --- | --- | --- |
| LP-2ST | - | 28.7 | 50.2 | 63.5 | 70.6 | 74.1 |
| ALIBI | - | 55.0 | 65.0 | 69.0 | 71.5 | 74.4 |
| Ours | 64.4 | 67.7 | 71.8 | 73.8 | 74.1 | 74.4 |

Here we summarize the experimental results. The synthesized data shows that our vector approximation method has relatively stable performance with the increase of the number of classes $K$. As a result, with large $K$, our method has a significantly better performance compared with existing methods. Such observation agrees well with our theoretical analysis in Section 4.2. We have also tested the results using benchmark datasets, which validate our method in real scenarios. It worths mentioning that several works on central label DP achieve better accuracy than those reported here, such as PATE [] and its improvement in []. As a weaker privacy requirement compared with local label DP, these results under central label DP are not comparable to our results.

## 6 Conclusion

In this paper, we have proposed a new method for classification with label differential privacy based on vector approximation. The general idea is to generate a noisy random vector first to protect the privacy of labels and train the model to match the privatized vector. Compared with existing scalar approximation methods, which conduct label flipping and let the flipped label match the model outputs, our method has better theoretical convergence properties and empirical performances. In particular, our method solves the problem of the degradation of utility with large number of classes $K$. Our analysis suggests that the prediction is optimal as long as the gap between the largest and second largest conditional class probability is enough, thus the risk only grows slightly with $K$. Moreover, our method is easier to implement and only requires $O(NK)$ time for label privatization. Numerical experiments with both synthesized data and standard benchmark datasets validate the effectiveness of our proposed method.

Limitations: The limitations of our work include the following aspects. Firstly, the privacy mechanism is not designed optimally, and it is possible to improve it further. For example, one may consider using asymmetric flipping probabilities, instead of (14) and (17). Secondly, our work is currently restricted to classification cases. It is possible to extend to regression problems in the future. Finally, the performance at low privacy regime (i.e. large $\epsilon$) may be further improved.

## Appendix A Additional Numerical Experiments

Here we present some additional experiments.

Higher $\epsilon$. Figure 2 shows the result with $\epsilon=1$. Now we set $\epsilon=2$, and the results are shown in Figure 3.

Figure: (a) $\sigma=0.05$.
Refer to caption: x5.png

With a weaker privacy requirement $\epsilon=2$, the performances of all methods become better. The vector approximation method still outperforms existing methods.

Other $k$. Now we still use $\epsilon=1$. However, recall that previous experiments use $k=200$. Now we use $k$ nearest neighbor method with $k=100$ as the base learner.

Figure: (a) $\sigma=0.05$.
Refer to caption: x7.png

## Appendix B Further Arguments about Approximation Error

### B.1 k 𝑘 k italic_k Nearest Neighbor Method

Now we bound $\Delta(\mathbf{x})$ for $k$ nearest neighbor approach, which has been extensively analyzed in literatures [, , , , , ](^2^22To avoid confusion, we emphasize that lowercase $k$ is the number of nearest neighbor used in the kNN method, while $K$ is the number of classes.). Recall that the output structure expressed in (19). For the kNN classifier, let

$$ $\displaystyle g_{j}(\mathbf{x})=\frac{1}{k}\sum_{i\in\mathcal{N}_{k}(\mathbf{x })}Z_{i}(j),$ (35) $$

in which $\mathcal{N}_{k}(\mathbf{x})$ is the set of $k$ nearest neighbors of $\mathbf{x}$ among $\{\mathbf{X}_{1},\ldots,\mathbf{X}_{N}\}$.

Define
$p_{r}(\mathbf{x})=\int_{B(\mathbf{x},r)}f(\mathbf{u})d\mathbf{u}$
as the probability mass of $B(\mathbf{x},r)$, in which $f$ is the pdf of feature vector $\mathbf{X}$. Define

$$ $\displaystyle r_{0}(\mathbf{x})=\inf\left\{r|p_{r}(\mathbf{x})\geq\frac{2k}{N} \right\}.$ (36) $$

Define
$\rho(\mathbf{x})=\underset{i\in\mathcal{N}_{k}(\mathbf{x})}{\max}\left\lVert
\mathbf{X}_{i}-\mathbf{x}\right\rVert$
as the kNN distance. Assume that $\eta_{j}(\mathbf{x})$ is $L$-Lipschitz. Now we bound the approximation error as follows.

$$ $\displaystyle|g_{j}(\mathbf{x})-\eta_{j}(\mathbf{x})|$ $\displaystyle=$ $\displaystyle\left|\frac{1}{k}\sum_{i\in\mathcal{N}_{k}(\mathbf{x})}Z_{i}(j)- \tilde{\eta}_{j}(\mathbf{x})\right|$ (37) $\displaystyle\leq$ $\displaystyle\left|\frac{1}{k}\sum_{i\in\mathcal{N}_{k}(\mathbf{x})}(Z_{i}(j)- \tilde{\eta}_{j}(\mathbf{X}_{i}))\right|+\left|\frac{1}{k}\sum_{i\in\mathcal{N }_{k}(\mathbf{x})}(\tilde{\eta}_{j}(\mathbf{X}_{i})-\tilde{\eta}_{j}(\mathbf{x }))\right|$ $\displaystyle\leq$ $\displaystyle\left|\frac{1}{k}\sum_{i\in\mathcal{N}_{k}(\mathbf{x})}(Z_{i}(j)- \tilde{\eta}_{j}(\mathbf{X}_{i}))\right|+\frac{e^{\epsilon/2}-1}{e^{\epsilon/2 }+1}L\rho(\mathbf{x}),$ $$

in which the last step uses (28). From Hoeffding’s inequality,

$$ $\displaystyle\text{P}\left(\left|\frac{1}{k}\sum_{i\in\mathcal{N}_{k}(\mathbf{ x})}(Z_{i}(j)-\tilde{\eta}_{j}(\mathbf{X}_{i}))\right|>\sqrt{\frac{1}{2k}\ln \frac{2K}{\delta}}\right)\leq\frac{\delta}{K}.$ (38) $$

Moreover, define $n(\mathbf{x},r)$ as the number of samples in $B(\mathbf{x},r)$, then

$$ $\displaystyle\text{P}(\rho(\mathbf{x})>r_{0}(\mathbf{x}))$ $\displaystyle\leq$ $\displaystyle\text{P}(n(\mathbf{x},r_{0}(\mathbf{x}))<k)$ (39) $\displaystyle\leq$ $\displaystyle e^{-Np_{r_{0}(\mathbf{x})}(\mathbf{x})}\left(\frac{eNp_{r_{0}( \mathbf{x})}(\mathbf{x})}{k}\right)^{k}$ $\displaystyle=$ $\displaystyle e^{-2k}(2e)^{k}=e^{-(1-\ln 2)k}.$ $$

From (37), (38) and (39), consider the definition of $\Delta$ in (22), with probability at least $1-\delta-e^{-(1-\ln 2)k}$,

$$ $\displaystyle\Delta(\mathbf{x})\leq\sqrt{\frac{1}{2k}\ln\frac{2K}{\delta}}+ \frac{e^{\epsilon/2}-1}{e^{\epsilon/2}+1}Lr_{0},$ (40) $$

which grows with $\sqrt{\ln K}$.

### B.2 Neural Network

Neural networks are much harder to analyze compared with traditional methods like kNN. Here we just provide an argument to intuitively show that the approximation $g_{j}(\mathbf{x})\approx\tilde{\eta}_{j}(\mathbf{x})$ holds.

In deep neural network models, the parameters can be expressed as $\mathbf{w}=(\mathbf{w}_{1},\ldots,\mathbf{w}_{K})\in\mathcal{W}_{1}\times
\ldots\times\mathcal{W}_{K}$, and the output (19) is now $g_{j}(\mathbf{x})=h_{j}(\mathbf{w}_{j}^{*},\mathbf{x})$, in which $h_{j}$ is the output of $j$-th neural network model. $\mathbf{w}_{j}^{*}$ is trained using $(\mathbf{X}_{i},\mathbf{Z}_{i})$, $i=1,\ldots,N$ to minimize the empirical loss:

$$ $\displaystyle\mathbf{w}_{j}^{*}=\underset{\mathbf{w}_{j}\in\mathcal{W}_{j}}{ \arg\min}\;\frac{1}{N}\sum_{i=1}^{N}l(h_{j}(\mathbf{w}_{j},\mathbf{X}_{i}),Z_{ i}(j)),j\in[K],$ (41) $$

in which $l$ is the surrogate loss function used for training. A typical choice of $l$ is the binary cross entropy loss.

Let
$\mathcal{G}_{j}=\{h_{j}(\mathbf{w}_{j},\cdot)|\mathbf{w}_{j}\in\mathcal{W}_{j}\}$
be the set of all possible functions $g_{j}$ parameterized by $\mathbf{w}_{j}$. Then from (41),

$$ $\displaystyle\frac{1}{N}\sum_{i=1}^{N}l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{X}_{i }),Z_{i}(j))=\underset{u\in\mathcal{G}_{j}}{\min}\frac{1}{N}\sum_{i=1}^{N}l(u( \mathbf{X}_{i}),Z_{i}(j)).$ (42) $$

Denote $\mathcal{G}=\{g:\mathcal{X}\rightarrow[0,1]\}$ as the set of all functions mapping from $\mathcal{X}$ to $[0,1]$. Then

$$ $\displaystyle\mathbb{E}[l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{X}),Z(j))]$ $\displaystyle\overset{(a)}{\approx}$ $\displaystyle\underset{u\in\mathcal{G}_{j}}{\min}\;\mathbb{E}[l(u(\mathbf{X}), Z(j))]$ (43) $\displaystyle\overset{(b)}{\approx}$ $\displaystyle\underset{u\in\mathcal{G}}{\min}\;\mathbb{E}[l(u(\mathbf{X}),Z(j))]$ $\displaystyle=$ $\displaystyle\mathbb{E}\left[\underset{u\in\mathcal{G}}{\min}\;\mathbb{E}[l(u( \mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]\right].$ $$

In (43), (a) holds because from weak law of large number, the right hand side of (42) converges to its expectation. For the left side of (42), theories about generalization has been widely established []. The generalization gap converges to zero with the increase of sample size $N$. (b) uses the universal approximation theorem [, , ]. For a neural network that is sufficiently wide and deep, each function in $\mathcal{G}$ can be closely approximated by a function in $\mathcal{G}_{j}$.

From now on, suppose that $l$ is the binary cross entropy loss, i.e. $l(q,p)=-p\ln q-(1-p)\ln(1-q)$. It can be shown that $\tilde{\eta}_{j}(\mathbf{x})$ is the minimizer of $\mathbb{E}[l(u(\mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]$. Recall that $\mathcal{G}$ is defined as the set of all functions mapping from $\mathcal{X}$ to $[0,1]$. Hence, $g_{j}(\mathbf{w}_{j}^{*})\in\mathcal{G}$. This implies

$$ $\displaystyle\mathbb{E}\left[l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{X}),Z(j)) \right]\geq\mathbb{E}\left[\underset{u\in\mathcal{G}}{\min}\mathbb{E}[l(u( \mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]\right].$ (44) $$

From (43), the left hand side of (44) is not larger than the right hand side too much. Therefore, there exists a $\delta>0$ such that

$$ $\displaystyle\mathbb{E}\left[\underset{u\in\mathcal{G}}{\min}\mathbb{E}[l(u( \mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]\right]\leq\mathbb{E}\left[l(g_{j}( \mathbf{w}_{j}^{*},\mathbf{X}),Z(j))\right]\leq\mathbb{E}\left[\underset{u\in \mathcal{G}}{\min}\mathbb{E}[l(u(\mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}] \right]+\delta.$ (45) $$

Recall the steps in (43). $\delta$ goes to zero with the increase of model complexity and sample size $N$.

Assume that $g_{j}(\mathbf{w}_{j}^{*},\mathbf{x})$ is continuous in $\mathbf{x}$. Then $l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{x}),Z(j))$ is also continuous in $\mathbf{x}$. As a result, $l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{x}),Z(j))$ can not be much larger than $\min_{u\in\mathcal{G}}\mathbb{E}[l(u(\mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]$, otherwise there will be a neighborhood of $\mathbf{x}$ called $\mathcal{N}(\mathbf{x})$, such that $l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{x}^{\prime}),Z(j))$ is much larger than $\min_{u\in\mathcal{G}}\mathbb{E}[l(u(\mathbf{x}^{\prime}),Z(j))|\mathbf{X}=
\mathbf{x}^{\prime}]$ for all $\mathbf{x}^{\prime}\in\mathcal{N}(\mathbf{x})$, which violates the second inequality in (45). Therefore,

$$ $\displaystyle\mathbb{E}[l(g_{j}(\mathbf{w}_{j}^{*},\mathbf{x}),Z(j))|\mathbf{X }=\mathbf{x}]\approx\underset{u\in\mathcal{G}}{\min}\mathbb{E}[l(u(\mathbf{x}) ,Z(j))|\mathbf{X}=\mathbf{x}].$ (46) $$

Recall that $l$ denotes the binary cross entropy loss, thus

$$ $\displaystyle l(u(\mathbf{x}),Z(j))=-Z(j)\ln u(\mathbf{x})-(1-Z(j))\ln(1-u( \mathbf{x})).$ (47) $$

Recall the definition of $\tilde{\eta}_{j}$ in (21), we have

$$ $\displaystyle\mathbb{E}[l(u(\mathbf{x}),Z(j))]=-\tilde{\eta}_{j}(\mathbf{x}) \ln u(\mathbf{x})-(1-\tilde{\eta}_{j}(\mathbf{x}))\ln(1-u(\mathbf{x})).$ (48) $$

To minimize $\mathbb{E}[l(u(\mathbf{x}),Z(j))|\mathbf{X}=\mathbf{x}]$, we have $u(\mathbf{x})=\tilde{\eta}_{j}(\mathbf{x})$. Therefore, from (46),

$$ $\displaystyle g_{j}(\mathbf{x})=h_{j}(\mathbf{w}_{j}^{*},\mathbf{x})\approx \tilde{\eta}_{j}(\mathbf{x}).$ (49) $$

Such argument holds for all $j=1,\ldots,K$. Recall (22), $\Delta(\mathbf{x})$ can be obtained by a union bound of $g_{j}(\mathbf{x})-\tilde{\eta}_{j}(\mathbf{x})$.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: In particular, [Ghazi et al. '21](https://arxiv.org/abs/2102.06062) have an analysis in Appendix F where they show that the excess risk of learning with stochastic gradient descent is $K / \sqrt{N}$ for pure-DP and $\sqrt{K / N}$ for approximate-DP. A subsequent paper by [Ghazi et al. '24](https://arxiv.org/abs/2406.19040) provides a more complex method that can theoretically achieve a excess empirical error rate of $\sqrt{(\log K) / N}$.

But I think the $\sim \sqrt{(\log K) / k}$ scaling does not exactly say how the excess error scales with $N$. I would imagine that as $N \to \infty$, the optimal learning rule would also be scaling $k$ in some way, and not keep it fixed. I think this analysis might bring in dimensionality factors into the picture, which are necessary for understanding the precise scaling of excess risk with $N$.

---

On the experimental side, I am wondering if the authors have also considered datasets with non-uniform distribution over labels. For example, one could consider MNIST or CIFAR datasets by additional duplicates of certain labels to make the distribution of labels to be biased. How does the proposed method perform against prior methods, especially methods that use prior information (such as RRWithPrior or LP-MST)?
soundness: 4
strengths: The paper proposes a simple method and shows that it outperforms prior methods proposed in literature of LP-MST (Label Privacy Multi Stage Training [[Ghazi et al. '21](https://arxiv.org/abs/2102.06062)]) and ALIBI [[Malek et al. '21](https://arxiv.org/abs/2106.03408)].

The method is also simple to implement with minimal computational overhead relative to prior methods.

The paper is well written and easy to follow.
summary: This paper consider the problem of supervised multi-class learning problem under the setting of "label differential privacy" (LDP). This is a setting that is well-studied in recent literature, where the input features are considered public, and only the label is considered sensitive and needs to be protected by differential privacy.

This paper proposes a new randomizing mechanism that satisfies LDP, and outperforms prior methods studied in literature. The new method is as follows: Suppose there are $K$ possible labels. Given any label $y \in [K]$, construct the $K$-dimensional one-hot encoding of $y$ and apply the (binary) Randomized Response mechanism on each bit of the one-hot encoding, flipping each bit with probability $\frac{1}{1 + e^{\epsilon/2}}$.

A theoretical analysis is done for the k-nearest neighbor learning rule showing that the excess risk grows as $\sim \sqrt{\ln K}$ with increasing $K$ (keeping other parameter fixed).

Experimental results show that this approach outperforms prior methods studied in literature on a synthetic dataset (mixture of Gaussians data with centers around a circle) as well as real data (MNIST, CIFAR).
weaknesses: I feel there is rooom for making the paper stronger on the theoretical side.

I feel the analysis of k-NN is a bit incomplete (Appendix B.1) and doesn't highlight the complete picture. What I would have liked to see is how the excess risk decreases as $N \to \infty$ (see more details about this under "Questions").

Nevertheless, I find it quite interesting that such a simple method shows a clear improvement over prior methods in the experiments, and so I don't think of the above as a significant weakness, since the theoretical analysis is not critical for the experimental results.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: 1. Can you elaborate your reasoning on the line 107: "However, ALIBI generates outputs using Bayesian inference and normalizes them to 1 using a softmax operation. Intuitively, such normalization causes bias"?
2. In section 4.3 Practical Implementation, how does changing the activation function of the last layer affects the model performance? Do you use this in the experiments chapter and if yes, how do you modify the training process?
3. To be pedantic, line 87 should say "Malek Esmaeili et al. (2021) proposes PATE-FM". Original PATE was introduced by [Papernot et al., 2016](https://arxiv.org/abs/1610.05755), and is not specific to label DP.
soundness: 4
strengths: 1. The paper studies an important and well defined problem of label DP, which however does not get as much attention in the literature as traditional DP, while being relevant for many practical applications
2. The paper proposes a novel method to provide local label-only DP guarantees, and thoroughly explores it. The proposed method provides better utility (at the same privacy budget) compared to the prior methods on standard benchmarks. The paper provides necessary proofs of privacy guarantees, as well as general intuition behind the method.
3. The paper does a good job of putting this work in the context of the overall field, providing important details of prior works (notably, by Malek Esmaeili et al. (2021) as it shares the most similarities with the current paper)
4. The evaluation protocol looks solid and follows standard practices and baselines, including what is typically used by prior works.
5. The proposed practical implementation is quite neat, making the implementation of the method computationally efficient.
summary: This paper introduces a new approach to local label differential privacy, transforming each label into a K-dimensional vector, where each component is independently randomized with a RAPPOR-like mechanism. This vector-based approach preserves more information than scalar label transformations while maintaining ε-local differential privacy. The authors provide theoretical analysis showing that their method's performance only degrades slightly with increasing number of classes K. They empirically validate their approach using both synthetic data and standard benchmark datasets (MNIST, Fashion-MNIST, CIFAR-10, CIFAR-100), demonstrating that their method significantly outperforms existing approaches, especially when the number of classes is large and the privacy requirements are strict (small ε). Notably, proposed method outperforms a similar approach proposed by Malek Esmaeili et al. (2021), also relying on expanding a label to a vector of probabilities and adding noise to the vector.
weaknesses: At it's core, the proposed method can be summarised as applying technique from RAPPOR (Erlingsson et al. (2014)) to the "soft label" approach to label DP introduced by ALIBI (Malek Esmaeili et al. (2021)). Both techniques are properly acknowledged by the authors, and combining two existing techniques in a novel way is not a weakness by itself. Especially given the strong empirical results and accompanying theoretical analysis. 

However, I believe this should affect the focus of the analysis. In particular, the main focus area for the theoretical part of the paper is answering the question "how does the excess risk grow with the number of classes K", implicitly comparing it with the randomized response and RRWithPrior (Ghazi et al. (2021)), which are known to degrade in utility with growing K. Given strong conceptual similarities between ALIBI and the method proposed here, as well as the fact that the former is the current state-of-the-art for label DP task, I would have expected the theoretical analysis to focus on comparing the two methods. Or, if the analysis of $\Delta(x)$ is relevant for comparison with ALIBI, it needs to be shown.

Additionally, citing computational efficiency ($O(K^2$) vs $O(K$)) when comparing the new approach with ALIBI (Malek Esmaeili et al. (2021)) looks misplaced, when in any practical ML application the cost of training would dominate over the computational cost of flipping labels.

---

confidence: 3
contribution: 3
initial_rating: 3
presentation: 3
questions: Could the authors provide justifications or address the weaknesses mentioned above, especially regarding the novelty of the method and the theoretical basis of the claimed improvements? If these concerns are adequately addressed, I would be open to revising my rating and overall assessment of the paper.
soundness: 3
strengths: - The paper is well-organized and easy to follow, helping readers grasp the main ideas and methodology.
- The authors provide a numerical evaluation of the proposed methods, which helps to demonstrate its performance in practice.
- The authors provide a semi formal justification of the performance of the proposed method
summary: This paper introduces a new (?) approach for local label differential privacy (LDP) in machine learning, presenting both the theoretical framework and a numerical evaluation of the proposed method’s effectiveness. This method is based on a component-wise randomised response mechanism on the one-hot encoding of the class.
weaknesses: - The focus on local differential privacy is not clear from the title and abstract, which could be misleading for readers. Revising these sections to clearly indicate this focus would improve accessibility and transparency.
- The methods mentioned in the “Others” section of the related work could be discussed in more detail to give readers a clearer understanding of the techniques used in prior studies.
- The practical applicability of the method is limited, as it requires training a separate discriminant for each class, which could be cumbersome or impractical for larger or more complex tasks.
- The novelty of the proposed method is questionable, as noted by the authors themselves in lines 232-233, where they acknowledge its prior use in the literature.
- The authors claim that their method achieves better results by encoding more information in a vector rather than a scalar, but it remains unclear if this added information genuinely benefits the privacy-utility tradeoff. It would be valuable to see a theoretical result similar to Theorem 2 applied to the randomized response mechanism over the simplex to support a comparative analysis.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: - What is the purpose of the footnote in Table 3?

Also, see weaknesses.
soundness: 3
strengths: - The paper addresses a meaningful problem: label LDP learning with a large number of label classes. This has important practical relevance, particularly in applications with long-tailed data distributions.
- The paper proposes a simple yet effective technique to tackle this issue.
- The theoretical results are adaptable and could be extended to various scenarios under specific assumptions (e.g., smooth regression functions).
- The experimental results demonstrate significant improvements over previous methods.
summary: This paper introduces a vector approximation method aimed at improving label differential privacy (label DP) for large multi-class datasets. By encoding labels as vectors rather than scalars, the authors argue that this approach retains more class information, enabling better performance in high-class settings where traditional label DP methods degrade significantly. They present both theoretical analysis and empirical validation on synthesized and benchmark datasets, demonstrating superior accuracy, especially as the number of classes $K$ grows.
weaknesses: - The theoretical results provide only an upper bound for the proposed method. I suggest including additional comparisons and discussions between this bound and existing results. Additionally, could the authors establish any lower bounds for previous methods that use scalar labels alone (and possibly find the phase transition between $\log K$ and $K$ dependence)? Such bounds would clearly demonstrate the necessity of the proposed method. 
- The experiments were conducted on standard datasets. It would be valuable for the authors to conduct experiments on datasets with long-tailed distributions to highlight the method's practical relevance. Furthermore, it would be interesting to discuss how a long-tail distribution or class imbalance might impact the theoretical guarantees of the algorithm.
- The paper is somewhat repetitive and could benefit from further editing for conciseness.

Meta-review: ## Summary of Contributions

This paper studies label differential privacy (label-DP) setting, where we want to train an ML model and the examples are public but the labels are sensitive and should be protected with differential privacy. The paper proposes a simple but effective algorithm for randomizing the labels and training: Encode the labels as one-hot encoding and flip each bit with certain probability, and train normally with cross-entropy loss. Note that the label randomization is the same as the so-called RAPPOR algorithm (Erlingsson et al., 2014) but this is the first time it is used in the context of label-DP. Despite the relatively simple algorithm, the authors show that this consistently performs better than previous algorithms (Ghazi et al., NeurIPS'21; Malek et al., NeurIPS'21) which are more complicated and computational intensive. Furthermore, the authors provide some theoretical justifications for nearest-neighbor classifiers.

## Strengths

- The algorithm is very simple and has little overhead compared to non-private training. As a result, it can be very practical.

- Empirically, the algorithm consistently outperforms the aforementioned previously known algorithms on all datasets as long as the $\epsilon$ value is not too large. The improvements are especially large (sometimes 10+ percent) in the small $\epsilon$ (aka high-privacy) regime, which is arguably the most important regime for privacy protection.

- The authors also provide theoretical justifications.

## Weaknesses

- I don't see any major weakness here. A minor weakness is that the theoretical justification is given in the form of nearest-neighbor classifier, which is a different setting than previous work (e.g. Ghazi et al.'s theoretical results are for convex ERM). This means that it is not possible to directly compare the new theoretical results with existing ones.

## Recommendation

Given the algorithm is simple and clearly better (both from computational efficiency and model accuracy perspectives) than previous algorithms in label-DP, I think this paper is a clear accept to ICLR.

Decision: Accept (Spotlight)