Marc Tommasi

Mikaela Keller

Aurélien Bellet

Benjamin Nguyen

Martine De Cock

Sébastien Gambs

Mohamed Maouche

Rémi Gilleron

Pascal Denis

Damien Sileo

Brij Mohan

Lal Srivastava

Mahsa Asadi

Gaurav Maheshwari

Mariana Vargas

Onkar Pandit

Carlos Jorge

Zubiaga Peña

William De Vazelhes

Kamal Macwan

Vitalii Emelianov

Abstract

In recent years, due to the growing importance of network applications and the growing concerns for privacy, there is an increasing interest in decentralized forms of machine learning. In this dissertation, we study the setting that involves a communication network of agents, where each agent locally privatizes (adds noise to) its data, and where the agents aim to collaboratively learn statistical models over their data. Such local privatization is in line with a standard of data privacy known as local differential privacy, and local differential privacy is useful when alternatives, such as secure multi-party computation or central differential privacy performed by a trusted curator, are infeasible. However, local differential privacy results, typically, in worse utility (less accurate statistical models) compared to central differential privacy because, for the same privacy budget, local differential privacy adds more privatization noise than central differential privacy. The principal question of this dissertation is the following: given that local differential privacy must be used, how could the agents maximize the utility they achieve? We study two cases to address the stated principal question.

In the first case, we consider the problem of distributed averaging, where each agent intends to collaboratively compute the unbiased average over the individual values of all agents without revealing neither their sensitive attributes nor their degree (number of neighbors). Usually, existing works solve this problem by assuming that either (i) each agent reveals its degree to its neighbors or (ii) every two neighboring agents can perform handshakes (requests that rely on replies) in every exchange of information. Since such assumptions are not always desirable, we propose an approach that is handshake-free and where the degrees are privatized. In particular, we use a gossip algorithm that computes averages that are biased when the graph of agents is non-regular (when the vertices have unequal degrees) and then perform a procedure combining multiple biased averages for bias correction. We apply the proposed approach for fitting linear regression models. We prove the asymptotic guarantee that the mean squared error between the average of privatized attributes computed by our approach and the average of sensitive attributes is O 1 n , where n is the number of agents.

In the second case, we consider a group of agents, where features (for fitting regression models) are computed by transforming sensitive attributes, and where the transformations have high-magnitude gradients or singularities. In such setting, there is a risk to magnify the privatization noise if the perturbed data is in an interval where the feature function has high-magnitude gradients. We provide a tailored noise mechanism for privatizing features by solving a convex program in such a way that (i) only pertinent intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized.

Résumé

Ces dernières années, les applications en ligne se sont beaucoup développées. Cela a attiré une plus grande attention sur les problèmes de confidentialité des données et motivé la recherche sur les formes décentralisées d'apprentissage automatique. Dans cette thèse, nous nous intéressons à la situation où les agents d'un réseau de communication souhaitent apprendre un modèle statistique de façon collaborative, tout en préservant la confidentialité de leurs données personnelles. Une façon de protéger ces données est de les obfusquer (bruiter) avant de les partager. Ce genre d'obfuscation locale est conforme à la confidentialité différentielle locale (un standard d'obfuscation des données), et la confidentialité différentielle locale est utile lorsque d'autres solutions, reposant sur le calcul multipartite sécurisé ou sur la confidentialité différentielle centrale realisée par un tiers de confiance jouant le rôle d'orchestrateur, sont irréalisables. Cependant, la confidentialité différentielle locale souffre généralement d'une utilité moindre (les modèles statistiques sont moins précis) que la confidentialité différentielle centrale car, pour le même budget de confidentialité, la confidentialité différentielle locale doit ajouter plus de bruit que la confidentialité différentielle centrale pour obfusquer les données. La question principale de cette thèse est la suivante : en garantissant la forme locale de la confidentialité différentielle, comment les agents peuvent-ils maximiser l'utilité qu'ils obtiennent ? Nous répondons à cette question dans deux cas particuliers.

Dans le premier cas, nous considérons le problème du calcul distribué, où les agents souhaitent estimer de façon collaborative la moyenne non-biaisée de l'ensemble des valeurs individuelles de tous les agents, sans révéler ni leurs attributs sensibles ni leur degré (le degré d'un sommet étant le nombre de ses voisins). Généralement, les travaux existants résolvent ce problème en supposant soit (i) que les agents révèlent leur degré à leurs voisins respectifs, soit (ii) que toutes les paires de voisins peuvent éffectuer des handshakes (pour s'assurer de la réponse de chacun). Puisque de telles hypothèses ne sont pas toujours réalisables, nous proposons une approche qui ne nécessite pas de handshakes et qui ajoute du bruit aux degrés. En particulier, nous utilisons un algorithme de bavardage qui calcule des moyennes biaisées quand le graphe est non-régulier (quand tous les sommets n'ont pas le même degré), puis nous appliquons une procédure combinant les moyennes biaisées pour en corriger le biais. Nous appliquons ensuite l'approche proposée pour estimer des modèles de régression linéaire. Nous prouvons que, asymptotiquement, l'erreur quadratique moyenne entre la moyenne des attributs cachés (par le bruit) calculée par notre approche et la véritable moyenne des attributs sensibles est O 1 n , où n est le nombre d'agents.

Dans le second cas, nous considérons un groupe d'agents, où les features (valeurs entrant dans l'estimation des modèles de régression linéaire) sont calculées par application de fonctions sur des attributs sensibles, et ces fonctions présentent une grande amplitude de gradient ou des singularités. Dans une telle situation, il existe un risque d'amplifier le bruit d'obfuscation si les données perturbées se trouvent dans un intervalle où ladite fonction a une grande amplitude de gradient. Nous proposons un mécanisme de bruitage spécifique qui cache les features en résolvant un problème d'optimisation de telle sorte que (i) seuls des intervalles pertinents pour les fonctions considérées soient sélectionnés, (ii) la variance du bruit soit minimisée et (iii) le biais du bruit soit minimisé. BiasCorrectingGossip (BCGo) for privacy-preserving regression . . .

List of Figures

Chapter 1 Introduction

In recent years, due to the growing importance of network applications and the growing concerns for privacy, there is an increasing interest in decentralized forms of machine learning [NTC17; Col+16; VBT17]. On the one hand, reluctance to share sensitive data reduces the risk of unwanted profiling which can expose to targeted advertisement or discrimination in job applications. On the other hand, sharing such data can be useful in improving statistical models used in healthcare [START_REF] Ogier | FLamby: Datasets and Benchmarks for Cross-Silo Federated Learning in Realistic Healthcare Settings[END_REF][START_REF] Lamer | Specifications for the Routine Implementation of Federated Learning in Hospitals Networks[END_REF] or software maintenance [START_REF] Erlingsson | RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response[END_REF]. Data obfuscation is a computationally light approach to share data while preserving privacy with or without centralization. Upon centralization, an authority is entrusted to preserve privacy of each record shared with it. Upon decentralization, software on a user's device preserves privacy while records are shared in a network of users. When software is respectful towards regulation enhancing privacy, such as the General Data Protection Regulation, decentralization allows for preserving privacy without trusting an authority [START_REF] Near | Differential Privacy for Databases[END_REF]. However, decentralization requires additional care, such as failure detection or tailored design of communication protocols.

We do not consider cryptographic approaches, such as secure multi-party computation [START_REF] Sotthiwat | Partially Encrypted Multi-Party Computation for Federated Learning[END_REF], mainly due to additional computational cost. Also, we aim for studying networks where information flow is characterized by absence of handshakes (requests that rely on replies). As in such case, interaction among users is characterized by a stronger self-management because the users are not obliged to wait for each other.

In this dissertation, we study the setting that involves a communication network of agents, where an agent can communicate to another agent only if there is a communication link between them (we refer to such agents as neighboring agents), where each agent is attributed a vector of individual values, and where each agent intends to collaboratively compute statistics over the individual values of all agents for fitting statistical models. Furthermore, we consider that every agent intends to keep its individual values private (i.e., individual values are sensitive attributes). We recall two common approaches for computing statistics over the individual values of all agents in a privacy-preserving way:

• In the centralized approach, the community of agents chooses a trust-worthy agent (a trusted central curator). Then, each agent shares its sensitive attributes with the central curator, the central curator computes statistics over the sensitive attributes of all agents, and the central curator privatizes the statistics. At this point, the central curator can share the privatized statistics with the agents.

• In the decentralized approach, each agent privatizes its sensitive attributes locally and shares the privatized attributes with its neighboring agents.

Then, the community of agents commits to a procedure where each agent iteratively performs computations over the received values and shares the results with the neighbors. As the number of iterations increases, such information dissemination can be tailored to lead to statistics of interest over the privatized attributes.

First, we discuss the centralized approach in more detail. We assume that a central curator is connected to every agent (otherwise, the community adds communication links so that the central curator is connected to every agent). This way, each agent can share its sensitive attributes with the central curator, the central curator computes and then privatizes (adds appropriate amount of noise to) the statistics of interest, and, finally, the central curator shares the privatized statistics with the community.

Next, we discuss the decentralized approach in more detail. Even though no central curator is selected, the community can compute statistics from locally privatized attributes using a distributed algorithm. A suitable choice of such distributed algorithm is an iterative algorithm known as a gossip algorithm. In the initialization of a gossip algorithm, each agent shares its vector of individual values with its neighbors. In the first step, each agent computes the average from the receivable values. In the second step, each agent updates its shared value by the computed average. Under conditions studied later in this dissertation, iteration over the two steps leads to convergence, and each agent obtains the statistics of interest over the privatized attributes.

The statistics computed by the centralized approach are more accurate (which leads to a higher utility) than the statistics computed by the decentralized approach because the amount of noise to guarantee differential privacy (a standard of data privacy) is, typically, higher in a statistic computed from locally privatized attributes as opposed to a privatized statistic computed from sensitive attributes. However, the centralized approach relies on a central curator for privatization, whereas the decentralized approach does not. Meanwhile, the decentralized approach is susceptible to issues of distributed communication, e.g., inactivity of agents or the bias due to non-regular connectivity (when the graph of agents is non-regular, i.e., the numbers of neighbors vary).

In this dissertation, we reuse elements from the two aforementioned approaches. As in the centralized approach, we have a central curator. However, the role of the central curator is other than privatizing sensitive attributes. For example, such role can be solving mathematical optimization problems or averaging. As in the decentralized approach, each agent privatizes its sensitive attributes locally.

We focus on statistical models which can be fitted using statistics that are averages (later, we show that this is the case for linear regression). This way, we are interested in distributed averaging of locally privatized attributes, which is an actively studied problem [START_REF] Dellenbach | Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries[END_REF][START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF]. Regarding real-world applications, distributed averaging with a minimal reliance on a central curator (which, typically, is an entity that provides or hosts an instance of software) is an element of selfmanaging distributed systems. In particular, a reduced reliance on a central curator reduces risks associated with robustness, infrastructure for data storage, and trust. For example, an approach relying on a central curator is susceptible to power cuts or information leakage. However, the design of a self-managing distributed system that functions well in practice requires consideration of numerous factors, such as inactive or malicious agents, convergence, asynchronicity, or the aforementioned bias due to non-regular connectivity.

We proceed by stating our principal question:

• Given that local differential privacy must be used, how could the agents maximize the utility they achieve? More precisely, how could the agents of a communication network maximize the accuracy of collaboratively computed averages of locally privatized attributes?

In this dissertation, we answer the latter question by the two following contributions.

In Section 3.3, we prove an asymptotic guarantee for the mean squared error between the average of sensitive attributes and the average of locally privatized attributes computed by a bias-correcting gossip algorithm, when the graph of agents is modeled by a random graph model parametrized by an arbitrary degree sequence, when the degrees (numbers of neighbors) of agents are sensitive, and when the agents interact without handshakes. We apply the proposed approach for fitting linear regression models while keeping the degrees private. We show on a synthetic graph dataset and real graph datasets that, when the features are polynomials of degrees, the regression model fitted by our approach can outperform the solution when locally privatized attributes are averaged by centralized averaging, i.e., the averaging function f (x) = 1 n i∈ [n] x i , where x ∈ R n . In Chapter 4, we provide a utility-maximizing mechanism for privatizing features that are computed by transforming sensitive attributes, when the transformations have high-magnitude gradients or singularities. In such setting, there is a risk of obtaining an outlier feature due to transforming a privatized attribute in an interval where the transformation has high-magnitude gradients. We mitigate the aforementioned risk by providing a tailored noise mechanism for privatizing features by solving a convex program in such a way that (i) only informative intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized. We show on synthetic datasets and a synthetically-extended real dataset that the tailored noise mechanism results in a higher utility compared to a classic privatization mechanism, when fitting a linear regression model where the feature function is either the logarithm, the reciprocal, or the tangent.

Outline. In Chapter 2, we discuss the background of the fields on which this dissertation relies. In Chapter 3, we study the bias in distributed averaging when the graph of agents is non-regular. In Chapter 4, we study the tailored noise mechanism. In Chapter 5, we summarize this dissertation and discuss future directions.

Chapter 2

Background

In this chapter, we discuss the background of the fields on which this dissertation relies (illustrated in Figure 2.5). In particular, we review definitions, provide notation, and sometimes provide descriptions and examples.

At the beginning of this chapter, we review some basic concepts of linear algebra and familiarize with the general notation followed throughout this dissertation. In particular, we review the spectral norm that is used in our example of distributed averaging on particular random graphs known as Erdős-Rényi graphs (discussed in Section 3.2). Then, in Section 2.1, we review probability theory. In Section 2.2, we review graph theory. In Section 2.3, we review distributed systems. Afterwards, in Section 2.4, we review machine learning. In Section 2.5, we review data privacy. In Section 2.6, we review mathematical optimization. Finally, in Section 2.7, we briefly summarize how the reviewed fields relate to the settings discussed in this dissertation.

For a review of linear algebra, we recommend and mostly follow the textbook by Horn and Johnson [START_REF] Horn | Matrix Analysis[END_REF]. In this dissertation, we limit ourselves to the space R of real numbers (as opposed to the space C of complex numbers).

We start by recalling definitions of a field and a vector space; we do so with the intention to review the basis for definitions of vectors and matrices which are fundamental in linear algebra.

A field (also known as a scalar field) is a set of scalars closed under addition and multiplication; we denote a field by F . An n-dimensional vector space S (also known as a vector space) over a field F is a set of n-tuples, where the set S meets the following conditions:

• S is closed under vector addition (which is associative and commutative).

That is, for each u, v ∈ S, we have u + v ∈ S.

• S includes an identity which is the vector of 0's; we denote the vector of 0's by 0. That is, 0 ∈ S.

• S includes the additive inverse of its each element. That is, for each u ∈ S, we have -u ∈ S, where u + (-u) = 0.

• S is closed under scalar multiplication. That is, for each c ∈ F and for each u ∈ S, we have cu ∈ U .

An element of a vector space over a field F is known as a vector. A finite collection of vectors u 1 , u 2 , . . . , u k is linearly dependent if and only if there are scalars c 1 , c 2 , . . . , c k , not all zero, such that

c 1 u 1 + c 2 u 2 + . . . + c k u k = 0,
where k ∈ N 1 , and N 1 = N \ {0}. Further, we remark that by F n we denote a set of n-tuples whose elements are in F . Similarly, by F m×n we denote a set of m × n arrays whose elements are in F . An element of F m×n is known as a matrix. Essentially, a vector is a collection of elements over one axis (e.g., a sequence), and a matrix is a collection elements over two axes (e.g., a table). This way, a vector can be also interpreted as a matrix whose second axis is of length 1.

We summarize the notation of matrices, vectors, and scalars, which we have chosen to follow throughout this dissertation. Let x ∈ R n be a vector and let Y ∈ R n×n be a matrix. When we refer to a particular element of x, we use an index in the subscript, e.g., x 2 denotes the 2-nd element of x (we remark that x 2 takes the italic font and x takes the roman bolded font). Similarly, y 1,2 denotes the element in the 1-st row and the 2-nd column of Y (we remark that y 1,2 takes the lower-case and Y takes the upper-case). This way, we usually denote scalars and vectors in lower-case and matrices in upper-case. When we refer to some particular row or column of a matrix, we use the colon symbol (i.e., ":"). For example, Y :,2 refers to the 2-nd column of Y (as an exception to the general notation conventions followed in this dissertation, we remark that the vector Y :,2 keeps the upper-case opposed to taking the lower-case).

In Table 2.1, we provide a summary of the general notation followed throughout the dissertation.

Table 2.1: General notation followed throughout the dissertation Notation Meaning

x Italic lower-case usually denotes a scalar or a map x Roman bolded lower-case denotes a vector X Roman bolded upper-case usually denotes a matrix X Italic upper-case usually denotes a random variable or a set X Italic bolded upper-case usually denotes a random matrix

N 1 N \ {0} [x] {i ≤ x : i ∈ N 1 } (x ∈ N 1 ) 1
Vector of 1's 0

Vector of 0's I k k × k identity matrix (1's in the main diagonal, 0's elsewhere)

We proceed by recalling definitions of a square matrix and a diagonal matrix.

A square matrix is a matrix with an equal number of columns and rows. A diagonal matrix is a square matrix where non-zero elements are only in its main diagonal, and the main diagonal of an n × n matrix A is the diagonal (a vector) that contains the elements a 1,1 , a 2,2 , . . . , a n,n . This way, the first element of the main diagonal is at the upper-left corner of A and the last element of the main diagonal is at the bottom-right corner of A.

We proceed by recalling the following basic operations that can be performed on matrices: the transpose, matrix inversion, and eigendecomposition.

Let A be an m × n matrix. The transpose is the operation that provides the n × m matrix A T whose (i, j)-th element is a j,i , for each i ∈ [n] and j ∈ [m]. We denote the transpose by the suffix of A T .

Let A be an n × n matrix. Matrix inversion is the operation that provides a matrix A -1 (if it exists) so that the following equality is met:

AA -1 = I n ,
where I n is the n × n identity matrix. We denote matrix inversion by the suffix of A -1 .

Before reviewing eigencomposition, we remark that an eigenvalue and an eigenvector of a matrix A are, respectively, a scalar λ and a non-zero vector u which result in the following equality:

Au = λu.
Eigendecomposition of an n × n matrix A with n linearly independent eigenvectors is the pair of a matrix U and a matrix Λ, where the columns of U contain the eigenvectors of A and Λ is a diagonal matrix that contains the eigenvalues of A in the order that is respective to the eigenvector alignment in the columns of U. Eigendecomposition of A can be expressed in factors as follows:

A = UΛU -1 .
For the previous definition, we consulted the textbook by Johnson et al. [START_REF] Johnson | Introduction to Linear Algebra[END_REF] Finally, we recall definitions of a vector norm, a matrix norm, an induced matrix norm, the spectral norm, and then discuss a useful result between the spectral norm and the largest singular value, where a singular value is the square root of an eigenvalue.

Let S denote a vector space over R. A norm ∥ • ∥ is a function ∥ • ∥ : S → R which, for each u, v ∈ S, meets the following conditions:

• ∥u∥ ≥ 0.

• ∥u∥ = 0 if and only if u = 0.

• ∥cu∥ = |c| ∥u∥, for each c ∈ R.

• ∥u + v∥ ≤ ∥u∥ + ∥v∥.
Essentially, a norm is a function that assigns a length to a vector. We remark that the fourth of the previously stated conditions is known as the triangle inequality.

Common examples of norms are the l 1 norm and the l 2 norm. Let u ∈ R n . The l 1 norm ∥ • ∥ 1 is defined as follows:

∥u∥ 1 = i∈[n] |u i |.
In other words, the l 1 norm of a vector is the sum of the absolute values of the elements of the vector. The l 2 norm ∥ • ∥ 2 (also known as the Euclidean norm) is defined as follows:

∥u∥ 2 = i∈[n] u 2 i .
In other words, the l 2 norm of a vector is the square root of the sum of the squares of the elements of the vector. Let S denote a set of n × n matrices over R. A matrix norm ∥ • ∥ is a function ∥ • ∥ : S → R, which, for each A, B ∈ S, meets the following conditions:

• ∥A∥ ≥ 0.

• ∥A∥ = 0 if and only if all elements of A are 0's.

• ∥cA∥ = |c| ∥A∥, for each c ∈ R.

• ∥A + B∥ ≤ ∥A∥ + ∥B∥. • ∥AB∥ ≤ ∥A∥ ∥B∥.
Essentially, a matrix norm is a function that assigns a size to a matrix.

Let x ∈ R n . Let Y ∈ R n×n . A matrix norm ∥ • ∥ induced by a norm ∥ • ∥ on an n-dimensional vector space over R (also known as an induced matrix norm) is defined as follows:

∥Y∥ = max x̸ =0 ∥Yx∥ ∥x∥ .
The spectral norm ∥ • ∥ 2 is a matrix norm induced by the l 2 norm ∥ • ∥ 2 on an n-dimensional vector space over R.

We recall the following result showing a connection between the spectral norm of Y and the largest singular value of Y:

∥Y∥ 2 = max x̸ =0 ∥Yx∥ 2 ∥x∥ 2 = σ 1 (Y), (2.1)
where σ 1 (Y) denotes the largest singular value of Y. We remark that the previous result is proved in Horn and Johnson [START_REF] Horn | Matrix Analysis[END_REF].

Probability theory

In this section, we review probability theory. In particular, we review some preliminaries of the following fields on which this dissertation relies: random graphs (discussed in Subsection 2.2.2), machine learning (discussed in Section 2.4), and data privacy (discussed in Section 2.5). Also, we review some techniques used in our example of distributed averaging on particular random graphs known as Erdős-Rényi graphs (discussed in Section 3.2) and in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4). At the beginning of this section, we review some basic concepts of probability theory, such as random variables and sampling. In Subsection 2.1.1, we review estimation of some basic types of statistics, such as the mean and the variance. In Subsection 2.1.2, we review common probability distributions. Finally, in Subsection 2.1.3, we review statistical significance.

For a review of probability theory, we recommend and mostly follow the textbook by Wasserman [START_REF] Wasserman | All of Statistics: A Concise Course in Statistical Inference[END_REF]. For a supplementary reference to definitions of probability theory, we recommend the dictionary by Everitt and Skrondal [START_REF] Everitt | The Cambridge Dictionary of Statistics[END_REF].

We start by recalling definitions of the following basic concepts of probability theory: a trial, a sample space, and an event.

A trial (also known as a statistical experiment) is a procedure that provides an outcome from a set of possible outcomes. We remark that outcomes of trials may be used to model various real-world phenomena. The domain of outcomes of a trial is referred to as a sample space; we denote it by Ω. An event is a subset of a sample space Ω.

We proceed by recalling definitions of disjoint sets, a partition, a power set, and a σ-algebra. For a review of definitions related to sets, we recommend the textbook by Halmos [START_REF] Halmos | Naive Set Theory[END_REF].

Disjoint sets are two distinct sets whose intersection is the empty set. In other words, disjoint sets have no elements in common. When we have a collection of sets, where any two sets in the collection are disjoint, then we can refer to such collection as a collection of pairwise disjoint sets.

Let k ≥ 2. A partition of a set A is a set of pairwise disjoint sets B 1 , B 2 , . . . , B k ⊂ A, so that B 1 ∪ B 2 ∪ . . . ∪ B k = A. Similarly as in Szemerédi [START_REF] Szemerédi | On sets of integers containing k elements in arithmetic progression[END_REF], we refer to the pairwise disjoint sets B 1 , B 2 , . . . , B k as partition classes.

The power set of a set A is the set of all subsets of A; we denote it by P(A). A σ-algebra on a set A is a non-empty set Σ ⊆ P(A) which meets the following conditions:

• The empty set ∅ ∈ Σ.

• If B 1 , B 2 , . . . , B k ∈ Σ, then B 1 ∪ B 2 , ∪ . . . ∪ B k ∈ Σ. • If B ∈ Σ, then the set difference A \ B ∈ Σ.
We proceed by recalling definitions of a probability measure and a probability, and then stating the addition law of probability.

Let S be a set of events, so that S is a σ-algebra on a sample space Ω. A probability measure (also known as a probability distribution) is a function p : S → [0, 1] that satisfies the following conditions:

• p(B) ≥ 0, for each B ∈ S.

• p(Ω) = 1.

• p(B 1 ∪ B 2 ) = p(B 1 ) + p(B 2 ), for each two events B 1 , B 2 ∈ S that are disjoint sets.

The value p(B) is the probability of an event B ∈ S. Essentially, the higher the probability of an event, the more likely it is that the event contains the outcome that occurs. For example, if p(B) = 0, then we know that no outcome in B can occur.

The addition law of probability is the theorem which states that, for two events B 1 and B 2 , we have

Pr(B 1 ∪ B 2 ) = Pr(B 1 ) + Pr(B 2 ) -Pr(B 1 ∩ B 2 ), (2.2)
where B 1 ∪ B 2 denotes that an outcome occurs either in the event B 1 or the event B 2 , and B 1 ∩ B 2 denotes that an outcome occurs in both events B 1 and B 2 . For the previous theorem, we consulted the textbook by DeGroot and Schervish [START_REF] Degroot | Probability and Statistics[END_REF].

We proceed by recalling definitions of a measurable space and a measurable function. For a review of definitions related to measure theory, we recommend the textbook by Shao [START_REF] Shao | Mathematical Statistics[END_REF].

A measurable space is a pair (X, Σ) of a set X and a σ-algebra on X. Let (X 1 , Σ 1 ) and (X 2 , Σ 2 ) be measurable spaces. A function f :

(X 1 , Σ 1 ) → (X 2 , Σ 2 ) is a measurable function if and only if f -1 (Σ 2 ) ⊂ Σ 1 . That is, for every set X ′ 2 ∈ Σ 2 , we have {x 1 ∈ X 1 : f (x 1 ) ∈ X ′ 2 } ∈ Σ 1 .
Having stated previous definitions, we are ready to recall a definition of a random variable. A random variable is a measurable function X : (Ω, S, p) → (R, B), where B is the smallest σ-algebra that contains all open subsets of R (B is known as a Borel σ-algebra), S is a set of events that is a σ-algebra on Ω, the triple (Ω, S, p) is known as a probability space, and the pairs (Ω, S) and (R, B) are measurable spaces.

We highlight that the probability measure p assigns a measure (a scalar greater or equal to 0 and lower or equal to 1) to every outcome in the sample space Ω. Also, we remark that when we use the expression "an outcome of a random variable", we refer to "an outcome of a trial that is modeled by a random variable". For conciseness, we sometimes shorthand the expression "X : (Ω, S, p) → (R, B)" by "X : Ω → R".

When speaking of random variables, we either consider discrete random variables or continuous (real-valued) random variables. We remark that we use a broader definition of a discrete random variable mainly because later in this dissertation we consider random graphs.

We recall a definition of a discrete random variable. A discrete random variable is a function X : Ω → R that takes on either a finite number of values (i.e., x 1 , x 2 , . . . , x n ∈ Ω, where n ∈ N 1 ) or a countably infinite number of values (i.e., x 1 , x 2 , . . . ∈ Ω) according to a function p X (x) : Ω → [0, 1] known as the probability mass function and defined by

p X (x) = Pr(X = x),
where Pr(X = x) denotes the probability that an outcome of X takes a value x, and where the probability mass function must satisfy the following conditions:

• p X (x) ≥ 0, for each x ∈ Ω. • x∈Ω p X (x) = 1.
We recall a definition of a continuous (real-valued) random variable. A continuous random variable is a function X : Ω → R that takes values in Ω according to a function p X (x) : R → R known as the probability density function and defined by

b a p X (x)dx = Pr(a ≤ X ≤ b),
where a and b are any scalars under the condition that a ≤ b, Pr(a ≤ X ≤ b) is the probability that an outcome of X takes a value that is in the interval [a, b], and where the probability density function must satisfy the following conditions:

• p X (x) ≥ 0, for each x ∈ R. • ∞ -∞ p X (x)dx = 1.
Essentially, probability mass functions and probability density functions can be interpreted as probability distributions. When a random variable X follows a probability distribution p, this is sometimes denoted as follows:

X ∼ p.
We remark that denoting the probability distribution by p (instead of p X ) might reduce ambiguity when we have several random variables that follow the same probability distribution.

In Table 2.2, we provide a summary of the introduced notation of basic concepts of probability theory. We review some more definitions that are more closely related to random variables: the cumulative distribution function, the quantile function, the support, and independent random variables.

The cumulative distribution function of a (real-valued) random variable X is the function ϕ X : R → [0, 1] defined by

ϕ X (x) = Pr(X ≤ x),
where Pr(X ≤ x) is the probability that an outcome of a random variable is less than or equal to a value x.

The quantile function of a (real-valued) random variable X is the function ϕ -1 X (q) : [0, 1] → R that is the inverse of the cumulative distribution ϕ X (x) of X, it is defined as follows:

ϕ -1 X (q) = inf{x : ϕ X (x) > q}. The support of a random variable is the subset of its sample space, where the subset contains the elements that are mapped by the probability mass/density function to probabilities greater than 0.

Independent random variables are two random variables where an outcome of one random variable does not influence the outcome of the other. For the previous definition, we consulted the textbook by Tijms [START_REF] Tijms | Understanding Probability: Chance Rules in Everyday Life[END_REF]. The independence between random variables X and Y are denoted by X⊥Y . When we have a collection {X i } i∈[n] of random variables, where each two random variables X, X ′ ∈ {X i } i∈ [n] are such that X⊥X ′ , then we refer to {X i } i∈[n] as a collection of pairwise independent random variables.

We proceed by recalling definitions of a joint probability distribution and a marginal probability distribution; we do so with the intention to show a link and a distinction between the two. A joint probability distribution is a probability distribution that provides probabilities for outcomes of several random variables. To consider a particular discrete case, the joint probability mass function of discrete random variables

X 1 , X 2 , . . . , X n : Ω → R is the function p X 1 ,X 2 ,...,Xn : Ω n → [0, 1], defined by p X 1 ,X 2 ,...,Xn (x 1 , x 2 , . . . , x n ) = Pr(X 1 = x 1 , X 2 = x 2 , . . . , X n = x n ).
A marginal probability distribution is a probability distribution that provides probabilities for outcomes of one or several random variables that define a joint probability distribution p X 1 ,X 2 ,...,Xn (x 1 , x 2 , . . . , x n ). For example, when we have a joint probability distribution p X,Y (x, y) of random variables X and Y , then one of its two marginal probability distributions is

p X (x) = y∈Ω p X,Y (x, y),
and the second marginal distribution is p Y (y).

We relate a conditional probability to a joint probability distribution. A conditional probability is a probability that is parametrized by a fixed outcome of another random variable. For random variables X and Y , the conditional probability of an outcome x of a random variable X given an outcome y of a random variable Y is defined as follows:

