# Privacy Auditing in Differential Private Machine Learning:
## 2 Preliminaries
### Differential Privacy Fundamentals  
An individual's privacy is closely related to intuitive notions of privacy, such as release of privacy unit and privacy loss [63]. The privacy unit (e.g., person) quantifies how much influence a person can have on the dataset. The privacy loss quantifies how recognizable the data release is. The formalization of differential privacy is defined in relation to the privacy unit and the privacy loss. The DP framework can ensure that the insertion or deletion of a record in a dataset has no effect on the query results, thus ensuring privacy. To satisfy the DP, a random function called \"mechanism\" is used. Any function can be a mechanism as long as we can mathematically prove that the function satisfies the given definition of differential privacy. The relevant definitions, proof, and theorems are presented below. **DP mechanism:** DP relies on rigorous mathematical proofs to ensure privacy guarantees. These foundations help us to understand the behavior of DP models and determine the privacy loss [64,65]. DP is defined in terms of privacy unit (input) and privacy loss (output) of a randomized function. The description of this function that satisfies DP is called the mechanism \(\mathcal{M}(\cdot)\)[66]. **Adjacent datasets**: Two datasets, \(D\) and \(D^{\prime}\), are adjacent if \(D\subset D^{\prime}\) differs by the change in a single individual \(|D|\pm 1\). To determine whether your data analysis is a DP data analysis, you must provide data transformations that contain each function from a dataset to a dataset. For example, if you are using functions to help you understand your data, the properties or statistics you are using are _statistical queries_. **Inbounded and bounded DP**[67,68]: If the dataset is not known, you are operating under _unbounded_ DP (e.g., the sets of possible datasets is of any size). In contrast, if the dataset is known, you are operating under bounded DP (e.g., the sets of possible datasets are known size). **Pure DP**[2]: In the original DP, a mechanism, \(\mathcal{M}\), satisfies \(\epsilon\)-DP if for all pairs of _adjacent datasets_, \(D\)_and_\(D^{\prime}\), differing by one individual, and for all possible sets of outputs, \(\mathsf{S}\), of the algorithm, the following identity is as shown:  
\[\Pr[\mathcal{M}(D)\in\mathsf{S}]\leq e^{\epsilon}\times\Pr\big{[}\mathcal{M} \big{(}D^{\prime}\big{)}\in\mathsf{S}\big{]}, \tag{1}\]  
where \(\Pr\) denotes probability, \(\epsilon\) is the privacy budget (also known as a privacy risk or a privacy loss parameter) representing the degree of privacy protection, and \(e^{\epsilon}\) is amount of information leakage or the maximum difference between the outcomes of two _transformations_. **Approximate DP:** In approximate DP, a small failure probability of error, \(\delta\), is added to pure DP to relax the constraint:  
\[\Pr[\mathcal{M}(D)\in\mathsf{S}]\leq e^{\epsilon}\times\Pr\big{[}\mathcal{M} \big{(}D^{\prime}\big{)}\in\mathsf{S}\big{]}+\delta \tag{2}\]  
This makes it easier to design practical algorithms that keep the privacy guarantees perfect with higher utility, especially when the dataset is large. If \(\delta=0\), we can achieve a stricter notation of \(e\)-differential privacy. **The privacy loss**[36,69]: Let \(\mathcal{M}(\cdot)\) be a mechanism and \(D\) and \(D^{\prime}\) adjacent datasets, _the privacy loss_ for a given output, \(y\) :  
\[L\big{(}\mathcal{M}(D),\mathcal{M}\big{(}D^{\prime}\big{)},\,y\big{)}=\ln\! \left(\frac{\Pr[\mathcal{M}(D)=y]}{\Pr[\mathcal{M}(D^{\prime})\,=y]}\right)= \leq\epsilon \tag{3}\]  
The privacy loss quantifies how assure a potential attacker can be based on the odds ratio of the two possibilities. In this way, the distance between the output distributions for a given \(y\) can be measured. In other words, the pair of output distributions provides the _distinguishability_ of the mechanisms. If the loss is zero, the probabilities match and the attacker have no advantage. If the loss is positive, the attacker chooses dataset \(D\).