Detailansicht
Maximizing Fisher information in $\epsilon$-differential privacy mechanisms
Matej Vedak
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Computational Science
Betreuer*in
Lukas Steinberger
DOI
10.25365/thesis.78096
URN
urn:nbn:at:at-ubw:1-16819.54496.420889-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Lokale differentielle Privatsphäre (LDP) hat sich als führendes Framework zum Schutz persönlicher Informationen etabliert, selbst gegenüber nicht vertrauenswürdigen Datenanalysten. Obwohl viele Mechanismen die ε-LDP-Bedingungen erfüllen, variiert ihr Nutzen für die statistische Schätzung erheblich. Um dies zu adressieren, maximieren wir die Fisher-Information innerhalb der Menge der ε-LDP-Mechanismen, wodurch die Effizienz nachfolgender statistischer Parameterschätzungen sichergestellt wird. Bisherige Ansätze basierten auf linearer Programmierung mit exponentieller Komplexität $O(2^k)$ (wobei $k=∣\mathscr{X}∣$ die Kardinalität des Eingabealphabets ist), was die praktische Anwendung auf kleine Eingabealphabete beschränkte. Wir entwickeln einen projizierten Gradientenanstiegsalgorithmus mit Kantendurchlauf (PGAET), der eine polynomiale Komplexität von $O(k^9)$ aufweist und somit Optimierungen in hochdimensionalen Kontexten ermöglicht. Wir demonstrieren seine Effizienz anhand diskreter (Poisson) und kontinuierlicher Verteilungen (Cauchy) durch Diskretisierungs- und Approximationsverfahren. Unsere Ergebnisse erweitern die bisher bekannten Resultate auf Eingabealphabetgrößen bis $k=30$, was eine deutliche Verbesserung gegenüber früheren Arbeiten darstellt. Diese Arbeit bietet Forschenden eine Methode, um Datenschutzmechanismen mit größeren Eingabealphabeten zu entwickeln, die gleichzeitig effiziente statistische Schätzungen ermöglichen.
Abstract
(Englisch)
Local differential privacy (LDP) has emerged as a leading framework of personal information protection, even from untrusted data analysts. While many mechanisms satisfy $\epsilon$-privacy constraints, their utility for statistical estimation varies significantly. To address this, we maximize Fisher information over the set of $\epsilon$-LDP mechanisms, ensuring efficiency in subsequent statistical parameter estimates. Prior approaches relied on linear programming with exponential complexity $O(2^k)$ ($k=|\mathscr{X}|$, input alphabet cardinality), limiting practical applications to small input alphabets. We develop a projected gradient ascent algorithm with edge traversal (PGAET) that achieves polynomial complexity $O(k^9)$, enabling optimization in high-dimensional settings. We demonstrate its efficiency on discrete (Poisson) and continuous distributions (Cauchy) via discretization and approximation techniques. We extend previously known results to input alphabet sizes up to $k=30$, a significant improvement over previously known results. Our work provides a method for researchers to investigate and construct privacy mechanisms with larger input alphabets that retain efficiency in statistical estimation.
Schlagwörter
Schlagwörter
(Deutsch)
Konvexe Optimierung Projizierter Gradientenanstieg Optimierung in der Differenziellen Privatsphäre Fisher-Information
Schlagwörter
(Englisch)
Convex Optimization Projected Gradient Ascent Optimization in Differential Privacy Fisher Information
Autor*innen
Matej Vedak 
Haupttitel (Englisch)
Maximizing Fisher information in $\epsilon$-differential privacy mechanisms
Publikationsjahr
2025
Umfangsangabe
34 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*in
Lukas Steinberger
Klassifikationen
31 Mathematik > 31.73 Mathematische Statistik ,
31 Mathematik > 31.80 Angewandte Mathematik
AC Nummer
AC17482437
Utheses ID
74976
Studienkennzahl
UA | 066 | 910 | |