p X|Y (x | y) = p X,Y (x, y) p Y (y) , (2.3)
where p Y (y) > 0. We remark that p X|Y is called the conditional probability distribution of X given Y . We recall Bayes' theorem. Let k ≥ 2 and let events B 1 , B 2 , . . . , B k form a partition of a sample space Ω, where, for each i ∈ [k], we have Pr(B i ) > 0. Let an event A ⊆ Ω, where Pr(A) > 0. Bayes' theorem (also known as Bayes' rule) is stated as follows:

Pr(B i | A) = Pr(A | B i ) Pr(B i ) j∈[k] Pr(A | B j ) Pr(B j )
.

Since the law of total probability states that

j∈[k] Pr(A | B j ) Pr(B j ) = Pr(A),
the denominator in Bayes' theorem can be substituted with Pr(A). In such case, the expression of Bayes' theorem resembles the conditional probability defined in Equation 2.3. Finally, we recall definitions of a statistical population, sampling, a stochastic process, and a statistical model.

A statistical population (also known as a population) is a finite or infinite set of elements. Sampling is a procedure that selects a subset of elements from a statistical population. We remark that a subset obtained by sampling is referred to as a sample, and an element of a sample is referred to as an observation (also known as a realization or as a sample point). For example, uniformlyrandom sampling is sampling that leads to every element of a population being observed with the same probability. We remark that a statistical population can be modeled by a collection of independent and identically distributed random variables (by identically distributed, we mean that the random variables follow the same probability distribution). This way, a set of outcomes of independent and identically distributed random variables can be interpreted as a sample of a statistical population.

A stochastic process is a finite or infinite sequence (X t ) t∈T of random variables, where X t is a random variable at time t, and T is a time range. Typically, T = {0, 1, 2, . . .}.

A statistical model is a pair of a sample space and a set of probability distributions on the sample space. For the previous definition, we consulted McCullagh [START_REF] Mccullagh | What is a statistical model?[END_REF]. For statistical models, it is common to assume that observations are obtained from an underlying probability distribution. We remark that collecting such observations helps in identifying probability distributions that are good approximations of the underlying probability distribution.

Statistics and their estimation

In this subsection, we review some common statistics as well as estimation techniques. In particular, we review Hoeffding's inequality that is used in our example of distributed averaging on particular random graphs known as Erdős-Rényi graphs (discussed in Section 3.2). Also, we review U-statistics that are used in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

To start with, we highlight that by a statistic we refer to a numerical characteristic that is either an average (e.g., the average age of a demographic population) or a count (e.g., the number of members in a demographic population).

We proceed by recalling definitions of an estimate and an estimator. An estimate of a parameter θ is the following value:

θ = f (x 1 , x 2 , . . . , x n ),
where {x 1 , x 2 , . . . , x n } is a collection of observations of independent and identically distributed random variables X 1 , X 2 , . . . , X n whose probability distribution is parametrized by θ, and where f is a real-valued function. In other words, θ is an observation of the following random variable:

Θ = f (X 1 , X 2 , . . . , X n ),
where Θ is known as an estimator. We remark that the caret symbol (i.e., "ˆ") indicates that a term is an estimate, e.g., an estimate θ approximates a parameter θ. Also, we remark that a probability distribution parametrized by θ can be unknown yet observable. In such case, we sometimes refer to θ as the true value of a parameter of an unknown probability distribution. For the previous definitions, we consulted the textbook by DeGroot and Schervish [START_REF] Degroot | Probability and Statistics[END_REF].

We recall definitions of some common statistics that are related to random variables: the expected value, the variance, and the standard deviation.

The expected value E[•] (or the mean) of a (real-valued) discrete random variable X taking values x 1 , x 2 , . . . is defined as follows:

E[X] = i∈{1,2,...} x i p X (x i ),
assuming that the sum is well-defined, and where p X is the probability mass function of X.

Similarly, when X is a continuous random variable, the expected value is defined as follows:

E[X] = ∞ -∞ xp X (x)dx,
assuming that the integral is well-defined, and where p X is the probability density function of X. We remark that the mean E[X] of a continuous random variable is well-defined when ∞ -∞ |x|p X (x)dx < ∞. We denote the mean of a random variable by µ.

The variance of a (real-valued) discrete random variable X taking values x 1 , x 2 , . . . is defined as follows:

var(X) = i∈{1,2,...} (x i -µ x ) 2 p X (x i ),
assuming that the sum is well-defined, where p X is the probability mass function of X, and where µ x is the mean of X.

Similarly, when X is a continuous random variable, the variance is defined as follows:

var(X) = ∞ -∞ (x -µ x ) 2 p X (x)dx,
assuming that the integral is well-defined, and where p X is the probability density function of X. We denote the variance of a random variable by σ 2 . The standard deviation of a random variable is the squared root of its variance; we denote it by σ.

Having stated the definitions of the mean and the variance, we recall a useful tool in probability theory, which is a particular concentration inequality known as Hoeffding's inequality, and where a concentration inequality is a method for obtaining a bound on how far an observation of a random variable deviates from some fixed value, by also bounding the probability of such observation. Let t > 0. Let X 1 , X 2 , . . . , X n be independent random variables, each of which has the mean and the variance that are well-defined, and where the support of each random variable is the interval [a, b] with a ≤ b (i.e., random variables X 1 , X 2 , . . . , X n are bounded). Let S n = i∈[n] X i . Hoeffding's inequality [START_REF] Hoeffding | Probability Inequalities for Sums of Bounded Random Variables[END_REF] is defined as follows:

Pr(S n -E[S n ] ≥ t) ≤ exp - 2t 2 i∈[n] (b -a) 2 .
In other words, Hoeffding's inequality is a concentration inequality that bounds the difference between the sum S n and the expected value of S n . We highlight that Hoeffding's inequality can be rearranged to bound the difference between the average of random variables and the expected value of that average, that is

Pr 1 n S n -E 1 n S n ≥ t ≤ exp - 2n 2 t 2 i∈[n] (b -a) 2 .
(2.4)

We proceed by reviewing some common statistics that are computed from samples: the sample mean and the sample variance.

The sample mean is the average computed over the elements in a sample. Let a sample {x 1 , x 2 , . . . , x n } be a collection of observations of n independent and identically distributed (real-valued) random variables. The sample mean is defined as follows:

μx = 1 n i∈[n]
x i .

Similarly, the unbiased sample variance is defined as follows:

σ2 x = n n -1 1 n i∈[n] (x i -μx ) 2 = 1 n -1 i∈[n] (x i -μx ) 2 .
The denominator n -1 (as opposed to n) in the expression of the unbiased sample variance corrects the bias due to the use of the sample mean μx as opposed to the true mean µ x , where a bias (also known as an estimator bias) is defined as the difference between the expected value of an estimator and the true value of the parameter that is estimated by the estimator. The aforementioned bias correction due to the use of the sample mean μx as opposed to the true mean µ x is known as Bessel's correction. For the previous definitions, we consulted the textbook by Radziwill [START_REF] Radziwill | Statistics with R: (the Easier Way)[END_REF].

We remark that the sample mean μx and the unbiased sample variance σ2

x are examples of unbiased estimates, where an unbiased estimate is an estimate without the estimator bias. We remark the bar symbol (i.e., "¯") indicates that a term is an unbiased estimate.

We review a family of unbiased estimates known as U-statistics [START_REF] Hoeffding | A Class of Statistics with Asymptotically Normal Distribution[END_REF] which are defined below.

Definition 1. Let r ∈ N 1 . Let n ≥ r. Let {x 1 , x 2 , . . . , x n } be a sample of observations of n independent and identically distributed random variables. Let ϕ : R r → R be a symmetric function. A U-statistic with kernel ϕ of degree r is defined as follows:

ūx = n r -1 i 1 <...<ir ϕ(x i 1 , x i 2 , . . . , x ir ),
where the sum is over all r-combinations of the elements in the sample (x i 1 , x i 2 , . . . , x ir are r distinct elements in the sample).

We remark that the sample mean and the sample variance are common examples of U-statistics. Also, we remark that the letter "U" in the term "U-statistic" abbreviates "unbiased". For a more detailed description of U-statistics, we recommend the lecture notes by Ferguson [START_REF] Ferguson | U-statistics[END_REF].

Common probability distributions

In this subsection, we review some common probability distributions. In particular, we review the Bernoulli distribution, the Binomial distribution, and the Poisson distribution as preliminaries for random graphs (discussed in Subsection 2.2.2). Then, we review the uniform distribution, mainly, as a preliminary for graph generation (discussed in Subsection 2.2.3). We review the Laplace distribution and the Gaussian distributions as preliminaries for data privacy (discussed in Section 2.5). Finally, we review Student's t-distribution as a preliminary for defining a particular confidence interval (discussed in Subsection 2.1.3). For the definitions in this subsection, we consult the dictionary by Everitt and Skrondal [START_REF] Everitt | The Cambridge Dictionary of Statistics[END_REF].

The Bernoulli distribution is a probability distribution of a discrete random variable X with outcomes either 1 or 0, and whose probability mass function is defined as follows:

Pr(X = 1 | p) = p, Pr(X = 0 | p) = 1 -p,
where p is the probability of a Bernoulli trial which is commonly illustrated as a coin toss where "heads" appear with probability p and "tails" appear with probability 1 -p. In our case, we interpret "heads" as the value 1.

The Binomial distribution is a probability distribution of a discrete random variable X whose probability mass function is defined as follows:

p X (k | n, p) = n k p k (1 -p) n-k ,
where p is the probability of a Bernoulli trial resulting in the value 1, n is the number of independent Bernoulli trials, and k is the number of Bernoulli trials that result in the value 1. We interpret the Binomial distribution as a probability distribution modeling the number k of occurrences of "heads" (outcomes of the value 1) in a sequence of n independent Bernoulli trials. The Poisson distribution is a probability distribution of a discrete random variable X whose probability mass function is defined as follows:

p X (k | λ) = λ k k! e -λ ,
where λ > 0 is a parameter known as the rate and k ∈ N is a parameter known as the count. We interpret the Poisson distribution as a probability distribution modeling occurrence of k events in an interval of time, given that the events may occur at a fixed rate λ, independently of previous occurrences. The uniform distribution is a probability distribution of a continuous random variable X whose probability density function is defined as follows:

p X (x | a, b) = 1 b -a ,
where a < b. The uniform distribution is characterized by all its outcomes having the same probability. The support of a random variable that follows the uniform distribution is the interval [a, b]. We denote the uniform distribution by uni(a, b).

The Laplace distribution is a probability distribution of a continuous random variable X whose probability density function is defined as follows:

p X (x | µ, b) = 1 2b e -|x-µ| b ,
where µ is a parameter known as the mean and b > 0. We denote the Laplace distribution by lap(µ, b).

The Gaussian distribution (also known as the Normal distribution) is a probability distribution of a continuous random variable X whose probability density function is defined as follows:

p X (x | µ, σ 2 ) = 1 σ √ 2π e -(x-µ) 2 2σ 2 ,
where µ is a parameter known as the mean and σ 2 > 0 is a parameter known as the variance. We denote the Gaussian distribution by N (µ, σ 2 ). Student's t-distribution is a probability distribution of a continuous random variable X whose probability density function is defined as follows:

p X (x | ν) = Γ ν+1 2 √ νπΓ ν 2 1 + x 2 ν -ν+1 2 ,
where ν ∈ N 1 is a parameter known as the degrees of freedom and Γ(ν) = (ν -1)! is the gamma function. We remind that Student's t-distribution can be used to define a particular confidence interval for evaluating statistical significance (we review statistical significance in Subsection 2.1.3). In Figure 2.1, we illustrate two probability density functions with the intention to indicate that the flatness of probability density functions can give a comparative indication of the variance of the corresponding probability distributions. In particular, a flatter probability density function indicates a higher variance compared to a steeper probability density function.

Figure 2.1: Illustration of two probability density functions (expressed as a dashed curve and a filled curve). The variance corresponding to the dashed curve is higher, since the filled curve has a region of higher probabilities.

Statistical significance

In this subsection, we elaborate on statistical significance. In particular, we review a confidence interval for a population mean, as such confidence interval is used in the experiments of our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4). For the definitions in this subsection, we consult the textbook by Weiss [START_REF] Weiss | Introductory Statistics[END_REF].

We start by recalling definitions of the null hypothesis, the alternative hypothesis, statistical significance, p-value, and the significance level. The intention of this is to discuss an interpretation of the significance level.

The null hypothesis is defined as the statement that two statistical models are the same. In relation to that, the alternative hypothesis is defined as the statement that the two statistical model differ significantly. One accepts the alternative hypothesis by gathering evidence that (under statistical significance) allows for rejecting the corresponding null hypothesis.

Statistical significance is a measure of unlikeness of an event occurring under the assumption of the null hypothesis. The p-value is the probability of the event occurring under the assumption that the null hypothesis is true, it is sometimes denoted by p. The significance level is the probability of rejecting the null hypothesis that was assumed to be true; we denote it by α. It is claimed that the event is statistically significant if p ≤ α. When speaking of statistical significance in the context of computer science research problems, it is common to fix the significance level to α = 0.05. This way, in this dissertation, we fix the significance level to α = 0.05.

We proceed by recalling a definition of a confidence interval for the population mean.

A (1 -α)-confidence interval (also known as a confidence interval) for the population mean is an interval estimate which contains the mean of a statistical population with the confidence level 1 -α.

We proceed by recalling a definition of the confidence interval based on Student's t-distribution. We remark that, for this, we follow a particular procedure known as the one-mean t-interval procedure.

The confidence interval that is based on Student's t-distribution is the following interval:

[μ x -l, μx + l] ,
(2.5)

where μx is the sample mean of a sample {x 1 , x 2 , . . . , x n } with n observations from a given statistical population,

l = ϕ -1 1 - α ci 2 | ν σx √ n
is the half-length of the confidence interval, σx is the square root of the unbiased sample variance of the sample, ν = n -1 are the degrees of freedom, α ci = 0.05 is the significance level, and ϕ -1 is the quantile function (the inverse of the cumulative distribution function ϕ) of Student's t-distribution. We remark that the inversion of ϕ can result in a complex formula or the inverse might not have a closed-form expression. In such cases, ϕ -1 can be approximated using Taylor series, similarly as in Giner and Smyth [START_REF] Giner | statmod: Probability Calculations for the Inverse Gaussian Distribution[END_REF]. Also, we remark that the middle point of the confidence interval in Equation 2.5 is the sample mean μx .

Graph theory

In this section, we review graph theory. In particular, we review some preliminaries related to execution of distributed algorithms on graphs (discussed in Subsection 2.3.2). Also, we review some preliminaries of random graphs models that are discussed in our example and contribution on the bias in distributed averaging when the graph of agents is non-regular (discussed, respectively, in Section 3.2 and Section 3.3). At the beginning of this section, we review some basic concepts of graph theory. In Subsection 2.2.1, we precise to what we refer to when speaking of structural properties related to the edges of a graph. In Subsection 2.2.2, we review some common random graph models. In Subsection 2.2.3, we review some basics of graph generation.

For a review of graph theory, we recommend and mostly follow the textbook by Diestel [START_REF] Diestel | Graph Theory[END_REF]. For a supplementary reference to definitions of graph theory, we recommend the textbook by van Steen [START_REF] Van Steen | Graph Theory and Complex Networks: An Introduction[END_REF].

We start by recalling definitions of the following basic concepts of graph theory: a graph, the order of a graph, the size of a graph, and a subgraph.

A graph is a pair G = (V, E) of a set V of vertices and a set E of edges, where an element v that belongs to V is known as a vertex and an edge is a 2-element subset of V . Given vertices v, u ∈ V , we denote an edge between them either by {v, u} or vu. We remark that graphs can be visualized as fixed points (vertices) that are joined by lines (edges).

The order of a graph G = (V, E) is the number |V | of vertices, and the size of the graph is the number |E| of edges. The empty graph is the graph whose set of vertices and whose set of edges are empty sets.

A subgraph G ′ = (V ′ , E ′ ) of a graph G = (V, E) is a graph whose vertices and edges are, respectively, a subset of V and a subset of E. In other words, V ′ ⊆ V and E ′ ⊆ E.

We proceed by recalling definitions of the following basic concepts that are related to edges: adjacent vertices, the degree of a vertex, the degree sequence, the degree distribution, an adjacency matrix, a walk, a path, a cycle, and the diameter of a graph.

Adjacent vertices (also known as neighboring vertices) are two vertices of a graph that have an edge in common. The neighborhood of a vertex v is the set of all adjacent vertices of v; we denote the neighborhood of a vertex v by N (v).

The degree of a vertex is the number of edges incident with that vertex; we denote the degree of a vertex v by d v . In other words, the degree of a vertex is the cardinality of its neighborhood. The degree sequence of a graph is a sequence whose elements are the degrees of all vertices on that graph; we denote a degree sequence by d. The degree distribution of a graph is the histogram (expressed in relative frequencies) of the degree sequence of the graph.

The adjacency matrix of a graph G = (V, E) is the square |V | × |V | matrix A whose (i, j)-th element a i,j is defined as follows:

a i,j = 1 when v i v j ∈ E, 0 otherwise.
This way, a i,j indicates the presence (by 1) or the absence (by 0) of the edge between vertices v i , v j ∈ V . A walk (of length k) in a graph G is a sequence (v 0 , e 1 , v 1 , e 2 , . . . , v k-1 , e k , v k ) that alternates between a vertex and an edge in such a way that, for each i ∈ [k], we have that the edge e i = v i-1 v i . A closed walk is a walk where v 0 = v k . A trail is a walk in which all edges are distinct. A path is a trail in which all vertices are distinct. A cycle (of length k ≥ 3) is a trail that is a closed walk and in which all vertices except v 0 and v k are distinct. An acyclic graph (also known as a forest) is a graph without cycles. The diameter of a graph is the length of the shortest path between two vertices in the graph, where the size of such shortest path is higher or equal to the shortest path between any two vertices of the graph (in case a path between some two vertices does not exist, then the diameter is ∞).

We recall a definition of the edge density of the pair of two (non-empty) disjoint subsets of vertices on a graph G = (V, E).

Let E(V ′ ) denote the set of edges, where each edge in the set is incident with at least one vertex in a subset V ′ ⊆ V . Let C, C ′ ⊆ V be (non-empty) disjoint subsets. We define the edge density of the pair (C, C ′ ) as follows:

den(C, C ′ ) = |E(C ∩ C ′ )| |C| |C ′ | . (2.6)
In Table 2.3, we provide a summary of the introduced notation of basic concepts of graph theory.

G Graph V Set of vertices of G E Set of edges of G v Vertex in V e Edge in E n (Commonly denotes) the order of G deg(v), d v Degree of v d Degree sequence (d 1 , d 2 , . . . , d n ) N (v) Neighborhood of v
We proceed by recalling definitions of a connected graph, an (un)directed graph, a labeled graph, a weighted graph, a regular graph, a complete graph, a tree, a spanning subgraph, and a spanning tree.

A connected graph is a (non-empty) graph whose any two vertices can be linked by a path in the graph. A triangle graph (also known as a triangle) is a connected graph with 3 vertices.

A directed graph is a pair G = (V, E) of disjoint sets of vertices and edges together with two maps f beg : E → V and f end : E → V , where, for each edge e ∈ E, the maps assign, respectively, an initial vertex f beg (e) ∈ e and a terminal vertex f end (e) ∈ e. When f beg (e) = f end (e), the edge e is known as a loop (also known as a self-loop). We remark that an undirected graph refers to a graph as defined at the beginning of this section.

Having the maps f beg and f end , we can interpret a directed graph as a graph whose edges are ordered pairs of vertices, and the direction of an edge goes from the initial vertex to the terminal vertex. The edges of a directed graph can be visualized by curves with an arrow at one (or both) end-points, as opposed to an undirected graph, where curves are without added symbols at the end-points. This way, the arrow of a curve (an edge) of a directed graph indicates the direction of that edge (though we might also have an arrow at each end of the curve). We remark that the direction of an edge is important when defining a walk on a graph. When we have an edge between vertices v and u, which corresponds to an unordered pair (v, u), then a walk on the graph can move from v to u but not from u to v.

A labeled graph is a graph where either every vertex, edge, or both are associated with a label, where a label is an element of a finite set known as an alphabet. A weighted graph is a labeled graph whose labels (weights) are real-valued and assigned to edges.

A k-regular graph (also known as a regular graph) is a graph where all the vertices have the same degree k. A complete graph is a graph where all the vertices are pairwise adjacent. In other words, a complete graph is a graph where all possible edges are present. We remark that a complete graph on n vertices is an n-regular graph.

A tree is an acyclic graph that is connected. A spanning subgraph of a graph G = (V, E) is a subgraph G ′ = (V, E ′ ) of G (i.e., G and G ′ have the same set V of vertices). A spanning tree of a graph G = (V, E) is a spanning subgraph G ′ = (V, E ′ ) of G, where G ′ a tree.

In Figure 2.2, we illustrate tree basic yet distinct graphs.

Figure 2.2: Illustration of three distinct graphs. The graph on the left is a graph that is a tree. The graph in the center is a graph with one additional edge (the additional edge makes the graph no longer a tree). The graph on the right is a directed graph (the arrows indicate the direction of edges).

Structural properties of graphs

In this subsection, we review some graph theory concepts that are related to structural properties of graphs, where by structural properties we mostly refer to the edge density or to regularities of the degree distribution. In particular, we review power-law degree sequences that are used in our contribution on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3).

For the definitions in this subsection, we consult the textbook by van der Hofstad [START_REF] Van Der Hofstad | Random Graphs and Complex Networks[END_REF]. We start by recalling definitions of the following graph theory concepts that are related to community structure: the connected component of a vertex, the largest connected component, and a giant component.

The

connected component of a vertex v ∈ V of a graph G = (V, E) is a set G(v) ⊆ V of vertices, where G(v) includes a vertex u ∈ V if there exists a path between v and u in G. The largest connected component G max of a graph G is any connected component of a vertex v ∈ V for which the cardinality of the connected component G(v) is maximal, i.e., G max = max v∈V |G(v)|. A giant component of G is the largest connected component G max of G such that lim k→∞ inf |G max | k > 0.
We proceed by discussing community structure. As indicated by Leskovec et al. [START_REF] Leskovec | Statistical properties of community structure in large social and information networks[END_REF], the definition of a community structure tends to vary from context to context. This is primarily because it is difficult to define a community in a network, where a network is a graph which has a stronger relation to real-world applications, and where the vertices of such graph are referred to as nodes or agents, and the edges are referred to as links. However, as suggested by the aforementioned authors, community detection is an actively studied area.

In this dissertation, we relate the community structure of a network to its structural properties, where by structural properties we either consider the edge density of two pairwise disjoint subjects of vertices, a clustering coefficient (whose definition tends to vary also), or regularities of the degree distribution. For example, when aiming for identifying or establishing a community structure in a network, the set of vertices of a graph could be partitioned in such a way that every partition class would contain the vertices of the same degree.

We recall the following definition of the clustering coefficient c G of a connected, undirected graph G = (V, E):

c G = 1 |V | v∈V 2|M (v)| |N (v)|(|N (v)| -1)
,

where, for each v ∈ V , the cardinality of the neighborhood of v is |N (v)| ≥ 2, and the set M (v) ⊆ E includes all edges whose elements are in the neighborhood N (v).

As indicated by Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], the value of the clustering coefficient c G indicates the cliquishness of a typical neighborhood in the graph G, where a clique of a graph G is a complete subgraph G ′ of at least three vertices such that G ′ is not contained in a larger complete subgraph of G.

We proceed by discussing a small-world network and a scale-free network.

A small-world network is a network whose largest connected component contains a significant proportion of the vertices. The name of a small-world network is related to the small-world experiment [START_REF] Milgram | The Small-World Problem[END_REF] which was a pioneering experiment on community structure in large real-world networks where nodes are persons, and the presence of a link between nodes indicate that the corresponding persons know each other. The experiment showed that the average shortest path in a network over a set of residents in the United States was unexpectedly short as the length of such path was estimated to be approximately 6. Furthermore, we highlight that, as indicated by Watts and Strogatz [START_REF] Watts | Collective dynamics of 'small-world' networks[END_REF], the average shortest path in a small-world network is, typically, the logarithm of the number of nodes.

A scale-free network is a network whose degree distribution follows a powerlaw distribution, i.e., the relative frequency of a degree d in the degree sequence is proportional to d raised to a negative power. In other words, a power-law distribution is a probability distribution where the probability of observing a scalar value x is proportional to x raised to a negative power, i.e., p(x | a, γ) ∝ ax -γ , where p denotes a probability density function, a > 0 and γ > 0. We recommend the article by Barabási and Albert [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF] for a more extensive discussion on scale-free networks and power-law distributions.

Referring to the article by Boccaletti et al. [START_REF] Boccaletti | Complex networks: Structure and dynamics[END_REF], we recall and discuss a complex network and a chaotic network.

A complex network is a network that is large, non-regular, and dynamically evolves in time. Typically, a complex network models a real-world network that is large enough so that its properties are difficult to assess by taking its individual nodes. This way, the properties of a complex network are sometimes identified probabilistically using random graph models (discussed in Subsection 2.2.2). We remark that complex networks tend to have the characteristics of the aforementioned small-world network and the scale-free network.

The dynamic evolution mentioned in the definition of a complex network has an equilibrium state, where an equilibrium state is a state towards which the complex network evolves and then stops changing once it is reached. Otherwise, if an evolving network has no equilibrium state, we refer to it as a chaotic network. An example of a chaotic network is a sequence of graphs that repeats in cycles.

Random graph models

In this subsection, we review some common random graph models. In particular, we review the Erdős-Rényi model and the configuration model that are used, respectively, in our example and contribution on distributed averaging on random graphs (discussed, respectively, in Section 3.2 and Section 3.3).

We start by recalling definitions of a random graph model and a random graph.

A random graph model is a probability distribution over a family of random graphs, where a random graph is defined as a graph with fixed vertices and the presence of edges being modeled as a random variable.

A positive aspect of random graph models is that they allow for analysis of the properties of larger graphs (e.g., complex networks), primarily due to the applicability of techniques encountered in probability theory (as opposed to relying on the use of techniques encountered in combinatorics, which is another common practice in graph theory). For a review of random graph theory, we recommend and mostly follow the textbook by van der Hofstad [START_REF] Van Der Hofstad | Random Graphs and Complex Networks[END_REF]. We remark that the textbook focuses on applications of random graph models for larger real-world networks.

We proceed by recalling definitions of the following random graph models: the Erdős-Rényi model, the stochastic block model, and the configuration model.

The Erdős-Rényi (ER) model [START_REF] Erdős | On Random Graphs I[END_REF] is a random graph model that is defined below.

Definition 2. The ER model is a probability distribution over graphs, which is parametrized by the number n of vertices and the probability p of the edge assignment between any of its two vertices.

We denote the probability mass function of the ER model by p G (G | n, p).

A graph that is an observation of an ER random graph has an n × n adjacency matrix with 0's in its main diagonal and with outcomes of independent Bernoulli trials of probability p in the remaining elements of the adjacency matrix. In an ER graph, the degree d v of a vertex v follows the Binomial distribution, i.e., for each d ∈ {0, . . . , n -1}, we have

Pr(d v = d) = n -1 d p d (1 -p) (n-1)-d . (2.7)
For larger ER graphs, the probability of a vertex v taking a degree d ∈ {0, . . . , n-1} can be modeled by a Poisson distribution as follows:

lim n→∞ Pr(d v = d) = (np) d d! e -np .
We remark that the ER model was introduced at the end of the 50's by Erdős and Rényi [START_REF] Erdős | On Random Graphs I[END_REF]. Initially, the ER model was used to probabilistically prove the existence of a graph that meets certain properties, where such application of a random graph model is known as the probabilistic method [START_REF] Noga Alon | Efficient Testing of Large Graphs[END_REF]. In Figure 2.3, we illustrate two possible observations of an ER random graph, where the probabilities of the two observations differ. 8 . This suggests that an observation of a graph where all vertices have degree 1 is more likely.

The ER model has a phase transition in the presence of a giant component. We elaborate on this based on the analysis by Bollobás [START_REF] Bollobás | The evolution of random graphs[END_REF]. Let ϵ ≥ 0. If np ≥ (1 + ϵ), then, with high probability, an ER random graph has a giant component of order at least n 2/3 , and the order of any other connected component is

O(log n) (big O notation O is discussed in Subsection 2.3.1). Otherwise, if np < (1 + ϵ),
then, with high probability, there is no such giant component though the order of any connected component remains O(log n).

The stochastic block model [START_REF] Holland | Stochastic blockmodels: First steps[END_REF] is a random graph model that is defined below.

Definition 3. The stochastic block model is a probability distribution over graphs, which is parametrized by the number n of vertices, the number 2 ≤ k ≤ n of communities (blocks), the expected fractions n ∈ [0, 1] k of vertices in a community, and the probabilities P ∈ [0, 1] k×k for edge assignments between every two communities.

We denote the probability mass function of the stochastic block model by p G (G | n, k, n, P). For the previous definition, we consulted the textbook by van der Hofstad [START_REF] Van Der Hofstad | Random Graphs and Complex Networks[END_REF].

The stochastic block model generalizes the ER model in such way that, instead of having a probability for edge assignments between any two vertices, we have probabilities for edge assignments between any two communities of vertices.

The configuration model [START_REF] Mark | The Structure and Function of Complex Networks[END_REF] is a random graph model that is defined as follows:

Definition 4. The configuration model is a probability distribution over graphs, which is parametrized by a degree sequence d, so that, for each i ∈ [n -1] and j ∈ {i + 1, . . . , n}, we have

Pr {v i , v j } ∈ E = d i d j i ′ ∈[n] d i ′ -1 .
We denote the probability mass function of the configuration model by p G (G | d). For the previous definition, we consulted the textbook by Newman [START_REF] Mark | Networks: An Introduction[END_REF].

Basics of graph generation

In this subsection, we review some basics of graph generation. In particular, we review a procedure for generating graphs with power-law degree sequences, where the procedure is used in our contribution on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3).

Firstly, we review a general method for generation of mathematical objects known as inverse transform sampling. Then, we review some methods that are commonly encountered in graph generation.

Regarding graph generation, we mostly consider the case where the vertices of a graph are fixed and the presence of edges is determined by a random procedure, thus a generated graph can be interpreted as an observation of a random graph. We highlight that graph generation can have additional constraints, e.g., a generated graph must be connected. We remark that the additional constraints can sometimes be met fully and sometimes only partially but at the best effort.

In some contexts, other mathematical objects have to be generated first before generating a graph. For example, when generating a graph from the configuration model, we might need to generate a degree sequence first because the configuration model is parametrized by a degree sequence.

We proceed by discussing inverse transform sampling. For a review of inverse transform sampling, we recommend the textbook by Devroye [START_REF] Devroye | Non-Uniform Random Variate Generation[END_REF].

Inverse transform sampling (also known as the inversion method) is a universal strategy for generating mathematical objects (e.g., graphs or scalars) from a probability distribution, where such strategy requires a value u that is independently observed from the uniform distribution, and which also requires the cumulative distribution function ϕ (for which we can compute the inverse) of the probability distribution. In particular, the generation of a value x from the probability distribution of interest by inverse transform sampling is the following evaluation:

x = ϕ -1 (u),
where, for each generated value, we use an independent value u.

For example, if one aims for generating a power-law degree sequence d, a common choice for this is the Pareto distribution which is a probability distribution with the following probability density function:

p(x | α, γ) = γα γ x -(γ+1) ,
where α > 0 is known as a scale parameter and γ > 0 is known as a shape parameter. For the definition of the Pareto distribution, we consulted the dictionary by Everitt and Skrondal [START_REF] Everitt | The Cambridge Dictionary of Statistics[END_REF]. For a more extensive description of the Pareto distribution, we recommend the article by Newman [START_REF] Mark | Power laws, Pareto distributions and Zipf's law[END_REF].

