# On the Privacy-Utility Trade-Off in Differentially Private Hierarchical Text Classification
## 2 Preliminaries
### Differential Privacy  
In DP [11], a statistical aggregation function \(f(\cdot)\) is evaluated over a dataset \(\mathcal{D}\), and the result is perturbed before being provided to the data analyst. By means of perturbation, DP prevents an adversary with arbitrary auxiliary knowledge on all but one participant in a dataset \(\mathcal{D}\) from confidently deciding whether \(f(\cdot)\) was evaluated on \(\mathcal{D}\), or some neighboring dataset \(\mathcal{D}^{\prime}\) differing in one element. Assuming that every participant in \(\mathcal{D}\) is represented by a single record \(d\in\mathcal{D}\), privacy is intuitively provided to any individual. The perturbation strength is steered by setting privacy parameters \((\varepsilon,\delta)\), and small privacy parameters will result in high perturbation. A formal definition of DP is provided in Definition 1. **Definition 1** (\((\varepsilon,\delta)\)-Dp [19]). : _A randomized mechanism \(\mathcal{M}\) on a query function \(f\) satisfies \((\varepsilon,\delta)\)-DP for \(\delta>0\) if, for all pairs of neighboring databases \(\mathcal{D},\mathcal{D}^{\prime}\) and for all outputs \(\mathcal{O}\subseteq\text{range}(\mathcal{M})\),_  
\[\Pr[\mathcal{M}(\mathcal{D})\in\mathcal{O}]\leq e^{\varepsilon}\Pr[\mathcal{M }(\mathcal{D}^{\prime})\in\mathcal{O}]+\delta. \tag{1}\]  
DP is enforced by mechanisms. Mechanisms for numerical data perturb the original query value \(f(\mathcal{D})\) by adding numerical noise. DP mechanisms need to add noise scaled to the _global sensitivity_. Global sensitivity is formally defined in Definition 2. **Definition 2** (Global \(\ell_{1}\)-sensitivity [11]). : _Let \(\mathcal{D}\) and \(\mathcal{D}^{\prime}\) be neighboring databases. The global \(\ell_{1}\)-sensitivity of a function \(f\), denoted by \(\Delta f\), is defined as_  
\[\Delta f=\max_{\forall\mathcal{D},\mathcal{D}^{\prime}}\|f(\mathcal{D})-f( \mathcal{D}^{\prime})\|_{1}.\]  
In this work, we use the Gaussian mechanism for gradient perturbation to perturb the Adam optimizer for ANN training (the Tensorflow privacy package was used throughout this work: [[https://github.com/tensorflow/privacy](https://github.com/tensorflow/privacy)]([https://github.com/tensorflow/privacy](https://github.com/tensorflow/privacy))) as suggested by [PERSON] et al. [12]. For simplicity, we shall refer to the perturbed Adam optimizer as DP-Adam. A DP optimizer for ANN training, such as DP-Adam, uses a randomized mechanism \(\mathcal{M}_{nn}\). The optimizer updates the weight coefficients \(\theta_{t}\) of an ANN per training step \(t\in\{1,\ldots,T\}\) with \(\theta_{t}\gets\theta_{t-1}-\alpha(\hat{g})\), where \(\hat{g}=\mathcal{M}_{nn}(\partial loss/\partial\theta_{t-1})\) denotes a perturbed gradient. \(\alpha\) is a scaling function on \(\hat{g}\) to compute an update (i.e., learning rate). After \(T\) steps, DP-Adam outputs a DP weight matrix \(\theta\) that is used by the ANN prediction function. In case of DP-Adam, \(\mathcal{M}_{nn}\) is a Gaussian mechanism as specified in Theorem 1. **Theorem 1** (Gaussian Mechanism [19]). : _Let \(\epsilon\in(0,1)\) be arbitrary. For \(c^{2}>2 ln(\frac{1.25}{\delta})\), the Gaussian mechanism with parameter \(\sigma\geq c\frac{\Delta f}{\epsilon}\) satisfies \((\epsilon,\delta)\)-DP, when adding noise scaled to the Normal distribution \(\mathcal{N}(0,\sigma^{2})\)._  
DP-Adam bounds the sensitivity of the computed gradients by a clipping norm \(\mathcal{C}\), based on which the gradients are clipped before perturbation. Since weight updates are performed iteratively during training, a composition of mechanism executions is required until the training step \(T\) is reached and the final private weights \(\theta\) are obtained. We use Renyi DP as suggested by [PERSON] [20] to calculate the tight, overall privacy guarantee \(\epsilon\) under composition. \((\alpha,\epsilon_{RDP})-\text{Renyi DP}\) (RDP), with \(\alpha>1\), quantifies the difference in distributions \(\mathcal{M}(\mathcal{D})\), \(\mathcal{M}(\mathcal{D}^{\prime})\) by their Renyi divergence [21].