[233] A. E. Roth. *The Shapley value: essays in honor of Lloyd S. Shapley* (Cambridge University Press, 1988).

[234] E. ElSalamouny and C. Palamidessi. *Reconstruction of the distribution of sensitive data under free-will privacy* (2022). 2208.11268.

[235] Y. Zhu. *How niantic is profiting off tracking where you go while playing “ pokémon go”* (2016). URL https://www.forbes.com/sites/yehongzhu/2016/07/29/how-niantic-is-profiting-off-tracking-where-you-go-while-playing-pokémon-go/.

[236] S. Dredge. *Tinder dating app was sharing more of users’ location data than they realised* (2014). URL https://www.theguardian.com/technology/2014/feb/20/tinder-app-dating-data-location-sharing.

[237] K. Chatzikokolakis, C. Palamidessi, and M. Stronati. *A predictive differentially-private mechanism for mobility traces*. In E. De Cristofaro and S. J. Murdoch, eds., *Privacy Enhancing Technologies*, pp. 21–41 (Springer International Publishing, Cham, 2014).

[238] D. Haussler. *Convolution kernels on discrete structures ucsc crl* (1999).

[239] T. Hofmann, B. Schölkopf, and A. J. Smola. *Kernel methods in machine learning*. The Annals of Statistics **36**(3) (2008). URL https://doi.org/10.1214%2F009053607000000677.

[240] I. J. Schoenberg. *Metric spaces and completely monotone functions*. Annals of Mathematics **39**(4), 811 (1938). URL http://www.jstor.org/stable/1968466.

[241] S. Bernstein. *Sur les fonctions absolument monotones*. Acta Mathematica **52**(none), 1 (1929). URL https://doi.org/10.1007/BF02592679.

[242] D. Widder. *The laplace transform, vol. 6 of*. Princeton Mathematical Series (1941).

[243] H. Wendland. *Scattered Data Approximation*. Cambridge Monographs on Applied and Computational Mathematics (Cambridge University Press, 2004).

[244] G. Cohen, S. Afshar, J. Tapson, and A. Van Schaik. *Emnist: Extending mnist to handwritten letters*. In *2017 international joint conference on neural networks (IJCNN)*, pp. 2921–2926 (IEEE, 2017).

[245] I. J. Goodfellow, M. Mirza, D. Xiao, A. Courville, and Y. Bengio. *An empirical investigation of catastrophic forgetting in gradient-based neural networks*. arXiv preprint arXiv:1312.6211 (2013).

[246] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, et al. *Overcoming catastrophic forgetting in neural networks*. Proceedings of the national academy of sciences **114**(13), 3521 (2017).

[247] D. Lopez-Paz and M. Ranzato. *Gradient episodic memory for continual learning*. Advances in neural information processing systems **30** (2017).
[248] Z. Zhang and M. Sabuncu. *Generalized cross entropy loss for training deep neural networks with noisy labels*. Advances in neural information processing systems **31** (2018).

[249] R. M. Corless, G. H. Gonnet, D. E. Hare, D. J. Jeffrey, and D. E. Knuth. *On the lambert w function*. Advances in Computational mathematics **5**, 329 (1996).
# Appendices
Proofs from Chapter 3

**THEOREM 3.1.** The privacy mechanism generated by BA produces an elastic location-privacy mechanism.

*Proof.* Let $x, y \in \mathcal{X}$ be any true and reported location, respectively. Letting $\hat{C}_{BA}$ to be the limiting mechanism generated by BA, to show that $\hat{C}_{BA}$ possesses an elastic distinguishability metric, we need to ensure that:

1. The probability of reporting $y$ to obfuscate $x$ given by $\hat{C}_{BA}$ should be exponentially reducing w.r.t. the Euclidean distance between $x$ and $y$, staying consistent with the essence of geo-ind (the property captured by (3.4)).

2. Under $\hat{C}_{BA}$, the probability of reporting $y$ to obfuscate $x$ should be taking into account the mass of reported points around $y$, i.e., the more geo-spatially isolated (from other reported points) $y$ is in the space, the less likely it should be to report it, as, ideally, we would like to have $x$ being reported as a location amidst a crowd of other reported locations (the property captured by (3.5)).

Let's simplify the notation and denote $\mathbb{P}[\hat{C}_{BA}(x) = y]$ as $\mathbb{P}_{BA}[y|x]$ and let $q(y)$ be the probability mass of the observed location $y$. Hence, for being an elastic location-privacy mechanism, $\hat{C}_{BA}$ should satisfy (3.4) and (3.5), i.e., we must have:

$$ \mathbb{P}_{BA}[y|x] \propto \exp\{-\beta d_E(x, y)\} \qquad (A.1) $$

$$ \mathbb{P}_{BA}[y|x] \propto q(y) \qquad (A.2) $$
Therefore, in order to satisfy (A.1) and (A.2), it is sufficient to have:

$$
\begin{align*}
\mathbb{P}_{\text{BA}}[y|x] &\propto \exp\{-\beta d_{\text{E}}(x, y) + \ln q(y)\} \\
\Rightarrow \mathbb{P}_{\text{BA}}[y|x] &\propto q(y) \exp\{-\beta d_{\text{E}}(x, y)\} \\
&= \frac{q(y) \exp\{\beta d_{\text{E}}(x, y)\}}{\sum_{z \in \mathcal{X}} q(z) \exp\{-\beta d_{\text{E}}(x, z)\}} \tag{A.3}
\end{align*}
$$

Now, it's sufficient to note that, if we interpret the mass of y as the probability of being reported by the mechanism, (A.3) is exactly the fixpoint of $\mathcal{G} \circ \mathcal{F}$, cf. Remarks 3.2.1 and 3.2.2. $\square$

**THEOREM 3.2.** For any $t \ge 1$, the mechanism generated by BA over $\mathcal{X}$ at the $t$'th iteration, seen as a stochastic matrix, is invertible.

*Proof.* For notational convenience, in this proof, we shall denote the Euclidean distance $d_E(\cdot)$ as $d(\cdot)$. For any $t \ge 1$, let $C^{(t)}$ be the channel generated at the $t$'th iteration of BA. Hence, we have:

$$
C_{x,y}^{(t)} = \frac{c_{t-1}(y) \exp\{-\beta d(x, y)\}}{\sum_{z \in \mathcal{Y}} c_t(z) \exp\{-\beta d(x, z)\}} \quad (A.4)
$$

Let $C' \in C(\mathcal{X}, \mathcal{X})$ such that $C'_{x,y} = \exp\{-\beta d(x, y)\}$. Correspondingly, let us define $C''^{(t)}, C'''^{(t)} \in C(\mathcal{X}, \mathcal{X})$ s.t. $C''^{(t)} = c_{t-1}(y)C'_{x,y}$ and $C'''^{(t)} = K_x C''^{(t)}$ where $K_x = (\sum_{z \in \mathcal{Y}} c_t(z) \exp\{-\beta d(x, z)\})^{-1}$. Therefore, we have $C'''^{(t)} = C^{(t)}$.

Exploiting the fact that scaling of rows and columns of matrices by real numbers (elementary operations on rows and columns) preserves their linear independence, we ensure that if $C'$ is invertible, then so is $C''^{(t)}$ (elementary column operation on $C'$) which, in turn, implies that $C'''^{(t)} = C^{(t)}$ is invertible (elementary row operation on $C''^{(t)}$). Therefore, in order to show $C^{(t)}$ is invertible, it is sufficient to prove that $C'$ is invertible.

Note that $\exp\{-\beta d(x, y)^2\} = \exp\{-\beta ||x - y||_2^2\}$ is the Gaussian kernel for any $\beta > 0$ and is positive definite [238, 239]. Furthermore, Schoenberg [240] observed that for any completely monotone function $g: \mathbb{R}_{\ge 0} \to \mathbb{R}$, we can use Hausdorff-Bernstein-Widder theorem [241, 242] to deduce that radial basis function (RBF) kernels such as $\exp\{-\beta g(||x - y||_2^2)\}$ are also positive definite. Moreover, in addition to being positive definite, it was also shown that Gaussian kernels are strictly positive definite [239, 243].

Let $f: \mathbb{R}_{\ge 0} \to \mathbb{R}$ be the square-root function, i.e., $f(x) = \sqrt{x}$ for all $x \in \mathbb{R}_{\ge 0}$. Therefore, observing that $f$ is completely monotone and recalling that Gaussian kernels are strictly positive definite, i.e., $z^T \exp\{-\beta ||x_i - x_j||_2^2\} z \ge 0$ for every $z \in \mathbb{R}^m$ with equality holding iff $z = 0$, we can use Schoenberg theorem [240] to show the strict positive definiteness of $\exp\{-\beta f(d(x, y)^2)\} = \exp\{-\beta d(x, y)\}$. Hence, noting that $C'$ is the Gram matrix of the RBF kernel $\exp\{-\beta d(x, y)\}$, we must have $z^T C' z \ge 0$ for every $z \in \mathbb{R}^m$ with equality holding iff $z = 0$. This implies that $C'$ is positive definite and, hence, invertible. Therefore, in turn, $C^{(t)}$ is invertible.
$\square$

**THEOREM 3.3.** PRIVIC converges to the unique MLE of the true distribution.
*Proof.* For $1 \le t \le N$ and $1 \le i \le n$, in the $i$'th round of PRIVIC, the $i$'th sampled user locally sanitize their location $x_i^{(t)}$ with $\hat{C}^{(t)}$ and reports the noisy location $y_i^{(t)}$. Therefore, the combined mechanism (referred to as output probability matrix in [46]) for implementing GIBU is $\mathcal{G} = (\hat{C}^{(1)} \dots \hat{C}^{(N)})$ s.t.

$$ \mathcal{G}(x, y_i^{(t)}) = \mathbb{P}[y_i^{(t)}|x] = \hat{C}^{(t)}(x, y_i^{(t)}) \\ \forall x \in \mathcal{X}, i \in \{1, \dots, n\}. $$

By Theorem 3.2, $\hat{C}^{(t)}$ is invertible for every $t \ge 1$ and let $\hat{C}^{(t)-1}$ denote the corresponding inverse of $\hat{C}^{(t)}$. Therefore, defining $\mathcal{G}'$ s.t $\mathcal{G}' = \frac{1}{N}(\hat{C}^{(1)-1} \dots \hat{C}^{(N)-1})^T$ ensures that $\mathcal{G} \cdot \mathcal{G}' = \mathbb{I}_m$ where $m = |\mathcal{X}|$. Therefore, $\mathcal{G}$ is right-invertible.

Hence, combining the right-invertibility of $\mathcal{G}$ with Theorem 3 (GIBU converges to MLEs) and Corollary 1 (right-invertibility of the combined channel of GIBU implies unique MLE) of [46], we can conclude that GIBU $((\hat{C}^{(1)}, y^{(1)}), \dots, (\hat{C}^{(N)}, y^{(N)}))$ estimates the unique MLE of the prior $\pi_{\mathcal{X}}$, implying that PRIVIC converges. $\square$
<figure><img src="image_57.png" /></figure>

Tables from Chapter 3