For generating a degree sequence d of length n, we repeat inverse transform sampling n times, thus for each i ∈ [n], we compute the following independent value:

d ′ i = ϕ -1 par (u i ), where ϕ -1 par (u i ) = α u 1/(γ-1) i
is the inverse of the cumulative distribution function of the Pareto distribution and u i is the i-th observation of the uniform distribution. Since the degree is a natural number and not a real number, we would also perform rounding: for each i ∈ [n], we have

d i = ⌈d ′ i ⌉.
This way, by collecting every degree d i , we arrive to the intended generation of a power-law degree sequence d. We remark that the generation of a graph that follows the configuration model is discussed in Chung and Lu [START_REF] Chung | Connected components in random graphs with given expected degree sequences[END_REF].

We proceed by reviewing preferential attachment process which is a generation procedure carried iteratively along a number of parties (e.g., the parties could be the vertices of a graph), where the parties that have more resources (e.g., a higher degree of a vertex can be interpreted as a more numerous resource) are more likely to have the next resource allocated to them. Graphs that are generated by a preferential attachment process tend to have power-law degree sequences. We remark that preferential attachment processes are discussed more extensively in Barabási and Albert [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF].

Finally, we review the Chinese restaurant process [START_REF] Zhou | Negative Binomial Process Count and Mixture Modeling[END_REF] which is a particular preferential attachment process where every party can hold a limited number of resources. The Chinese restaurant process is commonly illustrated by an analogy where in a restaurant each table has a limited number of seats and a new customer can choose any table with an open seat, with a stronger preference for the tables with more occupied seats. To relate the analogy to graph generation, new edges are more likely to be assigned to vertices of higher degree. We remark that the Chinese restaurant process can be applied for generating graphs with an unfixed number of vertices. That is, in such case we allow for an event (with a certain probability) of the appearance of a new vertex as opposed to only allowing for events of appearances of edges. To relate to the analogy, the appearance of a new vertex corresponds to the opening of a new table.

Distributed systems

In this section, we review distributed systems. In particular, we review some preliminaries (e.g., randomized algorithms) for differential privacy (discussed in Subsection 2.5.1). Also, we review some preliminaries (e.g., overlay networks and gossip algorithms) for distributed averaging, which are discussed in our examples and contribution on the bias in distributed averaging when the graph of agents is non-regular (discussed in Chapter 3). Furthermore, we elaborate on a central curator which is present in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

At the beginning of this section, we review some basic concepts related to distributed systems. In Subsection 2.3.1, we review some basic concepts related to algorithms. In Subsection 2.3.2, we discuss execution of distributed algorithms on graphs.

For a review of distributed systems, we recommend and mostly follow the textbook by van Steen and Tanenbaum [START_REF] Van Steen | Distributed Systems[END_REF].

We start reviewing the following basic concepts of distributed systems: a distributed system, a communication network, a communication protocol, and a central curator.

According to van Steen and Tanenbaum [START_REF] Van Steen | Distributed Systems[END_REF], definitions of a distributed system tend to vary from context to context. In this dissertation, we interpret a distributed system as a collection of autonomous computing elements that appears to its users as a single coherent system. We remark that the aforementioned definition does not take into account Byzantine failures which is a particular failure of distributed systems, where the cause of a failure of a single element of a distributed system can not be identified by the remaining elements of the distributed system.

More precisely, we interpret a distributed system as a communication network with a number of interconnected agents (e.g., machines, processors, processes) that store, process, and dispatch information according to a communication protocol, where a communication network refers to a network of agents which exchange messages, and where a communication protocol refers to a list of rules that are intended to be followed by the agents. In real-world distributed systems, the agents can be geographically distant, so that the communication itself is established by a far-reaching channel such as the internet.

A distributed system might have a central curator (also known as a central coordinator or simply a coordinator) which is an agent that has an assigned role for granting permissions to resources requested by other agents, where the permissions include the access to storing, processing, and forwarding of resources. Typically, a central curator is linked to every other agent of the communication network. We remark that Korach et al. [START_REF] Korach | A Modular Technique for the Design of Efficient Distributed Leader Finding Algorithms[END_REF] provides an algorithm for choosing a central curator in a communication network (such procedure is known as the coordinator election problem or leader election).

In Figure 2.4, we illustrate an example of the graph of a distributed system without a central curator and an example of the graph of a distributed system which strongly relies on a central curator.

Figure 2.4: Illustration of a distributed system without a central curator (left) and a distributed system with a central curator (right). We remark that the central curator is the node to which every other node is connected. In the distributed system on the left, the message of a sender can traverse several intermediate agents until the addressee receives the message. In the distributed system on the right, the message traverses only the central curator (the longest path that a message can travel is of length 2).

We proceed by discussing an overlay network. An overlay network of a communication network is a communication network that is built "on top" or "in parallel" to the formerly mentioned communication network. We remark that the graph of an overlay network is usually connected. Also, we remark that overlay networks are useful for addressing robustness issues. For example, when a communication network is susceptible to inactive agents, an overlay network could be built in such a way that each agent would have more or at least several neighbors. This way, if one neighbor becomes inactive, the information can still flow along the remaining active neighbors. For a more extensive discussion on overlay networks, we recommend the article by Sitaraman et al. [START_REF] Sitaraman | Overlay networks: An akamai perspective[END_REF] We proceed by discussing some particular modes of information flow in distributed systems. This mostly concerns approaches of how and when the agents exchange, share, or access messages.

Firstly, we highlight that we focus on distributed systems where agents collaboratively solve common tasks, i.e., the agents share resources with the aim of reaching common objectives. For example, contribution and revision of Wikipedia articles can be interpreted as an example of a distributed system characterized by collaboration. In this dissertation, we in particular focus on the task where each agent intends to obtain the average of values distributed over the agents of a communication network.

Secondly, we highlight that we also focus on distributed systems with the following characteristics of self-management: minimized reliance on a central curator, handshake-free interaction, asynchronicity. This way, we proceed by discussing the following concepts related to information flow in a communication network: a handshake, synchronicity, and asynchronicity.

When speaking of handshakes, we refer to tuples of two messages, i.e., a request (of a task) together with a reply, where the request is sent from an agent i to an agent j, and the reply (sent from the agent j to the agent i) confirms that the task was carried successfully, which is similar to handshakes discussed in Denning and Sacco [START_REF] Denning | Timestamps in key distribution protocols[END_REF]. For example, handshakes can be used to improve certainty that a request was received, since the reply to the request can be a message indicating that the request was received. However, we remark that the two generals' problem [AEH75] is a common example of distributed systems, which illustrates that a communication protocol which relies on handshakes is insufficient for having complete certainty that a message from one agent was reached by another. Synchronicity is a mode of communication where messages among participants (e.g, agents of a distributed system) are sent at the same (or near-real) time. Asynchronicity is a mode of communication where messages among participants are sent at different times. For the previous definitions, we consulted Mick and Middlebrook [START_REF] Snyder | Asynchronous and synchronous modalities[END_REF].

We remark that synchronous communication and asynchronous communication can be modeled by the ticks of a clock, where the ticks indicate the instances of time at which the communication (or processing) is performed. We can model synchronous communication by a global clock, where every agent communicates at the same instances of time as the other agents. Regarding asynchronous communication, we can model it by having an independent local clock for each agent, thus the agents can communicate at distinct instances of time.

Asynchronous communication and synchronous communication may not be fully realistic or practical. In asynchronous communication, an agent communicates to its neighboring agents one at a time, and thus it may be unpractical to wait for the handshakes from a neighbor that is either inactive or at that moment is executing a significantly costly process. On the other hand, in synchronous communication, it may happen that the interactions finished out of phase (some agents had no more messages to send but not the others), and hence one can not trust that all computations are complete.

Algorithms

In this subsection, we review some basic concepts related to algorithms. In particular, we review some preliminaries of distributed algorithms that are used in our example where a distributed algorithm is executed on a graph (discussed in Subsection 2.3.2). Also, we review randomized algorithms and gossip algorithms, which are used in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

For the definitions in this subsection, we consider the lecture notes by Hodkinson and Cunninghamas [START_REF] Hodkinson | Computability, Algorithms, and Complexity[END_REF]. For a supplementary reference to definitions related to algorithms, we recommend the textbook by Cormen et al. [START_REF] Cormen | Introduction to Algorithms[END_REF] We start by recalling a definition of a Turing machine. A Turing machine is a 6-tuple M = (S, Σ, Σ 0 , s 0 , F, f ), where

• S is a finite non-empty set, where an element of S is known as a state.

• Σ is a finite set of at least two elements, where Σ is known as the alphabet of M . It is required that a particular element b ∈ Σ, where b is known as the blank symbol.

• Σ 0 ⊆ Σ \ {b} is a non-empty set, where Σ 0 is known as the input alphabet of M .

• s 0 ∈ S is known as the initial state of M .

• F ⊂ S is known as the set of final states of M .

• f : (S \ F ) × Σ → S × Σ × {-1, 0, 1} is a partial function, where f is known as the instruction table of M .
We remark that a Turing machine can be interpreted as a 1-way infinite tape, a read/write head, and a finite set of states. A Turing machine can get its current state, read the current state, and then write, move, and change state according to its instruction table. The blank symbol is the only symbol in the alphabet that can occur on the tape infinitely many times. This way, we highlight that an algorithm is what a Turing machine implements.

In this dissertation, we sometimes simplify the interpretation of an algorithm, and thus consider it as a sequence of instructions aimed to perform a particular task. Sometimes, we express an algorithm as a function whose input is accessible to all instructions of the algorithm and whose output is the result of the last instruction of the algorithm.

We proceed by recalling definitions of the computation cost and the asymptotic time complexity.

The computational cost (also known as the running time) of an algorithm is the amount of time it takes to execute the algorithm. For example, let us consider a random walk on a graph, which, referring to Lovász [START_REF] Lovász | Random walks on graphs[END_REF], is a finite Markov chain (discussed in Subsection 2.4.3). In other words, a random walk on a graph is a stochastic process that describes a walk on a graph. If we interpreted a random walk as an algorithm, the computational cost of a random walk can be considered as the length of the walk that was taken until the random walk terminated.

When the computational cost of an algorithm is difficult to identify precisely, sometimes it can be helpful to consider the asymptotic time complexity of an algorithm, where the asymptotic time complexity can be expressed in big O notation. Let functions f, g : R → R. Big O notation O(•) is expressed as follows:

f (x) = O g(x) (as x → ∞),
which means that there exists k > 0 and x 0 ∈ R so that, for each x > x 0 , we have

f (x) ≤ kg(x).
In other words, big O notation is an asymptotic upper bound at the limit of arguments of a function going to infinity. In graph problems, the asymptotic time complexity of an algorithm is commonly expressed by an upper bound when the number of vertices of a graph or the number of edges of a graph goes to infinity.

We proceed by recalling definitions of a recursive algorithm, a randomized algorithm, a distributed algorithm, and a gossip algorithm.

A recursive algorithm is an algorithm which has at least one instruction that reuses the algorithm itself (such reuse is known as a nesting). This way, the recursion depth is defined as the maximal number of nestings within nestings. The recursion depth of an algorithm can be interpreted as a counter that decreases by 1 once the furthest nesting terminates. When the counter reaches 0, there are no more nestings to execute.

A randomized algorithm is an algorithm which uses random variables. For the previous definition, we consulted Motwani and Raghavan [START_REF] Motwani | Randomized Algorithms[END_REF].

A distributed algorithm is an algorithm which is executed in a distributed system. For example, a random walk on a graph is a distributed and randomized algorithm that models the traversal of a message in a communication network. For an elaborated discussion of distributed algorithms, we recommend the textbook by Tel [START_REF] Tel | Introduction to Distributed Algorithms[END_REF].

We discuss an example of a distributed, recursive, randomized algorithm that collects a sample of vertices of a graph G. Let r ∈ N 1 be the recursion depth. For each v ∈ V , let U v ⊆ N (v) be a uniformly-random choice of a subset of vertices from the neighborhood N (v). (We remark that U v contains scalars and not random variables.) Let a distributed, recursive, randomized algorithm A be defined as follows:

A(v, r) = {v} when r = 0, ∪ u∈Uv A(u, r -1) ∪ {v} when r > 0,
where ∪ denotes the union of sets and ∪ u∈Uv A(u, r -1) denotes the union of A(u, r -1) over each u ∈ U v . In the first step, the algorithm A appends the initial vertex v to the output set. Then, A propagates along the selected neighbors, adds them to the output set, and calls itself again with a decreased counter. This happens for r recursive iterations in total. If r is large enough, the output set contains all vertices of G if G is connected. This is because the algorithm propagates along every vertex of G.

As suggested by Jelasity [START_REF] Jelasity | Gossip". In: Self-organising Software -From Natural to Artificial Adaptation[END_REF], it is difficult to capture what exactly is a gossip algorithm. In this dissertation, we consider that a gossip algorithm is a distributed algorithm, where each agent of the communication network can disseminate or aggregate information along its neighboring agents. We provide a reference to Demers et al. [START_REF] Demers | Epidemic Algorithms for Replicated Database Maintenance[END_REF] which is known as one of the earliest formalizations of a gossip algorithm.

Basics of distributed algorithms on graphs

In this subsection, we discuss execution of distributed algorithms on graphs. In particular, we briefly review distributed averaging and discuss some assumptions, so that information at one agent of the communication network could at some point reach any other agent of the communication network, which is used in our example and contribution on the bias in distributed averaging when the graph of agents is non-regular (discussed in Chapter 3) Afterwards, we discuss an example where a random walk on the graph of a communication network provides a uniformlyrandom sample of a vertex of that graph. We remark that the aforementioned example illustrates the basis of the problem studied in Chapter 3.

Distributed averaging is a task where every agent of a communication network may communicate only with its neighboring agents, while aiming to compute the average of individual values attributed to all agents in the communication network. One of more common methods for solving such distributed averaging problems is an application of gossip algorithms [START_REF] Silvestre | Broadcast and Gossip Stochastic Average Consensus Algorithms in Directed Topologies[END_REF]. We remark that computing such averages is a basis for numerous applications that involve decision making or personalized modeling [START_REF] Almeida | DJAM: Distributed Jacobi Asynchronous Method for Learning Personal Models[END_REF]. We remark that decision making in distributed systems without a central curator is discussed in Tsitsiklis [START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF].

We review two common assumptions on the graph of a communication network for executing distributed algorithms, so that information at one agent of the communication network could at some point reach any other agent of the communication network.

The first assumption is that the graph G of a communication network is connected. The second assumption is that G has a self-loop or a cycle of odd length. For the source of the two assumptions, we refer to DeGroot learning [START_REF] Morris | Reaching a consensus[END_REF], where DeGroot learning refers to a particular model of distributed averaging.

Referring to the article by Lovász [Lov93], we discuss an example where a random walk samples a vertex of a graph G = (V, E). In particular, we show that a naive application of a random walk results in a biased sample, when G is non-regular (when the vertices have unequal degrees).

Let v beg denote the vertex on which the random walk begins. Let v end denote the vertex on which the random walk ends (v end is the sampled vertex). Let s ∈ N be the number of steps the random walk takes (s is a counter). Let n = |V | denote the number of vertices. Let T be an n × n matrix where, for each i, j ∈ [n], we have

t i,j = 1/deg(v i ) when v j ∈ N (v i ), 0 otherwise.
In DeGroot learning [START_REF] Morris | Reaching a consensus[END_REF], T is known as a transition matrix, where, for each i, j ∈ [n], the element t i,j of T is the probability of the transition from the vertex v i to the vertex v j , where v i , v j ∈ V . When each row of a transition matrix sums to 1, the transition matrix is a row stochastic matrix. When each row and each column of a transition matrix sums to 1, the transition matrix is a doubly stochastic matrix. We remark that the transition matrix T is a linear transformation from R n to R n . For the definitions of stochastic matrices, we consulted the textbook by Horn and Johnson [START_REF] Horn | Matrix Analysis[END_REF]. Let p(v | s, v beg ) denote the probability of sampling v ∈ V at the step s, when the random walk begins on the vertex v beg . Since the initial vertex v beg is chosen uniformly, let p(v beg ) be defined as a uniform probability mass function over the vertices in V . We define p(v | s, v beg ) by applying the transition matrix T iteratively as follows:

p(v | s, v beg ) = Tp(v | s -1, v beg ) = T s p(v beg ).
This way, p(v | s, v beg ) models a random walk that samples a vertex v of a graph G.

In Levin et al. [START_REF] Levin | Markov Chains and Mixing Times[END_REF], it is claimed that s = O(log n) is enough so that p(v | s, v beg ) is a stationary distribution over the vertices in V , when G is connected and has a self-loop or a cycle of odd length. For random walks, such stationary condition is more commonly known as the mixing time. When the mixing time is reached, we have

Pr(v end | s, v beg ) = deg(v end ) 2|E| ,
i.e., the probability of sampling v end is non-uniform when G is non-regular. In other words, the sampling is biased when G is non-regular. We recall how the aforementioned application of the random walk can be improved using the Metropolis-Hastings algorithm (discussed in Subsection 2.4.3) so that any vertex of G is sampled uniformly. The main idea behind such Metropolis-Hastings step is that, when the random walk proposes, for example, the edge (v 1 , v 2 ) which is the transition of the random walk from a vertex v 1 to a vertex v 2 , then we perform a Bernoulli trial for deciding if the edge is indeed taken or another edge proposal is drawn (and an additional check of a Bernoulli trial is made). The probability of succeeding such Bernoulli trial is defined as follows:

min 1, Pr(v 1 | s, v beg ) Pr(v 2 | s, v beg ) = min 1, deg(v 1 ) deg(v 2 ) .
As discussed later, upon the Metropolis-Hastings step and upon reaching the mixing time, the random walk provides a uniform sample of a vertex when G is non-regular. In other words, the Metropolis-Hastings step corrects the bias when G is non-regular.

Machine learning

In this section, we review machine learning. In particular, we review linear regression models used in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4). Also, we review the Metropolis-Hastings algorithm which we use in our examples on the bias of sampling a vertex of a graph using a random walk and in distributed averaging when the graph of agents is non-regular (discussed, respectively, in Subsection 2.3.2 and Subsection 3.1.2). At the beginning of this section, we review definitions of basic concepts of machine learning. In Subsection 2.4.1, we discuss supervised learning. In Subsection 2.4.2, we discuss clustering. In Subsection 2.4.3, we discuss statistical inference.

For a review of machine learning, we recommend and mostly follow the textbook by Mohri et al. [START_REF] Mohri | Foundations of Machine Learning[END_REF] For a supplementary reference to definitions of machine learning, we recommend the textbook by Mitchell [START_REF] Mitchell | Machine learning, International Edition[END_REF].

Mitchell [START_REF] Mitchell | Machine learning, International Edition[END_REF] defines machine learning as the study of algorithms that allows for computer programs to automatically improve through experience. This way, a learner (which is a computer program) is said to learn from experience with respect to some class of tasks and performance measure, if its performance at the class of tasks, as measured by the performance measure, improves with the experience. For example, this involves the case where the learner uses previously acquired information and current information for an accurate modeling of certain phenomena.

We start by discussing the following basic concepts of machine learning: an attribute, a feature, an example, and a label.

We interpret an attribute as a base characteristic of an entity. However, we remark that it is difficult to capture the definition of an attribute exactly, as it tends to vary from context to context. We interpret a feature as a value describing a characteristic of an entity, where such description is useful for tasks related to prediction, inference, and evaluation, and where a feature is computed from other attributes or features of an entity. We remark that we consider restrained definitions of attributes and features in order to clarify the motivation of our contribution on the tailored noise mechanism (discussed in Chapter 4).

An example (also known as an instance) is a representation of an entity, it may be a feature or a feature vector. A label (also known as a target value) is a value assigned to an example, which indicates a correspondence to a particular task. A pair of an example and a label is known as a labeled example. For instance, if an example contains characteristics of an email, a label could be an indicator of whether the email is spam or not. We denote a set of (all possible) examples by X , and we denote a set of (all possible) labels by Y.

We proceed by recalling definitions of a concept and a hypothesis. A concept is a function c : X → Y interpreted as an unknown function that models a phenomenon. A concept class is a set of concepts of interest; we denote a concept class by C. A hypothesis is a function h : X → Y interpreted as a model of a concept. A hypothesis space is a set of hypotheses; we denote a hypothesis space by H. For example, the set H of functions f (x) = θ 0 + θ 1 x over parameters θ 0 , θ 1 ∈ R is a hypothesis space of linear functions.

Referring to the lecture notes by Rosernberg [START_REF] Rosenberg | Excess Risk Decomposition[END_REF], we discuss the evaluation of how closely a hypothesis matches a concept. This way, we recall definitions of a loss function, the hypothesis risk, the empirical risk, and the empirical risk minimizer.

A loss function is a function L : Y × Y → R + that weights the cost of a choice of a hypothesis to model a given concept, where R + is the space of non-negative real numbers.

The hypothesis risk is defined as follows:

r(h, c) = X L h(x), c(x) dx,
where h is a hypothesis, c is a concept, L is a loss function, and X is a set of (all possible) examples. We remark that the hypothesis risk can not be computed because the concept c is unknown. The empirical risk is defined as follows:

r h, {(x i , y i )} n i=1 = 1 n i∈[n] L h(x i ), y i ,
where the set {(x i , y i )} n i=1 of labeled examples is a sample from a statistical population over X × Y, and where X , Y ⊆ R denote, respectively, a set of (all possible) examples and a set of (all possible) labels.

An empirical risk minimizer is a hypothesis defined as follows:

ĥ ∈ arg min h∈H r h, {(x i , y i )} n i=1 ,
where H is a hypothesis space. In Table 2.4, we provide a summary of the introduced notation of basic concepts of machine learning. Referring to the lecture notes by Rosernberg [START_REF] Rosenberg | Excess Risk Decomposition[END_REF], we discuss the hypothesis space error and the sampling error.

The hypothesis space error is the error due to selecting a particular hypothesis space and is defined as follows:

r(h H , c),
where a risk minimizer h H is defined as

h H ∈ arg min h∈H r(h, c).
The hypothesis space error r(h H , c) can not be computed because the concept c is unknown.

The observation error (also known as the sampling error) is the error due to limited number of observations and is defined as follows: r ĥ, {(x i , y i )} n i=1 -r(h H , c).

The observation error can not be computed because, as discussed above, we can not compute the hypothesis space error r(h H , c). However, we remark that the observation error can be approximated by upper-bounding it by the empirical risk r ĥ, {(x i , y i )} n i=1 .

Supervised learning

In this subsection, we discuss supervised learning. In particular, we review linear regression which is used in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4). We start by briefly reviewing supervised learning. Then, we discuss the fitting of statistical models. Finally, we discuss classification and regression, which are two common tasks related to supervised learning.

Supervised learning is a machine learning scenario where the learner has a set of labeled examples and a set of unlabeled examples, and where the learner intends to use the labeled examples to predict the labels for the unlabeled examples.

Referring to the textbook by Mitchell [START_REF] Mitchell | Machine learning, International Edition[END_REF], we discuss the fitting of statistical models. In particular, we discuss fitting, overfitting, and underfitting.

Let us consider the case where the learner uses labeled examples to estimate parameters of an underlying statistical model with the intention to predict the labels for unlabeled examples with sufficient accuracy. An estimation procedure that makes use of labeled examples to estimate model parameters is known as the fitting of a statistical model.

Regarding the accuracy of a fitted statistical model, it is influenced by the number of labeled examples used for fitting, the choice of a hypothesis space, and the choice of a fitting method. We remark that having more labeled examples leads to closer estimates of the parameters of an underlying statistical model because the sampling error decreases when the size of a sample increases. Also, we remark that a chosen hypothesis space intends to contain statistical models (hypotheses) that are sufficiently close to the underlying statical model (the concept).

Given a hypothesis space H, a hypothesis h ∈ H is said to overfit a sample if there exists some other hypothesis h ′ ∈ H, such that h has a smaller error than h ′ over the sample, but h ′ has a smaller error over the entire underlying statistical population. This way, overfitting is the case when the choice of a hypothesis h poorly generalizes the underlying concept c. Otherwise, when a hypothesis h has a smaller error over a sample than some other hypothesis h ′ because h is a function that lacks significant terms compared to the underlying concept c (e.g., h is a polynomial of a lower order than c), then the case of choosing such h is known as underfitting.

We proceed by discussing the evaluation of fitted statistical models.

The fit of a statistical model can be evaluated by assessing the utility (e.g., predictive accuracy) of the chosen hypothesis by splitting the available set of labeled examples to two subsets known as a training set and a test set. To elaborate on that process, we remark that, firstly, a statistical model is fitted using the training set. Then, we can compute predicted labels of the test set. Finally, the fit can be evaluated by, for example, summing the absolute differences between the predicted labels of the test set and the respective true labels of the test test.

The evaluation of a fit is more reliable when performing it on several choices of training sets and test sets, this is known as cross-validation. A common crossvalidation technique is k-fold cross-validation where the set of labeled examples is arbitrarily partitioned in k subsets (folds) of approximately equal size and the fitted statistical model is evaluated k times by taking 1 of those folds as a test set and forming a training set from the remaining k -1 folds.

We proceed by making a brief distinction between classification and regression. Classification is a supervised learning task where the labels are categorical (e.g., binary values), whereas regression is a supervised learning task where the labels are real-valued. We highlight that, in this dissertation, we focus on a particular form of linear regression where a target value is expressed as a linear function of features together with a noise term. More precisely, we consider multiple linear regression where a target value is expressed as a linear combination of features together with a noise term, where each feature is multiplied by a scalar parameter.

We proceed by discussing regression in more detail, for which we consult the textbook by Yan and Su [START_REF] Yan | Linear regression analysis: theory and computing[END_REF]. In particular, we start by recalling a definition of a multiple linear regression model. Then, we discuss two classic fitting methods for fitting a linear regression model. Finally, we discuss an example of evaluating the fit of a linear regression model.

We recall a definition of a multiple linear regression model with m + 1 regression parameters and a scalar target value. Let n ∈ N be the number of examples. Let m ∈ N be the number of features in an example (i.e., the size of a feature vector). For each i ∈ [n], we have

y i = θ 0 + θ 1 x i,1 + . . . + θ m x i,m + ξ reg i , (2.8)
where x i,1 , x i,2 , . . . , x i,m are features, θ 0 , θ 1 , . . . , θ m ∈ R are regression parameters, ξ reg i is regression noise which is an independent observation of N (0, σ 2 ), and σ is the standard deviation of regression noise.

We recall ordinary least squares which is a classic fitting method of a multiple linear regression model. Let θ be the vector of parameter estimates. Let X = 1 x 1 . . . x m ∈ R n×(m+1) be a matrix of features, where x 1 , x 2 , . . . , x m are feature vectors. Let y be a vector of target values. In ordinary least squares, the vector θ of parameter estimates can derived in the following way (the regression error terms are absent as they can not be observed):

y = X θ ⇐⇒ X T y = X T X θ ⇐⇒ θ = (X T X) -1 X T y ⇐⇒ θ = 1 n X T X -1 1 n X T y, (2.9) 1 n X T X =       1 1 n i∈[n] x i,1 . . . 1 n i∈[n] x i,m 1 n i∈[n] x i,1 1 n i∈[n] x 2 i,1 . . . 1 n i∈[n] x i,1 x i,m . . . . . . . . . . . . 1 n i∈[n] x i,m 1 n i∈[n] x i,1 x i,m . . . 1 n i∈[n] x 2 i,m       (2.10) 1 n X T y = 1 n i∈[n] y i 1 n i∈[n] y i x i,1 . . . 1 n i∈[n] y i x i,m T .
(2.11)

Since the matrix inverse 1 n X T X -1 can be numerically difficult to compute, we recall another classic fitting method known as regularized least squares (otherwise known as ridge regression) where the term 1 n X T X is substituted with the term

1 n X T X + λI m+1 =      1 + λ . . . 1 n i∈[n] x i,m 1 n i∈[n] x i,1 . . . 1 n i∈[n] x i,1 x i,m . . . . . . . . . 1 n i∈[n] x i,m . . . 1 n i∈[n] x 2 i,m + λ      , (2.12)
and where λ ∈ R is known as the regularization parameter, and I m+1 is the (m + 1) × (m + 1) identity matrix.

We discuss an example of evaluating the fit of a linear regression model Let {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x n , y n )} be a set of labeled examples (pairs of features and target values). For each i ∈ [n], we define the following linear regression model:

y i = θ 0 + θ 1 x i + ξ reg i ,
where θ 0 , θ 1 ∈ R are regression parameters, ξ reg i is regression noise which is an independent observation of N (0, σ 2 ), and σ is the standard deviation of regression noise. Let {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x k , y k )} and {(x k , y k ), (x k+1 , y k+1 ), . . . , (x n , y n )} be, respectively, a training set and a test set, where 1 < k < n. Let θ0 and θ1 be the parameter estimates computed from the training set by some fitting method (e.g., ordinary least squares). This way, for each i ∈ {k, . . . , n}, we compute a predicted target value y pred i as follows:

y pred i = θ0 + θ1 x i .
Finally, we can evaluate the fit of the learned model with the parameter estimates θ0 and θ1 by assessing its predictive accuracy. This way, for example, we can compute the following sum over the test set: i∈{k,...,n}

|y pred i -y i |.
However, we remind that evaluation of a fit is more reliable when applying the previously discussed cross validation.

Clustering

In this subsection, we discuss clustering. In particular, we review k-means clustering to which we refer in our future directions (discussed in Section 5.2).

For the definitions in this subsection, we consult the textbook by Shalev-Shwartz and Ben-David [START_REF] Shalev | Understanding Machine Learning -From Theory to Algorithms[END_REF] We start by briefly reviewing clustering which is part of a machine learning scenario known as unsupervised learning. We remark that in unsupervised learning, differently than in supervised learning, we have only unlabeled examples.

Clustering is a machine learning task where we have only unlabeled examples, where similar mathematical objects are grouped together in clusters (or partition classes) and dissimilar objects are grouped in separate clusters (or separate partition classes), and where distinct clusters can share the same instances (this leads to soft clustering which contrasts hard clustering where distinct partition classes do not share the same instances).

The assignment of an object to a cluster (or a partition class) can be interpreted as the assignment of a label that indicates the index of the cluster. As a result, in clustering, the labels simply indicate indexing, as opposed to some meaningful classes (which is the case in the task of classification). This way, it is difficult to apply a general technique to evaluate the success of a clustering procedure. We remark that even though a clustering procedure can provide a set of clusters that is informative, there might be other sets of clusters that are informative as well.

Common clustering methods include linkage-based clustering, k-means clustering, and spectral clustering:

• Linkage-based clustering methods are iterative methods where clusters merge if their similarity is high enough.

• k-means clustering methods are iterative methods where instances are associated to one of k clusters based on cost (e.g., distance) minimization.

• Spectral clustering methods are methods that group instances based on the eigenvalues of a similarity matrix of instances, where the (i, j)-th element of a similarity matrix is a similarity measurement between an instance i and an instance j.

We elaborate on k-means clustering methods because we refer to them upon discussing our future directions (discussed in Section 5.2).

