Thesis Title: Post-processing in Differential Privacy

Thesis Committee:

Dr. Pascal Van Hentenryck (advisor), H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Mathieu Dahan, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Ferdinando Fioretto, Department of Computer Science, University of Virginia

Dr. Mohit Singh, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Dr. Juba Ziani, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology

Date and Time: Monday, November 13th, 1:00pm - 3:00pm (EST)

In-Person Location: Coda C1315 Grant Park

Meeting Link: https://teams.microsoft.com/l/meetup-join/19%3ameeting_MzkyZDY1ZGYtMzBlZi00OWM3LTllZDgtMDg3Mzk5NWMwZjU5%40thread.v2/0?context=%7b%22Tid%22%3a%22482198bb-ae7b-4b25-8b7a-6d7f32faa083%22%2c%22Oid%22%3a%22a93cede1-1521-497d-87a5-316246475612%22%7d

Join conversation

teams.microsoft.com

Meeting ID: 246 461 654 154
Passcode: HY3jv4

Abstract:

In recent years, the prominence of data privacy concerns has surged alongside the unprecedented growth in large-scale data collection and analysis. Since its introduction in 2006, differential privacy has rapidly emerged as the gold standard for addressing these escalating privacy challenges in both private industry and the public sector. One of its pivotal properties allows for arbitrary post-processing of data without compromising privacy, contributing to its great versatility and widespread adoption. Despite the extensive use of post-processing by researchers and practitioners, its impacts on outputs still remain poorly understood. This knowledge gap could potentially result in significant socio-economic consequences, particularly following the implementation of differential privacy in the 2020 U.S. decennial census. This thesis seeks to address this critical gap by conducting an in-depth analysis of post-processing in differential privacy, with a specific focus on accuracy, bias, and fairness.

Chapter 3 delves into the differentially private release of hierarchical data across multiple granularities. Within this context, the thesis proposes a variety of optimization-based post-processing mechanisms that are tailored to enhance the accuracy of released data while adhering to consistency constraints. The experimental results, based on extensive real datasets, highlight significant improvements over existing methods, including a substantial reduction in computational time and higher accuracy.

Chapter 4 investigates the bias introduced by post-processing, with an emphasis on the behavior of projection---a commonly used technique in practice. This study identifies sources of non-zero bias and establishes an upper bound on the projection-induced bias. Furthermore, the thesis proposes an algorithmic approach to effectively mitigate bias.

Chapter 5 recognizes the disparate errors observed in post-processed outcomes as a fairness issue and analyzes two critical settings: data release and downstream decisions. In the first setting, the thesis presents tight bounds on the unfairness for traditional post-processing mechanisms, providing decision makers with a valuable tool to quantify the disparate impacts introduced by their data releases. In the second setting, this study concentrates on the fund allocation problem and proposes a novel post-processing mechanism that is near-optimal under different fairness metrics.