<table><caption>**Table B.1:** EMD between the true and the estimated PMFs by PRIVIC on the Paris locations.</caption><thead><tr><th rowspan="2">N</th><th colspan="5">β = 1</th><th colspan="5">β = 0.5</th></tr><tr><th>Round 1</th><th>Round 2</th><th>Round 3</th><th>Round 4</th><th>Round 5</th><th>Round 1</th><th>Round 2</th><th>Round 3</th><th>Round 4</th><th>Round 5</th></tr></thead><tbody><tr><td>1</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td><td>2.02262</td></tr><tr><td>2</td><td>0.27104</td><td>0.27796</td><td>0.28247</td><td>0.27758</td><td>0.26276</td><td>0.57738</td><td>0.57994</td><td>0.55791</td><td>0.60717</td><td>0.56880</td></tr><tr><td>3</td><td>0.21916</td><td>0.23750</td><td>0.25035</td><td>0.25116</td><td>0.23241</td><td>0.51324</td><td>0.48295</td><td>0.47043</td><td>0.51285</td><td>0.45826</td></tr><tr><td>4</td><td>0.19156</td><td>0.21115</td><td>0.21726</td><td>0.20913</td><td>0.20408</td><td>0.43184</td><td>0.42398</td><td>0.41040</td><td>0.45230</td><td>0.41119</td></tr><tr><td>5</td><td>0.18241</td><td>0.19264</td><td>0.19570</td><td>0.19747</td><td>0.18728</td><td>0.39741</td><td>0.38771</td><td>0.37284</td><td>0.41176</td><td>0.36953</td></tr><tr><td>6</td><td>0.16526</td><td>0.18020</td><td>0.174578</td><td>0.17310</td><td>0.17268</td><td>0.37818</td><td>0.35482</td><td>0.36039</td><td>0.36375</td><td>0.38045</td></tr><tr><td>7</td><td>0.14643</td><td>0.18159</td><td>0.16092</td><td>0.17222</td><td>0.17139</td><td>0.35044</td><td>0.34383</td><td>0.34818</td><td>0.35760</td><td>0.36804</td></tr><tr><td>8</td><td>0.13860</td><td>0.17605</td><td>0.15938</td><td>0.17078</td><td>0.16192</td><td>0.34086</td><td>0.32983</td><td>0.35769</td><td>0.34430</td><td>0.34780</td></tr><tr><td>9</td><td>0.15047</td><td>0.16926</td><td>0.15153</td><td>0.17005</td><td>0.15266</td><td>0.33137</td><td>0.31749</td><td>0.34690</td><td>0.33840</td><td>0.34028</td></tr><tr><td>10</td><td>0.14734</td><td>0.14825</td><td>0.14585</td><td>0.15001</td><td>0.15459</td><td>0.3170</td><td>0.32975</td><td>0.32772</td><td>0.34529</td><td>0.32670</td></tr><tr><td>11</td><td>0.14227</td><td>0.14135</td><td>0.14326</td><td>0.13797</td><td>0.14507</td><td>0.31917</td><td>0.31851</td><td>0.32689</td><td>0.33667</td><td>0.32043</td></tr><tr><td>12</td><td>0.13818</td><td>0.14448</td><td>0.14703</td><td>0.13589</td><td>0.14142</td><td>0.32137</td><td>0.32451</td><td>0.31843</td><td>0.32556</td><td>0.34014</td></tr><tr><td>13</td><td>0.16111</td><td>0.13641</td><td>0.14893</td><td>0.14208</td><td>0.13808</td><td>0.31224</td><td>0.31219</td><td>0.31380</td><td>0.31515</td><td>0.31159</td></tr><tr><td>14</td><td>0.13894</td><td>0.13111</td><td>0.14094</td><td>0.14199</td><td>0.14192</td><td>0.30883</td><td>0.30496</td><td>0.30578</td><td>0.30726</td><td>0.30282</td></tr><tr><td>15</td><td>0.15106</td><td>0.14271</td><td>0.14601</td><td>0.13584</td><td>0.12413</td><td>0.29405</td><td>0.31198</td><td>0.30786</td><td>0.31167</td><td>0.30100</td></tr></tbody></table>

<table><caption>**Table B.2:** EMD between the true and the estimated PMFs by PRIVIC on the San Francisco locations.</caption><thead><tr><th rowspan="2">N</th><th colspan="5">β = 1</th><th colspan="5">β = 0.5</th></tr><tr><th>Round 1</th><th>Round 2</th><th>Round 3</th><th>Round 4</th><th>Round 5</th><th>Round 1</th><th>Round 2</th><th>Round 3</th><th>Round 4</th><th>Round 5</th></tr></thead><tbody><tr><td>1</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td><td>7.37595</td></tr><tr><td>2</td><td>0.37229</td><td>0.37038</td><td>0.36784</td><td>0.36949</td><td>0.36816</td><td>0.79621</td><td>0.80474</td><td>0.80219</td><td>0.80670</td><td>0.79940</td></tr><tr><td>3</td><td>0.29828</td><td>0.298370</td><td>0.30017</td><td>0.29784</td><td>0.29859</td><td>0.64931</td><td>0.66292</td><td>0.65362</td><td>0.65950</td><td>0.65285</td></tr><tr><td>4</td><td>0.26091</td><td>0.26029</td><td>0.26231</td><td>0.26180</td><td>0.26518</td><td>0.56896</td><td>0.57378</td><td>0.57338</td><td>0.57125</td><td>0.56618</td></tr><tr><td>5</td><td>0.23472</td><td>0.23419</td><td>0.23337</td><td>0.23740</td><td>0.23897</td><td>0.51672</td><td>0.51710</td><td>0.51735</td><td>0.51880</td><td>0.51138</td></tr><tr><td>6</td><td>0.21367</td><td>0.21432</td><td>0.21537</td><td>0.21777</td><td>0.21881</td><td>0.48194</td><td>0.48299</td><td>0.47992</td><td>0.48267</td><td>0.47791</td></tr><tr><td>7</td><td>0.19612</td><td>0.19761</td><td>0.19904</td><td>0.20120</td><td>0.20067</td><td>0.45531</td><td>0.45861</td><td>0.45122</td><td>0.45732</td><td>0.45450</td></tr><tr><td>8</td><td>0.18244</td><td>0.18412</td><td>0.18741</td><td>0.18724</td><td>0.18674</td><td>0.43588</td><td>0.43745</td><td>0.43558</td><td>0.43704</td><td>0.43584</td></tr></tbody></table>
**THEOREM 4.1.** [Compositionality Theorem for AGeoI] Let mechanisms $\mathcal{K}_1$ and $\mathcal{K}_2$ be $(\varepsilon_1, \delta_1)$ and $(\varepsilon_2, \delta_2)$ geo-indistinguishable, respectively. Then their composition is $(\varepsilon_1 + \varepsilon_2, \delta_1 + \delta_2)$-geo-indistinguishable. In other words, for every $S_1, S_2 \subseteq \mathcal{Y}$ and all $x_1, x'_1, x_2, x'_2 \in \mathcal{X}$:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x_1, x_2)] \le e^{\varepsilon_1 d(x_1, x'_1) + \varepsilon_2 d(x_2, x'_2)} \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x'_1, x'_2)] + (\delta_1 e^{\varepsilon_1 d(x_1, x'_1)} + \delta_2 e^{\varepsilon_2 d(x_2, x'_2)}) $$

*Proof.* Let us simplify the notation and denote:

$$ P_i = \mathbb{P}_{\mathcal{K}_i} [y_i \in S_i | x_i] $$

$$ P'_i = \mathbb{P}_{\mathcal{K}_i} [y_i \in S_i | x'_i] $$

$$ \tilde{\delta}_i = \delta_i e^{\varepsilon_i d(x_i, x'_i)} $$

for $i \in \{1, 2\}$. As mechanisms $\mathcal{K}_1$ and $\mathcal{K}_2$ are applied independently, we have:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x_1, x_2)] = P_1 P_2 \qquad (C.1) $$

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x'_1, x'_2)] = P'_1 P'_2 \qquad (C.2) $$