k-means clustering is an iterative clustering method which partitions instances (with coordinates) into k partition classes based on center points (the initial coordinates of the center points of the k partition classes can be chosen arbitrarily), and one iteration of k-means clustering takes the following two steps:

1. Each clustered instance is assigned the label of the center point that has the shortest distance to the instance (the distance is computed based on the coordinates and a chosen metric).

2. The locations of the center points are updated taking the average values of the coordinates of the instances that are assigned to the respective center points.

Statistical inference

In this subsection, we discuss statistical inference. In particular, we review the Metropolis-Hastings algorithm which we use in our examples on the bias of sampling a vertex of a graph using a random walk and in distributed averaging when the graph of agents is non-regular (discussed, respectively, in Subsection 2.3.2 and Subsection 3.1.2).

For the definitions in this subsection, we consult the textbook by Hastie et al. [START_REF] Hastie | The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition[END_REF] We start by reviewing statistical inference, where statistical inference is part of artificial intelligence which is a field that is broader than machine learning.

Statistical inference (also known as inference) is a task where probabilistic information is inferred from evidence. Let D = {(x 1 , y 1 ), (x 2 , y 2 ), . . . , (x n , y n )} be a sample of labeled examples (also known as evidence). Let H denote a hypothesis space. Common statistical inference methods include maximum likelihood inference and Bayesian inference:

• Maximum likelihood inference involves methods that aim for obtaining a hypothesis h L = arg max h∈H Pr(D | h). In other words, such methods choose the hypothesis h L for which the likelihood (defined below) of observing the evidence D is maximized.

• Bayesian inference involves methods that aim for obtaining a hypothesis h P = arg max h∈H Pr(h | D). In other words, such methods choose the hypothesis h P that maximizes the posterior (defined below) upon the evidence D.

We proceed by reviewing Bayesian inference in more detail. Bayesian inference is a form of statistical inference characterized by an application of Bayes' theorem and by the treatment of the output and the parameters of statistical models as random variables. Let random variables X and Θ be, respectively, the output of a statistical model and the parameter of the statistical model. In Bayesian inference, the relation between X and Θ is established by Bayes' theorem as follows:

p Θ (θ | x) = p X,Θ (x, θ) p X (x) = p X|Θ (x | θ)p Θ (θ) p X (x) = p X|Θ (x | θ)p Θ (θ) p X|Θ (x | θ)p Θ (θ)dθ ,
where p X is known as a prior probability distribution (or simply a prior), p Θ | X is known as a posterior distribution (or simply a posterior), p X|Θ (x | θ) is known as a likelihood, and p X|Θ (x | θ)p Θ (θ)dθ is known as a marginal likelihood.

The marginal likelihood can be difficult to compute and thus may require to restate the Bayesian inference problem. This way, in Bayesian inference, it is common to estimate the posterior rather than obtain it exactly. For example, variational methods is a family of such methods, where a variation (a probability distribution) substitutes the likelihood in such a way that the integration in the marginal likelihood has a closed-form expression. Hence, the marginal likelihood appears feasible to compute in practical settings.

We proceed by discussing Markov chain Monte Carlo methods which is another method for estimating the posterior. Then, we review a definition of a particular Markov chain Monte Carlo method known as the Metropolis-Hastings algorithm.

A Markov chain Monte Carlo (MCMC) method is an algorithm that is characterized by repeated sampling and the use of Markov chains, where a Markov chain is a stochastic process in which every state can only depend on the state that precedes it. Let x and x ′ denote outcomes that can be interpreted as states of a Markov chain, where x ′ precedes x. In MCMC methods, we use an iterative procedure where we obtain x ′ given x, update x by the obtained value x ′ , and then repeat.

The Metropolis-Hastings (MH) algorithm [START_REF] Hastings | Monte Carlo sampling methods using Markov chains and their applications[END_REF] is a particular MCMC method for obtaining a sequence of observations from a probability distribution (known as the target distribution). We remark that the MH algorithm approximates the target distribution without the influence of autocorrelation, where autocorrelation refers to the case where subsequences of observations are correlated.

We proceed by describing the MH algorithm. Let x and x ′ denote states which are respective outcomes of random variables X and X ′ . Let g X ′ | X and g X | X ′ denote conditional probability distributions; we refer to them as proposal distributions. Let t ∈ N be the number of iterations. In each iteration i ∈ [t], the MH algorithm computes

p i (x) = g X ′ | X (x ′ | x)a(x, x ′ ), where a(x, x ′ ) = min 1, p i-1 (x ′ ) p i-1 (x) g X | X ′ (x | x ′ ) g X ′ | X (x ′ | x)
is known as the acceptance rate and p 0 is fixed in advance. When i ∈ [t] increases, then p i approaches a stationary distribution and approximates more closely the target distribution. We remark that a stationary distribution is the probability distribution of a random variable in a stationary process, and a stationary process is a stochastic process where the unconditional joint probability distribution of the random variables does not change in time when the stochastic process is shifted in time.

Data privacy

In this section, we briefly review the field of data privacy. In particular, we review the threat model of honest-but-curious agents and the classic privatization mechanisms that are used in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

At the beginning of this section, we discuss basic concepts of data privacy. In Subsection 2.5.1, we discuss a common measure of data privacy known as differential privacy.

For this section, we consult the survey by Aggarwal and Yu [START_REF] Charu | On static and dynamic methods for condensation-based privacy-preserving data mining[END_REF].

When speaking of data privacy, we tend do consider real-world communication networks of agents, where an agent is a user's device, a remote server, a computer cluster, etc. If the awareness of a particular attribute of an agent could lead to an unwanted profiling of the agent, we refer to such attribute as a sensitive attribute.

We briefly elaborate on the following data privacy measures:

• In k-anonymity, each sensitive attribute of each instance of a shared dataset has the same value as at least k -1 respective sensitive attributes of other instances in the dataset.

• In l-diversity, each sensitive attribute of a shared dataset has at least l distinct values that are present in it.

• In (ϵ, δ)-differential privacy, each sensitive attribute of a shared dataset is hidden under noise that is calibrated in a particular way based on parameters ϵ, δ ≥ 0.

In this dissertation, we focus on differential privacy. We proceed by discussing a distinction between local data privacy and central data privacy, we do so by partially consulting the tutorial slides by Nguyen [START_REF] Nguyen | Tutoriel: Anonymization Techniques: Theory and Practice[END_REF].

In local data privacy, each agent shares its own dataset, and thus each agent is responsible on its own to make sure that the shared dataset meets the conditions of a selected data privacy measure. In central data privacy, each agent trusts a central curator, and thus it is the central curator who shares a dataset which contains instances (or statistics) of information provided by the agents. This way, it is the central curator who makes sure that the shared dataset meets the conditions of a selected data privacy measure.

We recall the threat model of honest-but-carious agents, where a threat model is a model that specifies what kind of access an attacker has to a system when attempting to disturb it or learn something that should be kept private.

Honest-but-curious agents [START_REF] Goldreich | The Foundations of Cryptography -Volume 2: Basic Applications[END_REF] is a threat model where the agents of a communication network follow the communication protocol (honesty) but they are also interested in discovering all available information (curiosity). We remark that honest-but-curious agents can be seen as a realistic threat model concerning local data privacy because, in local data privacy, the agents communicate among each other as opposed to relying on a central curator.

Differential privacy

In this subsection, we discuss differential privacy which is an actively studied measure of data privacy. In particular, we review the Gaussian mechanism and the Laplace mechanism which are used, respectively, in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

For a review of differential privacy, we recommend and mostly follow the article by Dwork and Roth [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF].

We start this subsection by recalling the definition of (ϵ, δ)-indistinguishability which was proposed by Dwork et al. [START_REF] Dwork | Our Data, Ourselves: Privacy Via Distributed Noise Generation[END_REF] and is commonly known as differential privacy.

Definition 5. Let ϵ, δ ≥ 0. A randomized algorithm A is (ϵ, δ)-differentially private if and only if, for all S ⊆ image(A) and for all tuples (D, D ′ ) in a collection where adjacent datasets D and D ′ differ only in the attributes of one instance, we have

Pr(A(D) ∈ S) ≤ e ϵ Pr(A(D ′ ) ∈ S) + δ.
The aforementioned collection of tuples (D, D ′ ) is a set of tuples of adjacent datasets, where adjacent datasets are datasets that differ in one row, and where a dataset is a table whose rows are over instances and the columns are over attributes.

We highlight that, in local differential privacy, each agent adds noise to its sensitive attributes on its own, whereas, in central differential privacy, a central curator typically adds noise to statistics computed from attributes. Thus, in central differential privacy, it is more common to refer to sensitive statistics as opposed to sensitive attributes. We remark that adding noise to sensitive statistics as opposed to sensitive attributes results in a lower error between a privatized statistic and a sensitive statistic, when such statistics are averages computed from attributes.

Regarding the motivation of central differential privacy, bounding the probability of observing one adjacent dataset by the probability of observing another adjacent dataset (as in Definition 5) can be interpreted as a level of privatization, which is measured by the privacy budget (ϵ, δ), against a reconstruction attack, where by a reconstruction attack we refer to an identification of the value of a sensitive attribute. Referring to Garfinkel et al. [START_REF] Simson | Understanding database reconstruction attacks on public data[END_REF], we remark that, in a reconstruction attack, an attacker can reconstruct sensitive attributes by making comparisons of the following two statistics: a statistic that is computed over the sensitive attributes and a statistic that is computed over the same sensitive attributes except some of them being removed or modified in a particular way.

We remark that, when the privacy budget (ϵ, δ) is higher, the noisiness of privatized statistics or privatized attributes is lower because it is easier to meet the bound in Definition 5.

We proceed by recalling definitions of the Gaussian mechanism and the Laplace mechanism, which are classic privatization mechanisms for adding noise to sensitive attributes.

Firstly, we define the Gaussian mechanism.

Definition 6. Let ϵ, δ > 0. Let X ⊆ R n , where n ∈ N. Let f : X → R k ,
where k ∈ N. The Gaussian mechanism is a mechanism that privatizes a value f (x), where x ∈ X , by adding to it independent observations of the following Gaussian random variable:

N 0, 2 log(1.25/δ)∆ 2 2 (f ) ϵ 2 ,
where the l 2 sensitivity

∆ 2 (f ) = max adjacent x 1 ,x 2 ∈X ∥f (x 1 ) -f (x 2 )∥ 2 . (2.13)
We remark that generation of noisy values according to the Gaussian mechanism is a classic strategy to guarantee (ϵ, δ)-differential privacy.

Secondly, we define the Laplace mechanism.

Definition 7. Let ϵ > 0. Let X ⊆ R n , where n ∈ N. Let f : X → R k ,
where k ∈ N. The Laplace mechanism is a mechanism that privatizes a value f (x), where x ∈ X , by adding to it independent observations of the following Laplace random variable:

lap 0, ∆(f ) ϵ ,
where the l 1 sensitivity

∆(f ) = max adjacent x 1 ,x 2 ∈X ∥f (x 1 ) -f (x 2 )∥ 1 . (2.14)
We remark that generation of noisy values according to the Laplace mechanism is a classic strategy to guarantee (ϵ, 0)-differential privacy (also known as ϵ-differential privacy).

Finally, we highlight that Dwork and Roth [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF] provides a composition theorem which states that a collection of size k of (ϵ, δ)-differentially private randomized algorithms is (kϵ, kδ)-differentially private. In our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4) we reuse the aforementioned composition theorem. In particular, we refer to (kϵ, kδ) as the (total) privacy budget and we refer to (ϵ, δ) as an even split (one of k parts) of the total privacy budget.

Mathematical optimization

In this section, we briefly review mathematical optimization. In particular, we review the standard form of a convex program, which is accepted by the cvxopt package, and that is used in our contribution on the tailored noise mechanism (discussed in Chapter 4).

At the beginning of this section, we discuss basic vocabulary of mathematical optimization and convex programs. In Subsection 2.6.1, we discuss the basic principles of implementing a convex program using the cvxopt package.

For a review of mathematical optimization, we recommend and mostly follow the textbook by Boyd and Vandenberghe [START_REF] Boyd | Convex Optimization[END_REF].

We start by reviewing mathematical optimization.

Mathematical optimization is a field on solving optimization problems that can be stated in the following form: we intend to minimize f 0 (w) subject to the constraints

f 1 (w) ≤ b 1 , f 2 (w) ≤ b 2 , . . . , f k (w) ≤ b k ,
where w ∈ R n are optimization variables (also known as constraint variables),

n ∈ N, f 0 : R n → R is an objective function, f 1 , f 2 , . . . , f k : R n → R are constraint functions, b 1 , b 2 , . . . , b k ∈ R
are upper-bounds of constraint functions, and k ∈ N is the number of constraints.

An optimization problem is feasible if there exist values of the constraint variables so that the constraints of the optimization problem are met. Otherwise, an optimization problem is infeasible. For example, let w 1 and w 2 be constraint variables whose values are in the interval [1, 2]. If an optimization problem consists of the equality constraint w 1 + w 2 ≤ 2, then the optimization problem is feasible because w 1 and w 2 can take the value 1. However, upon the inequality constraint w 1 + w 2 ≤ 1, the optimization problem is infeasible because w 1 + w 2 is at least 2.

If w results in the lowest value of the objective function of an optimization problem such that the constraints are met, then we refer to w as a solution of the optimization problem. We remark that a value of the objective function is referred to as an objective value.

We briefly elaborate on some subfields of mathematical optimization:

• In linear optimization, the objective function and the constraint functions are linear functions.

• In non-linear optimization, the objective function and the constraint functions are non-linear functions.

• In convex optimization, the objective function and the constraint functions are convex functions, where a function f : R n → R is convex if the domain of f is a convex set S and if for each x, y ∈ S, we have f

(αx + (1 -α)y) ≤ αf (x) + (1 -α)f (y)
, where n ∈ N and 0 ≤ α ≤ 1 (a set S is convex if, for any x, y ∈ S and any 0 ≤ α ≤ 1 , we have αx + (1 -α)y ∈ S). This way, convex optimization is a generalization of linear optimization or a special case of non-linear optimization.

In this dissertation, we focus on convex optimization. We highlight that optimization problems solved in convex optimization can be stated in the following form: we intend to minimize f 0 (w) subject to the constraints

f 1 (w) ≤ 0, f 2 (w) ≤ 0, . . . , f k (w) ≤ 0, g 1 (w) = 0, g 2 (w) = 0, . . . , g l (w) = 0, where w ∈ R n are constraint variables, n ∈ N, f 0 : R n → R is a (convex) objective function, f 1 , f 2 , . . . , f k : R n → R are (convex) inequality constraint functions, k ∈ N
is the number of inequality constraints, g 1 , g 2 , . . . , g l : R n → R are (convex) equality constraint functions, and l ∈ N is the number of equality constraints. We refer to an optimization problem solved in convex optimization as a convex program. Finally, we remark that, in this dissertation, we consider algorithms that are designed to find solutions of convex programs in an iterative manner and under the stopping condition which is met when an infeasibility measure gets lower than a prescribed tolerance (i.e., in such algorithms, we allow for some slack that concerns the feasibility). We refer to such algorithms as constraint solvers. To summarize, we consider constraint solvers that are guided by the following two factors:

• The feasibility of the constraints.

• The minimization of the objective function.

The cvxopt package

In this subsection, we discuss the basic principles of solving a convex program using cvxopt [ADV20] which is a python library. We remark that cvxopt is used in our contribution on the tailored noise mechanism (discussed in Chapter 4)

We describe the elements of a convex program, which are accepted by the standard form of cvxopt. Let w ∈ R n be the constraint variables of a convex program, where n is the number of constraint variables. The arguments to the convex constraint solver of cvxopt are data structures that represent the linear equality constraints, the linear inequality constraints, the objective function, and the non-linear constraints of a convex program: 2.7. Summary Chapter 2. Background

• The linear equality constraints. Let A ∈ R k×n be a matrix whose elements are the coefficients of constraint variables in the linear equality constraints, and where k is the number of linear equality constraints. Let b ∈ R k be a vector whose elements are the constant terms in the linear equality constraints. The aim of the constraint solver is to find such w that Aw = b.

• The linear inequality constraints. Let G ∈ R l×n be a matrix whose elements are the coefficients of constraint variables in the linear inequality constraints, and where l is the number of linear inequality constraints. Let h ∈ R l be a vector whose elements are the constant terms in the linear inequality constraints. The aim of the constraint solver is to find such w that Gw ⪯ h (where ⪯ denotes "element-wise less than or equal").

• The objective function. Let f cvx 0 : R n → R + denote a twice-differentiable objective and convex function, where R + is the space of non-negative real numbers. The aim of the constraint solver is to minimize f cvx 0 (w).

• The non-linear constraints. Let f cvx 1 , f cvx 2 , . . . , f cvx m : R n → R denote twicedifferentiable non-linear (yet convex) constraint functions, where m is the number of non-linear constraints. The aim of the constraint solver is to find such w that, for each i ∈ [m], we have

f cvx i ⪯ 0.
In each iteration of the constraint solver, cvxopt requires to evaluate the firstorder partial derivatives and the second-order partial derivatives of the objective function f cvx 0 and the non-linear constraint functions f cvx 1 , f cvx 2 , . . . , f cvx m . The first-order partial derivatives are stored in a matrix D ∈ R (1+m)×n whose first row contains the first-order partial derivatives of f cvx 0 evaluated on w, and whose subsequent rows contain the first-order partial derivatives of non-linear constraints f cvx 1 , f cvx 2 , . . . , f cvx m evaluated on w. The second-order partial derivatives are stored in a matrix H ∈ R n×n such that

H = i={0}∪[m] z i ∇ 2 f cvx i (w),
where ∇ 2 f cvx i (w) is the matrix of the second-order partial derivatives of f cvx i evaluated on w, and z 0 , z 1 , . . . , z n m are scalars provided by the constraint solver. We highlight that the matrix A of linear equality constraints, the matrix G of linear inequality constraints, the matrix D of first-order partial derivatives, and the matrix H of second-order partial derivatives can be sparse, i.e., most of their entries equal to 0. Storing those matrices in data structures dedicated to sparse matrices reduces the computational cost and the memory cost of the convex program.

Summary

In this section, we briefly summarize how the fields reviewed in this chapter make part of the settings that are related to this dissertation. First, we provide a diagram that indicates the relations among the fields and the settings. Then, we briefly elaborate on the settings. Finally, we summarize the main reasons why the reviewed fields are selected for this dissertation.

In Figure 2.5, we illustrate the relation among the fields and the settings that are part of (or close to) the scope of this dissertation. We remark that we use simplified and broadened naming of the settings because our main intention is to highlight the boundary between the aspects that are part and outside the scope of this dissertation. We briefly elaborate on the settings (illustrated in Figure 2.5) that are part of (or close to) the scope of this dissertation.

The setting with static, distributed models refers to the case when a communication network of agents is modeled by a fixed graph, whereas the setting with dynamic models (outside the scope) refers to the case where the graph of the communication network changes over time.

The setting with optimized, privatized models refers to the case with utilitymaximizing privatization mechanisms, as opposed to the classic privatization mechanisms, e.g., the Gaussian mechanism (Definition 6) and the Laplace mechanism (Definition 7). We remark that classic privatization mechanisms result, typically, in more privatization noise than necessary (discussed in Chapter 4).

The setting with personalized models (outside the scope) refers to the case where each agent (or a distinct subgroup of agents) of a communication network aims for learning local statistical models, as opposed to the case where all the agents aim for learning the same statistical model.

We summarize the main reasons why the reviewed fields (illustrated in Figure 2.5) are selected for this dissertation.

Regarding probability theory, we use Hoeffding's inequality in our example of distributed averaging on Erdős-Rényi graphs (discussed in Section 3.2) and we use U-statistics in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

Regarding graph theory, we use power-law degree sequences in our contribution on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3).

Regarding random graphs, we use the Erdős-Rényi model and the configuration model, respectively, in our example and contribution on distributed averaging on random graphs (discussed, respectively, in Section 3.2 and Section 3.3).

Regarding distributed systems, we discuss overlay networks and gossip algorithms for distributed averaging in our examples and contribution on the bias in distributed averaging when the graph of agents is non-regular (discussed in Chapter 3). Also, we discuss a central curator which is present in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

Regarding machine learning, we use linear regression models in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

Regarding data privacy, we use the threat model of honest-but-curious agents and the classic privatization mechanisms in our contributions on distributed averaging on graphs with arbitrary degree sequences (discussed in Section 3.3) and the tailored noise mechanism (discussed in Chapter 4).

Finally, regarding mathematical optimization, we review the standard form of a convex program, which is accepted by the cvxopt package, and that is used in our contribution on the tailored noise mechanism (discussed in Chapter 4). In particular, we use a convex program to design a utility-maximizing privatization mechanism.

Chapter 3

Bias in distributed averaging

In this chapter, we study the setting of distributed averaging (discussed in Subsection 2.3.2), where each agent of a communication network is attributed a vector of individual values, and where each agent intends to collaboratively (without a central curator) compute the unbiased averages over all the aforementioned vectors. In particular, we aim for performing distributed averaging while mitigating the bias which is present when the graph of agents is non-regular (i.e., the numbers of neighbors vary).

Usually, existing works solve this problem by assuming that either (i) each agent reveals its degree to its neighbors or (ii) every two neighboring agents can perform handshakes (discussed in Section 2.3) in every exchange of information. However, the degrees reveal information about the profiles of the agents and the handshakes are impractical upon inactive agents.

Outline. In Section 3.1, we discuss two approaches for computing an unbiased empirical distribution of the individual values attributed to the agents: the first approach is based on overlay networks (discussed in Section 2.3) and the second approach is based on the simple gossip algorithm (discussed in Subsection 2.3.1). In Section 3.2, we walk through an example of proving an asymptotic guarantee for the spectral norm of the difference between the linear transformation 1 T 1 n (centralized averaging) and the linear transformation due to the simple gossip algorithm upon convergence, where 1 is the vector of 1's of length n, and when the graph of agents is modeled by the ER model (Definition 2). In Section 3.3, we prove an asymptotic guarantee for the mean squared error between the average of sensitive attributes and the average of locally privatized attributes computed by a bias-correcting variant of the simple gossip algorithm, when the graph of agents is modeled by the configuration model (Definition 4), and when the agents interact without handshakes.

Estimating empirical distributions

At the beginning of this section, we formulate the problem of estimating a probability distribution in a distributed manner.

Let G = (V, E, λ, Σ) be a vertex-labeled graph, where Σ is a set of (all possible) labels (real-valued vectors) and a function λ : V → Σ assigns a label to a vertex.

Estimating empirical distributions Chapter 3. Bias in distributed averaging

Our communication network is on the graph G, and each agent (a vertex in V ) is assigned a label l which is drawn independently from some fixed but unknown probability distribution on Σ.

We aim for approximating the unknown probability distribution by an empirical distribution pΣ , where the probability of observing a label l is the following:

pΣ (l) = |{v ∈ V | λ(v) = l}| |V | . (3.1)
In Subsection 3.1.1, we discuss computation of an unbiased empirical distribution by an overlay network (discussed in Section 2.3). In Subsection 3.1.2, we discuss computation of an unbiased empirical distribution using gossip algorithms (discussed in Subsection 2.3.1).

Approach with an overlay network

The agents of a communication network can obtain the empirical distribution pΣ (Equation 3.1) in a distributed manner using an overlay network which is a tree.

We summarize the application of such overlay network as follows:

1. The agents compute a spanning tree of the graph, for example, by an algorithm discussed in Gallager et al. [START_REF] Gallager | A Distributed Algorithm for Minimum-Weight Spanning Trees[END_REF] 2. The agents propagate their labels (and all the labels they receive from others during the process) towards the root of the spanning tree. (If a smaller sample is desired they toss a coin and only propagate their own label with the probability equal to the size of the desired sample divided by the number of vertices). Since the overlay network is a tree, the root receives each label only once, and thus the computation of the empirical distribution pΣ at the root is unbiased.

3. The root broadcasts the sample back through the spanning tree overlay network, thus each agent is aware of the empirical distribution pΣ .

The issue with the approach of computing the empirical distribution pΣ by a spanning tree overlay network is that the transmission of the final sample is not robust upon failure or inactivity of a single agent. It is even worse when the failing agent is closer to the root because less agents in total can receive the result.

Approach with gossip algorithms

The agents of a communication network can compute the empirical distribution pΣ (Equation 3.1) by distributed averaging using gossip algorithms.

In this subsection, we firstly recall the simple gossip algorithm (Algorithm 1) and illustrate an example of applying Algorithm 1 for estimating the empirical distribution pΣ (we do so by defining Algorithm 2). Then, we show that we have a bias between the empirical distribution estimated by Algorithm 2 and the empirical distribution pΣ , when the graph G = (V, E, λ, Σ) of the communication network is non-regular (when the vertices have unequal degrees). Finally, we recall how the Chapter 3. Bias in distributed averaging 3.1. Estimating empirical distributions Metropolis-Hastings step (discussed in Subsection 2.3.2) can improve Algorithm 2, so that the aforementioned bias is corrected when each agent makes use of the degrees of its neighbors.

Simple gossip algorithm. We recall the simple gossip algorithm by defining Algorithm 1 below, which is a special case of gossip algorithms discussed by Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF] We remark that one iteration of Algorithm 1 is a linear transformation from R n to R n , i.e., the transition matrix T = diag(d) -1 A, where A is the adjacency matrix of the graph G of agents and d is the degree sequence of G. In other words, one iteration of Algorithm 1 involves each agent averaging the values revealed by its neighbors. This way, the execution of Algorithm 2 for the number t go of gossip iterations results in the linear transformation T tgo .

Algorithm 1: SimpleGossip (SiGo)

Input : A ∈ [0, 1] n×n : adjacency matrix of the graph G of agents t go ∈ N : number of gossip iterations

w ∈ R n Output : z ∈ R n 1 d ← i∈[n] A :,i 2 T ← diag(d) -1 A 3 z ← T tgo w
We illustrate an example of applying SiGo (Algorithm 1) for computing the order n of G, when G is a complete graph and has all self-loops. We assign a label 1 to one agent, and a label 0 to the remaining n -1 agents. In the 1-st iteration of SiGo, each agent computes the average 1+0+...+0 n = 1 n . By taking the reciprocal of 1 n , each agent computes n.

We proceed by illustrating an example of applying Algorithm 1 for estimating the empirical distribution pΣ , we do so by defining Algorithm 2 below. Firstly, for each vertex v ∈ V with a label λ(v), let I[λ(v)] ∈ {0, 1} |Σ| be the initial estimate of the empirical distribution pΣ , where the probability of the label λ(v) is 1 and all other probabilities are 0. Then, we remark that the output of Algorithm 2 is a matrix, as opposed to a vector (as in Algorithm 1). This way, for i ∈ [n], the i-th row of the aforementioned matrix contains an estimate of the empirical distribution pΣ computed by the agent i. Also, we remark Algorithm 1 corresponds to centralized simulation of distributed averaging, whereas Algorithm 2 corresponds to a decentralized one.

Algorithm 2: SimpleGossip for estimating a distribution

Input : G = (V, E, λ, Σ) : labeled graph of order n t go ∈ N : number of gossip iterations Output : Y (tgo) ∈ R n×|Σ| : estimates of the empirical distribution pΣ

1 for v ∈ V do 2 Y (0) v,: ← I[λ(v)] 3 for j ← 1 to t go do 4 for v ∈ V do 5 Y (j) v,: ← u∈N (v) Y (j-1) u,: deg(v)
In Line 6 of Algorithm 2, each agent iteratively updates its estimate by averaging the estimates computed by its neighbors. This way, when G is non-regular, there exist such v, u ∈ V so that deg(v) ̸ = deg(u). Thus, when Algorithm 2 converges, we have a bias (also discussed in Subsection 2.3.2) between a value of the empirical distribution estimated by Algorithm 2 and the respective value of the empirical distribution pΣ , when G is non-regular.

Metropolis-Hastings gossip algorithm. Algorithm 2 can be improved using the Metropolis-Hastings step (discussed in Subsection 2.3.2) in order to obtain unbiased estimates of the values of the empirical distribution pΣ , when G is non-regular; such improvement is defined by Algorithm 3 where for any neighboring vertices u, v ∈ V , we have

f MH (u, v) = 1 if deg(v) ≥ deg(u) and f MH (u, v) = deg(v)
deg(u) otherwise. We remark that the simple gossip algorithm with the Metropolis-Hastings step (MetropolisHastingsGossip) is discussed in Kenyeres and Kenyeres [START_REF] Kenyeres | Applicability of Generalized Metropolis-Hastings Algorithm to Estimating Aggregate Functions in Wireless Sensor Networks[END_REF] as well as Giaretta and Girdzijauskas [START_REF] Giaretta | Gossip Learning: Off the Beaten Path[END_REF].

Algorithm 3: MetropolisHastingsGossip for estimating a distribution

Input : G = (V, E, λ, Σ) : labeled graph of order n t go ∈ N : number of gossip iterations Output : Y (tgo) ∈ R n×|Σ| : estimates of the empirical distribution pΣ

1 for v ∈ V do 2 Y (0) v,: ← I[λ(v)] 3 for j ← 1 to t go do 4 for v ∈ V do 5 Y (j) v,: ← u∈N (v) f MH (u,v)Y (j-1) u,: + 1-f MH (u,v) Y (j-1) v,: deg(v)
When Algorithm 3 converges, each value of the empirical distribution pΣ (present in each row of the output) is unbiased due to the factor f MH (u, v) and the factor 1 -f MH (u, v) in Line 6. We remark that, for computing f MH (u, v), each agent has to be aware of the degree of its neighbors, while in some contexts the degree is a sensitive attribute.

We recall that Algorithm 1, Algorithm 2, and Algorithm 3 converge when the graph G is connected and has a self-loop or a cycle of odd length, as discussed in Subsection 2.3.2.

Averaging on ER graphs

In this section, we continue to study the bias between the average of individual values computed by the simple gossip algorithm (Algorithm 1) and the true average of individual values, when the graph G = (V, E) of agents is non-regular, as initially discussed in Subsection 3.1.2. When G is regular, the linear transformation due to the simple gossip algorithm upon convergence equals the linear transformation 1 T 1 n (centralized averaging), thus the bias is absent, where 1 is the vector of 1's of length n = |V |.

In particular, we walk through an example of proving an asymptotic guarantee for the spectral norm of the difference between the linear transformation 1 T 1 n and the linear transformation due to the simple gossip algorithm (Algorithm 1) upon convergence, when the graph of agents is modeled by the ER model (Definition 2). Instead of a scalar transition matrix T, we consider a random transition matrix T = diag(D) -1 A, where A is the random adjacency matrix of a random graph modeled by the ER model, and D is the random degree sequence of the random graph. We remark that the degree sequence D can be computed from the rows of (and thus depends on) the adjacency matrix A.

We intend to quantify the difference between the linear transformation 1 T 1 n (centralized averaging) and the linear transformation due to the simple gossip algorithm (Algorithm 1) upon convergence, when the simple gossip algorithm is executed on a graph modeled by the ER model. Thus, we intend to upper-bound the spectral norm

