Privacy-preserving learning by averaging in collaborative networks
Calcul des moyennes dans des réseaux collaboratifs pour l'apprentissage automatique et préservant la confidentialité
Résumé
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 $mathcal{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 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.
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 réalisé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 effectuer 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 $mathcal{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é.
Origine : Version validée par le jury (STAR)