Therefore, we obtain:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x_1, x_2)] = P_1 P_2 $$
$$
\begin{align*}
& \le \left( \min \left( 1 - \tilde{\delta}_1, e^{\epsilon_1 d(x_1, x_1')} P_1' \right) + \tilde{\delta}_1 \right) \left( \min \left( 1 - \tilde{\delta}_2, e^{\epsilon_2 d(x_2, x_2')} P_2' \right) + \tilde{\delta}_2 \right) \\
& \le m_1 m_2 + \tilde{\delta}_1 m_2 + m_1 \tilde{\delta}_2 + \tilde{\delta}_1 \tilde{\delta}_2 \\
& \quad \left[ \text{where } m_i = \min \left( 1 - \tilde{\delta}_i, e^{\epsilon_i d(x_i, x_i')} P_i' \right) \right] \\
& \le e^{\epsilon_1 d(x_1, x_1')} + \epsilon_2 d(x_2, x_2') P_1' P_2' \\
& \quad + \tilde{\delta}_1 - \tilde{\delta}_1 \tilde{\delta}_2 + \tilde{\delta}_2 - \tilde{\delta}_1 \tilde{\delta}_2 + \tilde{\delta}_1 \tilde{\delta}_2 \\
& \le e^{\epsilon_1 d(x_1, x_1')} + \epsilon_2 d(x_2, x_2') \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} \left[ (y_1, y_2) \in S_1 \times S_2 | (x_1', x_2') \right] + \left( \tilde{\delta}_1 e^{\epsilon_1 d(x_1, x_1')} + \tilde{\delta}_2 e^{\epsilon_2 d(x_2, x_2')} \right)
\end{align*}
$$

□

**LEMMA 4.2.** For every $x_1, x_2 \in \mathcal{X}$ and $y \in \mathcal{Y}$, we have $e^{-\epsilon d(x_1, x_2)} \mathbb{P}_{\mathcal{L}}[y|x_1] - \mathbb{P}_{\mathcal{L}}[y|x_2] \le 1$.

*Proof.*

$$
\begin{align*}
& e^{-\epsilon d(x_1, x_2)} \mathbb{P}[y|x_1] - \mathbb{P}[y|x_2] \le 1 \\
\iff & c \left( e^{-\epsilon(d(x_1, x_2) + d(x_1, y))} - e^{-\epsilon d(x_2, y)} \right) \le 1 \tag{C.3}
\end{align*}
$$

Now we observe that $d(x_1, x_2)+d(x_1, y) \ge d(x_2, y)$ due to the fact that $d$ is a metric and it satisfies the triangle inequality. Immediately, we have $e^{-\epsilon d(x_1, x_2)+d(x_1, y)} - e^{-\epsilon d(x_2, y)} \le 0$ for any $\epsilon \in \mathbb{R}_{\ge 0}$.
Therefore, as $c \ge 0$, (C.3) is trivially satisfied.
□
**PROPOSITION 5.1.** Abusing the notation $\mathbb{P}[\cdot]$ to denote the PDF, let $\mathcal{L}_{\varepsilon}: \mathbb{R}^n \to \mathbb{R}^n$ be the Laplace mechanism with distribution $\mathcal{L}_{x_0, \varepsilon}(x) = \mathbb{P}[\mathcal{L}_{\varepsilon}(x_0) = x] = Ke^{-\varepsilon d(x,x_0)}$ with $d$ being the Euclidean distance. If $\rho \sim \mathcal{L}_{x_0, \varepsilon}(x)$, then:

1. $\mathcal{L}_{x_0, \varepsilon}$ is $\varepsilon$-d-private and $K = \frac{\varepsilon^n \Gamma(\frac{n}{2})}{2\pi^{\frac{n}{2}} \Gamma(n)}$

2. $\|\rho\|_2 \sim \gamma_{\varepsilon,n}$ s.t. $\mathbb{P}[\|\rho\|_2 = r] = \frac{\varepsilon^n e^{-\varepsilon r} r^{n-1}}{\Gamma(n)}$

3. The $i^{th}$ component of $\rho$ has variance $\sigma_{\rho i}^2 = \frac{n+1}{\varepsilon^2}$

where $\Gamma(n)$ is the Gamma function defined for positive reals as $\int_0^\infty t^{n-1}e^{-t} dt$ which reduces to the factorial function whenever $n \in \mathbb{N}$.

*Proof.* We provide proof of the three statements separately:

1. If $\mathcal{L}_{x_0, \varepsilon}(x) = Ke^{-\varepsilon d(x,x_0)}$ is a probability density function of a point $x \in \mathbb{R}^n$ then $K$ should be such that $\int_{\mathbb{R}^n} \mathcal{L}_{x_0}(x)dx = 1$. We note that it depends only on the distance $x$ and $x_0$ and we can write $Ke^{-\varepsilon d(x,x_0)}$ as $Ke^{-\varepsilon r}$ where $r$ is the radius of the ball in $\mathbb{R}^n$ centered in $x_0$. Without loss of generality, let us now take $x_0 = 0$. The probability density of the event $x \in \mathbb{S}_n(r) = \{x : \|x\|_2 = r\}$ is then $p(x \in \mathbb{S}_n(r)) = Ke^{-\varepsilon r} \mathbb{S}_n(1)r^{n-1}$ where $S_n(1)$ is the surface of the unitary ball in $\mathbb{R}^n$ and $S_n(r) = S_n(1)r^{n-1}$ is the surface of a generic ball of radius $r$. Given that

$$S_n(1) = \frac{2\pi^{n/2}}{\Gamma(\frac{n}{2})} \qquad (D.1)$$
solving

$$
\begin{equation}
\begin{aligned}
\int_0^{+\infty} \mathbb{P}[x \in \mathbb{S}_n(r)] dr &= \int_0^{+\infty} K e^{-\epsilon r} S_n(1) r^{n-1} dr = \\
&\qquad K \frac{2\pi^{n/2} \Gamma(n)}{\epsilon^n \Gamma(\frac{n}{2})} = 1
\end{aligned}
\tag{D.2}
\end{equation}
$$

results in

$$
K = \frac{\varepsilon^n \Gamma(\frac{n}{2})}{2\pi^{\frac{n}{2}} \Gamma(n)} \qquad (\text{D.3})
$$

where $\Gamma(\cdot)$ denotes the gamma function. By plugging $\mathcal{L}_{x_0, \varepsilon}(x) = K e^{-\varepsilon d(x, x_0)}$ in Equation 2.3:

$$
Ke^{-\epsilon d(x, x_1)} \leq e^{\epsilon d(x_1, x_2)} Ke^{-\epsilon d(x, x_2)} \quad (D.4)
$$

$$
e^{\epsilon(\|x-x_2\|_2 - \|x-x_1\|_2)} \le e^{\epsilon\|x_1-x_2\|} = e^{\epsilon d(x_1,x_2)} \quad (D.5)
$$

which completes the proof of the first statement.

2. Without loss of generality, let us take $x_0 = 0$. Exploiting the radial symmetry of the Laplace distribution, we note that, in order to sample a point $\rho \sim \mathcal{L}_{\varepsilon}(x_0)$ in $\mathbb{R}^n$, it is possible to first sample the set of points distance $r$ from $x_0$ and then sample uniformly from the resulting hypersphere. Accordingly, the p.d.f. of the $L_2$-norm of $\rho$ is the p.d.f. of the event $\rho \in \mathbb{S}_n(r) = \{\rho \in \mathbb{R}^n : \|\rho\|_2 = r\}$ which is then $\mathbb{P}[\rho \in \mathbb{S}_n(r)] = K e^{-\epsilon r} \mathbb{S}_n(1)r^{n-1}$, where $\mathbb{S}_n(r)$ is the surface of the sphere with radius $r$ in $\mathbb{R}^n$. Hence, we can write

$$
\|\rho\|_2 \sim \gamma_{\epsilon,n} \text{ s.t. } \mathbb{P}[\|\rho\|_2 = r] = \frac{\epsilon^n e^{-\epsilon r} r^{n-1}}{\Gamma(n)} \quad (D.6)
$$

which completes the proof of the second statement.

3. With $\rho \sim \gamma_{\epsilon,n}$ we have that, by construction,

$$
\mathbb{E}[\rho^2] = \mathbb{E}\left[\sum_{i=1}^{n} \rho_i^2\right] = n\mathbb{E}[\rho_i^2] = n\sigma_{\rho_i}^2 \quad (\text{D.7})
$$

With the last equality holding since $\mathcal{L}_{0,\varepsilon}$ is isotropic and centered in zero. Recalling that

$$
\mathbb{E}[\rho^2] = \left. \frac{d^2}{dt^2} M_{\rho}(t) \right|_{t=0} \qquad (\text{D.8})
$$

with $M_{\rho}(t)$ the moment generating function of the gamma distribution $\gamma_{\epsilon,n}$,

$$
\begin{align*}
\frac{d^2}{dt^2} \left( \left(1 - \frac{t}{\epsilon}\right)^{-n} \right) \Big|_{t=0} &= \\
&= \frac{n(n+1)}{\epsilon^2} \left(1 - \frac{t}{\epsilon}\right)^{-(n+2)} \Big|_{t=0} &= \\
&= \frac{n(n+1)}{\epsilon^2}
\end{align*}
$$

which leads to $\sigma_{\rho_i}^2 = \frac{n+1}{\epsilon^2}$, completing the proof of the third statement and of the Proposition. $\square$
**PROPOSITION 5.2.** Let $y = f(x, \theta)$ be the fitting function of a machine learning model parameterized by $\theta$, and $(X, Y) = Z$ the dataset over which the RMSE loss function $F(Z, \theta)$ is to be minimized, with $x \in X$ and $y \in Y$. If $\rho \sim \mathcal{L}_{0,\epsilon}$, the bound on the increase of the cost function does not depend on the direction of $\rho$, in first-order approximation, and:

$$ \begin{aligned} & \|F(Z, \theta + \rho)\|_2 - \|F(Z, \theta)\|_2 \le \\ & \|J_f(X, \theta)\|_2 \|\rho\|_2 + o(\|J_f(X, \theta)\rho\|_2) \end{aligned} \qquad (5.8) $$

*Proof.* The Root Mean Square Error loss function is defined as:

$$ F = \sqrt{\frac{\sum_{i=1}^{|Z|} (f(x_i, \theta) - y_i)^2}{|Z|}} = \frac{\|f(X, \theta) - Y\|_2}{\sqrt{|Z|}} \qquad (D.9) $$

If the model parameters $\theta$ are sanitized by the addition of a random vector $\rho \sim \mathcal{L}_{0,\epsilon}$, we can evaluate how the cost function would change with respect to the non-sanitized parameters. Dropping the multiplicative constant we find:

$$ \begin{aligned} & \|f(X, \theta + \rho) - Y\|_2 - \|f(X, \theta) - Y\|_2 \\ & \le \|f(X, \theta + \rho) - Y - f(X, \theta) + Y\|_2 \\ & = \|f(X, \theta + \rho) - f(X, \theta)\|_2 \\ & = \|f(X, \theta) + J_f(X, \theta)\rho - f(x, \theta) + o(J_f(X, \theta)\rho)\|_2 \\ & = \|J_f(X, \theta)\rho + o(J_f(X, \theta)\rho)\|_2 \\ & \le \|J_f(X, \theta)\|_2 \|\rho\|_2 + o(\|J_f(X, \theta)\rho\|_2) \end{aligned} $$

□

with $J_f(X, \theta)$ being the Jacobian of $f$ with respect to $X$ and $o(\cdot)$ being higher terms coming from the Taylor expansion. Thus we proved that the bound on the increase of the cost function does not depend on the direction of the additive noise, but on its norm, in first-order approximation.

**THEOREM 5.3.** Let $\mathcal{K}_i$ be $(\epsilon_i)$-d-private mechanism for $i \in \{1, 2\}$. Then their independent composition is $(\epsilon_1 + \epsilon_2)$-d-private.

*Proof.* Let us simplify the notation and denote:

$$ P_i = \mathbb{P}_{\mathcal{K}_i} [y_i \in S_i | x_i] $$

$$ P'_i = \mathbb{P}_{\mathcal{K}_i} [y_i \in S_i | x'_i] $$
for $i \in \{1, 2\}$. As mechanisms $\mathcal{K}_1$ and $\mathcal{K}_2$ are applied independently, we have:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x_1, x_2)] = P_1 P_2 $$

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x'_1, x'_2)] = P'_1 P'_2 $$

Therefore, we obtain:

$$ \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x_1, x_2)] = P_1 P_2 $$

$$ \leq (e^{\varepsilon_1 d(x_1, x'_1)} P'_1) (e^{\varepsilon_2 d(x_2, x'_2)} P'_2) $$

$$ \leq e^{\varepsilon_1 d(x_1, x'_1) + \varepsilon_2 d(x_2, x'_2)} \mathbb{P}_{\mathcal{K}_1, \mathcal{K}_2} [(y_1, y_2) \in S_1 \times S_2 | (x'_1, x'_2)] $$

□
# Experimental settings in Chapter 5

All the following experiments are run on a local server running Ubuntu 20.04.3 LTS with an AMD EPYC 7282 16-Core processor, 1.5TB of RAM and NVIDIA A100 GPUs. Python and PyTorch are the main software tools adopted for simulating the federation of clients and their corresponding collaborative training.

## Synthetic data

A total of 100 users holding 10 samples each, drawn from either one of the distributions, participate in a training of two initial hypotheses which are sampled from a Gaussian distribution centred in 0 and unit variance at iteration $t = 0$. A total of $U = 7$ users are asked to participate in the optimization at each round and train locally the hypothesis that fits their dataset better for $E = 1$ epochs each time. The noise multiplier is set to $\nu = 5$. Local step size $s = 0.1$ and batch size $B_s = 10$ complete the required inputs to the algorithm. To verify the training process, another set of users with the same characteristics are held out from training to perform validation and stop the federated optimization once it is no improvement in the loss function in Equation (D.9) for 6 consecutive rounds. Although first, the updates seem to be distributed all over the domain, in just a few rounds of training the process converges to values very close to the two optimal parameters. With the heuristic presented in Section 5.4.2 it is easy to find that whenever a user participates in an optimization round it incurs a privacy leakage of at most $n/\nu = 2/5 = 0.4$, in a differential private sense, with respect to points in its neighbourhood. Using the result in Theorem 5.3 clients can compute the overall privacy leakage of the optimization process, should they be required to participate multiple times. For any user, whether to participate or not in a training round can be decided right before releasing the updated parameters, in case that would increase the privacy leakage above a threshold value decided beforehand.
## Hospital charge data

The dataset contains details about charges for the 100 most common inpatient services and the 30 most common outpatient services. It shows a great variety of charges applied by healthcare providers with details mostly related to the type of service and the location of the provider. Preprocessing of the dataset includes a number of procedures, the most important of which are described here:

i) Selection of the 4 most widely treated conditions, which amount to simple pneumonia; kidney and urinary tract infections; hart failure and shock; esophagitis and digestive system disorders.

ii) Transformation of ZIP codes into numerical coordinates in terms of longitude and latitude.

iii) Setting as target the Average Total Payments, i.e. the cost of the service averaged among the times it was given by a certain provider.

iv) As it is a standard procedure in the context of gradient-based optimization, dependent and independent variables are brought to be in the range of the units before being fed to the machine learning model. Note that this point takes the spot of the common feature normalization and standardization procedures, which we decided not to perform here to keep the setting as realistic as possible. In fact, both would require the knowledge of the empirical distribution of all the data. Although it is available in simulation, it would not be available in a real scenario, as each user would only have access to their dataset.