T tgo -1 T 1 n 2
, where t go is the number of gossip iterations. In particular, we provide Theorem 1 and walk through its proof. We remark that some techniques used in the proof of Theorem 1 result in a suboptimal asymptotic guarantee compared to similar works such as Lugosi et al. [START_REF] Lugosi | Concentration of the spectral norm of Erdős-Rényi random graphs[END_REF] However, by Theorem 1, we intend to provide an upper bound for the spectral norm

T tgo -1 T 1 n 2 instead of the spectral norm 1 np A -11 T n 2
, where the latter spectral norm is found in the literature, and where, for the former spectral norm, we have not found a reference in the literature. Also, we consider a transition matrix T which is random as opposed to fixed, and remark that the case where such transition matrix is fixed is discussed in the slides by Iutzeler [START_REF] Iutzeler | Gossip algorithms: Tutorial and Recent advances (part 1)[END_REF].

Theorem 1. Let A be the random adjacency matrix of an ER random graph modeled by the probability mass function p G (G | n, p), where n is the order of the graph, p is the probability of edge assignment between any two distinct vertices of the ER random graph, and G is an observation of the ER random graph. Let D be the random degree sequence of the ER random graph. Let T = diag(D) -1 A. Let us assume that the 2-nd largest singular value of T is O log n √ n . (We support the assumption in the proof.) With high probability, we have

lim tgo→∞ T tgo - 1 T 1 n 2 = O log n √ n , when p ∈ (log n) 2 n , 1 -(log n) 2 n .
Proof. Our proof is split in five parts. In the first part, we decompose the spectral norm in three components. From the second to the fourth part, we upper bound, respectively, the spectral norm of each of the decomposed components. In the fifth part, we compose the three upper bounds to obtain our result. Decomposition. We decompose the spectral norm as follows:

T tgo - 1 T 1 n 2 = T tgo -T + T - 1 np A + 1 np A - 1 T 1 n 2 ≤ T tgo -T 2 + T - 1 np A 2 + 1 np A - 11 T n 2 ,
where the second line is due to the triangle inequality.

The first component T tgo -T 2 . Let U be the random matrix of eigenvectors of the random transition matrix T, and let V be the random diagonal matrix of eigenvalues of T, so that UVU -1 is the eigendecomposition of T.

We highlight that

T tgo = UVU -1 . . . UVU -1 = UV tgo U -1 .
This way,

T tgo -T 2 = UV tgo U -1 -UVU -1 2 = U V tgo -V U -1 2 .
We recall that the spectral norm of a matrix equals the largest singular value of the matrix (indicated by Equation 2.1), and singular values can be obtained from respective eigenvalues. Then, we recall that the eigenvalues of the matrix U V tgo -V U -1 are in the diagonal of the matrix V tgo -V, since the matrix U V tgo -V U -1 is the eigendecomposition of the matrix T tgo -T.

An observation of T is a row stochastic matrix because the sum of each row of T is constrained to equal 1. In Banerjee and Mehatari [START_REF] Banerjee | An eigenvalue localization theorem for stochastic matrices and its application to Randić matrices[END_REF], the authors indicate that 1 is the highest singular value of a row stochastic matrix. This way, (1, 1) is a pair of an eigenvalue and an eigenvector of T. In Paz [START_REF] Paz | Graph-theoretic and algebraic characterizations of some Markov processes[END_REF], the author indicates that lim tgo→∞ T tgo exists when G is connected and has a self-loop or a cycle of odd length. Then, in Frieze and Karoński [START_REF] Frieze | Introduction to random graphs[END_REF], the authors show that G is connected, with high probability, when n → ∞ and p ∈ log n n , 1 . Furthermore, we remark that a triangle graph is a cycle of odd length, and, referring to Gilmer and Kopparty [START_REF] Gilmer | A local central limit theorem for triangles in a random graph[END_REF], we remark that the probability of the existence of a triangle subgraph between three vertices of an ER graph is p 3 . This way, with high probability, G has a cycle of odd length, and the only non-zero eigenvalue in lim tgo→∞ V tgo is 1 (we recall that the diagonal of lim tgo→∞ V tgo contains the eigenvalues of lim tgo→∞ T tgo ). As a result, the respective eigenvalue in lim tgo→∞ V tgo -V is 1 -1 = 0.

We assume that the 2-nd largest singular value of T is, with high probability,

O log n √ n , when p ∈ (log n) 2 n , 1 -(log n) 2 n
. We support the assumption by firstly indicating that Frieze and Karoński [START_REF] Frieze | Introduction to random graphs[END_REF] show that, with high probability, the 2-nd largest singular value of the adjacency matrix of an ER random graph is

O( √ n log n), when p ∈ (log n) 2 n , 1 -(log n) 2 n
. (We remark that we were unable to interpret and quantify exactly the high probability of the aforementioned argument, thus leaving it as a future direction.) Secondly, since the expected degree of a vertex of an ER random graph is (n -1)p, we indicate that every element of diag(D

) -1 is O( 1 n ). Since diag(D) -1 is a diagonal matrix, the second largest singular value of T is O( √ n log n)O 1 n = O log n √ n . Hence, with high probability, lim tgo→∞ T tgo -T 2 = O log n √ n , (3.2) when p ∈ (log n) 2 n , 1 -(log n) 2 n .
The second component T -1 np A

2

. We perform the following rearrangement:

T - 1 np A 2 = diag(D) -1 A - 1 np A 2 = diag(D) -1 A - 1 np diag(D)diag(D) -1 A 2 = I - diag(D) np diag(D) -1 A 2 ≤ I - diag(D) np 2 ∥T∥ 2 ≤ max i∈[n] 1 - D i np ∥T∥ 2 ,
where the random value D i is the i-th element of D.

We bound max

i∈[n]
1 -D i np . Since we consider the ER model, we have

1 - D i np = D i n -p = D i n -E D i n .
Let t > 0. By Hoeffding's inequality (Equation 2.4), for each i ∈ [n], we have

Pr D i n -E D i n ≥ t ≤ 2e -2nt 2 ,
which is a bound for 1 -D i np . However, we aim for bounding max

i∈[n]
1 -D i np . By the addition law of probability (Equation 2.2), we have

Pr ∃i ∈ [n], D i n -E D i n ≥ t ≤ i∈[n] Pr D i n -E D i n ≥ t ≤ 2ne -2nt 2 .
Fixing 0 < δ ≪ 1 and t = log(2n/δ) 2n

, we get

Pr ∃i ∈ [n], D i n -E D i n ≥ log(2n/δ) 2n ≤ 2ne -log(2n/δ) = 2ne log(δ/2n) = δ.
Therefore, with probability 1 -δ,

max i∈[n] 1 - D i np < log(2n/δ) 2n ,
which, in terms of n, is similar to a result in the article by G. Chung and Radcliffe [START_REF] Chung | On the Spectra of General Random Graphs[END_REF]. We proceed by the expression of ∥T∥ 2 . As discussed earlier, the largest singular value of an observation of T is 1. Thus, by Equation 2.1, we have ∥T∥ 2 = 1.

Hence, with probability 1 -δ,

T - 1 np A 2 ≤ max i∈[n] 1 - D i np ∥T∥ 2 < log(2n/δ) 2n . (3.3) The third component 1 np A -11 T n 2
. Oliveira [START_REF] Imbuzeiro | Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges[END_REF] shows that for an ER random graph, with probability 1 -δ,

A -p11 T 2 ≤ 4 (n -1)p log(n/δ) < 4 np log(n/δ).
We rearrange the previous result, and thus arrive to the expression where, with probability 1 -δ, we have the following:

1 np A - 11 T n 2 < 4 log(n/δ) np . (3.4)
Composition. We recompose the three components (Equation 3.2, Equation 3.3, and Equation 3.4). Hence, with high probability,

lim tgo→∞ T tgo - 1 T 1 n 2 < O log n √ n + log(2n/δ) 2n + 4 log(n/δ) np = O log n √ n , when p ∈ (log n) 2 n , 1 -(log n) 2 n .
By Theorem 1, we conclude that the spectral norm of the difference between the linear transformation due to the simple gossip algorithm (Algorithm 1) upon convergence and the linear transformation 1 T 1 n is O log n √ n , when the simple gossip algorithm is executed on a graph modeled by the ER model. Also, we remark that the aforementioned spectral norm is an asymptotic guarantee for the error between and the true average of individual values computed by the simple gossip algorithm (Algorithm 1) and the true average of individual values, when the graph of agents is non-regular yet close to a regular graph (as the expected degree of each vertex of a random graph that follows the ER model is the same).

Averaging on arbitrary graphs

In this section, we continue to study the bias between the average of individual values computed by the simple gossip algorithm (Algorithm 1) and the true average of individual values, when the graph G = (V, E) of agents is non-regular, as initially discussed in Subsection 3.1.2 and Section 3.2.

In particular, we prove an asymptotic guarantee for the mean squared error between the average of sensitive attributes and the average of locally privatized attributes computed by a bias-correcting variant of the simple gossip algorithm (Algorithm 1), when the individual values depend on the degrees of the agents, and the degrees are sensitive attributes. Unlike in Section 3.2 where the graph of agents is modeled by the ER model, we consider the case where the graph of agents is modeled by the configuration model (Definition 4). This way, we consider graphs with arbitrary degree sequences. Also, we consider handshake-free interaction (discussed in Section 2.3).

Introduction

In existing works on distributed averaging, it is common to assume a form of handshakes between every two neighboring agents in every exchange of information, i.e., when one agent uses information of a second agent, the second agent becomes aware of this and must actively help the process. However, there exist practical scenarios where such interaction is time consuming due to inactivity of some agents.

To give an illustrative example on handshake-free interaction, let us consider a group of researchers who aim at solving a particular problem. The researchers can follow each other, and thus read each other's currently best strategy in each other's most recently published paper. The researchers work on their solution strategy individually and without necessarily directly contacting each other, attempting to improve their current solution strategies based on their individual skills and the ideas read in the papers of the followed colleagues. At some point, some of them might find a fully satisfactory solution.

We proceed by elaborating on our setting. We model the network of agents by a graph where neighboring agents are connected by edges. Each agent has sensitive attributes, such as its degree, and each agent intends to privatize (add appropriate noise to) its sensitive attributes on its own (without a central curator) before sharing them with other agents. Otherwise, if the sensitive attributes are known, they might be used to profile an agent (e.g., in social media, the connectivity of an agent suggests its popularity).

Our approach for collaboratively computing an unbiased estimate of the average of sensitive attributes has two parts. In the first part, the agents commit to the simple gossip algorithm (Algorithm 1) for distributed averaging. More specifically, each agent hides its sensitive attributes under noise of edge-differential privacy (a standard of data privacy) and makes them visible to the neighbors. Then, each agent repeatedly averages the values revealed by its neighbors and updates the displayed value by the computed average. At some point this converges and the computed averages are biased when the graph is non-regular. In the second part, the agents perform a procedure combining the biased averages for bias correction. The proposed approach is decentralized, handshake-free, and privacy-preserving.

We investigate a use case for the proposed approach, namely, fitting linear regression models while keeping the degrees private. We prove the asymptotic guarantee that the mean squared error (MSE) between the average of privatized attributes computed by our approach and the average of sensitive attributes is O( 1 n ), where n is the number of agents. We show on a synthetic graph dataset that the expected error is sufficiently tight. Also, we show on the synthetic graph dataset and real graph datasets that, when the features are polynomials of degrees, the regression model fitted by our approach can outperform the solution when locally privatized attributes are averaged by centralized averaging (Cen), i.e., the averaging function

f (x) = 1 n i∈[n] x i , where x ∈ R n .
We briefly motivate several elements of our setting. Usually, there are two common forms of information flow [START_REF] Giakkoupis | Tight bounds for rumor spreading in graphs of a given conductance[END_REF]: pulling, where an agent asks its neighboring agent for its value, and pushing, where an agent sends its value to a neighboring agent. In this work, we study a weak form of pulling where an agent obtains the current value of a neighbor without the neighbor being aware of this. In particular, each agent continuously publishes its current values so that its neighbors can obtain them, but there is no other communication (e.g., there is no communication process to build overlay networks [START_REF] Jelasity | T-Man: Gossip-based fast overlay topology construction[END_REF] that can improve distributed computations). We argue that pulling results in a stronger self-management because an agent does not have to wait until another agent disseminates its current values. Since the agents do not exchange handshakes (like in the Transport Layer Security protocol), information dissemination is more robust upon inactive agents. Further, we assume that the degree is sensitive because it can reveal information about the profile of an agent [START_REF] Hay | Accurate Estimation of the Degree Distribution of Private Networks[END_REF][START_REF] Hay | Boosting the Accuracy of Differentially Private Histograms Through Consistency[END_REF]. Finally, we mention that our approach applies for graphs with power-law degree sequences which, as indicated by Zipf's law, are common in real-world (e.g., computer, social, biological) networks.

Outline. In Subsection 3.3.2, we precise our setting. In Subsection 3.3.3, we perform the literature study. In Subsection 3.3.4, we state our approach. In Subsection 3.3.5, we discuss a use case on linear regression. In Subsection 3.3.6, we prove the asymptotic guarantee that the MSE between the average of privatized attributes computed by our approach and the average of sensitive attributes is O( 1 n ). In Subsection 3.3.7, we discuss the experiments on a synthetic graph dataset and real graph datasets. In Subsection 3.3.8, we conclude.

Preliminaries

In this subsection, we precise our setting by describing the communication model and the threat model.

Communication model. We model our network of agents by an undirected graph G = (V, E), where V is the set of vertices and E is the set of edges. We denote the order of the graph by n. We denote the degree of a vertex v by d v . We denote the degree sequence of G by d = (d 1 , d 2 , . . . , d n ). We denote the lowest degree and the highest degree, respectively, by d min and d max . For k ∈ R and x ∈ R n , we denote the k-th raw moment We model G by an observation of a random graph (with fixed vertices and drawn edges) drawn from the configuration model (Definition 4) because the configuration model is parametrized by an arbitrary degree sequence.

We assume that G is connected and has a self-loop or a cycle of odd length because those conditions are necessary for Algorithm 1 to converge. We remark that the connectivity of the configuration model is discussed in Federico and van der Hofstad [START_REF] Federico | Critical Window for Connectivity in the Configuration Model[END_REF]. Then, we remark that a triangle graph is a cycle of odd length, and the count of triangle subgraphs in the configuration model is discussed in Gao et al. [START_REF] Gao | Counting Triangles in Power-Law Uniform Random Graphs[END_REF] Threat model. We assume that the agents are honest-but-curious [Gol04], i.e., all agents follow the established protocols (they are honest), but they try to use the available information to infer sensitive information of other agents (they are curious). We remark that in our setting where agents publish information and can see published information from others but no other communication is possible, it is straightforward to protect against agents which are malicious in the sense they deviate from the protocol in order to obtain more information. Protecting against agents which deviate from the protocol to influence the result of the computation, e.g., by publishing false information, which is also called data poisoning and studied in Sabater et al. [START_REF] Sabater | An accurate, scalable and verifiable protocol for federated differentially private averaging[END_REF], is outside the scope of this work.

We highlight that we use (ϵ, δ)-edge-differential privacy (we recall its definition below). In particular, we use local differential privacy [START_REF] Prasad Kasiviswanathan | What Can We Learn Privately?[END_REF], where privatization noise is added to attributes; we refer to such attributes as sensitive attributes.

Since we consider datasets of graphs, we remark that classic notions of differential privacy for graphs are edge-differential privacy and node-differential privacy [START_REF] Prasad Kasiviswanathan | Analyzing Graphs with Node Differential Privacy[END_REF][START_REF] Hay | Accurate Estimation of the Degree Distribution of Private Networks[END_REF]. In node-differential privacy, adjacent datasets of graphs differ in one vertex and all edges incident with that vertex. In edge-differential privacy, adjacent datasets of graphs differ in one edge. This way, node-differential privacy is, typically, considered as a stronger notion of privacy than edge-differential privacy [START_REF] Taki | It's Too Noisy in Here: Using Projection to Improve Differential Privacy on RDF Graphs[END_REF]. However, as indicated in Wang and Wu [START_REF] Wang | Preserving Differential Privacy in Degree-Correlation based Graph Generation[END_REF], node-differential privacy commonly leads to privatization noise that strongly perturbs privatized attributes. We remark that k-edge-differential privacy [START_REF] Hay | Accurate Estimation of the Degree Distribution of Private Networks[END_REF] is a notion in between edge-differential privacy and node-differential privacy, and under such notion adjacent datasets of graphs differ in k edges.

In this work, we chose to consider edge-differential privacy as opposed to kedge-differential privacy (or node differential privacy) due to the following reasons:

• We consider honest-but-curious agents as our threat model and exclude the threat of collusion among the neighborhood of a particular agent. If the collusion was taken into account, colluding agents would know all the edges of the aforementioned agent and thus would be able to compute its sensitive degree. In our case, each agent knows only one edge of its neighbor. Thus, we consider adjacent datasets of graphs which differ in one edge as opposed to k edges, where such k edges would be known to a set of k colluding agents.

• We consider handshake-free interaction among agents. In such case, an adversary could infer additional information about the size of the neighborhood of a particular agent due to a delay caused to perform a handshake. Thus, we consider adjacent dataset of graphs which differ in one edge as opposed to k edges, where information about such k edges could be inferred if additional k agents sent requests to the agent that is in the process of performing a handshake with the adversary.

• We model the graph of agents by the configuration model (Definition 4) which is parametrized by an arbitrary degree sequence. However, we are mostly interested in graphs with power-law degree sequences, and power-law degree sequences result, typically, in a relatively low average degree of the graph (in our experiments, we will either consider graphs with power-law degree sequences or graphs with a relatively low average degree). This way, we mostly consider cases where the probability of having many subsets of common neighbors is relatively low (i.e., the probability of having many short cycles in a graph is relatively low). As a consequence, it is relatively unlikely that an agent can correctly guess that its two neighbors are also neighbors among themselves.

We recall the definition of edge-differential privacy for graphs by stating it in a similar form as for (ϵ, δ)-differential privacy in Definition 5. A classic strategy to guarantee (ϵ, δ)-differential privacy is to generate noisy values from the Gaussian mechanism (Definition 6). Let G = (V, E) and G ′ = (V, E ′ ) be graphs of adjacent datasets, where e ∈ E and e ̸ ∈ E ′ . For each v ∈ V , let E v and E ′ v denote, respectively, the set of edges incident with v on G and G ′ . Let f be a map from a set of all edges incident with a vertex v to its degree, i.e.,

d v = |E v | = f (E v ) and d ′ v = |E ′ v | = f (E ′ v ).
Based on the global sensitivity discussed in Imola et al. [START_REF] Imola | Locally Differentially Private Analysis of Graph Statistics[END_REF], we recall the l 2 sensitivity of the degree of an agent under local (ϵ, δ)-edge-differential privacy:

∆ 2 (f ) = max v∈V ∥f (E v ) -f (E ′ v )∥ 2 = max v∈V |d v -d ′ v | = |d v -d v -1| = 1.

Literature study

In this subsection, we perform the literature study.

We highlight that we intend to design a communication protocol for distributed averaging, where (i) individual values that depend on the degrees are differentially private, (ii) the averages of individual values are unbiased, (iii) the choice of the degree sequence is arbitrary, (iv) handshakes are absent, and (v) a central curator is absent.

We proceed by discussing some reference works with partial solutions. If the degree was not a sensitive attribute, our problem could be solved by a gossip algorithm that corrects the bias by an application of the Metropolis-Hastings algorithm [START_REF] Hastings | Monte Carlo sampling methods using Markov chains and their applications[END_REF] (as discussed in Subsection 3.1.2). More specifically, in each gossip iteration, an agent could make use of the degrees of its neighbors to correct the bias from each value that is averaged.

If handshakes among agents were allowed, the community could solve the problem by agreeing on an overlay network (a network "built" on top of the initial one). For example, the community could agree on an overlay network that is a regular graph [START_REF] Hua | Efficient and Reliable Overlay Networks for Decentralized Federated Learning[END_REF] (as discussed in Subsection 3.1.1).

There are several gossip algorithms that solve our problem by relying on handshakes or pushing. Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF] requires the agents to agree on an independent edge set (so-called matching). Kempe et al. [START_REF] Kempe | Gossip-Based Computation of Aggregate Information[END_REF] assumes that each agent knows if a sent message failed to reach its destination. Bellet et al. [START_REF] Bellet | Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols[END_REF] assumes that an agent always accepts a message sent to it. In Dellenbach et al. [START_REF] Dellenbach | Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries[END_REF], every two neighbors initialize their communication by sharing a value related to a positive privatization noise for one and a negative privatization noise for other. Ridgley et al. [START_REF] Donato Ridgley | Simple, Private, and Accurate Distributed Averaging[END_REF] explicitly mentions the use of pushing.

We remark that garbled circuits [Gas+17; Nik+13] is an alternative approach based on secure multi-party computation. However, secure multi-party computation results in additional computational cost and involves public-key cryptography which relies on handshakes.

We discuss the reference works that we took as building blocks. Oliveira [Oli09] proves an asymptotic guarantee on the matrix norm between the adjacency matrix of an Erdős-Rényi random graph and its expectation, such guarantee has motivated us to work on a similar idea for graphs with arbitrary degree sequences. Iutzeler et al. [START_REF] Iutzeler | Analysis of Sum-Weight-Like Algorithms for Averaging in Wireless Sensor Networks[END_REF] discusses a gossip algorithm for distributed averaging on graphs with arbitrary degree sequences. Chierichetti et al. [START_REF] Chierichetti | Rumor spreading in social networks[END_REF] considers graph models characterized by power-law degree sequences. Lindell and Pinkas [START_REF] Lindell | Secure Multiparty Computation for Privacy-Preserving Data Mining[END_REF] provides a compendium on privacy-preserving distributed averaging techniques. Aysal et al.

[Ays+09] considers a gossip algorithm that is asynchronous. Bell et al. [START_REF] Bell | Private Protocols for U-Statistics in the Local Model and Beyond[END_REF] fits a regression model using unbiased averages which are computed in a distributed manner.

Approach

In this subsection, we firstly briefly discuss the simple gossip algorithm (Algorithm 1), where in later references the simple gossip algorithm is shorthanded by SiGo. Then, we state a theorem illustrating that SiGo results in biased averages when the graph G of agents is non-regular. Afterwards, we design a strategy for bias correction.

In SiGo (Algorithm 1), the transition matrix T is defined using the adjacency matrix A, which indicates that the averaging by SiGo is synchronous. However, Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF] indicates that, upon convergence, SiGo provides the same output when executed asynchronously. Regarding the convergence of SiGo (the elements of the output vector z become equal), Kermarrec and van Steen [START_REF] Kermarrec | Gossiping in distributed systems[END_REF] indicates that, in general, t go = ⌈log n⌉ is sufficient when log n is approximately the diameter of G and when the degree sequence d follows a power-law distribution.

We state a theorem for the value of each element of the output z of SiGo, when SiGo converges: Theorem 2. Let A be the adjacency matrix of a graph G of order n. Let d be the degree sequence of G. Let w ∈ R n . Let SiGo (A, t go , w) denote any element of the output z of Algorithm 1. We have

lim tgo→∞ SiGo (A, t go , w) = 1 n 1 µ d i∈[n] d i w i , (3.5)
when G is connected and has a self-loop or a cycle of odd length.

In later references, SiGo (w) shorthands lim tgo→∞ SiGo (A, t go , w).

Proof. In this proof, we expand lim tgo→∞ T tgo w, where

T = diag(d) -1 A
is the transition matrix of SiGo (Algorithm 1), and where w ∈ R n contains the values that are intended to be averaged. Even though T is not symmetric (it is a row stochastic matrix), we can define the matrix

X = diag(d) 1/2 Tdiag(d) -1/2 ,
similarly as in the article by G. Chung and Radcliffe [START_REF] Chung | On the Spectra of General Random Graphs[END_REF]. This way, X is symmetric.

Both T and X have a largest singular value 1, which has multiplicity 1 if G is connected, and this suggests that T1 = 1 is an eigenvector of T, which is paired with the eigenvalue 1. Similarly,

Xdiag(d) 1/2 1 = diag(d) 1/2 1
is an eigenvector of X, which is paired with the eigenvalue 1. We normalize the aforementioned eigenvector so that its elements sum to 1:

v 1 = diag(d) 1/2 1 √ nµ d .
Since X is symmetric, it has real eigenvalues and orthogonal eigenvectors. Let UΛU T be the eigendecomposition of X, where Λ is a diagonal matrix of eigenvalues in decreasing order, implying Λ 1,1 = 1. This way, we have U :,1 = v 1 .

Let I n denote the n × n identity matrix. We derive the limit when the elements of w are iteratively averaged using T:

lim tgo→∞ T tgo w = lim tgo→∞ diag(d) -1/2 Xdiag(d) 1/2 tgo w = lim tgo→∞ diag(d) -1/2 X tgo diag(d) 1/2 w = lim tgo→∞ diag(d) -1/2 UΛ tgo U T diag(d) 1/2 w = diag(d) -1/2 Udiag(1, 0, . . . , 0)U T diag(d) 1/2 w = diag(d) -1/2 v 1 v T 1 diag(d) 1/2 w = diag(d) -1/2 diag(d) 1/2 1 √ nµ d 1 T diag(d) 1/2 √ nµ d diag(d) 1/2 w = 1 nµ d I n 11 T diag(d)w = 1 nµ d 11 T diag(d)w = 1 1 n 1 µ d i∈[n] d i w i ,
where lim tgo→∞ Λ tgo exists when the graph is connected and has a self-loop or a cycle of odd length, as indicated by Paz [START_REF] Paz | Graph-theoretic and algebraic characterizations of some Markov processes[END_REF], and the second largest singular value of Λ is lower than 1, as indicated by Banerjee and Mehatari [START_REF] Banerjee | An eigenvalue localization theorem for stochastic matrices and its application to Randić matrices[END_REF]. Hence, when SiGo converges, every element of the output z of SiGo (Algorithm 1) is 1 n

1 µ d i∈[n] d i w i .
Theorem 2 indicates that the resulting average is biased by µ d and

d i (for each i ∈ [n]), when d i ̸ = µ d (i.e., G is non-regular).
That is, the squared difference between any element of the output of SiGo (w) and

µ w = 1 n i∈[n] w i is non-zero: SiGo (w) -µ w 2 =   1 n 1 µ d i∈[n] d i w i -µ w   2 (by Theorem 2) = µ d.w µ d -µ w 2 . (3.6)
Bias correction. We provide a procedure to correct the bias illustrated by Equation 3.6. We start by an example where the community computes an unbiased estimate of µ w from two gossiping runs. Firstly, Sigo is executed (sequentially or in parallel) with the respective inputs (w i d -1 i ) n i=1 and (d -1 i ) n i=1 :

SiGo (w i d -1 i ) n i=1 = 1 n 1 µ d i∈[n] w i (by Theorem 2) = µ w µ d , SiGo (d -1 i ) n i=1 = 1 n 1 µ d i∈[n] 1 = 1 µ d . (3.7)
Then, the community can compute

SiGo (w i d -1 i ) n i=1 SiGo (d -1 i ) n i=1 = µ w . (3.8)
By Theorem 2, we generalize Equation 3.8 and thus define the bias-correcting gossip algorithm (BCGo):

SiGo (w i d -1 i ) n i=1 SiGo (d -1 i ) n i=1 = 1 n 1 µ d i∈[n] d i (w i d -1 i ) 1 n 1 µ d i∈[n] d i (d -1 i ) = 1 n i∈[n] w i = µ w .
(3.9)

We illustrate an example of applying BCGo for computing the order n of a graph G, when G is connected and has a cycle of odd length. Similarly as in the example given after recalling SiGo (Algorithm 1), we assign a label 1 to one agent, and a label 0 to the remaining n -1 agents. When BCGo converges, each agent computes the average 1+0+...+0 n = 1 n (Equation 3.9). By taking the reciprocal of 1 n , each agent computes n.

We highlight that unbiased averages can be generalized by U-statistics (Definition 1). This way, the estimates obtained by BCGo (Equation 3.9) are U-statistics with kernel ϕ : x → x of degree 1. U-statistics of degree 1 are present in machine learning applications, for example, in classic strategies for fitting linear regression models, as discussed in Subsection 3.3.5, bootstrap aggregation in random forests, as discussed in Peng et al. [START_REF] Peng | Rates of convergence for random forests via generalized U-statistics[END_REF], and gradient descent in training artificial neural networks, as discussed in McMahan et al. [START_REF] Mcmahan | Communication-Efficient Learning of Deep Networks from Decentralized Data[END_REF]

Use case on linear regression

In this subsection, we investigate a use case for the proposed approach, namely, fitting a linear regression model while keeping the degrees private, where each agent is assigned one labeled example, and the features depend on the degrees. Firstly, we define a multiple linear regression model whose features are powers of the degrees. Then, we show that the regression model can be fitted from averages. Afterwards, we discuss the privatization and the bounding of powers of the degrees. Finally, we provide the pseudo-code for fitting the multiple linear regression model by regularized least squares and when averaging the privatized attributes by BCGo (Equation 3.9).

Let m ∈ N. We define a special case of a multiple linear regression model (defined in Equation 2.8) with m + 1 regression parameters and a scalar target value. For each i ∈ [n],

y i = θ 0 + θ 1 d k 1 i + . . . + θ m d km i + ξ reg i , (3.10)
where θ 0 , θ 1 , . . . , θ m ∈ R are regression parameters,

d k 1 i , d k 2 i , . . . , d km i ∈ R are features (k 1 , k 2 , . . . , k m ∈ R \ {0}), y i is a target value, ξ reg i
is regression noise which is an independent observation of N (0, σ 2 reg ), and σ 2 reg is the variance of regression noise. We remark that, while BCGo (Equation 3.9) can compute averages for fitting regression models with arbitrary features, we focus on the multiple linear regression model defined in Equation 3.10 because in this work we limit ourselves to privatization noise for the features that depend on powers of the degrees.

As a consequence, we remark that polynomials of arbitrary degree can approximate other functions (e.g., the logarithm, trigonometric functions, etc.) using the Taylor series (which are discussed in detail in Canuto and Tabacco [START_REF] Canuto | [END_REF]). This way, our regression model can approximate linear regression models with a broad class of features. Regarding the practical applicability of such regression models, we provide a reference to the linear regression datasets that are part of the NIST Standard Reference Database (accessible on itl.nist.gov/div898/strd/lls/l ls.shtml).

Let X = 1 x 1 . . . x m ∈ R n×(m+1) , where x 1 , x 2 , . . . , x m are feature vectors. Let y be a vector of target values. We fit the regression model defined in Equation 3.10 by regularized least squares (discussed in Subsection 2.4.1). That is, referring to Equation 2.9, we compute the vector θ of parameter estimates as follows:

θ = 1 n X T X + λI m+1 -1 1 n X T y, (3.11) where 1 n X T X =       1 1 n i∈[n] d k 1 i . . . 1 n i∈[n] d km i 1 n i∈[n] d k 1 i 1 n i∈[n] d 2k 1 i . . . 1 n i∈[n] d k 1 i d km i . . . . . . . . . . . . 1 n i∈[n] d km i 1 n i∈[n] d k 1 i d km i . . . 1 n i∈[n] d 2km i       =      1 µ d k 1 . . . µ d km µ d k 1 µ d 2k 1 . . . µ d k 1 .d km . . . . . . . . . . . . µ d km µ d k 1 .d km . . . µ d 2km      , (3.12) 1 n X T y = 1 n i∈[n] y i 1 n i∈[n] y i d k 1 i . . . 1 n i∈[n] y i d km i T = µ y µ y.d k 1 . . . µ y.d km T , (3.13)
and where λ ∈ R is the regularization parameter, and I m+1 is the (m + 1) × (m + 1) identity matrix. We highlight that the parameter estimates θ are computed from the averages

