# LTU Attacker for Membership Inference
## 4 Theoretical Analysis of Naive Attackers
The most obvious candidate function \(f\) is the loss function used to train \(\mathcal{M}_{D}\) (we call this a naive attacker), but the LTU Attacker can mine \(\mathcal{D}_{A}\) to potentially find more discriminative functions, or multiple functions to bag, and use \(\mathcal{D}_{A}\) to compute very good estimates for \(p_{R}\) and \(p_{D}\). We verify that an LTU Attacker using an \(f\) function making perfect membership predictions (e.g., having the knowledge of the _entire_ Defender dataset and using the nearest neighbor method) would get \(A_{Int}=1\), if there are no ties. Indeed, in that case, \(p_{R}=1\) and \(p_{D}=0\). In our second theorem, we show that the LTU Attacker can attain an analogous lower bound on accuracy connected to overfitting as the bounded loss function (BLF) adversary of [8]. Theorem 4.2: _If the loss function \(\ell(x)\) used to train the Defender model is bounded for all \(x\), without loss of generality \(0\leq\ell(x)\leq 1\) (since loss functions can always be re-scaled), and if \(e_{R}\), the expected value of the loss function on the Reserved data, is larger than \(e_{D}\), the expected value of the loss function on the Defender data, then a lower bound on the accuracy of the LTU Attacker is given by the following function of the generalization error gap \(e_{R}-e_{D}\):_  
\[A_{Int}\geq\frac{1}{2}+\frac{1}{2}(e_{R}-e_{D}) \tag{6}\]  
Proof. : If the order of the pair \((u_{1},u_{2})\) is random and the loss function \(\ell(x)\) is bounded by \(0\leq\ell(x)\leq 1\), then the LTU Attacker could predict \(u_{1}\in\mathcal{D}_{R}\) with probability \(\ell(u_{1})\), by drawing \(z\sim U(0,1)\) and predicting \(u_{1}\in\mathcal{D}_{R}\) if \(z<\ell(u_{1})\), and \(u_{1}\in\mathcal{D}_{D}\) otherwise. This gives the desired lower bound, derived in more detail in Appendix A:  
\[A_{Int} =\frac{1}{2}\underset{u_{1}\sim\mathcal{D}_{R}}{Pr}[z<\ell(u_{1}) ]+\frac{1}{2}\bigg{(}1-\underset{u_{1}\sim\mathcal{D}_{D}}{Pr}[z<\ell(u_{1}) ]\bigg{)} \tag{7}\] \[=\frac{1}{2}\underset{u_{1}\sim\mathcal{D}_{R}}{\mathbb{E}}[\ell (u_{1})]+\frac{1}{2}-\frac{1}{2}\underset{u_{1}\sim\mathcal{D}_{D}}{\mathbb{E }}[\ell(u_{1})]\] \[=\frac{1}{2}+\frac{e_{R}-e_{D}}{2}\] \[\text{where }e_{R}\coloneqq\underset{u_{1}\sim\mathcal{D}_{R}}{ \mathbb{E}}[\ell(u_{1})]\text{ and }e_{D}\coloneqq\underset{u_{1}\sim\mathcal{D}_{D}}{ \mathbb{E}}[\ell(u_{1})]\]  
This is only a lower bound on the accuracy of the attacker, connected to the main difficulty in machine learning-overfitting of the loss function. Other attack strategies may be more accurate. However, neither of the attack strategies in Theorems 4.1 and 4.2 is dominant over the other, as shown in Appendix B. The strategy in Theorem 4.1 is more widely applicable, since it does not require the function to be bounded. In the special case when the loss function used to train the Defender model is the 0-1 loss, and that is used to attack (i.e., \(f=\ell\)), the strategies in Theorems 4.1 and 4.2 are different, but have the same accuracy:  
\[p_{R} =\underset{u\sim\mathcal{D}_{R}}{Pr}[\ell(u)=1](1-\underset{u \sim\mathcal{D}_{D}}{\mathbb{P}}[\ell(u)=1])\] \[p_{D} =(1-\underset{u\sim\mathcal{D}_{R}}{\mathbb{P}}[\ell(u)=1])\underset {u\sim\mathcal{D}_{D}}{\mathbb{P}}[\ell(u)=1]\] \[p_{R}-p_{D} =\underset{u_{1}\sim\mathcal{D}_{R}}{\mathbb{P}}[\ell(u)=1]- \underset{u\sim\mathcal{D}_{D}}{\mathbb{P}}[\ell(u)=1]\] Figure 2:0  
Note that \(u\) is a dummy variable. The first line of the derivation is due to the fact that the only way the loss on the Reserved set can be greater than the loss on the Defender set is if the loss on the Reserved set is 1, which has probability \(Pr_{u\sim\mathcal{D}_{R}}[\ell(u)=1]\), and the loss on the Defender set is zero, which has probability \(1-Pr_{u\sim\mathcal{D}_{D}}[\ell(u)=1]\). The second line is derived similarly.