Given the preprocessing described above, the dataset results in 2947 clients, randomly split in train and validation subsets with 70 and 30 per cent of the total clients each. The goal is being able to predict the cost that a service would require given where it is performed in the country, and what kind of procedure it is. The model that was adopted in this context is a fully connected neural network (NN) of two layers, with a total of 11 parameters and Rectified Linear Unit (ReLU) activation function. Inputs to the model are an increasing index which uniquely defines the healthcare service, the longitude and latitude of the provider. Output of the model is the expected cost. Tests have been performed to minimize the RMSE loss on the clients selected for training (100 per round) and at each round the performance of the model is checked against a held-out set of validation clients, from where 200 are sampled every time. If 30 validation rounds are passed without improvement in the cost function, the optimization process is terminated. In order to decrease the variability of the results, a total of 10 runs have been performed with different seeds for every combination of number of hypotheses and noise multiplier.

## FEMNIST image classification

The task consists in performing image classification on the FEMNIST [182] dataset, which is a standard benchmark dataset for federated learning, based on EMNIST [244] and with the data points grouped by user. It consists of a large number of images of handwritten digits,
lower and upper case letters of the Latin alphabet. As a preprocessing step, images of client *c* are rotated 90 degrees counter-clockwise depending on the realization of the random variable $rot_c \sim \text{Bernoulli}(0.5)$. This is a common practice in machine learning to simulate local datasets held by different clients being generated by different distributions [138, 245–247]. The chosen architecture is described in Table E.1 and yields a parameter vector $\theta \in \mathbb{R}^{n_0}$, $n_0 = 1206590$. Runs are performed with a maximum of 500 rounds of federated optimization, unless 5 consecutive validation rounds are conducted without improvements on the validation loss. The latter is evaluated on a held out set of clients, consisting of 10% of the total number. Validation is performed every 5 training rounds, thus the process terminates after 25 rounds without the model’s performance improvement. The optimization process aims to minimize either the RMSE loss or the Cross Entropy loss [248] between model’s predictions and the target class.

<table><caption>**Table E.1:** NN architecture adopted in the experiments of Section 5.5.4</caption><thead><tr><th>Layer</th><th>Properties</th></tr></thead><tbody><tr><td>2D Convolution</td><td>kernel size: (2,2)<br>stride: (1,1)<br>nonlinearity: ReLU<br>output features: 32</td></tr><tr><td>2D Convolution</td><td>kernel size: (2,2)<br>stride: (1,1)<br>nonlinearity: ReLU<br>output features: 64</td></tr><tr><td>2D Max Pool</td><td>kernel size: (2,2)<br>stride: (2,2)<br>nonlinearity: ReLU</td></tr><tr><td>Fully Connected</td><td>nonlinearity: ReLU<br>units: 128</td></tr><tr><td>Fully Connected</td><td>nonlinearity: ReLU<br>units: 62</td></tr></tbody></table>
Proofs from Chapter 6

**LEMMA 6.1.** Given a binary classification NN with no hidden layers, batch size 1 and a final layer containing bias terms, the gradient update using a cross-entropy loss function reveals the values of the input **x** exactly.

*Proof.* Under the assumption that $|\mathbf{x}| \neq 0$, from the closed form above we can deduce the $x_i$ exactly using the knowledge of the $p_k - y_k$ values. However, this assumes that the values $p_k - y_k$ are always non-zero. Observe that the softmax function can never be 0, and for 2 outputs can also never be 1. Thus, assuming that $y_k \in \{0, 1\}$ we have that $p_k - y_k$ must always be non-zero. And so $\mathbf{x}$ is revealed exactly. □

**LEMMA 6.2.** If $\mathbf{x}$ and $\mathbf{x}'$ are gradient clones, there is some $K \in \mathbb{R}$ such that $\mathbf{x}' = K\mathbf{x}$.

*Proof.* Let some $\mathbf{x}$, $\mathbf{x}'$ be gradient clones. W.l.o.g. let $y(\mathbf{x}) = A$ and so $y_B(\mathbf{x}) = 0$. Then we have two possibilities: $y(\mathbf{x}') = A$ or $y(\mathbf{x}') = B$.

**Case 1**

$y(\mathbf{x}') = A$: Hence $y_B(\mathbf{x}') = 0$ and so from (6.11) we have that $\nabla w_B(\mathbf{x}) = \nabla w_B(\mathbf{x}')$, and so we deduce:

$$p_B(\mathbf{x})\mathbf{x} = p_B(\mathbf{x}')\mathbf{x}' \Rightarrow \qquad (F.1)$$
$$ 
\begin{aligned}
& \frac{e^{\sum_{i=1}^{n} x_i w_B(i) + b_B}}{e^{\sum_{i=1}^{n} x_i w_A(i) + b_A} + e^{\sum_{i=1}^{n} x_i w_B(i) + b_B}} \mathbf{x}_i = \\
& \frac{e^{\sum_{i=1}^{n} x'_i w_B(i) + b_B}}{e^{\sum_{i=1}^{n} x'_i w_A(i) + b_A} + e^{\sum_{i=1}^{n} x'_i w_B(i) + b_B}} \mathbf{x}'_i \Rightarrow \\
& \frac{e^{\mathbf{x} \cdot \mathbf{w}_B} \mathbf{x}_i}{e^{\mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x} \cdot \mathbf{w}_B + b_B}} = \frac{e^{\mathbf{x}' \cdot \mathbf{w}_B} \mathbf{x}'_i}{e^{\mathbf{x}' \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x}' \cdot \mathbf{w}_B + b_B}} \quad (F.2) \\
& \forall i \in \{1, \dots, n\}
\end{aligned}
$$

Setting

$$ K = e^{w_B \cdot (x - x')} \frac{\left( e^{x' \cdot w_A + b_A} + e^{x'_i \cdot w_B + b_B} \right)}{\left( e^{x \cdot w_A + b_A} + e^{x \cdot w_B + b_B} \right)} $$

gives us our desired result.

## Case 2

$y(\mathbf{x}') = B$: Hence, $y_A(\mathbf{x}') = 0$ and so from (6.10) we have that $\nabla w_A(\mathbf{x}) = \nabla w_A(\mathbf{x}')$ and so we deduce:

$$ (p_A(\mathbf{x}) - 1)\mathbf{x} = p_A(\mathbf{x}')\mathbf{x}' \Rightarrow \quad (F.3) $$

$$ -p_B(\mathbf{x})\mathbf{x} = p_A(\mathbf{x}')\mathbf{x}' \Rightarrow \quad (F.4) $$

$$ 
\begin{aligned}
& \frac{e^{\sum_{i=1}^{n} x_i w_B(i) + b_B}}{e^{\sum_{i=1}^{n} x_i w_A(i) + b_A} + e^{\sum_{i=1}^{n} x_i w_B(i) + b_B}} \mathbf{x}_i = \\
& \frac{e^{\sum_{i=1}^{n} x'_i w_A(i) + b_A}}{e^{\sum_{i=1}^{n} x'_i w_A(i) + b_A} + e^{\sum_{i=1}^{n} x'_i w_B(i) + b_B}} \mathbf{x}'_i \quad (F.5) \\
& \forall i \in \{1, \dots, n\}
\end{aligned}
$$

Setting

$$ K = -e^{w_B \cdot x - w_A \cdot x' + (b_B - b_A)} \frac{\left( e^{x' \cdot w_A + b_A} + e^{x'_i \cdot w_B + b_B} \right)}{\left( e^{x \cdot w_A + b_A} + e^{x \cdot w_B + b_B} \right)} $$

gives us our desired result. □

**LEMMA 6.3.** Setting $\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$ and $\Delta = b_B - b_A$, $\mathbf{x}$ has a gradient clone iff there is some $K \in \mathbb{R}$ satisfying the equation

$$ e^{K\gamma} - Ke^{\gamma} = (K - 1)e^{\Delta}. \quad (6.13) $$

The corresponding gradient clone of $\mathbf{x}$ would be $\mathbf{x}$ scaled by that $K$.

*Proof.* Let $\mathbf{x}'$ be a gradient clone of $\mathbf{x}$. Using the fact that $\mathbf{x}' = K\mathbf{x}$ for some $K \in \mathbb{R}$ (by Lemma 6.2), by comparing the signs of the components of $\nabla w(\mathbf{x})$ and $\nabla w(\mathbf{x})$ (Remark 6.4.2), and by Eqns. (6.10) and (6.11), we must have:

$$ p_B(\mathbf{x})\mathbf{x} = p_B(\mathbf{x}')\mathbf{x}' $$
$$ \Rightarrow p_B(\mathbf{x})\mathbf{x} = p_B(\mathbf{x}')K\mathbf{x} $$

$$ \Rightarrow p_B(\mathbf{x}) = p_B(\mathbf{x}')K \quad [\text{as } |\mathbf{x}| \neq 0] $$

$$ \Rightarrow \frac{e^{\mathbf{x} \cdot \mathbf{w}_B} e^{b_B}}{e^{\mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x} \cdot \mathbf{w}_B + b_B}} = \frac{e^{\mathbf{x}' \cdot \mathbf{w}_B} e^{b_B} K}{e^{\mathbf{x}' \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x}' \cdot \mathbf{w}_B + b_B}} $$

$$ \Rightarrow \frac{e^{\mathbf{x} \cdot \mathbf{w}_B}}{e^{\mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x} \cdot \mathbf{w}_B + b_B}} = \frac{e^{K \mathbf{x} \cdot \mathbf{w}_B} K}{e^{K \mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{K \mathbf{x} \cdot \mathbf{w}_B + b_B}} $$

$$ \Rightarrow \frac{e^{K \mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{K \mathbf{x} \cdot \mathbf{w}_B + b_B}}{e^{\mathbf{x} \cdot \mathbf{w}_A + b_A} + e^{\mathbf{x} \cdot \mathbf{w}_B + b_B}} = K e^{\mathbf{x} \cdot \mathbf{w}_B (K-1)} $$

$$ \Rightarrow \left( \frac{e^{K \mathbf{x} \cdot \mathbf{w}_B}}{e^{\mathbf{x} \cdot \mathbf{w}_B}} \right) \frac{e^{K(\mathbf{x} \cdot \mathbf{w}_A - \mathbf{x} \cdot \mathbf{w}_B) + b_A} + e^{b_B}}{e^{(\mathbf{x} \cdot \mathbf{w}_A - \mathbf{x} \cdot \mathbf{w}_B) + b_A} + e^{b_B}} $$

$$ = K e^{\mathbf{x} \cdot \mathbf{w}_B (K-1)} $$

$$ \Rightarrow e^{(K-1)\mathbf{x} \cdot \mathbf{w}_B} \left( \frac{e^{K\gamma} e^{b_A} + e^{b_B}}{e^{\gamma} e^{b_A} + e^{b_B}} \right) = K e^{\mathbf{x} \cdot \mathbf{w}_B (K-1)} $$

$$ \Rightarrow e^{K\gamma} e^{b_A} + e^{b_B} = K (e^{\gamma} e^{b_A} + e^{b_B}) $$

$$ \Rightarrow e^{K\gamma} + e^{\Delta} = K (e^{\gamma} + e^{\Delta}) $$

$$ \Rightarrow e^{K\gamma} - K e^{\gamma} = (K-1)e^{\Delta} $$

□

**THEOREM 6.4.** For any $K > 1$, if $\mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B) \le \frac{\ln K}{K-1}$, then $\mathbf{x}$ has no gradient clone scaled by that $K$.

*Proof.* Let $\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$ and $\Delta = b_B - b_A$. For $\mathbf{x}$ to have a gradient clone scaled by $K$, by Lemma 6.3, we must satisfy (6.13). Moreover, we note that the RHS of (6.13) is positive for $K > 1$. In particular, we have:

$$ e^{K\gamma} - K e^{\gamma} > 0 $$

$$ \iff e^{K\gamma} > e^{\gamma + \ln K} $$

$$ \iff K\gamma > \gamma + \ln K $$

$$ \iff \gamma > \frac{\ln K}{K-1} $$

But $\gamma \le \frac{\ln K}{K-1}$ by assumption.

□

**THEOREM 6.5.** $\mathbf{x}$ cannot have a gradient clone $\mathbf{x}'$ with $|\mathbf{x}'| > |\mathbf{x}|$ if there exists some $\lambda \in \mathbb{R}^+$ for which

$$ \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B) = 1 + \lambda + W_0 \left( \frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}} \right) $$

where $\Delta = b_B - b_A$ and $W_0$ is the principal branch of the Lambert W-function.

*Proof.* Let $\mathbf{x}'$ be a gradient clone of $\mathbf{x}$ with $|\mathbf{x}'| > |\mathbf{x}|$. By Lemma 6.2 and Remark 6.4.2, there must exist a $K > 1$ s.t. $\mathbf{x}' = K\mathbf{x}$ and let it be written as $K = 1 + T$ for some $T > 0$. Hence, setting
$\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$ and $\Delta = b_B - b_A$, by Lemma 6.3, we must have:

$$ 
\begin{aligned}
e^{K\gamma} - Ke^{\gamma} &= (K-1)e^{\Delta} \\
\Rightarrow e^{\gamma+\gamma T} - (1+T)e^{\gamma} &= Te^{\Delta} \\
\Rightarrow e^{\gamma T} &= 1+T(1+e^{\Delta-\gamma})
\end{aligned} 
\qquad (F.6) $$

As $e^{\gamma T} > 1 + \gamma T$, if we have $\gamma \ge 1 + e^{\Delta-\gamma}$, we would obtain $e^{\gamma T} > 1 + \gamma T \ge 1 + (1 + e^{\Delta-\gamma})T$, implying that (F.6) has no solution for any $T > 0$. Therefore, it is sufficient to have $\gamma \ge 1 + e^{\Delta-\gamma}$ to ensure that $\mathbf{x}$ does not have any gradient clone $\mathbf{x}'$ s.t. $|\mathbf{x}'| > |\mathbf{x}|$. But we observe:

$$ 
\begin{aligned}
\gamma &\ge 1 + e^{\Delta-\gamma} \\
\Leftrightarrow e^{\gamma}\gamma &\ge e^{\gamma} + e^{\Delta} \\
\Leftrightarrow e^{\gamma}(\gamma - 1) &\ge e^{\Delta} \\
\Leftrightarrow e^{-\gamma} &= e^{-\Delta}(\gamma - 1) - \lambda \quad \text{for some } \lambda > 0 \\
\Leftrightarrow e^{-\gamma} &= e^{-\Delta}(\gamma - (1 + \lambda e^{\Delta}))
\end{aligned} 
\qquad (F.7) $$

By the theory of generalization of Lambert W-functions [249], we must have: $\gamma = 1 + \lambda + W(\frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}})$, where $W(.)$ is the Lambert W-function. But as $\frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}}$ is necessarily positive, $W(\frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}})$ must lie on the principal branch of $W(.)$ denoted by $W_0(.)$. In other words, we must have:

$$ \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B) = 1 + \lambda + W_0 \left( \frac{e^{\Delta}}{e^{(1+\lambda e^{\Delta})}} \right) $$

□

**THEOREM 6.6.** $\mathbf{x}$ has a gradient clone $\mathbf{x}'$ iff all of the following hold:

$$ \text{a)} \quad \frac{e^{\Delta}}{e^{\gamma+e^{\Delta}}} - \frac{1}{\gamma} W \left( \frac{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}}{e^{\gamma+e^{\Delta}}} \right) \neq 1 $$

$$ \text{b)} \quad e^{-1}(e^{\gamma} + e^{\Delta}) < \gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}} $$

$$ \text{c)} \quad \mathbf{x}' = K\mathbf{x} \text{ with } K = \frac{e^{\Delta}}{e^{\gamma+e^{\Delta}}} - \frac{1}{\gamma} W \left( \frac{\frac{\gamma e^{\Delta}}{e^{\gamma+e^{\Delta}}}}{e^{\gamma+e^{\Delta}}} \right) $$