µ d k 1 , µ d k 2 , . . . , µ d km , µ d 2k 1 , µ d 2k 2 , . . . , µ d 2km , µ d k 1 .d k 2 , µ d k 1 .d k 3 , . . . , µ d k m-1 .d km , µ y.d k 1 , µ y.d k 2 , .
. . , µ y.d km , and µ y (2m + m(m-1) 2 + m + 1 of averages in total). By Definition 1, the aforementioned averages are U-statistics of degree 1.

We assume that d min and d max are known. For k ∈ R \ {0}, we privatize d k i using the Gaussian mechanism (Definition 6) as follows:

D dp i,k ∼ N d k i , (σ dp k ) 2 , (3.14) σ dp k = 2 log(1.25/δ ′ )∆ 2 (d k i ) ϵ ′ , (3.15)
where (ϵ ′ , δ ′ ) is an even split of the total privacy budget (ϵ, δ) and, as adjacent datasets of graphs differ in one edge (Definition 8), we have

∆ 2 (d k i ) = max d∈[d min ,dmax-1] (d + 1) k -d k =      d k min -(d min + 1) k when k < 0, (d min + 1) k -d k min when 0 < k < 1, d k max -(d max -1) k when k ≥ 1. (3.16)
We remark that we do not consider the privatization of the power 0 of a degree because it always equals 1 and thus is non-sensitive (it no longer depends on the degree).

Remark 1. A privatized attribute d dp i,k is an independent observation of D dp i,k (Equation 3.14). Upon BCGo, privatization of

d k 1 -1 i , d k 2 -1 i , . . . , d km-1 i is independent from d -1 i , d i . For clarity, privatized d -1 i , d i are denoted, respectively, by d dp i,-1 ′ , d dp i,1 ′ .
We highlight that we privatize the transformed degree d k i , as opposed to privatizing d i and then computing (d dp i ) k . This is done in order to mitigate the risk of d dp i being too close to the singularity at the value 0 when k < 0. If d dp i is close to 0, then the feature (d dp i ) k would be an outlier disturbing the prediction accuracy of the fitted regression model.

We proceed by discussing the bounds for each privatized attribute d dp i,k so that it stays centred at d k i (preserves unbiasedness). Let

a i = min(d k i -d k max , d k min -d k i ) when k < 0, min(d k i -d k min , d k max -d k i ) when k > 0.
This way, we have the following bounds:

d k i -a i ≤ d dp i,k ≤ d k i + a i .
(3.17)

Remark 2. If a privatized attribute d dp i,k is outside the bounds (Equation 3.17), it is resampled uniformly in the interval

[d k i -a i , d k i + a i ].
We highlight that, upon BCGo, the sensitive attributes of an agent i are

d k 1 -1 i , d k 2 -1 i , . . . , d km-1 i , d -1
i , d i (m + 2 in total). Similarly, upon Cen, the sensitive attributes are d k 1 i , d k 2 i , . . . , d km i (m in total). We leave the following remarks on the privacy guarantees for locally privatizing and then averaging the aforementioned powers of the degrees:

• We assume that d min and d max are known. This way, each agent can compute the l 2 sensitivity (Equation 3.16) for local privatization using the Gaussian mechanism (Definition 6). We recall that the Gaussian mechanism ensures (ϵ, δ)-differential privacy.

• We assume that each agent knows only its own edges, and not edges between other vertices. For example, such assumption mitigates the previously discussed threat of collusion among the neighborhood of a particular agent. Thus, the value of the degree of a particular vertex can not be deduced from a set of edges incident to that vertex.

• We assume that the computation of the average of locally privatized attributes is under a sufficiently low precision (i.e., some rounding happens). In other words, the probability of observing any possible (rounded) average should remain sufficiently high. For example, such assumption mitigates the threat of an adversary learning additional information about the topology of the communication network, when the adversary is connected to all the agents and when the adversary observes subsequent averaging. This way, revealed functions (i.e., averages) of locally privatized attributes (i.e., powers of the degrees) remain differentially private.

• Referring to Sei and Ohsuga [START_REF] Sei | Private True Data Mining: Differential Privacy Featuring Errors to Manage Internet-of-Things Data[END_REF], we assume that target values are nonsensitive. Even though a target value y i (Equation 3.10) is a linear combination of powers of the degree, the exact values of the regression parameters and the regression noise remain unknown, thus the value of the degree can not be deduced.

• Referring to the composition theorem in Dwork and Roth [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF], privatization of the sensitive attributes upon even splits of the total privacy budget (ϵ, δ) lead to (ϵ, δ)-differential privacy.

• If a privatized attribute is outside the bounds (Equation 3.17), we resample it uniformly, while uniform sampling is (0, 0)-differentially private.

In Algorithm 4, we provide the pseudo-code for fitting the multiple linear regression model by regularized least squares (Equation 3.12 and Equation 3.13) and when averaging the privatized attributes by BCGo (Equation 3.9). Algorithm 4: BiasCorrectingGossip (BCGo) for privacy-preserving regression /* Privatization (Remark 1) and bounding (Remark 2) */

1 ϵ ′ , δ ′ ← ϵ m+2 , δ m+2
2 for i ∈ [n] do 3 for j ∈ [m] do 4 d dp i,k j -1 ← privatizeAndBound(d k j -1 i , ϵ ′ , δ ′ ) 5 for k ∈ {-1 ′ , 1 ′ } do 6 d dp i,k ← privatizeAndBound(d k i , ϵ ′ , δ ′ ) /* Averaging by BCGo (Equation 3.9) */ 7 μy = SiGo((y i d dp i,-1 ) n i=1 ) SiGo (d dp i,-1 ′ ) n i=1 8 for j ∈ [m] do 9 μd k j , μd 2k j , μy.d k j ← SiGo (d dp i,k j -1 ) n i=1 SiGo (d dp i,-1 ′ ) n i=1 , SiGo ((d dp i,k j -1 ) 2 d dp i,1 ′ ) n i=1 SiGo (d dp i,-1 ′ ) n i=1 , SiGo (y i d dp i,k j -1 ) n i=1 SiGo (d dp i,-1 ′ ) n i=1 10 for j ′ ∈ {j, . . . , m -1} do 11 μd k j .d k j ′ = SiGo (d dp i,k j -1 d dp i,k j ′ -1 d dp i,1 ′ ) n i=1 SiGo (d dp i,-1 ′ ) n i=1
/* Fitting by regularized least squares (Equation 3.11) */

12 θ ← fit(μ y , μd k 1 , . . . , μd 2k 1 , . . . , μy.d k 1 , . . . , μd k 1 .d k 2 , . . . , λ)
The pseudo-code in Algorithm 4 consists of the following three parts. In the first part, we privatize and bound powers of the degrees (the corresponding privacy guarantees are discussed in the list above). In the second part, we execute SiGo (Algorithm 1) on several functions whose arguments are locally privatized attributes and target values; such revealed functions remain differentially private because they do not reveal sensitive attributes. In the third part, each agent simply performs regularized least squares (Equation 3.11), which does not reveal sensitive attributes neither.

Error analysis

In this subsection, we define the expected errors between the average (e.g., µ d k 1 in Equation 3.12) of sensitive attributes and the average of privatized attributes computed, respectively, by Cen and BCGo (Equation 3.9). Then, we discuss the conditions when the average computed by BCGo results in less privatization noise compared to the average computed by Cen. Finally, we define the respective empirical errors for evaluating the aforementioned expected errors.

Let k ∈ R\{0}. We define the average (k-th raw moment) of sensitive attributes:

s k = µ d k = 1 n i∈[n] d k i . (3.18)
We define the averages of privatized attributes (Equation 3.14) computed, respectively, by Cen and BCGo:

S Cen k = 1 n i∈[n] D dp i,k , (3.19)
S BCGo k = SiGo (D dp i,k-1 ) n i=1 SiGo (D dp i,-1 ) n i=1 . (3.20)
We highlight that our error analysis is limited to sensitive attributes that are powers (excluding the power 0) of the degrees. Otherwise, the error analysis would be more complex because the numerator of Equation 3.9 would include the multiplication between the following two terms with privatization noise: the privatized w i and the privatized d -1 i . Expected errors. We define the expected error between the average (Equation 3.18) of sensitive attributes and the average (Equation 3.19) of privatized attributes computed by Cen:

e Cen k = E s k -S Cen k 2 , (3.21)
We state a theorem (a folklore result on the expected value of the squared average of Gaussian random variables) quantifying the expected error e Cen k (Equation 3.21).

Theorem 3. We have

e Cen k = 1 n (σ dp k ) 2 , (3.22)
where σ dp k is given in Equation 3.15. This way, e Cen k = O 1 n . Proof. We intend to expand e Cen k . We start as follows:

e Cen k = E s k -S Cen k 2 (by Eqn 3.21) = E µ d k -S Cen k 2 (by Eqn 3.18) = µ 2 d k -2µ d k E S Cen k + E S Cen k 2 . (3.23)
Then, we derive

E[S Cen k ] = E   1 n i∈[n] D dp i,k   (by Eqn 3.19) = 1 n i∈[n] E D dp i,k = 1 n i∈[n] d k i (by Eqn 3.14) = µ d k , (3.24) var S Cen k = var   1 n i∈[n] D dp i,k   (by Eqn 3.19) = 1 n 2 var   i∈[n] D dp i,k   = 1 n 2 i∈[n] var D dp i,k = 1 n (σ dp k ) 2 .
(by Eqn 3.15) (3.25)

Further, for a random variable Z, we state an identity:

E[Z 2 ] = var (Z) + E 2 [Z]. (3.26)
We continue the derivation in Equation 3.23:

e Cen k = µ 2 d k -2µ d k E S Cen k + var S Cen k + E 2 [S Cen k ] (by Eqn 3.26) = µ 2 d k -2µ 2 d k + 1 n (σ dp k ) 2 + µ 2 d k (by Eqn 3.25, Eqn 3.24) = 1 n (σ dp k ) 2 . (3.27)
Hence, we conclude that e Cen

k = O( 1 n ).
We define the expected error between the average (Equation 3.18) of sensitive attributes and the average (Equation 3.20) of privatized attributes computed by BCGo:

e BCGo k = E s k -S BCGo k 2 .
(3.28)

We provide a theorem quantifying the expected error e BCGo k (Equation 3.28) for the non-asymptotic case.

Theorem 4. Let 1 n µ d 2 µ 2 d (σ dp -1 ) 2 ̸ = 0 and 1 µ d -3 1 √ n √ µ d 2 µ d σ dp -1 > 0,
e BCGo k ≈ µ 2 d k -2 µ 2 d k µ d √ n √ 2µ d √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 + 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k µ 2 d n µ 2 d µ d 2 (σ dp -1 ) 2 √ n √ 2 √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 -1 , (3.29)
where f daw (x) = e -x 2 x 0 e t 2 dt. (The approximation is due to the absence of closedform expressions for the mean and the variance of the reciprocal of a Gaussian random variable, and the quantification of the approximation error is outside the scope of this work.) Proof. We intend to expand e BCGo k . We start as follows:

e BCGo k = E s k -S BCGo k 2 (by Eqn 3.28) = s 2 k + E S BCGo k 2 -2s k E S BCGo k = s 2 k + E SiGo (D dp i,k-1 ) n i=1 2 E     1 SiGo (D dp i,-1 ) n i=1   2   -2s k E SiGo (D dp i,k-1 ) n i=1 E   1 SiGo (D dp i,-1 ) n i=1   (by Eqn 3.20) = s 2 k + E     1 n 1 µ d i∈[n] d i D dp i,k-1   2   E   1 1 n 1 µ d i∈[n] d i D dp i,-1 2   (by Thm 2) -2s k E   1 n 1 µ d i∈[n] d i D dp i,k-1   E 1 1 n 1 µ d i∈[n] d i D dp i,-1 . (3.30)
Then, we express We use two heuristics for a Gaussian random variable Z with mean µ and variance σ 2 . That is, when µ ̸ = 0, σ ̸ = 0, and |µ| -3σ > 0, with high probability,

E   1 n 1 µ d i∈[n] d i D dp i,k-1   = 1 n 1 µ d i∈[n] d i E D dp i,k-1 = µ d k µ d , (by Eqn 3.14) (3.31) var   1 n 1 µ d i∈[n] d i D dp i,k-1   = 1 n 2 1 µ 2 d i∈[n] d 2 i var D dp i,k-1 = 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 . (by Eqn 3.15) (3.32) Thus, E     1 n 1 µ d i∈[n] d i D dp i,k-1   2   = var   1 n 1 µ d i∈[n] d i D dp i,k-1   + E 2   1 n 1 µ d i∈[n] d i D dp i,k-1   (by Eqn 3.26) = 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k
E 1 Z ≈ √ 2 σ f daw µ √ 2σ , (3.34) E 1 Z 2 ≈ 1 σ 2 µ √ 2 σ f daw µ √ 2σ -1 , (3.35)
where f daw (x) = e -x 2 x 0 e t 2 dt is the Dawson function. Peng [START_REF] Peng | The first negative moment in the sense of the Cauchy principal value[END_REF] shows that Equation 3.34 holds in the Cauchy principal value. When µ = 0.9 and σ = 0.1, Monte Carlo simulations (with 10 8 instances) provided on stats stack exchange st ats.stackexchange.com/q/535924 indicate that the approximations in Equation 3.34 and Equation 3.35 are tight, respectively, within factor 10 -4 and factor 10 -3 .

When 1 µ d ̸ = 0, 1 √ n √ µ d 2 µ d σ dp -1 ̸ = 0, 1 µ d -3 1 √ n √ µ d 2 µ d σ dp -1 > 0, with high probability, E 1 1 n 1 µ d i∈[n] d i D dp i,-1
(by Eqn 3.34, Eqn 3.31, Eqn 3.32)

≈ √ 2 1 n µ d 2 µ 2 d (σ dp -1 ) 2 f daw   1 µ d √ 2 1 n µ d 2 µ 2 d (σ dp -1 ) 2   = √ n √ 2µ d √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 , (3.36) E   1 1 n 1 µ d i∈[n] d i D dp i,-1 2   (by Eqn 3.35, Eqn 3.31, Eqn 3.32) ≈ 1 1 n µ d 2 µ 2 d (σ dp -1 ) 2   1 µ d √ 2 1 n µ d 2 µ 2 d (σ dp -1 ) 2 f daw   1 µ d √ 2 1 n µ d 2 µ 2 d (σ dp -1 ) 2   -1   = n µ 2 d µ d 2 (σ dp -1 ) 2 √ n √ 2 √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 -1 . (3.37)
We continue the derivation in Equation 3.30:

e BCGo k = s 2 k -2s k µ d k µ d E 1 1 n 1 µ d i∈[n] d i D dp i,-1
(by Eqn 3.31)

+ 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k µ 2 d E   1 1 n 1 µ d i∈[n] d i D dp i,-1 2   (by Eqn 3.33) (3.38) ≈ s 2 k -2s k µ d k µ d √ n √ 2µ d √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1
(by Eqn 3.36, Eqn 3.37)

+ 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k µ 2 d n µ 2 d µ d 2 (σ dp -1 ) 2 √ n √ 2 √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 -1 = µ 2 d k -2 µ 2 d k µ d √ n √ 2µ d √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1
(by Eqn 3.18)

+ 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k µ 2 d n µ 2 d µ d 2 (σ dp -1 ) 2 √ n √ 2 √ µ d 2 σ dp -1 f daw √ n √ 2µ d 2 σ dp -1 -1 . (3.39)
The quantification of the approximation error is outside the scope of this work.

We provide a theorem quantifying the expected error e BCGo k (Equation 3.28) for the asymptotic case.

Theorem 5. Let 1 n µ d 2 µ 2 d (σ dp -1 ) 2 ̸ = 0 and 1 µ d -3 1 √ n √ µ d 2 µ d σ dp -1 > 0,
E 1 1 n 1 µ d i∈[n] d i D dp i,-1 = µ d and var 1 1 n i∈[n] d i D dp i,-1 = O( 1 n ).
(We support the assumptions in the proof.) With high probability,

e BCGo k = µ d 2 n (σ dp k-1 ) 2 + µ d 2 n (σ dp k-1 ) 2 var 1 1 n i∈[n] d i D dp i,-1 + µ d k var 1 1 n i∈[n] d i D dp i,-1 , (3.40)
where D dp i,-1 is given in Equation 3.14. This way, e BCGo

k = O 1 n . Proof. When 1 √ n √ µ d 2 µ d σ dp -1 ̸ = 0 and 1 µ d -3 1 √ n √ µ d 2 µ d σ dp -1 > 0, we assume that E 1 1 n 1 µ d i∈[n] d i D dp i,-1 = µ d . (3.41)
We support the aforementioned assumption by the result that

1 1 n 1 µ d i∈[n] d i d -1 i = µ d
and by the evidence discussed in the proof of Theorem 4 that the approximation (Equation 3.34) of the reciprocal of a Gaussian random variable with mean µ and variance σ 2 is tight (when µ ̸ = 0, σ ̸ = 0, and |µ| -3σ > 0). This way,

E   1 1 n 1 µ d i∈[n] d i D dp i,-1 2   = µ 2 d + var 1 1 n 1 µ d i∈[n] d i D dp i,-1
.

(by Eqn 3.26, Eqn 3.41) (3.42)

We continue the derivation in Equation 3.38:

e BCGo k = µ 2 d k -2µ 2 d k + 1 n µ d 2 µ 2 d (σ dp k-1 ) 2 + µ 2 d k µ 2 d µ 2 d + var 1 1 n 1 µ d i∈[n] d i D dp i,-1
(by Eqn 3.18, Eqn 3.41, Eqn 3.42)

= µ d 2 n (σ dp k-1 ) 2 + µ d 2 n (σ dp k-1 ) 2 var 1 1 n i∈[n] d i D dp i,-1 + µ d k var 1 1 n i∈[n] d i D dp i,-1 . (3.43)
We assume that var

1 1 n i∈[n] d i D dp i,-1 = O 1 n , when 1 √ n √ µ d 2 µ d σ dp -1 ̸ = 0 and 1 µ d - 3 1 √ n √ µ d 2 µ d σ dp -1 > 0.
We support the aforementioned assumption by the conditions for the heuristic in Equation 3.35 and by the result that the variance of the squared average of n independent and identically distributed random variables is n times lower than the variance of a single such random variable (as suggested in Equation 3.25).

Hence, we conclude that e BCGo

k = O( 1 n ).
We proceed by discussing the conditions when the average computed by BCGo results in less privatization noise compared to the average computed by Cen. We define the ratio between e BCGo

e BCGo k e Cen k = µ d 2 (σ dp k-1 ) 2 (σ dp k ) 2 + µ d 2 (σ dp k-1 ) 2 var 1 1 n i∈[n] d i D dp i,-1 (σ dp k ) 2 + nµ d k var 1 1 n i∈[n] d i D dp i,-1 (σ dp k ) 2 . (3.44)
We assume that var

1 1 n i∈[n] d i D dp i,-1 = O 1 n , when 1 √ n √ µ d 2 µ d σ dp -1 ̸ = 0 and 1 µ d - 3 1 √ n √ µ d 2
µ d σ dp -1 > 0 (supported in the proof of Theorem 5). This way, the first term and the third term in Equation 3.44 are dominant when n → ∞, i.e., the first term and the third term are O(1) whereas the second term is O( 1 n ). We can expand the first term in Equation 3.44:

µ d 2 (σ dp k-1 ) 2 (σ dp k ) 2 = µ d 2 2 log 5(m+2) 4δ ′ ∆ 2 (d k-1 i ) 2 ϵ ′ /(m + 2) 2 2 log 5m 4δ ′ ∆ 2 (d k i ) 2 (ϵ ′ /m) 2 = m m + 2 2 log 5(m+2) 4δ ′ log 5m 4δ ′ µ d 2 ∆ 2 (d k-1 i ) ∆ 2 (d k i ) 2 . (3.45)
We conjecture that, in the non-asymptotic case, e BCGo k < e Cen k (Equation 3.44 is lower than 1) requires the following conditions: the number m of sensitive attributes is high (Equation 3.45 is lower), the number n of vertices is high (the second term and the third term in Equation 3.44 are lower), the degrees d are low (µ d 2 and µ d k in Equation 3.44 are lower), and k ≥ 2 (but remains low due to µ d k in Equation 3.44) as, in Equation 3.45, we have

∆ 2 (d k-1 i ) ∆ 2 (d k i ) = d k-1 max -(d max -1) k-1 d k max -(d max -1) k
(by Equation 3.16)

< 1. (3.46)
To summarize, we highlight that

∆ 2 (d k-1 i ) ∆ 2 (d k i ) < 1 suggests that we can have e BCGo k < e Cen
k , i.e., the average computed by BCGo can have less privatization noise compared to the average computed by Cen.

Empirical errors. We define the empirical errors that correspond to the expected errors stated, respectively, in Theorem 3 and Theorem 4:

êCen k =   1 n i∈[n] d k i - 1 n i∈[n] d dp i,k   2 , (3.47) êBCGo k =   1 n i∈[n] d k i - SiGo (d dp i,k-1 ) n i=1 SiGo (d dp i,-1 ) n i=1   2 , (3.48)
where d dp i,k is given in Remark 1. We remark that the empirical errors are stated with the intention to evaluate the corresponding expected errors, which is done Subsection 3.3.7.

Experiments

In this subsection, we specify two sets of experiments and interpret the results.

Experiment 3.1. We compare the accuracy of the averages of privatized attributes computed, respectively, by BCGo (Equation 3.9) and Cen. Secondly, we evaluate if the expected errors (Equation 3.22 and Equation 3.29) are tight (within factor of 10 to their empirical counterparts in Equation 3.47 and Equation 3.48) when n ranges from 10 2 to 10 4 and ϵ = 2 2 . Thirdly, we evaluate if the expected errors decrease linearly in n (as indicated by Theorem 5). Experiment 3.2. We compare the utility of the regression models (Equation 3.10) fitted, respectively, using the averages computed by BCGo (Equation 3.9), SiGo (Algorithm 1), and Cen. In particular, we evaluate the MSE between true target values and predicted target values (of a test set of size 10 3 ) when ϵ ranges from 2 -6 to 2 10 . Usually, ϵ > 10 is too high for privacy in practice [START_REF] Hsu | Differential Privacy: An Economic Method for Choosing Epsilon[END_REF].

We use a special case of the regression model given by Equation 3.10. That is, for each i ∈ [n],

y i = θ 0 + θ 1 d -1 i + θ 2 d 1/2 i + θ 3 d 2 i + ξ reg i , (3.49)
where θ 1 is coupled with a decreasing feature, θ 2 is coupled with a slower than linearly increasing feature, and θ 3 is coupled with a quicker than linearly increasing feature (this covers the three sensitivities in Equation 3.16), and where regression noise ξ reg i is drawn independently from N (0, 1). We fix the regression parameters to θ 0 = θ 1 = θ 2 = θ 3 = 1 to generate synthetic regression datasets. We fix the regularization parameter to λ = 1.

Our synthetic graph dataset is created by generating a power-law degree sequence with the shape parameter fixed to γ = 2 (discussed in Section A.1) and generating a graph from the configuration model (Definition 4). For real graph datasets, we use the graphs of the email-Eu-core network dataset (1005 vertices and 25571 edges) and the autonomous systems AS-733 dataset (6474 vertices and 13895 edges), both of which are part of SNAP [START_REF] Leskovec | SNAP Datasets: Stanford Large Network Dataset Collection[END_REF]. We have processed the real graph datasets by Step 3 of the procedure described in Section A.1 and have removed self-loops.

We precise the experiment setup:

• We fix δ = 1 n 2
, where such choice is also used in Near et al. [START_REF] Near | Duet: an expressive higher-order language and linear type system for statically enforcing differential privacy[END_REF] We fix the lowest degree to d min = 3 and the highest degree to d max = 10 2 . We fix the number of gossip iterations to t go = 2 10 .

• In Experiment 3.1, we normalize the errors dividing them by (σ dp k ) 2 (Equation 3.15). In Experiment 3.2, we normalize the MSE between true target values and predicted target values dividing it by (σ y ) 2 , where σ y is the standard deviation of true target values, similarly as in Gupta and Kling [START_REF] Vijai | On typical range, sensitivity, and normalization of Mean Squared Error and Nash-Sutcliffe Efficiency type metrics[END_REF].

• We fix the number of experiment repetitions to t exp = 2 10 . For the synthetic dataset, in each experiment repetition we generate a degree sequence and a graph. For Experiment 3.2, in each experiment repetition we generate privatized features and target values for fitting, and a test set of size 10 3 which contains target values assigned to an independently generated synthetic graph of order 10 3 for evaluating the real graph datasets. In Experiment 3.1, each privatized attribute d dp i,-1 ′ (Remark 1) is bounded (Equation 3.17) so that the conditions for the expected error (Equation 3.29) hold. This way, σ dp -1 in Equation 3.29 is substituted with an approximated variance (discussed in Section A.2) of a bounded d dp i,-1 ′ . In Experiment 3.2, the privatized attributes are bounded to improve the utility of the regression models fitted, respectively, using the averages computed by BCGo, SiGo, and Cen.

• We fix the significance level α ci = 0.05 (the computation of confidence intervals is described in Equation 2.5).

In Section A.4, we discuss secondary experiments.

Results. The experiments were run on a machine with an Intel E5-2643 processor (3.30 GHz) and 192 GB of RAM; for the synthetic dataset, this took 3 hours. Similarly, for the email network dataset this took 1 hour and for the autonomous systems dataset this took 9 hours. The most time consuming operation is the matrix power in Algorithm 1. The storage is mostly affected by the adjacency matrix of the graph; we remark that in our implementation we store the adjacency matrix in a sparse matrix. Our implementation is inappropriate when n ≥ 10 5 because Algorithm 1 is a centralized simulation of distributed averaging. For the study of Algorithm 1 on graphs whose order is n ≥ 10 5 , we suggest implementing Algorithm 1 in a distributed manner.

Conclusion

We have proved an asymptotic guarantee (Theorem 5) for the MSE between the average of sensitive attributes and the average of locally privatized attributes computed by the bias-correcting gossip algorithm (Equation 3.9), when the graph of agents is modeled by the configuration model (Definition 4), when the degrees of agents are sensitive, and when the agents interact without handshakes.

Equation 3.44 indicates that distributed averaging performed by the biascorrecting gossip algorithm BCGo can result in less privatization noise in comparison to the averaging function f (x) = 1 n i∈ [n] x i (where x ∈ R n ), when we compute U-statistics (Definition 1) of degree 1 from locally privatized degrees raised to a power k = 2, and when the graph has low degrees (i.e., when the 2-nd raw moment µ d 2 and the k-th raw moment µ d k of the degrees in Equation 3.44 are low).

We remark that the privatization of degrees by the Gaussian mechanism (Definition 6) is suboptimal since degrees are natural numbers and the Gaussian mechanism results in real-valued privatization noise. A more suitable privatization mechanism could be one that results in privatization noise with a discrete support, e.g., the discrete Gaussian mechanism [START_REF] Clément | The Discrete Gaussian for Differential Privacy[END_REF] or the tailored noise mechanism discussed in Chapter 4.

Future work. Let x ∈ R n . The unbiased sample variance of x is defined as follows:

σ2 x = 1 n(n -1) j>i (x i -x j ) 2 = 1 n -1 i∈[n] (x i -µ x ) 2 .
(3.50)

We highlight that BCGo can compute µ x and 1 n i∈[n] (x i -µ x ) 2 which are U-statistics of degree 1. This way, it remains to identify a strategy to obtain n -1 so that BCGo could be used to to compute σ2

x which is a U-statistic of degree 2. Taking the example with the unbiased sample variance, we conjecture that, by mathematical induction, it can be shown that BCGo can compute U-statistics of arbitrary degree.

Chapter 4

Tailored noise mechanism

In this chapter, we continue to study the setting of privacy-preserving distributed averaging where each agent of a communication network is attributed a vector of sensitive attributes, each agent locally privatizes each sensitive attribute, and each agent intends to collaboratively compute the averages over the privatized attributes.

In particular, we focus on a pre-processing step that happens prior to privatization, where the central curator solves a convex program and obtains privatization functions for privatizing sensitive attributes. Essentially, such privatization functions correspond to a utility-maximizing privatization mechanism which is shared to each agent, so that each agent could locally privatize its sensitive attributes.

To elaborate on our setting, we consider a group of agents, where each agent computes features (for fitting regression models) by transforming sensitive attributes, and where the transformations have high-magnitude gradients or singularities. In such setting, there is a risk of obtaining an outlier feature due to transforming a privatized attribute in an interval where the transformation has high-magnitude gradients. We mitigate the aforementioned risk by providing a tailored noise mechanism for privatizing features by solving a convex program in such a way that (i) only informative intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized.

We highlight that this chapter is based on a collaborative work with Moitree Basu who at the time was a doctorate student. Our common work mainly involved the following axes:

• Axis 1: Expression of models whose parameters can be computed from U-statistics (provided in Equation 4.1 below)

• Axis 2: Discretization of domains of features (discussed in Subsection 4.4.3)

• Axis 3: Expression of the constraints and the objective function of the convex program for obtaining privatization functions (discussed, respectively, in Subsection 4.4.1 and Subsection 4.4.2)

• Axis 4: Experiment setup (discussed in Section 4.6)

Regarding our individual theses, Moitree Basu had focused on the generalized expression of models mentioned in Axis 1 above. While for myself, I had focused on the comparison of the model where privatization noise is added before transforming attributes to features and the model where attributes are transformed to features before adding privatization noise (as such question arose while working on the bias-correcting gossip algorithm discussed in Section 3.3).

Introduction

We consider a setting where a group of agents intends to collaboratively fit a statistical model by sharing locally privatized features. For fitting a statistical model, one of the objectives is to identify such features which result in an accurate statistical model. In this work, we consider that features can be computed from attributes or other features, and such computations can be transformations with singularities. For example, the reciprocal function f (x) = 1 x has a singularity at x = 0. When privatizing features using a classic mechanism, e.g., the Gaussian mechanism (Definition 6) or the Laplace mechanism (Definition 7), we tend to firstly transform sensitive attributes into features, and only then add privatization noise. Otherwise, when privatization noise is added on sensitive attributes first, the classic mechanisms might result in a noisy value that falls too close to the singularity of a transformation, and thus the transformation results in an outlier feature. In other words, a privatized feature is susceptible to fall in an interval where the transformation has high-magnitude gradients. Furthermore, the classic mechanisms are suboptimal in terms of utility as they add, typically, more noise than necessary, as discussed in Balle and Wang [START_REF] Balle | Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising[END_REF].

In this work, we provide a tailored noise mechanism for privatizing features by solving a convex program in such a way that (i) only informative intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized. The execution of the tailored noise mechanism (TNM) firstly requires solving a convex program. We assume that the constraint solver is executed by a central curator, and the central curator shares the result of the constraint solver with each agent.

Regarding the motivation of the studied problem, TNM produces discrete probability distributions (as opposed to continuous) for privatizing features (an extension of TNM for continuous probability distributions is outside the scope of this work). This is similar to the discrete Gaussian mechanism [START_REF] Clément | The Discrete Gaussian for Differential Privacy[END_REF] which addresses the case when the data is discrete and spans over integers. Furthermore, certain classes of data have a bounded domain (e.g., for count data, we have natural numbers where the lowest value is 0), thus it might be useful to have the domain of a privatized feature, which is bounded in the same way as the domain of a respective sensitive feature. We remark that the Gaussian mechanism (Definition 6) and the Laplace mechanism (Laplace) result in unbounded domains of privatized features.

Regarding the novel qualities of TNM, we apply discretization strategies that mitigate the issue of obtaining an outlier feature due to transforming a privatized attribute in an interval where the transformation has high-magnitude gradients (or singularities). Also, we provide a convex program whose solution consists of a tailored privatization function parametrized by a sensitive feature, where the variance of the tailored privatization function is minimized and the absolute difference (biasedness) between the mean of the tailored privatization function and the sensitive feature is minimized.

We show on synthetic datasets and a synthetically-extended real dataset that TNM results, typically, in a lower MSE between true target values and predicted target values compared to Laplace, when fitting a linear regression model by regularized least squares that use U-statistics (Definition 1), and when the feature function is either the logarithm, the reciprocal, or the tangent.

Outline. In Section 4.2, we precise our setting. In Section 4.3, we perform the literature study. In Section 4.4, we design TNM. In Section 4.5, we describe the implementation of TNM using the cvxopt library for convex programs. In Section 4.6, we discuss the experiments. In Section 4.7, we conclude.

Preliminaries

In this section, we provide and recall the notation, and then we precise the setting.

Communication model. We have a group of agents each of which is attributed a data tuple with a scalar target value and a sensitive feature vector from a space X ⊆ R m, where m ∈ N 1 is the number of sensitive features.

In this work, the term "sensitive feature" encapsulates sensitive attributes. In particular, we consider that features can be computed from attributes or other features, and such computations can be transformations with singularities. We refer to the functions used to compute features from attributes as feature functions (e.g., we have the logarithm function, the identity function, the exponential function).

Threat model. We have a central curator who computes conditional probability mass functions (to which we refer as privatization functions) and shares them with the agents, so that each agent can hide its sensitive features under privatization noise (local differential privacy). The space of a privatized feature is denoted by X (we remark that X ⊇ X , where X is the space of sensitive features). This way, for each j ∈ [ m], x ∈ X j , x ∈ Xj , we have a privatization function with a conditional probability p j (x | x), where X j and Xj denote, respectively, the domain of the j-th sensitive feature and the domain of the j-th privatized feature.

Statistical model. We assume that our statistical model is a linear function h * that maps a feature vector to a scalar target value, where h * is parametrized by θ * ∈ R m+1 , and where m ∈ N 1 is the number of features. Once each agent privatizes its features and they are shared with the central curator, then the central curator can compute a matrix X ∈ R n×(m+1) composed of features and target values over all agents, where n is the number of agents. Then, the central curator fits a statistical model h (a linear function that maps a feature vector to a target value) using a function g : X → θ, where h is parametrized by θ. In this work, we aim for obtaining such privatization functions that minimize an objective value L( θ, θ * ), where L is an objective function whose common choice is the sum of the squared differences between the elements of the estimated parameters θ (computed from privatized features) and the true parameters θ * . We remark that the bolded font denotes vectors and matrices, as indicated in Table 2.1.

We consider the number l ∈ N 1 of models/approaches for obtaining parameter estimates θ. That is, for each k ∈ [l], we have a function g k : X → θ (to which we refer as Model k). We remark that distinct choices of g k include distinct fitting methods or distinct privatization strategies. In particular, we consider regularized least squares that uses U-statistics as indicated by Equation 2.9. This way, we have

g k f k,1 (X), f k,2 (X), . . . , f k,q k (X) , (4.1)
where q k ∈ N is the number of U-statistics (Definition 1) for fitting Model k, g k : R q k → R m+1 is a function for computing model parameters from U-statistics, and, for each s ∈ [q k ], we have a function f k,s : R n×(m+1) → R which computes a U-statistic from X.

In this work, the central curator computes the privatization functions by solving a convex program. Since convex programs are solved quicker (and require less memory) upon less constraint variables and constraints, the sensitive features of the agents are discretized. That is, the discretization is performed using thresholds, where, for every two adjacent thresholds, we attribute a representative value to which a sensitive feature is mapped to if the sensitive feature is in between those two adjacent thresholds (we perform binning, where the bins are the same for each feature vector of each agent). This way, a discretized domain X k,j includes the values of a sensitive feature j and Model k, and a discretized domain Xk,j ⊇ X k,j includes the values of a privatized feature j and Model k.

In summary, for computing privatization functions, the central curator solves a convex program to obtain a privatization function with a conditional probability p k,j (x | x), for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , where mk is the number of sensitive features used for fitting Model k.

In Table 4.1, we summarize the notation related to sensitive features and privatized features. We briefly expand on the notation. We use the acronym dp to refer to the application of a privatization function for differential privacy noise. We use the acronym tns to refer to the feature function that transforms attributes into features. We use the symbol "•" to denote the function composition. For example, for functions f, g, h, one of their compositions is expressed as h • g • f , which corresponds to firstly applying f , then g, and finally h.

In Table 4.2, we summarize the notation related to the work on tailored privatization. Finally, we remark that we particularly focus on the following two privatization strategies (which are models/approaches for obtaining parameter estimates θ):

• Model tns • dp. In this model, differential privacy noise is added to attributes first, and only then the attributes are transformed into features.

• Model dp • tns. In this model, attributes are transformed into features first, and only then differential privacy noise is added to the features.

Literature study

In this section, we perform the literature study. We highlight that this work has been mainly inspired by the utility-maximizing privatization mechanisms proposed by Ghosh et al. [START_REF] Ghosh | Universally Utility-maximizing Privacy Mechanisms[END_REF] [START_REF] Cormode | Constrained Private Mechanisms for Count Data[END_REF] have added additional constraints to resolve some anomalies in the work of Ghosh et al. [START_REF] Ghosh | Universally Utility-maximizing Privacy Mechanisms[END_REF]). The two utility-maximizing privatization mechanisms are characterized by solving a convex program to obtain a privatization function for count data. On one hand, our work is similar to the two mechanisms in the sense that we also define a convex program. On the other hand, our work is different in the sense that we consider a broader class of data than counts. Also, we have an additional constraint for unbiasedness. Furthermore, we take additional care of the singularities upon the computation of features.

Brenner and Nissim [START_REF] Brenner | Impossibility of Differentially Private Universally Optimal Mechanisms[END_REF] indicates that it is easier to provide stronger theoretical guarantees for maximizing the utility of privatized counts than for maximizing the utility of privatized sums. However, in our work, we focus on utility in practice as opposed to theoretical guarantees.

The issue with the privatization mechanisms that do not rely on convex programs (e.g., the Gaussian mechanism, Laplace or the discrete Gaussian mechanism [START_REF] Clément | The Discrete Gaussian for Differential Privacy[END_REF]) is that they result in suboptimal utility in exchange for simplicity of implementation and application. We remark that, upon defining a convex program, we have a discrete privatization function where we can explicitly specify the differential privacy requirement between every two of its probabilities (similarly as in Definition 5). Further, there exist approaches where privatization functions are obtained using generative adversarial networks [START_REF] Romanelli | Optimal Obfuscation Mechanisms via Machine Learning[END_REF] or stochastic gradient descent [START_REF] Wang | Local Differential Privacy for data collection and analysis[END_REF]. However, those techniques require a training set whereas in our approach we avoid such dependency.

We discuss several other mechanisms that are based on convex programs. Gupte and Sundararajan [START_REF] Gupte | Universally optimal privacy mechanisms for minimax agents[END_REF] is similar to Ghosh et al. [START_REF] Ghosh | Universally Utility-maximizing Privacy Mechanisms[END_REF] in the sense that the authors consider count data though they use a different objective function. Geng and Viswanath [START_REF] Geng | The Optimal Noise-Adding Mechanism in Differential Privacy[END_REF] considers central differential privacy (where we trust a central curator and share with it the true values of sensitive features). Shokri [START_REF] Shokri | Privacy Games: Optimal User-Centric Data Obfuscation[END_REF] considers local differential privacy, however the work does not consider unbiasedness.

We remark that blowfish privacy [START_REF] He | Blowfish privacy: tuning privacy-utility trade-offs using policies[END_REF] is a generalization of differential privacy and is appropriate for cases when the trade-off between privacy and utility is of interest. However, such framework requires background knowledge on the graph of agents.

Finally, we remark that Mironov et al. [START_REF] Mironov | On significance of the least significant bits for differential privacy[END_REF] discusses a privatization issue of Laplace due to the least significant bits. In our case, such issue is avoided by discretizing the features to the bins that do not rely on the least significant bits (e.g., the representative values of the bins can be rounded to a higher significant bit).

Approach

In this section, we intend to define a convex program for computing the conditional probabilities of a privatization function which is tailored for the following conditions:

1. Sampling from the privatization function guarantees (ϵ, 0)-differential privacy (Definition 5).

2. The biasedness of the privatization function is minimized, i.e., the absolute difference between the mean of the privatization function and the sensitive feature parametrizing the privatization function is minimized.

3. The variance of the privatization function is minimized.

4. Each conditional probability p k,j (x | x) of the privatization function must sum to 1, while each such probability must be greater or equal to 0 and less than or equal to 1.

We remark that a successful solution of the aforementioned convex program is interpreted as TNM because the solution includes the privatization functions for privatizing features.

In the subsections that follow, we elaborate how TNM integrates the four requirements stated in the aforementioned list. In Subsection 4.4.1, we define the constraints. In Subsection 4.4.2, we define the objective function. In Subsection 4.4.3, we review some strategies for discretization of domains of sensitive features and domains of privatized features.

Definition of the constraints

In this subsection, we define the constraints to cover Requirement 1 (for ensuring differential privacy) and Requirement 4 (for ensuring valid probability mass functions), and to partially cover Requirement 2 (for ensuring bias minimization). The complete coverage of Requirement 2 is achieved in conjunction with the objective function discussed later in Subsection 4.4.2.

Differential privacy constraint. Since, for Model k, we have mk sensitive features, we split the total privacy budget ϵ evenly for each sensitive feature. That is, for Model k, an even split of the total privacy budget ϵ is the following:

ϵ k = ϵ mk .
Let ϵ ≥ 0. For local ϵ-differential privacy (similarly as in Definition 5), it is requires that, for each k ∈ [l], j ∈ [ mk ], x 1 , x 2 ∈ X k,j , T ⊆ Xk,j , we have

x∈T p k,j (x | x 1 ) ≤ e ϵ k x∈T p k,j (x | x 2 ), (4.2)
which is a linear inequality constraint with the constraint variables p k,j (x | x 1 ) and p k,j (x | x 2 ). We remark that x 1 and x 2 in Equation 4.2 are adjacent values under the notion of local differential privacy, where in local differential privacy we add noise, typically, directly to sensitive attributes as opposed to statistics computed from them. Also, we remark that the sums in Equation 4.2 are due to the addition law of probability, as we intend to privatize a discrete class of data.

Since the number of subsets T ⊆ Xk,j is exponential in | Xk,j | (results in a large number of constraints), we reformulate Equation 4.2. That is, for each k ∈ [l], j ∈ [ mk ], x 1 , x 2 ∈ X k,j , x ∈ Xk,j , we have

p k,j (x | x 1 ) ≤ e ϵ k p k,j (x | x 2 ). (4.3)
We can further reduce the number of constraints by reformulating Equation 4.3. That is, for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have

p k,j (x | x) ≤ e ϵ k p max k,j (x), (4.4) p max k,j (x) ≤ e ϵ k p k,j (x | x), (4.5)
where p max k,j (x) is a constraint variable for the highest value in {p k,j (x | x) : x ∈ X k,j }. Finally, we rewrite Equation 4.4 and Equation 4.5 to the normal form of constraints (i.e., the terms with constraint variables are moved to the left hand side of the "less than or equal" symbol). That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have p k,j (x | x) -e ϵ k p max k,j (x) ≤ 0, (4.6) p max k,j (x) -e ϵ k p k,j (x | x) ≤ 0. (4.7)
We remark that a constraint solver might encounter numerical difficulties when the coefficients of constraint variables are high. This way, we scale Equation 4.6 and Equation 4.7. That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have 1 e ϵ k p k,j (x | x) -p max k,j (x) ≤ 0, (4.8) 1 e ϵ k p max k,j (x) -p k,j (x | x) ≤ 0. (4.9)
Hence, for ensuring local ϵ-differential privacy, we have two distinct linear inequality constraints.

Bias minimization constraint. We design the bias minimization of the privatization functions by firstly defining a linear inequality constraint. That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , we have x∈ Xk,j xp k,j (x | x) ≤ x + c k,j,x , (4.10)
where c k,j,x is a constraint variable that quantifies the bias (ideally equals 0). We remark that we use the "less than or equal" symbol as opposed to equality because we aim for a larger solution space. We rewrite Equation 4.10 in the normal form. That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , we have x∈ Xk,j xp k,j (x | x) -c k,j,x ≤ x.
(4.11)

Finally, we scale Equation 4.11. That is, for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , we have

1 max x∈ Xk,j |x|   x∈ Xk,j xp k,j (x | x) -c k,j,x   ≤ x max x∈ Xk,j |x| . (4.12)
Hence, for ensuring bias minimization, we have one linear inequality constraint. However, we remind that up until now we have discussed only the first part of the bias minimization, as the second part of the bias minimization is part of the objective function (discussed later in Subsection 4.4.2).

Constraints of probability mass functions. The probabilities of a probability mass function must sum to 1, while each such probability is greater or equal to 0 and less than or equal to 1.

We define the constraint for the probabilities of a probability mass function summing to 1. That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , we have x∈ Xk,j p k,j (x | x) = 1, (4.13)
which is a linear equality constraint in its normal form.

Approach

Chapter 4. Tailored noise mechanism

We define the constraint so that each probability is higher or equal to 0 (Equation 4.13 already implies that no probability is higher than 1 because their sum equals to 1). That is, for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have

p k,j (x | x) ≥ 0, (4.14)
which is a linear inequality constraint. We rewrite Equation 4.14 in the normal form. That is, for each

k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have -p k,j (x | x) ≤ 0. (4.15)
We require that the constraint variable p max k,j (x) is less than or equal to 1. That is, for each k ∈ [l], j ∈ [ mk ], x ∈ Xk,j , we have

p max k,j (x) ≤ 1, (4.16)
which is a linear inequality constraint in its normal form. Further, we require that the constraint variable p max k,j (x) is greater or equal to the probabilities in {p k,j (

x | x) : x ∈ X k,j }. That is, for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have p k,j (x | x) ≤ p max k,j (x), (4.17)
which is a linear inequality constraint. We rewrite Equation 4.17 in its normal form. That is, for each k ∈ [l], j ∈ [ mk ], x ∈ X k,j , x ∈ Xk,j , we have

p k,j (x | x) -p max k,j (x) ≤ 0. (4.18)
We remark that if the constraint in Equation 4.18 is met, it guarantees that the constraint in Equation 4.8 is met also. Hence, for valid probability mass functions, we have one linear equality constraint and three linear inequality constraints.

Definition of the objective function

In this subsection, we define the objective function so that it covers Requirement 3 (for ensuring variance minimization). We highlight that the objective function completes the coverage of Requirement 2 (for ensuring bias minimization) whose initial part is covered in Subsection 4.4.1 above.

Our intention is to minimize the total objective function L by minimizing the objective function L k of Model k, for each k ∈ [l], i.e., we minimize

L = k∈[l] L k . (4.19)
We define the objective function of Model k as

L k = L vce k + L bias k , (4.20)
where L vce k is the objective value for minimizing variance and L bias k is the objective value for minimizing bias.

Variance minimization. In Model tns • dp, we firstly privatize attributes and then transform them into features for computing U-statistics. For this reason, in the objective function, we have the variance of attributes and the variance of features. Thus, for each j ∈ [ mk ], let r j ∈ N 1 denote the number of features computed from an attribute j. Then, for each t ∈ [r j ], let f ′ k,j,t denote the t-th feature function.

We define the objective function for variance minimization as follows:

L vce k = j∈[ mk ],t∈[r j ],x∈X k,j ,x∈ Xk,j ρ vce k,j,t p k,j (x | x) f ′ k,j,t (x) -f ′ k,j,t (x) 2 , (4.21)
where

ρ vce k,j,t = 10 -2 min 1, 1 max x∈X k,j ,x∈ Xk,j f ′ k,j,t (x) -f ′ k,j,t (x) 2 (4.22)
is the scaling term of the objective function for variance minimization. We remark that the term 10 -2 is there due to the constraint variable p k,j (x | x) belonging to an interval of length 1 (thus the partial derivatives of the objective function for variable minimization should not be too high to avoid proposals that are outside that interval). We conclude that the objective function for variance minimization is linear with respect to the constraint variables.

Bias minimization. We define the objective function for bias minimization as follows:

L bias k = j∈[ mk ],x∈X k,j ρ bias k,j c 2 k,j,x , (4.23)
where ρ bias k,j = 10 -2

1 max x∈ Xk,j x2 (4.24)
is the scaling term of the objective function for bias minimization. We remark that the term 10 -2 is there so that the objective function for bias minimization has a lower influence on the total objective function.

We conclude that the objective function for bias minimization is convex since the constraint variable c k,j,x is squared.

Discretization of domains of features

In this subsection, we describe some strategies for discretization of domains of sensitive features and domains of privatized features, which are based on thresholds and representative values. That is, for every two adjacent thresholds, we attribute a representative value to which a sensitive feature is mapped to if the sensitive feature is in between those two adjacent thresholds.

We recall two classic discretization strategies: equal distance discretization and equal frequency discretization, which are discussed in Zheng and Casari [START_REF] Zheng | Feature engineering for machine learning: principles and techniques for data scientists[END_REF].

In equal distance discretization, we choose the number of thresholds, compute the difference between the highest and the lowest value, and determine the length of a discretization subinterval (we refer to it by a bin) by dividing the previously computed difference by the number of thresholds. Finally, we place thresholds at the boundaries of each bin and fix the representative value in the middle of two adjacent thresholds.

Equal distance discretization can be also used in the sense of mapping features to the transformation scale (e.g., the natural logarithm scale), then computing the thresholds and the representative values, and finally remapping them to the original scale (for the natural logarithm scale, such remapping is e x ). This results in more (or less) bins in the intervals where the gradient of the transformation of features has a higher (or lower) magnitude. We remark that the magnitude of a gradient can get high when the transformation has singularities. For example, the singularity in f (x) = 1

x is at x = 0. In equal frequency discretization, we determine the locations of the thresholds in such a way that there would be an approximately equal number of features falling in between every two adjacent thresholds. We fix each representative value in the middle of two adjacent thresholds.

Implementation

In this section, we relate our constraint problem (discussed in Section 4.4) to the standard form accepted by the cvxopt package (discussed in Subsection 2.6.1). Firstly, we precise the order and counts of the constraint variables in our convex program Then, we precise the order and counts of the constraints. Finally, we elaborate on the implementation details of the objective function.

Even though the convex program in Section 4.4 is quadratic (it has a quadratic objective function and linear constraints), we formulate it as a more general convex program. This way, future extensions that result in convex constraints or a convex objective function would be more straightforward to integrate. We remark that, in this work, we already discuss the scaling of constraints and the scaling of the objective function, which are typical practices to reduce the numerical difficulty for solving convex programs.

We remark that, in this work, we have used the default constraint solver of cvxopt, which is based on Cholesky decomposition. This choice is faster compared to an alternative that is based on the LDL decomposition, which is more suitable for convex programs that are numerically difficult, e.g., when it is difficult to appropriately scale the constraints or the objective function.

Order of constraint variables. Let idx(•) denote a map from a value to its index in its discrete domain. In Table 4.3, we list the constraint variables according to their order in the convex program and we also provide a formula for the index of a particular constraint variable.

p k,j (x | x) k ′ ∈[k] j ′ ∈[ mk ′ ] |X k ′ ,j ′ || Xk ′ ,j ′ | + j ′ ∈[j] |X k,j ′ || Xk,j ′ | +idx(x)| Xk,j | + idx(x) 2 p max k,j (x) k ′ ∈[k] j ′ ∈[ mk ′ ] | Xk ′ ,j ′ | + j ′ ∈[j] | Xk,j ′ | + idx(x) 3 c k,j,x k ′ ∈[k] j ′ ∈[ mk ′ ] |X k ′ ,j ′ | + j ′ ∈[j] |X k,j ′ | + idx(x)
In Table 4.4, we provide a formula for the total number of constraint variables.

p k,j (x | x) k∈[l],j∈[ mk ] |X k,j || Xk,j | (m ′ + m)|X || X | p max k,j (x) k∈[l],j∈[ mk ] | Xk,j | (m ′ + m)| X | c k,j,x k∈[l],j∈[ mk ] |X k,j | (m ′ + m)|X |
Order of constraints. In Table 4.5 and Table 4.6 below, we list, respectively, the order of linear equality constraints and the order of linear inequality constraints in the convex program. We remind that Equation 4.18 implies Equation 4.9, where the latter equation is the remaining constraint for differential privacy.

In Table 4.7, we provide a formula for the total number of each type of constraints. 4.23) for minimizing bias. This way, in each iteration, the constraint solver evaluates the objective function using the values of the constraint variables with probabilities of privatization functions, i.e., p k,j (x | x), and the values of the constraint variables indicating the amount of biasedness, i.e., c k,j,x .

Regarding the initial proposal of the solution of the constraint solver, we fix the constraint variables related to probabilities, i.e., p k,j (x | x) and p max k,j (x), so that they correspond to uniform distributions. Then, we fix the constraint variables c k,j,x so that the bias minimization constraints result in equalities.

Experiments

In this section, we discuss the experiments.

In Subsection 4.6.1, we describe datasets. In Subsection 4.6.2, we precise the experiment setup. In Subsection 4.6.3, we discuss the results of the experiments. In Subsection 4.6.4, we discuss secondary experiments.

Dataset description

In this subsection, we define the linear regression model and describe our datasets.

Linear regression model. Let m ∈ N 1 . For our experiments, we define a multiple linear regression model with m + 1 regression parameters and a scalar target value. For each i ∈ [n], we have

y i = θ 0 + θ 1 x i,1 + . . . + θ m x i,m + ξ reg i , (4.25)
where x i,1 , x i,2 , . . . , x i,m are (sensitive) features, θ 0 , θ 1 , . . . , θ m ∈ R are regression parameters, ξ reg i is regression noise which is an independent observation of N (0, σ 2 ), and σ is the standard deviation of regression noise.

We leave the following remarks on the privacy guarantees for locally privatizing the aforementioned sensitive features x i,1 , x i,2 , . . . , x i,m :

• Upon Laplace (Definition 7), we assume that the lowest value of each sensitive feature and the highest value of each sensitive feature are known. This way, each agent can compute the l 1 sensitivity (Equation 2.14) of Laplace. We recall that Laplace ensures ϵ-differential privacy.

• Upon TNM, we assume that the lowest value of each sensitive feature and the highest value of each sensitive feature are known. This way, equal distance discretization (which is required for obtaining privatization functions and is discussed in Subsection 4.4.3) allows for each agent to keep each of its sensitive feature hidden because upon the aforementioned assumption the central curator can perform equal distance discretization without knowing any of the sensitive features. However, for equal frequency discretization, the central curator would need to know each sensitive feature.

• Upon TNM, local privatization of sensitive features is ϵ-differentially private due to Equation 4.6 and Equation 4.7, which are derived from Equation 4.2. For privatizing its sensitive feature, each agent would firstly discretize it using the same discretization strategy as the central curator. We argue that the privacy guarantees of TNM (upon equal distance discretization) and Laplace are comparable because we rely on the same assumptions. Yet, the discretization in TNM results in a loss of utility due to the presence of granularity.

• Referring to Sei and Ohsuga [START_REF] Sei | Private True Data Mining: Differential Privacy Featuring Errors to Manage Internet-of-Things Data[END_REF], we assume that target values are nonsensitive. Even though a target value y i (Equation 4.25) is a linear combination of sensitive features, the exact values of the regression parameters and the regression noise remain unknown, thus the values of the sensitive features can not be deduced.

• Referring to the composition theorem in Dwork and Roth [START_REF] Dwork | The Algorithmic Foundations of Differential Privacy[END_REF], privatization of the sensitive features upon even splits of the total privacy budget ϵ lead to ϵ-differential privacy.

We fit the regression model defined in Equation 4.25 by regularized least squares (discussed in Subsection 2.4.1). That is, referring to Equation 2.9, we compute the vector θ of parameter estimates as follows:

θ = 1 n X T X + λI m+1 -1 1 n X T y, (4.26) where 1 n X T X =       1 1 n i∈[n] x i,1 . . . 1 n i∈[n] x i,m 1 n i∈[n] x i,1 1 n i∈[n] x 2 i,1 . . . 1 n i∈[n] x i,1 x i,m . . . . . . . . . . . . 1 n i∈[n] x i,m 1 n i∈[n] x i,1 x i,m . . . 1 n i∈[n] x 2 i,m       1 n X T y = 1 n i∈[n] y i 1 n i∈[n] y i x i,1 . . . 1 n i∈[n] y i x i,m T ,
and where λ ∈ R is the regularization parameter and I is the (m + 1) × (m + 1) identity matrix.

Datasets. We describe four synthetic datasets ds1, ds2a, ds2b, ds3, and a synthetically-extended real dataset misra1d (the size of the real dataset was extremely small, thus we generated additional instances). Let ϵ * = 10 -2 be the closest distance to which an attribute can reach the singularity when transforming the attribute into a feature. We list the descriptions of the datasets:

• ds1. We have the regression model so that, for each i ∈ [n], a target value y i = θ 0 + θ 1 log(a i ) + ξ reg i , where an attribute a i is drawn independently from uni(ϵ * , 1), regression noise ξ reg i is drawn independently from N (0, 1), true regression parameters θ 0 = θ 1 = 1. We intend to obtain regression parameter estimates θ0 and θ1 so that a predicted target value y pred i = θ0 + θ1 log(a i ).

• ds2a. We have the regression model so that, for each i ∈ [n], a target value

y i = θ 0 + θ 1 1 a i + ξ reg i ,
where an attribute a i is drawn independently from uni(ϵ * , 1), regression noise ξ reg i is drawn independently from N (0, 1), true regression parameters θ 0 = θ 1 = 1. We intend to obtain regression parameter estimates θ0 and θ1 so that a predicted target value y pred i = θ0 + θ1 1 a i . • ds2b. We have the regression model so that, for each i ∈ [n], a target value

y i = θ 0 + θ 1 a i + θ 2 1 a i + ξ reg i ,
where an attribute a i is drawn independently from uni(ϵ * , 1), regression noise ξ reg i is drawn independently from N (0, 1), true regression parameters θ 0 = θ 1 = θ 2 = 1. We intend to obtain regression parameter estimates θ0 , θ1 , and θ2 so that a predicted target value y pred i = θ0 + θ1 a i + θ2 1 a i . • ds3. We have the regression model so that, for each i ∈ [n], a target value y i = θ 0 + θ 1 tan(a i ) + ξ reg i , where an attribute a i is drawn independently from uni(-π 2 + ϵ * , π 2 -ϵ * ), regression noise ξ reg i is drawn independently from N (0, 1), true regression parameters θ 0 = θ 1 = 1. We intend to obtain regression parameter estimates θ0 and θ1 so that a predicted target value y pred i = θ0 + θ1 tan(a i ).

• misra1d. We have the regression model so that, for each i ∈ [n], a target value

y i = θµ 1 θµ 2 a i 1+ θµ 2 a i + ξ reg i ,
where an attribute a i = 10 3 × a ′ i , a ′ i is drawn independently from uni(0, 1), regression noise ξ reg i = 6.85 × 10 -2 × ξ reg i ′ , ξ reg i ′ is drawn independently from N (0, 1), regression parameters θµ 1 = 4.37 × 10 2 and θµ 2 = 3.02 × 10 -4 . We intend to obtain regression parameter estimates θ0 , θ1 , and θ2 so that a predicted target value

y pred i = θ0 + θ1 1 1+c 1 a i + θ2 1 1+c 2 a i , where c 1 = θµ 2 + θσ 2 , c 2 = θµ 2 + 1.1 × θσ 2 ,

and the sample standard deviation (of θµ

2 ) θσ 2 = 2.93 × 10 -6 . We remark that the coefficient 6.85 × 10 -2 of ξ reg i and values θµ 1 , θµ 2 , θσ 2 are taken from itl.nist.gov/div898/strd/nls/data/LINKS/v-misra1d.shtml, whereas the coefficient 10 3 of a i is the order of magnitude of the distance between the lowest and the highest target values in the original dataset.

Regarding the misra1d dataset, we have approximated its non-linear regression model, i.e.,

y i = θµ 1 θµ 2 a i 1+ θµ 2 a i + ξ reg
i by a linear one, i.e., y i ≈ θ0 + θ1

1 1+c 1 a i + θ2 1 1+c 2 a i .
• We normalize the MSE between true target values and predicted target values dividing it by (σ y ) 2 , where σ y is the standard deviation of true target values.

(We remark that such normalization is discussed in more detail in Gupta and Kling [START_REF] Vijai | On typical range, sensitivity, and normalization of Mean Squared Error and Nash-Sutcliffe Efficiency type metrics[END_REF].) We perform cross-validation with 10 folds. We fix the regularization parameter to λ = 10 3 .

• We fix the number of experiment repetitions to t exp = 2 7 . In each experiment repetition, we privatize features. Each synthetic dataset is generated once for all experiment repetitions.

• We fix the significance level to α ci = 0.05 (the computation of confidence intervals is described in Equation 2.5).

Result interpretation

In this subsection, we discuss the results of the two sets of experiments. Figure 4.1 illustrates the results of Experiment 4.1 on ds1. Due to sufficiently fine discretization, TNM performs better than Laplace. In Laplace, Model tns • dp performs slightly better than Model dp • tns upon a lower privacy budget and slightly worse upon a higher privacy budget. We conclude that the two models perform similarly because the log transformation approaches its singularity relatively slowly. Similarly, in TNM, Model tns • dp performs similar to Model dp • tns. The experiments were run on a machine with an Intel E5-2643 processor (3.30 GHz) and 192 GB of RAM; this took 15 minutes. For ds1, ds2a, and ds3, we had 880 constraint variables (Table 4.4) and 2440 constraints (Table 4.7). For ds2b and misra1d, we had 1320 constraint variables and 3660 constraints. For ds1, the memory requirement excessed our resources when the discretization granularity reached 100 bins (the implementation attempted to allocate space for 20400 constraint variables and 60200 constraints).

Secondary experiments

In this subsection, we discuss secondary experiments. In particular, we compare equal distance discretization with equal frequency discretization. Also, we compare coarser and finer domains of sensitive features and domains of privatized features.