where $\gamma = \mathbf{x} \cdot (\mathbf{w}_A - \mathbf{w}_B)$, $\Delta = b_B - b_A$, and $W(.)$ is the Lambert W-function.

*Proof.* Let $\mathbf{x}'$ be a gradient clone of $\mathbf{x}$. Then, by Lemma 6.2, $\mathbf{x}'$ must be of the form $K\mathbf{x}$ for some $K > 0$ and, by Lemma 6.3, such a $K$ must satisfy (6.13). In particular, we must have:

$$ 
\begin{aligned}
e^{K\gamma} - Ke^{\gamma} &= (K-1)e^{\Delta} \\
\Leftrightarrow e^{K\gamma} &= K(e^{\gamma} + e^{\Delta}) - e^{\Delta} \\
\Leftrightarrow e^{K\gamma} &= (e^{\gamma} + e^{\Delta})(K - \frac{e^{\Delta}}{e^{\gamma} + e^{\Delta}}) \\
[\text{as } e^{\gamma} + e^{\Delta} > 0]
\end{aligned} 
$$
$$ \Rightarrow K = \frac{e^{\Delta}}{e^{\gamma} + e^{\Delta}} - \frac{1}{\gamma} W \left( \frac{-\gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}}{e^{\gamma} + e^{\Delta}} \right) \qquad (F.8) $$

[by the theory of generalization of Lambert W-function [249]]

a) By definition of a gradient clone as in Definition 6.4.1, $x' \neq x$. Hence, we must have $K \neq 1$ in (F.8).

b) $W\left(\frac{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}{e^{\gamma}+e^{\Delta}}\right)$ and, correspondingly, (F.8) have no real solution if:

$$ \frac{-\gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}}{e^{\gamma}+e^{\Delta}} < -e^{-1} \Rightarrow e^{-1}(e^{\gamma} + e^{\Delta}) < \gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}} $$

c) If conditions a and b hold, $x'$ is a gradient clone of $x$ iff $x' = Kx$ where $K$ is as in (F.8).

□

**COROLLARY 6.7.** $x$ has at most two gradient clones in $\mathbb{R}^n$.

*Proof.* Let $x$ be any gradient clone of $x$. By Theorem 6.6, $x' = \left( \frac{e^{\Delta}}{e^{\gamma}+e^{\Delta}} - \frac{1}{\gamma} W\left( \frac{-\gamma e^{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}}{e^{\gamma}+e^{\Delta}} \right) \right)x$ where $\gamma = x \cdot (w_A - w_B)$, $\Delta = b_B - b_A$, and $W(.)$ is the Lambert W-function. From the theory of Lambert W-functions [249], we recall that $W\left(\frac{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}{e^{\gamma}+e^{\Delta}}\right)$

i) has exactly one real solution when $\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}} \in [0, \infty) \cup \{-e^{-1}\}$ which is given by its principal branch $W_0\left(\frac{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}{e^{\gamma}+e^{\Delta}}\right)$.

ii) has exactly two real solutions when $\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}} \in (-e^{-1}, 0)$ which are given by $W_1\left(\frac{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}{e^{\gamma}+e^{\Delta}}\right)$.

iii) has no real solution when $\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}} < -e^{-1}$ as is addressed by condition c) of Theorem 6.6.

As the values of $w_A, w_B, b_A, b_B$ are all fixed, any gradient clone of $x$ has at most the same number of gradient clones as the number of real solutions of $W\left(\frac{\frac{\gamma e^{\Delta}}{e^{\gamma}+e^{\Delta}}}{e^{\gamma}+e^{\Delta}}\right)$. □

**LEMMA 6.8.** If batches $B = \{x_1, \dots, x_k\}$ and $B' = \{x'_1, \dots, x'_k\}$ are gradient clones, we must have $X\pi = X'\pi'$ where:

$$ X = \begin{pmatrix} x_{11} & \dots & x_{k1} \\ \vdots & \vdots & \vdots \\ x_{1n} & \dots & x_{kn} \end{pmatrix}, \quad X' = \begin{pmatrix} x'_{11} & \dots & x'_{k1} \\ \vdots & \vdots & \vdots \\ x'_{1n} & \dots & x'_{kn} \end{pmatrix}, $$
$$ \pi = \begin{pmatrix} p_{11} - 1 & p_{21} & \dots & p_{k1} & \dots p_{m1} \\ p_{12} & p_{22} - 1 & \dots & p_{k2} & \dots p_{m2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p_{1k} & p_{2k} & \dots & p_{kk} - 1 & \dots p_{mk} \end{pmatrix}, $$

$$ \pi' = \begin{pmatrix} p'_{11} - 1 & p'_{21} & \dots & p'_{k1} & \dots p'_{m1} \\ p'_{12} & p'_{22} - 1 & \dots & p'_{k2} & \dots p'_{m2} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ p'_{1k} & p'_{2k} & \dots & p'_{kk} - 1 & \dots p'_{mk} \end{pmatrix}, $$

and $p_{js} = \mathbb{P}[\mathbf{x}_s = L_j]$ (i.e., the output probability of the $s$th input of batch $X$ to be classified as label $L_j$) and, similarly, $p'_{js} = \mathbb{P}[\mathbf{x}'_s = L_j]$ for $s = 1, \dots, k$ and $j = 1, \dots, m$.

*Proof.* Generalising the derivation of the gradient updates w.r.t. the weights in the FC layer for binary classification (as in Eqns. (6.10), (6.11), and (6.12)) to a classification task involving $m$ labels, for a specific training input $\mathbf{x} \in \mathbb{R}_{\ge 0}^n$ to the FC layer, we obtain:

$$ \frac{\partial \mathcal{L}}{\partial w_i} = \sum_{j=1}^{m} \frac{\partial \mathcal{L}}{\partial P_j(\mathbf{x})} \frac{\partial P_j(\mathbf{x})}{\partial z_i} \frac{\partial z_i}{\partial w_i} \\ = y_i(\mathbf{x})(P_i - 1)\mathbf{x} + \sum_{\substack{j=1 \\ j \neq i}}^{m} y_j(\mathbf{x})P_i\mathbf{x} \qquad (F.9) $$

Therefore, if the true label of $\mathbf{x}_s = (x_{s1}, \dots, x_{sn}) \in \mathbb{R}_{\ge 0}^n$ was $L_s$ for all $s \in \{1, \dots, k\}$, then for every $r \in \{1, \dots, k\}$ and $j \in \{1, \dots, n\}$:

$$ (\nabla \mathbf{w}(x_{sj}))_r = \begin{cases} (P_s(\mathbf{x}) - 1)x_{sj} & \text{if } s = r \\ P_r(\mathbf{x})x_{sj} & \text{o.w.} \end{cases} \qquad (F.10) $$

Hence, for each $\mathbf{x}_s = (x_{s1}, \dots, x_{sn}) \in B$:

$$ \nabla \mathbf{w}_B(\mathbf{x}_s) = (\nabla \mathbf{w}(x_{s1}), \dots, \nabla \mathbf{w}(x_{sn}))^\mathrm{T} = \begin{pmatrix} P_1(\mathbf{x}_s)x_{s1} & \dots & (P_s(\mathbf{x}_s) - 1)x_{s1} & \dots & P_m(\mathbf{x}_s)x_{s1} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ P_1(\mathbf{x}_s)x_{sn} & \dots & (P_s(\mathbf{x}_s) - 1)x_{sn} & \dots & P_m(\mathbf{x}_s)x_{sn} \end{pmatrix} $$

Thus, the gradient update averaged over the batch members that is shared with the server is:

$$ \frac{\sum_{i=1}^{k} \nabla \mathbf{w}_B(\mathbf{x}_i)}{k} = \frac{1}{k} W_B \qquad (F.11) $$
where $W_B \in \mathbb{R}^{n \times m}$ such that:

$$W_B(i, j) = \sum_{\substack{s=1 \\ s \neq j}}^{k} P_j(\mathbf{x}_s)x_{si} + (P_j(\mathbf{x}_j) - 1)x_{ji} \qquad (F.12)$$