Figure 4.6 illustrates a comparison between equal distance discretization and equal frequency discretization on ds1. The two discretization strategies result in similar utility because the two discretization strategies result in similar threshhold placements (the logarithm transformation approaches its singularity relatively slowly). Figure 4.9 illustrates a comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a upon equal frequency discretization. We observe that a finer discretization of sensitive features results in an improvement in utility for both Model tns • dp and Model dp • tns. However, we remark that 40 bins were not enough for equal frequency discretization to result in gradual improvement of utility for a higher privacy budget. 4.10 illustrates a comparison between a finer discretization and a coarser discretization of domains of privatized features on ds2a upon equal distance discretization, when there is one additional bin between every two bins of sensitive features (interpolation) and there are two additional bins one of which is lower and the other is higher than any other bin of sensitive features (extrapolation).

We observe that a finer discretization of privatized features does not result in a utility improvement upon a higher privacy budget. This is because, due the combination of the objective function for minimizing variance (Equation 4.21) and the differential privacy constraint (Equation 4.8), the obtained privatization functions have probabilities of 0 for sampling interpolated or extrapolated values. We remark that, in our experiments, the utility sometimes stagnates upon a higher privacy budget, e.g., this is the case in Figure 4.2. The cause of this is the regularization of the diagonal of the matrix 1 n X T X in Equation 2.12, which mitigates the numerical difficulty of taking its matrix inverse (Equation 4.26) in exchange for lower accuracy.

Conclusion

We have provided a utility-maximizing mechanism for privatizing features that are computed by transforming sensitive attributes, when the transformations have high-magnitude gradients or singularities. In particular, we have provided the tailored noise mechanism (TNM) for privatizing features by solving a convex program in such a way that (i) only informative intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized.

In our experiments results on synthetic datasets and a synthetically-extended real dataset, we have observed that TNM results, typically, in a lower MSE between true target values and predicted target values compared to the Laplace mechanism (Definition 7), when fitting a linear regression model by regularized least squares (Equation 2.12) that use U-statistics, and when the feature function is either the logarithm, the reciprocal, or the tangent.

Also, in our experiment results (illustrated in Figure 4.2), we have observed that, in TNM and for the linear regression model of the ds2a dataset, Model dp • tns (where attributes are transformed into features first, and only then differential privacy noise is added to the features) performs better than Model tns • dp (where differential privacy noise is added to attributes first, and only then the attributes are transformed into features) because the reciprocal transformation in ds2a approaches its singularity relatively quickly, thus the risk of obtaining outlier features is higher.

Future directions. Firstly, we remark that our approach of solving a convex program for obtaining the conditional probabilities of privatization functions is appropriate only for discrete privatization functions. To extend our approach for continuous privatization functions, we could attempt to identify a family of privatization functions with shape parameters, so that the convex program would remain tractable and intend to identify optimal shape parameters as opposed to conditional probabilities.

Secondly, we could attempt to identify a discretization strategy dedicated for models where attributes are transformed to several distinct features, and where the discretization strategy takes into account the influence of a weighted combination of distinct transformations. This way, we could determine the locations of the bins, which are informative over all distinct transformations.

Chapter 5

Summary and future directions

In Chapter 1, we have stated our principal question, which goes as follows: how could the agents of a communication network maximize the accuracy of collaboratively computed averages of locally privatized attributes? To answer this question, we have discussed two contributions, respectively, in Section 3.3 and Chapter 4. In the first work, we have discussed distributed averaging on graphs with arbitrary degree sequences, when the computed averages are unbiased, when the degrees of the agents are sensitive, and when the agents interact without handshakes. In the second work, we have discussed a utility-maximizing mechanism for privatizing features that are computed by transforming sensitive attributes, when the transformations have high-magnitude gradients or singularities.

In Section 5.1, we summarize the contributions by enumerating their advantages and disadvantages. In Section 5.2, we discuss future directions.

Summary of contributions

In this section, we summarize the two aforementioned contributions by enumerating their advantages and disadvantages, where the first contribution is the work on distributed averaging on graphs with arbitrary degree sequences, which is discussed in Section 3.3, and the second contribution is the work on tailored privatization, which is discussed in Chapter 4. For the work on tailored privatization, we also enumerate some remarks.

We remark that, in Section 3.2, we have provided an example of distributed averaging on ER graphs. However, ER graphs are not as general as graphs with arbitrary degree sequences because, in expectation, every vertex of an ER random graph has the degree np, where n is the order of the graph and p is the probability of edge assignment between any two distinct vertices of the ER random graph.

In the work on distributed averaging on graphs with arbitrary degree sequences, we have proved an asymptotic guarantee (Theorem 5) for the MSE between the average of sensitive attributes and the average of locally privatized attributes computed by the bias-correcting gossip algorithm (Equation 3.9), when the graph of agents is modeled by the configuration model (Definition 4), when the degrees of agents are sensitive, and when the agents interact without handshakes. x i (where x ∈ R n ), when we compute U-statistics (Definition 1) of degree 1 from locally privatized degrees raised to a power k = 2, and when the graph has low degrees (i.e., when the 2-nd raw moment µ d 2 and the k-th raw moment µ d k of the degrees in Equation 3.44 are low).

2. Handshake-free interaction is a characteristic of a communication model with a stronger self-management. As a consequence, information dissemination among the agents is more robust upon inactive agents.

We enumerate the disadvantages of the work on distributed averaging on graphs with arbitrary degree sequences:

1. Equation 3.45 indicates that distributed averaging of locally privatized attributes performed by BCGo requires to split the privacy budget in m + 2 parts and centralized averaging of locally privatized attributes requires to split the privacy budget in m parts, where m is the number of sensitive attributes. This way, the use of BCGo requires to split the privacy budget in 2 additional parts.

2. The heuristic (Equation 3.35) for the expected value of the reciprocal of the square of a Gaussian random variable, to our knowledge, has no closedform expression. This way, the approximation error in Equation 3.29 is left unquantified.

In the work on tailored privatization, we have provided a utility-maximizing mechanism for privatizing features that are computed by transforming sensitive attributes, when the transformations have high-magnitude gradients or singularities. In particular, we have provided the tailored noise mechanism (TNM) for privatizing features by solving a convex program in such a way that (i) only informative intervals of transformations are selected, (ii) the variance of privatization noise is minimized, and (iii) the biasedness of privatization noise is minimized.

We enumerate the advantages of the work on tailored privatization:

1. In our experiment results on synthetic datasets and a synthetically-extended real dataset, we have observed that TNM results, typically, in a lower MSE between true target values and predicted target values compared to the Laplace mechanism (Definition 7), when fitting a linear regression model by regularized least squares that use U-statistics (Definition 1), and when the feature function is either the logarithm, the reciprocal, or the tangent.

2. In our experiment results (illustrated in Figure 4.2), we have observed that, in TNM and for the linear regression model of the ds2a dataset, Model dp • tns (where attributes are transformed into features first, and only then differential privacy noise is added to the features) performs better than Model tns • dp (where differential privacy noise is added to attributes first, and only then the attributes are transformed into features) because ds2a has the reciprocal transformation which approaches its singularity relatively quickly, and the risk of obtaining outlier features is higher.

3. In our experiment results (illustrated in Figure 4.4 and Figure 4.5), we have observed that, in TNM and for the linear regression models of the ds2b dataset and the misra1d dataset, where two features are computed from distinct transformations of one attribute, Model tns • dp performs better than Model dp • tns because, for Model dp • tns, the privacy budget was split in 2 parts and, for Model tns • dp, the privacy budget remained unsplit.

4. The strategy of transforming the non-linear regression model of the original misra1d dataset to a linear one (Equation 4.27) can be generalized to other non-linear datasets.

We enumerate the disadvantages of the work on tailored privatization:

1. A utility-maximizing mechanism obtained by solving a convex program requires discretization of domains of privatization functions, and the presence of granularity results in utility loss.

2. We have found only one relevant real dataset (misra1d) where features are obtained from a transformation with a singularity, while misra1d is an extremely small dataset.

We enumerate some remarks of the work on tailored privatization:

1. In our experiment results (illustrated in Figure 4.6), we have observed that equal frequency discretisation performs better than equal distance discretization upon a transformation that approaches its singularity relatively slowly (for the discretization granularity that was handled by our machine).

2. In our experiment results (illustrated in Figure 4.7), we have observed that equal distance discretisation performs better than equal frequency discretization upon a transformations that approaches its singularity relatively quickly (for the discretization granularity that was handled by our machine).

Future directions

In this section, we firstly summarize more straightforward future directions of the work on distributed averaging on graphs with arbitrary degree sequences, which is discussed in Section 3.3, and the work on tailored privatization, which is discussed in Chapter 4. Then, we discuss future direction in a broader sense by considering the settings that are close to (yet outside of) the scope of this dissertation, as illustrated in Figure 2.5. We discuss future directions of the work on distributed averaging on graphs with arbitrary degree sequences:

1. By identifying a strategy to obtain the number n of neighbors, BCGo could be used to compute the unbiased sample variance which is a U-statistic of degree 2 (indicated by Equation 3.50). This way, we conjecture that, by mathematical induction, it can be shown that BCGo can compute U-statistics of arbitrary degree.

2. We conjecture that the convergence rate of BCGo executed on graphs with arbitrary degree sequences could be obtained from the transition matrix of the simple gossip algorithm (Algorithm 1), as BCGo is a combination of two distinct executions of the simple gossip algorithm (SiGo). Boyd et al. [START_REF] Boyd | Randomized gossip algorithms[END_REF] indicates that the convergence rate of a gossip algorithm can be determined from the second largest singular value of the transition matrix.

In such case, the convergence rate can be obtained from the spectral gap, which is discussed in more detail in the slides by Iutzeler [Iut16a;[START_REF] Iutzeler | Gossip algorithms: Tutorial and Recent advances (part 2)[END_REF].

3. For privatizing the degrees of agents, we have used the Gaussian mechanism (Definition 6). However, the degrees are always non-negative, thus their domain is bounded from below. A more suitable privatization mechanism could be one that results in privatization noise with a discrete support, e.g., the discrete Gaussian mechanism [START_REF] Clément | The Discrete Gaussian for Differential Privacy[END_REF] or TNM.

We discuss future directions of the work on tailored privatization:

1. Our approach of solving a convex program for obtaining the conditional probabilities of privatization functions is appropriate only for discrete privatization functions. To extend our approach for continuous privatization functions, we could attempt to identify a family of privatization functions with shape parameters, so that the convex program would remain tractable and intend to identify optimal shape parameters as opposed to conditional probabilities.

2. We could attempt to identify a discretization strategy dedicated for models where attributes are transformed to several distinct features, and where the discretization strategy takes into account the influence of a weighted combination of distinct transformations. This way, we could determine the locations of the bins, which are informative over all distinct transformations.

Broader future directions. We elaborate on the future directions in a broader sense. In Figure 2.5, we have illustrated two settings that are close to (yet outside of) the scope of this dissertation. One of such settings is related to dynamic communication models, and the other is related to personalized statistical models.

We start by discussing future directions towards dynamic communication models.

Firstly, we remark that communication models with a notion of time can be interpreted as complex networks (discussed in Subsection 2.2.1). Then, we highlight that the evolution of a complex network can be represented by its equilibrium state (a graph G) or by a sequence of graphs (G k ) k≥1 of length k, where each graph in the sequence represents a state upon a particular instance of time.

We envision a future direction where the representation of a complex network by a graph G could have an advantage over the representation of a complex network by a sequence (G k ) k≥1 . For example, if a graph G was generated by adding vertices (and their edges) one by one (an example of such generation is the Chinese restaurant process discussed in Subsection 2.2.3), it might suffice to identify emergent properties (e.g., the presence of a giant component discussed in Subsection 2.2.1) by taking at G rather than taking every element in the sequence (G k ) k≥1 that led to G. This way, the computation cost of the identification of emergent properties of a dynamic communication model would be kept low.

We proceed by discussing future directions towards personalized statistical models.

Firstly, we remind that the bias between the average of locally privatized attributes computed by SiGo and the true average of individual values is present when the graph of agents is non-regular (as mentioned in Chapter 3). As indicated by Equation 3.45, BCGo can result in privatization noise that is higher than the corrected bias, when the bias is low and due to the additional splits of the privacy budget in BCGo. This way, we conjecture that there exist graphs on which SiGo can outperform BCGo, especially when the average degree is low.

We envision a future direction where SiGo is executed separately in clusters of agents, where each cluster is formed of agents who have similar degrees, as in such case the aforementioned bias would get low. This way, the future direction would involve a search of a convenient approach for clustering agents that have similar degrees.

One possible approach could be an application of a clustering algorithm based on ϵ-regular pairs defined as follows. Let ϵ ∈ (0, 1). Let C, C ′ ⊆ V be pairwise disjoint subsets of vertices of a graph. where den(X, Y ) and den(C, C ′ ) are defined in Equation 2.6. As proven by Szemerédi's regularity lemma [START_REF] Szemerédi | On sets of integers containing k elements in arithmetic progression[END_REF], there exist such graphs for which it is possible to find a partition of vertices, where the partition includes pairwise disjoint subsets of vertices, and where each pair of subsets is ϵ-regular. However, as indicated by Gowers [START_REF] Gowers | Lower bounds of tower type for Szemerédi's uniformity lemma[END_REF] and Moshkovitz and Shapira [START_REF] Moshkovitz | A short proof of Gowers' lower bound for the regularity lemma[END_REF], such graphs are usually too large for tractability. We remark that the stochastic block model (Definition 3) is a convenient choice for modeling ϵ-regular pairs because it is parametrized by the probabilities for edge assignments between every two communities.

We conjecture that a variant of a simple clustering algorithm (e.g., k-means clustering) could be designed in such a way that ϵ-regularity would be used as an index and lead to almost ϵ-regular pairs. If SiGo propagated only among vertices that belong to distinct sets of (almost) ϵ-regular pairs, the propagation would happen among vertices that have similar degrees. This way, we would reduce the bias between the average of individual values computed by SiGo and the true average of individual values, when the graph is non-regular.

Experiment A.2. We evaluate the convergence of SiGo by comparing the variance of estimates of µ d -1 over all agents, respectively, when the number of gossip iterations is the following: t go ∈ {2 4 , 2 10 , 2 11 }. We consider the convergence sufficient if the variance is below 10 -10 .

In Figure A.2 illustrates the results of Experiment A.1 on the synthetic graph dataset, which indicate that the MSE is lower when the shape parameter γ is lower. For a higher γ, most of the vertices are of the lowest degree, and the variance due to privatization is low due to bounding indicated by Equation 3.17. Such case is more strongly susceptible to underfitting because the regression model is fitted mostly with features of lower variance. A.1, the results of Experiment A.2 indicate that the variance of estimates of µ d -1 (over all agents) gets significantly low when the number t go of gossip iterations reaches 2 10 . This way, we conclude that 2 10 are enough of gossip iterations for each of the evaluated datasets. The variance gets lower for the email network dataset sooner because its diameter is lower.

Table A.1: Empirical evaluation of the convergence of SiGo. We compare of the variance of estimates of µ d -1 (over all agents) over several choices of the number t go of gossip iterations t go email network autonomous systems synthetic graph (n = 10 3 ) 2 4

≈ 10 -7 ≈ 10 -3 ≈ 10 -5 2 10 ≈ 10 -33 ≈ 10 -17 ≈ 10 -33 2 11

≈ 10 -33 ≈ 10 -30 ≈ 10 -33

2. 1

 1 Illustration of two probability density functions . . . . . . . . . . . 2.2 Illustration of three distinct graphs . . . . . . . . . . . . . . . . . . 2.3 Illustration of two observations of the ER random graph . . . . . . 2.4 Illustration of a distributed system without a central curator and a distributed system with a central curator . . . . . . . . . . . . . . . 2.5 Relation among the fields and the settings considered in the dissertation 3.1 Experiment 3.1 on the synthetic graph dataset . . . . . . . . . . . . 3.2 Experiment 3.2 on the synthetic dataset . . . . . . . . . . . . . . . 3.3 Experiment 3.2 on the real graph datasets . . . . . . . . . . . . . . 4.1 Experiment 4.1 on ds1 . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Experiment 4.1 on ds2a . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Experiment 4.1 on ds3 . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Experiment 4.2 on ds2b . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Experiment 4.2 on misra1d . . . . . . . . . . . . . . . . . . . . . . . 4.6 Comparison between equal distance discretization and equal frequency discretization on ds1 . . . . . . . . . . . . . . . . . . . . . . 4.7 Comparison between equal distance discretization and equal frequency discretization on ds2a . . . . . . . . . . . . . . . . . . . . . 4.8 Comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a (upon equal distance discretization) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.9 Comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a (upon equal frequency discretization) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.10 Comparison between a finer discretization and a coarser discretization of domains of privatized features on ds2a (upon equal distance discretization) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Remainder of Experiment 3.1 on the synthetic dataset . . . . . . . A.2 Comparison of the MSE between true target values and predicted target values over several choices of the shape parameter γ . . . . .List of Algorithms1 SimpleGossip (SiGo) . . . . . . . . . . . . . . . . . . . . . . . . . . 2 SimpleGossip for estimating a distribution . . . . . . . . . . . . . . 3 MetropolisHastingsGossip for estimating a distribution . . . . . . 4

Figure 2 . 3 :

 23 Figure 2.3: Illustration of two observations of the ER random graph, when n = 10 and p = 1 10 . For such ER random graph, as indicated by Equation 2.7, the probability of observing a vertex whose degree is 9 equals 1 10 9 , whereas the

Figure 2 . 5 :

 25 Figure 2.5: Relation among the fields and the settings considered in the dissertation. The arrows indicate that a field (or a setting) influences another field (or another setting). The ovals at the bottom (pointed at by dashed arrows) are settings that are outside (yet close to) the scope of this dissertation. The ovals at the center are settings that are part of the scope.

Definition 8 .

 8 Let ϵ, δ ≥ 0. A randomized algorithm A is (ϵ, δ)-edge-differentially private if and only if, for all S ⊆ image(A) and for all triples (D, D ′ , e) in a collection where adjacent datasets D, D ′ differ in an edge e, we have Pr(A(D) ∈ S) ≤ exp(ϵ) Pr(A(D ′ ) ∈ S) + δ.

  where µ d k and σ dp k are given, respectively, in Equation 3.18 and Equation 3.15. With high probability,

  where µ d k and σ dp k are given, respectively, in Equation 3.18 and Equation 3.15. Let us assume that

k and e

 e Cen k (given, respectively, by Equation 3.22 and Equation 3.40):

  Figure 3.1 illustrates the results of Experiment 3.1 on the synthetic graph dataset, which indicate that BCGo results in more noisy averages than Cen when k = 1/2, and in less noisy averages when k = 2. (The case with k = -1 is in Section A.3.) Upon k = 2, the reason of BCGo outperforming Cen is explained by the ratio in Equation 3.46 being sufficiently lower than 1.

Figure 3 . 1 :

 31 Figure 3.1: Comparison of the expected errors (Equation 3.22 and Equation 3.29) and the empirical errors (Equation 3.47 and Equation 3.48), when ϵ = 2 2 . k = 1/2 (left) and k = 2 (right) refer, respectively, to estimation of µ d 1/2 and µ d 2 (present in Equation 3.12).

Figure 3 .

 3 Figure 3.2 illustrates the results of Experiment 3.2 on the synthetic dataset, which indicate that BCGo performs better than Cen and SiGo. Essentially, BCGo requires lower privatization noise for averaging the feature d 2 i (in Equation 3.49) compared to Cen and SiGo. We remark that SiGo performs relatively well because the elements of each average (Equation 3.12 and Equation 3.13) for regularized least squares are scaled by the same factor d i µ d (as in Theorem 2), which leads to relatively accurate parameter estimates. The quantification of the bias in the parameter estimates computed by SiGo is outside the scope of this work.

Figure 3

 3 Figure 3.2: Comparison of the MSE between true target values and predicted target values (Equation 3.49), when averaging, respectively, by BCGo, SiGo, and Cen, and when n = 10 3

Figure 3 .

 3 Figure3.3 illustrates the results of Experiment 3.2 on the real graph datasets, which indicate that BCGo performs better than Cen and SiGo, except on the email network dataset upon a higher privacy budget. BCGo performs worse upon a higher privacy budget because the estimation of µ y involves privatization (unlike Cen and SiGo) and depends on µ d 2 and µ d k (Equation 3.44), where µ d 2 and µ d k are higher for the email network dataset compared to the autonomous systems dataset.

Figure 3

 3 Figure 3.3: Comparison of the MSE between true target values and predicted target values (Equation 3.49), when averaging, respectively, by BCGo, SiGo, and Cen. We use the email network dataset (left) and the autonomous systems dataset (right).

Figure 4 . 1 :

 41 Figure 4.1: Experiment 4.1 on ds1. (In the convex program, the discretized domain for Model tns • dp of TNM is in the logarithm scale.)

Figure 4 . 2 :

 42 Figure 4.2: Experiment 4.1 on ds2a. (In the convex program, the discretized domain for Model tns • dp of TNM is in the reciprocal scale.)

Figure 4 . 3 :

 43 Figure 4.3: Experiment 4.1 on ds3. (In the convex program, the discretized domain for Model tns • dp of TNM is in the tangent scale.)

Figure 4 . 4 :

 44 Figure 4.4: Experiment 4.2 on ds2b. (In the convex program, the discretized domain for Model tns • dp of TNM is in the reciprocal scale.)

Figure 4 . 5 :

 45 Figure 4.5: Experiment 4.2 on misra1d

Figure 4 . 6 :

 46 Figure 4.6: Comparison between equal distance discretization and equal frequency discretization on ds1

Figure 4 .

 4 Figure 4.7 illustrates a comparison between equal distance discretization and equal frequency discretization on ds2a. Equal frequency discretization fails to result in gradual improvement of utility over the evaluated privacy budget because it is not fine enough in the interval with high-magnitude gradients (the reciprocal transformation approaches its singularity relatively quickly).

Figure 4

 4 Figure 4.7: Comparison between equal distance discretization and equal frequency discretization on ds2a

Figure 4 .

 4 Figure 4.8 illustrates a comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a upon equal distance discretization. We observe that a finer discretization of sensitive features results in an improvement in utility for both Model tns • dp and Model dp • tns.

Figure 4

 4 Figure 4.8: Comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a (upon equal distance discretization)

Figure 4 . 9 :

 49 Figure 4.9: Comparison between a finer discretization and a coarser discretization of domains of sensitive features on ds2a (upon equal frequency discretization)

Figure

  Figure 4.10 illustrates a comparison between a finer discretization and a coarser discretization of domains of privatized features on ds2a upon equal distance discretization, when there is one additional bin between every two bins of sensitive features (interpolation) and there are two additional bins one of which is lower and the other is higher than any other bin of sensitive features (extrapolation).

Figure 4 .

 4 Figure 4.10: Comparison between a finer discretization and a coarser discretization of domains of privatized features on ds2a (upon equal distance discretization)

5. 1 .

 1 Summary of contributions Chapter 5. Summary and future directions We enumerate the advantages of the work on distributed averaging on graphs with arbitrary degree sequences: 1. Equation 3.44 and Equation 3.45 indicate that distributed averaging performed by the bias-correcting gossip algorithm (BCGo) can result in less privatization noise in comparison to the averaging function f (x) = 1 n i∈[n]

  The pair (C, C ′ ) is ϵ-regular if for all X ⊆ C and Y ⊆ C ′ , such that |X| ≥ ϵ|C| and |Y | ≥ ϵ|C ′ |, we have |den(X, Y ) -den(C, C ′ )| ≤ ϵ,

Figure A. 2 :

 2 Figure A.2: Comparison of the MSE between true target values and predicted target values over several choices of the shape parameter γ

Table 2 .

 2 2: Introduced notation of basic concepts of probability theory

	Notation	Meaning
	Ω	Sample space
	S	Set of events
	A, B	Events
	X, Y	Random variables

Table 2

 2

	.3: Introduced notation of basic concepts of graph theory
	Notation	Meaning

Table 2

 2

	.4: Introduced notation of basic concepts of machine learning
	Notation	Meaning
	X	Set of (all possible) examples
	Y	Set of (all possible) labels
	L	Loss function
	C	Concept space
	H	Hypothesis space
	h	Hypothesis
	ĥ	Empirical risk minimizer
	r	Hypothesis risk
	r	Empirical risk

  1 n i∈[n] x k i by µ x k . Similarly, for k, l ∈ R and x, y ∈ R n , we denote 1 n i∈[n] x k i y l i by µ x k .y l . The summaries of notation are provided in Table 2.1 and Table 2.3.

Table 4 .

 4 1: Notation related to sensitive features and privatized features

	Notation	Meaning
	X k,j	Discretized domain of a sensitive feature j for Model k
	Xk,j	Discretized domain of a privatized feature j for Model k
	x	Value of a sensitive feature
	x	Value of a privatized feature

Table 4 .

 4 2: Notation related to the work on tailored privatization

	Notation	Meaning
	n	Number of agents
	m	Number of features
	m ′	Number of attributes (m ′ ≤ m)
	X	Matrix of features and target values
	θ *	True parameters of a statistical model
	θ	Estimated parameters of a statistical model
	l	Number of models for estimating parameters of a statistical model
	mk	Number of sensitive features for Model k
	q k	Number of U-statistics for Model k
	g k	Function computing parameters of Model k from U-statistics
	f k,s	Function computing a U-statistic s for Model k from X
	L	Objective function

  and Cormode et al. [CKS17; CKS21] (the works are similar though Cormode et al. [CKS17;

Table 4 .

 4 3: Order and indices of constraint variables in the convex program

	Order Variable Index
	1

Table 4 .

 4 4: Total number of constraint variables.

	Variable	Total number	Total number (in experiments)

Table 4

 4

			.5: Order of linear equality constraints
		Order	Description	Reference
		1	Probabilities sum to 1 Equation 4.13
		Table 4.6: Order of linear inequality constraints
	Order		Description	Reference
	1		Differential privacy	Equation 4.8
	2	Probabilities are greater than 0	Equation 4.15
	3	Highest probabilities are less than or equal to 1 Equation 4.18

Table 4 .

 4 7: Total number of constraints. In our experiments, we use discretized domains of equal size. Implementation of the objective function. Regarding our objective function L (defined in Equation 4.19), we remind that it is composed of the objective function L vce k (Equation 4.21) for minimizing variance and the objective function L bias

	Reference	Total number	Total number (experiments)
	Equation 4.13	k∈[l],j∈[ mk ] |X k,j |	(m ′ + m)|X |
	Equation 4.8	k∈[l],j∈[ mk ] |X k,j || Xk,j |	(m ′ + m)|X || X |
	Equation 4.15	k∈[l],j∈[ mk ] |X k,j || Xk,j |	(m ′ + m)|X || X |
	Equation 4.18	k∈[l],j∈[ mk ] |X k,j || Xk,j |	(m ′ + m)|X || X |

k (Equation

Acknowledgements

I am thankful to Jan Ramon for the guidance throughout the work on this thesis.

List of Tables

That is, for α 1 , α 2 ∈ R, we have θµ

For a closer approximation of the non-linear regression model, the sum should be over more than two values (contrary to the case in Equation 4.27).

In Section 3.3 on averaging on arbitrary graphs, we have a regression model (Equation 3.10) with multiple features that can involve the reciprocal transformation. We remark that this motivates the applicability of the aforementioned dataset ds2b.

Experiment setup

In this subsection, we specify two sets of experiments.

Experiment 4.1. We compare the utility (MSE between true target values and predicted target values) of the regression models (Equation 4.25) fitted, respectively, by non-privatized features, features privatized by Laplace, and features privatized by TNM, when there is one feature computed from one attribute. Experiment 4.2. We compare the utility (MSE between true target values and predicted target values) of the regression models (Equation 4.25) fitted, respectively, by non-privatized features, features privatized by Laplace, and features privatized by TNM, when there are two features computed from one attribute.

In both experiments, we compare Model tns • dp (where attributes are privatized first and then the privatized attributes are transformed into features) to Model dp • tns (where attributes are transformed into features first and then the features are privatized).

We precise the experiment setup:

• We discretize domains of sensitive features and domains of privatized features in equal distance and 20 bins (respectively, |X| = 20 and | X| = 20).

, 2 4 , 2 5 , 2 6 } for evaluating the privacy budget. We recall that, usually, ϵ > 10 is too high for privacy in practice [START_REF] Hsu | Differential Privacy: An Economic Method for Choosing Epsilon[END_REF]. We fix the number of agents to n = 10 4 .

• We fix the tolerance of the constraint solver to 10 -7 . The solution of constraint solver is successful when primal infeasibility (pres), dual infeasibility (dres), and gap are lower than the fixed tolerance. For more details, we refer to cvxopt.org/userguide/solvers. (In experiment results, we indicate pres, dres, and gap which are the highest over the evaluated privacy budget). We fix the maximal number of iterations of the constraint solver to 2 7 .

Appendix A

Averaging on arbitrary graphs

A.1 Generation of graphs with power-law degree sequences

We describe a procedure for generating graphs with power-law degree sequences with the lowest degree d min = 3 and the highest degree d max = 10 2 :

1. We generate a power-law degree sequence

. . , d ′′ n are generated (drawn independently) from a probability distribution where a value d ′′ takes the following probability:

, where γ > 1 and the support of the probability distribution is the set {1, 2, . . . , d max -3}. We remark that a power-law degree sequence is characterized by a higher proportion of vertices being attributed with lower degrees and a lower proportion of vertices being attributed with higher degrees.

2. We generate a graph G ′ using the configuration model (Definition 4), where the configuration model is parametrized by the power-law degree sequence d ′′ . We denote the degree sequence of G ′ by d ′ .

For each

we add the edge {v i , v i+1 }; and, for i = n, we add the edge {v n , v 1 } which guarantees that the graph is connected. If, for example, the edge {v i , v i+1 } was already present, we would try to add a subsequent edge that is absent, i.e., we would check the edges {v i , v i+2 }, {v i , v i+3 }, . . ., {v i , v i-1 }. This guarantees that the degree of each vertex increases by 2. Further, if the edge {v 1 , v 3 } is absent, we add it also because this guarantees that there is at least one cycle of odd length in the graph, as the presence of the edges {v 1 , v 2 } and {v 2 , v 3 } is assured by the aforementioned procedure that connects the graph. Finally, if the degree of some vertices is still lower than 3, we add some arbitrary edges so that the degree of each vertex is at least 3. We denote the resulting graph by G and its degree sequence by d.

A.2. Variance of a bounded attribute Chapter A. Averaging on arbitrary graphs

Since the graph G is connected and has at least one cycle of odd length, the principles of DeGroot learning indicate that the averages computed by Algorithm 1 involve the values of all agents in the communication network and that Algorithm 1 converges.

A.2 Variance of a bounded attribute

We approximate the variance of a bounded (privatized) attribute by averaging the variances of truncated Gaussian random variables as follows:

where

A.4 Secondary experiments

We have performed two sets of secondary experiments.

Experiment A.1. Similarly as in Experiment 3.2, we compare the utility of the regression model fitted using the averages computed by BCGo, when degree sequences are generated, respectively, from the following shape parameters: γ ∈ {2, 3, 4}.

Index