Therefore, if batches $B = \{\mathbf{x}_1, \dots, \mathbf{x}_k\}$ and $B' = \{\mathbf{x}'_1, \dots, \mathbf{x}'_k\}$ are gradient clones s.t. $y(\mathbf{x}_s) = y(\mathbf{x}'_s) = L_s$ for every $s \in \{1, \dots, k\}$, we must have $W_B = W_{B'}$

$$\iff \sum_{\substack{s=1 \\ s \neq j}}^{k} P_j(\mathbf{x}_s)x_{si} + (P_j(\mathbf{x}_j) - 1)x_{ji} = \sum_{\substack{s=1 \\ s \neq j}}^{k} P_j(\mathbf{x}'_s)x'_{si} + (P_j(\mathbf{x}'_j) - 1)x'_{ji} \qquad (F.13)$$

for every $i \in \{1, \dots, n\}$ and $j \in \{1, \dots, k\}$.

Unifying the notations with the theorem statement (i.e., $P_j(\mathbf{x}_s) = p_{js}$ and $P_j(\mathbf{x}'_s) = p'_{js}$, as an alternative representation of (F.13), we conclude that if $B$ and $B'$ are gradient clones, we must have:

$$X\pi = X'\pi' \qquad (F.14)$$

where:

$$X = \begin{pmatrix} x_{11} & \dots & x_{k1} \\ \vdots & \vdots & \vdots \\ x_{1n} & \dots & x_{kn} \end{pmatrix}, \quad X' = \begin{pmatrix} x'_{11} & \dots & x'_{k1} \\ \vdots & \vdots & \vdots \\ x'_{1n} & \dots & x'_{kn} \end{pmatrix},$$

$$\pi = \begin{pmatrix} p_{11} - 1 & p_{21} & \dots & p_{k1} & \dots & p_{m1} \\ p_{12} & p_{22} - 1 & \dots & p_{k2} & \dots & p_{m2} \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ p_{1k} & p_{2k} & \dots & p_{kk} - 1 & \dots & p_{mk} \end{pmatrix},$$

$$\pi' = \begin{pmatrix} p'_{11} - 1 & p'_{21} & \dots & p'_{k1} & \dots & p'_{m1} \\ p'_{12} & p'_{22} - 1 & \dots & p'_{k2} & \dots & p'_{m2} \\ \vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\ p'_{1k} & p'_{2k} & \dots & p'_{kk} - 1 & \dots & p'_{mk} \end{pmatrix}.$$

□

**THEOREM 6.9.** If the data in the batch that is used to train a certain round are similar and when the FL model learns well, the spatial arrangement of the members of the batch used for training is unique with respect to the shared gradients.

*Proof.* Noting that $\sum_{j=1}^{m} p_{js} = 1$, we have $\sigma_s - 1 = -(m-1)r_s$ for every $s \in \{1, \dots, k\}$. Therefore, we may rewrite (6.14) as:

$$\sum_{\substack{s=1 \\ s \neq j}}^{m} (x_{si} - x'_{si})r_j + (x_{ji} - x'_{ji})(-(m-1)r_j) = 0$$
$$
\begin{align*}
&\Rightarrow \sum_{\substack{s=1 \\ s \neq j}}^{m} (x_{si} - x'_{si}) r_j = (x_{ji} - x'_{ji})(m-1)r_j \\
&\Rightarrow \sum_{s=1}^{m} (x_{si} - x'_{si}) r_j = (x_{ji} - x'_{ji})mr_j \\
&\Rightarrow \frac{\sum_{s=1}^{m} (x_{si} - x'_{si}) r_j}{m} = (x_{ji} - x'_{ji}) r_j \tag{F.15}
\end{align*}
$$

Eqn. (F.15) essentially implies that:

$$
(x_{1i} - x'_{1i}) r_1 = (x_{2i} - x'_{2i}) r_2 = \dots = (x_{ki} - x'_{ki}) r_k \quad (\text{F.16})
$$

Moreover, realistically $\sigma_j < 1$ and, thus, $r_j > 0$ for every $j \in \{1, \dots, k\}$. Under this setting and as we are given $\mathbf{x}_{j1} \approx \mathbf{x}_{j2}$ for every $j_1, j_2 \in \{1, \dots, k\}$, Eqn. (F.16) would mean:

$$
\begin{align}
x_{1i} - x'_{1i} &= x_{2i} - x'_{2i} = \dots = x_{ki} - x'_{ki} \notag \\
\Rightarrow x_{si} - x_{ti} &= x'_{si} - x'_{ti} \quad \forall s, t \in \{1, \dots, k\}, \quad i \in \{1, \dots, n\} \tag{F.17}
\end{align}
$$

From Eqn. (F.17) we can conclude that $d_p(\mathbf{x}_s, \mathbf{x}_t) = d_p(\mathbf{x}'_s, \mathbf{x}'_t) \forall s, t \in \{1, \dots, k\}$ where $d_p$ is any $\ell^p$ norm. Therefore, in particular, with $p = 2$ we must have:

$$
\|\mathbf{x}_s - \mathbf{x}_t\|_2 = \|\mathbf{x}'_s - \mathbf{x}'_t\|_2 \quad \forall s, t \in \{1, \dots, k\} \quad (\text{F.18})
$$

Eqn. (F.18) illustrates that, under the aforementioned assumptions, if a potential batch $B'$ is
a gradient clone of the true batch $B$ used for training, the spatial arrangement of $B'$ must be the
same as $B'$.

$\square$

**LEMMA 6.10.** For batch size = 2, $\pi$ (and, similarly, $\pi'$) is right-invertible.

Proof. For $k = 2$, $\Pi = \begin{pmatrix} p_{11}-1 & p_{21} & \cdots & p_{m1} \\ p_{12} & p_{22}-1 & \cdots & p_{m2} \end{pmatrix}$ where $p_{js} = \mathbb{P}[\mathbf{x}_s = L_j]$ is the output (softmax) probability of the $s^{th}$ input of batch $X$ (with true label $L_s$) to be classified as label $L_j$. Let $\alpha, \beta \in \mathbb{R}$, not both 0, such that $\alpha\Pi[1] + \beta\Pi[2] = \mathbf{0}_{1 \times m}$.

**Case 1:** $\alpha\beta \ge 0$, i.e., $\alpha$ and $\beta$ are of the same sign: W.l.o.g., let $\alpha \ge 0, \beta > 0$. Then $\alpha p_{31}, \dots, \alpha p_{m1} \ge 0$ and $\beta p_{32}, \dots, \beta p_{m2} > 0$. Hence, $\alpha\Pi[1]_j + \beta\Pi[2]_j > 0$ for every $j \in \{3, \dots, m\}$.

**Case 2:** $\alpha$ and $\beta$ are of opposite signs: W.L.O.G., let $\alpha \ge 0, \beta < 0$. Then $\alpha p_{21} \ge 0$ and $\beta(p_{22} - 1) > 0$. Hence, $\alpha\Pi[1]_2 + \beta\Pi[2]_2 > 0$.

Both the cases make us arrive to a contradiction suggesting that no such $\alpha, \beta$ can exist.
Hence, the rows of $\Pi$ are linearly independent and, hence, $\Pi$ is right-invertible.
$\square$

**THEOREM 6.12.** $d_E(\mathbf{x}_i, \mathbf{x}'_i) = d_E(\delta_{1i}\mathbf{x}_1, -\delta_{2i}\mathbf{x}_2)$ for $i=1,2$, where $D = \mathbf{I}_{2 \times 2} + \delta$.

$$
\text{\textit{Proof.}} \text{ Let } D = \mathbf{I}_{2 \times 2} + \delta = \begin{pmatrix} D_{11} & D_{12} \\ D_{21} & D_{22} \end{pmatrix} = \begin{pmatrix} 1 + \delta_{11} & \delta_{12} \\ \delta_{21} & 1 + \delta_{22} \end{pmatrix} \text{ for some } \delta_{ij} \in \mathbb{R} \text{ for } i, j \in \{1, 2\}.
$$
Plugging in $D = \mathbb{I}_{2 \times 2} + \delta$ into Corollary 6.11, we have:

$$x'_{1i} = x_{1i} + \delta_{11}x_{1i} + \delta_{21}x_{2i} \qquad (F.19)$$

$$x'_{2i} = x_{2i} + \delta_{12}x_{1i} + \delta_{22}x_{2i} \qquad (F.20)$$

Let us start with the case of $i = 1$:

$$ \begin{aligned} d_E(\mathbf{x}_1, \mathbf{x}'_1) &= \left( \sum_{i=1}^{n} |x_{1i} - x'_{1i}|^2 \right)^{\frac{1}{2}} \\ &= \left( \sum_{i=1}^{n} |\delta_{11}x_{1i} + \delta_{21}x_{2i}|^2 \right)^{\frac{1}{2}} \quad [\text{using (F.19)}] \\ &= d_E(\delta_{1i}\mathbf{x}_1, -\delta_{2i}\mathbf{x}_2) \end{aligned} \qquad (F.21) $$

The case of $i = 2$ proceeds exactly the same way. $\square$

**LEMMA 6.13.** Let $z_{k-1}$ be the vector of outputs from the penultimate layer $k-1$ of a neural network. Assume a single non-zero value $z_{j,k-1}$ is revealed. Then every $z_{i,k-1}$ for $i \neq j$ can be deduced by an adversary with knowledge of the network and gradients.

*Proof.* From (6.19) we can deduce the value of $p_i(\mathbf{x}) - y_i(\mathbf{x})$ from the revealed $z_{j,k-1}$ and the corresponding gradient $\nabla w_{j,i,k-1}(\mathbf{x})$. Thus we can also deduce the values of the remaining $z_{i,k-1}$ using the partial derivatives $z_{i,k-1}(p_i(\mathbf{x}) - y_i(\mathbf{x}))$. $\square$

**THEOREM 6.14.** Let $z_{k-1}$ denote the vectors of outputs from penultimate layer of the NN, and let $\mathbf{x}$ be the vector of inputs. Then an adversary with knowledge of $z_{k-1}$ learns the values in $\mathbf{x}$ exactly.

*Proof.* The proof follows by induction. We first show that knowledge of the penultimate layer leaks the values in the previous layer. We have:

$$ \begin{aligned} \nabla w_{i,j,k-1} &= z_{i,k-2} \frac{\partial \mathcal{L}}{\partial z_{i,k-1}} \\ &= z_{i,k-2} \sum_m w_{i,m,k} \frac{\partial \mathcal{L}}{\partial z_{m,k}} \quad [\text{from (6.23)}] \\ &= z_{i,k-2} \sum_m w_{i,m,k} (p_m(\mathbf{x}) - y_m(\mathbf{x})) \quad [\text{from (6.21)}] \\ &= z_{i,k-2} \sum_m w_{i,m,k} (p_m(\mathbf{x}) - y_m(\mathbf{x})) \quad [\text{from (6.22)}] \end{aligned} $$
Since $p_m(\mathbf{x}) - y_m(\mathbf{x})$ is leaked from $z_{k-1}$ and knowledge of the gradients (recall (6.19)), then we have that $z_{i,k-2}$ is deducible (since the $w_{i,m,k}$ and $\nabla w_{i,j,k-1}$ are known to the adversary). Thus the output values in layer $k-2$ are leaked through knowledge of the values in layer $k-1$.

The induction step gives us that from knowledge of any hidden layer (or more precisely, the derivatives in any hidden layer), we can infer the values and derivatives in the previous layer.

In particular, note that from any derivative $\frac{\partial \mathcal{L}}{\partial z_{i,h}}$ we can compute derivatives in the previous layer $\frac{\partial \mathcal{L}}{\partial z_{i,h-1}}$ (by (6.21)). And since we can compute those derivatives at the final layer (by (6.22)) then they are computable all the way through to the first hidden layer.

Secondly, knowledge of the derivatives at any layer $h$ leaks the output values $z_{h-1}$ of the previous layer (by (6.23)), and when $h$ is the first layer, leaks the values of $\mathbf{x}$ (by (6.24)).

Finally, we address the issue caused by ReLU in that sometimes the values of the derivatives are 0 (eg. in (6.21)). Observe that from (6.21), that if the outputs from a layer are all zero'ed (by ReLU), then so are the derivatives $\frac{\partial \mathcal{L}}{\partial z_{i,h}}$ on the previous layers (follows by recursion). And therefore, by (6.23), the gradient updates are also zero, which means the network does not learn anything on any of the previous layers. We conclude that, for the network to learn, there must exist a node in each layer which is not zero'ed by the ReLU activation, and therefore by which the gradients can leak information about the input values $\mathbf{x}$.

Thus, we conclude by induction that knowledge of the penultimate layer leaks the values of $\mathbf{x}$ exactly. $\square$
**LEMMA 7.1.** If $u_i$ reports a price greater than her true price, i.e., $p_i \ge \pi_i$, then her utility will be less than the utility for the true price, i.e., $\rho(p_i) \le \rho(\pi_i)$.

*Proof.* Suppose the $i^{th}$ provider reports the privacy price as $p_i > \pi_i$. We want to show:

$$ \begin{align*} \rho(\pi_i) - \rho(p_i) &> 0 \\ &\iff \mu(\pi_i) - \pi_i f(\pi_i) - \mu(p_i) + \pi_i f(p_i) &> 0 \\ &\iff \mu(\pi_i) - \mu(p_i) - \pi_i(f(\pi_i) - f(p_i)) &> 0 \\ &\iff \pi_i f(\pi_i) + \int_{\pi_i}^{\infty} f(z) dz - (p_i f(p_i) + \int_{p_i}^{\infty} f(z) dz) - \pi_i(f(\pi_i) - f(p_i)) &> 0 \\ &\iff \pi_i f(p_i) - p_i f(p_i) + \int_{\pi_i}^{p_i} f(z) dz &> 0 \\ &\iff \int_{\pi_i}^{p_i} f(z) dz &> f(p_i)(p_i - \pi_i) \end{align*} $$

Note that $f$ is a monotonically decreasing function. Let $g(p) = f(\pi_i) - f(p)$ for any $p \in \mathbb{R}$. Furthermore, $\int_{\pi_i}^{p_i} f(z) dz$ can be written as $f(p_i)(p_i - \pi_i) + \int_{\pi_i}^{p_i} g(z) dz$. Observe that $f$ is monotonically decreasing means $g(.)$ is monotonically decreasing, hence, $g(\pi_i) > g(p)$ for any $p > \pi_i$, $g(p_i) > 0$. Hence, $\int_{\pi_i}^{p_i} g(z) dz > 0 \Rightarrow \int_{\pi_i}^{p_i} f(z) dz > f(p_i)(p_i - \pi_i) \Rightarrow (2)$. $\square$ $\square$

**LEMMA 7.2.** If $u_i$ reports a price smaller than her true price, i.e., $p_i \le \pi_i$, then her utility will be less than the utility for the true price, i.e., $\rho(p_i) \le \rho(\pi_i)$.

*Proof.* Similar and symmetric argument to Lemma 7.1. $\square$ $\square$
**THEOREM 7.4.** If $\tau(\cdot)$ is additive, then maximizing information and maximizing profit (desiderata (a) and (b)) are equivalent, in the sense that a $\varepsilon$-allocating function $f(\cdot, \cdot)$ that maximizes the one, maximizes also the other.

*Proof.* Let $\tau$ be a monotonically increasing and additive function representing the pay-off earned by the data consumer by processing the information obtained from the different data providers. We wish to maximize her profit, i.e., $\sum_{i=1}^n (\tau(\varepsilon_i) - \mu(p_i))$ for a fixed budget of expenses $B$, i.e., $\sum_{i=1}^n \mu(p_i) = B$. Therefore, we boil down to maximizing $\sum_{i=1}^n \tau(\varepsilon_i) = \tau(\sum_{i=1}^n \varepsilon_i)$ for $\sum_{i=1}^n \mu(p_i) = B$, where $\varepsilon_i = f(c, p_i)$. As $\tau$ is increasing, it attains maximum if and only if $\sum_{i=1}^n \varepsilon_i = \sum_{i=1}^n f(c, p_i)$ is maximum. Then just observe that $\sum_{i=1}^n f(c, p_i) = I(u)$ (cf. Definition 7.3.3). $\square$

**THEOREM 7.6.** If $\tau$ is additive, then there exists a $c$ that gives an optimal **profit-maximizing** function $f(c, \cdot) \in \mathcal{F}$, for a fixed budget, and we can derive such $c$ via the method of the Lagrangians.

*Proof.* The profit of the data consumer is $\sum_{i=1}^n (\tau(\varepsilon_i) - \mu(p_i))$, where $\varepsilon_i = f(c, p_i)$. Therefore, to maximize her profit for a fixed budget of expenses $B$ (used to pay the incentives to the data providers), i.e., $\sum_{i=1}^n \mu(p_i) = B$, we just have to maximize $\sum_{i=1}^n \tau(\varepsilon_i) = \sum_{i=1}^n \tau(f(p_i))$, which by the assumption of additivity of $\tau$, is equal to $\tau(\sum_{i=1}^n f(c, p_i))$.

Note that the definition of $\mathcal{F}$ (cf. (7.1)) ensures that all its functions are continuous on $c$. Since the sum of continuous functions is continuous, we have that also $\sum_{i=1}^n f(c, p_i)$ is continuous on $c$. Moreover, $c$ ranges in a closed interval: $c \in [0, c_{\min}]$, where $c_{\min} = \min_{p \in \{p_1, \dots, p_n\}} \{c : f(c, p) = 0\}$. Thus, by *Extreme Value Theorem*, there exists a $c$ which maximizes $\sum_{i=1}^n f(c, p_i)$, which, in turn, maximizes $\sum_{i=1}^n (\tau(\varepsilon_i) - \mu(p_i))$.

Furthermore, the condition of differentiability makes possible to apply the method of the lagrangians to find the maximum, by imposing that the partial derivatives are 0. The concavity condition implies that those points correspond to a (global) maximum. $\square$

**THEOREM 7.7.** There exists a $c$ that gives an optimal **information-maximizing** function $f(c, \cdot) \in \mathcal{F}$, for a fixed budget, and we can derive such $c$ via the method of the Lagrangians.

*Proof.* By the sequential compositionality of differential privacy, the total information obtained by the data consumer is $\sum_{i=1}^n \varepsilon_i = \sum_{i=1}^n f(c, p_i)$. The rest follows as the proof of Theorem 7.6. $\square$

$\square$
Examples from Chapter 7

**Example 7.3.3** Let $\mathcal{F} = \{\ln(e - cp) : c \in \mathbb{R}^+\}$. We want to maximize

$$F(c) = \sum_{i=1}^{n} f(c, p_i)$$

subject to the constraint

$$G(c) = \sum_{i=1}^{n} \mu(p_i) = \sum_{i=1}^{n} [p_i \ln(e - cp_i) + \int_{p_i}^{\frac{e-1}{c}} \ln(e - zp_i)dz] - B = 0,$$

for a fixed budget constant $B \in \mathbb{R}^+$. By the sequential compositionality of differential privacy, we have $\sum_{i=1}^{n} f(c, p_i) = \sum_{i=1}^{n} \ln(e - cp_i)$. Furthermore, $G(c) = \sum_{i=1}^{n} [p_i \ln(e - cp_i) + p_i \ln(\frac{e}{e - cp_i}) + \frac{e}{c} \ln(e - cp_i)] - K = 0$ where $K = B + \frac{n(e-1)}{c}$.

Using the method of Lagrange multipliers, we define the Lagrangian function $\mathcal{L}(c, \lambda) = F(c) - \lambda(G(c) - K) = \sum_{i=1}^{n} \ln(e - cp_i) - \lambda(\sum_{i=1}^{n} [p_i \ln(e - cp_i) + p_i \ln(\frac{e}{e - cp_i}) + \frac{e}{c} \ln(e - cp_i)] - K) = \sum_{i=1}^{n} \ln(e - cp_i) - \lambda(\sum_{i=1}^{n} [p_i + \frac{e}{c} \ln(e - cp_i)] - K)$. Thus we have

$$\mathcal{L}(c, \lambda) = \sum_{i=1}^{n} \ln(e - cp_i) - \lambda \sum_{i=1}^{n} p_i - \frac{\lambda e}{c} \sum_{i=1}^{n} \ln(e - cp_i) + \lambda K \quad (H.1)$$

Hence, to find the optimal solution of c, we wish to solve the following:

$$\frac{\partial \mathcal{L}(c, \lambda)}{\partial \lambda} = 0 \qquad (H.2)$$

$$\frac{\partial \mathcal{L}(c, \lambda)}{\partial c} = 0 \qquad (H.3)$$
Solving equation (H.2), we get

$$ 
\begin{aligned}
\frac{\partial \mathcal{L}(c, \lambda)}{\partial \lambda} &= 0 \\
\iff K - \sum_{i=1}^{n} \left[ p_i + \frac{e}{c} \ln(e - c p_i) \right] &= 0 \\
\iff \sum_{i=1}^{n} \left[ p_i + \frac{e}{c} \ln(e - c p_i) \right] &= K \\
\iff \ln\left(\prod_{i=1}^{n} e^{p_i} (e - c p_i)^{\frac{e}{c}}\right) &= K
\end{aligned}
\qquad (H.4)
$$

Observe that:

$$ \lim_{c \to 0} \ln \left( \prod_{i=1}^{n} e^{p_i} (e - c p_i)^{\frac{e}{c}} \right) = \infty \qquad (H.5) $$

$$ \lim_{c \to \infty} \ln \left( \prod_{i=1}^{n} e^{p_i} (e - c p_i)^{\frac{e}{c}} \right) = 0 \qquad (H.6) $$

Combining (H.5), (H.6), the fact that $K = B + \frac{n(e-1)}{c} > 0$, and $\ln(\prod_{i=1}^{n} e^{p_i} (e - c p_i)^{\frac{e}{c}})$ is continuous, by the Intermediate Value Theorem [206], we, thereby, can conclude that the curve $y = \ln(\prod_{i=1}^{n} e^{p_i} (e - c p_i)^{\frac{e}{c}})$ intersects the curve $y = K$ at least once for $c \in (0, \infty)$, implying that we have at least one solution of (H.4) ($\dagger_1$).

Moreover, solving equation (H.3), we get

$$ 
\begin{aligned}
\frac{\partial \mathcal{L}(c, \lambda)}{\partial c} &= 0 \\
\iff \frac{\partial \left( \sum_{i=1}^{n} \ln(e - c p_i) \left(1 - \frac{\lambda e}{c}\right) - \lambda \sum_{i=1}^{n} p_i + K \right)}{\partial c} &= 0 \\
\iff \frac{\partial \left( \sum_{i=1}^{n} \ln(e - c p_i) \left(1 - \frac{\lambda e}{c}\right) \right)}{\partial c} &= 0 \\
\iff \sum_{i=1}^{n} \frac{-p_i}{e - c p_i} \left(1 - \frac{\lambda e}{c}\right) + \frac{\lambda e}{c^2} \sum_{i=1}^{n} \ln(e - c p_i) &= 0
\end{aligned}
\qquad (H.7)
$$

Equation (H.7) is linear in $\lambda$, implying for every given $c$, we will find a $\lambda$ satisfying (H.7) ($\dagger_2$).

Therefore, combining ($\dagger_1$) and ($\dagger_2$), we conclude that there is at least one optimal choice of $f(\cdot, \cdot)$ in $\mathcal{F}$ that maximizes the information gathered by the data consumer, subject to the fixed budget.

**Example 7.3.4** Let $\mathcal{F} = \{1 - cp : c \in \mathbb{R}^+\}$. We want to maximize

$$ F(c) = \sum_{i=1}^{n} f(p_i) = \sum_{i=1}^{n} (1 - c p_i) $$

subject to

$$ G(c) = \sum_{i=1}^{n} \mu(p_i) = \sum_{i=1}^{n} [p_i(1 - c p_i) + \int_{p_i}^{\frac{1}{c}} (1 - cz) dz] = B, $$
for a fixed budget $B \in \mathbb{R}^+$.

Observe that $G(c) = \frac{n}{2c} - \frac{c}{2} \sum_{i=1}^{n} p_i^2$. Using the method of Lagrange multipliers, we define the Lagrangian function $\mathcal{L}(c, \lambda) = F(c) - \lambda(G(c) - B) = -c \sum_{i=1}^{n} p_i - \lambda(\frac{n}{2c} - \frac{c}{2} \sum_{i=1}^{n} p_i^2 - B)$. Thus we have

$$ \mathcal{L}(c, \lambda) = -c \sum_{i=1}^{n} p_i - \lambda \left( \frac{n}{2c} - \frac{c}{2} \sum_{i=1}^{n} p_i^2 - B \right) \quad (H.8) $$

Hence, to find the optimal solution of $c$, we solve the following:

$$ \frac{\partial \mathcal{L}(c, \lambda)}{\partial \lambda} = 0 \qquad (H.9) $$

$$ \frac{\partial \mathcal{L}(c, \lambda)}{\partial c} = 0 \qquad (H.10) $$

Solving equation (H.9), we get

$$ \begin{aligned} \frac{\partial \mathcal{L}(c, \lambda)}{\partial \lambda} &= 0 \\ &\iff -\left(\frac{n}{2c} - \frac{c}{2} \sum_{i=1}^{n} p_i^2 - B\right) = 0 \\ &\iff \frac{n}{2c} - \frac{c}{2} \sum_{i=1}^{n} p_i^2 = B \\ &\iff c^2 \sum_{i=1}^{n} p_i^2 + 2Bc - n = 0 \end{aligned} \qquad (H.11) $$

Note that the LHS of equation (H.11) is a quadratic equation in $c$, and as $4B^2+4n \sum_{i=1}^{n} p_i^2 > 0$, equation (H.11) has two distinct roots, or candidates for choosing the optimal $c$ ($\dagger'_1$).

Moreover, solving equation (H.10), we get

$$ \begin{aligned} \frac{\partial \mathcal{L}(c, \lambda)}{\partial c} &= 0 \\ &\iff -\sum_{i=1}^{n} p_i + \frac{\lambda n}{2c^2} + \frac{\lambda}{2} \sum_{i=1}^{n} p_i^2 = 0 \end{aligned} \qquad (H.12) $$

Note that for every given $c$, we will find a $\lambda$ satisfying (H.12) ($\dagger'_2$).

Therefore, combining ($\dagger'_1$) and ($\dagger'_2$), we conclude that there is at least one optimal choice of $f(\cdot, \cdot)$ in $\mathcal{F}_1$ that maximizes the information gathered by the data consumer, subject to the fixed budget.
**THEOREM 8.1.** If the privacy valuation function used in order to impose the penalty scheme to any member $p$ of a federation $F$ is $f(m) = K_1(e^{K_2m} - 1)$, the Shapley valuation function $\psi$ chosen must satisfy

$$ \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi\left(\varepsilon_p^T, \frac{\ln\left(\frac{w^*\varepsilon_p^T}{K_1} + K\right)}{K_2}\right), $$

where $K = \frac{1}{K_1} \sum_{\substack{p' \neq p \\ p' \in F}} d(m)_{p'} \varepsilon_{p'}^T + 1$ and $w^*$ is the scaling parameter as given by (8.2).

*Proof.* Using the privacy valuation function $f(m) = K_1(e^{K_2m} - 1)$, we have $f^{-1}(\varepsilon) = \frac{\ln(\frac{\varepsilon}{K_1} + 1)}{K_2}$. Let $p$ be an arbitrary member of $F$ with a maximum privacy threshold $\varepsilon_p^T$. Therefore, in order to impose a penalty scheme on $p$, it needs to be ensured that

$$ \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi(v, M) \Rightarrow \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi(v, f^{-1}(\varepsilon_F^P)) $$

$[\because w^* \in [0, 1]$ is the scaling parameter chosen by $D$ and $\varepsilon_F^P = w^* \varepsilon_F^T]$

$$ \Rightarrow \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi\left(v, \frac{\ln\left(\frac{\varepsilon_F^P}{K_1} + 1\right)}{K_2}\right) \Rightarrow \frac{\ln\left(\frac{\varepsilon_p^T}{K_1} + 1\right)}{K_2} < \psi\left(v, \frac{\ln\left(\frac{C_0 + w^* \varepsilon_p^T}{K_1} + 1\right)}{K_2}\right) $$
$$
\left[
\begin{array}{l}
\text{where } C_0 = \sum_{p' \neq p \in F} d_p' \epsilon_{p'}^T \text{ is a constant} \\
\Rightarrow \frac{\ln\left(\frac{\epsilon_p^T}{K_1} + 1\right)}{K_2} < \psi \left( \nu, \frac{\ln\left(\frac{C_0 + w^* \epsilon_p^T}{K_1} + 1\right)}{K_2} \right) \Rightarrow \frac{\ln\left(\frac{\epsilon_p^T}{K_1} + 1\right)}{K_2} < \psi \left( \nu, \frac{\ln\left(\frac{w^* \epsilon_p^T}{K_1} + K\right)}{K_2} \right) \quad (I.1) \\
\left[
\begin{array}{l}
\text{where } K = \frac{C_0}{K_1} + 1
\end{array}
\right]
\end{array}
\right.
$$

□
**Titre** : Comprendre et optimiser le compromis entre vie privée et utilité d'un point de vue fondamental

**Mots clés** : confidentialité différentielle, confidentialité de localisation, apprentissage automatique, optimisation de la confidentialité et de l'utilité

**Résumé** : Avec les récentes avancées technologiques, les menaces de violation de la vie privée concernant les données personnelles des individus augmentent plus que jamais. Si la protection de la confidentialité des informations sensibles devient plus importante que jamais, il est également crucial de préserver l'utilité des données dans la société contemporaine basée sur l'information. Differential Privacy (DP) est considérée comme l'étalon-or des garanties formelles de protection de la vie privée. Son applicabilité étendue et sa technique de mise en œuvre simple ont conduit à une croissance rapide de sa popularité et de l'intérêt pour l'étude et l'application de la confidentialité différentielle à une variété de domaines, tant dans les universités que dans l'industrie. Au fil du temps, la communauté a exploré diverses variantes de la DP pour répondre aux préoccupations en matière de protection de la vie privée dans différents contextes et dans le cadre de divers modèles de menace.

Malgré l'acceptation prolifique du DP, l'interprétation

de son interaction avec l'utilité des données reste nébuleuse, ce qui accroît le besoin de réponses à des questions rudimentaires telles que la manière dont l'ajout de bruit DP affecte l'utilité des données partagées (par exemple, la qualité de service des propriétaires de données, l'utilité statistique des fournisseurs de services, la précision de l'analyse et de la formation de modèles effectuées, etc.) et s'il existe un mécanisme DP optimal en ce qui concerne l'utilité des données dans différents domaines et contextes. L'objectif de cette thèse était de répondre à ces questions et, en particulier, d'établir une base théorique pour analyser de manière exhaustive le compromis entre la protection de la vie privée et l'utilité des données sensibles selon diverses perspectives et dans le contexte de différents cas d'utilisation. Outre la dissection de la bataille séculaire entre la vie privée et l'utilité, cette thèse développe également des mécanismes de préservation de la vie privée afin d'optimiser la perte d'utilité avec des garanties formelles de respect de la vie privée dans divers domaines d'applicabilité.

**Title** : Understanding and optimizing the trade-off between privacy and utility from a foundational perspective

**Keywords** : differential privacy, location privacy, machine learning, privacy and utility optimisation

**Abstract** : With recent advancements in technology, the threats of privacy violations of individuals' personal data are surging like never before. While protecting the privacy of sensitive information is becoming more important than ever before, it is also crucial to uphold the utility of the data in the contemporary information-based society. Differential privacy (DP) is considered to be the gold standard of formal privacy guarantees. Its widespread applicability and uncomplicated implementation technique have led to a rapid growth in its popularity and interest in studying and applying DP to a variety of domains in academia and industry alike. Over time, the community has explored various variants of DP addressing privacy concerns in different contexts and under a variety of threat models.

Despite the prolific acceptance of DP, it is still nebulous to interpret how it interacts with the utility of data,

escalating the need for answers to rudimentary questions like how adding DP noise affects the utility of the shared data (e.g., the quality of service of the data owners, the statistical utility of the service providers, the accuracy of the analysis and model training performed, etc.) and does there exist some optimal DP mechanism with respect to the usefulness of data in different realms and contexts. The objective of this thesis has been to address these questions and, in particular, establish a theoretical foundation to comprehensively analyze the trade-off between privacy and the utility of sensitive data from a variety of perspectives and in the context of different use cases. Aside from dissecting the age-old battle between privacy and utility, this thesis also develops privacy-preserving mechanisms to proceed in the direction of optimizing utility loss with formal privacy guarantees in diverse domains of applicability.